lucene-java-3.5.0/lucene/src/test/org/apache/lucene/util/TestFixedBitSet.java

   1 /**
   2  * Licensed to the Apache Software Foundation (ASF) under one or more
   3  * contributor license agreements.  See the NOTICE file distributed with
   4  * this work for additional information regarding copyright ownership.
   5  * The ASF licenses this file to You under the Apache License, Version 2.0
   6  * (the "License"); you may not use this file except in compliance with
   7  * the License.  You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 package org.apache.lucene.util;
  19
  20 import java.io.IOException;
  21 import java.util.BitSet;
  22
  23 import org.apache.lucene.search.DocIdSetIterator;
  24
  25 public class TestFixedBitSet extends LuceneTestCase {
  26
  27   void doGet(BitSet a, FixedBitSet b) {
  28     int max = b.length();
  29     for (int i=0; i<max; i++) {
  30       if (a.get(i) != b.get(i)) {
  31         fail("mismatch: BitSet=["+i+"]="+a.get(i));
  32       }
  33     }
  34   }
  35
  36   void doNextSetBit(BitSet a, FixedBitSet b) {
  37     int aa=-1,bb=-1;
  38     do {
  39       aa = a.nextSetBit(aa+1);
  40       bb = bb < b.length()-1 ? b.nextSetBit(bb+1) : -1;
  41       assertEquals(aa,bb);
  42     } while (aa>=0);
  43   }
  44
  45   void doPrevSetBit(BitSet a, FixedBitSet b) {
  46     int aa = a.size() + random.nextInt(100);
  47     int bb = aa;
  48     do {
  49       // aa = a.prevSetBit(aa-1);
  50       aa--;
  51       while ((aa >= 0) && (! a.get(aa))) {
  52         aa--;
  53       }
  54       if (b.length() == 0) {
  55         bb = -1;
  56       } else if (bb > b.length()-1) {
  57         bb = b.prevSetBit(b.length()-1);
  58       } else if (bb < 1) {
  59         bb = -1;
  60       } else {
  61         bb = bb >= 1 ? b.prevSetBit(bb-1) : -1;
  62       }
  63       assertEquals(aa,bb);
  64     } while (aa>=0);
  65   }
  66
  67   // test interleaving different FixedBitSetIterator.next()/skipTo()
  68   void doIterate(BitSet a, FixedBitSet b, int mode) throws IOException {
  69     if (mode==1) doIterate1(a, b);
  70     if (mode==2) doIterate2(a, b);
  71   }
  72
  73   void doIterate1(BitSet a, FixedBitSet b) throws IOException {
  74     int aa=-1,bb=-1;
  75     DocIdSetIterator iterator = b.iterator();
  76     do {
  77       aa = a.nextSetBit(aa+1);
  78       bb = (bb < b.length() && random.nextBoolean()) ? iterator.nextDoc() : iterator.advance(bb + 1);
  79       assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
  80     } while (aa>=0);
  81   }
  82
  83   void doIterate2(BitSet a, FixedBitSet b) throws IOException {
  84     int aa=-1,bb=-1;
  85     DocIdSetIterator iterator = b.iterator();
  86     do {
  87       aa = a.nextSetBit(aa+1);
  88       bb = random.nextBoolean() ? iterator.nextDoc() : iterator.advance(bb + 1);
  89       assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
  90     } while (aa>=0);
  91   }
  92
  93   void doRandomSets(int maxSize, int iter, int mode) throws IOException {
  94     BitSet a0=null;
  95     FixedBitSet b0=null;
  96
  97     for (int i=0; i<iter; i++) {
  98       int sz = _TestUtil.nextInt(random, 2, maxSize);
  99       BitSet a = new BitSet(sz);
 100       FixedBitSet b = new FixedBitSet(sz);
 101
 102       // test the various ways of setting bits
 103       if (sz>0) {
 104         int nOper = random.nextInt(sz);
 105         for (int j=0; j<nOper; j++) {
 106           int idx;
 107
 108           idx = random.nextInt(sz);
 109           a.set(idx);
 110           b.set(idx);
 111
 112           idx = random.nextInt(sz);
 113           a.clear(idx);
 114           b.clear(idx);
 115
 116           idx = random.nextInt(sz);
 117           a.flip(idx);
 118           b.flip(idx, idx+1);
 119
 120           idx = random.nextInt(sz);
 121           a.flip(idx);
 122           b.flip(idx, idx+1);
 123
 124           boolean val2 = b.get(idx);
 125           boolean val = b.getAndSet(idx);
 126           assertTrue(val2 == val);
 127           assertTrue(b.get(idx));
 128
 129           if (!val) b.clear(idx);
 130           assertTrue(b.get(idx) == val);
 131         }
 132       }
 133
 134       // test that the various ways of accessing the bits are equivalent
 135       doGet(a,b);
 136
 137       // test ranges, including possible extension
 138       int fromIndex, toIndex;
 139       fromIndex = random.nextInt(sz/2);
 140       toIndex = fromIndex + random.nextInt(sz - fromIndex);
 141       BitSet aa = (BitSet)a.clone(); aa.flip(fromIndex,toIndex);
 142       FixedBitSet bb = (FixedBitSet)b.clone(); bb.flip(fromIndex,toIndex);
 143
 144       doIterate(aa,bb, mode);   // a problem here is from flip or doIterate
 145
 146       fromIndex = random.nextInt(sz/2);
 147       toIndex = fromIndex + random.nextInt(sz - fromIndex);
 148       aa = (BitSet)a.clone(); aa.clear(fromIndex,toIndex);
 149       bb = (FixedBitSet)b.clone(); bb.clear(fromIndex,toIndex);
 150
 151       doNextSetBit(aa,bb); // a problem here is from clear() or nextSetBit
 152
 153       doPrevSetBit(aa,bb);
 154
 155       fromIndex = random.nextInt(sz/2);
 156       toIndex = fromIndex + random.nextInt(sz - fromIndex);
 157       aa = (BitSet)a.clone(); aa.set(fromIndex,toIndex);
 158       bb = (FixedBitSet)b.clone(); bb.set(fromIndex,toIndex);
 159
 160       doNextSetBit(aa,bb); // a problem here is from set() or nextSetBit
 161
 162       doPrevSetBit(aa,bb);
 163
 164       if (b0 != null && b0.length() <= b.length()) {
 165         assertEquals(a.cardinality(), b.cardinality());
 166
 167         BitSet a_and = (BitSet)a.clone(); a_and.and(a0);
 168         BitSet a_or = (BitSet)a.clone(); a_or.or(a0);
 169         BitSet a_andn = (BitSet)a.clone(); a_andn.andNot(a0);
 170
 171         FixedBitSet b_and = (FixedBitSet)b.clone(); assertEquals(b,b_and); b_and.and(b0);
 172         FixedBitSet b_or = (FixedBitSet)b.clone(); b_or.or(b0);
 173         FixedBitSet b_andn = (FixedBitSet)b.clone(); b_andn.andNot(b0);
 174
 175         assertEquals(a0.cardinality(), b0.cardinality());
 176         assertEquals(a_or.cardinality(), b_or.cardinality());
 177
 178         doIterate(a_and,b_and, mode);
 179         doIterate(a_or,b_or, mode);
 180         doIterate(a_andn,b_andn, mode);
 181
 182         assertEquals(a_and.cardinality(), b_and.cardinality());
 183         assertEquals(a_or.cardinality(), b_or.cardinality());
 184         assertEquals(a_andn.cardinality(), b_andn.cardinality());
 185       }
 186
 187       a0=a;
 188       b0=b;
 189     }
 190   }
 191
 192   // large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
 193   // larger testsuite.
 194   public void testSmall() throws IOException {
 195     doRandomSets(atLeast(1200), atLeast(1000), 1);
 196     doRandomSets(atLeast(1200), atLeast(1000), 2);
 197   }
 198
 199   // uncomment to run a bigger test (~2 minutes).
 200   /*
 201   public void testBig() {
 202     doRandomSets(2000,200000, 1);
 203     doRandomSets(2000,200000, 2);
 204   }
 205   */
 206
 207   public void testEquals() {
 208     // This test can't handle numBits==0:
 209     final int numBits = random.nextInt(2000) + 1;
 210     FixedBitSet b1 = new FixedBitSet(numBits);
 211     FixedBitSet b2 = new FixedBitSet(numBits);
 212     assertTrue(b1.equals(b2));
 213     assertTrue(b2.equals(b1));
 214     for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
 215       int idx = random.nextInt(numBits);
 216       if (!b1.get(idx)) {
 217         b1.set(idx);
 218         assertFalse(b1.equals(b2));
 219         assertFalse(b2.equals(b1));
 220         b2.set(idx);
 221         assertTrue(b1.equals(b2));
 222         assertTrue(b2.equals(b1));
 223       }
 224     }
 225
 226     // try different type of object
 227     assertFalse(b1.equals(new Object()));
 228   }
 229
 230   public void testHashCodeEquals() {
 231     // This test can't handle numBits==0:
 232     final int numBits = random.nextInt(2000) + 1;
 233     FixedBitSet b1 = new FixedBitSet(numBits);
 234     FixedBitSet b2 = new FixedBitSet(numBits);
 235     assertTrue(b1.equals(b2));
 236     assertTrue(b2.equals(b1));
 237     for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
 238       int idx = random.nextInt(numBits);
 239       if (!b1.get(idx)) {
 240         b1.set(idx);
 241         assertFalse(b1.equals(b2));
 242         assertFalse(b1.hashCode() == b2.hashCode());
 243         b2.set(idx);
 244         assertEquals(b1, b2);
 245         assertEquals(b1.hashCode(), b2.hashCode());
 246       }
 247     }
 248   }
 249
 250   public void testSmallBitSets() {
 251     // Make sure size 0-10 bit sets are OK:
 252     for(int numBits=0;numBits<10;numBits++) {
 253       FixedBitSet b1 = new FixedBitSet(numBits);
 254       FixedBitSet b2 = new FixedBitSet(numBits);
 255       assertTrue(b1.equals(b2));
 256       assertEquals(b1.hashCode(), b2.hashCode());
 257       assertEquals(0, b1.cardinality());
 258       if (numBits > 0) {
 259         b1.set(0, numBits);
 260         assertEquals(numBits, b1.cardinality());
 261         b1.flip(0, numBits);
 262         assertEquals(0, b1.cardinality());
 263       }
 264     }
 265   }
 266
 267   private FixedBitSet makeFixedBitSet(int[] a, int numBits) {
 268     FixedBitSet bs = new FixedBitSet(numBits);
 269     for (int e: a) {
 270       bs.set(e);
 271     }
 272     return bs;
 273   }
 274
 275   private BitSet makeBitSet(int[] a) {
 276     BitSet bs = new BitSet();
 277     for (int e: a) {
 278       bs.set(e);
 279     }
 280     return bs;
 281   }
 282
 283   private void checkPrevSetBitArray(int [] a, int numBits) {
 284     FixedBitSet obs = makeFixedBitSet(a, numBits);
 285     BitSet bs = makeBitSet(a);
 286     doPrevSetBit(bs, obs);
 287   }
 288
 289   public void testPrevSetBit() {
 290     checkPrevSetBitArray(new int[] {}, 0);
 291     checkPrevSetBitArray(new int[] {0}, 1);
 292     checkPrevSetBitArray(new int[] {0,2}, 3);
 293   }
 294 }
 295
 296
 297