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

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. More...
int32_t | maxSize ()
| Return maximum size of queue. More...
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. More...
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. More...

TYPE | top ()
| Returns the least element of the PriorityQueue. More...
TYPE | pop ()
| Removes and returns the least element of the PriorityQueue. More...
TYPE | updateTop ()
| Should be called when the Object at top changes values. More...
int32_t | size () const
| Returns the number of elements currently stored in the PriorityQueue. More...
bool | empty () const
| Returns whether PriorityQueue is currently empty. More...
void | clear ()
| Removes all entries from the PriorityQueue. More...
Public Member Functions inherited from Lucene::LuceneObject
virtual | ~LuceneObject ()
virtual LuceneObjectPtr | clone (const LuceneObjectPtr &other=LuceneObjectPtr())
| Return clone of this object. More...
virtual int32_t | hashCode ()
| Return hash code for this object. More...
virtual bool | equals (const LuceneObjectPtr &other)
| Return whether two objects are equal. More...
virtual int32_t | compareTo (const LuceneObjectPtr &other)
| Compare two objects. More...
virtual String | toString ()
| Returns a string representation of the object. More...
Public Member Functions inherited from Lucene::LuceneSync
virtual | ~LuceneSync ()
virtual SynchronizePtr | getSync ()
| Return this object synchronize lock. More...
virtual LuceneSignalPtr | getSignal ()
| Return this object signal. More...
virtual void | lock (int32_t timeout=0)
| Lock this object using an optional timeout. More...
virtual void | unlock ()
| Unlock this object. More...
virtual bool | holdsLock ()
| Returns true if this object is currently locked by current thread. More...
virtual void | wait (int32_t timeout=0)
| Wait for signal using an optional timeout. More...
virtual void | notifyAll ()
| Notify all threads waiting for signal. More...

## 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. More...
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. More...
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 | ( |  | ) |

inline virtual

## 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.

Referenced by Lucene::PriorityQueue< FieldDocPtr >::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.

## ◆ clear()

template<typename TYPE>

void Lucene::PriorityQueue< TYPE >::clear | ( |  | ) |

inline

Removes all entries from the PriorityQueue.

## ◆ downHeap()

template<typename TYPE>

void Lucene::PriorityQueue< TYPE >::downHeap | ( |  | ) |

inline protected

Referenced by Lucene::PriorityQueue< FieldDocPtr >::pop(), and Lucene::PriorityQueue< FieldDocPtr >::updateTop().

## ◆ empty()

template<typename TYPE>

bool Lucene::PriorityQueue< TYPE >::empty | ( |  | ) | const

inline

Returns whether PriorityQueue is currently empty.

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

## ◆ getSentinelObject()

template<typename TYPE>

virtual TYPE Lucene::PriorityQueue< TYPE >::getSentinelObject | ( |  | ) |

inline protected virtual

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< FieldDocPtr >::initialize().

## ◆ initialize()

template<typename TYPE>

virtual void Lucene::PriorityQueue< TYPE >::initialize | ( |  | ) |

inline virtual

Called directly after instantiation to create objects that depend on this object being fully constructed.

Reimplemented from Lucene::LuceneObject.

## ◆ lessThan()

template<typename TYPE>

virtual bool Lucene::PriorityQueue< TYPE >::lessThan | ( | const TYPE & | first,
|  | const TYPE & | second
| ) |  |

inline protected virtual

Determines the ordering of objects in this priority queue. Subclasses must define this one method.

Reimplemented in Lucene::SegmentMergeQueue, Lucene::PriorityQueueScoreDocs, Lucene::PhraseQueue, and Lucene::FieldDocSortedHitQueue.

Referenced by Lucene::PriorityQueue< FieldDocPtr >::addOverflow(), Lucene::PriorityQueue< FieldDocPtr >::downHeap(), and Lucene::PriorityQueue< FieldDocPtr >::upHeap().

## ◆ maxSize()

template<typename TYPE>

int32_t Lucene::PriorityQueue< TYPE >::maxSize | ( |  | ) |

inline

Return maximum size of queue.

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

## ◆ pop()

template<typename TYPE>

TYPE Lucene::PriorityQueue< TYPE >::pop | ( |  | ) |

inline

Removes and returns the least element of the PriorityQueue.

## ◆ size()

template<typename TYPE>

int32_t Lucene::PriorityQueue< TYPE >::size | ( |  | ) | const

inline

Returns the number of elements currently stored in the PriorityQueue.

## ◆ top()

template<typename TYPE>

TYPE Lucene::PriorityQueue< TYPE >::top | ( |  | ) |

inline

Returns the least element of the PriorityQueue.

## ◆ updateTop()

template<typename TYPE>

TYPE Lucene::PriorityQueue< TYPE >::updateTop | ( |  | ) |

inline

Should be called when the Object at top changes values.

Referenced by Lucene::PriorityQueue< FieldDocPtr >::addOverflow().

## ◆ upHeap()

template<typename TYPE>

void Lucene::PriorityQueue< TYPE >::upHeap | ( |  | ) |

inline protected

Referenced by Lucene::PriorityQueue< FieldDocPtr >::add().

## Field Documentation

## ◆ _maxSize

template<typename TYPE>

int32_t Lucene::PriorityQueue< TYPE >::_maxSize

protected

Referenced by Lucene::PriorityQueue< FieldDocPtr >::addOverflow(), Lucene::PriorityQueue< FieldDocPtr >::initialize(), Lucene::PriorityQueue< FieldDocPtr >::maxSize(), and Lucene::PriorityQueue< FieldDocPtr >::PriorityQueue().

## ◆ _size

template<typename TYPE>

int32_t Lucene::PriorityQueue< TYPE >::_size

protected

Referenced by Lucene::PriorityQueue< FieldDocPtr >::add(), Lucene::PriorityQueue< FieldDocPtr >::addOverflow(), Lucene::PriorityQueue< FieldDocPtr >::clear(), Lucene::PriorityQueue< FieldDocPtr >::downHeap(), Lucene::PriorityQueue< FieldDocPtr >::empty(), Lucene::PriorityQueue< FieldDocPtr >::initialize(), Lucene::PriorityQueue< FieldDocPtr >::pop(), Lucene::PriorityQueue< FieldDocPtr >::PriorityQueue(), Lucene::PriorityQueue< FieldDocPtr >::size(), and Lucene::PriorityQueue< FieldDocPtr >::upHeap().

## ◆ heap

template<typename TYPE>

heap_type Lucene::PriorityQueue< TYPE >::heap

protected

Referenced by Lucene::PriorityQueue< FieldDocPtr >::add(), Lucene::PriorityQueue< FieldDocPtr >::addOverflow(), Lucene::PriorityQueue< FieldDocPtr >::clear(), Lucene::PriorityQueue< FieldDocPtr >::downHeap(), Lucene::PriorityQueue< FieldDocPtr >::initialize(), Lucene::PriorityQueue< FieldDocPtr >::pop(), Lucene::PriorityQueue< FieldDocPtr >::top(), Lucene::PriorityQueue< FieldDocPtr >::updateTop(), and Lucene::PriorityQueue< FieldDocPtr >::upHeap().

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

- PriorityQueue.h

clucene.sourceforge.net