| /* |
| * 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.Support; |
| using NUnit.Framework; |
| |
| using DocIdSetIterator = Lucene.Net.Search.DocIdSetIterator; |
| |
| namespace Lucene.Net.Util |
| { |
| |
| /// <version> $Id$ |
| /// </version> |
| [TestFixture] |
| public class TestOpenBitSet:LuceneTestCase |
| { |
| internal System.Random rand; |
| |
| internal virtual void DoGet(System.Collections.BitArray a, OpenBitSet b) |
| { |
| int max = a.Count; |
| for (int i = 0; i < max; i++) |
| { |
| Assert.AreEqual(a.Get(i) != b.Get(i), "mismatch: BitSet=[" + i + "]=" + a.Get(i)); |
| } |
| } |
| |
| internal virtual void DoNextSetBit(System.Collections.BitArray a, OpenBitSet b) |
| { |
| int aa = - 1, bb = - 1; |
| do |
| { |
| aa = BitSetSupport.NextSetBit(a, aa + 1); |
| bb = b.NextSetBit(bb + 1); |
| Assert.AreEqual(aa, bb); |
| } |
| while (aa >= 0); |
| } |
| |
| // test interleaving different OpenBitSetIterator.next()/skipTo() |
| internal virtual void DoIterate(System.Collections.BitArray a, OpenBitSet b, int mode) |
| { |
| if (mode == 1) |
| DoIterate1(a, b); |
| if (mode == 2) |
| DoIterate2(a, b); |
| } |
| |
| internal virtual void DoIterate1(System.Collections.BitArray a, OpenBitSet b) |
| { |
| int aa = - 1, bb = - 1; |
| OpenBitSetIterator iterator = new OpenBitSetIterator(b); |
| do |
| { |
| aa = BitSetSupport.NextSetBit(a, aa + 1); |
| bb = rand.NextDouble() > 0.5 ? iterator.NextDoc() : iterator.Advance(bb + 1); |
| Assert.AreEqual(aa == - 1?DocIdSetIterator.NO_MORE_DOCS:aa, bb); |
| } |
| while (aa >= 0); |
| } |
| |
| internal virtual void DoIterate2(System.Collections.BitArray a, OpenBitSet b) |
| { |
| int aa = - 1, bb = - 1; |
| OpenBitSetIterator iterator = new OpenBitSetIterator(b); |
| do |
| { |
| aa = BitSetSupport.NextSetBit(a, aa + 1); |
| bb = rand.NextDouble() > 0.5 ? 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) |
| { |
| System.Collections.BitArray a0 = null; |
| OpenBitSet b0 = null; |
| |
| for (int i = 0; i < iter; i++) |
| { |
| int sz = rand.Next(maxSize); |
| System.Collections.BitArray a = new System.Collections.BitArray(sz); |
| OpenBitSet b = new OpenBitSet(sz); |
| |
| // test the various ways of setting bits |
| if (sz > 0) |
| { |
| int nOper = rand.Next(sz); |
| for (int j = 0; j < nOper; j++) |
| { |
| int idx; |
| |
| idx = rand.Next(sz); |
| a.Set(idx, true); |
| b.FastSet(idx); |
| idx = rand.Next(sz); |
| a.Set(idx, false); |
| b.FastClear(idx); |
| idx = rand.Next(sz); |
| a.Set(idx, !a.Get(idx)); |
| b.FastFlip(idx); |
| |
| bool val = b.FlipAndGet(idx); |
| bool val2 = b.FlipAndGet(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); |
| |
| // {{dougsale-2.4.0}} |
| // |
| // Java's java.util.BitSet automatically grows as needed - i.e., when a bit is referenced beyond |
| // the size of the BitSet, an exception isn't thrown - rather, the set grows to the size of the |
| // referenced bit. |
| // |
| // System.Collections.BitArray does not have this feature, and thus I've faked it here by |
| // "growing" the array explicitly when necessary (creating a new instance of the appropriate size |
| // and setting the appropriate bits). |
| // |
| |
| // test ranges, including possible extension |
| int fromIndex, toIndex; |
| fromIndex = rand.Next(sz + 80); |
| toIndex = fromIndex + rand.Next((sz >> 1) + 1); |
| |
| // {{dougsale-2.4.0}}: |
| // The following commented-out, compound statement's 'for loop' implicitly grows the Java BitSets 'a' |
| // and 'aa' to the same cardinality as 'j+1' when 'a.Count < j+1' and 'fromIndex < toIndex': |
| //BitArray aa = (BitArray)a.Clone(); for (int j = fromIndex; j < toIndex; j++) aa.Set(j, !a.Get(j)); |
| // So, if necessary, lets explicitly grow 'a' now; then 'a' and its clone, 'aa', will be of the required size. |
| if (a.Count < toIndex && fromIndex < toIndex) |
| { |
| System.Collections.BitArray tmp = new System.Collections.BitArray(toIndex, false); |
| for (int k = 0; k < a.Count; k++) |
| tmp.Set(k, a.Get(k)); |
| a = tmp; |
| } |
| // {{dougsale-2.4.0}}: now we can invoke this statement without going 'out-of-bounds' |
| System.Collections.BitArray aa = (System.Collections.BitArray)a.Clone(); for (int j = fromIndex; j < toIndex; j++) aa.Set(j, !a.Get(j)); |
| OpenBitSet bb = (OpenBitSet)b.Clone(); bb.Flip(fromIndex, toIndex); |
| |
| DoIterate(aa, bb, mode); // a problem here is from flip or doIterate |
| |
| fromIndex = rand.Next(sz + 80); |
| toIndex = fromIndex + rand.Next((sz >> 1) + 1); |
| // {{dougsale-2.4.0}}: |
| // The following commented-out, compound statement's 'for loop' implicitly grows the Java BitSet 'aa' |
| // when 'a.Count < j+1' and 'fromIndex < toIndex' |
| //aa = (BitArray)a.Clone(); for (int j = fromIndex; j < toIndex; j++) aa.Set(j, false); |
| // So, if necessary, lets explicitly grow 'aa' now |
| if (a.Count < toIndex && fromIndex < toIndex) |
| { |
| aa = new System.Collections.BitArray(toIndex); |
| for (int k = 0; k < a.Count; k++) |
| aa.Set(k, a.Get(k)); |
| } |
| else |
| { |
| aa = (System.Collections.BitArray)a.Clone(); |
| } |
| for (int j = fromIndex; j < toIndex; j++) aa.Set(j, false); |
| bb = (OpenBitSet)b.Clone(); bb.Clear(fromIndex, toIndex); |
| |
| DoNextSetBit(aa, bb); // a problem here is from clear() or nextSetBit |
| |
| fromIndex = rand.Next(sz + 80); |
| toIndex = fromIndex + rand.Next((sz >> 1) + 1); |
| // {{dougsale-2.4.0}}: |
| // The following commented-out, compound statement's 'for loop' implicitly grows the Java BitSet 'aa' |
| // when 'a.Count < j+1' and 'fromIndex < toIndex' |
| //aa = (BitArray)a.Clone(); for (int j = fromIndex; j < toIndex; j++) aa.Set(j, false); |
| // So, if necessary, lets explicitly grow 'aa' now |
| if (a.Count < toIndex && fromIndex < toIndex) |
| { |
| aa = new System.Collections.BitArray(toIndex); |
| for (int k = 0; k < a.Count; k++) |
| aa.Set(k, a.Get(k)); |
| } |
| else |
| { |
| aa = (System.Collections.BitArray)a.Clone(); |
| } |
| for (int j = fromIndex; j < toIndex; j++) aa.Set(j, true); |
| bb = (OpenBitSet)b.Clone(); bb.Set(fromIndex, toIndex); |
| |
| DoNextSetBit(aa, bb); // a problem here is from set() or nextSetBit |
| |
| |
| if (a0 != null) |
| { |
| Assert.AreEqual(a.Equals(a0), b.Equals(b0)); |
| |
| Assert.AreEqual(BitSetSupport.Cardinality(a), b.Cardinality()); |
| |
| // {{dougsale-2.4.0}} |
| // |
| // The Java code used java.util.BitSet, which grows as needed. |
| // When a bit, outside the dimension of the set is referenced, |
| // the set automatically grows to the necessary size. The |
| // new entries default to false. |
| // |
| // BitArray does not grow automatically and is not growable. |
| // Thus when BitArray instances of mismatched cardinality |
| // interact, we must first explicitly "grow" the smaller one. |
| // |
| // This growth is acheived by creating a new instance of the |
| // required size and copying the appropriate values. |
| // |
| |
| //BitArray a_and = (BitArray)a.Clone(); a_and.And(a0); |
| //BitArray a_or = (BitArray)a.Clone(); a_or.Or(a0); |
| //BitArray a_xor = (BitArray)a.Clone(); a_xor.Xor(a0); |
| //BitArray a_andn = (BitArray)a.Clone(); for (int j = 0; j < a_andn.Count; j++) if (a0.Get(j)) a_andn.Set(j, false); |
| |
| System.Collections.BitArray a_and; |
| System.Collections.BitArray a_or; |
| System.Collections.BitArray a_xor; |
| System.Collections.BitArray a_andn; |
| |
| if (a.Count < a0.Count) |
| { |
| // the Java code would have implicitly resized 'a_and', 'a_or', 'a_xor', and 'a_andn' |
| // in this case, so we explicitly create a resized stand-in for 'a' here, allowing for |
| // a to keep its original size while 'a_and', 'a_or', 'a_xor', and 'a_andn' are resized |
| System.Collections.BitArray tmp = new System.Collections.BitArray(a0.Count, false); |
| for (int z = 0; z < a.Count; z++) |
| tmp.Set(z, a.Get(z)); |
| |
| a_and = (System.Collections.BitArray)tmp.Clone(); a_and.And(a0); |
| a_or = (System.Collections.BitArray)tmp.Clone(); a_or.Or(a0); |
| a_xor = (System.Collections.BitArray)tmp.Clone(); a_xor.Xor(a0); |
| a_andn = (System.Collections.BitArray)tmp.Clone(); for (int j = 0; j < a_andn.Count; j++) if (a0.Get(j)) a_andn.Set(j, false); |
| } |
| else if (a.Count > a0.Count) |
| { |
| // the Java code would have implicitly resized 'a0' in this case, so |
| // we explicitly do so here: |
| System.Collections.BitArray tmp = new System.Collections.BitArray(a.Count, false); |
| for (int z = 0; z < a0.Count; z++) |
| tmp.Set(z, a0.Get(z)); |
| a0 = tmp; |
| |
| a_and = (System.Collections.BitArray)a.Clone(); a_and.And(a0); |
| a_or = (System.Collections.BitArray)a.Clone(); a_or.Or(a0); |
| a_xor = (System.Collections.BitArray)a.Clone(); a_xor.Xor(a0); |
| a_andn = (System.Collections.BitArray)a.Clone(); for (int j = 0; j < a_andn.Count; j++) if (a0.Get(j)) a_andn.Set(j, false); |
| } |
| else |
| { |
| // 'a' and 'a0' are the same size, no explicit growing necessary |
| a_and = (System.Collections.BitArray)a.Clone(); a_and.And(a0); |
| a_or = (System.Collections.BitArray)a.Clone(); a_or.Or(a0); |
| a_xor = (System.Collections.BitArray)a.Clone(); a_xor.Xor(a0); |
| a_andn = (System.Collections.BitArray)a.Clone(); for (int j = 0; j < a_andn.Count; j++) if (a0.Get(j)) a_andn.Set(j, false); |
| } |
| |
| 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(BitSetSupport.Cardinality(a_and), b_and.Cardinality()); |
| Assert.AreEqual(BitSetSupport.Cardinality(a_or), b_or.Cardinality()); |
| Assert.AreEqual(BitSetSupport.Cardinality(a_xor), b_xor.Cardinality()); |
| Assert.AreEqual(BitSetSupport.Cardinality(a_andn), 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] |
| public virtual void TestSmall() |
| { |
| // TODO: fix for 64 bit tests. |
| if (IntPtr.Size == 4) |
| { |
| rand = NewRandom(); |
| DoRandomSets(1200, 1000, 1); |
| DoRandomSets(1200, 1000, 2); |
| } |
| } |
| |
| [Test] |
| public virtual void TestBig() |
| { |
| // uncomment to run a bigger test (~2 minutes). |
| // rand = newRandom(); |
| // doRandomSets(2000,200000, 1); |
| // doRandomSets(2000,200000, 2); |
| } |
| |
| [Test] |
| public virtual void TestEquals() |
| { |
| rand = NewRandom(); |
| 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 System.Object())); |
| } |
| |
| [Test] |
| public virtual void TestBitUtils() |
| { |
| rand = NewRandom(); |
| long num = 100000; |
| Assert.AreEqual(5, BitUtil.Ntz(num)); |
| Assert.AreEqual(5, BitUtil.Ntz2(num)); |
| Assert.AreEqual(5, BitUtil.Ntz3(num)); |
| |
| num = 10; |
| Assert.AreEqual(1, BitUtil.Ntz(num)); |
| Assert.AreEqual(1, BitUtil.Ntz2(num)); |
| Assert.AreEqual(1, BitUtil.Ntz3(num)); |
| |
| for (int i = 0; i < 64; i++) |
| { |
| num = 1L << i; |
| Assert.AreEqual(i, BitUtil.Ntz(num)); |
| Assert.AreEqual(i, BitUtil.Ntz2(num)); |
| Assert.AreEqual(i, BitUtil.Ntz3(num)); |
| } |
| } |
| |
| [Test] |
| public 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()); |
| } |
| } |
| |
| |
| } |
