Lucene++ - a full-featured, c++ search engine
API Documentation
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. More...
#include <PriorityQueue.h>
Public Types | |
typedef std::vector< TYPE > | heap_type |
Public Member Functions | |
PriorityQueue (int32_t maxSize) | |
virtual | ~PriorityQueue () |
virtual void | initialize () |
Called directly after instantiation to create objects that depend on this object being fully constructed. | |
int32_t | maxSize () |
Return maximum size of queue. | |
TYPE | add (const TYPE &type) |
Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize an IndexOutOfBoundsException is thrown. | |
TYPE | addOverflow (const TYPE &type) |
Adds an Object to a PriorityQueue in log(size) time. 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. | |
TYPE | top () |
Returns the least element of the PriorityQueue. | |
TYPE | pop () |
Removes and returns the least element of the PriorityQueue. | |
TYPE | updateTop () |
Should be called when the Object at top changes values. | |
int32_t | size () const |
Returns the number of elements currently stored in the PriorityQueue. | |
bool | empty () const |
Returns whether PriorityQueue is currently empty. | |
void | clear () |
Removes all entries from the PriorityQueue. | |
![]() | |
virtual | ~LuceneObject () |
virtual LuceneObjectPtr | clone (const LuceneObjectPtr &other=LuceneObjectPtr()) |
Return clone of this object. | |
virtual int32_t | hashCode () |
Return hash code for this object. | |
virtual bool | equals (const LuceneObjectPtr &other) |
Return whether two objects are equal. | |
virtual int32_t | compareTo (const LuceneObjectPtr &other) |
Compare two objects. | |
virtual String | toString () |
Returns a string representation of the object. | |
![]() | |
virtual | ~LuceneSync () |
virtual SynchronizePtr | getSync () |
Return this object synchronize lock. | |
virtual LuceneSignalPtr | getSignal () |
Return this object signal. | |
virtual void | lock (int32_t timeout=0) |
Lock this object using an optional timeout. | |
virtual void | unlock () |
Unlock this object. | |
virtual bool | holdsLock () |
Returns true if this object is currently locked by current thread. | |
virtual void | wait (int32_t timeout=0) |
Wait for signal using an optional timeout. | |
virtual void | notifyAll () |
Notify all threads waiting for signal. | |
Protected Member Functions | |
void | upHeap () |
void | downHeap () |
virtual bool | lessThan (const TYPE &first, const TYPE &second) |
Determines the ordering of objects in this priority queue. Subclasses must define this one method. | |
virtual TYPE | getSentinelObject () |
This method can be overridden by extending classes to return a sentinel object which will be used by initialize to fill the queue, so that the code which uses that queue can always assume it's full and only change the top without attempting to insert any new object. | |
![]() | |
LuceneObject () | |
Protected Attributes | |
heap_type | heap |
int32_t | _size |
int32_t | _maxSize |
![]() | |
SynchronizePtr | objectLock |
LuceneSignalPtr | objectSignal |
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.
NOTE: This class pre-allocates a full array of length maxSize + 1.
typedef std::vector<TYPE> Lucene::PriorityQueue< TYPE >::heap_type |
|
inline |
|
inlinevirtual |
|
inline |
Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize an IndexOutOfBoundsException
is thrown.
References Lucene::PriorityQueue< TYPE >::_size, Lucene::PriorityQueue< TYPE >::heap, and Lucene::PriorityQueue< TYPE >::upHeap().
Referenced by Lucene::PriorityQueue< TYPE >::addOverflow().
|
inline |
Adds an Object to a PriorityQueue in log(size) time. 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.
References Lucene::PriorityQueue< TYPE >::_maxSize, Lucene::PriorityQueue< TYPE >::_size, Lucene::PriorityQueue< TYPE >::add(), Lucene::PriorityQueue< TYPE >::heap, Lucene::PriorityQueue< TYPE >::lessThan(), and Lucene::PriorityQueue< TYPE >::updateTop().
|
inline |
Removes all entries from the PriorityQueue.
References Lucene::PriorityQueue< TYPE >::_size, and Lucene::PriorityQueue< TYPE >::heap.
|
inlineprotected |
|
inline |
Returns whether PriorityQueue is currently empty.
References Lucene::PriorityQueue< TYPE >::_size.
Referenced by Lucene::PriorityQueue< TYPE >::initialize().
|
inlineprotectedvirtual |
This method can be overridden by extending classes to return a sentinel object which will be used by initialize
to fill the queue, so that the code which uses that queue can always assume it's full and only change the top without attempting to insert any new object.
Those sentinel values should always compare worse than any non-sentinel value (ie., lessThan
should always favour the non-sentinel values).
Reimplemented in Lucene::PriorityQueueScoreDocs.
Referenced by Lucene::PriorityQueue< TYPE >::initialize().
|
inlinevirtual |
Called directly after instantiation to create objects that depend on this object being fully constructed.
Reimplemented from Lucene::LuceneObject.
References Lucene::PriorityQueue< TYPE >::_maxSize, Lucene::PriorityQueue< TYPE >::_size, Lucene::PriorityQueue< TYPE >::empty(), Lucene::PriorityQueue< TYPE >::getSentinelObject(), and Lucene::PriorityQueue< TYPE >::heap.
|
inlineprotectedvirtual |
Determines the ordering of objects in this priority queue. Subclasses must define this one method.
Reimplemented in Lucene::FieldDocSortedHitQueue, Lucene::PhraseQueue, Lucene::PriorityQueueScoreDocs, and Lucene::SegmentMergeQueue.
Referenced by Lucene::PriorityQueue< TYPE >::addOverflow(), Lucene::PriorityQueue< TYPE >::downHeap(), and Lucene::PriorityQueue< TYPE >::upHeap().
|
inline |
Return maximum size of queue.
References Lucene::PriorityQueue< TYPE >::_maxSize.
Referenced by Lucene::PriorityQueue< TYPE >::PriorityQueue().
|
inline |
Removes and returns the least element of the PriorityQueue.
References Lucene::PriorityQueue< TYPE >::_size, Lucene::PriorityQueue< TYPE >::downHeap(), and Lucene::PriorityQueue< TYPE >::heap.
|
inline |
Returns the number of elements currently stored in the PriorityQueue.
References Lucene::PriorityQueue< TYPE >::_size.
|
inline |
Returns the least element of the PriorityQueue.
References Lucene::PriorityQueue< TYPE >::heap.
|
inline |
Should be called when the Object at top changes values.
References Lucene::PriorityQueue< TYPE >::downHeap(), and Lucene::PriorityQueue< TYPE >::heap.
Referenced by Lucene::PriorityQueue< TYPE >::addOverflow().
|
inlineprotected |
|
protected |
|
protected |
Referenced by Lucene::PriorityQueue< TYPE >::add(), Lucene::PriorityQueue< TYPE >::addOverflow(), Lucene::PriorityQueue< TYPE >::clear(), Lucene::PriorityQueue< TYPE >::downHeap(), Lucene::PriorityQueue< TYPE >::empty(), Lucene::PriorityQueue< TYPE >::initialize(), Lucene::PriorityQueue< TYPE >::pop(), Lucene::PriorityQueue< TYPE >::PriorityQueue(), Lucene::PriorityQueue< TYPE >::size(), and Lucene::PriorityQueue< TYPE >::upHeap().
|
protected |
Referenced by Lucene::PriorityQueue< TYPE >::add(), Lucene::PriorityQueue< TYPE >::addOverflow(), Lucene::PriorityQueue< TYPE >::clear(), Lucene::PriorityQueue< TYPE >::downHeap(), Lucene::PriorityQueue< TYPE >::initialize(), Lucene::PriorityQueue< TYPE >::pop(), Lucene::PriorityQueue< TYPE >::top(), Lucene::PriorityQueue< TYPE >::updateTop(), and Lucene::PriorityQueue< TYPE >::upHeap().