Lucene++ - a full-featured, c++ search engine
API Documentation


Loading...
Searching...
No Matches
Public Types | Public Member Functions | Protected Member Functions | Protected Attributes
Lucene::PriorityQueue< TYPE > Class Template Reference

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>

+ Inheritance diagram for Lucene::PriorityQueue< TYPE >:

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.
 
- Public Member Functions inherited from Lucene::LuceneObject
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.
 
- Public Member Functions inherited from Lucene::LuceneSync
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.
 
- Protected Member Functions inherited from Lucene::LuceneObject
 LuceneObject ()
 

Protected Attributes

heap_type heap
 
int32_t _size
 
int32_t _maxSize
 
- Protected Attributes inherited from Lucene::LuceneSync
SynchronizePtr objectLock
 
LuceneSignalPtr objectSignal
 

Detailed Description

template<typename TYPE>
class Lucene::PriorityQueue< TYPE >

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.

Member Typedef Documentation

◆ heap_type

template<typename TYPE >
typedef std::vector<TYPE> Lucene::PriorityQueue< TYPE >::heap_type

Constructor & Destructor Documentation

◆ PriorityQueue()

template<typename TYPE >
Lucene::PriorityQueue< TYPE >::PriorityQueue ( int32_t  maxSize)
inline

◆ ~PriorityQueue()

template<typename TYPE >
virtual Lucene::PriorityQueue< TYPE >::~PriorityQueue ( )
inlinevirtual

Member Function Documentation

◆ add()

template<typename TYPE >
TYPE Lucene::PriorityQueue< TYPE >::add ( const TYPE &  type)
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().

◆ addOverflow()

template<typename TYPE >
TYPE Lucene::PriorityQueue< TYPE >::addOverflow ( const TYPE &  type)
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().

◆ clear()

template<typename TYPE >
void Lucene::PriorityQueue< TYPE >::clear ( )
inline

◆ downHeap()

template<typename TYPE >
void Lucene::PriorityQueue< TYPE >::downHeap ( )
inlineprotected

◆ empty()

template<typename TYPE >
bool Lucene::PriorityQueue< TYPE >::empty ( ) const
inline

Returns whether PriorityQueue is currently empty.

References Lucene::PriorityQueue< TYPE >::_size.

Referenced by Lucene::PriorityQueue< TYPE >::initialize().

◆ getSentinelObject()

template<typename TYPE >
virtual TYPE Lucene::PriorityQueue< TYPE >::getSentinelObject ( )
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().

◆ initialize()

template<typename TYPE >
virtual void 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.

◆ lessThan()

template<typename TYPE >
virtual bool Lucene::PriorityQueue< TYPE >::lessThan ( const TYPE &  first,
const TYPE &  second 
)
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().

◆ maxSize()

template<typename TYPE >
int32_t Lucene::PriorityQueue< TYPE >::maxSize ( )
inline

Return maximum size of queue.

References Lucene::PriorityQueue< TYPE >::_maxSize.

Referenced by Lucene::PriorityQueue< TYPE >::PriorityQueue().

◆ pop()

template<typename TYPE >
TYPE Lucene::PriorityQueue< TYPE >::pop ( )
inline

◆ size()

template<typename TYPE >
int32_t Lucene::PriorityQueue< TYPE >::size ( ) const
inline

Returns the number of elements currently stored in the PriorityQueue.

References Lucene::PriorityQueue< TYPE >::_size.

◆ top()

template<typename TYPE >
TYPE Lucene::PriorityQueue< TYPE >::top ( )
inline

Returns the least element of the PriorityQueue.

References Lucene::PriorityQueue< TYPE >::heap.

◆ updateTop()

template<typename TYPE >
TYPE Lucene::PriorityQueue< TYPE >::updateTop ( )
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().

◆ upHeap()

template<typename TYPE >
void Lucene::PriorityQueue< TYPE >::upHeap ( )
inlineprotected

Field Documentation

◆ _maxSize

template<typename TYPE >
int32_t Lucene::PriorityQueue< TYPE >::_maxSize
protected

◆ _size

template<typename TYPE >
int32_t Lucene::PriorityQueue< TYPE >::_size
protected

◆ heap

template<typename TYPE >
heap_type Lucene::PriorityQueue< TYPE >::heap
protected

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

clucene.sourceforge.net