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
9 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 package org.apache.lucene.util;
20 import java.util.BitSet;
22 import org.apache.lucene.search.DocIdSetIterator;
24 public class TestOpenBitSet extends LuceneTestCase {
26 void doGet(BitSet a, OpenBitSet b) {
28 for (int i=0; i<max; i++) {
29 if (a.get(i) != b.get(i)) {
30 fail("mismatch: BitSet=["+i+"]="+a.get(i));
32 if (a.get(i) != b.get((long) i)) {
33 fail("mismatch: BitSet=["+i+"]="+a.get(i));
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));
43 if (a.get(i) != b.fastGet((long) i)) {
44 fail("mismatch: BitSet=["+i+"]="+a.get(i));
49 void doNextSetBit(BitSet a, OpenBitSet b) {
52 aa = a.nextSetBit(aa+1);
53 bb = b.nextSetBit(bb+1);
58 void doNextSetBitLong(BitSet a, OpenBitSet b) {
61 aa = a.nextSetBit(aa+1);
62 bb = (int) b.nextSetBit((long) (bb+1));
67 void doPrevSetBit(BitSet a, OpenBitSet b) {
68 int aa = a.size() + random.nextInt(100);
71 // aa = a.prevSetBit(aa-1);
73 while ((aa >= 0) && (! a.get(aa))) {
76 bb = b.prevSetBit(bb-1);
81 void doPrevSetBitLong(BitSet a, OpenBitSet b) {
82 int aa = a.size() + random.nextInt(100);
85 // aa = a.prevSetBit(aa-1);
87 while ((aa >= 0) && (! a.get(aa))) {
90 bb = (int) b.prevSetBit((long) (bb-1));
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);
101 void doIterate1(BitSet a, OpenBitSet b) {
103 OpenBitSetIterator iterator = new OpenBitSetIterator(b);
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);
111 void doIterate2(BitSet a, OpenBitSet b) {
113 OpenBitSetIterator iterator = new OpenBitSetIterator(b);
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);
121 void doRandomSets(int maxSize, int iter, int mode) {
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);
130 // test the various ways of setting bits
132 int nOper = random.nextInt(sz);
133 for (int j=0; j<nOper; j++) {
136 idx = random.nextInt(sz);
140 idx = random.nextInt(sz);
142 b.fastSet((long) idx);
144 idx = random.nextInt(sz);
148 idx = random.nextInt(sz);
150 b.fastClear((long) idx);
152 idx = random.nextInt(sz);
156 boolean val = b.flipAndGet(idx);
157 boolean val2 = b.flipAndGet(idx);
158 assertTrue(val != val2);
160 idx = random.nextInt(sz);
162 b.fastFlip((long) idx);
164 val = b.flipAndGet((long) idx);
165 val2 = b.flipAndGet((long) idx);
166 assertTrue(val != val2);
168 val = b.getAndSet(idx);
169 assertTrue(val2 == val);
170 assertTrue(b.get(idx));
172 if (!val) b.fastClear(idx);
173 assertTrue(b.get(idx) == val);
177 // test that the various ways of accessing the bits are equivalent
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);
188 doIterate(aa,bb, mode); // a problem here is from flip or doIterate
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);
195 doNextSetBit(aa,bb); // a problem here is from clear() or nextSetBit
196 doNextSetBitLong(aa,bb);
199 doPrevSetBitLong(aa,bb);
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);
206 doNextSetBit(aa,bb); // a problem here is from set() or nextSetBit
207 doNextSetBitLong(aa,bb);
210 doPrevSetBitLong(aa,bb);
213 assertEquals( a.equals(a0), b.equals(b0));
215 assertEquals(a.cardinality(), b.cardinality());
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);
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);
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);
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());
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));
249 // large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
251 public void testSmall() {
252 doRandomSets(atLeast(1200), atLeast(1000), 1);
253 doRandomSets(atLeast(1200), atLeast(1000), 2);
256 // uncomment to run a bigger test (~2 minutes).
258 public void testBig() {
259 doRandomSets(2000,200000, 1);
260 doRandomSets(2000,200000, 2);
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));
270 assertFalse(b1.equals(b2));
271 assertFalse(b2.equals(b1));
273 assertTrue(b1.equals(b2));
274 assertTrue(b2.equals(b1));
276 assertFalse(b1.equals(b2));
277 assertFalse(b2.equals(b1));
279 assertTrue(b1.equals(b2));
280 assertTrue(b2.equals(b1));
282 // try different type of object
283 assertFalse(b1.equals(new Object()));
286 public void testHashCodeEquals() {
287 OpenBitSet bs1 = new OpenBitSet(200);
288 OpenBitSet bs2 = new OpenBitSet(64);
291 assertEquals(bs1, bs2);
292 assertEquals(bs1.hashCode(), bs2.hashCode());
296 private OpenBitSet makeOpenBitSet(int[] a) {
297 OpenBitSet bs = new OpenBitSet();
304 private BitSet makeBitSet(int[] a) {
305 BitSet bs = new BitSet();
312 private void checkPrevSetBitArray(int [] a) {
313 OpenBitSet obs = makeOpenBitSet(a);
314 BitSet bs = makeBitSet(a);
315 doPrevSetBit(bs, obs);
318 public void testPrevSetBit() {
319 checkPrevSetBitArray(new int[] {});
320 checkPrevSetBitArray(new int[] {0});
321 checkPrevSetBitArray(new int[] {0,2});