Program Listing for File IndexedDaryHeap.h

↰ Return to documentation for file (ADS/priority/IndexedDaryHeap.h)

/*--------------------------------------------------------------------------*/
/*------------------------- File IndexedDaryHeap.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_IndexedDaryHeap
 #define __ADS_IndexedDaryHeap
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"

#include <cstddef>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS IndexedDaryHeap --------------------------*/
/*--------------------------------------------------------------------------*/

template< class K , unsigned D = 4 >
class IndexedDaryHeap {

 static_assert( D >= 2 , "a heap needs at least two children per node" );

/*--------------------------------------------------------------------------*/
 public:

 using Key = K;
 using Item = int;
 using Priority = K;
 using Handle = int;

 struct Entry {
  K key;
  int id;
  };

 explicit IndexedDaryHeap( int n = 0 );

 void reset( int n );

 [[nodiscard]] int ids( void ) const { return( int( f_pos.size() ) ); }

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

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

 [[nodiscard]] bool contains( int id ) const;

 [[nodiscard]] const K & key( int id ) const;

 void push( int id , const K & k );

 void decrease( int id , const K & k );

 bool pushOrDecrease( int id , const K & k );

 [[nodiscard]] const Entry & top( void ) const;

 Entry pop( void );

 void clear( void );

 Handle insert( int id , const K & k ) {
  push( id , k );
  return( id );
  }

 [[nodiscard]] int min( void ) const { return( top().id ); }

 int deleteMin( void ) { return( pop().id ); }

/*--------------------------------------------------------------------------*/
 private:

 void up( std::size_t i , Entry x );

 void down( std::size_t i , Entry x );

 [[nodiscard]] bool ordered( void ) const;

 std::vector< Entry > f_A;
 std::vector< int > f_pos;

 };  // end( class IndexedDaryHeap )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/priority/impl/IndexedDaryHeap.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* IndexedDaryHeap.h included */

/*--------------------------------------------------------------------------*/
/*----------------------- End File IndexedDaryHeap.h -----------------------*/
/*--------------------------------------------------------------------------*/