Generated on Tue Dec 16 13:35:10 2008 for ell-3.0.0 by doxygen 1.5.1
ell::util::PriorityQueue

ell::util::PriorityQueue< QV, QK, CompareKey > Class Template Reference

#include <PriorityQueue.hh>

Detailed Description

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
class ell::util::PriorityQueue< QV, QK, CompareKey >

Implements a priority queue of compressed states that are ordered according to their energy (using lexicographical order on compressed string representation as tiebreaker). The top() element corresponds to the state with the smallest energy in the queue.

Definition at line 36 of file PriorityQueue.hh.

Public Types

typedef InternalPQtype::const_iterator const_iterator
typedef std::pair< iterator,
bool > 		InsertResult
typedef InternalPQtype::iterator iterator
typedef QK QueueKey
typedef QV QueueValue
typedef InternalPQtype::size_type size_type

Public Member Functions

iterator begin (void)
const_iterator begin (void) const
bool empty (void) const
iterator end (void)
const_iterator end (void) const
void erase (const QK &key)
void erase (const State *s)
iterator find (const QK &key)
const_iterator find (const QK &key) const
iterator find (const State *s)
const_iterator find (const State *s) const
double getMaxE (void) const
InsertResult insert (const QK &key)
InsertResult insert (const State *keyState)
void pop (void)
 PriorityQueue ()
void reduceMaxE (const double maxE)
size_type size (void) const
const_iterator top (void) const
virtual ~PriorityQueue ()

Protected Types

typedef std::map< QK, QV,
CompareKey > 		InternalPQtype

Protected Attributes

InternalPQtype pq

Member Typedef Documentation

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
typedef InternalPQtype::const_iterator ell::util::PriorityQueue< QV, QK, CompareKey >::const_iterator

constant iterator to a <QK, T> pair of the queue

Definition at line 54 of file PriorityQueue.hh.

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
typedef std::pair<iterator, bool> ell::util::PriorityQueue< QV, QK, CompareKey >::InsertResult

Result type of insertion operation.

Definition at line 60 of file PriorityQueue.hh.

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
typedef std::map< QK, QV, CompareKey > ell::util::PriorityQueue< QV, QK, CompareKey >::InternalPQtype [protected]

shortcut for the internal priority queue data structure

Definition at line 46 of file PriorityQueue.hh.

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
typedef InternalPQtype::iterator ell::util::PriorityQueue< QV, QK, CompareKey >::iterator

iterator to a <QK,QueueVal> pair of the queue

Definition at line 56 of file PriorityQueue.hh.

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
typedef QK ell::util::PriorityQueue< QV, QK, CompareKey >::QueueKey

Definition at line 42 of file PriorityQueue.hh.

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
typedef QV ell::util::PriorityQueue< QV, QK, CompareKey >::QueueValue

Definition at line 41 of file PriorityQueue.hh.

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
typedef InternalPQtype::size_type ell::util::PriorityQueue< QV, QK, CompareKey >::size_type

size type of the queue

Definition at line 58 of file PriorityQueue.hh.

Constructor & Destructor Documentation

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
ell::util::PriorityQueue< QV, QK, CompareKey >::PriorityQueue (  ) 

construction

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
virtual ell::util::PriorityQueue< QV, QK, CompareKey >::~PriorityQueue (  )  [virtual]

destruction

Member Function Documentation

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
iterator ell::util::PriorityQueue< QV, QK, CompareKey >::begin ( void   ) 

returns an iterator to the top() element of the queue

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
const_iterator ell::util::PriorityQueue< QV, QK, CompareKey >::begin ( void   )  const

returns a constant iterator to the top() element of the queue

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
bool ell::util::PriorityQueue< QV, QK, CompareKey >::empty ( void   )  const

Whether or not the queue contains no elements

Returns:
true if size()==0 and false otherwise

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
iterator ell::util::PriorityQueue< QV, QK, CompareKey >::end ( void   ) 

returns an iterator behind the last element of the queue

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
const_iterator ell::util::PriorityQueue< QV, QK, CompareKey >::end ( void   )  const

returns a constant iterator behind the last element of the queue

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
void ell::util::PriorityQueue< QV, QK, CompareKey >::erase ( const QK &  key  ) 

Erases the key/value pair of the given key

Parameters:
key the key to erase the key/value pair of

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
void ell::util::PriorityQueue< QV, QK, CompareKey >::erase ( const State *  s  ) 

Erases the key/value pair representing the given state

Parameters:
s the state of that the key/value pair is to erase

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
iterator ell::util::PriorityQueue< QV, QK, CompareKey >::find ( const QK &  key  ) 

Returns an iterator to the queue element representing s or end() otherwise.

Parameters:
key the key to find
Returns:
iterator to the element or end() if not found

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
const_iterator ell::util::PriorityQueue< QV, QK, CompareKey >::find ( const QK &  key  )  const

Returns a constant iterator to the queue element representing s or end() otherwise.

Parameters:
key the key to find
Returns:
constant iterator to the element or end() if not found

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
iterator ell::util::PriorityQueue< QV, QK, CompareKey >::find ( const State *  s  ) 

Returns an iterator to the queue element representing s or end() otherwise.

Parameters:
s the state of which the representation has to be found
Returns:
iterator to the element or end() if not found

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
const_iterator ell::util::PriorityQueue< QV, QK, CompareKey >::find ( const State *  s  )  const

Returns a constant iterator to the queue element representing s or end() otherwise.

Parameters:
s the state of which the representation has to be found
Returns:
constant iterator to the element or end() if not found

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
double ell::util::PriorityQueue< QV, QK, CompareKey >::getMaxE ( void   )  const

Returns the maximal energy stored in the queue

Returns:
the energy of the last queue element

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
InsertResult ell::util::PriorityQueue< QV, QK, CompareKey >::insert ( const QK &  key  ) 

Inserts an empty QueueValue for the given key. The new QueueValue object is created and can be filled afterwards using the provided iterator. NOTE: An already existing QueueValue object for the given key will be overwritten!

Parameters:
key the key a new value is to be inserted
Returns:
(first) the iterator to the (newly created) QueueValue object and (second) a boolean that is true if the value was created and NOT already part of the queue.

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
InsertResult ell::util::PriorityQueue< QV, QK, CompareKey >::insert ( const State *  keyState  ) 

Inserts a key/value pair to the queue using the given information. A new QueueValue object is created and can be filled afterwards using the provided iterator. NOTE: An already existing QueueValue object for the given key will be overwritten!

Parameters:
keyState the state that is to be inserted as a key
Returns:
(first) the iterator to the (newly created) QueueValue object and (second) a boolean that is true if the value was created and NOT already part of the queue.

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
void ell::util::PriorityQueue< QV, QK, CompareKey >::pop ( void   ) 

deletes the top element of the queue

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
void ell::util::PriorityQueue< QV, QK, CompareKey >::reduceMaxE ( const double  maxE  ) 

Deletes all elements from the queue with key.E > maxE

Parameters:
maxE the energy to that all elements of the queue should be smaller

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
size_type ell::util::PriorityQueue< QV, QK, CompareKey >::size ( void   )  const

the number of elements in the queue

Returns:
the number of elements

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
const_iterator ell::util::PriorityQueue< QV, QK, CompareKey >::top ( void   )  const

returns the top element of the queue which is the top() element

Field Documentation

template<class QV, class QK = QueueKey, typename CompareKey = std::less<QK>>
InternalPQtype ell::util::PriorityQueue< QV, QK, CompareKey >::pq [protected]

the internal priority queue data structure

Definition at line 49 of file PriorityQueue.hh.

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