You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucenenet.apache.org by sy...@apache.org on 2015/02/17 18:29:44 UTC
[02/12] lucenenet git commit: Changed a variable name. Changed and
added comments.
Changed a variable name. Changed and added comments.
Project: http://git-wip-us.apache.org/repos/asf/lucenenet/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucenenet/commit/5361c00d
Tree: http://git-wip-us.apache.org/repos/asf/lucenenet/tree/5361c00d
Diff: http://git-wip-us.apache.org/repos/asf/lucenenet/diff/5361c00d
Branch: refs/heads/master
Commit: 5361c00d9d1a74d0b9c07e0b17a8469a6c966591
Parents: 9c38dec
Author: Guido Tagliavini Ponce <t-...@microsoft.com>
Authored: Thu Feb 12 14:19:21 2015 -0800
Committer: Guido Tagliavini Ponce <t-...@microsoft.com>
Committed: Thu Feb 12 14:19:21 2015 -0800
----------------------------------------------------------------------
src/Lucene.Net.Core/Util/PriorityQueue.cs | 49 ++++++++++++++------------
1 file changed, 26 insertions(+), 23 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucenenet/blob/5361c00d/src/Lucene.Net.Core/Util/PriorityQueue.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Util/PriorityQueue.cs b/src/Lucene.Net.Core/Util/PriorityQueue.cs
index f601de8..3938745 100644
--- a/src/Lucene.Net.Core/Util/PriorityQueue.cs
+++ b/src/Lucene.Net.Core/Util/PriorityQueue.cs
@@ -1,4 +1,5 @@
using System;
+using System.Collections.Generic;
namespace Lucene.Net.Util
{
@@ -21,8 +22,8 @@ namespace Lucene.Net.Util
/// <summary>
/// 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.
+ /// element with least priority can always be found in constant time. It is represented as a
+ /// Min-Heap so that Add()'s and Pop()'s require log(size) time.
///
/// <p><b>NOTE</b>: this class will pre-allocate a full array of
/// length <code>maxSize+1</code> if instantiated via the
@@ -31,9 +32,10 @@ namespace Lucene.Net.Util
///
/// @lucene.internal
/// </summary>
+
public abstract class PriorityQueue<T>
{
- private int Size_Renamed = 0;
+ private int QueueSize = 0;
private readonly int MaxSize;
private readonly T[] Heap;
@@ -41,7 +43,7 @@ namespace Lucene.Net.Util
: this(maxSize, true)
{
}
-
+
public PriorityQueue(int maxSize, bool prepopulate)
{
int heapSize;
@@ -96,7 +98,7 @@ namespace Lucene.Net.Util
{
Heap[i] = SentinelObject;
}
- Size_Renamed = maxSize;
+ QueueSize = maxSize;
}
}
}
@@ -157,13 +159,13 @@ namespace Lucene.Net.Util
/// <summary>
/// Adds an Object to a PriorityQueue in log(size) time. If one tries to add
/// more objects than maxSize from initialize an
- /// <seealso cref="ArrayIndexOutOfBoundsException"/> is thrown.
+ /// <seealso cref="IndexOutOfRangeException"/> is thrown.
/// </summary>
/// <returns> the new 'top' element in the queue. </returns>
public T Add(T element)
{
- Size_Renamed++;
- Heap[Size_Renamed] = element;
+ QueueSize++;
+ Heap[QueueSize] = element;
UpHeap();
return Heap[1];
}
@@ -180,16 +182,16 @@ namespace Lucene.Net.Util
/// </summary>
public virtual T InsertWithOverflow(T element)
{
- if (Size_Renamed < MaxSize)
+ if (QueueSize < MaxSize)
{
Add(element);
return default(T);
}
- else if (Size_Renamed > 0 && !LessThan(element, Heap[1]))
+ else if (QueueSize > 0 && !LessThan(element, Heap[1]))
{
T ret = Heap[1];
Heap[1] = element;
- UpdateTop();
+ DownHeap();
return ret;
}
else
@@ -199,7 +201,8 @@ namespace Lucene.Net.Util
}
/// <summary>
- /// Returns the least element of the PriorityQueue in constant time. </summary>
+ /// Returns the least element of the PriorityQueue in constant time.
+ /// Returns null if the queue is empty. </summary>
public T Top()
{
// We don't need to check size here: if maxSize is 0,
@@ -214,12 +217,12 @@ namespace Lucene.Net.Util
/// </summary>
public T Pop()
{
- if (Size_Renamed > 0)
+ if (QueueSize > 0)
{
T result = Heap[1]; // save first value
- Heap[1] = Heap[Size_Renamed]; // move last to first
- Heap[Size_Renamed] = default(T); // permit GC of objects
- Size_Renamed--;
+ Heap[1] = Heap[QueueSize]; // move last to first
+ Heap[QueueSize] = default(T); // permit GC of objects
+ QueueSize--;
DownHeap(); // adjust heap
return result;
}
@@ -257,23 +260,23 @@ namespace Lucene.Net.Util
/// Returns the number of elements currently stored in the PriorityQueue. </summary>
public int Size()
{
- return Size_Renamed;
+ return QueueSize;
}
/// <summary>
/// Removes all entries from the PriorityQueue. </summary>
public void Clear()
{
- for (int i = 0; i <= Size_Renamed; i++)
+ for (int i = 0; i <= QueueSize; i++)
{
Heap[i] = default(T);
}
- Size_Renamed = 0;
+ QueueSize = 0;
}
private void UpHeap()
{
- int i = Size_Renamed;
+ int i = QueueSize;
T node = Heap[i]; // save bottom node
int j = (int)((uint)i >> 1);
while (j > 0 && LessThan(node, Heap[j]))
@@ -291,17 +294,17 @@ namespace Lucene.Net.Util
T node = Heap[i]; // save top node
int j = i << 1; // find smaller child
int k = j + 1;
- if (k <= Size_Renamed && LessThan(Heap[k], Heap[j]))
+ if (k <= QueueSize && LessThan(Heap[k], Heap[j]))
{
j = k;
}
- while (j <= Size_Renamed && LessThan(Heap[j], node))
+ while (j <= QueueSize && LessThan(Heap[j], node))
{
Heap[i] = Heap[j]; // shift up child
i = j;
j = i << 1;
k = j + 1;
- if (k <= Size_Renamed && LessThan(Heap[k], Heap[j]))
+ if (k <= QueueSize && LessThan(Heap[k], Heap[j]))
{
j = k;
}