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