• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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