src/Lucene.Net.Tests/Util/TestOpenBitSet.cs - lucenenet - Git at Google

 /*
  * 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 Lucene.Net.Attributes;
 using Lucene.Net.Randomized.Generators;
 using Lucene.Net.Support;
 using NUnit.Framework;
 using System.Collections;

 namespace Lucene.Net.Util
 {
     using DocIdSetIterator = Lucene.Net.Search.DocIdSetIterator;

     [TestFixture]
     public class TestOpenBitSet : BaseDocIdSetTestCase<OpenBitSet>
     {
         public override OpenBitSet CopyOf(BitArray bs, int length)
         {
             OpenBitSet set = new OpenBitSet(length);
             for (int doc = bs.NextSetBit(0); doc != -1; doc = bs.NextSetBit(doc + 1))
             {
                 set.Set(doc);
             }
             return set;
         }

         internal virtual void DoGet(BitArray a, OpenBitSet b)
         {
             int max = a.Length;
             for (int i = 0; i < max; i++)
             {
                 if (a.SafeGet(i) != b.Get(i))
                 {
                     Assert.Fail("mismatch: BitSet=[" + i + "]=" + a.SafeGet(i));
                 }
                 if (a.SafeGet(i) != b.Get((long)i))
                 {
                     Assert.Fail("mismatch: BitSet=[" + i + "]=" + a.SafeGet(i));
                 }
             }
         }

         internal virtual void DoGetFast(BitArray a, OpenBitSet b, int max)
         {
             for (int i = 0; i < max; i++)
             {
                 if (a.SafeGet(i) != b.FastGet(i))
                 {
                     Assert.Fail("mismatch: BitSet=[" + i + "]=" + a.SafeGet(i));
                 }
                 if (a.SafeGet(i) != b.FastGet((long)i))
                 {
                     Assert.Fail("mismatch: BitSet=[" + i + "]=" + a.SafeGet(i));
                 }
             }
         }

         internal virtual void DoNextSetBit(BitArray a, OpenBitSet b)
         {
             int aa = -1, bb = -1;
             do
             {
                 aa = a.NextSetBit(aa + 1);
                 bb = b.NextSetBit(bb + 1);
                 Assert.AreEqual(aa, bb);
             } while (aa >= 0);
         }

         internal virtual void DoNextSetBitLong(BitArray a, OpenBitSet b)
         {
             int aa = -1, bb = -1;
             do
             {
                 aa = a.NextSetBit(aa + 1);
                 bb = (int)b.NextSetBit((long)(bb + 1));
                 Assert.AreEqual(aa, bb);
             } while (aa >= 0);
         }

         internal virtual void DoPrevSetBit(BitArray a, OpenBitSet b)
         {
             int aa = a.Length + Random.Next(100);
             int bb = aa;
             do
             {
                 // aa = a.PrevSetBit(aa-1);
                 aa--;
                 while ((aa >= 0) && (!a.SafeGet(aa)))
                 {
                     aa--;
                 }
                 bb = b.PrevSetBit(bb - 1);
                 Assert.AreEqual(aa, bb);
             } while (aa >= 0);
         }

         internal virtual void DoPrevSetBitLong(BitArray a, OpenBitSet b)
         {
             int aa = a.Length + Random.Next(100);
             int bb = aa;
             do
             {
                 // aa = a.PrevSetBit(aa-1);
                 aa--;
                 while ((aa >= 0) && (!a.SafeGet(aa)))
                 {
                     aa--;
                 }
                 bb = (int)b.PrevSetBit((long)(bb - 1));
                 Assert.AreEqual(aa, bb);
             } while (aa >= 0);
         }

         // test interleaving different OpenBitSetIterator.Next()/skipTo()
         internal virtual void DoIterate(BitArray a, OpenBitSet b, int mode)
         {
             if (mode == 1)
             {
                 DoIterate1(a, b);
             }
             if (mode == 2)
             {
                 DoIterate2(a, b);
             }
         }

         internal virtual void DoIterate1(BitArray a, OpenBitSet b)
         {
             int aa = -1, bb = -1;
             OpenBitSetIterator iterator = new OpenBitSetIterator(b);
             do
             {
                 aa = a.NextSetBit(aa + 1);
                 bb = Random.NextBoolean() ? iterator.NextDoc() : iterator.Advance(bb + 1);
                 Assert.AreEqual(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
             } while (aa >= 0);
         }

         internal virtual void DoIterate2(BitArray a, OpenBitSet b)
         {
             int aa = -1, bb = -1;
             OpenBitSetIterator iterator = new OpenBitSetIterator(b);
             do
             {
                 aa = a.NextSetBit(aa + 1);
                 bb = Random.NextBoolean() ? iterator.NextDoc() : iterator.Advance(bb + 1);
                 Assert.AreEqual(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
             } while (aa >= 0);
         }

         internal virtual void DoRandomSets(int maxSize, int iter, int mode)
         {
             BitArray a0 = null;
             OpenBitSet b0 = null;

             for (int i = 0; i < iter; i++)
             {
                 int sz = Random.Next(maxSize);
                 BitArray a = new BitArray(sz);
                 OpenBitSet b = new OpenBitSet(sz);

                 // test the various ways of setting bits
                 if (sz > 0)
                 {
                     int nOper = Random.Next(sz);
                     for (int j = 0; j < nOper; j++)
                     {
                         int idx;

                         idx = Random.Next(sz);
                         a.SafeSet(idx, true);
                         b.FastSet(idx);

                         idx = Random.Next(sz);
                         a.SafeSet(idx, true);
                         b.FastSet((long)idx);

                         idx = Random.Next(sz);
                         a.SafeSet(idx, false);
                         b.FastClear(idx);

                         idx = Random.Next(sz);
                         a.SafeSet(idx, false);
                         b.FastClear((long)idx);

                         idx = Random.Next(sz);
                         a.SafeSet(idx, !a.SafeGet(idx));
                         b.FastFlip(idx);

                         bool val = b.FlipAndGet(idx);
                         bool val2 = b.FlipAndGet(idx);
                         Assert.IsTrue(val != val2);

                         idx = Random.Next(sz);
                         a.SafeSet(idx, !a.SafeGet(idx));
                         b.FastFlip((long)idx);

                         val = b.FlipAndGet((long)idx);
                         val2 = b.FlipAndGet((long)idx);
                         Assert.IsTrue(val != val2);

                         val = b.GetAndSet(idx);
                         Assert.IsTrue(val2 == val);
                         Assert.IsTrue(b.Get(idx));

                         if (!val)
                         {
                             b.FastClear(idx);
                         }
                         Assert.IsTrue(b.Get(idx) == val);
                     }
                 }

                 // test that the various ways of accessing the bits are equivalent
                 DoGet(a, b);
                 DoGetFast(a, b, sz);

                 // test ranges, including possible extension
                 int fromIndex, toIndex;
                 fromIndex = Random.Next(sz + 80);
                 toIndex = fromIndex + Random.Next((sz >> 1) + 1);

                 BitArray aa = new BitArray(a);
                 // C# BitArray class does not support dynamic sizing.
                 // We have to explicitly change its size using the Length attribute.
                 if (toIndex > aa.Length)
                 {
                     aa.Length = toIndex;
                 }
                 aa.Flip(fromIndex, toIndex);
                 OpenBitSet bb = (OpenBitSet)b.Clone();
                 bb.Flip(fromIndex, toIndex);

                 DoIterate(aa, bb, mode); // a problem here is from flip or doIterate

                 fromIndex = Random.Next(sz + 80);
                 toIndex = fromIndex + Random.Next((sz >> 1) + 1);
                 aa = new BitArray(a);
                 if (toIndex > aa.Length)
                 {
                     aa.Length = toIndex;
                 }
                 aa.Clear(fromIndex, toIndex);
                 bb = (OpenBitSet)b.Clone();
                 bb.Clear(fromIndex, toIndex);

                 DoNextSetBit(aa, bb); // a problem here is from clear() or nextSetBit
                 DoNextSetBitLong(aa, bb);

                 DoPrevSetBit(aa, bb);
                 DoPrevSetBitLong(aa, bb);

                 fromIndex = Random.Next(sz + 80);
                 toIndex = fromIndex + Random.Next((sz >> 1) + 1);
                 aa = new BitArray(a);
                 if (toIndex > aa.Length)
                 {
                     aa.Length = toIndex;
                 }
                 aa.Set(fromIndex, toIndex);
                 bb = (OpenBitSet)b.Clone();
                 bb.Set(fromIndex, toIndex);

                 DoNextSetBit(aa, bb); // a problem here is from set() or nextSetBit
                 DoNextSetBitLong(aa, bb);

                 DoPrevSetBit(aa, bb);
                 DoPrevSetBitLong(aa, bb);

                 if (a0 != null)
                 {
                     aa = new BitArray(a);
                     BitArray aa0 = new BitArray(a0);
                     int largest = Math.Max(a.Length, a0.Length);
                     aa.Length = aa0.Length = largest;
                     // BitWiseEquals needs both arrays to be the same size for succeeding.
                     // We could enlarge the smallest of a and a0, but then the tests below
                     // won't test "UnequalLengths" operations.
                     Assert.AreEqual(aa.BitWiseEquals(aa0), b.Equals(b0));

                     Assert.AreEqual(a.Cardinality(), b.Cardinality());

                     BitArray a_and = new BitArray(a);
                     a_and = a_and.And_UnequalLengths(a0);
                     BitArray a_or = new BitArray(a);
                     a_or = a_or.Or_UnequalLengths(a0);
                     BitArray a_xor = new BitArray(a);
                     a_xor = a_xor.Xor_UnequalLengths(a0);
                     BitArray a_andn = new BitArray(a);
                     a_andn.AndNot(a0);

                     OpenBitSet b_and = (OpenBitSet)b.Clone();
                     Assert.AreEqual(b, b_and);
                     b_and.And(b0);
                     OpenBitSet b_or = (OpenBitSet)b.Clone();
                     b_or.Or(b0);
                     OpenBitSet b_xor = (OpenBitSet)b.Clone();
                     b_xor.Xor(b0);
                     OpenBitSet b_andn = (OpenBitSet)b.Clone();
                     b_andn.AndNot(b0);

                     DoIterate(a_and, b_and, mode);
                     DoIterate(a_or, b_or, mode);
                     DoIterate(a_xor, b_xor, mode);
                     DoIterate(a_andn, b_andn, mode);

                     Assert.AreEqual(a_and.Cardinality(), b_and.Cardinality());
                     Assert.AreEqual(a_or.Cardinality(), b_or.Cardinality());
                     Assert.AreEqual(a_xor.Cardinality(), b_xor.Cardinality());
                     Assert.AreEqual(a_andn.Cardinality(), b_andn.Cardinality());

                     // test non-mutating popcounts
                     Assert.AreEqual(b_and.Cardinality(), OpenBitSet.IntersectionCount(b, b0));
                     Assert.AreEqual(b_or.Cardinality(), OpenBitSet.UnionCount(b, b0));
                     Assert.AreEqual(b_xor.Cardinality(), OpenBitSet.XorCount(b, b0));
                     Assert.AreEqual(b_andn.Cardinality(), OpenBitSet.AndNotCount(b, b0));
                 }

                 a0 = a;
                 b0 = b;
             }
         }

         // large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
         // larger testsuite.
         [Test, LongRunningTest]
         public virtual void TestSmall()
         {
             DoRandomSets(AtLeast(1200), AtLeast(1000), 1);
             DoRandomSets(AtLeast(1200), AtLeast(1000), 2);
         }

         [Test, LuceneNetSpecific]
         public void TestClearSmall()
         {
             OpenBitSet a = new OpenBitSet(30);   // 0110010111001000101101001001110...0
             int[] onesA = { 1, 2, 5, 7, 8, 9, 12, 16, 18, 19, 21, 24, 27, 28, 29 };

             for (int i = 0; i < onesA.size(); i++)
             {
                 a.Set(onesA[i]);
             }

             OpenBitSet b = new OpenBitSet(30);   // 0110000001001000101101001001110...0
             int[] onesB = { 1, 2, 9, 12, 16, 18, 19, 21, 24, 27, 28, 29 };

             for (int i = 0; i < onesB.size(); i++)
             {
                 b.Set(onesB[i]);
             }

             a.Clear(5, 9);
             Assert.True(a.Equals(b));

             a.Clear(9, 10);
             Assert.False(a.Equals(b));

             a.Set(9);
             Assert.True(a.Equals(b));
         }

         [Test, LuceneNetSpecific]
         public void TestClearLarge()
         {
             int iters = AtLeast(1000);
             for (int it = 0; it < iters; it++)
             {
                 Random random = new Random();
                 int sz = AtLeast(1200);
                 OpenBitSet a = new OpenBitSet(sz);
                 OpenBitSet b = new OpenBitSet(sz);
                 int from = random.Next(sz - 1);
                 int to = random.Next(from, sz);

                 for (int i = 0; i < sz / 2; i++)
                 {
                     int index = random.Next(sz - 1);
                     a.Set(index);

                     if (index < from || index >= to)
                     {
                         b.Set(index);
                     }
                 }

                 a.Clear(from, to);
                 Assert.True(a.Equals(b));
             }
         }

         // uncomment to run a bigger test (~2 minutes).
         /*
         public void TestBig() {
           doRandomSets(2000,200000, 1);
           doRandomSets(2000,200000, 2);
         }
         */

         [Test]
         public virtual void TestEquals()
         {
             OpenBitSet b1 = new OpenBitSet(1111);
             OpenBitSet b2 = new OpenBitSet(2222);
             Assert.IsTrue(b1.Equals(b2));
             Assert.IsTrue(b2.Equals(b1));
             b1.Set(10);
             Assert.IsFalse(b1.Equals(b2));
             Assert.IsFalse(b2.Equals(b1));
             b2.Set(10);
             Assert.IsTrue(b1.Equals(b2));
             Assert.IsTrue(b2.Equals(b1));
             b2.Set(2221);
             Assert.IsFalse(b1.Equals(b2));
             Assert.IsFalse(b2.Equals(b1));
             b1.Set(2221);
             Assert.IsTrue(b1.Equals(b2));
             Assert.IsTrue(b2.Equals(b1));

             // try different type of object
             Assert.IsFalse(b1.Equals(new object()));
         }

         [Test]
         public virtual void TestHashCodeEquals()
         {
             OpenBitSet bs1 = new OpenBitSet(200);
             OpenBitSet bs2 = new OpenBitSet(64);
             bs1.Set(3);
             bs2.Set(3);
             Assert.AreEqual(bs1, bs2);
             Assert.AreEqual(bs1.GetHashCode(), bs2.GetHashCode());
         }

         private OpenBitSet MakeOpenBitSet(int[] a)
         {
             OpenBitSet bs = new OpenBitSet();
             foreach (int e in a)
             {
                 bs.Set(e);
             }
             return bs;
         }

         private BitArray MakeBitSet(int[] a)
         {
             BitArray bs = new BitArray(a.Length);
             foreach (int e in a)
             {
                 bs.SafeSet(e, true);
             }
             return bs;
         }

         private void CheckPrevSetBitArray(int[] a)
         {
             OpenBitSet obs = MakeOpenBitSet(a);
             BitArray bs = MakeBitSet(a);
             DoPrevSetBit(bs, obs);
         }

         [Test]
         public virtual void TestPrevSetBit()
         {
             CheckPrevSetBitArray(new int[] { });
             CheckPrevSetBitArray(new int[] { 0 });
             CheckPrevSetBitArray(new int[] { 0, 2 });
         }

         [Test]
         public virtual void TestEnsureCapacity()
         {
             OpenBitSet bits = new OpenBitSet(1);
             int bit = Random.Next(100) + 10;
             bits.EnsureCapacity(bit); // make room for more bits
             bits.FastSet(bit - 1);
             Assert.IsTrue(bits.FastGet(bit - 1));
             bits.EnsureCapacity(bit + 1);
             bits.FastSet(bit);
             Assert.IsTrue(bits.FastGet(bit));
             bits.EnsureCapacity(3); // should not change numBits nor grow the array
             bits.FastSet(3);
             Assert.IsTrue(bits.FastGet(3));
             bits.FastSet(bit - 1);
             Assert.IsTrue(bits.FastGet(bit - 1));

             // test ensureCapacityWords
             int numWords = Random.Next(10) + 2; // make sure we grow the array (at least 128 bits)
             bits.EnsureCapacityWords(numWords);
             bit = TestUtil.NextInt32(Random, 127, (numWords << 6) - 1); // pick a bit >= to 128, but still within range
             bits.FastSet(bit);
             Assert.IsTrue(bits.FastGet(bit));
             bits.FastClear(bit);
             Assert.IsFalse(bits.FastGet(bit));
             bits.FastFlip(bit);
             Assert.IsTrue(bits.FastGet(bit));
             bits.EnsureCapacityWords(2); // should not change numBits nor grow the array
             bits.FastSet(3);
             Assert.IsTrue(bits.FastGet(3));
             bits.FastSet(bit - 1);
             Assert.IsTrue(bits.FastGet(bit - 1));
         }

         [Test, LuceneNetSpecific] // https://github.com/apache/lucenenet/pull/154
         public virtual void TestXorWithDifferentCapacity()
         {
             OpenBitSet smaller = new OpenBitSet(2);
             OpenBitSet larger = new OpenBitSet(64 * 10000);

             larger.Set(64 * 10000 - 1);
             larger.Set(65);
             larger.Set(3);
             smaller.Set(3);
             smaller.Set(66);

             smaller.Xor(larger);
             Assert.IsTrue(smaller.Get(64 * 10000 - 1));
             Assert.IsTrue(smaller.Get(65));
             Assert.IsFalse(smaller.Get(3));
             Assert.IsTrue(smaller.Get(66));
         }
     }
 }
	/*
	* 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 Lucene.Net.Attributes;
	using Lucene.Net.Randomized.Generators;
	using Lucene.Net.Support;
	using NUnit.Framework;
	using System.Collections;

	namespace Lucene.Net.Util
	{
	using DocIdSetIterator = Lucene.Net.Search.DocIdSetIterator;

	[TestFixture]
	public class TestOpenBitSet : BaseDocIdSetTestCase<OpenBitSet>
	{
	public override OpenBitSet CopyOf(BitArray bs, int length)
	{
	OpenBitSet set = new OpenBitSet(length);
	for (int doc = bs.NextSetBit(0); doc != -1; doc = bs.NextSetBit(doc + 1))
	{
	set.Set(doc);
	}
	return set;
	}

	internal virtual void DoGet(BitArray a, OpenBitSet b)
	{
	int max = a.Length;
	for (int i = 0; i < max; i++)
	{
	if (a.SafeGet(i) != b.Get(i))
	{
	Assert.Fail("mismatch: BitSet=[" + i + "]=" + a.SafeGet(i));
	}
	if (a.SafeGet(i) != b.Get((long)i))
	{
	Assert.Fail("mismatch: BitSet=[" + i + "]=" + a.SafeGet(i));
	}
	}
	}

	internal virtual void DoGetFast(BitArray a, OpenBitSet b, int max)
	{
	for (int i = 0; i < max; i++)
	{
	if (a.SafeGet(i) != b.FastGet(i))
	{
	Assert.Fail("mismatch: BitSet=[" + i + "]=" + a.SafeGet(i));
	}
	if (a.SafeGet(i) != b.FastGet((long)i))
	{
	Assert.Fail("mismatch: BitSet=[" + i + "]=" + a.SafeGet(i));
	}
	}
	}

	internal virtual void DoNextSetBit(BitArray a, OpenBitSet b)
	{
	int aa = -1, bb = -1;
	do
	{
	aa = a.NextSetBit(aa + 1);
	bb = b.NextSetBit(bb + 1);
	Assert.AreEqual(aa, bb);
	} while (aa >= 0);
	}

	internal virtual void DoNextSetBitLong(BitArray a, OpenBitSet b)
	{
	int aa = -1, bb = -1;
	do
	{
	aa = a.NextSetBit(aa + 1);
	bb = (int)b.NextSetBit((long)(bb + 1));
	Assert.AreEqual(aa, bb);
	} while (aa >= 0);
	}

	internal virtual void DoPrevSetBit(BitArray a, OpenBitSet b)
	{
	int aa = a.Length + Random.Next(100);
	int bb = aa;
	do
	{
	// aa = a.PrevSetBit(aa-1);
	aa--;
	while ((aa >= 0) && (!a.SafeGet(aa)))
	{
	aa--;
	}
	bb = b.PrevSetBit(bb - 1);
	Assert.AreEqual(aa, bb);
	} while (aa >= 0);
	}

	internal virtual void DoPrevSetBitLong(BitArray a, OpenBitSet b)
	{
	int aa = a.Length + Random.Next(100);
	int bb = aa;
	do
	{
	// aa = a.PrevSetBit(aa-1);
	aa--;
	while ((aa >= 0) && (!a.SafeGet(aa)))
	{
	aa--;
	}
	bb = (int)b.PrevSetBit((long)(bb - 1));
	Assert.AreEqual(aa, bb);
	} while (aa >= 0);
	}

	// test interleaving different OpenBitSetIterator.Next()/skipTo()
	internal virtual void DoIterate(BitArray a, OpenBitSet b, int mode)
	{
	if (mode == 1)
	{
	DoIterate1(a, b);
	}
	if (mode == 2)
	{
	DoIterate2(a, b);
	}
	}

	internal virtual void DoIterate1(BitArray a, OpenBitSet b)
	{
	int aa = -1, bb = -1;
	OpenBitSetIterator iterator = new OpenBitSetIterator(b);
	do
	{
	aa = a.NextSetBit(aa + 1);
	bb = Random.NextBoolean() ? iterator.NextDoc() : iterator.Advance(bb + 1);
	Assert.AreEqual(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
	} while (aa >= 0);
	}

	internal virtual void DoIterate2(BitArray a, OpenBitSet b)
	{
	int aa = -1, bb = -1;
	OpenBitSetIterator iterator = new OpenBitSetIterator(b);
	do
	{
	aa = a.NextSetBit(aa + 1);
	bb = Random.NextBoolean() ? iterator.NextDoc() : iterator.Advance(bb + 1);
	Assert.AreEqual(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
	} while (aa >= 0);
	}

	internal virtual void DoRandomSets(int maxSize, int iter, int mode)
	{
	BitArray a0 = null;
	OpenBitSet b0 = null;

	for (int i = 0; i < iter; i++)
	{
	int sz = Random.Next(maxSize);
	BitArray a = new BitArray(sz);
	OpenBitSet b = new OpenBitSet(sz);

	// test the various ways of setting bits
	if (sz > 0)
	{
	int nOper = Random.Next(sz);
	for (int j = 0; j < nOper; j++)
	{
	int idx;

	idx = Random.Next(sz);
	a.SafeSet(idx, true);
	b.FastSet(idx);

	idx = Random.Next(sz);
	a.SafeSet(idx, true);
	b.FastSet((long)idx);

	idx = Random.Next(sz);
	a.SafeSet(idx, false);
	b.FastClear(idx);

	idx = Random.Next(sz);
	a.SafeSet(idx, false);
	b.FastClear((long)idx);

	idx = Random.Next(sz);
	a.SafeSet(idx, !a.SafeGet(idx));
	b.FastFlip(idx);

	bool val = b.FlipAndGet(idx);
	bool val2 = b.FlipAndGet(idx);
	Assert.IsTrue(val != val2);

	idx = Random.Next(sz);
	a.SafeSet(idx, !a.SafeGet(idx));
	b.FastFlip((long)idx);

	val = b.FlipAndGet((long)idx);
	val2 = b.FlipAndGet((long)idx);
	Assert.IsTrue(val != val2);

	val = b.GetAndSet(idx);
	Assert.IsTrue(val2 == val);
	Assert.IsTrue(b.Get(idx));

	if (!val)
	{
	b.FastClear(idx);
	}
	Assert.IsTrue(b.Get(idx) == val);
	}
	}

	// test that the various ways of accessing the bits are equivalent
	DoGet(a, b);
	DoGetFast(a, b, sz);

	// test ranges, including possible extension
	int fromIndex, toIndex;
	fromIndex = Random.Next(sz + 80);
	toIndex = fromIndex + Random.Next((sz >> 1) + 1);

	BitArray aa = new BitArray(a);
	// C# BitArray class does not support dynamic sizing.
	// We have to explicitly change its size using the Length attribute.
	if (toIndex > aa.Length)
	{
	aa.Length = toIndex;
	}
	aa.Flip(fromIndex, toIndex);
	OpenBitSet bb = (OpenBitSet)b.Clone();
	bb.Flip(fromIndex, toIndex);

	DoIterate(aa, bb, mode); // a problem here is from flip or doIterate

	fromIndex = Random.Next(sz + 80);
	toIndex = fromIndex + Random.Next((sz >> 1) + 1);
	aa = new BitArray(a);
	if (toIndex > aa.Length)
	{
	aa.Length = toIndex;
	}
	aa.Clear(fromIndex, toIndex);
	bb = (OpenBitSet)b.Clone();
	bb.Clear(fromIndex, toIndex);

	DoNextSetBit(aa, bb); // a problem here is from clear() or nextSetBit
	DoNextSetBitLong(aa, bb);

	DoPrevSetBit(aa, bb);
	DoPrevSetBitLong(aa, bb);

	fromIndex = Random.Next(sz + 80);
	toIndex = fromIndex + Random.Next((sz >> 1) + 1);
	aa = new BitArray(a);
	if (toIndex > aa.Length)
	{
	aa.Length = toIndex;
	}
	aa.Set(fromIndex, toIndex);
	bb = (OpenBitSet)b.Clone();
	bb.Set(fromIndex, toIndex);

	DoNextSetBit(aa, bb); // a problem here is from set() or nextSetBit
	DoNextSetBitLong(aa, bb);

	DoPrevSetBit(aa, bb);
	DoPrevSetBitLong(aa, bb);

	if (a0 != null)
	{
	aa = new BitArray(a);
	BitArray aa0 = new BitArray(a0);
	int largest = Math.Max(a.Length, a0.Length);
	aa.Length = aa0.Length = largest;
	// BitWiseEquals needs both arrays to be the same size for succeeding.
	// We could enlarge the smallest of a and a0, but then the tests below
	// won't test "UnequalLengths" operations.
	Assert.AreEqual(aa.BitWiseEquals(aa0), b.Equals(b0));

	Assert.AreEqual(a.Cardinality(), b.Cardinality());

	BitArray a_and = new BitArray(a);
	a_and = a_and.And_UnequalLengths(a0);
	BitArray a_or = new BitArray(a);
	a_or = a_or.Or_UnequalLengths(a0);
	BitArray a_xor = new BitArray(a);
	a_xor = a_xor.Xor_UnequalLengths(a0);
	BitArray a_andn = new BitArray(a);
	a_andn.AndNot(a0);

	OpenBitSet b_and = (OpenBitSet)b.Clone();
	Assert.AreEqual(b, b_and);
	b_and.And(b0);
	OpenBitSet b_or = (OpenBitSet)b.Clone();
	b_or.Or(b0);
	OpenBitSet b_xor = (OpenBitSet)b.Clone();
	b_xor.Xor(b0);
	OpenBitSet b_andn = (OpenBitSet)b.Clone();
	b_andn.AndNot(b0);

	DoIterate(a_and, b_and, mode);
	DoIterate(a_or, b_or, mode);
	DoIterate(a_xor, b_xor, mode);
	DoIterate(a_andn, b_andn, mode);

	Assert.AreEqual(a_and.Cardinality(), b_and.Cardinality());
	Assert.AreEqual(a_or.Cardinality(), b_or.Cardinality());
	Assert.AreEqual(a_xor.Cardinality(), b_xor.Cardinality());
	Assert.AreEqual(a_andn.Cardinality(), b_andn.Cardinality());

	// test non-mutating popcounts
	Assert.AreEqual(b_and.Cardinality(), OpenBitSet.IntersectionCount(b, b0));
	Assert.AreEqual(b_or.Cardinality(), OpenBitSet.UnionCount(b, b0));
	Assert.AreEqual(b_xor.Cardinality(), OpenBitSet.XorCount(b, b0));
	Assert.AreEqual(b_andn.Cardinality(), OpenBitSet.AndNotCount(b, b0));
	}

	a0 = a;
	b0 = b;
	}
	}

	// large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
	// larger testsuite.
	[Test, LongRunningTest]
	public virtual void TestSmall()
	{
	DoRandomSets(AtLeast(1200), AtLeast(1000), 1);
	DoRandomSets(AtLeast(1200), AtLeast(1000), 2);
	}

	[Test, LuceneNetSpecific]
	public void TestClearSmall()
	{
	OpenBitSet a = new OpenBitSet(30); // 0110010111001000101101001001110...0
	int[] onesA = { 1, 2, 5, 7, 8, 9, 12, 16, 18, 19, 21, 24, 27, 28, 29 };

	for (int i = 0; i < onesA.size(); i++)
	{
	a.Set(onesA[i]);
	}

	OpenBitSet b = new OpenBitSet(30); // 0110000001001000101101001001110...0
	int[] onesB = { 1, 2, 9, 12, 16, 18, 19, 21, 24, 27, 28, 29 };

	for (int i = 0; i < onesB.size(); i++)
	{
	b.Set(onesB[i]);
	}

	a.Clear(5, 9);
	Assert.True(a.Equals(b));

	a.Clear(9, 10);
	Assert.False(a.Equals(b));

	a.Set(9);
	Assert.True(a.Equals(b));
	}

	[Test, LuceneNetSpecific]
	public void TestClearLarge()
	{
	int iters = AtLeast(1000);
	for (int it = 0; it < iters; it++)
	{
	Random random = new Random();
	int sz = AtLeast(1200);
	OpenBitSet a = new OpenBitSet(sz);
	OpenBitSet b = new OpenBitSet(sz);
	int from = random.Next(sz - 1);
	int to = random.Next(from, sz);

	for (int i = 0; i < sz / 2; i++)
	{
	int index = random.Next(sz - 1);
	a.Set(index);

	if (index < from \|\| index >= to)
	{
	b.Set(index);
	}
	}

	a.Clear(from, to);
	Assert.True(a.Equals(b));
	}
	}

	// uncomment to run a bigger test (~2 minutes).
	/*
	public void TestBig() {
	doRandomSets(2000,200000, 1);
	doRandomSets(2000,200000, 2);
	}
	*/

	[Test]
	public virtual void TestEquals()
	{
	OpenBitSet b1 = new OpenBitSet(1111);
	OpenBitSet b2 = new OpenBitSet(2222);
	Assert.IsTrue(b1.Equals(b2));
	Assert.IsTrue(b2.Equals(b1));
	b1.Set(10);
	Assert.IsFalse(b1.Equals(b2));
	Assert.IsFalse(b2.Equals(b1));
	b2.Set(10);
	Assert.IsTrue(b1.Equals(b2));
	Assert.IsTrue(b2.Equals(b1));
	b2.Set(2221);
	Assert.IsFalse(b1.Equals(b2));
	Assert.IsFalse(b2.Equals(b1));
	b1.Set(2221);
	Assert.IsTrue(b1.Equals(b2));
	Assert.IsTrue(b2.Equals(b1));

	// try different type of object
	Assert.IsFalse(b1.Equals(new object()));
	}

	[Test]
	public virtual void TestHashCodeEquals()
	{
	OpenBitSet bs1 = new OpenBitSet(200);
	OpenBitSet bs2 = new OpenBitSet(64);
	bs1.Set(3);
	bs2.Set(3);
	Assert.AreEqual(bs1, bs2);
	Assert.AreEqual(bs1.GetHashCode(), bs2.GetHashCode());
	}

	private OpenBitSet MakeOpenBitSet(int[] a)
	{
	OpenBitSet bs = new OpenBitSet();
	foreach (int e in a)
	{
	bs.Set(e);
	}
	return bs;
	}

	private BitArray MakeBitSet(int[] a)
	{
	BitArray bs = new BitArray(a.Length);
	foreach (int e in a)
	{
	bs.SafeSet(e, true);
	}
	return bs;
	}

	private void CheckPrevSetBitArray(int[] a)
	{
	OpenBitSet obs = MakeOpenBitSet(a);
	BitArray bs = MakeBitSet(a);
	DoPrevSetBit(bs, obs);
	}

	[Test]
	public virtual void TestPrevSetBit()
	{
	CheckPrevSetBitArray(new int[] { });
	CheckPrevSetBitArray(new int[] { 0 });
	CheckPrevSetBitArray(new int[] { 0, 2 });
	}

	[Test]
	public virtual void TestEnsureCapacity()
	{
	OpenBitSet bits = new OpenBitSet(1);
	int bit = Random.Next(100) + 10;
	bits.EnsureCapacity(bit); // make room for more bits
	bits.FastSet(bit - 1);
	Assert.IsTrue(bits.FastGet(bit - 1));
	bits.EnsureCapacity(bit + 1);
	bits.FastSet(bit);
	Assert.IsTrue(bits.FastGet(bit));
	bits.EnsureCapacity(3); // should not change numBits nor grow the array
	bits.FastSet(3);
	Assert.IsTrue(bits.FastGet(3));
	bits.FastSet(bit - 1);
	Assert.IsTrue(bits.FastGet(bit - 1));

	// test ensureCapacityWords
	int numWords = Random.Next(10) + 2; // make sure we grow the array (at least 128 bits)
	bits.EnsureCapacityWords(numWords);
	bit = TestUtil.NextInt32(Random, 127, (numWords << 6) - 1); // pick a bit >= to 128, but still within range
	bits.FastSet(bit);
	Assert.IsTrue(bits.FastGet(bit));
	bits.FastClear(bit);
	Assert.IsFalse(bits.FastGet(bit));
	bits.FastFlip(bit);
	Assert.IsTrue(bits.FastGet(bit));
	bits.EnsureCapacityWords(2); // should not change numBits nor grow the array
	bits.FastSet(3);
	Assert.IsTrue(bits.FastGet(3));
	bits.FastSet(bit - 1);
	Assert.IsTrue(bits.FastGet(bit - 1));
	}

	[Test, LuceneNetSpecific] // https://github.com/apache/lucenenet/pull/154
	public virtual void TestXorWithDifferentCapacity()
	{
	OpenBitSet smaller = new OpenBitSet(2);
	OpenBitSet larger = new OpenBitSet(64 * 10000);

	larger.Set(64 * 10000 - 1);
	larger.Set(65);
	larger.Set(3);
	smaller.Set(3);
	smaller.Set(66);

	smaller.Xor(larger);
	Assert.IsTrue(smaller.Get(64 * 10000 - 1));
	Assert.IsTrue(smaller.Get(65));
	Assert.IsFalse(smaller.Get(3));
	Assert.IsTrue(smaller.Get(66));
	}
	}
	}