--- /dev/null
+/**
+ * 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.
+ */
+
+package org.apache.lucene.util;
+
+import java.util.BitSet;
+
+import org.apache.lucene.search.DocIdSetIterator;
+
+public class TestOpenBitSet extends LuceneTestCase {
+
+ void doGet(BitSet a, OpenBitSet b) {
+ int max = a.size();
+ for (int i=0; i<max; i++) {
+ if (a.get(i) != b.get(i)) {
+ fail("mismatch: BitSet=["+i+"]="+a.get(i));
+ }
+ if (a.get(i) != b.get((long) i)) {
+ fail("mismatch: BitSet=["+i+"]="+a.get(i));
+ }
+ }
+ }
+
+ void doGetFast(BitSet a, OpenBitSet b, int max) {
+ for (int i=0; i<max; i++) {
+ if (a.get(i) != b.fastGet(i)) {
+ fail("mismatch: BitSet=["+i+"]="+a.get(i));
+ }
+ if (a.get(i) != b.fastGet((long) i)) {
+ fail("mismatch: BitSet=["+i+"]="+a.get(i));
+ }
+ }
+ }
+
+ void doNextSetBit(BitSet a, OpenBitSet b) {
+ int aa=-1,bb=-1;
+ do {
+ aa = a.nextSetBit(aa+1);
+ bb = b.nextSetBit(bb+1);
+ assertEquals(aa,bb);
+ } while (aa>=0);
+ }
+
+ void doNextSetBitLong(BitSet a, OpenBitSet b) {
+ int aa=-1,bb=-1;
+ do {
+ aa = a.nextSetBit(aa+1);
+ bb = (int) b.nextSetBit((long) (bb+1));
+ assertEquals(aa,bb);
+ } while (aa>=0);
+ }
+
+ void doPrevSetBit(BitSet a, OpenBitSet b) {
+ int aa = a.size() + random.nextInt(100);
+ int bb = aa;
+ do {
+ // aa = a.prevSetBit(aa-1);
+ aa--;
+ while ((aa >= 0) && (! a.get(aa))) {
+ aa--;
+ }
+ bb = b.prevSetBit(bb-1);
+ assertEquals(aa,bb);
+ } while (aa>=0);
+ }
+
+ void doPrevSetBitLong(BitSet a, OpenBitSet b) {
+ int aa = a.size() + random.nextInt(100);
+ int bb = aa;
+ do {
+ // aa = a.prevSetBit(aa-1);
+ aa--;
+ while ((aa >= 0) && (! a.get(aa))) {
+ aa--;
+ }
+ bb = (int) b.prevSetBit((long) (bb-1));
+ assertEquals(aa,bb);
+ } while (aa>=0);
+ }
+
+ // test interleaving different OpenBitSetIterator.next()/skipTo()
+ void doIterate(BitSet a, OpenBitSet b, int mode) {
+ if (mode==1) doIterate1(a, b);
+ if (mode==2) doIterate2(a, b);
+ }
+
+ void doIterate1(BitSet 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);
+ assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
+ } while (aa>=0);
+ }
+
+ void doIterate2(BitSet 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);
+ assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
+ } while (aa>=0);
+ }
+
+ void doRandomSets(int maxSize, int iter, int mode) {
+ BitSet a0=null;
+ OpenBitSet b0=null;
+
+ for (int i=0; i<iter; i++) {
+ int sz = random.nextInt(maxSize);
+ BitSet a = new BitSet(sz);
+ OpenBitSet b = new OpenBitSet(sz);
+
+ // test the various ways of setting bits
+ if (sz>0) {
+ int nOper = random.nextInt(sz);
+ for (int j=0; j<nOper; j++) {
+ int idx;
+
+ idx = random.nextInt(sz);
+ a.set(idx);
+ b.fastSet(idx);
+
+ idx = random.nextInt(sz);
+ a.set(idx);
+ b.fastSet((long) idx);
+
+ idx = random.nextInt(sz);
+ a.clear(idx);
+ b.fastClear(idx);
+
+ idx = random.nextInt(sz);
+ a.clear(idx);
+ b.fastClear((long) idx);
+
+ idx = random.nextInt(sz);
+ a.flip(idx);
+ b.fastFlip(idx);
+
+ boolean val = b.flipAndGet(idx);
+ boolean val2 = b.flipAndGet(idx);
+ assertTrue(val != val2);
+
+ idx = random.nextInt(sz);
+ a.flip(idx);
+ b.fastFlip((long) idx);
+
+ val = b.flipAndGet((long) idx);
+ val2 = b.flipAndGet((long) idx);
+ assertTrue(val != val2);
+
+ val = b.getAndSet(idx);
+ assertTrue(val2 == val);
+ assertTrue(b.get(idx));
+
+ if (!val) b.fastClear(idx);
+ assertTrue(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.nextInt(sz+80);
+ toIndex = fromIndex + random.nextInt((sz>>1)+1);
+ BitSet aa = (BitSet)a.clone(); 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.nextInt(sz+80);
+ toIndex = fromIndex + random.nextInt((sz>>1)+1);
+ aa = (BitSet)a.clone(); 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.nextInt(sz+80);
+ toIndex = fromIndex + random.nextInt((sz>>1)+1);
+ aa = (BitSet)a.clone(); 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) {
+ assertEquals( a.equals(a0), b.equals(b0));
+
+ assertEquals(a.cardinality(), b.cardinality());
+
+ BitSet a_and = (BitSet)a.clone(); a_and.and(a0);
+ BitSet a_or = (BitSet)a.clone(); a_or.or(a0);
+ BitSet a_xor = (BitSet)a.clone(); a_xor.xor(a0);
+ BitSet a_andn = (BitSet)a.clone(); a_andn.andNot(a0);
+
+ OpenBitSet b_and = (OpenBitSet)b.clone(); assertEquals(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);
+
+ assertEquals(a_and.cardinality(), b_and.cardinality());
+ assertEquals(a_or.cardinality(), b_or.cardinality());
+ assertEquals(a_xor.cardinality(), b_xor.cardinality());
+ assertEquals(a_andn.cardinality(), b_andn.cardinality());
+
+ // test non-mutating popcounts
+ assertEquals(b_and.cardinality(), OpenBitSet.intersectionCount(b,b0));
+ assertEquals(b_or.cardinality(), OpenBitSet.unionCount(b,b0));
+ assertEquals(b_xor.cardinality(), OpenBitSet.xorCount(b,b0));
+ assertEquals(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.
+ public void testSmall() {
+ doRandomSets(atLeast(1200), atLeast(1000), 1);
+ doRandomSets(atLeast(1200), atLeast(1000), 2);
+ }
+
+ // uncomment to run a bigger test (~2 minutes).
+ /*
+ public void testBig() {
+ doRandomSets(2000,200000, 1);
+ doRandomSets(2000,200000, 2);
+ }
+ */
+
+ public void testEquals() {
+ OpenBitSet b1 = new OpenBitSet(1111);
+ OpenBitSet b2 = new OpenBitSet(2222);
+ assertTrue(b1.equals(b2));
+ assertTrue(b2.equals(b1));
+ b1.set(10);
+ assertFalse(b1.equals(b2));
+ assertFalse(b2.equals(b1));
+ b2.set(10);
+ assertTrue(b1.equals(b2));
+ assertTrue(b2.equals(b1));
+ b2.set(2221);
+ assertFalse(b1.equals(b2));
+ assertFalse(b2.equals(b1));
+ b1.set(2221);
+ assertTrue(b1.equals(b2));
+ assertTrue(b2.equals(b1));
+
+ // try different type of object
+ assertFalse(b1.equals(new Object()));
+ }
+
+ public void testHashCodeEquals() {
+ OpenBitSet bs1 = new OpenBitSet(200);
+ OpenBitSet bs2 = new OpenBitSet(64);
+ bs1.set(3);
+ bs2.set(3);
+ assertEquals(bs1, bs2);
+ assertEquals(bs1.hashCode(), bs2.hashCode());
+ }
+
+
+ private OpenBitSet makeOpenBitSet(int[] a) {
+ OpenBitSet bs = new OpenBitSet();
+ for (int e: a) {
+ bs.set(e);
+ }
+ return bs;
+ }
+
+ private BitSet makeBitSet(int[] a) {
+ BitSet bs = new BitSet();
+ for (int e: a) {
+ bs.set(e);
+ }
+ return bs;
+ }
+
+ private void checkPrevSetBitArray(int [] a) {
+ OpenBitSet obs = makeOpenBitSet(a);
+ BitSet bs = makeBitSet(a);
+ doPrevSetBit(bs, obs);
+ }
+
+ public void testPrevSetBit() {
+ checkPrevSetBitArray(new int[] {});
+ checkPrevSetBitArray(new int[] {0});
+ checkPrevSetBitArray(new int[] {0,2});
+ }
+}
+
+
+
fnp / pylucene.git / blobdiff