X-Git-Url: https://git.mdrn.pl/pylucene.git/blobdiff_plain/a2e61f0c04805cfcb8706176758d1283c7e3a55c..aaeed5504b982cf3545252ab528713250aa33eed:/lucene-java-3.5.0/lucene/backwards/src/test/org/apache/lucene/util/TestFixedBitSet.java

diff --git a/lucene-java-3.5.0/lucene/backwards/src/test/org/apache/lucene/util/TestFixedBitSet.java b/lucene-java-3.5.0/lucene/backwards/src/test/org/apache/lucene/util/TestFixedBitSet.java
new file mode 100644
index 0000000..b4e575e
--- /dev/null
+++ b/lucene-java-3.5.0/lucene/backwards/src/test/org/apache/lucene/util/TestFixedBitSet.java
@@ -0,0 +1,289 @@
+/**
+ * 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.io.IOException;
+import java.util.BitSet;
+
+import org.apache.lucene.search.DocIdSetIterator;
+
+public class TestFixedBitSet extends LuceneTestCase {
+
+  void doGet(BitSet a, FixedBitSet b) {
+    int max = b.length();
+    for (int i=0; i<max; i++) {
+      if (a.get(i) != b.get(i)) {
+        fail("mismatch: BitSet=["+i+"]="+a.get(i));
+      }
+    }
+  }
+
+  void doNextSetBit(BitSet a, FixedBitSet b) {
+    int aa=-1,bb=-1;
+    do {
+      aa = a.nextSetBit(aa+1);
+      bb = bb < b.length()-1 ? b.nextSetBit(bb+1) : -1;
+      assertEquals(aa,bb);
+    } while (aa>=0);
+  }
+
+  void doPrevSetBit(BitSet a, FixedBitSet 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--;
+      }
+      if (b.length() == 0) {
+        bb = -1;
+      } else if (bb > b.length()-1) {
+        bb = b.prevSetBit(b.length()-1);
+      } else if (bb < 1) {
+        bb = -1;
+      } else {
+        bb = bb >= 1 ? b.prevSetBit(bb-1) : -1;
+      }
+      assertEquals(aa,bb);
+    } while (aa>=0);
+  }
+
+  // test interleaving different FixedBitSetIterator.next()/skipTo()
+  void doIterate(BitSet a, FixedBitSet b, int mode) throws IOException {
+    if (mode==1) doIterate1(a, b);
+    if (mode==2) doIterate2(a, b);
+  }
+
+  void doIterate1(BitSet a, FixedBitSet b) throws IOException {
+    int aa=-1,bb=-1;
+    DocIdSetIterator iterator = b.iterator();
+    do {
+      aa = a.nextSetBit(aa+1);
+      bb = (bb < b.length() && random.nextBoolean()) ? iterator.nextDoc() : iterator.advance(bb + 1);
+      assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
+    } while (aa>=0);
+  }
+
+  void doIterate2(BitSet a, FixedBitSet b) throws IOException {
+    int aa=-1,bb=-1;
+    DocIdSetIterator iterator = b.iterator();
+    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) throws IOException {
+    BitSet a0=null;
+    FixedBitSet b0=null;
+
+    for (int i=0; i<iter; i++) {
+      int sz = _TestUtil.nextInt(random, 2, maxSize);
+      BitSet a = new BitSet(sz);
+      FixedBitSet b = new FixedBitSet(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.set(idx);
+          
+          idx = random.nextInt(sz);
+          a.clear(idx);
+          b.clear(idx);
+          
+          idx = random.nextInt(sz);
+          a.flip(idx);
+          b.flip(idx, idx+1);
+
+          idx = random.nextInt(sz);
+          a.flip(idx);
+          b.flip(idx, idx+1);
+
+          boolean val2 = b.get(idx);
+          boolean val = b.getAndSet(idx);
+          assertTrue(val2 == val);
+          assertTrue(b.get(idx));
+          
+          if (!val) b.clear(idx);
+          assertTrue(b.get(idx) == val);
+        }
+      }
+
+      // test that the various ways of accessing the bits are equivalent
+      doGet(a,b);
+
+      // test ranges, including possible extension
+      int fromIndex, toIndex;
+      fromIndex = random.nextInt(sz/2);
+      toIndex = fromIndex + random.nextInt(sz - fromIndex);
+      BitSet aa = (BitSet)a.clone(); aa.flip(fromIndex,toIndex);
+      FixedBitSet bb = (FixedBitSet)b.clone(); bb.flip(fromIndex,toIndex);
+
+      doIterate(aa,bb, mode);   // a problem here is from flip or doIterate
+
+      fromIndex = random.nextInt(sz/2);
+      toIndex = fromIndex + random.nextInt(sz - fromIndex);
+      aa = (BitSet)a.clone(); aa.clear(fromIndex,toIndex);
+      bb = (FixedBitSet)b.clone(); bb.clear(fromIndex,toIndex);
+
+      doNextSetBit(aa,bb); // a problem here is from clear() or nextSetBit
+      
+      doPrevSetBit(aa,bb);
+
+      fromIndex = random.nextInt(sz/2);
+      toIndex = fromIndex + random.nextInt(sz - fromIndex);
+      aa = (BitSet)a.clone(); aa.set(fromIndex,toIndex);
+      bb = (FixedBitSet)b.clone(); bb.set(fromIndex,toIndex);
+
+      doNextSetBit(aa,bb); // a problem here is from set() or nextSetBit
+    
+      doPrevSetBit(aa,bb);
+
+      if (b0 != null && b0.length() <= b.length()) {
+        assertEquals(a.cardinality(), b.cardinality());
+
+        BitSet a_or = (BitSet) a.clone();
+        a_or.or(a0);
+
+        FixedBitSet b_or = (FixedBitSet) b.clone();
+        b_or.or(b0);
+
+        assertEquals(a0.cardinality(), b0.cardinality());
+        assertEquals(a_or.cardinality(), b_or.cardinality());
+
+        doIterate(a_or, b_or, mode);
+      }
+
+      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() throws IOException {
+    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() {
+    // This test can't handle numBits==0:
+    final int numBits = random.nextInt(2000) + 1;
+    FixedBitSet b1 = new FixedBitSet(numBits);
+    FixedBitSet b2 = new FixedBitSet(numBits);
+    assertTrue(b1.equals(b2));
+    assertTrue(b2.equals(b1));
+    for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
+      int idx = random.nextInt(numBits);
+      if (!b1.get(idx)) {
+        b1.set(idx);
+        assertFalse(b1.equals(b2));
+        assertFalse(b2.equals(b1));
+        b2.set(idx);
+        assertTrue(b1.equals(b2));
+        assertTrue(b2.equals(b1));
+      }
+    }
+
+    // try different type of object
+    assertFalse(b1.equals(new Object()));
+  }
+  
+  public void testHashCodeEquals() {
+    // This test can't handle numBits==0:
+    final int numBits = random.nextInt(2000) + 1;
+    FixedBitSet b1 = new FixedBitSet(numBits);
+    FixedBitSet b2 = new FixedBitSet(numBits);
+    assertTrue(b1.equals(b2));
+    assertTrue(b2.equals(b1));
+    for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
+      int idx = random.nextInt(numBits);
+      if (!b1.get(idx)) {
+        b1.set(idx);
+        assertFalse(b1.equals(b2));
+        assertFalse(b1.hashCode() == b2.hashCode());
+        b2.set(idx);
+        assertEquals(b1, b2);
+        assertEquals(b1.hashCode(), b2.hashCode());
+      }
+    }
+  } 
+
+  public void testSmallBitSets() {
+    // Make sure size 0-10 bit sets are OK:
+    for(int numBits=0;numBits<10;numBits++) {
+      FixedBitSet b1 = new FixedBitSet(numBits);
+      FixedBitSet b2 = new FixedBitSet(numBits);
+      assertTrue(b1.equals(b2));
+      assertEquals(b1.hashCode(), b2.hashCode());
+      assertEquals(0, b1.cardinality());
+      if (numBits > 0) {
+        b1.set(0, numBits);
+        assertEquals(numBits, b1.cardinality());
+        b1.flip(0, numBits);
+        assertEquals(0, b1.cardinality());
+      }
+    }
+  }
+  
+  private FixedBitSet makeFixedBitSet(int[] a, int numBits) {
+    FixedBitSet bs = new FixedBitSet(numBits);
+    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, int numBits) {
+    FixedBitSet obs = makeFixedBitSet(a, numBits);
+    BitSet bs = makeBitSet(a);
+    doPrevSetBit(bs, obs);
+  }
+
+  public void testPrevSetBit() {
+    checkPrevSetBitArray(new int[] {}, 0);
+    checkPrevSetBitArray(new int[] {0}, 1);
+    checkPrevSetBitArray(new int[] {0,2}, 3);
+  }
+}
+
+
+