All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
Aux::BucketPQ Class Reference

Addressable priority queue for values in the range [0,n) and integer keys (= priorities) in the range [minPrio, maxPrio]. More...

#include <BucketPQ.h>

Public Member Functions

 BucketPQ (const std::vector< int64_t > &keys, int64_t minAdmissibleKey, int64_t maxAdmissibleKey)
 Builds priority queue from the vector keys, values are indices of keys. More...
 
 BucketPQ (uint64_t capacity, int64_t minAdmissibleKey, int64_t maxAdmissibleKey)
 Builds priority queue of the specified capacity capacity. More...
 
virtual ~BucketPQ ()=default
 Default destructor. More...
 
virtual void insert (int64_t key, index value) override
 Inserts key-value pair (, ). More...
 
virtual std::pair< int64_t, indexextractMin () override
 Removes the element with minimum key and returns the key-value pair. More...
 
virtual void changeKey (int64_t newKey, index value) override
 Modifies entry with value value. More...
 
virtual uint64_t size () const override
 
virtual void remove (const index &val) override
 Removes key-value pair given by value val. More...
 
- Public Member Functions inherited from Aux::PrioQueue< int64_t, index >
 PrioQueue (const std::vector< int64_t > &keys)
 Builds priority queue from the vector keys, values are indices of keys. More...
 
 PrioQueue (uint64_t capacity)
 Builds priority queue of the specified capacity capacity. More...
 
virtual ~PrioQueue ()=default
 Default destructor. More...
 
virtual void decreaseKey (int64_tnewKey, indexvalue)
 
virtual void print ()
 DEBUGGING. More...
 

Additional Inherited Members

- Protected Member Functions inherited from Aux::PrioQueue< int64_t, index >
 PrioQueue ()=default
 Default constructor without functionality. More...
 
virtual void remove (const ElemType &elem)
 Removes key-value pair given by elem. More...
 
virtual std::set< std::pair
< int64_t, index > > 
content () const
 

Detailed Description

Addressable priority queue for values in the range [0,n) and integer keys (= priorities) in the range [minPrio, maxPrio].

minPrio and maxPrio can be positive or negative, respectively with the obvious constraint minPrio <= maxPrio. Amortized constant running time for each operation.

Constructor & Destructor Documentation

Aux::BucketPQ::BucketPQ ( const std::vector< int64_t > &  keys,
int64_t  minAdmissibleKey,
int64_t  maxAdmissibleKey 
)

Builds priority queue from the vector keys, values are indices of keys.

Parameters
[in]keysVector of keys
[in]minAdmissibleKeyMinimum admissible key
[in]maxAdmissibleKeyMaximum admissible key
Aux::BucketPQ::BucketPQ ( uint64_t  capacity,
int64_t  minAdmissibleKey,
int64_t  maxAdmissibleKey 
)

Builds priority queue of the specified capacity capacity.

virtual Aux::BucketPQ::~BucketPQ ( )
virtualdefault

Default destructor.

Member Function Documentation

void Aux::BucketPQ::changeKey ( int64_t  newKey,
index  value 
)
overridevirtual

Modifies entry with value value.

The entry is then set to newKey with the same value. If the corresponding key is not present, the element will be inserted.

Reimplemented from Aux::PrioQueue< int64_t, index >.

std::pair< int64_t, index > Aux::BucketPQ::extractMin ( )
overridevirtual

Removes the element with minimum key and returns the key-value pair.

Reimplemented from Aux::PrioQueue< int64_t, index >.

void Aux::BucketPQ::insert ( int64_t  key,
index  value 
)
overridevirtual

Inserts key-value pair (, ).

Reimplemented from Aux::PrioQueue< int64_t, index >.

void Aux::BucketPQ::remove ( const index val)
overridevirtual

Removes key-value pair given by value val.

Reimplemented from Aux::PrioQueue< int64_t, index >.

uint64_t Aux::BucketPQ::size ( ) const
overridevirtual
Returns
Number of elements in PQ.

Reimplemented from Aux::PrioQueue< int64_t, index >.


The documentation for this class was generated from the following files: