lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From synhers...@apache.org
Subject [03/12] lucenenet git commit: Added PQ tests.
Date Tue, 17 Feb 2015 17:29:45 GMT
Added PQ tests.


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

Branch: refs/heads/master
Commit: aeb5e0384cf154e97ef16fad522276e501e0818a
Parents: 5361c00
Author: Guido Tagliavini Ponce <t-gupon@microsoft.com>
Authored: Thu Feb 12 14:20:01 2015 -0800
Committer: Guido Tagliavini Ponce <t-gupon@microsoft.com>
Committed: Thu Feb 12 14:20:01 2015 -0800

----------------------------------------------------------------------
 .../core/Util/TestPriorityQueue.cs              | 315 ++++++++++++++++++-
 1 file changed, 313 insertions(+), 2 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucenenet/blob/aeb5e038/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 9237bd5..d7e18a4 100644
--- a/src/Lucene.Net.Tests/core/Util/TestPriorityQueue.cs
+++ b/src/Lucene.Net.Tests/core/Util/TestPriorityQueue.cs
@@ -23,6 +23,8 @@ namespace Lucene.Net.Util
     [TestFixture]
     public class TestPriorityQueue : LuceneTestCase
     {
+        private static readonly int MAX_PQ_SIZE = ArrayUtil.MAX_ARRAY_LENGTH - 1;
+
         private class IntegerQueue : PriorityQueue<int?>
         {
             public IntegerQueue(int count)
@@ -30,12 +32,309 @@ namespace Lucene.Net.Util
             {
             }
 
+            public IntegerQueue(int count, bool prepopulate)
+                : base(count, prepopulate)
+            {
+            }
+
             public override bool LessThan(int? a, int? b)
             {
                 return (a < b);
             }
         }
 
+        private class IntegerQueueWithSentinel : IntegerQueue
+        {
+            public IntegerQueueWithSentinel(int count, bool prepopulate)
+                : base(count, prepopulate)
+            {
+            }
+
+            protected override int? SentinelObject
+            {
+                get
+                {
+                    return int.MaxValue;
+                }
+            }
+        }
+
+        [Ignore] // Increase heap size to run this test
+        [Test]
+        public static void TestMaxSizeBounds()
+        {
+            // Minimum size is 0
+            int maxSize = 0;
+            PriorityQueue<int?> pq = new IntegerQueue(maxSize);
+
+            // Maximum size is ArrayUtil.MAX_ARRAY_LENGTH - 1
+            maxSize = MAX_PQ_SIZE;
+            pq = new IntegerQueue(maxSize);
+
+            // A valid maximum size
+            maxSize = 12345;
+            pq = new IntegerQueue(maxSize);
+            
+            // Cannot construct a negative size heap
+            maxSize = -3;
+            try
+            {
+                pq = new IntegerQueue(maxSize);
+                // Should had thrown an exception
+                Assert.Fail();
+            }
+            catch (ArgumentException)
+            {
+            }
+
+            maxSize = MAX_PQ_SIZE;
+            try
+            {
+                pq = new IntegerQueue(maxSize);
+            }
+            catch (ArgumentException)
+            {
+            }
+        }
+
+        [Test]
+        public static void TestPrepopulation()
+        {
+            int maxSize = 10;
+            // Populates the internal array
+            PriorityQueue<int?> pq = new IntegerQueueWithSentinel(maxSize, true);
+            Assert.AreEqual(pq.Top(), int.MaxValue);
+            Assert.AreEqual(pq.Size(), 10);
+
+            // Does not populate it
+            pq = new IntegerQueue(maxSize, false);
+            Assert.AreEqual(pq.Top(), default(int?));
+            Assert.AreEqual(pq.Size(), 0);
+        }
+
+        [Test]
+        public static void TestAdd()
+        {
+            int maxSize = 10;
+            PriorityQueue<int?> pq = new IntegerQueue(maxSize);
+            
+            // Add mixed elements
+            pq.Add(5);
+            Assert.AreEqual(pq.Top(), 5);
+            Assert.AreEqual(pq.Size(), 1);
+            pq.Add(1);
+            Assert.AreEqual(pq.Top(), 1);
+            Assert.AreEqual(pq.Size(), 2);
+            pq.Add(3);
+            Assert.AreEqual(pq.Top(), 1);
+            Assert.AreEqual(pq.Size(), 3);
+            pq.Add(-1);
+            Assert.AreEqual(pq.Top(), -1);
+            Assert.AreEqual(pq.Size(), 4);
+            pq.Add(-111111);
+            Assert.AreEqual(pq.Top(), -111111);
+            Assert.AreEqual(pq.Size(), 5);
+
+            // Add a sorted list of elements
+            pq = new IntegerQueue(maxSize);
+            pq.Add(-111111);
+            Assert.AreEqual(pq.Top(), -111111);
+            Assert.AreEqual(pq.Size(), 1);
+            pq.Add(-1);
+            Assert.AreEqual(pq.Top(), -111111);
+            Assert.AreEqual(pq.Size(), 2);
+            pq.Add(1);
+            Assert.AreEqual(pq.Top(), -111111);
+            Assert.AreEqual(pq.Size(), 3);
+            pq.Add(3);
+            Assert.AreEqual(pq.Top(), -111111);
+            Assert.AreEqual(pq.Size(), 4);
+            pq.Add(5);
+            Assert.AreEqual(pq.Top(), -111111);
+            Assert.AreEqual(pq.Size(), 5);
+
+            // Add a reversed sorted list of elements
+            pq = new IntegerQueue(maxSize);
+            pq.Add(5);
+            Assert.AreEqual(pq.Top(), 5);
+            Assert.AreEqual(pq.Size(), 1);
+            pq.Add(3);
+            Assert.AreEqual(pq.Top(), 3);
+            Assert.AreEqual(pq.Size(), 2);
+            pq.Add(1);
+            Assert.AreEqual(pq.Top(), 1);
+            Assert.AreEqual(pq.Size(), 3);
+            pq.Add(-1);
+            Assert.AreEqual(pq.Top(), -1);
+            Assert.AreEqual(pq.Size(), 4);
+            pq.Add(-111111);
+            Assert.AreEqual(pq.Top(), -111111);
+            Assert.AreEqual(pq.Size(), 5);
+        }
+
+        [Test]
+        public static void TestDuplicates()
+        {
+            // Tests that the queue doesn't absorb elements with duplicate keys
+            int maxSize = 10;
+            PriorityQueue<int?> pq = new IntegerQueue(maxSize);
+
+            pq.Add(3);
+            pq.Add(3);
+            Assert.AreEqual(pq.Size(), 2);
+
+            pq.Add(3);
+            Assert.AreEqual(pq.Size(), 3);
+
+            pq.Add(17);
+            pq.Add(17);
+            pq.Add(17);
+            pq.Add(17);
+            Assert.AreEqual(pq.Size(), 7);
+        }
+
+        [Test]
+        public static void TestPop()
+        {
+            int maxSize = 10;
+            PriorityQueue<int?> pq = new IntegerQueue(maxSize);
+
+            // Add one element and pop it
+            pq.Add(7);
+            pq.Pop();
+            Assert.AreEqual(pq.Size(), 0);
+            
+            // Add a bunch of elements, pop them all
+            pq.Add(1);
+            pq.Add(20);
+            pq.Add(1);
+            pq.Add(15);
+            pq.Add(4);
+            pq.Add(12);
+            pq.Add(1000);
+            pq.Add(-3);
+            pq.Pop();
+            Assert.AreEqual(pq.Size(), 7);
+            pq.Pop();
+            pq.Pop();
+            pq.Pop();
+            pq.Pop();
+            pq.Pop();
+            pq.Pop();
+            pq.Pop();
+            Assert.AreEqual(pq.Size(), 0);
+
+            // Interleaved adds and pops
+            pq.Add(1);
+            pq.Add(20);
+            pq.Pop();
+            Assert.AreEqual(pq.Size(), 1);
+            pq.Add(1);
+            pq.Add(15);
+            pq.Add(4);
+            pq.Pop();
+            pq.Pop();
+            Assert.AreEqual(pq.Size(), 2);
+            pq.Add(12);
+            pq.Add(1000);
+            pq.Add(-3);
+            pq.Pop();
+            pq.Pop();
+            Assert.AreEqual(pq.Size(), 3);
+
+            // Pop an empty PQ
+            pq.Pop();
+            pq.Pop();
+            pq.Pop();
+            pq.Pop();
+            pq.Pop();
+            pq.Pop();
+        }
+
+        [Test]
+        public static void TestOverflow()
+        {
+            // Tests adding elements to full queues
+            // Add's documentation claims throwing an IndexOutOfRangeException in this situation
+            
+            // Add an element to a prepopulated queue
+            int maxSize = 10;
+            PriorityQueue<int?> pq = new IntegerQueueWithSentinel(maxSize, true);
+
+            try
+            {
+                pq.Add(3);
+                Assert.Fail();
+            }
+            catch (IndexOutOfRangeException)
+            {
+            }
+
+            // Populate manually
+            maxSize = 5;
+            pq = new IntegerQueue(maxSize);
+            pq.Add(1);
+            pq.Add(4);
+            pq.Add(-1);
+            pq.Add(0);
+            pq.Add(10);
+
+            try
+            {
+                pq.Add(666);
+            }
+            catch (IndexOutOfRangeException)
+            {
+            }
+        }
+
+        [Test]
+        public static void TestStress()
+        {
+            int maxSize = AtLeast(100000);
+
+            PriorityQueue<int?> pq = new IntegerQueue(maxSize);
+            int sum = 0, sum2 = 0;
+
+            DateTime start, end;
+            TimeSpan total;
+            start = DateTime.Now;
+
+            // Add a lot of elements
+            for (int i = 0; i < maxSize; i++)
+            {
+                int next = Random().Next();
+                sum += next;
+                pq.Add(next);
+            }
+
+            end = DateTime.Now;
+            total = end - start;
+            // Note that this measurement considers the random number generation
+            System.Console.WriteLine("Total adding time: {0} ticks or {1}ms", total.Ticks,
total.Milliseconds);
+            System.Console.WriteLine("Time per add: {0} ticks", total.Ticks / maxSize);
+
+            // Pop them and check that the elements are taken in sorted order
+            start = DateTime.Now;
+            int last = int.MinValue;
+            for (int i = 0; i < maxSize; i++)
+            {
+                int? next = pq.Pop();
+                Assert.IsTrue((int)next >= last);
+                last = (int)next;
+                sum2 += last;
+            }
+
+            end = DateTime.Now;
+            total = end - start;
+            // Note that this measurement considers the random number generation
+            System.Console.WriteLine("Total poping time: {0} ticks or {1}ms", total.Ticks,
total.Milliseconds);
+            System.Console.WriteLine("Time per pop: {0} ticks", total.Ticks / maxSize);
+
+            // Loose checking that we didn't lose data in the process
+            Assert.AreEqual(sum, sum2);
+        }
+
         [Test]
         public virtual void TestPQ()
         {
@@ -90,8 +389,10 @@ namespace Lucene.Net.Util
         }
 
         [Test]
-        public virtual void TestFixedSize()
+        public virtual void TestInsertWithOverflowDoesNotOverflow()
         {
+            // Tests that InsertWithOverflow does not cause overflow
+
             PriorityQueue<int?> pq = new IntegerQueue(3);
             pq.InsertWithOverflow(2);
             pq.InsertWithOverflow(3);
@@ -104,8 +405,11 @@ namespace Lucene.Net.Util
         }
 
         [Test]
-        public virtual void TestInsertWithOverflow()
+        public virtual void TestInsertWithOverflowDiscardsRight()
         {
+            // Tests that InsertWithOverflow discards the correct value,
+            // and the resulting PQ preserves its structure
+
             int size = 4;
             PriorityQueue<int?> pq = new IntegerQueue(size);
             int? i1 = 2;
@@ -123,6 +427,13 @@ namespace Lucene.Net.Util
             Assert.IsTrue(pq.InsertWithOverflow(i6) == i6); // i6 should not have been inserted
             Assert.AreEqual(size, pq.Size());
             Assert.AreEqual((int?)2, pq.Top());
+
+            pq.Pop();
+            Assert.AreEqual((int?)3, pq.Top());
+            pq.Pop();
+            Assert.AreEqual((int?)5, pq.Top());
+            pq.Pop();
+            Assert.AreEqual((int?)7, pq.Top());
         }
     }
 }
\ No newline at end of file


Mime
View raw message