OpenList.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*---------------------------- File OpenList.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_ads_OpenList
 #define __PBeFS_ads_OpenList
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <cstddef>
 
#include <type_traits>
 
#include "ADS/priority/BucketQueue.h"
 
#include "ADS/priority/DaryHeap.h"
 
#include "PBeFS/astar/OpenList.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS HeapOpenList ---------------------------*/
/*--------------------------------------------------------------------------*/
template< class NodeT , unsigned Arity = 4 >
class HeapOpenList {
 
 using Cost = decltype( NodeT::g );
 
 public:

 
 void push( NodeT * node ) { push( node , node->g ); }

 
 void push( NodeT * node , Cost g ) {
  f_heap.push( Item{ g + node->h , g , node } );
  }

 
 [[nodiscard]] OpenEntry< NodeT > top( void ) const {
  return( OpenEntry< NodeT >{ f_heap.top().node , f_heap.top().g } );
  }

 
 [[nodiscard]] Cost top_f( void ) const { return( f_heap.top().f ); }

 
 OpenEntry< NodeT > pop( void ) {
  const Item x = f_heap.pop();
  return( OpenEntry< NodeT >{ x.node , x.g } );
  }

 
 [[nodiscard]] bool empty( void ) const noexcept {
  return( f_heap.empty() );
  }

 
 [[nodiscard]] std::size_t size( void ) const noexcept {
  return( f_heap.size() );
  }
 
 private:

 struct Item {
  Cost f;
  Cost g;
  NodeT * node;
  };

 struct Better {
  bool operator()( const Item & a , const Item & b ) const noexcept {
   return( ( a.f < b.f ) || ( ( a.f == b.f ) && ( a.g > b.g ) ) );
   }
  };
 
 ADS::DaryHeap< Item , Better , Arity > f_heap;         
 
 };  // end( class( HeapOpenList ) )
 
/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS BucketOpenList --------------------------*/
/*--------------------------------------------------------------------------*/
template< class NodeT >
class BucketOpenList {
 
 using Cost = decltype( NodeT::g );
 
 static_assert( std::is_integral_v< Cost > ,
                "BucketOpenList requires an integer cost type" );
 
 public:

 
 void push( NodeT * node ) { push( node , node->g ); }

 
 void push( NodeT * node , Cost g ) { f_queue.push( node , g + node->h , g ); }

 
 [[nodiscard]] OpenEntry< NodeT > top( void ) {
  return( OpenEntry< NodeT >{ f_queue.top() , f_queue.topG() } );
  }

 
 [[nodiscard]] Cost top_f( void ) { return( f_queue.topF() ); }

 
 OpenEntry< NodeT > pop( void ) {
  const auto e = f_queue.popEntry();
  return( OpenEntry< NodeT >{ e.item , e.g } );
  }

 
 [[nodiscard]] bool empty( void ) const noexcept {
  return( f_queue.empty() );
  }

 
 [[nodiscard]] std::size_t size( void ) const noexcept {
  return( f_queue.size() );
  }
 
 private:
 
 ADS::BucketQueue< NodeT * , Cost > f_queue;               
 
 };  // end( class( BucketOpenList ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_ads_OpenList */
 
/*--------------------------------------------------------------------------*/
/*-------------------------- End File OpenList.h ---------------------------*/
/*--------------------------------------------------------------------------*/