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