Lucene.Net.Util.PriorityQueue< T > 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...

Public Member Functions
abstract bool	LessThan (T a, T b)
	Determines the ordering of objects in this priority queue. Subclasses must define this one method.
T	Add (T element)
	Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize an System.IndexOutOfRangeException is thrown.
virtual T	InsertWithOverflow (T element)
	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.
T	Top ()
	Returns the least element of the PriorityQueue in constant time.
T	Pop ()
	Removes and returns the least element of the PriorityQueue in log(size) time.
T	UpdateTop ()
	Should be called when the Object at top changes values. Still log(n) worst case, but it's at least twice as fast to
int	Size ()
	Returns the number of elements currently stored in the PriorityQueue.
void	Clear ()
	Removes all entries from the PriorityQueue.

Detailed Description

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, in Initialize.

Definition at line 36 of file PriorityQueue.cs.

Member Function Documentation

T Lucene.Net.Util.PriorityQueue< T >.Add

(

T

element

)

Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize an System.IndexOutOfRangeException is thrown.

Returns

the new 'top' element in the queue.

Definition at line 141 of file PriorityQueue.cs.

void Lucene.Net.Util.PriorityQueue< T >.Clear

(

)

Removes all entries from the PriorityQueue.

Definition at line 233 of file PriorityQueue.cs.

virtual T Lucene.Net.Util.PriorityQueue< T >.InsertWithOverflow ( T  element )

virtual

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.

Definition at line 158 of file PriorityQueue.cs.

abstract bool Lucene.Net.Util.PriorityQueue< T >.LessThan ( T  a, T  b  )

pure virtual

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

T Lucene.Net.Util.PriorityQueue< T >.Pop

(

)

Removes and returns the least element of the PriorityQueue in log(size) time.

Definition at line 191 of file PriorityQueue.cs.

int Lucene.Net.Util.PriorityQueue< T >.Size

(

)

Returns the number of elements currently stored in the PriorityQueue.

Definition at line 227 of file PriorityQueue.cs.

T Lucene.Net.Util.PriorityQueue< T >.Top

(

)

Returns the least element of the PriorityQueue in constant time.

Definition at line 179 of file PriorityQueue.cs.

T Lucene.Net.Util.PriorityQueue< T >.UpdateTop

(

)

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.updateTop(); instead of o = pq.pop(); o.change(); pq.push(o);

Returns

the new 'top' element.

Definition at line 220 of file PriorityQueue.cs.

---

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

• core/Util/PriorityQueue.cs