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