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