001: /**
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */package org.apache.solr.util;
017:
018: import junit.framework.TestCase;
019:
020: import java.util.Random;
021: import java.util.BitSet;
022:
023: /**
024: * @author yonik
025: * @version $Id$
026: */
027: public class TestOpenBitSet extends TestCase {
028: static Random rand = new Random();
029:
030: void doGet(BitSet a, OpenBitSet b) {
031: int max = a.size();
032: for (int i = 0; i < max; i++) {
033: if (a.get(i) != b.get(i)) {
034: fail("mismatch: BitSet=[" + i + "]=" + a.get(i));
035: }
036: }
037: }
038:
039: void doNextSetBit(BitSet a, OpenBitSet b) {
040: int aa = -1, bb = -1;
041: do {
042: aa = a.nextSetBit(aa + 1);
043: bb = b.nextSetBit(bb + 1);
044: assertEquals(aa, bb);
045: } while (aa >= 0);
046: }
047:
048: // test interleaving different BitSetIterator.next()
049: void doIterate(BitSet a, OpenBitSet b) {
050: int aa = -1, bb = -1;
051: BitSetIterator iterator = new BitSetIterator(b);
052: do {
053: aa = a.nextSetBit(aa + 1);
054: if (rand.nextBoolean())
055: bb = iterator.next();
056: else
057: bb = iterator.next(bb + 1);
058: assertEquals(aa, bb);
059: } while (aa >= 0);
060: }
061:
062: void doRandomSets(int maxSize, int iter) {
063: BitSet a0 = null;
064: OpenBitSet b0 = null;
065:
066: for (int i = 0; i < iter; i++) {
067: int sz = rand.nextInt(maxSize);
068: BitSet a = new BitSet(sz);
069: OpenBitSet b = new OpenBitSet(sz);
070:
071: // test the various ways of setting bits
072: if (sz > 0) {
073: int nOper = rand.nextInt(sz);
074: for (int j = 0; j < nOper; j++) {
075: int idx;
076: idx = rand.nextInt(sz);
077: a.set(idx);
078: b.fastSet(idx);
079: idx = rand.nextInt(sz);
080: a.clear(idx);
081: b.fastClear(idx);
082: idx = rand.nextInt(sz);
083: a.flip(idx);
084: b.fastFlip(idx);
085: int idx1 = rand.nextInt(sz);
086: int idx2 = rand.nextInt(sz);
087: if (idx1 > idx2) {
088: idx = idx1;
089: idx1 = idx2;
090: idx2 = idx;
091: }
092: a.flip(idx1, idx2);
093: b.flip(idx1, idx2);
094:
095: boolean val = b.flipAndGet(idx);
096: boolean val2 = b.flipAndGet(idx);
097: assertTrue(val != val2);
098:
099: val = b.getAndSet(idx);
100: assertTrue(val2 == val);
101: assertTrue(b.get(idx));
102: if (!val)
103: b.fastClear(idx);
104: assertTrue(b.get(idx) == val);
105: }
106: }
107:
108: // test that the various ways of accessing the bits are equivalent
109: doGet(a, b);
110: doNextSetBit(a, b);
111: doIterate(a, b);
112:
113: // test negation
114: int fromIndex = rand.nextInt(sz + 80);
115: int toIndex = fromIndex + rand.nextInt((sz >> 1) + 1);
116: BitSet a_not = (BitSet) a.clone();
117: a_not.flip(fromIndex, toIndex);
118: OpenBitSet b_not = (OpenBitSet) b.clone();
119: b_not.flip(fromIndex, toIndex);
120: doIterate(a, b);
121:
122: if (a0 != null) {
123: assertEquals(a.equals(a0), b.equals(b0));
124:
125: assertEquals(a.cardinality(), b.cardinality());
126:
127: BitSet a_and = (BitSet) a.clone();
128: a_and.and(a0);
129: BitSet a_or = (BitSet) a.clone();
130: a_or.or(a0);
131: BitSet a_xor = (BitSet) a.clone();
132: a_xor.xor(a0);
133: BitSet a_andn = (BitSet) a.clone();
134: a_andn.andNot(a0);
135:
136: OpenBitSet b_and = (OpenBitSet) b.clone();
137: assertEquals(b, b_and);
138: b_and.and(b0);
139: OpenBitSet b_or = (OpenBitSet) b.clone();
140: b_or.or(b0);
141: OpenBitSet b_xor = (OpenBitSet) b.clone();
142: b_xor.xor(b0);
143: OpenBitSet b_andn = (OpenBitSet) b.clone();
144: b_andn.andNot(b0);
145:
146: doIterate(a_and, b_and);
147: doIterate(a_or, b_or);
148: doIterate(a_xor, b_xor);
149: doIterate(a_andn, b_andn);
150:
151: assertEquals(a_and.cardinality(), b_and.cardinality());
152: assertEquals(a_or.cardinality(), b_or.cardinality());
153: assertEquals(a_xor.cardinality(), b_xor.cardinality());
154: assertEquals(a_andn.cardinality(), b_andn.cardinality());
155:
156: // test non-mutating popcounts
157: assertEquals(b_and.cardinality(), OpenBitSet
158: .intersectionCount(b, b0));
159: assertEquals(b_or.cardinality(), OpenBitSet.unionCount(
160: b, b0));
161: assertEquals(b_xor.cardinality(), OpenBitSet.xorCount(
162: b, b0));
163: assertEquals(b_andn.cardinality(), OpenBitSet
164: .andNotCount(b, b0));
165: }
166:
167: a0 = a;
168: b0 = b;
169: }
170: }
171:
172: // large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
173: // larger testsuite.
174: public void testSmall() {
175: doRandomSets(1200, 1000);
176: }
177:
178: public void testBig() {
179: // uncomment to run a bigger test (~2 minutes).
180: // doRandomSets(2000,200000);
181: }
182:
183: public void testEquals() {
184: OpenBitSet b1 = new OpenBitSet(1111);
185: OpenBitSet b2 = new OpenBitSet(2222);
186: assertTrue(b1.equals(b2));
187: assertTrue(b2.equals(b1));
188: b1.set(10);
189: assertFalse(b1.equals(b2));
190: assertFalse(b2.equals(b1));
191: b2.set(10);
192: assertTrue(b1.equals(b2));
193: assertTrue(b2.equals(b1));
194: b2.set(2221);
195: assertFalse(b1.equals(b2));
196: assertFalse(b2.equals(b1));
197: b1.set(2221);
198: assertTrue(b1.equals(b2));
199: assertTrue(b2.equals(b1));
200:
201: // try different type of object
202: assertFalse(b1.equals(1));
203: }
204:
205: }
|