lucene::util::PriorityQueue< _type, _valueDeletor > Class Template Reference
A PriorityQueue maintains a partial ordering of its elements such that the least element can always be found in constant time. More...
#include <PriorityQueue.h>
Public Member Functions | |
| virtual | ~PriorityQueue () |
| void | put (_type element) |
| Adds an Object to a PriorityQueue in log(size) time. | |
| bool | insert (_type element) |
| Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()). | |
| _type | insertWithOverflow (_type element) |
| insertWithOverflow() is the same as insert() except its return value: it returns the object (if any) that was dropped off the heap because it was full. | |
| _type | top () |
| Returns the least element of the PriorityQueue in constant time. | |
| _type | pop () |
| Removes and returns the least element of the PriorityQueue in log(size) time. | |
| void | adjustTop () |
| Should be called when the object at top changes values. | |
| size_t | size () |
| Returns the number of elements currently stored in the PriorityQueue. | |
| void | clear () |
| Removes all entries from the PriorityQueue. | |
Protected Member Functions | |
| PriorityQueue () | |
| virtual bool | lessThan (_type a, _type b)=0 |
| void | initialize (const int32_t maxSize, bool deleteOnClear) |
Protected Attributes | |
| _type * | heap |
Detailed Description
template<class _type, typename _valueDeletor>
class lucene::util::PriorityQueue< _type, _valueDeletor >
A PriorityQueue maintains a partial ordering of its elements such that the least element can always be found in constant time.
Put()'s and pop()'s require log(size) time.
Constructor & Destructor Documentation
| lucene::util::PriorityQueue< _type, _valueDeletor >::PriorityQueue | ( | ) | [inline, protected] |
| virtual lucene::util::PriorityQueue< _type, _valueDeletor >::~PriorityQueue | ( | ) | [inline, virtual] |
Member Function Documentation
| virtual bool lucene::util::PriorityQueue< _type, _valueDeletor >::lessThan | ( | _type | a, | |
| _type | b | |||
| ) | [protected, pure virtual] |
| void lucene::util::PriorityQueue< _type, _valueDeletor >::initialize | ( | const int32_t | maxSize, | |
| bool | deleteOnClear | |||
| ) | [inline, protected] |
| void lucene::util::PriorityQueue< _type, _valueDeletor >::put | ( | _type | element | ) | [inline] |
Adds an Object to a PriorityQueue in log(size) time.
If one tries to add more objects than maxSize from initialize a RuntimeException (ArrayIndexOutOfBound) is thrown.
| bool lucene::util::PriorityQueue< _type, _valueDeletor >::insert | ( | _type | element | ) | [inline] |
Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()).
- Parameters:
-
element
- Returns:
- true if element is added, false otherwise.
| _type lucene::util::PriorityQueue< _type, _valueDeletor >::insertWithOverflow | ( | _type | element | ) | [inline] |
insertWithOverflow() is the same as insert() except its return value: it returns the object (if any) that was dropped off the heap because it was full.
This can be the given parameter (in case it is smaller than the full heap's minimum, and couldn't be added), or another object that was previously the smallest value in the heap and now has been replaced by a larger one, or null if the queue wasn't yet full with maxSize elements. NOTE: value is not being deleted - its the user responsibilty to dispose the returned _type (only if != NULL && != element).
| _type lucene::util::PriorityQueue< _type, _valueDeletor >::top | ( | ) | [inline] |
Returns the least element of the PriorityQueue in constant time.
| _type lucene::util::PriorityQueue< _type, _valueDeletor >::pop | ( | ) | [inline] |
Removes and returns the least element of the PriorityQueue in log(size) time.
| void lucene::util::PriorityQueue< _type, _valueDeletor >::adjustTop | ( | ) | [inline] |
Should be called when the object at top changes values.
Still log(n) worst case, but it's at least twice as fast to
{ pq.top().change(); pq.adjustTop(); }
instead of
{ o = pq.pop(); o.change(); pq.push(o); }
| size_t lucene::util::PriorityQueue< _type, _valueDeletor >::size | ( | ) | [inline] |
Returns the number of elements currently stored in the PriorityQueue.
| void lucene::util::PriorityQueue< _type, _valueDeletor >::clear | ( | ) | [inline] |
Removes all entries from the PriorityQueue.
Field Documentation
_type* lucene::util::PriorityQueue< _type, _valueDeletor >::heap [protected] |
The documentation for this class was generated from the following file: