{
private int size;
private int maxSize;
protected internal T[] heap;
/// Determines the ordering of objects in this priority queue. Subclasses
/// must define this one method.
///
public abstract bool LessThan(T a, T b);
/// This method can be overridden by extending classes to return a sentinel
/// object which will be used by {@link #Initialize(int)} 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 (i.e., {@link #LessThan(Object, Object)} should always favor the
/// non-sentinel values).
///
/// By default, this method returns false, which means the queue will not be
/// filled with sentinel values. Otherwise, the value returned will be used to
/// pre-populate the queue. Adds sentinel values to the queue.
///
/// If this method is extended to return a non-null value, then the following
/// usage pattern is recommended:
///
///
/// // extends getSentinelObject() to return a non-null value.
/// PriorityQueue pq = new MyQueue(numHits);
/// // save the 'top' element, which is guaranteed to not be null.
/// MyObject pqTop = (MyObject) pq.top();
/// <...>
/// // now in order to add a new element, which is 'better' than top (after
/// // you've verified it is better), it is as simple as:
/// pqTop.change().
/// pqTop = pq.updateTop();
///
///
/// NOTE: if this method returns a non-null value, it will be called by
/// {@link #Initialize(int)} {@link #Size()} times, relying on a new object to
/// be returned and will not check if it's null again. Therefore you should
/// ensure any call to this method creates a new instance and behaves
/// consistently, e.g., it cannot return null if it previously returned
/// non-null.
///
///
/// the sentinel object to use to pre-populate the queue, or null if
/// sentinel objects are not supported.
///
protected internal virtual T GetSentinelObject()
{
return default(T);
}
/// Subclass constructors must call this.
protected internal void Initialize(int maxSize)
{
size = 0;
int heapSize;
if (0 == maxSize)
// We allocate 1 extra to avoid if statement in top()
heapSize = 2;
else
{
if (maxSize == Int32.MaxValue)
{
// Don't wrap heapSize to -1, in this case, which
// causes a confusing NegativeArraySizeException.
// Note that very likely this will simply then hit
// an OOME, but at least that's more indicative to
// caller that this values is too big. We don't +1
// in this case, but it's very unlikely in practice
// one will actually insert this many objects into
// the PQ:
heapSize = Int32.MaxValue;
}
else
{
// NOTE: we add +1 because all access to heap is
// 1-based not 0-based. heap[0] is unused.
heapSize = maxSize + 1;
}
}
heap = new T[heapSize];
this.maxSize = maxSize;
// If sentinel objects are supported, populate the queue with them
T sentinel = GetSentinelObject();
if (sentinel != null && !sentinel.Equals(default(T)) )
{
heap[1] = sentinel;
for (int i = 2; i < heap.Length; i++)
{
heap[i] = GetSentinelObject();
}
size = maxSize;
}
}
/// 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.
///
///
/// use {@link #Add(Object)} which returns the new top object,
/// saving an additional call to {@link #Top()}.
///
[Obsolete("use Add(Object) which returns the new top object, saving an additional call to Top().")]
public void Put(T element)
{
size++;
heap[size] = element;
UpHeap();
}
/// Adds an Object to a PriorityQueue in log(size) time. If one tries to add
/// more objects than maxSize from initialize an
/// {@link ArrayIndexOutOfBoundsException} is thrown.
///
///
/// the new 'top' element in the queue.
///
public T Add(T element)
{
size++;
heap[size] = element;
UpHeap();
return heap[1];
}
/// Adds element to the PriorityQueue in log(size) time if either the
/// PriorityQueue is not full, or not lessThan(element, top()).
///
///
///
///
/// true if element is added, false otherwise.
///
/// use {@link #InsertWithOverflow(Object)} instead, which
/// encourages objects reuse.
///
[Obsolete("use InsertWithOverflow(Object) instead, which encourages objects reuse.")]
public virtual bool Insert(T element)
{
return !element.Equals(InsertWithOverflow(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. 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.
///
public virtual T InsertWithOverflow(T element)
{
if (size < maxSize)
{
Put(element);
return default(T);
}
else if (size > 0 && !LessThan(element, heap[1]))
{
T ret = heap[1];
heap[1] = element;
AdjustTop();
return ret;
}
else
{
return element;
}
}
/// Returns the least element of the PriorityQueue in constant time.
public T Top()
{
// We don't need to check size here: if maxSize is 0,
// then heap is length 2 array with both entries null.
// If size is 0 then heap[1] is already null.
return heap[1];
}
/// Removes and returns the least element of the PriorityQueue in log(size)
/// time.
///
public T Pop()
{
if (size > 0)
{
T result = heap[1]; // save first value
heap[1] = heap[size]; // move last to first
heap[size] = default(T); // permit GC of objects
size--;
DownHeap(); // adjust heap
return result;
}
else
return default(T);
}
/// 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);
///
///
///
/// use {@link #UpdateTop()} which returns the new top element and
/// saves an additional call to {@link #Top()}.
///
[Obsolete("use UpdateTop() which returns the new top element and saves an additional call to Top()")]
public void AdjustTop()
{
DownHeap();
}
/// 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);
///
///
///
/// the new 'top' element.
///
public T UpdateTop()
{
DownHeap();
return heap[1];
}
/// Returns the number of elements currently stored in the PriorityQueue.
public int Size()
{
return size;
}
/// Removes all entries from the PriorityQueue.
public void Clear()
{
for (int i = 0; i <= size; i++)
{
heap[i] = default(T);
}
size = 0;
}
private void UpHeap()
{
int i = size;
T node = heap[i]; // save bottom node
int j = Support.Number.URShift(i, 1);
while (j > 0 && LessThan(node, heap[j]))
{
heap[i] = heap[j]; // shift parents down
i = j;
j = Support.Number.URShift(j, 1);
}
heap[i] = node; // install saved node
}
private void DownHeap()
{
int i = 1;
T node = heap[i]; // save top node
int j = i << 1; // find smaller child
int k = j + 1;
if (k <= size && LessThan(heap[k], heap[j]))
{
j = k;
}
while (j <= size && LessThan(heap[j], node))
{
heap[i] = heap[j]; // shift up child
i = j;
j = i << 1;
k = j + 1;
if (k <= size && LessThan(heap[k], heap[j]))
{
j = k;
}
}
heap[i] = node; // install saved node
}
}
}