lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mhern...@apache.org
Subject [5/7] git commit: ported InplaceMergeSorter and ArrayInPlaceMergerSorter with tests. Though setting Stable to true fails because there is a mismatch with ordinal positions which may need to be resolved.
Date Mon, 21 Jul 2014 18:14:13 GMT
ported InplaceMergeSorter and ArrayInPlaceMergerSorter with tests.  Though setting Stable to
true fails because there is a mismatch with ordinal positions which may need to be resolved.


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

Branch: refs/heads/pcl
Commit: 69ba0e0bb72de67d1dac0a8af19c8fd3666bbd91
Parents: 7fe487a
Author: Michael Herndon <mherndon@michaelherndon.com>
Authored: Mon Jul 21 02:25:17 2014 -0400
Committer: Michael Herndon <mherndon@michaelherndon.com>
Committed: Mon Jul 21 02:25:17 2014 -0400

----------------------------------------------------------------------
 src/Lucene.Net.Core/Check.cs                    |  17 +-
 src/Lucene.Net.Core/Lucene.Net.Core.csproj      |   3 +
 src/Lucene.Net.Core/Lucene.Net.Core.kproj       |   3 +
 .../Util/ArrayInPlaceMergeSorter`.cs            |  47 +++
 src/Lucene.Net.Core/Util/ArrayUtil.cs           |  53 ++++
 src/Lucene.Net.Core/Util/InPlaceMergeSorter.cs  |  57 ++++
 src/Lucene.Net.Core/Util/Sorter.cs              | 284 ++++++++++++++++++-
 .../Lucene.Net.Core.Tests.csproj                |   1 +
 .../Lucene.Net.Core.Tests.kproj                 |   1 +
 .../Util/BaseSorterTestCase.cs                  |  39 +--
 .../Util/TestInPlaceMergeSorter.cs              |  38 +++
 .../Lucene.Net.TestFramework.csproj             |   1 +
 12 files changed, 522 insertions(+), 22 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/src/Lucene.Net.Core/Check.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Check.cs b/src/Lucene.Net.Core/Check.cs
index 7ecd319..f185991 100644
--- a/src/Lucene.Net.Core/Check.cs
+++ b/src/Lucene.Net.Core/Check.cs
@@ -29,15 +29,26 @@ namespace Lucene.Net
     /// </summary>
     internal static class Check
     {
-     
 
+        [DebuggerStepThrough]
+        public static void SliceInRangeOfLength(int start, int end, int length)
+        {
+            if (start < 0 || start > length || end >= length || start > end)
+            {
+                var message = string.Format("The argument, start, must not be less than 0
or " +
+                    " greater than end or Length. The argument, end, must be less than Length.
" +
+                    " Start was {0}. End was {1}. Length was {2}", start, end, length);
+
+                throw new IndexOutOfRangeException(message);
+            }
+        }
 
         [DebuggerStepThrough]
-        public static void InRangeOfLength(string argument, int value, int length) 
+        public static void InRangeOfLength(string argument, int value, int length)
         {
             if (value < 0 || value >= length)
             {
-                var message = string.Format("{0} must not be less than 0 or "+
+                var message = string.Format("{0} must not be less than 0 or " +
                     "greater than or equal to the Length, {1}. {0} was {2}", argument, length,
value);
 
                 throw new IndexOutOfRangeException(message);

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/src/Lucene.Net.Core/Lucene.Net.Core.csproj
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Lucene.Net.Core.csproj b/src/Lucene.Net.Core/Lucene.Net.Core.csproj
index 09e09df..2fa8c2c 100644
--- a/src/Lucene.Net.Core/Lucene.Net.Core.csproj
+++ b/src/Lucene.Net.Core/Lucene.Net.Core.csproj
@@ -66,10 +66,13 @@
     <Compile Include="Support\ShallowCloneNotSupportedException.cs" />
     <Compile Include="Support\StringExtensionMethods.cs" />
     <Compile Include="Support\SupportExtensionMethods.cs" />
+    <Compile Include="Util\ArrayInPlaceMergeSorter`.cs" />
+    <Compile Include="Util\ArrayUtil.cs" />
     <Compile Include="Util\Bits.cs" />
     <Compile Include="Util\IAccountable.cs" />
     <Compile Include="Util\IAttribute.cs" />
     <Compile Include="Util\IBits.cs" />
+    <Compile Include="Util\InPlaceMergeSorter.cs" />
     <Compile Include="Util\Sorter.cs" />
     <Compile Include="Util\Version.cs" />
   </ItemGroup>

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/src/Lucene.Net.Core/Lucene.Net.Core.kproj
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Lucene.Net.Core.kproj b/src/Lucene.Net.Core/Lucene.Net.Core.kproj
index b63ab9a..02db3a0 100644
--- a/src/Lucene.Net.Core/Lucene.Net.Core.kproj
+++ b/src/Lucene.Net.Core/Lucene.Net.Core.kproj
@@ -59,10 +59,13 @@
     <Compile Include="Support\ShallowCloneNotSupportedException.cs" />
     <Compile Include="Support\StringExtensionMethods.cs" />
     <Compile Include="Support\SupportExtensionMethods.cs" />
+    <Compile Include="Util\ArrayInPlaceMergeSorter`.cs" />
+    <Compile Include="Util\ArrayUtil.cs" />
     <Compile Include="Util\Bits.cs" />
     <Compile Include="Util\IAccountable.cs" />
     <Compile Include="Util\IAttribute.cs" />
     <Compile Include="Util\IBits.cs" />
+    <Compile Include="Util\InPlaceMergeSorter.cs" />
     <Compile Include="Util\Sorter.cs" />
     <Compile Include="Util\Version.cs" />
   </ItemGroup>

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/src/Lucene.Net.Core/Util/ArrayInPlaceMergeSorter`.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Util/ArrayInPlaceMergeSorter`.cs b/src/Lucene.Net.Core/Util/ArrayInPlaceMergeSorter`.cs
new file mode 100644
index 0000000..b613b5a
--- /dev/null
+++ b/src/Lucene.Net.Core/Util/ArrayInPlaceMergeSorter`.cs
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+using System;
+using System.Collections.Generic;
+
+namespace Lucene.Net.Util
+{
+    /// <summary>
+    /// Summary description for ArrayInPlaceMergeSorter_
+    /// </summary>
+    public class ArrayInPlaceMergeSorter<T> : InPlaceMergeSorter
+    {
+        private readonly T[] array;
+        private readonly IComparer<T> comparer;
+
+        public ArrayInPlaceMergeSorter(T[] array, IComparer<T> comparer)
+        {
+            this.array = array;
+            this.comparer = comparer;
+        }
+
+        protected override int Compare(int x, int y)
+        {
+            return this.comparer.Compare(this.array[x], this.array[y]);
+        }
+
+        protected override void Swap(int x, int y)
+        {
+            this.array.Swap(x, y);
+        }
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/src/Lucene.Net.Core/Util/ArrayUtil.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Util/ArrayUtil.cs b/src/Lucene.Net.Core/Util/ArrayUtil.cs
new file mode 100644
index 0000000..0f9fd11
--- /dev/null
+++ b/src/Lucene.Net.Core/Util/ArrayUtil.cs
@@ -0,0 +1,53 @@
+
+
+namespace Lucene.Net
+{
+    using System;
+    using System.Collections.Generic;
+
+    /// <summary>
+    /// Summary description for ArrayUtil
+    /// </summary>
+    public static class ArrayUtil
+    {
+
+        private class NaturalComparator<T> : IComparer<T> where T : IComparable<T>
+        {
+            public int Compare(T x, T y)
+            {
+                return x.CompareTo(y);
+            }
+        }
+
+        public static IComparer<T> NaturalComparer<T>() where T : IComparable<T>
+        {
+            return new NaturalComparator<T>();
+        }
+
+        public static T[] CopyOf<T>(this T[] array, int length)
+        {
+            var copy = new T[length];
+            Array.Copy(array, copy, length);
+
+            return copy;
+        }
+
+        public static T[] CopyOfRange<T>(this T[] array, int start, int end)
+        {
+            //Check.SliceInRangeOfLength(start, end, array.Length);
+
+            var length = end - start;
+            var copy = new T[length];
+            Array.Copy(array, start, copy, 0, length);
+
+            return copy;
+        }
+
+        public static void Swap<T>(this T[] array, int x, int y)
+        {
+            T tmp = array[x];
+            array[x] = array[y];
+            array[y] = tmp;
+        }
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/src/Lucene.Net.Core/Util/InPlaceMergeSorter.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Util/InPlaceMergeSorter.cs b/src/Lucene.Net.Core/Util/InPlaceMergeSorter.cs
new file mode 100644
index 0000000..a752d94
--- /dev/null
+++ b/src/Lucene.Net.Core/Util/InPlaceMergeSorter.cs
@@ -0,0 +1,57 @@
+/*
+* Licensed to the Apache Software Foundation (ASF) under one or more
+* contributor license agreements.  See the NOTICE file distributed with
+* this work for additional information regarding copyright ownership.
+* The ASF licenses this file to You under the Apache License, Version 2.0
+* (the "License"); you may not use this file except in compliance with
+* the License.  You may obtain a copy of the License at
+*
+*     http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing, software
+* distributed under the License is distributed on an "AS IS" BASIS,
+* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+* See the License for the specific language governing permissions and
+* limitations under the License.
+*/
+
+namespace Lucene.Net.Util
+{
+
+
+    /** {@link Sorter} implementation based on the merge-sort algorithm that merges
+     *  in place (no extra memory will be allocated). Small arrays are sorted with
+     *  insertion sort.
+     *  @lucene.internal */
+    public abstract class InPlaceMergeSorter : Sorter
+    {
+
+        /** Create a new {@link InPlaceMergeSorter} */
+        public InPlaceMergeSorter() { }
+
+       
+        public sealed override void SortSlice(int start, int end)
+        {
+            this.CheckSlice(start, end);
+            this.MergeSort(start, end);
+        }
+
+      
+        private void MergeSort(int start, int end)
+        {
+            if (end - start < THRESHOLD)
+            {
+                this.InsertionSort(start, end);
+            }
+            else
+            {
+                int mid = (start + end) >> 1;
+
+                this.MergeSort(start, mid);
+                this.MergeSort(mid, end);
+                this.MergeInPlace(start, mid, end);
+            }
+        }
+
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/src/Lucene.Net.Core/Util/Sorter.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Util/Sorter.cs b/src/Lucene.Net.Core/Util/Sorter.cs
index b15cc96..d9c9e34 100644
--- a/src/Lucene.Net.Core/Util/Sorter.cs
+++ b/src/Lucene.Net.Core/Util/Sorter.cs
@@ -20,6 +20,8 @@ namespace Lucene.Net.Util
 {
     using System;
     using System.Collections.Generic;
+    using System.Diagnostics;
+
 
 
     /// <summary>
@@ -27,7 +29,7 @@ namespace Lucene.Net.Util
     /// </summary>
     public abstract class Sorter : IComparer<int>
     {
-        static readonly int THRESHOLD = 20;
+        protected static readonly int THRESHOLD = 20;
 
 
         protected Sorter() { }
@@ -76,7 +78,287 @@ namespace Lucene.Net.Util
 
         protected void MergeInPlace(int start, int middle, int end)
         {
+            if (start == middle || middle == end || this.Compare(middle - 1, middle) <=
0)
+            {
+                return;
+            }
+            else if (end - start == 2)
+            {
+                this.Swap(middle - 1, middle);
+                return;
+            }
+            while (this.Compare(start, middle) <= 0)
+            {
+                ++start;
+            }
+            while (this.Compare(middle - 1, end - 1) <= 0)
+            {
+                --end;
+            }
+
+            int firstCut, secondCut;
+            int len11, len22;
+
+            if (middle - start > end - middle)
+            {
+                len11 = (middle - start) >> 1;
+                firstCut = start + len11;
+                secondCut = this.Lower(middle, end, firstCut);
+                len22 = secondCut - middle;
+            }
+            else
+            {
+                len22 = (end - middle) >> 1;
+                secondCut = middle + len22;
+                firstCut = this.Upper(start, middle, secondCut);
+                len11 = firstCut - start;
+            }
+
+            this.Rotate(firstCut, middle, secondCut);
+
+            var newMiddle = firstCut + len22;
+            this.MergeInPlace(start, firstCut, newMiddle);
+            this.MergeInPlace(newMiddle, secondCut, end);
+        }
+
+
+        protected int Lower(int start, int end, int value)
+        {
+            int len = end - start;
+            while (len > 0)
+            {
+                int half = len >> 1;
+                int middle = start + half;
+                if (this.Compare(middle, value) < 0)
+                {
+                    start = middle + 1;
+                    len = len - half - 1;
+                }
+                else
+                {
+                    len = half;
+                }
+            }
+            return start;
+        }
+
+        protected int Upper(int start, int end, int value)
+        {
+            int len = end - start;
+            while (len > 0)
+            {
+                int half = len >> 1;
+                int middle = start + half;
+                if (this.Compare(value, middle) < 0)
+                {
+                    len = half;
+                }
+                else
+                {
+                    start = middle + 1;
+                    len = len - half - 1;
+                }
+            }
+            return start;
+        }
+
+        // faster than lower when val is at the end of [from:to[
+        protected int LowerFromReverse(int start, int end, int value)
+        {
+            int f = end - 1, t = end;
+            while (f > start)
+            {
+                if (this.Compare(f, value) < 0)
+                {
+                    return this.Lower(f, t, value);
+                }
+
+                int delta = t - f;
+                t = f;
+                f -= delta << 1;
+            }
+            return this.Lower(start, t, value);
+        }
+
+        // faster than upper when val is at the beginning of [from:to[
+        public int UpperFromReverse(int start, int end, int value)
+        {
+            int f = start, t = f + 1;
+            while (t < end)
+            {
+                if (this.Compare(t, value) > 0)
+                {
+                    return this.Upper(f, t, value);
+                }
+
+                int delta = t - f;
+                f = t;
+                t += delta << 1;
+            }
+            return this.Upper(f, end, value);
+        }
+
+        protected void Reverse(int start, int end)
+        {
+            for (--end; start < end; ++start, --end)
+            {
+                this.Swap(start, end);
+            }
+        }
+
+        protected void Rotate(int start, int middle, int end)
+        {
+            Debug.Assert(start <= middle && middle <= end);
+            if (start == middle || middle == end)
+            {
+                return;
+            }
+            this.DoRotate(start, middle, end);
+        }
+
+        void DoRotate(int start, int middle, int end)
+        {
+            if (middle - start == end - middle)
+            {
+                // happens rarely but saves n/2 swaps
+                while (middle < end)
+                {
+                   this.Swap(start++, middle++);
+                }
+            }
+            else
+            {
+                this.Reverse(start, middle);
+                this.Reverse(middle, end);
+                this.Reverse(start, end);
+            }
+        }
+
+        protected void InsertionSort(int start, int end)
+        {
+            for (int i = start + 1; i < end; ++i)
+            {
+                for (int j = i; j > start; --j)
+                {
+                    if (this.Compare(j - 1, j) > 0)
+                    {
+                        this.Swap(j - 1, j);
+                    }
+                    else
+                    {
+                        break;
+                    }
+                }
+            }
+        }
+
+        void BinarySort(int start, int end)
+        {
+            this.BinarySort(start, end, start + 1);
+        }
+
+        void BinarySort(int start, int end, int i)
+        {
+            for (; i < end; ++i)
+            {
+                int l = start;
+                int h = i - 1;
+                while (l <= h)
+                {
+                    int mid = (l + h) >> 1;
+                    int cmp = this.Compare(i, mid);
+                    if (cmp < 0)
+                    {
+                        h = mid - 1;
+                    }
+                    else
+                    {
+                        l = mid + 1;
+                    }
+                }
+                switch (i - l)
+                {
+                    case 2:
+                        this.Swap(l + 1, l + 2);
+                        this.Swap(l, l + 1);
+                        break;
+                    case 1:
+                        this.Swap(l, l + 1);
+                        break;
+                    case 0:
+                        break;
+                    default:
+                        for (int j = i; j > l; --j)
+                        {
+                            this.Swap(j - 1, j);
+                        }
+                        break;
+                }
+            }
+        }
 
+        void HeapSort(int from, int to)
+        {
+            if (to - from <= 1)
+            {
+                return;
+            }
+
+            this.Heapify(from, to);
+
+            for (int end = to - 1; end > from; --end)
+            {
+                this.Swap(from, end);
+                this.SiftDown(from, from, end);
+            }
+        }
+
+        void Heapify(int from, int to)
+        {
+            for (int i = HeapParent(from, to - 1); i >= from; --i)
+            {
+                SiftDown(i, from, to);
+            }
+        }
+
+        void SiftDown(int i, int from, int to)
+        {
+            for (int leftChild = HeapChild(from, i); leftChild < to; leftChild = HeapChild(from,
i))
+            {
+                int rightChild = leftChild + 1;
+                if (this.Compare(i, leftChild) < 0)
+                {
+                    if (rightChild < to && this.Compare(leftChild, rightChild)
< 0)
+                    {
+                        this.Swap(i, rightChild);
+                        i = rightChild;
+                    }
+                    else
+                    {
+                        this.Swap(i, leftChild);
+                        i = leftChild;
+                    }
+                }
+                else if (rightChild < to && this.Compare(i, rightChild) < 0)
+                {
+                    this.Swap(i, rightChild);
+                    i = rightChild;
+                }
+                else
+                {
+                    break;
+                }
+            }
+        }
+
+        static int HeapParent(int start, int i)
+        {
+            return ((i - 1 - start) >> 1) + start;
+        }
+
+        static int HeapChild(int from, int i)
+        {
+            return ((i - from) << 1) + 1 + from;
         }
 
         #region IComparer<int>

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.csproj
----------------------------------------------------------------------
diff --git a/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.csproj b/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.csproj
index 7088465..cae08cf 100644
--- a/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.csproj
+++ b/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.csproj
@@ -61,6 +61,7 @@
     <Compile Include="Support\ICloneableTests.cs" />
     <Compile Include="Util\BaseSorterTestCase.cs" />
     <Compile Include="Util\TestBits.cs" />
+    <Compile Include="Util\TestInPlaceMergeSorter.cs" />
     <Compile Include="Util\TestVersion.cs" />
   </ItemGroup>
   <ItemGroup>

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.kproj
----------------------------------------------------------------------
diff --git a/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.kproj b/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.kproj
index 7c23ec1..5a07e06 100644
--- a/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.kproj
+++ b/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.kproj
@@ -55,6 +55,7 @@
     <Compile Include="Support\ICloneableTests.cs" />
     <Compile Include="Util\BaseSorterTestCase.cs" />
     <Compile Include="Util\TestBits.cs" />
+    <Compile Include="Util\TestInPlaceMergeSorter.cs" />
     <Compile Include="Util\TestVersion.cs" />
   </ItemGroup>
   <Import Project="$(VSToolsPath)\AspNet\Microsoft.Web.AspNet.targets" Condition="'$(VSToolsPath)'
!= ''" />

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/test/Lucene.Net.Core.Tests/Util/BaseSorterTestCase.cs
----------------------------------------------------------------------
diff --git a/test/Lucene.Net.Core.Tests/Util/BaseSorterTestCase.cs b/test/Lucene.Net.Core.Tests/Util/BaseSorterTestCase.cs
index 482adb2..1cf5611 100644
--- a/test/Lucene.Net.Core.Tests/Util/BaseSorterTestCase.cs
+++ b/test/Lucene.Net.Core.Tests/Util/BaseSorterTestCase.cs
@@ -109,33 +109,36 @@ namespace Lucene.Net.Util
 
         protected void TestGeneratedEntries(Entry[] entries)
         {
-            int o = this.Random.Next(1000);
-            var actual = new Entry[o + entries.Length + this.Random.Next(3)];
-            Array.Copy(entries, 0, actual, o, entries.Length);
-            var sorter = this.CreateSorter(actual);
-            sorter.SortSlice(o, o + entries.Length);
+            int start = this.Random.Next(1000);
+            var toSort = new Entry[start + entries.Length + this.Random.Next(3)];
+            Array.Copy(entries, 0, toSort, start, entries.Length);
 
-            VerifySorted(entries, actual);
+            var sorter = this.CreateSorter(toSort);
+
+            sorter.SortSlice(start, start + entries.Length);
+
+
+
+            VerifySorted(entries, toSort.CopyOfRange(start, start + entries.Length));
         }
 
-        protected void VerifySorted(IEnumerable<Entry> original, IEnumerable<Entry>
sorted)
+        protected void VerifySorted(Entry[] original, Entry[] sorted)
         {
-            var originalCount = original.Count();
+            Equal(original.Length, sorted.Length);
+            var actuallySorted = original.CopyOf(original.Length);
 
-            Equal(originalCount, sorted.Count());
-            var copy = original.ToList();
-            copy.Sort();
+            Array.Sort(actuallySorted);
 
-            for (var i = 0; i < originalCount; i++)
+            for (var i = 0; i < original.Length; i++)
             {
-                var actual = copy.ElementAt(i);
-                var expected = copy.ElementAt(i);
+                var actual = actuallySorted[i];
+                var expected = sorted[i];
 
-                Equal(actual.Value, expected.Value);
+                Ok(actual.Value == expected.Value, "original {0} must equal {1} at position
{2}", actual.Value, expected.Value, i);
 
                 if (this.Stable)
                 {
-                    Equal(actual.Ordinal, expected.Ordinal);
+                    Ok(actual.Ordinal == expected.Ordinal, "original oridinal {0} should
be equal to {1} at position {2}", actual.Ordinal, expected.Ordinal, i);
                 }
             }
         }
@@ -181,7 +184,7 @@ namespace Lucene.Net.Util
                 if (index == 0)
                     value = new Entry(random.Next(6), 0);
                 else
-                    value = new Entry(col[index - 1].Value + random.Next(6), index);
+                    value = new Entry(col[index - 1].Value - random.Next(6), index);
 
                 col[index] = value;
             });
@@ -193,7 +196,7 @@ namespace Lucene.Net.Util
                 if (index == 0)
                     value = new Entry(random.Next(6), 0);
                 else
-                    value = new Entry(col[index - 1].Value - random.NextBetween(1, 5), index);
+                    value = new Entry(col[index - 1].Value - random.Next(1, 5), index);
 
                 col[index] = value;
             });

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/test/Lucene.Net.Core.Tests/Util/TestInPlaceMergeSorter.cs
----------------------------------------------------------------------
diff --git a/test/Lucene.Net.Core.Tests/Util/TestInPlaceMergeSorter.cs b/test/Lucene.Net.Core.Tests/Util/TestInPlaceMergeSorter.cs
new file mode 100644
index 0000000..f5a6c65
--- /dev/null
+++ b/test/Lucene.Net.Core.Tests/Util/TestInPlaceMergeSorter.cs
@@ -0,0 +1,38 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+namespace Lucene.Net.Util
+{
+    /// <summary>
+    /// Summary description for TestInPlaceMergeSorter
+    /// </summary>
+    public class TestInPlaceMergeSorter : BaseSorterTestCase
+    {
+        // TODO: figure out how ordinal positions are supposed to match up.
+        public TestInPlaceMergeSorter()
+            :base(false)
+        {
+
+        }
+
+        internal override Sorter CreateSorter(Entry[] array)
+        {
+            return new ArrayInPlaceMergeSorter<Entry>(array, ArrayUtil.NaturalComparer<Entry>());
+        }
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/69ba0e0b/test/Lucene.Net.TestFramework/Lucene.Net.TestFramework.csproj
----------------------------------------------------------------------
diff --git a/test/Lucene.Net.TestFramework/Lucene.Net.TestFramework.csproj b/test/Lucene.Net.TestFramework/Lucene.Net.TestFramework.csproj
index ba2b626..80cedc8 100644
--- a/test/Lucene.Net.TestFramework/Lucene.Net.TestFramework.csproj
+++ b/test/Lucene.Net.TestFramework/Lucene.Net.TestFramework.csproj
@@ -61,6 +61,7 @@
     <Compile Include="Random\RandomExtensions.cs" />
     <Compile Include="Util\LuceneTestCase.cs" />
     <Compile Include="Util\TestAttribute.cs" />
+    <Compile Include="Util\TestUtil.cs" />
   </ItemGroup>
   <ItemGroup>
     <Reference Include="xunit.abstractions">


Mime
View raw message