lucene-java-3.5.0/lucene/backwards/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_or = (BitSet) a.clone();
 168         a_or.or(a0);
 169
 170         FixedBitSet b_or = (FixedBitSet) b.clone();
 171         b_or.or(b0);
 172
 173         assertEquals(a0.cardinality(), b0.cardinality());
 174         assertEquals(a_or.cardinality(), b_or.cardinality());
 175
 176         doIterate(a_or, b_or, mode);
 177       }
 178
 179       a0=a;
 180       b0=b;
 181     }
 182   }
 183
 184   // large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
 185   // larger testsuite.
 186   public void testSmall() throws IOException {
 187     doRandomSets(atLeast(1200), atLeast(1000), 1);
 188     doRandomSets(atLeast(1200), atLeast(1000), 2);
 189   }
 190
 191   // uncomment to run a bigger test (~2 minutes).
 192   /*
 193   public void testBig() {
 194     doRandomSets(2000,200000, 1);
 195     doRandomSets(2000,200000, 2);
 196   }
 197   */
 198
 199   public void testEquals() {
 200     // This test can't handle numBits==0:
 201     final int numBits = random.nextInt(2000) + 1;
 202     FixedBitSet b1 = new FixedBitSet(numBits);
 203     FixedBitSet b2 = new FixedBitSet(numBits);
 204     assertTrue(b1.equals(b2));
 205     assertTrue(b2.equals(b1));
 206     for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
 207       int idx = random.nextInt(numBits);
 208       if (!b1.get(idx)) {
 209         b1.set(idx);
 210         assertFalse(b1.equals(b2));
 211         assertFalse(b2.equals(b1));
 212         b2.set(idx);
 213         assertTrue(b1.equals(b2));
 214         assertTrue(b2.equals(b1));
 215       }
 216     }
 217
 218     // try different type of object
 219     assertFalse(b1.equals(new Object()));
 220   }
 221
 222   public void testHashCodeEquals() {
 223     // This test can't handle numBits==0:
 224     final int numBits = random.nextInt(2000) + 1;
 225     FixedBitSet b1 = new FixedBitSet(numBits);
 226     FixedBitSet b2 = new FixedBitSet(numBits);
 227     assertTrue(b1.equals(b2));
 228     assertTrue(b2.equals(b1));
 229     for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
 230       int idx = random.nextInt(numBits);
 231       if (!b1.get(idx)) {
 232         b1.set(idx);
 233         assertFalse(b1.equals(b2));
 234         assertFalse(b1.hashCode() == b2.hashCode());
 235         b2.set(idx);
 236         assertEquals(b1, b2);
 237         assertEquals(b1.hashCode(), b2.hashCode());
 238       }
 239     }
 240   }
 241
 242   public void testSmallBitSets() {
 243     // Make sure size 0-10 bit sets are OK:
 244     for(int numBits=0;numBits<10;numBits++) {
 245       FixedBitSet b1 = new FixedBitSet(numBits);
 246       FixedBitSet b2 = new FixedBitSet(numBits);
 247       assertTrue(b1.equals(b2));
 248       assertEquals(b1.hashCode(), b2.hashCode());
 249       assertEquals(0, b1.cardinality());
 250       if (numBits > 0) {
 251         b1.set(0, numBits);
 252         assertEquals(numBits, b1.cardinality());
 253         b1.flip(0, numBits);
 254         assertEquals(0, b1.cardinality());
 255       }
 256     }
 257   }
 258
 259   private FixedBitSet makeFixedBitSet(int[] a, int numBits) {
 260     FixedBitSet bs = new FixedBitSet(numBits);
 261     for (int e: a) {
 262       bs.set(e);
 263     }
 264     return bs;
 265   }
 266
 267   private BitSet makeBitSet(int[] a) {
 268     BitSet bs = new BitSet();
 269     for (int e: a) {
 270       bs.set(e);
 271     }
 272     return bs;
 273   }
 274
 275   private void checkPrevSetBitArray(int [] a, int numBits) {
 276     FixedBitSet obs = makeFixedBitSet(a, numBits);
 277     BitSet bs = makeBitSet(a);
 278     doPrevSetBit(bs, obs);
 279   }
 280
 281   public void testPrevSetBit() {
 282     checkPrevSetBitArray(new int[] {}, 0);
 283     checkPrevSetBitArray(new int[] {0}, 1);
 284     checkPrevSetBitArray(new int[] {0,2}, 3);
 285   }
 286 }
 287
 288
 289