lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mhern...@apache.org
Subject [9/9] git commit: adding BytesRefArray.cs, need to swap out ByteRef for BytesRefBuilder after BytesRefBuilder is ported.
Date Wed, 20 Aug 2014 02:32:13 GMT
adding BytesRefArray.cs, need to swap out ByteRef for BytesRefBuilder after BytesRefBuilder is ported.


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

Branch: refs/heads/pcl
Commit: b1d556579d98f80ea2713ebfc8bed77cf7dcacc2
Parents: b838907
Author: Michael Herndon <mherndon@michaelherndon.com>
Authored: Tue Aug 19 22:31:17 2014 -0400
Committer: Michael Herndon <mherndon@michaelherndon.com>
Committed: Tue Aug 19 22:31:17 2014 -0400

----------------------------------------------------------------------
 Lucene.vs2013.sln.GhostDoc.user.dic             |   2 +
 src/Lucene.Net.Core/Lucene.Net.Core.csproj      |   4 +
 .../Support/NumberExtensionMethods.cs           | 129 +++++-
 src/Lucene.Net.Core/Util/ByteBlockPool.cs       |  21 +-
 src/Lucene.Net.Core/Util/BytesRef.cs            |  44 +--
 src/Lucene.Net.Core/Util/BytesRefArray.cs       | 394 +++++++++++++++++++
 src/Lucene.Net.Core/Util/InPlaceMergeSorter.cs  |   2 +-
 src/Lucene.Net.Core/Util/IntroSorter.cs         | 136 +++++++
 src/Lucene.Net.Core/Util/Sorter.cs              |   2 +-
 .../Lucene.Net.Core.Tests.csproj                |   2 +
 .../Util/BaseSorterTestCase.cs                  |   2 +-
 .../Util/TestByteArrayRef.cs                    | 155 ++++++++
 .../Util/TestByteBlockPool.cs                   |  39 +-
 test/Lucene.Net.Core.Tests/Util/TestBytesRef.cs |   8 +-
 14 files changed, 875 insertions(+), 65 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/Lucene.vs2013.sln.GhostDoc.user.dic
----------------------------------------------------------------------
diff --git a/Lucene.vs2013.sln.GhostDoc.user.dic b/Lucene.vs2013.sln.GhostDoc.user.dic
index b058ecd..117fab3 100644
--- a/Lucene.vs2013.sln.GhostDoc.user.dic
+++ b/Lucene.vs2013.sln.GhostDoc.user.dic
@@ -1 +1,3 @@
+indices
+init
 Subword

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/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 a248120..9265b37 100644
--- a/src/Lucene.Net.Core/Lucene.Net.Core.csproj
+++ b/src/Lucene.Net.Core/Lucene.Net.Core.csproj
@@ -74,14 +74,18 @@
     <Compile Include="Util\Bits.cs" />
     <Compile Include="Util\BitUtil.cs" />
     <Compile Include="Util\BroadWord.cs" />
+    <Compile Include="Util\ByteBlockPool.cs" />
     <Compile Include="Util\BytesRef.cs" />
+    <Compile Include="Util\BytesRefArray.cs" />
     <Compile Include="Util\CharsRefBuilder.cs" />
     <Compile Include="Util\CharsRef.cs" />
     <Compile Include="Util\Constants.cs" />
+    <Compile Include="Util\Counter.cs" />
     <Compile Include="Util\IAccountable.cs" />
     <Compile Include="Util\IAttribute.cs" />
     <Compile Include="Util\IBits.cs" />
     <Compile Include="Util\InPlaceMergeSorter.cs" />
+    <Compile Include="Util\IntroSorter.cs" />
     <Compile Include="Util\IPurgeStrategy.cs" />
     <Compile Include="Util\PclPurgeStrategy.cs" />
     <Compile Include="Util\RamUsageEstimator.cs" />

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/src/Lucene.Net.Core/Support/NumberExtensionMethods.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Support/NumberExtensionMethods.cs b/src/Lucene.Net.Core/Support/NumberExtensionMethods.cs
index e31b742..aa97ee2 100644
--- a/src/Lucene.Net.Core/Support/NumberExtensionMethods.cs
+++ b/src/Lucene.Net.Core/Support/NumberExtensionMethods.cs
@@ -17,54 +17,157 @@
 
 namespace Lucene.Net.Support
 {
+    using System;
+
     /// <summary>
     /// Extension methods for numeric types to enable the same functionality that
     /// currently exists in the standard java libraries. 
     /// </summary>
     public static class NumberExtensionMethods
     {
+
+        private static class DeBruijn32Leading
+        {
+
+        }
+
         /// <summary>
         /// FFS bit positions with De Bruijn sequences.
         /// </summary>
-        static class DeBruijn32
+        private static class DeBruijn32
         {
-            static readonly int[] POSITIONS = 
-	        {
-	            0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
-	            31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
-	        };
+            private static readonly int[] POSITIONS =
+            {
+                0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+                31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
+            };
 
             /// <summary>
             /// Returns the first set bit (FFS), or 0 if no bits are set.
             /// </summary>
             public static int Position(int number)
             {
-                var res = unchecked((uint)(number & -number) * 0x077CB531U) >> 27;
+                var res = unchecked((uint) (number & -number)*0x077CB531U) >> 27;
                 return POSITIONS[res];
             }
         }
 
 
-        static class DeBruijn64
+        private static class DeBruijn64
         {
 
 
-            static readonly int[] POSITIONS = {
-                0,  1,  2, 53,  3,  7, 54, 27, 4, 38, 41,  8, 34, 55, 48, 28,
-                62,  5, 39, 46, 44, 42, 22,  9, 24, 35, 59, 56, 49, 18, 29, 11,
-                63, 52,  6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
+            private static readonly int[] POSITIONS =
+            {
+                0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
+                62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
+                63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
                 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
             };
 
             public static int Position(long value)
             {
 
-                var result = unchecked((uint)(value & -value) * 0x022fdd63cc95386d) >> 58;
+                var result = unchecked((uint) (value & -value)*0x022fdd63cc95386d) >> 58;
                 return POSITIONS[result];
             }
         }
 
 
+        public static int NumberOfLeadingZeros(this long value)
+        {
+            return (int) NumberOfLeadingZeros((ulong) value);
+        }
+
+         [CLSCompliant(false)]
+        public static uint NumberOfLeadingZeros(this ulong value)
+        {
+            if (value == 0)
+                return 64;
+            uint number = 1;
+            var test = (uint)value >> 32;
+
+
+            if (test == 0)
+            {
+                number += 32;
+                test = (uint)value;
+            }
+
+            if (test >> 16 == 0)
+            {
+                number += 16;
+                test <<= 16;
+            }
+
+            if (test >> 24 == 0)
+            {
+                number += 8;
+                test <<= 8;
+            }
+
+            if (test >> 28 == 0)
+            {
+                number += 4;
+                test <<= 4;
+            }
+
+            if (test >> 30 == 0)
+            {
+                number += 2;
+                test <<= 2;
+            }
+            number -= test >> 31;
+
+            return number;
+        }
+
+        public static int NumberOfLeadingZeros(this int value)
+        {
+            return (int) NumberOfLeadingZeros((uint) value);
+        }
+
+        [CLSCompliant(false)]
+        public static uint NumberOfLeadingZeros(this uint value)
+        {
+            // from hacker's delight
+            http: //www.hackersdelight.org/permissions.htm
+            uint test, number;
+            uint x = value;
+
+            number = 32;
+            test = x >> 16;
+            if (test != 0)
+            {
+                number = number - 16;
+                x = test;
+            }
+            test = x >> 8;
+            if (test != 0)
+            {
+                number = number - 8;
+                x = test;
+            }
+            test = x >> 4;
+            if (test != 0)
+            {
+                number = number - 4;
+                x = test;
+            }
+            test = x >> 2;
+            if (test != 0)
+            {
+                number = number - 2;
+                x = test;
+            }
+            test = x >> 1;
+            
+            if (test != 0)
+                return number - 2;
+
+            return number - x;
+        }
+
         /// <summary>
         /// Returns the number of trailing zeros. i.e 100 has two trailing zeros.
         /// </summary>

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/src/Lucene.Net.Core/Util/ByteBlockPool.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Util/ByteBlockPool.cs b/src/Lucene.Net.Core/Util/ByteBlockPool.cs
index cd1978c..9d35fd2 100644
--- a/src/Lucene.Net.Core/Util/ByteBlockPool.cs
+++ b/src/Lucene.Net.Core/Util/ByteBlockPool.cs
@@ -115,6 +115,8 @@ namespace Lucene.Net.Util
         public ByteBlockPool(Allocator allocator)
         {
             this.allocator = allocator;
+            // this should always be called when a pool is created.
+            this.NextBuffer();
         }
 
         /// <summary>
@@ -163,7 +165,12 @@ namespace Lucene.Net.Util
                     var offset = reuseFirst ? 1 : 0;
                     // Recycle all but the first buffer
                     allocator.RecycleByteBlocks(Buffers, offset, 1 + this.bufferPosition);
-                    Array.Clear(Buffers, 0, Buffers.Length);
+
+
+                    for (var i = offset; i < (this.bufferPosition + 1); i++)
+                    {
+                        Buffers[i] = new byte[10];
+                    }
                 }
                 if (reuseFirst)
                 {
@@ -171,7 +178,7 @@ namespace Lucene.Net.Util
                     this.bufferPosition = 0;
                     BytePosition = 0;
                     ByteOffset = 0;
-                    Buffer = Buffers[0];
+                    this.Buffer = this.Buffers[0];
                 }
                 else
                 {
@@ -179,6 +186,7 @@ namespace Lucene.Net.Util
                     BytePosition = BYTE_BLOCK_SIZE;
                     ByteOffset = -BYTE_BLOCK_SIZE;
                     Buffer = null;
+                   
                 }
             }
         }
@@ -196,9 +204,10 @@ namespace Lucene.Net.Util
                 var newBuffers =
                     new byte[ArrayUtil.Oversize(Buffers.Length + 1, RamUsageEstimator.NUM_BYTES_OBJECT_REF)][];
                 Array.Copy(Buffers, 0, newBuffers, 0, Buffers.Length);
-                Buffers = newBuffers;
+                
+                this.Buffers = newBuffers;
             }
-            Buffer = Buffers[1 + this.bufferPosition] = allocator.ByteBlock;
+           this.Buffer = Buffers[1 + this.bufferPosition] = allocator.ByteBlock;
             this.bufferPosition++;
 
             BytePosition = 0;
@@ -314,8 +323,12 @@ namespace Lucene.Net.Util
             {
                 if (overflow <= 0)
                 {
+                    if (Buffer == null)
+                        this.Buffer = this.Buffers[this.bufferPosition];
+                    
                     Array.Copy(bytes.Bytes, offset, Buffer, BytePosition, length);
                     BytePosition += length;
+                    
                     break;
                 }
 

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/src/Lucene.Net.Core/Util/BytesRef.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Util/BytesRef.cs b/src/Lucene.Net.Core/Util/BytesRef.cs
index a97e870..5631a7e 100644
--- a/src/Lucene.Net.Core/Util/BytesRef.cs
+++ b/src/Lucene.Net.Core/Util/BytesRef.cs
@@ -161,7 +161,7 @@ namespace Lucene.Net.Util
         public void CopyChars(string text)
         {
             Debug.Assert(this.Offset == 0);
-            UnicodeUtil.Utf16ToUtf8(text.ToCharArray(0, text.Length), 0, text.Length, this);
+            UnicodeUtil.Utf16ToUtf8(text.ToCharArray(), 0, text.Length, this);
         }
 
         /// <summary>
@@ -376,7 +376,7 @@ namespace Lucene.Net.Util
         /// @deprecated this comparator is only a transition mechanism
 #pragma warning disable 0612, 0618
         private static readonly IComparer<BytesRef> UTF8_SORTED_AS_UTF16_SORT_ORDER = new Utf8SortedAsUtf16Comparator();
-#pragma warning restore 0612, 0618
+
 
         /// @deprecated this comparator is only a transition mechanism
         [Obsolete("this comparator is only a transition mechanism")]
@@ -384,6 +384,7 @@ namespace Lucene.Net.Util
         {
             get { return UTF8_SORTED_AS_UTF16_SORT_ORDER; }
         }
+#pragma warning restore 0612, 0618
 
         /// @deprecated this comparator is only a transition mechanism
         [Obsolete("this comparator is only a transition mechanism")]
@@ -413,31 +414,30 @@ namespace Lucene.Net.Util
                     var aByte = aBytes[aOffset++] & 0xff;
                     var bByte = bBytes[bOffset++] & 0xff;
 
-                    if (aByte != bByte)
-                    {
-                        // See http://icu-project.org/docs/papers/utf16_code_point_order.html#utf-8-in-utf-16-order
+                    if (aByte == bByte) 
+                        continue;
+                    // See http://icu-project.org/docs/papers/utf16_code_point_order.html#utf-8-in-utf-16-order
 
-                        // We know the terms are not equal, but, we may
-                        // have to carefully fixup the bytes at the
-                        // difference to match UTF16's sort order:
+                    // We know the terms are not equal, but, we may
+                    // have to carefully fixup the bytes at the
+                    // difference to match UTF16's sort order:
 
-                        // NOTE: instead of moving supplementary code points (0xee and 0xef) to the unused 0xfe and 0xff,
-                        // we move them to the unused 0xfc and 0xfd [reserved for future 6-byte character sequences]
-                        // this reserves 0xff for preflex's term reordering (surrogate dance), and if unicode grows such
-                        // that 6-byte sequences are needed we have much bigger problems anyway.
-                        if (aByte >= 0xee && bByte >= 0xee)
+                    // NOTE: instead of moving supplementary code points (0xee and 0xef) to the unused 0xfe and 0xff,
+                    // we move them to the unused 0xfc and 0xfd [reserved for future 6-byte character sequences]
+                    // this reserves 0xff for preflex's term reordering (surrogate dance), and if unicode grows such
+                    // that 6-byte sequences are needed we have much bigger problems anyway.
+                    if (aByte >= 0xee && bByte >= 0xee)
+                    {
+                        if ((aByte & 0xfe) == 0xee)
+                        {
+                            aByte += 0xe;
+                        }
+                        if ((bByte & 0xfe) == 0xee)
                         {
-                            if ((aByte & 0xfe) == 0xee)
-                            {
-                                aByte += 0xe;
-                            }
-                            if ((bByte & 0xfe) == 0xee)
-                            {
-                                bByte += 0xe;
-                            }
+                            bByte += 0xe;
                         }
-                        return aByte - bByte;
                     }
+                    return aByte - bByte;
                 }
 
                 // One is a prefix of the other, or, they are equal:

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/src/Lucene.Net.Core/Util/BytesRefArray.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Util/BytesRefArray.cs b/src/Lucene.Net.Core/Util/BytesRefArray.cs
new file mode 100644
index 0000000..d6ebed8
--- /dev/null
+++ b/src/Lucene.Net.Core/Util/BytesRefArray.cs
@@ -0,0 +1,394 @@
+/*
+ * 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
+{
+    using System;
+    using System.Collections.Generic;
+    using System.Diagnostics;
+
+    /// <summary>
+    ///     A simple append only random-access <seealso cref="BytesRef" /> array that stores full
+    ///     copies of the appended bytes in a <seealso cref="ByteBlockPool" />.
+    ///     <b>Note: this class is not Thread-Safe!</b>
+    ///     @lucene.internal
+    ///     @lucene.experimental
+    /// </summary>
+    // ReSharper disable CSharpWarnings::CS1574
+    public sealed class BytesRefArray : IEnumerable<BytesRef>
+    {
+        private readonly Counter bytesUsed;
+        private readonly ByteBlockPool pool;
+        private int currentOffset;
+        private int lastElement;
+        private int[] offsets = new int[1];
+
+        /// <summary>
+        ///     Creates a new <seealso cref="BytesRefArray" /> with a counter to track allocated bytes
+        /// </summary>
+        public BytesRefArray(Counter bytesUsed)
+        {
+            this.pool = new ByteBlockPool(new ByteBlockPool.DirectTrackingAllocator(bytesUsed));
+         
+            bytesUsed.AddAndGet(RamUsageEstimator.NUM_BYTES_VALUE_TYPE_ARRAY_HEADER + RamUsageEstimator.NUM_BYTES_INT);
+            this.bytesUsed = bytesUsed;
+        }
+
+        /// <summary>
+        ///     Returns the current size of this <seealso cref="BytesRefArray" />
+        /// </summary>
+        /// <returns> the current size of this <seealso cref="BytesRefArray" /> </returns>
+        public int Length
+        {
+            get { return lastElement; }
+        }
+
+        /// <summary>
+        ///     Returns an enumerator that iterates through the collection.
+        /// </summary>
+        /// <returns>
+        ///     A <see cref="T:System.Collections.Generic.IEnumerator`1" /> that can be used to iterate through the
+        ///     collection.
+        /// </returns>
+        public IEnumerator<BytesRef> GetEnumerator()
+        {
+            return this.GetEnumerator(null);
+        }
+
+        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
+        {
+            return this.GetEnumerator(null);
+        }
+
+        /// <summary>
+        ///     Clears this <seealso cref="BytesRefArray" />
+        /// </summary>
+        public void Clear()
+        {
+            lastElement = 0;
+            currentOffset = 0;
+            Array.Clear(offsets, 0, offsets.Length);
+            pool.Reset(false, true); // no need to 0 fill the buffers we control the allocator
+        }
+
+        /// <summary>
+        ///     Appends a copy of the given <seealso cref="BytesRef" /> to this <seealso cref="BytesRefArray" />.
+        /// </summary>
+        /// <param name="bytes"> the bytes to append </param>
+        /// <returns> the index of the appended bytes </returns>
+        public int Append(BytesRef bytes)
+        {
+            if (lastElement >= offsets.Length)
+            {
+                var oldLen = offsets.Length;
+                offsets = offsets.Grow(offsets.Length + 1);
+                bytesUsed.AddAndGet((offsets.Length - oldLen)*RamUsageEstimator.NUM_BYTES_INT);
+            }
+            pool.Append(bytes);
+            offsets[lastElement++] = currentOffset;
+            currentOffset += bytes.Length;
+            return lastElement - 1;
+        }
+
+        /// <summary>
+        ///     Returns the <i>n'th</i> element of this <seealso cref="BytesRefArray" />
+        /// </summary>
+        /// <param name="spare"> a spare <seealso cref="BytesRef" /> instance </param>
+        /// <param name="index"> the elements index to retrieve </param>
+        /// <returns> the <i>n'th</i> element of this <seealso cref="BytesRefArray" /> </returns>
+        public BytesRef Retrieve(BytesRef spare, int index)
+        {
+            Debug.Assert(spare != null, "spare must never be null");
+            Debug.Assert(spare.Offset == 0);
+
+            if (index > this.lastElement)
+                throw new IndexOutOfRangeException("index " + index + " must be less than the size: " +
+                                                   this.lastElement);
+            var offset = this.offsets[index];
+            var length = index == this.lastElement - 1 ? this.currentOffset - offset : this.offsets[index + 1] - offset;
+
+            spare.Grow(length);
+            spare.Length = length;
+            this.pool.ReadBytes(offset, spare.Bytes, spare.Offset, spare.Length);
+            return spare;
+        }
+
+        /// <summary>
+        /// Sorts the specified comp.
+        /// </summary>
+        /// <param name="comp">The comp.</param>
+        /// <returns>System.Int32[].</returns>
+        private int[] Sort(IComparer<BytesRef> comp)
+        {
+            var orderedEntries = new int[this.Length];
+            for (var i = 0; i < orderedEntries.Length; i++)
+            {
+                orderedEntries[i] = i;
+            }
+
+            using (var sorter = new ByteRefArraySorter(this, comp, orderedEntries))
+            {
+                sorter.Sort(0, this.Length);
+            }
+
+            return orderedEntries;
+        }
+
+
+        /// <summary>
+        /// <p>
+        /// Returns a <seealso cref="BytesRefEnumerator" /> with point in time semantics. The
+        /// iterator provides access to all so far appended <seealso cref="BytesRef" /> instances.
+        /// </p>
+        /// <p>
+        /// If a non <code>null</code><seealso cref="IComparer{BytesRef}" /> is provided the iterator will
+        /// iterate the byte values in the order specified by the comparator. Otherwise
+        /// the order is the same as the values were appended.
+        /// </p>
+        /// <p>
+        /// this is a non-destructive operation.
+        /// </p>
+        /// </summary>
+        /// <param name="comp">The comp.</param>
+        /// <returns>IEnumerator&lt;BytesRef&gt;.</returns>
+        public IEnumerator<BytesRef> GetEnumerator(IComparer<BytesRef> comp)
+        {
+            var spare = new BytesRef();
+            var size = this.Length;
+            var indices = comp == null ? null : Sort(comp);
+            return new BytesRefEnumerator(this,  size, indices);
+        }
+
+        /// <summary>
+        /// Class ByteRefArraySorter.
+        /// </summary>
+        private class ByteRefArraySorter : IntroSorter, IDisposable
+        {
+            private BytesRefArray bytesRefArray;
+            private IComparer<BytesRef> comparer;
+            private int[] orderedEntries;
+            private BytesRef pivot;
+            private BytesRef scratch1;
+            private BytesRef scratch2;
+
+            /// <summary>
+            /// Initializes a new instance of the <see cref="ByteRefArraySorter"/> class.
+            /// </summary>
+            /// <param name="outerInstance">The outer instance.</param>
+            /// <param name="comp">The comp.</param>
+            /// <param name="orderedEntries">The ordered entries.</param>
+            public ByteRefArraySorter(BytesRefArray outerInstance, IComparer<BytesRef> comp, int[] orderedEntries)
+            {
+                this.bytesRefArray = outerInstance;
+                this.comparer = comp;
+                this.orderedEntries = orderedEntries;
+                pivot = new BytesRef();
+                scratch1 = new BytesRef();
+                scratch2 = new BytesRef();
+            }
+
+            /// <summary>
+            /// Save the value at slot <code>i</code> so that it can later be used as a
+            /// pivot, see <seealso cref="ComparePivot(int)" />.
+            /// </summary>
+            /// <value>The pivot.</value>
+            protected internal override int Pivot
+            {
+                set
+                {
+                    var index = orderedEntries[value];
+                    bytesRefArray.Retrieve(pivot, index);
+                }
+            }
+
+            /// <summary>
+            /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.
+            /// </summary>
+            public void Dispose()
+            {
+                GC.SuppressFinalize(this);
+                this.Dispose(true);
+            }
+
+            /// <summary>
+            /// Swaps the specified i.
+            /// </summary>
+            /// <param name="i">The i.</param>
+            /// <param name="j">The j.</param>
+            protected override void Swap(int i, int j)
+            {
+                var o = orderedEntries[i];
+                orderedEntries[i] = orderedEntries[j];
+                orderedEntries[j] = o;
+            }
+
+            /// <summary>
+            /// Compares the specified i.
+            /// </summary>
+            /// <param name="i">The i.</param>
+            /// <param name="j">The j.</param>
+            /// <returns>System.Int32.</returns>
+            protected override int Compare(int i, int j)
+            {
+                int idx1 = orderedEntries[i], 
+                    idx2 = orderedEntries[j];
+                
+                return this.comparer.Compare(bytesRefArray.Retrieve(scratch1, idx1),
+                    bytesRefArray.Retrieve(scratch2, idx2));
+            }
+
+            /// <summary>
+            /// Compare the pivot with the slot at <code>j</code>, similarly to
+            /// <seealso cref="Sorter.Compare(int, int)" />.
+            /// </summary>
+            /// <param name="j">The j.</param>
+            /// <returns>System.Int32.</returns>
+            protected internal override int ComparePivot(int j)
+            {
+                var index = orderedEntries[j];
+                return this.comparer.Compare(this.pivot, bytesRefArray.Retrieve(this.scratch2, index));
+            }
+
+
+            private void Dispose(bool disposing)
+            {
+                if (!disposing)
+                    return;
+
+                this.pivot = null;
+                this.scratch1 = null;
+                this.scratch2 = null;
+                this.bytesRefArray = null;
+                this.comparer = null;
+                this.orderedEntries = null;
+            }
+
+            /// <summary>
+            /// Finalizes an instance of the <see cref="ByteRefArraySorter"/> class.
+            /// </summary>
+            ~ByteRefArraySorter()
+            {
+                this.Dispose(false);
+            }
+        }
+
+
+        /// <summary>
+        ///     Class BytesRefEnumerator.
+        /// </summary>
+        // ReSharper disable once ClassWithVirtualMembersNeverInherited.Local
+        private class BytesRefEnumerator : IEnumerator<BytesRef>
+        {
+            private readonly int[] indices;
+            private readonly int size;
+            private BytesRefArray bytesRefArray;
+            private int position;
+
+            /// <summary>
+            ///     Initializes a new instance of the <see cref="BytesRefEnumerator" /> class.
+            /// </summary>
+            /// <param name="bytesRefArray">The bytes reference array.</param>
+            /// <param name="size">The size.</param>
+            /// <param name="indices">The indices.</param>
+            public BytesRefEnumerator(BytesRefArray bytesRefArray,  int size, int[] indices)
+            {
+                this.bytesRefArray = bytesRefArray;
+                this.size = size;
+                this.indices = indices;
+                this.position = -1;
+            }
+
+            /// <summary>
+            ///     Gets the element in the collection at the current position of the enumerator.
+            /// </summary>
+            /// <value>The current.</value>
+            public BytesRef Current { get; private set; }
+
+            object System.Collections.IEnumerator.Current
+            {
+                get { return this.Current; }
+            }
+
+            /// <summary>
+            ///     Advances the enumerator to the next element of the collection.
+            /// </summary>
+            /// <returns>
+            ///     true if the enumerator was successfully advanced to the next element; false if the enumerator has passed the
+            ///     end of the collection.
+            /// </returns>
+            public bool MoveNext()
+            {
+                                this.position++;
+
+                var next = position < size;
+
+                if (!next)
+                {
+                    this.Current = null;
+                    return false;
+                }
+
+                // return a new instance for each loop. 
+                var bytesRef = new BytesRef();
+                this.Current = bytesRefArray.Retrieve(bytesRef, indices == null ? position : indices[position]);
+                return true;
+            }
+
+            /// <summary>
+            ///     Sets the enumerator to its initial position, which is before the first element in the collection.
+            /// </summary>
+            public void Reset()
+            {
+                this.position = -1;
+            }
+
+            /// <summary>
+            ///     Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.
+            /// </summary>
+            public void Dispose()
+            {
+                GC.SuppressFinalize(this);
+                this.Dispose(true);
+            }
+
+
+            /// <summary>
+            ///     Releases unmanaged and - optionally - managed resources.
+            /// </summary>
+            /// <param name="disposing">
+            ///     <c>true</c> to release both managed and unmanaged resources; <c>false</c> to release only
+            ///     unmanaged resources.
+            /// </param>
+            protected virtual void Dispose(bool disposing)
+            {
+                if (!disposing)
+                    return;
+
+                this.Current = null;
+                this.bytesRefArray = null;
+            }
+
+            /// <summary>
+            ///     Finalizes an instance of the <see cref="BytesRefEnumerator" /> class.
+            /// </summary>
+            ~BytesRefEnumerator()
+            {
+                this.Dispose(false);
+            }
+        }
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/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
index fc5ddea..0aa340f 100644
--- a/src/Lucene.Net.Core/Util/InPlaceMergeSorter.cs
+++ b/src/Lucene.Net.Core/Util/InPlaceMergeSorter.cs
@@ -27,7 +27,7 @@ namespace Lucene.Net.Util
 
        
        
-        public sealed override void SortRange(int start, int count)
+        public sealed override void Sort(int start, int count)
         {
             this.CheckSlice(start, count);
             this.MergeSort(start, count);

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/src/Lucene.Net.Core/Util/IntroSorter.cs
----------------------------------------------------------------------
diff --git a/src/Lucene.Net.Core/Util/IntroSorter.cs b/src/Lucene.Net.Core/Util/IntroSorter.cs
new file mode 100644
index 0000000..572fdfe
--- /dev/null
+++ b/src/Lucene.Net.Core/Util/IntroSorter.cs
@@ -0,0 +1,136 @@
+/*
+ * 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
+{
+    using Lucene.Net.Support;
+    /// <summary>
+    /// <seealso cref="Sorter" /> implementation based on a variant of the quicksort algorithm
+    /// called <a href="http://en.wikipedia.org/wiki/Introsort">introsort</a>: when
+    /// the recursion level exceeds the log of the length of the array to sort, it
+    /// falls back to heapsort. this prevents quicksort from running into its
+    /// worst-case quadratic runtime. Small arrays are sorted with
+    /// insertion sort.
+    /// @lucene.internal
+    /// </summary>
+    public abstract class IntroSorter : Sorter
+    {
+        /// <summary>
+        /// Performs Ceil(Log2(n)) calculation
+        /// </summary>
+        /// <param name="number">The number.</param>
+        /// <returns>System.Int32.</returns>
+        internal static int CeilLog2(int number)
+        {
+            //8bits in a byte
+            return sizeof(int) * 8 - (number -1).NumberOfLeadingZeros();
+        }
+
+
+        /// <summary>
+        /// Sort a slice or range which begins at the <paramref name="start" /> index to the <paramref name="count" /> index.
+        /// </summary>
+        /// <param name="start">The position to start the slice.</param>
+        /// <param name="count">The count or length of the slice.</param>
+        public override sealed void Sort(int start, int count)
+        {
+            //CheckRange(from, to);
+            this.QuickSort(start, count, CeilLog2(count - start));
+        }
+
+        /// <summary>
+        /// Performs a Quick Sort.
+        /// </summary>
+        /// <param name="start">The start.</param>
+        /// <param name="count">The count.</param>
+        /// <param name="maxDepth">The maximum depth.</param>
+        internal virtual void QuickSort(int start, int count, int maxDepth)
+        {
+            if (count - start < THRESHOLD)
+            {
+                this.InsertionSort(start, count);
+                return;
+            }
+            
+            if (--maxDepth < 0)
+            {
+                this.HeapSort(start, count);
+                return;
+            }
+
+            var mid = (int)((uint)(start + count) >> 1);
+
+            if (this.Compare(start, mid) > 0)
+            {
+                this.Swap(start, mid);
+            }
+
+            if (Compare(mid, count - 1) > 0)
+            {
+                this.Swap(mid, count - 1);
+                if (this.Compare(start, mid) > 0)
+                {
+                    Swap(start, mid);
+                }
+            }
+
+            int left = start + 1;
+            int right = count - 2;
+
+            Pivot = mid;
+            for (; ; )
+            {
+                while (this.ComparePivot(right) < 0)
+                {
+                    --right;
+                }
+
+                while (left < right && ComparePivot(left) >= 0)
+                {
+                    ++left;
+                }
+
+                if (left < right)
+                {
+                    this.Swap(left, right);
+                    --right;
+                }
+                else
+                {
+                    break;
+                }
+            }
+
+            this.QuickSort(start, left + 1, maxDepth);
+            this.QuickSort(left + 1, count, maxDepth);
+        }
+
+        /// <summary>
+        /// Save the value at slot <code>i</code> so that it can later be used as a
+        /// pivot, see <seealso cref="ComparePivot(int)"/>.
+        /// </summary>
+        protected internal abstract int Pivot { set; }
+
+        /// <summary>
+        /// Compare the pivot with the slot at <code>j</code>, similarly to
+        ///  <seealso cref="Sorter.Compare(int, int)"/>.
+        /// </summary>
+        protected internal abstract int ComparePivot(int j);
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/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 88f44d3..0b3fb19 100644
--- a/src/Lucene.Net.Core/Util/Sorter.cs
+++ b/src/Lucene.Net.Core/Util/Sorter.cs
@@ -37,7 +37,7 @@ namespace Lucene.Net.Util
         /// <param name="start">The position to start the slice.</param>
         /// <param name="count">The count or length of the slice. </param>
         /// <exception cref="IndexOutOfRangeException">Throws when start is greater or equal the length or when the start + count </exception>
-        public abstract void SortRange(int start, int count);
+        public abstract void Sort(int start, int count);
 
 
         /// <summary>

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/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 20870d0..52d924a 100644
--- a/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.csproj
+++ b/test/Lucene.Net.Core.Tests/Lucene.Net.Core.Tests.csproj
@@ -62,6 +62,8 @@
     <Compile Include="Util\BaseSorterTestCase.cs" />
     <Compile Include="Util\TestArrayUtil.cs" />
     <Compile Include="Util\TestBits.cs" />
+    <Compile Include="Util\TestByteArrayRef.cs" />
+    <Compile Include="Util\TestByteBlockPool.cs" />
     <Compile Include="Util\TestBroadWord.cs" />
     <Compile Include="Util\TestBytesRef.cs" />
     <Compile Include="Util\TestCharsRef.cs" />

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/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 2295746..0318665 100644
--- a/test/Lucene.Net.Core.Tests/Util/BaseSorterTestCase.cs
+++ b/test/Lucene.Net.Core.Tests/Util/BaseSorterTestCase.cs
@@ -113,7 +113,7 @@ namespace Lucene.Net.Util
 
             var sorter = this.CreateSorter(toSort);
 
-            sorter.SortRange(start, start + entries.Length);
+            sorter.Sort(start, start + entries.Length);
 
             return toSort.CopyOfRange(start, start + entries.Length);
         }

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/test/Lucene.Net.Core.Tests/Util/TestByteArrayRef.cs
----------------------------------------------------------------------
diff --git a/test/Lucene.Net.Core.Tests/Util/TestByteArrayRef.cs b/test/Lucene.Net.Core.Tests/Util/TestByteArrayRef.cs
new file mode 100644
index 0000000..88993dc
--- /dev/null
+++ b/test/Lucene.Net.Core.Tests/Util/TestByteArrayRef.cs
@@ -0,0 +1,155 @@
+/*
+ * 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
+{
+    using System.Linq;
+    using Lucene.Net.Random;
+    using System;
+    using System.Collections.Generic;
+   
+
+    public class TestBytesRefArray : LuceneTestCase
+    {
+        [Test]
+        public virtual void TestAppend()
+        {
+            var random = this.Random;
+            var  list = new BytesRefArray(Counter.NewCounter());
+            IList<string> stringList = new List<string>();
+            for (int j = 0; j < 2; j++)
+            {
+                if (j > 0 && random.NextBoolean())
+                {
+                    list.Clear();
+                    stringList.Clear();
+                }
+                int entries = this.AtLeast(500);
+                BytesRef spare = new BytesRef();
+                int initSize = list.Length;
+                for (int i = 0; i < entries; i++)
+                {
+                    string randomRealisticUnicodeString = random.RandomRealisticUnicodeString();
+                    spare.CopyChars(randomRealisticUnicodeString);
+                    Equal(i + initSize, list.Append(spare));
+                    stringList.Add(randomRealisticUnicodeString);
+                }
+                for (int i = 0; i < entries; i++)
+                {
+                    NotNull(list.Retrieve(spare, i));
+                    Equal(stringList[i], spare.Utf8ToString(), "entry " + i + " doesn't match");
+                }
+
+                // check random
+                for (int i = 0; i < entries; i++)
+                {
+                    int e = random.Next(entries);
+                    NotNull(list.Retrieve(spare, e));
+                    Equal(stringList[e], spare.Utf8ToString(), "entry " + i + " doesn't match");
+                }
+                for (int i = 0; i < 2; i++)
+                {
+                    var iterator = list.GetEnumerator();
+                    foreach (string @string in stringList)
+                    {
+                        iterator.MoveNext();
+                        Equal(@string, iterator.Current.Utf8ToString());
+                    }
+                }
+            }
+        }
+
+        [Test]
+        public virtual void TestSort()
+        {
+            var random = this.Random;
+            var list = new BytesRefArray(Util.Counter.NewCounter());
+            var stringList = new List<string>();
+
+            for (int j = 0; j < 2; j++)
+            {
+                if (j > 0 && random.NextBoolean())
+                {
+                    list.Clear();
+                    stringList.Clear();
+                }
+                int entries = this.AtLeast(500);
+                var spare = new BytesRef();
+                int initSize = list.Length;
+                for (int i = 0; i < entries; i++)
+                {
+                    string randomRealisticUnicodeString = random.RandomRealisticUnicodeString();
+                    spare.CopyChars(randomRealisticUnicodeString);
+                    Equal(initSize + i, list.Append(spare));
+                    stringList.Add(randomRealisticUnicodeString);
+                }
+
+
+#pragma warning disable 0612,  0618
+
+                // requires a custom comparison
+                stringList.Sort(new Comparison<string>((left, right) =>
+                {
+                    if (left == right)
+                        return 0;
+
+                    var limit = left.Length;
+                    if (right.Length < limit)
+                        limit = right.Length;
+
+                    var i = 0;
+                    while (i < limit)
+                    {
+                        char x = left[i],
+                            y = right[i];
+
+                        if (x == y)
+                        {
+                            i++;
+                            continue;
+                        }
+                            
+
+                        if (x > y)
+                            return 1;
+                        
+                        if(y > x)
+                            return -1;  
+                    }
+
+                    return left.Length - right.Length;
+                }));
+               // var items = list.OrderBy(o => o, BytesRef.Utf8SortedAsUtf16Comparer).ToList();
+                var iterator = list.GetEnumerator(BytesRef.Utf8SortedAsUtf16Comparer);
+                var items = new List<BytesRef>();
+                while(iterator.MoveNext())
+                    items.Add(iterator.Current);
+
+#pragma warning restore 0612, 0618
+                int a = 0;
+                foreach (var item
+                    in items)
+                {
+                    Equal(stringList[a], item.Utf8ToString(), "entry " + a + " doesn't match");
+                    a++;
+                }
+                Null(iterator.Current);
+                Equal(a, stringList.Count);
+            }
+        }
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/test/Lucene.Net.Core.Tests/Util/TestByteBlockPool.cs
----------------------------------------------------------------------
diff --git a/test/Lucene.Net.Core.Tests/Util/TestByteBlockPool.cs b/test/Lucene.Net.Core.Tests/Util/TestByteBlockPool.cs
index b632a4c..0bfff1b 100644
--- a/test/Lucene.Net.Core.Tests/Util/TestByteBlockPool.cs
+++ b/test/Lucene.Net.Core.Tests/Util/TestByteBlockPool.cs
@@ -1,26 +1,25 @@
-
+/*
+ * 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
 {
     using Lucene.Net.Random;
     using System.Collections.Generic;
 
-    /*
-     * 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.
-     */
 
     public class TestByteBlockPool : LuceneTestCase
     {
@@ -52,7 +51,7 @@ namespace Lucene.Net.Util
         {
             var bytesUsed = Counter.NewCounter();
             var  pool = new ByteBlockPool(new ByteBlockPool.DirectTrackingAllocator(bytesUsed));
-            pool.NextBuffer();
+            
             var reuseFirst = this.Random.NextBoolean();
             for (var j = 0; j < 2; j++)
             {
@@ -60,11 +59,12 @@ namespace Lucene.Net.Util
                 int maxLength = this.AtLeast(500),
                     numValues = this.AtLeast(100);
                 
-                var @ref = new BytesRefProxy();
+               
                 numValues.Times(i =>
                 {
                     string value = this.Random.RandomRealisticUnicodeString(maxLength: maxLength);
                     list.Add(new BytesRefProxy(value));
+                    var @ref = new BytesRefProxy();
                     @ref.CopyChars(value);
                     pool.Append(@ref);
                 });
@@ -73,6 +73,7 @@ namespace Lucene.Net.Util
                 long position = 0;
                 foreach (var expected in list)
                 {
+                    var @ref = new BytesRefProxy();
                     @ref.ForceGrow(expected.Length);
                     @ref.SetLength(expected.Length);
                     pool.ReadBytes(position, @ref.Bytes, @ref.Offset, @ref.Length);

http://git-wip-us.apache.org/repos/asf/lucenenet/blob/b1d55657/test/Lucene.Net.Core.Tests/Util/TestBytesRef.cs
----------------------------------------------------------------------
diff --git a/test/Lucene.Net.Core.Tests/Util/TestBytesRef.cs b/test/Lucene.Net.Core.Tests/Util/TestBytesRef.cs
index d5927e2..034d89f 100644
--- a/test/Lucene.Net.Core.Tests/Util/TestBytesRef.cs
+++ b/test/Lucene.Net.Core.Tests/Util/TestBytesRef.cs
@@ -50,11 +50,11 @@ namespace Lucene.Net.Util
         {
             100.Times((i) =>
             {
-                var utf8str1 = this.Random.ToUnicodeString();
-                var utf8str2 = new BytesRef(utf8str1).Utf8ToString();
-                Equal(utf8str1, utf8str2);
+                var utf8Str1 = this.Random.ToUnicodeString();
+                var utf8Str2 = new BytesRef(utf8Str1).Utf8ToString();
+                Equal(utf8Str1, utf8Str2);
             });
-            var value = "\uFFFF";
+            const string value = "\uFFFF";
 
             Equal(value, new BytesRef(value).Utf8ToString());
         }


Mime
View raw message