lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From synhers...@apache.org
Subject [1/5] lucenenet git commit: Added resizing functionality to the PQ. This is needed to support usages in which the maximum size cannot be predefined. Discarded a test which checked correct overflow. Added a test to check resizing.
Date Sun, 01 Mar 2015 19:41:04 GMT
Repository: lucenenet
Updated Branches:
  refs/heads/master 781e1c2cf -> bdf4ec7b0


Added resizing functionality to the PQ. This is needed to support usages in which the maximum
size cannot be predefined. Discarded a test which checked correct overflow. Added a test to
check resizing.


Project: http://git-wip-us.apache.org/repos/asf/lucenenet/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucenenet/commit/abce0d52
Tree: http://git-wip-us.apache.org/repos/asf/lucenenet/tree/abce0d52
Diff: http://git-wip-us.apache.org/repos/asf/lucenenet/diff/abce0d52

Branch: refs/heads/master
Commit: abce0d52410f20bcc89cdc3682669eb6ae289d19
Parents: f1a2b50
Author: Guido Tagliavini Ponce <t-gupon@microsoft.com>
Authored: Wed Feb 18 11:30:14 2015 -0800
Committer: Guido Tagliavini Ponce <t-gupon@microsoft.com>
Committed: Wed Feb 18 11:30:14 2015 -0800

----------------------------------------------------------------------
 src/Lucene.Net.Core/Util/PriorityQueue.cs       | 41 ++++++++++++++------
 .../core/Util/TestPriorityQueue.cs              | 38 ++++++++++++++++--
 2 files changed, 64 insertions(+), 15 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucenenet/blob/abce0d52/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 3938745..9b76121 100644
--- a/src/Lucene.Net.Core/Util/PriorityQueue.cs
+++ b/src/Lucene.Net.Core/Util/PriorityQueue.cs
@@ -28,7 +28,8 @@ namespace Lucene.Net.Util
     /// <p><b>NOTE</b>: this class will pre-allocate a full array of
     /// length <code>maxSize+1</code> if instantiated via the
     /// <seealso cref="#PriorityQueue(int,boolean)"/> constructor with
-    /// <code>prepopulate</code> set to <code>true</code>.
+    /// <code>prepopulate</code> set to <code>true</code>. That maximum
+    /// size can grow as we insert elements over the time.
     ///
     /// @lucene.internal
     /// </summary>
@@ -36,8 +37,13 @@ namespace Lucene.Net.Util
     public abstract class PriorityQueue<T>
     {
         private int QueueSize = 0;
-        private readonly int MaxSize;
-        private readonly T[] Heap;
+        private int MaxSize;
+        private T[] Heap;
+
+        public PriorityQueue()
+            : this(0, false)
+        {
+        } 
 
         public PriorityQueue(int maxSize)
             : this(maxSize, true)
@@ -56,7 +62,7 @@ namespace Lucene.Net.Util
                 if (0 == maxSize)
                 {
                     // We allocate 1 extra to avoid if statement in top()
-                    heapSize = 2;
+                    maxSize++;
                 }
                 else
                 {
@@ -73,14 +79,12 @@ namespace Lucene.Net.Util
                         // Throw exception to prevent confusing OOME:
                         throw new System.ArgumentException("maxSize must be < " + ArrayUtil.MAX_ARRAY_LENGTH
+ "; got: " + maxSize);
                     }
-                    else
-                    {
-                        // NOTE: we add +1 because all access to heap is
-                        // 1-based not 0-based.  heap[0] is unused.
-                        heapSize = maxSize + 1;
-                    }
                 }
             }
+
+            // NOTE: we add +1 because all access to heap is
+            // 1-based not 0-based.  heap[0] is unused.
+            heapSize = maxSize + 1;
             
             // T is unbounded type, so this unchecked cast works always:
             T[] h = new T[heapSize];
@@ -158,13 +162,17 @@ 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="IndexOutOfRangeException"/> is thrown.
+        /// more objects than maxSize from initialize and it is not possible to resize
+        /// the heap, an <seealso cref="IndexOutOfRangeException"/> is thrown.
         /// </summary>
         /// <returns> the new 'top' element in the queue. </returns>
         public T Add(T element)
         {
             QueueSize++;
+            if (QueueSize > MaxSize)
+            {
+                Resize();
+            }
             Heap[QueueSize] = element;
             UpHeap();
             return Heap[1];
@@ -274,6 +282,15 @@ namespace Lucene.Net.Util
             QueueSize = 0;
         }
 
+        private void Resize()
+        {
+            int newSize = Math.Min(ArrayUtil.MAX_ARRAY_LENGTH - 1, 2*MaxSize);
+            T[] newHeap = new T[newSize + 1];
+            Array.Copy(Heap, newHeap, MaxSize + 1);
+            MaxSize = newSize;
+            Heap = newHeap;
+        }
+
         private void UpHeap()
         {
             int i = QueueSize;

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/abce0d52/src/Lucene.Net.Tests/core/Util/TestPriorityQueue.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Tests/core/Util/TestPriorityQueue.cs b/src/Lucene.Net.Tests/core/Util/TestPriorityQueue.cs
index 0c94de5..eed8cc0 100644
--- a/src/Lucene.Net.Tests/core/Util/TestPriorityQueue.cs
+++ b/src/Lucene.Net.Tests/core/Util/TestPriorityQueue.cs
@@ -302,6 +302,8 @@ namespace Lucene.Net.Util
             Assert.AreEqual(pq.Top().Field, 1);
         }
 
+        /*
+         * With the resizing feature, this test has no longer sense.
         [Test]
         public static void TestOverflow()
         {
@@ -338,6 +340,37 @@ namespace Lucene.Net.Util
             {
             }
         }
+         */
+
+        [Test]
+        public static void TestResize()
+        {
+            // Initialize a queue with maximum size 4
+            PriorityQueue<int?> pq = new IntegerQueue(4);
+            pq.Add(3);
+            pq.Add(-2);
+            pq.Add(1);
+            pq.Add(-10);
+               
+            Assert.AreEqual(pq.Size(), 4);
+
+            // Should resize the queue
+            pq.Add(7);
+
+            Assert.AreEqual(pq.Size(), 5);
+
+            pq.Add(10);
+            pq.Add(1);
+            pq.Add(5);
+
+            Assert.AreEqual(pq.Size(), 8);
+
+            // Should resize again
+            pq.Add(100);
+            pq.Add(16);
+
+            Assert.AreEqual(pq.Size(), 10);
+        }
 
         [Test]
         public virtual void TestClear()
@@ -494,9 +527,8 @@ namespace Lucene.Net.Util
         [Test, Timeout(0)]
         public static void TestStress()
         {
-            int atLeast = 10000000;
+            int atLeast = 1000000;
             int maxSize = AtLeast(atLeast);
-            int size;
             PriorityQueue<int?> pq = new IntegerQueue(maxSize);
 
             // Add a lot of elements
@@ -532,7 +564,7 @@ namespace Lucene.Net.Util
             Assert.AreEqual(pq.Size(), 0);
 
             // One last time
-            for (int i = 0; i < 2 * maxSize; i++)
+            for (int i = 0; 2 * i < maxSize; i++)
             {
                 pq.Add(Random().Next());
             }


Mime
View raw message