1 /*
2 * Copyright (c) 1998, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /* @test
25 * @bug 4098239 4107540 4080736 4261102 4274710 4305272
26 * 4979017 4979028 4979031 5030267 6222207 8040806
27 * @summary Test the operation of the methods of BitSet class
28 * @author Mike McCloskey, Martin Buchholz
29 * @run main/othervm BSMethods
30 */
31
32 import java.util.*;
33
34 /**
35 * This is a simple test class created to run tests on the BitSet class.
36 *
37 */
38 public class BSMethods {
39
40 private static Random generator = new Random();
41 private static boolean failure = false;
42
43 private static void fail(String diagnostic) {
44 new Error(diagnostic).printStackTrace();
45 failure = true;
46 }
47
48 private static void check(boolean condition) {
49 check(condition, "something's fishy");
50 }
51
52 private static void check(boolean condition, String diagnostic) {
53 if (! condition)
54 fail(diagnostic);
55 }
56
57 private static void checkEmpty(BitSet s) {
58 check(s.isEmpty(), "isEmpty");
59 check(s.length() == 0, "length");
60 check(s.cardinality() == 0, "cardinality");
61 check(s.equals(new BitSet()) , "equals");
62 check(s.equals(new BitSet(0)) , "equals");
63 check(s.equals(new BitSet(127)), "equals");
64 check(s.equals(new BitSet(128)), "equals");
65 check(s.nextSetBit(0) == -1, "nextSetBit");
66 check(s.nextSetBit(127) == -1, "nextSetBit");
67 check(s.nextSetBit(128) == -1, "nextSetBit");
68 check(s.nextClearBit(0) == 0, "nextClearBit");
69 check(s.nextClearBit(127) == 127, "nextClearBit");
70 check(s.nextClearBit(128) == 128, "nextClearBit");
71 check(s.toString().equals("{}"), "toString");
72 check(! s.get(0), "get");
73 }
74
75 private static BitSet makeSet(int... elts) {
76 BitSet s = new BitSet();
77 for (int elt : elts)
78 s.set(elt);
79 return s;
80 }
81
82 private static void checkEquality(BitSet s, BitSet t) {
83 checkSanity(s, t);
84 check(s.equals(t), "equals");
85 check(s.toString().equals(t.toString()), "equal strings");
86 check(s.length() == t.length(), "equal lengths");
87 check(s.cardinality() == t.cardinality(), "equal cardinalities");
88 }
89
90 private static void checkSanity(BitSet... sets) {
91 for (BitSet s : sets) {
92 int len = s.length();
93 int cardinality1 = s.cardinality();
94 int cardinality2 = 0;
95 for (int i = s.nextSetBit(0); i >= 0; i = s.nextSetBit(i+1)) {
96 check(s.get(i));
97 cardinality2++;
98 }
99 check(s.nextSetBit(len) == -1, "last set bit");
100 check(s.nextClearBit(len) == len, "last set bit");
101 check(s.isEmpty() == (len == 0), "emptiness");
102 check(cardinality1 == cardinality2, "cardinalities");
103 check(len <= s.size(), "length <= size");
104 check(len >= 0, "length >= 0");
105 check(cardinality1 >= 0, "cardinality >= 0");
106 }
107 }
108
109 public static void main(String[] args) {
110
111 //testFlipTime();
112
113 // These are the single bit versions
114 testSetGetClearFlip();
115
116 // Test the ranged versions
117 testClear();
118
119 testFlip();
120 testSet();
121 testGet();
122
123 // BitSet interaction calls
124 testAndNot();
125 testAnd();
126 testOr();
127 testXor();
128
129 // Miscellaneous calls
130 testLength();
131 testEquals();
132 testNextSetBit();
133 testNextClearBit();
134 testIntersects();
135 testCardinality();
136 testEmpty();
137 testEmpty2();
138 testToString();
139 testLogicalIdentities();
140
141 if (failure)
142 throw new RuntimeException("One or more BitSet failures.");
143 }
144
145 private static void report(String testName, int failCount) {
146 System.err.println(testName+": " +
147 (failCount==0 ? "Passed":"Failed("+failCount+")"));
148 if (failCount > 0)
149 failure = true;
150 }
151
152 private static void testFlipTime() {
153 // Make a fairly random bitset
154 BitSet b1 = new BitSet();
155 b1.set(1000);
156 long startTime = System.currentTimeMillis();
157 for(int x=0; x<100000; x++) {
158 b1.flip(100, 900);
159 }
160 long endTime = System.currentTimeMillis();
161 long total = endTime - startTime;
162 System.out.println("Multiple word flip Time "+total);
163
164 startTime = System.currentTimeMillis();
165 for(int x=0; x<100000; x++) {
166 b1.flip(2, 44);
167 }
168 endTime = System.currentTimeMillis();
169 total = endTime - startTime;
170 System.out.println("Single word flip Time "+total);
171 }
172
173 private static void testNextSetBit() {
174 int failCount = 0;
175
176 for (int i=0; i<100; i++) {
177 int numberOfSetBits = generator.nextInt(100) + 1;
178 BitSet testSet = new BitSet();
179 int[] history = new int[numberOfSetBits];
180
181 // Set some random bits and remember them
182 int nextBitToSet = 0;
183 for (int x=0; x<numberOfSetBits; x++) {
184 nextBitToSet += generator.nextInt(30)+1;
185 history[x] = nextBitToSet;
186 testSet.set(nextBitToSet);
187 }
188
189 // Verify their retrieval using nextSetBit()
190 int historyIndex = 0;
191 for(int x=testSet.nextSetBit(0); x>=0; x=testSet.nextSetBit(x+1)) {
192 if (x != history[historyIndex++])
193 failCount++;
194 }
195
196 checkSanity(testSet);
197 }
198
199 report("NextSetBit ", failCount);
200 }
201
202 private static void testNextClearBit() {
203 int failCount = 0;
204
205 for (int i=0; i<1000; i++) {
206 BitSet b = new BitSet(256);
207 int[] history = new int[10];
208
209 // Set all the bits
210 for (int x=0; x<256; x++)
211 b.set(x);
212
213 // Clear some random bits and remember them
214 int nextBitToClear = 0;
215 for (int x=0; x<10; x++) {
216 nextBitToClear += generator.nextInt(24)+1;
217 history[x] = nextBitToClear;
218 b.clear(nextBitToClear);
219 }
220
221 // Verify their retrieval using nextClearBit()
222 int historyIndex = 0;
223 for(int x=b.nextClearBit(0); x<256; x=b.nextClearBit(x+1)) {
224 if (x != history[historyIndex++])
225 failCount++;
226 }
227
228 checkSanity(b);
229 }
230
231 // regression test for 4350178
232 BitSet bs = new BitSet();
233 if (bs.nextClearBit(0) != 0)
234 failCount++;
235 for (int i = 0; i < 64; i++) {
236 bs.set(i);
237 if (bs.nextClearBit(0) != i+1)
238 failCount++;
239 }
240
241 checkSanity(bs);
242
243 report("NextClearBit ", failCount);
244 }
245
246 private static void testSetGetClearFlip() {
247 int failCount = 0;
248
249 for (int i=0; i<100; i++) {
250 BitSet testSet = new BitSet();
251 HashSet<Integer> history = new HashSet<Integer>();
252
253 // Set a random number of bits in random places
254 // up to a random maximum
255 int nextBitToSet = 0;
256 int numberOfSetBits = generator.nextInt(100) + 1;
257 int highestPossibleSetBit = generator.nextInt(1000) + 1;
258 for (int x=0; x<numberOfSetBits; x++) {
259 nextBitToSet = generator.nextInt(highestPossibleSetBit);
260 history.add(new Integer(nextBitToSet));
261 testSet.set(nextBitToSet);
262 }
263
264 // Make sure each bit is set appropriately
265 for (int x=0; x<highestPossibleSetBit; x++) {
266 if (testSet.get(x) != history.contains(new Integer(x)))
267 failCount++;
268 }
269
270 // Clear the bits
271 Iterator<Integer> setBitIterator = history.iterator();
272 while (setBitIterator.hasNext()) {
273 Integer setBit = setBitIterator.next();
274 testSet.clear(setBit.intValue());
275 }
276
277 // Verify they were cleared
278 for (int x=0; x<highestPossibleSetBit; x++)
279 if (testSet.get(x))
280 failCount++;
281 if(testSet.length() != 0)
282 failCount++;
283
284 // Set them with set(int, boolean)
285 setBitIterator = history.iterator();
286 while (setBitIterator.hasNext()) {
287 Integer setBit = setBitIterator.next();
288 testSet.set(setBit.intValue(), true);
289 }
290
291 // Make sure each bit is set appropriately
292 for (int x=0; x<highestPossibleSetBit; x++) {
293 if (testSet.get(x) != history.contains(new Integer(x)))
294 failCount++;
295 }
296
297 // Clear them with set(int, boolean)
298 setBitIterator = history.iterator();
299 while (setBitIterator.hasNext()) {
300 Integer setBit = (Integer)setBitIterator.next();
301 testSet.set(setBit.intValue(), false);
302 }
303
304 // Verify they were cleared
305 for (int x=0; x<highestPossibleSetBit; x++)
306 if (testSet.get(x))
307 failCount++;
308 if(testSet.length() != 0)
309 failCount++;
310
311 // Flip them on
312 setBitIterator = history.iterator();
313 while (setBitIterator.hasNext()) {
314 Integer setBit = (Integer)setBitIterator.next();
315 testSet.flip(setBit.intValue());
316 }
317
318 // Verify they were flipped
319 for (int x=0; x<highestPossibleSetBit; x++) {
320 if (testSet.get(x) != history.contains(new Integer(x)))
321 failCount++;
322 }
323
324 // Flip them off
325 setBitIterator = history.iterator();
326 while (setBitIterator.hasNext()) {
327 Integer setBit = (Integer)setBitIterator.next();
328 testSet.flip(setBit.intValue());
329 }
330
331 // Verify they were flipped
332 for (int x=0; x<highestPossibleSetBit; x++)
333 if (testSet.get(x))
334 failCount++;
335 if(testSet.length() != 0)
336 failCount++;
337
338 checkSanity(testSet);
339 }
340
341 report("SetGetClearFlip ", failCount);
342 }
343
344 private static void testAndNot() {
345 int failCount = 0;
346
347 for (int i=0; i<100; i++) {
348 BitSet b1 = new BitSet(256);
349 BitSet b2 = new BitSet(256);
350
351 // Set some random bits in first set and remember them
352 int nextBitToSet = 0;
353 for (int x=0; x<10; x++)
354 b1.set(generator.nextInt(255));
355
356 // Set some random bits in second set and remember them
357 for (int x=10; x<20; x++)
358 b2.set(generator.nextInt(255));
359
360 // andNot the sets together
361 BitSet b3 = (BitSet)b1.clone();
362 b3.andNot(b2);
363
364 // Examine each bit of b3 for errors
365 for(int x=0; x<256; x++) {
366 boolean bit1 = b1.get(x);
367 boolean bit2 = b2.get(x);
368 boolean bit3 = b3.get(x);
369 if (!(bit3 == (bit1 & (!bit2))))
370 failCount++;
371 }
372 checkSanity(b1, b2, b3);
373 }
374
375 report("AndNot ", failCount);
376 }
377
378 private static void testAnd() {
379 int failCount = 0;
380
381 for (int i=0; i<100; i++) {
382 BitSet b1 = new BitSet(256);
383 BitSet b2 = new BitSet(256);
384
385 // Set some random bits in first set and remember them
386 int nextBitToSet = 0;
387 for (int x=0; x<10; x++)
388 b1.set(generator.nextInt(255));
389
390 // Set more random bits in second set and remember them
391 for (int x=10; x<20; x++)
392 b2.set(generator.nextInt(255));
393
394 // And the sets together
395 BitSet b3 = (BitSet)b1.clone();
396 b3.and(b2);
397
398 // Examine each bit of b3 for errors
399 for(int x=0; x<256; x++) {
400 boolean bit1 = b1.get(x);
401 boolean bit2 = b2.get(x);
402 boolean bit3 = b3.get(x);
403 if (!(bit3 == (bit1 & bit2)))
404 failCount++;
405 }
406 checkSanity(b1, b2, b3);
407 }
408
409 // `and' that happens to clear the last word
410 BitSet b4 = makeSet(2, 127);
411 b4.and(makeSet(2, 64));
412 checkSanity(b4);
413 if (!(b4.equals(makeSet(2))))
414 failCount++;
415
416 report("And ", failCount);
417 }
418
419 private static void testOr() {
420 int failCount = 0;
421
422 for (int i=0; i<100; i++) {
423 BitSet b1 = new BitSet(256);
424 BitSet b2 = new BitSet(256);
425 int[] history = new int[20];
426
427 // Set some random bits in first set and remember them
428 int nextBitToSet = 0;
429 for (int x=0; x<10; x++) {
430 nextBitToSet = generator.nextInt(255);
431 history[x] = nextBitToSet;
432 b1.set(nextBitToSet);
433 }
434
435 // Set more random bits in second set and remember them
436 for (int x=10; x<20; x++) {
437 nextBitToSet = generator.nextInt(255);
438 history[x] = nextBitToSet;
439 b2.set(nextBitToSet);
440 }
441
442 // Or the sets together
443 BitSet b3 = (BitSet)b1.clone();
444 b3.or(b2);
445
446 // Verify the set bits of b3 from the history
447 int historyIndex = 0;
448 for(int x=0; x<20; x++) {
449 if (!b3.get(history[x]))
450 failCount++;
451 }
452
453 // Examine each bit of b3 for errors
454 for(int x=0; x<256; x++) {
455 boolean bit1 = b1.get(x);
456 boolean bit2 = b2.get(x);
457 boolean bit3 = b3.get(x);
458 if (!(bit3 == (bit1 | bit2)))
459 failCount++;
460 }
461 checkSanity(b1, b2, b3);
462 }
463
464 report("Or ", failCount);
465 }
466
467 private static void testXor() {
468 int failCount = 0;
469
470 for (int i=0; i<100; i++) {
471 BitSet b1 = new BitSet(256);
472 BitSet b2 = new BitSet(256);
473
474 // Set some random bits in first set and remember them
475 int nextBitToSet = 0;
476 for (int x=0; x<10; x++)
477 b1.set(generator.nextInt(255));
478
479 // Set more random bits in second set and remember them
480 for (int x=10; x<20; x++)
481 b2.set(generator.nextInt(255));
482
483 // Xor the sets together
484 BitSet b3 = (BitSet)b1.clone();
485 b3.xor(b2);
486
487 // Examine each bit of b3 for errors
488 for(int x=0; x<256; x++) {
489 boolean bit1 = b1.get(x);
490 boolean bit2 = b2.get(x);
491 boolean bit3 = b3.get(x);
492 if (!(bit3 == (bit1 ^ bit2)))
493 failCount++;
494 }
495 checkSanity(b1, b2, b3);
496 b3.xor(b3); checkEmpty(b3);
497 }
498
499 // xor that happens to clear the last word
500 BitSet b4 = makeSet(2, 64, 127);
501 b4.xor(makeSet(64, 127));
502 checkSanity(b4);
503 if (!(b4.equals(makeSet(2))))
504 failCount++;
505
506 report("Xor ", failCount);
507 }
508
509 private static void testEquals() {
510 int failCount = 0;
511
512 for (int i=0; i<100; i++) {
513 // Create BitSets of different sizes
514 BitSet b1 = new BitSet(generator.nextInt(1000)+1);
515 BitSet b2 = new BitSet(generator.nextInt(1000)+1);
516
517 // Set some random bits
518 int nextBitToSet = 0;
519 for (int x=0; x<10; x++) {
520 nextBitToSet += generator.nextInt(50)+1;
521 b1.set(nextBitToSet);
522 b2.set(nextBitToSet);
523 }
524
525 // Verify their equality despite different storage sizes
526 if (!b1.equals(b2))
527 failCount++;
528 checkEquality(b1,b2);
529 }
530
531 report("Equals ", failCount);
532 }
533
534 private static void testLength() {
535 int failCount = 0;
536
537 // Test length after set
538 for (int i=0; i<100; i++) {
539 BitSet b1 = new BitSet(256);
540 int highestSetBit = 0;
541
542 for(int x=0; x<100; x++) {
543 int nextBitToSet = generator.nextInt(255);
544 if (nextBitToSet > highestSetBit)
545 highestSetBit = nextBitToSet;
546 b1.set(nextBitToSet);
547 if (b1.length() != highestSetBit + 1)
548 failCount++;
549 }
550 checkSanity(b1);
551 }
552
553 // Test length after flip
554 for (int i=0; i<100; i++) {
555 BitSet b1 = new BitSet(256);
556 for(int x=0; x<100; x++) {
557 // Flip a random range twice
558 int rangeStart = generator.nextInt(100);
559 int rangeEnd = rangeStart + generator.nextInt(100);
560 b1.flip(rangeStart);
561 b1.flip(rangeStart);
562 if (b1.length() != 0)
563 failCount++;
564 b1.flip(rangeStart, rangeEnd);
565 b1.flip(rangeStart, rangeEnd);
566 if (b1.length() != 0)
567 failCount++;
568 }
569 checkSanity(b1);
570 }
571
572 // Test length after or
573 for (int i=0; i<100; i++) {
574 BitSet b1 = new BitSet(256);
575 BitSet b2 = new BitSet(256);
576 int bit1 = generator.nextInt(100);
577 int bit2 = generator.nextInt(100);
578 int highestSetBit = (bit1 > bit2) ? bit1 : bit2;
579 b1.set(bit1);
580 b2.set(bit2);
581 b1.or(b2);
582 if (b1.length() != highestSetBit + 1)
583 failCount++;
584 checkSanity(b1, b2);
585 }
586
587 report("Length ", failCount);
588 }
589
590 private static void testClear() {
591 int failCount = 0;
592
593 for (int i=0; i<1000; i++) {
594 BitSet b1 = new BitSet();
595
596 // Make a fairly random bitset
597 int numberOfSetBits = generator.nextInt(100) + 1;
598 int highestPossibleSetBit = generator.nextInt(1000) + 1;
599
600 for (int x=0; x<numberOfSetBits; x++)
601 b1.set(generator.nextInt(highestPossibleSetBit));
602
603 BitSet b2 = (BitSet)b1.clone();
604
605 // Clear out a random range
606 int rangeStart = generator.nextInt(100);
607 int rangeEnd = rangeStart + generator.nextInt(100);
608
609 // Use the clear(int, int) call on b1
610 b1.clear(rangeStart, rangeEnd);
611
612 // Use a loop on b2
613 for (int x=rangeStart; x<rangeEnd; x++)
614 b2.clear(x);
615
616 // Verify their equality
617 if (!b1.equals(b2)) {
618 System.out.println("rangeStart = " + rangeStart);
619 System.out.println("rangeEnd = " + rangeEnd);
620 System.out.println("b1 = " + b1);
621 System.out.println("b2 = " + b2);
622 failCount++;
623 }
624 checkEquality(b1,b2);
625 }
626
627 report("Clear ", failCount);
628 }
629
630 private static void testSet() {
631 int failCount = 0;
632
633 // Test set(int, int)
634 for (int i=0; i<1000; i++) {
635 BitSet b1 = new BitSet();
636
637 // Make a fairly random bitset
638 int numberOfSetBits = generator.nextInt(100) + 1;
639 int highestPossibleSetBit = generator.nextInt(1000) + 1;
640
641 for (int x=0; x<numberOfSetBits; x++)
642 b1.set(generator.nextInt(highestPossibleSetBit));
643
644 BitSet b2 = (BitSet)b1.clone();
645
646 // Set a random range
647 int rangeStart = generator.nextInt(100);
648 int rangeEnd = rangeStart + generator.nextInt(100);
649
650 // Use the set(int, int) call on b1
651 b1.set(rangeStart, rangeEnd);
652
653 // Use a loop on b2
654 for (int x=rangeStart; x<rangeEnd; x++)
655 b2.set(x);
656
657 // Verify their equality
658 if (!b1.equals(b2)) {
659 System.out.println("Set 1");
660 System.out.println("rangeStart = " + rangeStart);
661 System.out.println("rangeEnd = " + rangeEnd);
662 System.out.println("b1 = " + b1);
663 System.out.println("b2 = " + b2);
664 failCount++;
665 }
666 checkEquality(b1,b2);
667 }
668
669 // Test set(int, int, boolean)
670 for (int i=0; i<100; i++) {
671 BitSet b1 = new BitSet();
672
673 // Make a fairly random bitset
674 int numberOfSetBits = generator.nextInt(100) + 1;
675 int highestPossibleSetBit = generator.nextInt(1000) + 1;
676
677 for (int x=0; x<numberOfSetBits; x++)
678 b1.set(generator.nextInt(highestPossibleSetBit));
679
680 BitSet b2 = (BitSet)b1.clone();
681 boolean setOrClear = generator.nextBoolean();
682
683 // Set a random range
684 int rangeStart = generator.nextInt(100);
685 int rangeEnd = rangeStart + generator.nextInt(100);
686
687 // Use the set(int, int, boolean) call on b1
688 b1.set(rangeStart, rangeEnd, setOrClear);
689
690 // Use a loop on b2
691 for (int x=rangeStart; x<rangeEnd; x++)
692 b2.set(x, setOrClear);
693
694 // Verify their equality
695 if (!b1.equals(b2)) {
696 System.out.println("Set 2");
697 System.out.println("b1 = " + b1);
698 System.out.println("b2 = " + b2);
699 failCount++;
700 }
701 checkEquality(b1,b2);
702 }
703
704 report("Set ", failCount);
705 }
706
707 private static void testFlip() {
708 int failCount = 0;
709
710 for (int i=0; i<1000; i++) {
711 BitSet b1 = new BitSet();
712
713 // Make a fairly random bitset
714 int numberOfSetBits = generator.nextInt(100) + 1;
715 int highestPossibleSetBit = generator.nextInt(1000) + 1;
716
717 for (int x=0; x<numberOfSetBits; x++)
718 b1.set(generator.nextInt(highestPossibleSetBit));
719
720 BitSet b2 = (BitSet)b1.clone();
721
722 // Flip a random range
723 int rangeStart = generator.nextInt(100);
724 int rangeEnd = rangeStart + generator.nextInt(100);
725
726 // Use the flip(int, int) call on b1
727 b1.flip(rangeStart, rangeEnd);
728
729 // Use a loop on b2
730 for (int x=rangeStart; x<rangeEnd; x++)
731 b2.flip(x);
732
733 // Verify their equality
734 if (!b1.equals(b2))
735 failCount++;
736 checkEquality(b1,b2);
737 }
738
739 report("Flip ", failCount);
740 }
741
742 private static void testGet() {
743 int failCount = 0;
744
745 for (int i=0; i<1000; i++) {
746 BitSet b1 = new BitSet();
747
748 // Make a fairly random bitset
749 int numberOfSetBits = generator.nextInt(100) + 1;
750 int highestPossibleSetBit = generator.nextInt(1000) + 1;
751
752 for (int x=0; x<numberOfSetBits; x++)
753 b1.set(generator.nextInt(highestPossibleSetBit));
754
755 // Get a new set from a random range
756 int rangeStart = generator.nextInt(100);
757 int rangeEnd = rangeStart + generator.nextInt(100);
758
759 BitSet b2 = b1.get(rangeStart, rangeEnd);
760
761 BitSet b3 = new BitSet();
762 for(int x=rangeStart; x<rangeEnd; x++)
763 b3.set(x-rangeStart, b1.get(x));
764
765 // Verify their equality
766 if (!b2.equals(b3)) {
767 System.out.println("start="+rangeStart);
768 System.out.println("end="+rangeEnd);
769 System.out.println(b1);
770 System.out.println(b2);
771 System.out.println(b3);
772 failCount++;
773 }
774 checkEquality(b2,b3);
775 }
776
777 report("Get ", failCount);
778 }
779
780
781 private static void testIntersects() {
782 int failCount = 0;
783
784 for (int i=0; i<100; i++) {
785 BitSet b1 = new BitSet(256);
786 BitSet b2 = new BitSet(256);
787
788 // Set some random bits in first set
789 int nextBitToSet = 0;
790 for (int x=0; x<30; x++) {
791 nextBitToSet = generator.nextInt(255);
792 b1.set(nextBitToSet);
793 }
794
795 // Set more random bits in second set
796 for (int x=0; x<30; x++) {
797 nextBitToSet = generator.nextInt(255);
798 b2.set(nextBitToSet);
799 }
800
801 // Make sure they intersect
802 nextBitToSet = generator.nextInt(255);
803 b1.set(nextBitToSet);
804 b2.set(nextBitToSet);
805
806 if (!b1.intersects(b2))
807 failCount++;
808
809 // Remove the common set bits
810 b1.andNot(b2);
811
812 // Make sure they don't intersect
813 if (b1.intersects(b2))
814 failCount++;
815
816 checkSanity(b1, b2);
817 }
818
819 report("Intersects ", failCount);
820 }
821
822 private static void testCardinality() {
823 int failCount = 0;
824
825 for (int i=0; i<100; i++) {
826 BitSet b1 = new BitSet(256);
827
828 // Set a random number of increasing bits
829 int nextBitToSet = 0;
830 int iterations = generator.nextInt(20)+1;
831 for (int x=0; x<iterations; x++) {
832 nextBitToSet += generator.nextInt(20)+1;
833 b1.set(nextBitToSet);
834 }
835
836 if (b1.cardinality() != iterations) {
837 System.out.println("Iterations is "+iterations);
838 System.out.println("Cardinality is "+b1.cardinality());
839 failCount++;
840 }
841
842 checkSanity(b1);
843 }
844
845 report("Cardinality ", failCount);
846 }
847
848 private static void testEmpty() {
849 int failCount = 0;
850
851 BitSet b1 = new BitSet();
852 if (!b1.isEmpty())
853 failCount++;
854
855 int nextBitToSet = 0;
856 int numberOfSetBits = generator.nextInt(100) + 1;
857 int highestPossibleSetBit = generator.nextInt(1000) + 1;
858 for (int x=0; x<numberOfSetBits; x++) {
859 nextBitToSet = generator.nextInt(highestPossibleSetBit);
860 b1.set(nextBitToSet);
861 if (b1.isEmpty())
862 failCount++;
863 b1.clear(nextBitToSet);
864 if (!b1.isEmpty())
865 failCount++;
866 }
867
868 report("Empty ", failCount);
869 }
870
871 private static void testEmpty2() {
872 {BitSet t = new BitSet(); t.set(100); t.clear(3,600); checkEmpty(t);}
873 checkEmpty(new BitSet(0));
874 checkEmpty(new BitSet(342));
875 BitSet s = new BitSet(0);
876 checkEmpty(s);
877 s.clear(92); checkEmpty(s);
878 s.clear(127,127); checkEmpty(s);
879 s.set(127,127); checkEmpty(s);
880 s.set(128,128); checkEmpty(s);
881 BitSet empty = new BitSet();
882 {BitSet t = new BitSet(); t.and (empty); checkEmpty(t);}
883 {BitSet t = new BitSet(); t.or (empty); checkEmpty(t);}
884 {BitSet t = new BitSet(); t.xor (empty); checkEmpty(t);}
885 {BitSet t = new BitSet(); t.andNot(empty); checkEmpty(t);}
886 {BitSet t = new BitSet(); t.and (t); checkEmpty(t);}
887 {BitSet t = new BitSet(); t.or (t); checkEmpty(t);}
888 {BitSet t = new BitSet(); t.xor (t); checkEmpty(t);}
889 {BitSet t = new BitSet(); t.andNot(t); checkEmpty(t);}
890 {BitSet t = new BitSet(); t.and(makeSet(1)); checkEmpty(t);}
891 {BitSet t = new BitSet(); t.and(makeSet(127)); checkEmpty(t);}
892 {BitSet t = new BitSet(); t.and(makeSet(128)); checkEmpty(t);}
893 {BitSet t = new BitSet(); t.flip(7);t.flip(7); checkEmpty(t);}
894 {BitSet t = new BitSet(); checkEmpty(t.get(200,300));}
895 {BitSet t = makeSet(2,5); check(t.get(2,6).equals(makeSet(0,3)),"");}
896 }
897
898 private static void testToString() {
899 check(new BitSet().toString().equals("{}"));
900 check(makeSet(2,3,42,43,234).toString().equals("{2, 3, 42, 43, 234}"));
901
902 final long MB = 1024*1024;
903 if (Runtime.getRuntime().maxMemory() >= 512*MB) {
904 // only run it if we have enough memory
905 try {
906 check(makeSet(Integer.MAX_VALUE-1).toString().equals(
907 "{" + (Integer.MAX_VALUE-1) + "}"));
908 check(makeSet(Integer.MAX_VALUE).toString().equals(
909 "{" + Integer.MAX_VALUE + "}"));
910 check(makeSet(0, 1, Integer.MAX_VALUE-1, Integer.MAX_VALUE).toString().equals(
911 "{0, 1, " + (Integer.MAX_VALUE-1) + ", " + Integer.MAX_VALUE + "}"));
912 } catch (IndexOutOfBoundsException exc) {
913 fail("toString() with indices near MAX_VALUE");
914 }
915 }
916 }
917
918 private static void testLogicalIdentities() {
919 int failCount = 0;
920
921 // Verify that (!b1)|(!b2) == !(b1&b2)
922 for (int i=0; i<50; i++) {
923 // Construct two fairly random bitsets
924 BitSet b1 = new BitSet();
925 BitSet b2 = new BitSet();
926
927 int numberOfSetBits = generator.nextInt(100) + 1;
928 int highestPossibleSetBit = generator.nextInt(1000) + 1;
929
930 for (int x=0; x<numberOfSetBits; x++) {
931 b1.set(generator.nextInt(highestPossibleSetBit));
932 b2.set(generator.nextInt(highestPossibleSetBit));
933 }
934
935 BitSet b3 = (BitSet) b1.clone();
936 BitSet b4 = (BitSet) b2.clone();
937
938 for (int x=0; x<highestPossibleSetBit; x++) {
939 b1.flip(x);
940 b2.flip(x);
941 }
942 b1.or(b2);
943 b3.and(b4);
944 for (int x=0; x<highestPossibleSetBit; x++)
945 b3.flip(x);
946 if (!b1.equals(b3))
947 failCount++;
948 checkSanity(b1, b2, b3, b4);
949 }
950
951 // Verify that (b1&(!b2)|(b2&(!b1) == b1^b2
952 for (int i=0; i<50; i++) {
953 // Construct two fairly random bitsets
954 BitSet b1 = new BitSet();
955 BitSet b2 = new BitSet();
956
957 int numberOfSetBits = generator.nextInt(100) + 1;
958 int highestPossibleSetBit = generator.nextInt(1000) + 1;
959
960 for (int x=0; x<numberOfSetBits; x++) {
961 b1.set(generator.nextInt(highestPossibleSetBit));
962 b2.set(generator.nextInt(highestPossibleSetBit));
963 }
964
965 BitSet b3 = (BitSet) b1.clone();
966 BitSet b4 = (BitSet) b2.clone();
967 BitSet b5 = (BitSet) b1.clone();
968 BitSet b6 = (BitSet) b2.clone();
969
970 for (int x=0; x<highestPossibleSetBit; x++)
971 b2.flip(x);
972 b1.and(b2);
973 for (int x=0; x<highestPossibleSetBit; x++)
974 b3.flip(x);
975 b3.and(b4);
976 b1.or(b3);
977 b5.xor(b6);
978 if (!b1.equals(b5))
979 failCount++;
980 checkSanity(b1, b2, b3, b4, b5, b6);
981 }
982 report("Logical Identities ", failCount);
983 }
984
985 }