Program Listing for File ListPriorityQueue.h

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

/*--------------------------------------------------------------------------*/
/*------------------------ File ListPriorityQueue.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/priority/PriorityQueue.h"
#include "ADS/sequence/List.h"

#include <concepts>
#include <cstddef>
#include <utility>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS ListPriorityQueue -------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , std::totally_ordered P = int , bool Sorted = true >
class ListPriorityQueue {

 using Pair = std::pair< P , T >;

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

 using Item = T;
 using Priority = P;
 using Handle = typename List< Pair >::Pos;

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

 [[nodiscard]] int size( void ) const;

 [[nodiscard]] const T & min( void ) const;

 T deleteMin( void );

 Handle insert( const T & x , const P & p );

 void decrease( Handle & y , const P & p );

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 // a constant view of the pairs ( priority , item ), by priority when the
 // list is sorted, bidirectional; a change through it would break the order

 using value_type = Pair;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = const Pair &;
 using const_reference = const Pair &;
 using iterator = typename List< Pair >::const_iterator;
 using const_iterator = typename List< Pair >::const_iterator;

 [[nodiscard]] const_iterator begin( void ) const { return( f_L.begin() ); }
 [[nodiscard]] const_iterator end( void ) const { return( f_L.end() ); }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 [[nodiscard]] Handle first( void ) const;

 [[nodiscard]] Handle after( const P & p ) const;

 [[nodiscard]] bool owns( Handle y ) const;

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

 List< Pair > f_L;
 int f_size = 0;

 };  // end( class ListPriorityQueue )

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

}  // end( namespace ADS )

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

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

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

#endif  /* ListPriorityQueue.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File ListPriorityQueue.h ----------------------*/
/*--------------------------------------------------------------------------*/