You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucenenet.apache.org by do...@apache.org on 2009/07/29 20:04:24 UTC
svn commit: r798995 [21/35] - in /incubator/lucene.net/trunk/C#/src:
Lucene.Net/ Lucene.Net/Analysis/ Lucene.Net/Analysis/Standard/
Lucene.Net/Document/ Lucene.Net/Index/ Lucene.Net/QueryParser/
Lucene.Net/Search/ Lucene.Net/Search/Function/ Lucene.Net...
Modified: incubator/lucene.net/trunk/C#/src/Lucene.Net/SupportClass.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/SupportClass.cs?rev=798995&r1=798994&r2=798995&view=diff
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/SupportClass.cs (original)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/SupportClass.cs Wed Jul 29 18:04:12 2009
@@ -16,7 +16,6 @@
*/
using System;
-using System.Collections;
/// <summary>
/// This interface should be implemented by any class whose instances are intended
@@ -36,6 +35,204 @@
/// </summary>
public class SupportClass
{
+ public class TextSupport
+ {
+ /// <summary>
+ /// Copies an array of chars obtained from a String into a specified array of chars
+ /// </summary>
+ /// <param name="sourceString">The String to get the chars from</param>
+ /// <param name="sourceStart">Position of the String to start getting the chars</param>
+ /// <param name="sourceEnd">Position of the String to end getting the chars</param>
+ /// <param name="destinationArray">Array to return the chars</param>
+ /// <param name="destinationStart">Position of the destination array of chars to start storing the chars</param>
+ /// <returns>An array of chars</returns>
+ public static void GetCharsFromString(string sourceString, int sourceStart, int sourceEnd, char[] destinationArray, int destinationStart)
+ {
+ int sourceCounter;
+ int destinationCounter;
+ sourceCounter = sourceStart;
+ destinationCounter = destinationStart;
+ while (sourceCounter < sourceEnd)
+ {
+ destinationArray[destinationCounter] = (char)sourceString[sourceCounter];
+ sourceCounter++;
+ destinationCounter++;
+ }
+ }
+ }
+
+ public class CollectionsSupport
+ {
+ public class BitSet
+ {
+ private System.Collections.BitArray bitArray = null;
+
+ public BitSet(int size)
+ {
+ bitArray = new System.Collections.BitArray(size, false);
+ }
+
+ public void Set(int index)
+ {
+ if (index >= bitArray.Count)
+ GrowBitArray(index + 1);
+ bitArray.Set(index, true);
+ }
+
+ /// <summary>
+ /// Returns the next set bit at or index, or -1 if no such bit exists.
+ /// </summary>
+ /// <param name="index">the index of the bit at which to start checking</param>
+ /// <returns>the next set bit or -1</returns>
+ public int NextSetBit(int index)
+ {
+ while (index < bitArray.Count)
+ {
+ // if index bit is set, return it; otherwise check next index bit
+ if (bitArray.Get(index))
+ return index;
+ else
+ index++;
+ }
+ // if no bits are set at or after index, return -1
+ return -1;
+ }
+
+ private void GrowBitArray(int size)
+ {
+ //TODO:
+ // might be able to change this to:
+ bitArray.Length = size;
+
+ //System.Collections.BitArray tmp = new System.Collections.BitArray(size, false);
+ //for (int i = 0; i < bitArray.Count; i++)
+ // tmp.Set(i, bitArray.Get(i));
+ //bitArray = tmp;
+ }
+ }
+
+ public static void ArrayFill(object[] array, object fillValue)
+ {
+ ArrayFill(array, 0, array.Length, fillValue);
+ }
+ public static void ArrayFill(object[] array, int from, int to, object fillValue)
+ {
+ for (int i = from; i < to; i++)
+ array[i] = fillValue;
+ }
+
+ public static void ArrayFill(byte[] array, byte fillValue)
+ {
+ ArrayFill(array, 0, array.Length, fillValue);
+ }
+ public static void ArrayFill(byte[] array, int from, int to, byte fillValue)
+ {
+ for (int i = from; i < to; i++)
+ array[i] = fillValue;
+ }
+
+ public static void ArrayFill(char[] array, char fillValue)
+ {
+ ArrayFill(array, 0, array.Length, fillValue);
+ }
+ public static void ArrayFill(char[] array, int from, int to, char fillValue)
+ {
+ for (int i = from; i < to; i++)
+ array[i] = fillValue;
+ }
+
+ public static void ArrayFill(int[] array, int fillValue)
+ {
+ ArrayFill(array, 0, array.Length, fillValue);
+ }
+ public static void ArrayFill(int[] array, int from, int to, int fillValue)
+ {
+ for (int i = from; i < to; i++)
+ array[i] = fillValue;
+ }
+
+ public static void ArrayFill(long[] array, long fillValue)
+ {
+ ArrayFill(array, 0, array.Length, fillValue);
+ }
+ public static void ArrayFill(long[] array, int from, int to, long fillValue)
+ {
+ for (int i = from; i < to; i++)
+ array[i] = fillValue;
+ }
+
+ public static void AddAll(System.Collections.Generic.ICollection<byte[]> source, System.Collections.Generic.ICollection<byte[]> destination)
+ {
+ System.Collections.Generic.IEnumerator<byte[]> enumerator = source.GetEnumerator();
+ while (enumerator.MoveNext())
+ destination.Add(enumerator.Current);
+ }
+
+ public static void AddAll(System.Collections.Generic.ICollection<string> source, System.Collections.Generic.ICollection<string> destination)
+ {
+ System.Collections.Generic.IEnumerator<string> enumerator = source.GetEnumerator();
+ while (enumerator.MoveNext())
+ destination.Add(enumerator.Current);
+ }
+
+ public static void AddAll(System.Collections.Generic.IList<object> source, System.Collections.Generic.IList<object> destination)
+ {
+ System.Collections.Generic.IEnumerator<object> enumerator = source.GetEnumerator();
+ while (enumerator.MoveNext())
+ destination.Add(enumerator.Current);
+ }
+
+ public static System.Collections.Generic.SortedDictionary<string, Lucene.Net.Index.IndexReader> TailMap(System.Collections.Generic.SortedDictionary<string, Lucene.Net.Index.IndexReader> map, string fromKey)
+ {
+ System.Collections.Generic.SortedDictionary<string, Lucene.Net.Index.IndexReader> tailMap;
+
+ if (map.Comparer != null)
+ tailMap = new System.Collections.Generic.SortedDictionary<string, Lucene.Net.Index.IndexReader>(map.Comparer);
+ else
+ tailMap = new System.Collections.Generic.SortedDictionary<string, Lucene.Net.Index.IndexReader>();
+
+ if (map != null && map.Count > 0)
+ {
+ System.Collections.Generic.IEnumerator<System.Collections.Generic.KeyValuePair<string, Lucene.Net.Index.IndexReader>> e = map.GetEnumerator();
+
+ if (map.Comparer != null)
+ while (e.MoveNext())
+ {
+ if (map.Comparer.Compare(fromKey, e.Current.Key) <= 0)
+ tailMap[e.Current.Key] = e.Current.Value;
+ }
+ else
+ while (e.MoveNext())
+ {
+ if (string.CompareOrdinal(fromKey, e.Current.Key) <= 0)
+ tailMap[e.Current.Key] = e.Current.Value;
+ }
+ }
+
+ return tailMap;
+ }
+
+ public static void PutAll(System.Collections.IDictionary source, System.Collections.IDictionary destination)
+ {
+ // using destination[key] = source[key] avoids exceptions on duplicate, and
+ // preserves the most recent duplicate key, which is semantically equivalent
+ // to the java.util.Map functionality
+ System.Collections.IEnumerator enumerator = source.Keys.GetEnumerator();
+ while (enumerator.MoveNext())
+ destination[enumerator.Current] = source[enumerator.Current];
+ }
+
+ public static void PutAll(System.Collections.Generic.IDictionary<object, object> source, System.Collections.Generic.IDictionary<object, object> destination)
+ {
+ // using destination[key] = source[key] avoids exceptions on duplicate, and
+ // preserves the most recent duplicate key, which is semantically equivalent
+ // to the java.util.Map functionality
+ System.Collections.Generic.IEnumerator<object> enumerator = source.Keys.GetEnumerator();
+ while (enumerator.MoveNext())
+ destination[enumerator.Current] = source[enumerator.Current];
+ }
+ }
+
/// <summary>
/// Support class used to handle threads
/// </summary>
@@ -259,7 +456,7 @@
/// Calling this method usually terminates the thread.
/// </summary>
/// <param name="stateInfo">An object that contains application-specific information, such as state, which can be used by the thread being aborted</param>
- public void Abort(System.Object stateInfo)
+ public void Abort(object stateInfo)
{
lock (this)
{
@@ -276,9 +473,9 @@
}
/// <summary>
- /// Obtain a String that represents the current Object
+ /// Obtain a String that represents the current object
/// </summary>
- /// <returns>A String that represents the current Object</returns>
+ /// <returns>A String that represents the current object</returns>
public override System.String ToString()
{
return "Thread[" + Name + "," + Priority.ToString() + "," + "" + "]";
@@ -544,7 +741,6 @@
return -1;
}
-
/// <summary>
/// Returns the number of bits set to true in this BitSet.
/// </summary>
@@ -555,7 +751,7 @@
int count = 0;
for (int i = 0; i < bits.Count; i++)
{
- if (bits[i] == true)
+ if (bits[i])
count++;
}
return count;
@@ -765,18 +961,6 @@
}
}
- public static bool TryParse(System.String s, out float f)
- {
- bool ok = false;
-
- if (s.EndsWith("f") || s.EndsWith("F"))
- ok=System.Single.TryParse(s.Substring(0, s.Length - 1).Replace(".", System.Globalization.CultureInfo.CurrentCulture.NumberFormat.NumberDecimalSeparator),out f);
- else
- ok=System.Single.TryParse(s.Replace(".", System.Globalization.CultureInfo.CurrentCulture.NumberFormat.NumberDecimalSeparator),out f);
-
- return ok;
- }
-
/// <summary>
///
/// </summary>
@@ -903,25 +1087,34 @@
}
}
- public static System.Collections.SortedList TailMap(System.Collections.SortedList list, System.Object limit)
+ /// <summary>
+ /// This class provides supporting methods of java.util.BitSet
+ /// that are not present in System.Collections.BitArray.
+ /// </summary>
+ public class BitSetSupport
{
- System.Collections.Comparer comparer = System.Collections.Comparer.Default;
- System.Collections.SortedList newList = new System.Collections.SortedList();
-
- if (list != null)
- {
- if (list.Count > 0)
- {
- int index = 0;
- while (comparer.Compare(list.GetKey(index), limit) < 0)
- index++;
-
- for (; index < list.Count; index++)
- newList.Add(list.GetKey(index), list[list.GetKey(index)]);
+ /// <summary>
+ /// Returns the next set bit at or after docId, or -1 if no such bit exists.
+ /// </summary>
+ /// <param name="bitArray"></param>
+ /// <param name="docId">the index of bit array at which to start checking</param>
+ /// <returns>the next set bit or -1</returns>
+ public static int NextSetBit(System.Collections.BitArray bitArray, int docId)
+ {
+ while (docId < bitArray.Length)
+ {
+ // if docId bit is set, return it
+ // otherwise check next docId bit
+ if (bitArray.Get(docId))
+ return docId;
+ else
+ docId++;
}
+ // if no bits are set at or after docId, return -1
+ return -1;
}
- return newList;
+ private BitSetSupport() { }
}
/// <summary>
@@ -975,7 +1168,7 @@
{
public interface ICompressionAdapter
{
- byte[] Compress(byte[] input);
+ byte[] Compress(byte[] input, int offset, int length);
byte[] Uncompress(byte[] input);
}
@@ -991,10 +1184,10 @@
return compressionAdapter.Uncompress(input);
}
- public static byte[] Compress(byte[] input)
+ public static byte[] Compress(byte[] input, int offset, int length)
{
CheckCompressionSupport();
- return compressionAdapter.Compress(input);
+ return compressionAdapter.Compress(input, offset, length);
}
private static void CheckCompressionSupport()
@@ -1006,273 +1199,11 @@
throw new System.SystemException("Compression support not configured");
Type compressionLibClass = Type.GetType(compressionLibClassName, true);
- System.Object compressionAdapterObj = Activator.CreateInstance(compressionLibClass);
+ object compressionAdapterObj = Activator.CreateInstance(compressionLibClass);
compressionAdapter = compressionAdapterObj as ICompressionAdapter;
if (compressionAdapter == null)
throw new System.SystemException("Compression adapter does not support the ICompressionAdapter interface");
}
}
}
-
- #region WEAKHASHTABLE
- /// <summary>
- /// A Hashtable which holds weak references to its keys so they
- /// can be collected during GC.
- /// </summary>
- [System.Diagnostics.DebuggerDisplay("Count = {Values.Count}")]
- public class WeakHashTable : Hashtable, IEnumerable
- {
- /// <summary>
- /// A weak referene wrapper for the hashtable keys. Whenever a key\value pair
- /// is added to the hashtable, the key is wrapped using a WeakKey. WeakKey saves the
- /// value of the original object hashcode for fast comparison.
- /// </summary>
- class WeakKey : WeakReference
- {
- int hashCode;
-
- public WeakKey(object key)
- : base(key)
- {
- if (key == null)
- throw new ArgumentNullException("key");
-
- hashCode = key.GetHashCode();
- }
-
- public override int GetHashCode()
- {
- return hashCode;
- }
- }
-
- /// <summary>
- /// A Dictionary enumerator which wraps the original hashtable enumerator
- /// and performs 2 tasks: Extract the real key from a WeakKey and skip keys
- /// that were already collected.
- /// </summary>
- class WeakDictionaryEnumerator : IDictionaryEnumerator
- {
- IDictionaryEnumerator baseEnumerator;
- object currentKey;
- object currentValue;
-
- public WeakDictionaryEnumerator(IDictionaryEnumerator baseEnumerator)
- {
- this.baseEnumerator = baseEnumerator;
- }
-
- public DictionaryEntry Entry
- {
- get
- {
- return new DictionaryEntry(this.currentKey, this.currentValue);
- }
- }
-
- public object Key
- {
- get
- {
- return this.currentKey;
- }
- }
-
- public object Value
- {
- get
- {
- return this.currentValue;
- }
- }
-
- public object Current
- {
- get
- {
- return Entry;
- }
- }
-
- public bool MoveNext()
- {
- while (baseEnumerator.MoveNext())
- {
- object key = ((WeakKey)baseEnumerator.Key).Target;
- if (key != null)
- {
- this.currentKey = key;
- this.currentValue = baseEnumerator.Value;
- return true;
- }
- }
- return false;
- }
-
- public void Reset()
- {
- baseEnumerator.Reset();
- this.currentKey = null;
- this.currentValue = null;
- }
- }
-
-
- /// <summary>
- /// Serves as a simple "GC Monitor" that indicates whether cleanup is needed.
- /// If collectableObject.IsAlive is false, GC has occurred and we should perform cleanup
- /// </summary>
- WeakReference collectableObject = new WeakReference(new Object());
-
- /// <summary>
- /// Customize the hashtable lookup process by overriding KeyEquals. KeyEquals
- /// will compare both WeakKey to WeakKey and WeakKey to real keys
- /// </summary>
- protected override bool KeyEquals(object x, object y)
- {
- if (x == y)
- return true;
-
- if (x is WeakKey)
- {
- x = ((WeakKey)x).Target;
- if (x == null)
- return false;
- }
-
- if (y is WeakKey)
- {
- y = ((WeakKey)y).Target;
- if (y == null)
- return false;
- }
-
- return x.Equals(y);
- }
-
- protected override int GetHash(object key)
- {
- return key.GetHashCode();
- }
-
- /// <summary>
- /// Perform cleanup if GC occurred
- /// </summary>
- private void CleanIfNeeded()
- {
- if (collectableObject.Target == null)
- {
- Clean();
- collectableObject = new WeakReference(new Object());
- }
- }
-
- /// <summary>
- /// Iterate over all keys and remove keys that were collected
- /// </summary>
- private void Clean()
- {
- ArrayList keysToDelete = new ArrayList();
- foreach (WeakKey wtk in base.Keys)
- {
- if (!wtk.IsAlive)
- {
- keysToDelete.Add(wtk);
- }
- }
-
- foreach (WeakKey wtk in keysToDelete)
- Remove(wtk);
- }
-
-
- /// <summary>
- /// Wrap each key with a WeakKey and add it to the hashtable
- /// </summary>
- public override void Add(object key, object value)
- {
- CleanIfNeeded();
- base.Add(new WeakKey(key), value);
- }
-
- public override IDictionaryEnumerator GetEnumerator()
- {
- return new WeakDictionaryEnumerator(base.GetEnumerator());
- }
-
- /// <summary>
- /// Create a temporary copy of the real keys and return that
- /// </summary>
- public override ICollection Keys
- {
- get
- {
- ArrayList keys = new ArrayList(Count);
- foreach (WeakKey key in base.Keys)
- {
- object realKey = key.Target;
- if (realKey != null)
- keys.Add(realKey);
- }
- return keys;
- }
- }
-
- public override object this[object key]
- {
- get
- {
- return base[key];
- }
- set
- {
- CleanIfNeeded();
- base[new WeakKey(key)] = value;
- }
- }
-
- public override void CopyTo(Array array, int index)
- {
- int arrayIndex = index;
- foreach (DictionaryEntry de in this)
- {
- array.SetValue(de, arrayIndex++);
- }
- }
-
- public override int Count
- {
- get
- {
- CleanIfNeeded();
- return base.Count;
- }
- }
-
- IEnumerator IEnumerable.GetEnumerator()
- {
- return GetEnumerator();
- }
- }
-
- #endregion
-
- public class Cryptography
- {
- static public bool FIPSCompliant = false;
-
- static public System.Security.Cryptography.HashAlgorithm GetHashAlgorithm()
- {
- if (FIPSCompliant)
- {
- //LUCENENET-175
- //No Assumptions should be made on the HashAlgorithm. It may change in time.
- //SHA256 SHA384 SHA512 etc.
- return System.Security.Cryptography.SHA1.Create();
- }
- return System.Security.Cryptography.MD5.Create();
- }
- }
-
-
}
Added: incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/ArrayUtil.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/Util/ArrayUtil.cs?rev=798995&view=auto
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/ArrayUtil.cs (added)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/ArrayUtil.cs Wed Jul 29 18:04:12 2009
@@ -0,0 +1,162 @@
+/**
+ * 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;
+using System.Text;
+
+namespace Lucene.Net.Util
+{
+ public sealed class ArrayUtil {
+
+ public static int GetNextSize(int targetSize)
+ {
+ /* This over-allocates proportional to the list size, making room
+ * for additional growth. The over-allocation is mild, but is
+ * enough to give linear-time amortized behavior over a long
+ * sequence of appends() in the presence of a poorly-performing
+ * system realloc().
+ * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
+ */
+ return (targetSize >> 3) + (targetSize < 9 ? 3 : 6) + targetSize;
+ }
+
+ public static int GetShrinkSize(int currentSize, int targetSize)
+ {
+ int newSize = GetNextSize(targetSize);
+ // Only reallocate if we are "substantially" smaller.
+ // This saves us from "running hot" (constantly making a
+ // bit bigger then a bit smaller, over and over):
+ if (newSize < currentSize / 2)
+ return newSize;
+ else
+ return currentSize;
+ }
+
+ public static int[] Grow(int[] array, int minSize)
+ {
+ if (array.Length < minSize)
+ {
+ int[] newArray = new int[GetNextSize(minSize)];
+ Array.Copy(array, 0, newArray, 0, array.Length);
+ return newArray;
+ }
+ else
+ return array;
+ }
+
+ public static int[] Grow(int[] array)
+ {
+ return Grow(array, 1 + array.Length);
+ }
+
+ public static int[] Shrink(int[] array, int targetSize)
+ {
+ int newSize = GetShrinkSize(array.Length, targetSize);
+ if (newSize != array.Length)
+ {
+ int[] newArray = new int[newSize];
+ Array.Copy(array, 0, newArray, 0, newSize);
+ return newArray;
+ }
+ else
+ return array;
+ }
+
+ public static long[] Grow(long[] array, int minSize)
+ {
+ if (array.Length < minSize)
+ {
+ long[] newArray = new long[GetNextSize(minSize)];
+ Array.Copy(array, 0, newArray, 0, array.Length);
+ return newArray;
+ }
+ else
+ return array;
+ }
+
+ public static long[] Grow(long[] array)
+ {
+ return Grow(array, 1 + array.Length);
+ }
+
+ public static long[] Shrink(long[] array, int targetSize)
+ {
+ int newSize = GetShrinkSize(array.Length, targetSize);
+ if (newSize != array.Length)
+ {
+ long[] newArray = new long[newSize];
+ Array.Copy(array, 0, newArray, 0, newSize);
+ return newArray;
+ }
+ else
+ return array;
+ }
+
+ public static byte[] Grow(byte[] array, int minSize)
+ {
+ if (array.Length < minSize)
+ {
+ byte[] newArray = new byte[GetNextSize(minSize)];
+ Array.Copy(array, 0, newArray, 0, array.Length);
+ return newArray;
+ }
+ else
+ return array;
+ }
+
+ public static byte[] Grow(byte[] array)
+ {
+ return Grow(array, 1 + array.Length);
+ }
+
+ public static byte[] Shrink(byte[] array, int targetSize)
+ {
+ int newSize = GetShrinkSize(array.Length, targetSize);
+ if (newSize != array.Length)
+ {
+ byte[] newArray = new byte[newSize];
+ Array.Copy(array, 0, newArray, 0, newSize);
+ return newArray;
+ }
+ else
+ return array;
+ }
+
+ /// <summary>
+ /// Returns hash of chars in range start (inclusive) to end (inclusive).
+ /// </summary>
+ public static int HashCode(char[] array, int start, int end)
+ {
+ int code = 0;
+ for (int i = end - 1; i >= start; i--)
+ code = code * 31 + array[i];
+ return code;
+ }
+
+ /// <summary>
+ /// Returns hash of chars in range start (inclusive) to end (inclusive).
+ /// </summary>
+ public static int HashCode(byte[] array, int start, int end)
+ {
+ int code = 0;
+ for (int i = end - 1; i >= start; i--)
+ code = code * 31 + array[i];
+ return code;
+ }
+ }
+}
Added: incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/BitUtil.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/Util/BitUtil.cs?rev=798995&view=auto
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/BitUtil.cs (added)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/BitUtil.cs Wed Jul 29 18:04:12 2009
@@ -0,0 +1,852 @@
+/**
+ * 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;
+using System.Text;
+
+namespace Lucene.Net.Util
+{
+ /// <summary>
+ /// A variety of high efficiencly bit twiddling routines.
+ /// (from org.apache.solr.util rev 555343)
+ /// </summary>
+ public class BitUtil
+ {
+
+ /** Returns the number of bits set in the long */
+ public static int pop(long x) {
+ /* Hacker's Delight 32 bit pop function:
+ * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
+ *
+ int pop(unsigned x) {
+ x = x - ((x >> 1) & 0x55555555);
+ x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+ x = (x + (x >> 4)) & 0x0F0F0F0F;
+ x = x + (x >> 8);
+ x = x + (x >> 16);
+ return x & 0x0000003F;
+ }
+ ***/
+
+ //{DOUG-2.4.0: mod'd to do logical right shift (>>>); have to use unsigned types and >>
+ //// 64 bit java version of the C function from above
+ //x = x - ((x >>> 1) & 0x5555555555555555L);
+ //x = (x & 0x3333333333333333L) + ((x >>>2 ) & 0x3333333333333333L);
+ //x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
+ //x = x + (x >>> 8);
+ //x = x + (x >>> 16);
+ //x = x + (x >>> 32);
+ //return ((int)x) & 0x7F;
+
+ // 64 bit java version of the C function from above
+ ulong ux = (ulong) x;
+ ux = ux - ((ux >> 1) & 0x5555555555555555UL);
+ ux = (ux & 0x3333333333333333UL) + ((ux >>2 ) & 0x3333333333333333UL);
+ ux = (ux + (ux >> 4)) & 0x0F0F0F0F0F0F0F0FL;
+ ux = ux + (ux >> 8);
+ ux = ux + (ux >> 16);
+ ux = ux + (ux >> 32);
+ return ((int)ux) & 0x7F;
+ }
+
+ /*** Returns the number of set bits in an array of longs. */
+ public static long pop_array(long[] A, int wordOffset, int numWords) {
+ /*
+ * Robert Harley and David Seal's bit counting algorithm, as documented
+ * in the revisions of Hacker's Delight
+ * http://www.hackersdelight.org/revisions.pdf
+ * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
+ *
+ * This function was adapted to Java, and extended to use 64 bit words.
+ * if only we had access to wider registers like SSE from java...
+ *
+ * This function can be transformed to compute the popcount of other functions
+ * on bitsets via something like this:
+ * sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
+ *
+ */
+ int n = wordOffset+numWords;
+ long tot=0, tot8=0;
+ long ones=0, twos=0, fours=0;
+
+ int i;
+ for (i = wordOffset; i <= n - 8; i+=8) {
+ /*** C macro from Hacker's Delight
+ #define CSA(h,l, a,b,c) \
+ {unsigned u = a ^ b; unsigned v = c; \
+ h = (a & b) | (u & v); l = u ^ v;}
+ ***/
+
+ long twosA,twosB,foursA,foursB,eights;
+
+ // CSA(twosA, ones, ones, A[i], A[i+1])
+ {
+ long b=A[i], c=A[i+1];
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, A[i+2], A[i+3])
+ {
+ long b=A[i+2], c=A[i+3];
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursA, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ //CSA(twosA, ones, ones, A[i+4], A[i+5])
+ {
+ long b=A[i+4], c=A[i+5];
+ long u=ones^b;
+ twosA=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, A[i+6], A[i+7])
+ {
+ long b=A[i+6], c=A[i+7];
+ long u=ones^b;
+ twosB=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursB, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursB=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+
+ //CSA(eights, fours, fours, foursA, foursB)
+ {
+ long u=fours^foursA;
+ eights=(fours&foursA)|(u&foursB);
+ fours=u^foursB;
+ }
+ tot8 += pop(eights);
+ }
+
+ // handle trailing words in a binary-search manner...
+ // derived from the loop above by setting specific elements to 0.
+ // the original method in Hackers Delight used a simple for loop:
+ // for (i = i; i < n; i++) // Add in the last elements
+ // tot = tot + pop(A[i]);
+
+ if (i<=n-4) {
+ long twosA, twosB, foursA, eights;
+ {
+ long b=A[i], c=A[i+1];
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ {
+ long b=A[i+2], c=A[i+3];
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=4;
+ }
+
+ if (i<=n-2) {
+ long b=A[i], c=A[i+1];
+ long u=ones ^ b;
+ long twosA=(ones & b)|( u & c);
+ ones=u^c;
+
+ long foursA=twos&twosA;
+ twos=twos^twosA;
+
+ long eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=2;
+ }
+
+ if (i<n) {
+ tot += pop(A[i]);
+ }
+
+ tot += (pop(fours)<<2)
+ + (pop(twos)<<1)
+ + pop(ones)
+ + (tot8<<3);
+
+ return tot;
+ }
+
+ /** Returns the popcount or cardinality of the two sets after an intersection.
+ * Neither array is modified.
+ */
+ public static long pop_intersect(long[] A, long[] B, int wordOffset, int numWords) {
+ // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
+ int n = wordOffset+numWords;
+ long tot=0, tot8=0;
+ long ones=0, twos=0, fours=0;
+
+ int i;
+ for (i = wordOffset; i <= n - 8; i+=8) {
+ long twosA,twosB,foursA,foursB,eights;
+
+ // CSA(twosA, ones, ones, (A[i] & B[i]), (A[i+1] & B[i+1]))
+ {
+ long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, (A[i+2] & B[i+2]), (A[i+3] & B[i+3]))
+ {
+ long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursA, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ //CSA(twosA, ones, ones, (A[i+4] & B[i+4]), (A[i+5] & B[i+5]))
+ {
+ long b=(A[i+4] & B[i+4]), c=(A[i+5] & B[i+5]);
+ long u=ones^b;
+ twosA=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, (A[i+6] & B[i+6]), (A[i+7] & B[i+7]))
+ {
+ long b=(A[i+6] & B[i+6]), c=(A[i+7] & B[i+7]);
+ long u=ones^b;
+ twosB=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursB, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursB=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+
+ //CSA(eights, fours, fours, foursA, foursB)
+ {
+ long u=fours^foursA;
+ eights=(fours&foursA)|(u&foursB);
+ fours=u^foursB;
+ }
+ tot8 += pop(eights);
+ }
+
+
+ if (i<=n-4) {
+ long twosA, twosB, foursA, eights;
+ {
+ long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ {
+ long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=4;
+ }
+
+ if (i<=n-2) {
+ long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
+ long u=ones ^ b;
+ long twosA=(ones & b)|( u & c);
+ ones=u^c;
+
+ long foursA=twos&twosA;
+ twos=twos^twosA;
+
+ long eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=2;
+ }
+
+ if (i<n) {
+ tot += pop((A[i] & B[i]));
+ }
+
+ tot += (pop(fours)<<2)
+ + (pop(twos)<<1)
+ + pop(ones)
+ + (tot8<<3);
+
+ return tot;
+ }
+
+ /** Returns the popcount or cardinality of the union of two sets.
+ * Neither array is modified.
+ */
+ public static long pop_union(long[] A, long[] B, int wordOffset, int numWords) {
+ // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \| B[\1]\)/g'
+ int n = wordOffset+numWords;
+ long tot=0, tot8=0;
+ long ones=0, twos=0, fours=0;
+
+ int i;
+ for (i = wordOffset; i <= n - 8; i+=8) {
+ /*** C macro from Hacker's Delight
+ #define CSA(h,l, a,b,c) \
+ {unsigned u = a ^ b; unsigned v = c; \
+ h = (a & b) | (u & v); l = u ^ v;}
+ ***/
+
+ long twosA,twosB,foursA,foursB,eights;
+
+ // CSA(twosA, ones, ones, (A[i] | B[i]), (A[i+1] | B[i+1]))
+ {
+ long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, (A[i+2] | B[i+2]), (A[i+3] | B[i+3]))
+ {
+ long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursA, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ //CSA(twosA, ones, ones, (A[i+4] | B[i+4]), (A[i+5] | B[i+5]))
+ {
+ long b=(A[i+4] | B[i+4]), c=(A[i+5] | B[i+5]);
+ long u=ones^b;
+ twosA=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, (A[i+6] | B[i+6]), (A[i+7] | B[i+7]))
+ {
+ long b=(A[i+6] | B[i+6]), c=(A[i+7] | B[i+7]);
+ long u=ones^b;
+ twosB=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursB, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursB=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+
+ //CSA(eights, fours, fours, foursA, foursB)
+ {
+ long u=fours^foursA;
+ eights=(fours&foursA)|(u&foursB);
+ fours=u^foursB;
+ }
+ tot8 += pop(eights);
+ }
+
+
+ if (i<=n-4) {
+ long twosA, twosB, foursA, eights;
+ {
+ long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ {
+ long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=4;
+ }
+
+ if (i<=n-2) {
+ long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
+ long u=ones ^ b;
+ long twosA=(ones & b)|( u & c);
+ ones=u^c;
+
+ long foursA=twos&twosA;
+ twos=twos^twosA;
+
+ long eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=2;
+ }
+
+ if (i<n) {
+ tot += pop((A[i] | B[i]));
+ }
+
+ tot += (pop(fours)<<2)
+ + (pop(twos)<<1)
+ + pop(ones)
+ + (tot8<<3);
+
+ return tot;
+ }
+
+ /** Returns the popcount or cardinality of A & ~B
+ * Neither array is modified.
+ */
+ public static long pop_andnot(long[] A, long[] B, int wordOffset, int numWords) {
+ // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& ~B[\1]\)/g'
+ int n = wordOffset+numWords;
+ long tot=0, tot8=0;
+ long ones=0, twos=0, fours=0;
+
+ int i;
+ for (i = wordOffset; i <= n - 8; i+=8) {
+ /*** C macro from Hacker's Delight
+ #define CSA(h,l, a,b,c) \
+ {unsigned u = a ^ b; unsigned v = c; \
+ h = (a & b) | (u & v); l = u ^ v;}
+ ***/
+
+ long twosA,twosB,foursA,foursB,eights;
+
+ // CSA(twosA, ones, ones, (A[i] & ~B[i]), (A[i+1] & ~B[i+1]))
+ {
+ long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, (A[i+2] & ~B[i+2]), (A[i+3] & ~B[i+3]))
+ {
+ long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursA, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ //CSA(twosA, ones, ones, (A[i+4] & ~B[i+4]), (A[i+5] & ~B[i+5]))
+ {
+ long b=(A[i+4] & ~B[i+4]), c=(A[i+5] & ~B[i+5]);
+ long u=ones^b;
+ twosA=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, (A[i+6] & ~B[i+6]), (A[i+7] & ~B[i+7]))
+ {
+ long b=(A[i+6] & ~B[i+6]), c=(A[i+7] & ~B[i+7]);
+ long u=ones^b;
+ twosB=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursB, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursB=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+
+ //CSA(eights, fours, fours, foursA, foursB)
+ {
+ long u=fours^foursA;
+ eights=(fours&foursA)|(u&foursB);
+ fours=u^foursB;
+ }
+ tot8 += pop(eights);
+ }
+
+
+ if (i<=n-4) {
+ long twosA, twosB, foursA, eights;
+ {
+ long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ {
+ long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=4;
+ }
+
+ if (i<=n-2) {
+ long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
+ long u=ones ^ b;
+ long twosA=(ones & b)|( u & c);
+ ones=u^c;
+
+ long foursA=twos&twosA;
+ twos=twos^twosA;
+
+ long eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=2;
+ }
+
+ if (i<n) {
+ tot += pop((A[i] & ~B[i]));
+ }
+
+ tot += (pop(fours)<<2)
+ + (pop(twos)<<1)
+ + pop(ones)
+ + (tot8<<3);
+
+ return tot;
+ }
+
+ public static long pop_xor(long[] A, long[] B, int wordOffset, int numWords) {
+ int n = wordOffset+numWords;
+ long tot=0, tot8=0;
+ long ones=0, twos=0, fours=0;
+
+ int i;
+ for (i = wordOffset; i <= n - 8; i+=8) {
+ /*** C macro from Hacker's Delight
+ #define CSA(h,l, a,b,c) \
+ {unsigned u = a ^ b; unsigned v = c; \
+ h = (a & b) | (u & v); l = u ^ v;}
+ ***/
+
+ long twosA,twosB,foursA,foursB,eights;
+
+ // CSA(twosA, ones, ones, (A[i] ^ B[i]), (A[i+1] ^ B[i+1]))
+ {
+ long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, (A[i+2] ^ B[i+2]), (A[i+3] ^ B[i+3]))
+ {
+ long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursA, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ //CSA(twosA, ones, ones, (A[i+4] ^ B[i+4]), (A[i+5] ^ B[i+5]))
+ {
+ long b=(A[i+4] ^ B[i+4]), c=(A[i+5] ^ B[i+5]);
+ long u=ones^b;
+ twosA=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ // CSA(twosB, ones, ones, (A[i+6] ^ B[i+6]), (A[i+7] ^ B[i+7]))
+ {
+ long b=(A[i+6] ^ B[i+6]), c=(A[i+7] ^ B[i+7]);
+ long u=ones^b;
+ twosB=(ones&b)|(u&c);
+ ones=u^c;
+ }
+ //CSA(foursB, twos, twos, twosA, twosB)
+ {
+ long u=twos^twosA;
+ foursB=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+
+ //CSA(eights, fours, fours, foursA, foursB)
+ {
+ long u=fours^foursA;
+ eights=(fours&foursA)|(u&foursB);
+ fours=u^foursB;
+ }
+ tot8 += pop(eights);
+ }
+
+
+ if (i<=n-4) {
+ long twosA, twosB, foursA, eights;
+ {
+ long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
+ long u=ones ^ b;
+ twosA=(ones & b)|( u & c);
+ ones=u^c;
+ }
+ {
+ long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
+ long u=ones^b;
+ twosB =(ones&b)|(u&c);
+ ones=u^c;
+ }
+ {
+ long u=twos^twosA;
+ foursA=(twos&twosA)|(u&twosB);
+ twos=u^twosB;
+ }
+ eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=4;
+ }
+
+ if (i<=n-2) {
+ long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
+ long u=ones ^ b;
+ long twosA=(ones & b)|( u & c);
+ ones=u^c;
+
+ long foursA=twos&twosA;
+ twos=twos^twosA;
+
+ long eights=fours&foursA;
+ fours=fours^foursA;
+
+ tot8 += pop(eights);
+ i+=2;
+ }
+
+ if (i<n) {
+ tot += pop((A[i] ^ B[i]));
+ }
+
+ tot += (pop(fours)<<2)
+ + (pop(twos)<<1)
+ + pop(ones)
+ + (tot8<<3);
+
+ return tot;
+ }
+
+ /* python code to generate ntzTable
+ def ntz(val):
+ if val==0: return 8
+ i=0
+ while (val&0x01)==0:
+ i = i+1
+ val >>= 1
+ return i
+ print ','.join([ str(ntz(i)) for i in range(256) ])
+ ***/
+ /** table of number of trailing zeros in a byte */
+ public static readonly byte[] ntzTable = {8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0};
+
+
+ /** Returns number of trailing zeros in the 64 bit long value. */
+ public static int ntz(long val) {
+ // A full binary search to determine the low byte was slower than
+ // a linear search for nextSetBit(). This is most likely because
+ // the implementation of nextSetBit() shifts bits to the right, increasing
+ // the probability that the first non-zero byte is in the rhs.
+ //
+ // This implementation does a single binary search at the top level only
+ // so that all other bit shifting can be done on ints instead of longs to
+ // remain friendly to 32 bit architectures. In addition, the case of a
+ // non-zero first byte is checked for first because it is the most common
+ // in dense bit arrays.
+
+ //{DOUG-2.4.0: mod'd to do logical right shift (>>>); have to use unsigned types and >>
+ //int lower = (int)val;
+ //int lowByte = lower & 0xff;
+ //if (lowByte != 0) return ntzTable[lowByte];
+
+ //if (lower!=0) {
+ // lowByte = (lower>>>8) & 0xff;
+ // if (lowByte != 0) return ntzTable[lowByte] + 8;
+ // lowByte = (lower>>>16) & 0xff;
+ // if (lowByte != 0) return ntzTable[lowByte] + 16;
+ // // no need to mask off low byte for the last byte in the 32 bit word
+ // // no need to check for zero on the last byte either.
+ // return ntzTable[lower>>>24] + 24;
+ //} else {
+ // // grab upper 32 bits
+ // int upper=(int)(val>>32);
+ // lowByte = upper & 0xff;
+ // if (lowByte != 0) return ntzTable[lowByte] + 32;
+ // lowByte = (upper>>>8) & 0xff;
+ // if (lowByte != 0) return ntzTable[lowByte] + 40;
+ // lowByte = (upper>>>16) & 0xff;
+ // if (lowByte != 0) return ntzTable[lowByte] + 48;
+ // // no need to mask off low byte for the last byte in the 32 bit word
+ // // no need to check for zero on the last byte either.
+ // return ntzTable[upper>>>24] + 56;
+ //}
+ uint lower = (uint)val;
+ uint lowByte = lower & 0xff;
+ if (lowByte != 0) return ntzTable[lowByte];
+
+ if (lower!=0) {
+ lowByte = (lower>>8) & 0xff;
+ if (lowByte != 0) return ntzTable[lowByte] + 8;
+ lowByte = (lower>>16) & 0xff;
+ if (lowByte != 0) return ntzTable[lowByte] + 16;
+ // no need to mask off low byte for the last byte in the 32 bit word
+ // no need to check for zero on the last byte either.
+ return ntzTable[lower>>24] + 24;
+ } else {
+ // grab upper 32 bits
+ uint upper=(uint)(val>>32);
+ lowByte = upper & 0xff;
+ if (lowByte != 0) return ntzTable[lowByte] + 32;
+ lowByte = (upper>>8) & 0xff;
+ if (lowByte != 0) return ntzTable[lowByte] + 40;
+ lowByte = (upper>>16) & 0xff;
+ if (lowByte != 0) return ntzTable[lowByte] + 48;
+ // no need to mask off low byte for the last byte in the 32 bit word
+ // no need to check for zero on the last byte either.
+ return ntzTable[upper>>24] + 56;
+ }
+ }
+
+ /** returns 0 based index of first set bit
+ * (only works for x!=0)
+ * <br/> This is an alternate implementation of ntz()
+ */
+ public static int ntz2(long x) {
+ int n = 0;
+ int y = (int)x;
+ //{DOUG-2.4.0: mod'd to do logical right shift (>>>); have to use unsigned types and >>
+ //if (y==0) {n+=32; y = (int)((ulong)x>>32); } // the only 64 bit shift necessary
+ //if ((y & 0x0000FFFF) == 0) { n+=16; (uint)y>>=16; }
+ //if ((y & 0x000000FF) == 0) { n+=8; (uint)y>>=8; }
+ if (y==0) {n+=32; y = (int)((ulong)x>>32); } // the only 64 bit shift necessary
+ if ((y & 0x0000FFFF) == 0) { n+=16; y = (int)((uint)y>>16); }
+ if ((y & 0x000000FF) == 0) { n+=8; y= (int)((uint)y>>8); }
+ return (ntzTable[ y & 0xff ]) + n;
+ }
+
+ /** returns 0 based index of first set bit
+ * <br/> This is an alternate implementation of ntz()
+ */
+ public static int ntz3(long x) {
+ // another implementation taken from Hackers Delight, extended to 64 bits
+ // and converted to Java.
+ // Many 32 bit ntz algorithms are at http://www.hackersdelight.org/HDcode/ntz.cc
+ int n = 1;
+ //{DOUG-2.4.0: mod'd to do logical right shift (>>>); have to use unsigned types and >>
+ //// do the first step as a long, all others as ints.
+ //int y = (int)x;
+ //if (y==0) {n+=32; y = (int)(x>>>32); }
+ //if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
+ //if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
+ //if ((y & 0x0000000F) == 0) { n+=4; y>>>=4; }
+ //if ((y & 0x00000003) == 0) { n+=2; y>>>=2; }
+ //return n - (y & 1);
+ // do the first step as a long, all others as ints.
+ int y = (int)x;
+ if (y==0) {n+=32; y = (int)((ulong)x>>32); }
+ if ((y & 0x0000FFFF) == 0) { n+=16; y = (int)((uint)y>>16); }
+ if ((y & 0x000000FF) == 0) { n+=8; y = (int)((uint)y>>8); }
+ if ((y & 0x0000000F) == 0) { n+=4; y = (int)((uint)y>>4); }
+ if ((y & 0x00000003) == 0) { n+=2; y = (int)((uint)y>>2); }
+ return n - (y & 1);
+ }
+
+
+ /** returns true if v is a power of two or zero*/
+ public static bool isPowerOfTwo(int v) {
+ return ((v & (v-1)) == 0);
+ }
+
+ /** returns true if v is a power of two or zero*/
+ public static bool isPowerOfTwo(long v) {
+ return ((v & (v-1)) == 0);
+ }
+
+ /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
+ public static int nextHighestPowerOfTwo(int v) {
+ v--;
+ v |= v >> 1;
+ v |= v >> 2;
+ v |= v >> 4;
+ v |= v >> 8;
+ v |= v >> 16;
+ v++;
+ return v;
+ }
+
+ /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
+ public static long nextHighestPowerOfTwo(long v) {
+ v--;
+ v |= v >> 1;
+ v |= v >> 2;
+ v |= v >> 4;
+ v |= v >> 8;
+ v |= v >> 16;
+ v |= v >> 32;
+ v++;
+ return v;
+ }
+ }
+}
Modified: incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/BitVector.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/Util/BitVector.cs?rev=798995&r1=798994&r2=798995&view=diff
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/BitVector.cs (original)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/BitVector.cs Wed Jul 29 18:04:12 2009
@@ -70,7 +70,33 @@
bits[bit >> 3] &= (byte) (~ (1 << (bit & 7)));
count = - 1;
}
-
+
+ /// <summary>
+ /// Sets the value of bit to true and returns true if bit was already set.
+ /// </summary>
+ /// <param name="bit"></param>
+ /// <returns>true if bit was already set</returns>
+ public bool GetAndSet(int bit)
+ {
+ if (bit >= size)
+ throw new IndexOutOfRangeException("bit (" + bit + ") is out of this bit vector's range (" + size + ")");
+
+ int pos = bit >> 3;
+ int v = bits[pos];
+ int flag = 1 << (bit & 7);
+ if ((flag & v) != 0)
+ {
+ return true;
+ }
+ else
+ {
+ bits[pos] = (byte)(v | flag);
+ if (count != -1)
+ count++;
+ return false;
+ }
+ }
+
/// <summary>Returns <code>true</code> if <code>bit</code> is one and
/// <code>false</code> if it is zero.
/// </summary>
@@ -111,7 +137,6 @@
private static readonly byte[] BYTE_COUNTS = new byte[]{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
-
/// <summary>Writes this vector to the file <code>name</code> in Directory
/// <code>d</code>, in a format that can be read by the constructor {@link
/// #BitVector(Directory, String)}.
Added: incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/Cache.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/Util/Cache/Cache.cs?rev=798995&view=auto
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/Cache.cs (added)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/Cache.cs Wed Jul 29 18:04:12 2009
@@ -0,0 +1,114 @@
+/**
+ * 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.Cache
+{
+ /**
+ * Base class for cache implementations.
+ */
+ public abstract class Cache
+ {
+ /**
+ * Returns a thread-safe cache backed by the specified cache.
+ * In order to guarantee thread-safety, all access to the backed cache must
+ * be accomplished through the returned cache.
+ */
+ public static Cache SynchronizedCache_Renamed(Cache cache)
+ {
+ return cache.GetSynchronizedCache();
+ }
+
+ /**
+ * Puts a (key, value)-pair into the cache.
+ */
+ public abstract void Put(object key, object value);
+
+ /**
+ * Returns the value for the given key.
+ */
+ public abstract object Get(object key);
+
+ /**
+ * Returns whether the given key is in this cache.
+ */
+ public abstract bool ContainsKey(object key);
+
+ /**
+ * Closes the cache.
+ */
+ public abstract void Close();
+
+ /**
+ * Called by {@link #synchronizedCache(Cache)}. This method
+ * returns a {@link SynchronizedCache} instance that wraps
+ * this instance by default and can be overridden to return
+ * e. g. subclasses of {@link SynchronizedCache} or this
+ * in case this cache is already synchronized.
+ */
+ protected internal virtual Cache GetSynchronizedCache()
+ {
+ return new SynchronizedCache(this);
+ }
+
+ /**
+ * Simple Cache wrapper that synchronizes all
+ * calls that access the cache.
+ */
+ public class SynchronizedCache : Cache
+ {
+ object mutex;
+ Cache cache;
+
+ protected internal SynchronizedCache(Cache cache)
+ {
+ this.cache = cache;
+ this.mutex = this;
+ }
+
+ protected internal SynchronizedCache(Cache cache, object mutex)
+ {
+ this.cache = cache;
+ this.mutex = mutex;
+ }
+
+ public override void Put(object key, object value)
+ {
+ lock (mutex) { cache.Put(key, value); }
+ }
+
+ public override object Get(object key)
+ {
+ lock (mutex) { return cache.Get(key); }
+ }
+
+ public override bool ContainsKey(object key)
+ {
+ lock (mutex) { return cache.ContainsKey(key); }
+ }
+
+ public override void Close()
+ {
+ lock (mutex) { cache.Close(); }
+ }
+
+ protected internal override Cache GetSynchronizedCache()
+ {
+ return this;
+ }
+ }
+ }
+}
Added: incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs?rev=798995&view=auto
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs (added)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs Wed Jul 29 18:04:12 2009
@@ -0,0 +1,78 @@
+/**
+ * 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 Hashtable = System.Collections.Hashtable;
+using LinkedList = System.Collections.Generic.LinkedList<object>;
+using Math = System.Math;
+
+namespace Lucene.Net.Util.Cache
+{
+ public class SimpleLRUCache : SimpleMapCache
+ {
+ private const float LOADFACTOR = 0.75f;
+
+ private int cacheSize;
+ private LinkedList lru;
+
+ public SimpleLRUCache(int cacheSize)
+ : base(null)
+ {
+ this.cacheSize = cacheSize;
+ int capacity = (int)Math.Ceiling(cacheSize / LOADFACTOR) + 1;
+ base.map = new System.Collections.Hashtable(capacity, LOADFACTOR);
+
+ lru = new LinkedList();
+ }
+
+ public override void Put(object key, object value)
+ {
+ if (lru.Contains(key))
+ {
+ // move key to most recently used position
+ lru.Remove(key);
+ lru.AddFirst(key);
+ }
+ else
+ {
+ if (lru.Count == cacheSize)
+ {
+ object last = lru.Last;
+ lru.Remove(last);
+ // remove least recently used item from cache
+ base.map.Remove(last);
+ }
+ // place key in most recently used position
+ lru.AddFirst(key);
+ }
+
+ base.Put(key, value);
+ }
+
+ public override object Get(object key)
+ {
+ if (lru.Contains(key))
+ {
+ // if LRU data structure contains key, move the key
+ // to the "most recently used" position
+ lru.Remove(key);
+ lru.AddFirst(key);
+ }
+
+ return base.Get(key);
+ }
+ }
+}
Added: incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleMapCache.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/Util/Cache/SimpleMapCache.cs?rev=798995&view=auto
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleMapCache.cs (added)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleMapCache.cs Wed Jul 29 18:04:12 2009
@@ -0,0 +1,117 @@
+/**
+ * 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 Hashtable = System.Collections.Hashtable;
+using ICollection = System.Collections.ICollection;
+
+namespace Lucene.Net.Util.Cache
+{
+ /**
+ * Simple cache implementation that uses a HashMap to store (key, value) pairs.
+ * This cache is not synchronized, use {@link Cache#synchronizedCache(Cache)}
+ * if needed.
+ */
+ public class SimpleMapCache : Cache
+ {
+ protected Hashtable map;
+
+ public SimpleMapCache()
+ : this(new Hashtable())
+ {
+ }
+
+ public SimpleMapCache(Hashtable map)
+ {
+ this.map = map;
+ }
+
+ public override object Get(object key)
+ {
+ return map[key];
+ }
+
+ public override void Put(object key, object value)
+ {
+ map[key] = value;
+ }
+
+ public override void Close()
+ {
+ // NOOP
+ }
+
+ public override bool ContainsKey(object key)
+ {
+ return map.ContainsKey(key);
+ }
+
+ /**
+ * Returns a Set containing all keys in this cache.
+ */
+ public virtual ICollection keySet()
+ {
+ return map.Keys;
+ }
+
+ protected internal override Cache GetSynchronizedCache()
+ {
+ return new SynchronizedSimpleMapCache(this);
+ }
+
+ private class SynchronizedSimpleMapCache : SimpleMapCache
+ {
+ object mutex;
+ SimpleMapCache cache;
+
+ protected internal SynchronizedSimpleMapCache(SimpleMapCache cache)
+ {
+ this.cache = cache;
+ this.mutex = this;
+ }
+
+ public override void Put(object key, object value)
+ {
+ lock (mutex) { cache.Put(key, value); }
+ }
+
+ public override object Get(object key)
+ {
+ lock (mutex) { return cache.Get(key); }
+ }
+
+ public override bool ContainsKey(object key)
+ {
+ lock (mutex) { return cache.ContainsKey(key); }
+ }
+
+ public override void Close()
+ {
+ lock (mutex) { cache.Close(); }
+ }
+
+ public override ICollection keySet()
+ {
+ lock (mutex) { return cache.keySet(); }
+ }
+
+ protected internal override Cache GetSynchronizedCache()
+ {
+ return this;
+ }
+ }
+ }
+}
Added: incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/CloseableThreadLocal.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/Util/CloseableThreadLocal.cs?rev=798995&view=auto
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/CloseableThreadLocal.cs (added)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/CloseableThreadLocal.cs Wed Jul 29 18:04:12 2009
@@ -0,0 +1,84 @@
+/**
+ * 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.Threading;
+
+namespace Lucene.Net.Util
+{
+ // {{dougsale-2.4.0}}
+ // so here is the doc from the java version:
+
+ /** Java's builtin ThreadLocal has a serious flaw:
+ * it can take an arbitrarily long amount of time to
+ * dereference the things you had stored in it, even once the
+ * ThreadLocal instance itself is no longer referenced.
+ * This is because there is single, master map stored for
+ * each thread, which all ThreadLocals share, and that
+ * master map only periodically purges "stale" entries.
+ *
+ * While not technically a memory leak, because eventually
+ * the memory will be reclaimed, it can take a long time
+ * and you can easily hit OutOfMemoryError because from the
+ * GC's standpoint the stale entries are not reclaimaible.
+ *
+ * This class works around that, by only enrolling
+ * WeakReference values into the ThreadLocal, and
+ * separately holding a hard reference to each stored
+ * value. When you call {@link #close}, these hard
+ * references are cleared and then GC is freely able to
+ * reclaim space by objects stored in it.
+ */
+
+ // i'm not sure if C#'s Thread.SetData(System.LocalDataStoreSlot, object) has the same issue.
+ // For now, i'll just implement this using Thread.SetData(System.LocalDataStoreSlot, object)
+ // and Thread.GetData(System.LocalDataStoreSlot) so that we're API compliant.
+
+ public class CloseableThreadLocal
+ {
+ private System.LocalDataStoreSlot dataSlot;
+
+ public CloseableThreadLocal()
+ {
+ dataSlot = Thread.AllocateDataSlot();
+ }
+
+ virtual protected object InitialValue()
+ {
+ return null;
+ }
+
+ public object Get()
+ {
+ object v = Thread.GetData(dataSlot);
+ if (v == null)
+ {
+ v = InitialValue();
+ Set(v);
+ }
+ return v;
+ }
+
+ public void Set(object v)
+ {
+ Thread.SetData(dataSlot, v);
+ }
+
+ public void Close()
+ {
+ }
+ }
+}
Added: incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/DocIdBitSet.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/Util/DocIdBitSet.cs?rev=798995&view=auto
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/DocIdBitSet.cs (added)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/DocIdBitSet.cs Wed Jul 29 18:04:12 2009
@@ -0,0 +1,88 @@
+/**
+ * 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 BitArray = System.Collections.BitArray;
+using DocIdSet = Lucene.Net.Search.DocIdSet;
+using DocIdSetIterator = Lucene.Net.Search.DocIdSetIterator;
+
+namespace Lucene.Net.Util
+{
+ /// <summary>Simple DocIdSet and DocIdSetIterator backed by a BitArray</summary>
+ public class DocIdBitSet : DocIdSet
+ {
+ private BitArray bitArray;
+
+ public DocIdBitSet(BitArray bitArray)
+ {
+ this.bitArray = bitArray;
+ }
+
+ public override DocIdSetIterator Iterator()
+ {
+ return new DocIdBitSetIterator(bitArray);
+ }
+
+ /// <summary>Returns the underlying BitArray.</summary>
+ public BitArray GetBitSet()
+ {
+ return this.bitArray;
+ }
+
+ private class DocIdBitSetIterator : DocIdSetIterator
+ {
+ private int docId;
+ private BitArray bitArray;
+
+ internal DocIdBitSetIterator(BitArray bitArray)
+ {
+ this.bitArray = bitArray;
+ this.docId = -1;
+ }
+
+ public override int Doc()
+ {
+ System.Diagnostics.Debug.Assert(docId != -1);
+ return docId;
+ }
+
+ public override bool Next()
+ {
+ // (docId + 1) on next line requires -1 initial value for docNr:
+ return CheckNextDocId(SupportClass.BitSetSupport.NextSetBit(bitArray, docId + 1));
+ }
+
+ public override bool SkipTo(int skipDocNr)
+ {
+ return CheckNextDocId(SupportClass.BitSetSupport.NextSetBit(bitArray, skipDocNr));
+ }
+
+ private bool CheckNextDocId(int d)
+ {
+ if (d == -1)
+ { // -1 returned by BitArray.nextSetBit() when exhausted
+ docId = int.MaxValue;
+ return false;
+ }
+ else
+ {
+ docId = d;
+ return true;
+ }
+ }
+ }
+ }
+}