lucene-java-3.5.0/lucene/src/test/org/apache/lucene/util/TestOpenBitSet.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.util.BitSet;
  21
  22 import org.apache.lucene.search.DocIdSetIterator;
  23
  24 public class TestOpenBitSet extends LuceneTestCase {
  25
  26   void doGet(BitSet a, OpenBitSet b) {
  27     int max = a.size();
  28     for (int i=0; i<max; i++) {
  29       if (a.get(i) != b.get(i)) {
  30         fail("mismatch: BitSet=["+i+"]="+a.get(i));
  31       }
  32       if (a.get(i) != b.get((long) i)) {
  33         fail("mismatch: BitSet=["+i+"]="+a.get(i));
  34       }
  35     }
  36   }
  37
  38   void doGetFast(BitSet a, OpenBitSet b, int max) {
  39     for (int i=0; i<max; i++) {
  40       if (a.get(i) != b.fastGet(i)) {
  41         fail("mismatch: BitSet=["+i+"]="+a.get(i));
  42       }
  43       if (a.get(i) != b.fastGet((long) i)) {
  44         fail("mismatch: BitSet=["+i+"]="+a.get(i));
  45       }
  46     }
  47   }
  48
  49   void doNextSetBit(BitSet a, OpenBitSet b) {
  50     int aa=-1,bb=-1;
  51     do {
  52       aa = a.nextSetBit(aa+1);
  53       bb = b.nextSetBit(bb+1);
  54       assertEquals(aa,bb);
  55     } while (aa>=0);
  56   }
  57
  58   void doNextSetBitLong(BitSet a, OpenBitSet b) {
  59     int aa=-1,bb=-1;
  60     do {
  61       aa = a.nextSetBit(aa+1);
  62       bb = (int) b.nextSetBit((long) (bb+1));
  63       assertEquals(aa,bb);
  64     } while (aa>=0);
  65   }
  66
  67   void doPrevSetBit(BitSet a, OpenBitSet b) {
  68     int aa = a.size() + random.nextInt(100);
  69     int bb = aa;
  70     do {
  71       // aa = a.prevSetBit(aa-1);
  72       aa--;
  73       while ((aa >= 0) && (! a.get(aa))) {
  74         aa--;
  75       }
  76       bb = b.prevSetBit(bb-1);
  77       assertEquals(aa,bb);
  78     } while (aa>=0);
  79   }
  80
  81   void doPrevSetBitLong(BitSet a, OpenBitSet b) {
  82     int aa = a.size() + random.nextInt(100);
  83     int bb = aa;
  84     do {
  85       // aa = a.prevSetBit(aa-1);
  86       aa--;
  87       while ((aa >= 0) && (! a.get(aa))) {
  88         aa--;
  89       }
  90       bb = (int) b.prevSetBit((long) (bb-1));
  91       assertEquals(aa,bb);
  92     } while (aa>=0);
  93   }
  94
  95   // test interleaving different OpenBitSetIterator.next()/skipTo()
  96   void doIterate(BitSet a, OpenBitSet b, int mode) {
  97     if (mode==1) doIterate1(a, b);
  98     if (mode==2) doIterate2(a, b);
  99   }
 100
 101   void doIterate1(BitSet a, OpenBitSet b) {
 102     int aa=-1,bb=-1;
 103     OpenBitSetIterator iterator = new OpenBitSetIterator(b);
 104     do {
 105       aa = a.nextSetBit(aa+1);
 106       bb = random.nextBoolean() ? iterator.nextDoc() : iterator.advance(bb + 1);
 107       assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
 108     } while (aa>=0);
 109   }
 110
 111   void doIterate2(BitSet a, OpenBitSet b) {
 112     int aa=-1,bb=-1;
 113     OpenBitSetIterator iterator = new OpenBitSetIterator(b);
 114     do {
 115       aa = a.nextSetBit(aa+1);
 116       bb = random.nextBoolean() ? iterator.nextDoc() : iterator.advance(bb + 1);
 117       assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
 118     } while (aa>=0);
 119   }
 120
 121   void doRandomSets(int maxSize, int iter, int mode) {
 122     BitSet a0=null;
 123     OpenBitSet b0=null;
 124
 125     for (int i=0; i<iter; i++) {
 126       int sz = random.nextInt(maxSize);
 127       BitSet a = new BitSet(sz);
 128       OpenBitSet b = new OpenBitSet(sz);
 129
 130       // test the various ways of setting bits
 131       if (sz>0) {
 132         int nOper = random.nextInt(sz);
 133         for (int j=0; j<nOper; j++) {
 134           int idx;
 135
 136           idx = random.nextInt(sz);
 137           a.set(idx);
 138           b.fastSet(idx);
 139
 140           idx = random.nextInt(sz);
 141           a.set(idx);
 142           b.fastSet((long) idx);
 143
 144           idx = random.nextInt(sz);
 145           a.clear(idx);
 146           b.fastClear(idx);
 147
 148           idx = random.nextInt(sz);
 149           a.clear(idx);
 150           b.fastClear((long) idx);
 151
 152           idx = random.nextInt(sz);
 153           a.flip(idx);
 154           b.fastFlip(idx);
 155
 156           boolean val = b.flipAndGet(idx);
 157           boolean val2 = b.flipAndGet(idx);
 158           assertTrue(val != val2);
 159
 160           idx = random.nextInt(sz);
 161           a.flip(idx);
 162           b.fastFlip((long) idx);
 163
 164           val = b.flipAndGet((long) idx);
 165           val2 = b.flipAndGet((long) idx);
 166           assertTrue(val != val2);
 167
 168           val = b.getAndSet(idx);
 169           assertTrue(val2 == val);
 170           assertTrue(b.get(idx));
 171
 172           if (!val) b.fastClear(idx);
 173           assertTrue(b.get(idx) == val);
 174         }
 175       }
 176
 177       // test that the various ways of accessing the bits are equivalent
 178       doGet(a,b);
 179       doGetFast(a, b, sz);
 180
 181       // test ranges, including possible extension
 182       int fromIndex, toIndex;
 183       fromIndex = random.nextInt(sz+80);
 184       toIndex = fromIndex + random.nextInt((sz>>1)+1);
 185       BitSet aa = (BitSet)a.clone(); aa.flip(fromIndex,toIndex);
 186       OpenBitSet bb = (OpenBitSet)b.clone(); bb.flip(fromIndex,toIndex);
 187
 188       doIterate(aa,bb, mode);   // a problem here is from flip or doIterate
 189
 190       fromIndex = random.nextInt(sz+80);
 191       toIndex = fromIndex + random.nextInt((sz>>1)+1);
 192       aa = (BitSet)a.clone(); aa.clear(fromIndex,toIndex);
 193       bb = (OpenBitSet)b.clone(); bb.clear(fromIndex,toIndex);
 194
 195       doNextSetBit(aa,bb); // a problem here is from clear() or nextSetBit
 196       doNextSetBitLong(aa,bb);
 197
 198       doPrevSetBit(aa,bb);
 199       doPrevSetBitLong(aa,bb);
 200
 201       fromIndex = random.nextInt(sz+80);
 202       toIndex = fromIndex + random.nextInt((sz>>1)+1);
 203       aa = (BitSet)a.clone(); aa.set(fromIndex,toIndex);
 204       bb = (OpenBitSet)b.clone(); bb.set(fromIndex,toIndex);
 205
 206       doNextSetBit(aa,bb); // a problem here is from set() or nextSetBit
 207       doNextSetBitLong(aa,bb);
 208
 209       doPrevSetBit(aa,bb);
 210       doPrevSetBitLong(aa,bb);
 211
 212       if (a0 != null) {
 213         assertEquals( a.equals(a0), b.equals(b0));
 214
 215         assertEquals(a.cardinality(), b.cardinality());
 216
 217         BitSet a_and = (BitSet)a.clone(); a_and.and(a0);
 218         BitSet a_or = (BitSet)a.clone(); a_or.or(a0);
 219         BitSet a_xor = (BitSet)a.clone(); a_xor.xor(a0);
 220         BitSet a_andn = (BitSet)a.clone(); a_andn.andNot(a0);
 221
 222         OpenBitSet b_and = (OpenBitSet)b.clone(); assertEquals(b,b_and); b_and.and(b0);
 223         OpenBitSet b_or = (OpenBitSet)b.clone(); b_or.or(b0);
 224         OpenBitSet b_xor = (OpenBitSet)b.clone(); b_xor.xor(b0);
 225         OpenBitSet b_andn = (OpenBitSet)b.clone(); b_andn.andNot(b0);
 226
 227         doIterate(a_and,b_and, mode);
 228         doIterate(a_or,b_or, mode);
 229         doIterate(a_xor,b_xor, mode);
 230         doIterate(a_andn,b_andn, mode);
 231
 232         assertEquals(a_and.cardinality(), b_and.cardinality());
 233         assertEquals(a_or.cardinality(), b_or.cardinality());
 234         assertEquals(a_xor.cardinality(), b_xor.cardinality());
 235         assertEquals(a_andn.cardinality(), b_andn.cardinality());
 236
 237         // test non-mutating popcounts
 238         assertEquals(b_and.cardinality(), OpenBitSet.intersectionCount(b,b0));
 239         assertEquals(b_or.cardinality(), OpenBitSet.unionCount(b,b0));
 240         assertEquals(b_xor.cardinality(), OpenBitSet.xorCount(b,b0));
 241         assertEquals(b_andn.cardinality(), OpenBitSet.andNotCount(b,b0));
 242       }
 243
 244       a0=a;
 245       b0=b;
 246     }
 247   }
 248
 249   // large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
 250   // larger testsuite.
 251   public void testSmall() {
 252     doRandomSets(atLeast(1200), atLeast(1000), 1);
 253     doRandomSets(atLeast(1200), atLeast(1000), 2);
 254   }
 255
 256   // uncomment to run a bigger test (~2 minutes).
 257   /*
 258   public void testBig() {
 259     doRandomSets(2000,200000, 1);
 260     doRandomSets(2000,200000, 2);
 261   }
 262   */
 263
 264   public void testEquals() {
 265     OpenBitSet b1 = new OpenBitSet(1111);
 266     OpenBitSet b2 = new OpenBitSet(2222);
 267     assertTrue(b1.equals(b2));
 268     assertTrue(b2.equals(b1));
 269     b1.set(10);
 270     assertFalse(b1.equals(b2));
 271     assertFalse(b2.equals(b1));
 272     b2.set(10);
 273     assertTrue(b1.equals(b2));
 274     assertTrue(b2.equals(b1));
 275     b2.set(2221);
 276     assertFalse(b1.equals(b2));
 277     assertFalse(b2.equals(b1));
 278     b1.set(2221);
 279     assertTrue(b1.equals(b2));
 280     assertTrue(b2.equals(b1));
 281
 282     // try different type of object
 283     assertFalse(b1.equals(new Object()));
 284   }
 285
 286   public void testHashCodeEquals() {
 287     OpenBitSet bs1 = new OpenBitSet(200);
 288     OpenBitSet bs2 = new OpenBitSet(64);
 289     bs1.set(3);
 290     bs2.set(3);
 291     assertEquals(bs1, bs2);
 292     assertEquals(bs1.hashCode(), bs2.hashCode());
 293   }
 294
 295
 296   private OpenBitSet makeOpenBitSet(int[] a) {
 297     OpenBitSet bs = new OpenBitSet();
 298     for (int e: a) {
 299       bs.set(e);
 300     }
 301     return bs;
 302   }
 303
 304   private BitSet makeBitSet(int[] a) {
 305     BitSet bs = new BitSet();
 306     for (int e: a) {
 307       bs.set(e);
 308     }
 309     return bs;
 310   }
 311
 312   private void checkPrevSetBitArray(int [] a) {
 313     OpenBitSet obs = makeOpenBitSet(a);
 314     BitSet bs = makeBitSet(a);
 315     doPrevSetBit(bs, obs);
 316   }
 317
 318   public void testPrevSetBit() {
 319     checkPrevSetBitArray(new int[] {});
 320     checkPrevSetBitArray(new int[] {0});
 321     checkPrevSetBitArray(new int[] {0,2});
 322   }
 323 }
 324
 325
 326