001 /* BitSet.java -- A vector of bits.
002 Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc.
003
004 This file is part of GNU Classpath.
005
006 GNU Classpath is free software; you can redistribute it and/or modify
007 it under the terms of the GNU General Public License as published by
008 the Free Software Foundation; either version 2, or (at your option)
009 any later version.
010
011 GNU Classpath is distributed in the hope that it will be useful, but
012 WITHOUT ANY WARRANTY; without even the implied warranty of
013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 General Public License for more details.
015
016 You should have received a copy of the GNU General Public License
017 along with GNU Classpath; see the file COPYING. If not, write to the
018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019 02110-1301 USA.
020
021 Linking this library statically or dynamically with other modules is
022 making a combined work based on this library. Thus, the terms and
023 conditions of the GNU General Public License cover the whole
024 combination.
025
026 As a special exception, the copyright holders of this library give you
027 permission to link this library with independent modules to produce an
028 executable, regardless of the license terms of these independent
029 modules, and to copy and distribute the resulting executable under
030 terms of your choice, provided that you also meet, for each linked
031 independent module, the terms and conditions of the license of that
032 module. An independent module is a module which is not derived from
033 or based on this library. If you modify this library, you may extend
034 this exception to your version of the library, but you are not
035 obligated to do so. If you do not wish to do so, delete this
036 exception statement from your version. */
037
038 package java.util;
039 import java.io.Serializable;
040
041 /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3
042 * hashCode algorithm taken from JDK 1.2 docs.
043 */
044
045 /**
046 * This class can be thought of in two ways. You can see it as a
047 * vector of bits or as a set of non-negative integers. The name
048 * <code>BitSet</code> is a bit misleading.
049 *
050 * It is implemented by a bit vector, but its equally possible to see
051 * it as set of non-negative integer; each integer in the set is
052 * represented by a set bit at the corresponding index. The size of
053 * this structure is determined by the highest integer in the set.
054 *
055 * You can union, intersect and build (symmetric) remainders, by
056 * invoking the logical operations and, or, andNot, resp. xor.
057 *
058 * This implementation is NOT synchronized against concurrent access from
059 * multiple threads. Specifically, if one thread is reading from a bitset
060 * while another thread is simultaneously modifying it, the results are
061 * undefined.
062 *
063 * @author Jochen Hoenicke
064 * @author Tom Tromey (tromey@cygnus.com)
065 * @author Eric Blake (ebb9@email.byu.edu)
066 * @status updated to 1.4
067 */
068 public class BitSet implements Cloneable, Serializable
069 {
070 /**
071 * Compatible with JDK 1.0.
072 */
073 private static final long serialVersionUID = 7997698588986878753L;
074
075 /**
076 * A common mask.
077 */
078 private static final int LONG_MASK = 0x3f;
079
080 /**
081 * The actual bits.
082 * @serial the i'th bit is in bits[i/64] at position i%64 (where position
083 * 0 is the least significant).
084 */
085 private long[] bits;
086
087 /**
088 * Create a new empty bit set. All bits are initially false.
089 */
090 public BitSet()
091 {
092 this(64);
093 }
094
095 /**
096 * Create a new empty bit set, with a given size. This
097 * constructor reserves enough space to represent the integers
098 * from <code>0</code> to <code>nbits-1</code>.
099 *
100 * @param nbits the initial size of the bit set
101 * @throws NegativeArraySizeException if nbits < 0
102 */
103 public BitSet(int nbits)
104 {
105 if (nbits < 0)
106 throw new NegativeArraySizeException();
107
108 int length = nbits >>> 6;
109 if ((nbits & LONG_MASK) != 0)
110 ++length;
111 bits = new long[length];
112 }
113
114 /**
115 * Performs the logical AND operation on this bit set and the
116 * given <code>set</code>. This means it builds the intersection
117 * of the two sets. The result is stored into this bit set.
118 *
119 * @param bs the second bit set
120 * @throws NullPointerException if bs is null
121 */
122 public void and(BitSet bs)
123 {
124 int max = Math.min(bits.length, bs.bits.length);
125 int i;
126 for (i = 0; i < max; ++i)
127 bits[i] &= bs.bits[i];
128 while (i < bits.length)
129 bits[i++] = 0;
130 }
131
132 /**
133 * Performs the logical AND operation on this bit set and the
134 * complement of the given <code>bs</code>. This means it
135 * selects every element in the first set, that isn't in the
136 * second set. The result is stored into this bit set and is
137 * effectively the set difference of the two.
138 *
139 * @param bs the second bit set
140 * @throws NullPointerException if bs is null
141 * @since 1.2
142 */
143 public void andNot(BitSet bs)
144 {
145 int i = Math.min(bits.length, bs.bits.length);
146 while (--i >= 0)
147 bits[i] &= ~bs.bits[i];
148 }
149
150 /**
151 * Returns the number of bits set to true.
152 *
153 * @return the number of true bits
154 * @since 1.4
155 */
156 public int cardinality()
157 {
158 int card = 0;
159 for (int i = bits.length - 1; i >= 0; i--)
160 {
161 long a = bits[i];
162 // Take care of common cases.
163 if (a == 0)
164 continue;
165 if (a == -1)
166 {
167 card += 64;
168 continue;
169 }
170
171 // Successively collapse alternating bit groups into a sum.
172 a = ((a >> 1) & 0x5555555555555555L) + (a & 0x5555555555555555L);
173 a = ((a >> 2) & 0x3333333333333333L) + (a & 0x3333333333333333L);
174 int b = (int) ((a >>> 32) + a);
175 b = ((b >> 4) & 0x0f0f0f0f) + (b & 0x0f0f0f0f);
176 b = ((b >> 8) & 0x00ff00ff) + (b & 0x00ff00ff);
177 card += ((b >> 16) & 0x0000ffff) + (b & 0x0000ffff);
178 }
179 return card;
180 }
181
182 /**
183 * Sets all bits in the set to false.
184 *
185 * @since 1.4
186 */
187 public void clear()
188 {
189 Arrays.fill(bits, 0);
190 }
191
192 /**
193 * Removes the integer <code>pos</code> from this set. That is
194 * the corresponding bit is cleared. If the index is not in the set,
195 * this method does nothing.
196 *
197 * @param pos a non-negative integer
198 * @throws IndexOutOfBoundsException if pos < 0
199 */
200 public void clear(int pos)
201 {
202 int offset = pos >> 6;
203 ensure(offset);
204 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
205 // so we'll just let that be our exception.
206 bits[offset] &= ~(1L << pos);
207 }
208
209 /**
210 * Sets the bits between from (inclusive) and to (exclusive) to false.
211 *
212 * @param from the start range (inclusive)
213 * @param to the end range (exclusive)
214 * @throws IndexOutOfBoundsException if from < 0 || to < 0 ||
215 * from > to
216 * @since 1.4
217 */
218 public void clear(int from, int to)
219 {
220 if (from < 0 || from > to)
221 throw new IndexOutOfBoundsException();
222 if (from == to)
223 return;
224 int lo_offset = from >>> 6;
225 int hi_offset = to >>> 6;
226 ensure(hi_offset);
227 if (lo_offset == hi_offset)
228 {
229 bits[hi_offset] &= ((1L << from) - 1) | (-1L << to);
230 return;
231 }
232
233 bits[lo_offset] &= (1L << from) - 1;
234 bits[hi_offset] &= -1L << to;
235 for (int i = lo_offset + 1; i < hi_offset; i++)
236 bits[i] = 0;
237 }
238
239 /**
240 * Create a clone of this bit set, that is an instance of the same
241 * class and contains the same elements. But it doesn't change when
242 * this bit set changes.
243 *
244 * @return the clone of this object.
245 */
246 public Object clone()
247 {
248 try
249 {
250 BitSet bs = (BitSet) super.clone();
251 bs.bits = (long[]) bits.clone();
252 return bs;
253 }
254 catch (CloneNotSupportedException e)
255 {
256 // Impossible to get here.
257 return null;
258 }
259 }
260
261 /**
262 * Returns true if the <code>obj</code> is a bit set that contains
263 * exactly the same elements as this bit set, otherwise false.
264 *
265 * @param obj the object to compare to
266 * @return true if obj equals this bit set
267 */
268 public boolean equals(Object obj)
269 {
270 if (!(obj instanceof BitSet))
271 return false;
272 BitSet bs = (BitSet) obj;
273 int max = Math.min(bits.length, bs.bits.length);
274 int i;
275 for (i = 0; i < max; ++i)
276 if (bits[i] != bs.bits[i])
277 return false;
278 // If one is larger, check to make sure all extra bits are 0.
279 for (int j = i; j < bits.length; ++j)
280 if (bits[j] != 0)
281 return false;
282 for (int j = i; j < bs.bits.length; ++j)
283 if (bs.bits[j] != 0)
284 return false;
285 return true;
286 }
287
288 /**
289 * Sets the bit at the index to the opposite value.
290 *
291 * @param index the index of the bit
292 * @throws IndexOutOfBoundsException if index is negative
293 * @since 1.4
294 */
295 public void flip(int index)
296 {
297 int offset = index >> 6;
298 ensure(offset);
299 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
300 // so we'll just let that be our exception.
301 bits[offset] ^= 1L << index;
302 }
303
304 /**
305 * Sets a range of bits to the opposite value.
306 *
307 * @param from the low index (inclusive)
308 * @param to the high index (exclusive)
309 * @throws IndexOutOfBoundsException if from > to || from < 0 ||
310 * to < 0
311 * @since 1.4
312 */
313 public void flip(int from, int to)
314 {
315 if (from < 0 || from > to)
316 throw new IndexOutOfBoundsException();
317 if (from == to)
318 return;
319 int lo_offset = from >>> 6;
320 int hi_offset = to >>> 6;
321 ensure(hi_offset);
322 if (lo_offset == hi_offset)
323 {
324 bits[hi_offset] ^= (-1L << from) & ((1L << to) - 1);
325 return;
326 }
327
328 bits[lo_offset] ^= -1L << from;
329 bits[hi_offset] ^= (1L << to) - 1;
330 for (int i = lo_offset + 1; i < hi_offset; i++)
331 bits[i] ^= -1;
332 }
333
334 /**
335 * Returns true if the integer <code>bitIndex</code> is in this bit
336 * set, otherwise false.
337 *
338 * @param pos a non-negative integer
339 * @return the value of the bit at the specified position
340 * @throws IndexOutOfBoundsException if the pos is negative
341 */
342 public boolean get(int pos)
343 {
344 int offset = pos >> 6;
345 if (offset >= bits.length)
346 return false;
347 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
348 // so we'll just let that be our exception.
349 return (bits[offset] & (1L << pos)) != 0;
350 }
351
352 /**
353 * Returns a new <code>BitSet</code> composed of a range of bits from
354 * this one.
355 *
356 * @param from the low index (inclusive)
357 * @param to the high index (exclusive)
358 * @throws IndexOutOfBoundsException if from > to || from < 0 ||
359 * to < 0
360 * @since 1.4
361 */
362 public BitSet get(int from, int to)
363 {
364 if (from < 0 || from > to)
365 throw new IndexOutOfBoundsException();
366 BitSet bs = new BitSet(to - from);
367 int lo_offset = from >>> 6;
368 if (lo_offset >= bits.length || to == from)
369 return bs;
370
371 int lo_bit = from & LONG_MASK;
372 int hi_offset = to >>> 6;
373 if (lo_bit == 0)
374 {
375 int len = Math.min(hi_offset - lo_offset + 1, bits.length - lo_offset);
376 System.arraycopy(bits, lo_offset, bs.bits, 0, len);
377 if (hi_offset < bits.length)
378 bs.bits[hi_offset - lo_offset] &= (1L << to) - 1;
379 return bs;
380 }
381
382 int len = Math.min(hi_offset, bits.length - 1);
383 int reverse = 64 - lo_bit;
384 int i;
385 for (i = 0; lo_offset < len; lo_offset++, i++)
386 bs.bits[i] = ((bits[lo_offset] >>> lo_bit)
387 | (bits[lo_offset + 1] << reverse));
388 if ((to & LONG_MASK) > lo_bit)
389 bs.bits[i++] = bits[lo_offset] >>> lo_bit;
390 if (hi_offset < bits.length)
391 bs.bits[i - 1] &= (1L << (to - from)) - 1;
392 return bs;
393 }
394
395 /**
396 * Returns a hash code value for this bit set. The hash code of
397 * two bit sets containing the same integers is identical. The algorithm
398 * used to compute it is as follows:
399 *
400 * Suppose the bits in the BitSet were to be stored in an array of
401 * long integers called <code>bits</code>, in such a manner that
402 * bit <code>k</code> is set in the BitSet (for non-negative values
403 * of <code>k</code>) if and only if
404 *
405 * <code>((k/64) < bits.length)
406 * && ((bits[k/64] & (1L << (bit % 64))) != 0)
407 * </code>
408 *
409 * Then the following definition of the hashCode method
410 * would be a correct implementation of the actual algorithm:
411 *
412 *
413 <pre>public int hashCode()
414 {
415 long h = 1234;
416 for (int i = bits.length-1; i >= 0; i--)
417 {
418 h ^= bits[i] * (i + 1);
419 }
420
421 return (int)((h >> 32) ^ h);
422 }</pre>
423 *
424 * Note that the hash code values changes, if the set is changed.
425 *
426 * @return the hash code value for this bit set.
427 */
428 public int hashCode()
429 {
430 long h = 1234;
431 for (int i = bits.length; i > 0; )
432 h ^= i * bits[--i];
433 return (int) ((h >> 32) ^ h);
434 }
435
436 /**
437 * Returns true if the specified BitSet and this one share at least one
438 * common true bit.
439 *
440 * @param set the set to check for intersection
441 * @return true if the sets intersect
442 * @throws NullPointerException if set is null
443 * @since 1.4
444 */
445 public boolean intersects(BitSet set)
446 {
447 int i = Math.min(bits.length, set.bits.length);
448 while (--i >= 0)
449 if ((bits[i] & set.bits[i]) != 0)
450 return true;
451 return false;
452 }
453
454 /**
455 * Returns true if this set contains no true bits.
456 *
457 * @return true if all bits are false
458 * @since 1.4
459 */
460 public boolean isEmpty()
461 {
462 for (int i = bits.length - 1; i >= 0; i--)
463 if (bits[i] != 0)
464 return false;
465 return true;
466 }
467
468 /**
469 * Returns the logical number of bits actually used by this bit
470 * set. It returns the index of the highest set bit plus one.
471 * Note that this method doesn't return the number of set bits.
472 *
473 * @return the index of the highest set bit plus one.
474 */
475 public int length()
476 {
477 // Set i to highest index that contains a non-zero value.
478 int i;
479 for (i = bits.length - 1; i >= 0 && bits[i] == 0; --i)
480 ;
481
482 // if i < 0 all bits are cleared.
483 if (i < 0)
484 return 0;
485
486 // Now determine the exact length.
487 long b = bits[i];
488 int len = (i + 1) * 64;
489 // b >= 0 checks if the highest bit is zero.
490 while (b >= 0)
491 {
492 --len;
493 b <<= 1;
494 }
495
496 return len;
497 }
498
499 /**
500 * Returns the index of the next false bit, from the specified bit
501 * (inclusive).
502 *
503 * @param from the start location
504 * @return the first false bit
505 * @throws IndexOutOfBoundsException if from is negative
506 * @since 1.4
507 */
508 public int nextClearBit(int from)
509 {
510 int offset = from >> 6;
511 long mask = 1L << from;
512 while (offset < bits.length)
513 {
514 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
515 // so we'll just let that be our exception.
516 long h = bits[offset];
517 do
518 {
519 if ((h & mask) == 0)
520 return from;
521 mask <<= 1;
522 from++;
523 }
524 while (mask != 0);
525 mask = 1;
526 offset++;
527 }
528 return from;
529 }
530
531 /**
532 * Returns the index of the next true bit, from the specified bit
533 * (inclusive). If there is none, -1 is returned. You can iterate over
534 * all true bits with this loop:<br>
535 *
536 <pre>for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1))
537 {
538 // operate on i here
539 }</pre>
540 *
541 * @param from the start location
542 * @return the first true bit, or -1
543 * @throws IndexOutOfBoundsException if from is negative
544 * @since 1.4
545 */
546 public int nextSetBit(int from)
547 {
548 int offset = from >> 6;
549 long mask = 1L << from;
550 while (offset < bits.length)
551 {
552 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
553 // so we'll just let that be our exception.
554 long h = bits[offset];
555 do
556 {
557 if ((h & mask) != 0)
558 return from;
559 mask <<= 1;
560 from++;
561 }
562 while (mask != 0);
563 mask = 1;
564 offset++;
565 }
566 return -1;
567 }
568
569 /**
570 * Performs the logical OR operation on this bit set and the
571 * given <code>set</code>. This means it builds the union
572 * of the two sets. The result is stored into this bit set, which
573 * grows as necessary.
574 *
575 * @param bs the second bit set
576 * @throws NullPointerException if bs is null
577 */
578 public void or(BitSet bs)
579 {
580 ensure(bs.bits.length - 1);
581 for (int i = bs.bits.length - 1; i >= 0; i--)
582 bits[i] |= bs.bits[i];
583 }
584
585 /**
586 * Add the integer <code>bitIndex</code> to this set. That is
587 * the corresponding bit is set to true. If the index was already in
588 * the set, this method does nothing. The size of this structure
589 * is automatically increased as necessary.
590 *
591 * @param pos a non-negative integer.
592 * @throws IndexOutOfBoundsException if pos is negative
593 */
594 public void set(int pos)
595 {
596 int offset = pos >> 6;
597 ensure(offset);
598 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
599 // so we'll just let that be our exception.
600 bits[offset] |= 1L << pos;
601 }
602
603 /**
604 * Sets the bit at the given index to the specified value. The size of
605 * this structure is automatically increased as necessary.
606 *
607 * @param index the position to set
608 * @param value the value to set it to
609 * @throws IndexOutOfBoundsException if index is negative
610 * @since 1.4
611 */
612 public void set(int index, boolean value)
613 {
614 if (value)
615 set(index);
616 else
617 clear(index);
618 }
619
620 /**
621 * Sets the bits between from (inclusive) and to (exclusive) to true.
622 *
623 * @param from the start range (inclusive)
624 * @param to the end range (exclusive)
625 * @throws IndexOutOfBoundsException if from < 0 || from > to ||
626 * to < 0
627 * @since 1.4
628 */
629 public void set(int from, int to)
630 {
631 if (from < 0 || from > to)
632 throw new IndexOutOfBoundsException();
633 if (from == to)
634 return;
635 int lo_offset = from >>> 6;
636 int hi_offset = to >>> 6;
637 ensure(hi_offset);
638 if (lo_offset == hi_offset)
639 {
640 bits[hi_offset] |= (-1L << from) & ((1L << to) - 1);
641 return;
642 }
643
644 bits[lo_offset] |= -1L << from;
645 bits[hi_offset] |= (1L << to) - 1;
646 for (int i = lo_offset + 1; i < hi_offset; i++)
647 bits[i] = -1;
648 }
649
650 /**
651 * Sets the bits between from (inclusive) and to (exclusive) to the
652 * specified value.
653 *
654 * @param from the start range (inclusive)
655 * @param to the end range (exclusive)
656 * @param value the value to set it to
657 * @throws IndexOutOfBoundsException if from < 0 || from > to ||
658 * to < 0
659 * @since 1.4
660 */
661 public void set(int from, int to, boolean value)
662 {
663 if (value)
664 set(from, to);
665 else
666 clear(from, to);
667 }
668
669 /**
670 * Returns the number of bits actually used by this bit set. Note
671 * that this method doesn't return the number of set bits, and that
672 * future requests for larger bits will make this automatically grow.
673 *
674 * @return the number of bits currently used.
675 */
676 public int size()
677 {
678 return bits.length * 64;
679 }
680
681 /**
682 * Returns the string representation of this bit set. This
683 * consists of a comma separated list of the integers in this set
684 * surrounded by curly braces. There is a space after each comma.
685 * A sample string is thus "{1, 3, 53}".
686 * @return the string representation.
687 */
688 public String toString()
689 {
690 StringBuffer r = new StringBuffer("{");
691 boolean first = true;
692 for (int i = 0; i < bits.length; ++i)
693 {
694 long bit = 1;
695 long word = bits[i];
696 if (word == 0)
697 continue;
698 for (int j = 0; j < 64; ++j)
699 {
700 if ((word & bit) != 0)
701 {
702 if (! first)
703 r.append(", ");
704 r.append(64 * i + j);
705 first = false;
706 }
707 bit <<= 1;
708 }
709 }
710 return r.append("}").toString();
711 }
712
713 /**
714 * Performs the logical XOR operation on this bit set and the
715 * given <code>set</code>. This means it builds the symmetric
716 * remainder of the two sets (the elements that are in one set,
717 * but not in the other). The result is stored into this bit set,
718 * which grows as necessary.
719 *
720 * @param bs the second bit set
721 * @throws NullPointerException if bs is null
722 */
723 public void xor(BitSet bs)
724 {
725 ensure(bs.bits.length - 1);
726 for (int i = bs.bits.length - 1; i >= 0; i--)
727 bits[i] ^= bs.bits[i];
728 }
729
730 /**
731 * Make sure the vector is big enough.
732 *
733 * @param lastElt the size needed for the bits array
734 */
735 private void ensure(int lastElt)
736 {
737 if (lastElt >= bits.length)
738 {
739 long[] nd = new long[lastElt + 1];
740 System.arraycopy(bits, 0, nd, 0, bits.length);
741 bits = nd;
742 }
743 }
744
745 // This is used by EnumSet for efficiency.
746 final boolean containsAll(BitSet other)
747 {
748 for (int i = other.bits.length - 1; i >= 0; i--)
749 {
750 if ((bits[i] & other.bits[i]) != other.bits[i])
751 return false;
752 }
753 return true;
754 }
755 }