Program Listing for File BucketQueue.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File BucketQueue.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <concepts>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS BucketQueue -----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , std::integral K = int >
class BucketQueue {

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

 using Item = T;
 using Key = K;

 void push( const T & x , K f , K g );

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

 [[nodiscard]] K topF( void );

 [[nodiscard]] K topG( void );

 T pop( void );

 struct Entry {
  T item;
  K f , g;
  };

 Entry popEntry( void );

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

 [[nodiscard]] std::size_t size( void ) const;

 void clear( void );

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

 using Index = std::uint32_t;
 static constexpr Index NIL = ~Index( 0 );
 static constexpr std::size_t S = 4;

 struct Cell {
  T item;
  Index next;
  };

 struct Layer {
  Index count = 0;
  Index topG = 0;
  Index small[ S ] = { NIL , NIL , NIL , NIL };
  std::vector< Index > big;

  Index & head( std::size_t g ) {
   return( g < S ? small[ g ] : big[ g - S ] );
   }
  Index head( std::size_t g ) const {
   return( g < S ? small[ g ] : g - S < big.size() ? big[ g - S ] : NIL );
   }
  std::size_t lists( void ) const { return( S + big.size() ); }
  };

 public:

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

 // a constant view of the items in the order of the extractions (by f
 // increasing, then by g decreasing, each list from the last item pushed),
 // forward; it skips the empty lists without touching the lazy bounds that
 // top() moves

 class const_iterator {
  public:
  using iterator_category = std::forward_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using reference = const T &;
  using pointer = const T *;

  const_iterator( void ) = default;
  const_iterator( const BucketQueue * q , std::size_t f )
   : f_q( q ) , f_f( f ) { settle(); }

  reference operator*( void ) const { return( f_q->f_cells[ f_c ].item ); }
  pointer operator->( void ) const { return( &**this ); }

  const_iterator & operator++( void ) {
   f_c = f_q->f_cells[ f_c ].next;
   if( f_c == NIL ) {
    ++f_g;
    settle();
    }
   return( *this );
   }
  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }

  bool operator==( const const_iterator & o ) const {
   return( ( f_f == o.f_f ) && ( f_g == o.f_g ) && ( f_c == o.f_c ) );
   }

  private:
  void settle( void ) {
   const auto & L = f_q->f_layers;
   for( ; f_f < L.size() ; ++f_f , f_g = 0 ) {
    const Layer & l = L[ f_f ];
    if( l.count )
     for( ; f_g < l.lists() ; ++f_g )
      if( ( f_c = l.head( l.lists() - 1 - f_g ) ) != NIL ) return;
    }
   f_g = 0;
   f_c = NIL;
   }

  const BucketQueue * f_q = nullptr;
  std::size_t f_f = 0 , f_g = 0;
  Index f_c = NIL;
  };

 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = const T &;
 using const_reference = const T &;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , 0 ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , f_layers.size() ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 private:

 Layer & front( void );

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

 std::vector< Layer > f_layers;
 std::vector< Cell > f_cells;
 Index f_free = NIL;
 std::size_t f_minF = 0;
 std::size_t f_size = 0;

 };  // end( class BucketQueue )

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

}  // end( namespace ADS )

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

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

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

#endif  /* BucketQueue.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File BucketQueue.h -------------------------*/
/*--------------------------------------------------------------------------*/