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));
35 void doNextSetBit(BitSet a, OpenBitSet b) {
38 aa = a.nextSetBit(aa+1);
39 bb = b.nextSetBit(bb+1);
44 void doPrevSetBit(BitSet a, OpenBitSet b) {
45 int aa = a.size() + random.nextInt(100);
48 // aa = a.prevSetBit(aa-1);
50 while ((aa >= 0) && (! a.get(aa))) {
53 bb = b.prevSetBit(bb-1);
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);
64 void doIterate1(BitSet a, OpenBitSet b) {
66 OpenBitSetIterator iterator = new OpenBitSetIterator(b);
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);
74 void doIterate2(BitSet a, OpenBitSet b) {
76 OpenBitSetIterator iterator = new OpenBitSetIterator(b);
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);
84 void doRandomSets(int maxSize, int iter, int mode) {
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);
93 // test the various ways of setting bits
95 int nOper = random.nextInt(sz);
96 for (int j=0; j<nOper; j++) {
99 idx = random.nextInt(sz);
102 idx = random.nextInt(sz);
105 idx = random.nextInt(sz);
109 boolean val = b.flipAndGet(idx);
110 boolean val2 = b.flipAndGet(idx);
111 assertTrue(val != val2);
113 val = b.getAndSet(idx);
114 assertTrue(val2 == val);
115 assertTrue(b.get(idx));
117 if (!val) b.fastClear(idx);
118 assertTrue(b.get(idx) == val);
122 // test that the various ways of accessing the bits are equivalent
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);
132 doIterate(aa,bb, mode); // a problem here is from flip or doIterate
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);
139 doNextSetBit(aa,bb); // a problem here is from clear() or nextSetBit
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);
147 doNextSetBit(aa,bb); // a problem here is from set() or nextSetBit
152 assertEquals( a.equals(a0), b.equals(b0));
154 assertEquals(a.cardinality(), b.cardinality());
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);
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);
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);
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());
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));
188 // large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
190 public void testSmall() {
191 doRandomSets(atLeast(1200), atLeast(1000), 1);
192 doRandomSets(atLeast(1200), atLeast(1000), 2);
195 // uncomment to run a bigger test (~2 minutes).
197 public void testBig() {
198 doRandomSets(2000,200000, 1);
199 doRandomSets(2000,200000, 2);
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));
209 assertFalse(b1.equals(b2));
210 assertFalse(b2.equals(b1));
212 assertTrue(b1.equals(b2));
213 assertTrue(b2.equals(b1));
215 assertFalse(b1.equals(b2));
216 assertFalse(b2.equals(b1));
218 assertTrue(b1.equals(b2));
219 assertTrue(b2.equals(b1));
221 // try different type of object
222 assertFalse(b1.equals(new Object()));
225 public void testHashCodeEquals() {
226 OpenBitSet bs1 = new OpenBitSet(200);
227 OpenBitSet bs2 = new OpenBitSet(64);
230 assertEquals(bs1, bs2);
231 assertEquals(bs1.hashCode(), bs2.hashCode());
235 private OpenBitSet makeOpenBitSet(int[] a) {
236 OpenBitSet bs = new OpenBitSet();
243 private BitSet makeBitSet(int[] a) {
244 BitSet bs = new BitSet();
251 private void checkPrevSetBitArray(int [] a) {
252 OpenBitSet obs = makeOpenBitSet(a);
253 BitSet bs = makeBitSet(a);
254 doPrevSetBit(bs, obs);
257 public void testPrevSetBit() {
258 checkPrevSetBitArray(new int[] {});
259 checkPrevSetBitArray(new int[] {0});
260 checkPrevSetBitArray(new int[] {0,2});