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