0001: /*
0002: * @(#)BitSet.java 1.53 06/10/10
0003: *
0004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
0005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License version
0009: * 2 only, as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful, but
0012: * WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0014: * General Public License version 2 for more details (a copy is
0015: * included at /legal/license.txt).
0016: *
0017: * You should have received a copy of the GNU General Public License
0018: * version 2 along with this work; if not, write to the Free Software
0019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
0020: * 02110-1301 USA
0021: *
0022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
0023: * Clara, CA 95054 or visit www.sun.com if you need additional
0024: * information or have any questions.
0025: *
0026: */
0027:
0028: package java.util;
0029:
0030: import java.io.*;
0031:
0032: /**
0033: * This class implements a vector of bits that grows as needed. Each
0034: * component of the bit set has a <code>boolean</code> value. The
0035: * bits of a <code>BitSet</code> are indexed by nonnegative integers.
0036: * Individual indexed bits can be examined, set, or cleared. One
0037: * <code>BitSet</code> may be used to modify the contents of another
0038: * <code>BitSet</code> through logical AND, logical inclusive OR, and
0039: * logical exclusive OR operations.
0040: * <p>
0041: * By default, all bits in the set initially have the value
0042: * <code>false</code>.
0043: * <p>
0044: * Every bit set has a current size, which is the number of bits
0045: * of space currently in use by the bit set. Note that the size is
0046: * related to the implementation of a bit set, so it may change with
0047: * implementation. The length of a bit set relates to logical length
0048: * of a bit set and is defined independently of implementation.
0049: * <p>
0050: * Unless otherwise noted, passing a null parameter to any of the
0051: * methods in a <code>BitSet</code> will result in a
0052: * <code>NullPointerException</code>.
0053: *
0054: * A <code>BitSet</code> is not safe for multithreaded use without
0055: * external synchronization.
0056: *
0057: * @author Arthur van Hoff
0058: * @author Michael McCloskey
0059: * @version 1.46, 02/02/00
0060: * @since JDK1.0
0061: */
0062: public class BitSet implements Cloneable, java.io.Serializable {
0063: /*
0064: * BitSets are packed into arrays of "units." Currently a unit is a long,
0065: * which consists of 64 bits, requiring 6 address bits. The choice of unit
0066: * is determined purely by performance concerns.
0067: */
0068: private final static int ADDRESS_BITS_PER_UNIT = 6;
0069: private final static int BITS_PER_UNIT = 1 << ADDRESS_BITS_PER_UNIT;
0070: private final static int BIT_INDEX_MASK = BITS_PER_UNIT - 1;
0071:
0072: /* Used to shift left or right for a partial word mask */
0073: private static final long WORD_MASK = 0xffffffffffffffffL;
0074:
0075: /**
0076: * The bits in this BitSet. The ith bit is stored in bits[i/64] at
0077: * bit position i % 64 (where bit position 0 refers to the least
0078: * significant bit and 63 refers to the most significant bit).
0079: * INVARIANT: The words in bits[] above unitInUse-1 are zero.
0080: *
0081: * @serial
0082: */
0083: private long bits[]; // this should be called unit[]
0084:
0085: /**
0086: * The number of units in the logical size of this BitSet.
0087: * INVARIANT: unitsInUse is nonnegative.
0088: * INVARIANT: bits[unitsInUse-1] is nonzero unless unitsInUse is zero.
0089: */
0090: private transient int unitsInUse = 0;
0091:
0092: /* use serialVersionUID from JDK 1.0.2 for interoperability */
0093: private static final long serialVersionUID = 7997698588986878753L;
0094:
0095: /**
0096: * Given a bit index return unit index containing it.
0097: */
0098: private static int unitIndex(int bitIndex) {
0099: return bitIndex >> ADDRESS_BITS_PER_UNIT;
0100: }
0101:
0102: /**
0103: * Given a bit index, return a unit that masks that bit in its unit.
0104: */
0105: private static long bit(int bitIndex) {
0106: return 1L << (bitIndex & BIT_INDEX_MASK);
0107: }
0108:
0109: /**
0110: * Set the field unitsInUse with the logical size in units of the bit
0111: * set. WARNING:This function assumes that the number of units actually
0112: * in use is less than or equal to the current value of unitsInUse!
0113: */
0114: private void recalculateUnitsInUse() {
0115: // Traverse the bitset until a used unit is found
0116: int i;
0117: for (i = unitsInUse - 1; i >= 0; i--)
0118: if (bits[i] != 0)
0119: break;
0120:
0121: unitsInUse = i + 1; // The new logical size
0122: }
0123:
0124: /**
0125: * Creates a new bit set. All bits are initially <code>false</code>.
0126: */
0127: public BitSet() {
0128: this (BITS_PER_UNIT);
0129: }
0130:
0131: /**
0132: * Creates a bit set whose initial size is large enough to explicitly
0133: * represent bits with indices in the range <code>0</code> through
0134: * <code>nbits-1</code>. All bits are initially <code>false</code>.
0135: *
0136: * @param nbits the initial size of the bit set.
0137: * @exception NegativeArraySizeException if the specified initial size
0138: * is negative.
0139: */
0140: public BitSet(int nbits) {
0141: // nbits can't be negative; size 0 is OK
0142: if (nbits < 0)
0143: throw new NegativeArraySizeException("nbits < 0: " + nbits);
0144:
0145: bits = new long[(unitIndex(nbits - 1) + 1)];
0146: }
0147:
0148: /**
0149: * Ensures that the BitSet can hold enough units.
0150: * @param unitsRequired the minimum acceptable number of units.
0151: */
0152: private void ensureCapacity(int unitsRequired) {
0153: if (bits.length < unitsRequired) {
0154: // Allocate larger of doubled size or required size
0155: int request = Math.max(2 * bits.length, unitsRequired);
0156: long newBits[] = new long[request];
0157: System.arraycopy(bits, 0, newBits, 0, unitsInUse);
0158: bits = newBits;
0159: }
0160: }
0161:
0162: /**
0163: * Sets the bit at the specified index to to the complement of its
0164: * current value.
0165: *
0166: * @param bitIndex the index of the bit to flip.
0167: * @exception IndexOutOfBoundsException if the specified index is negative.
0168: * @since 1.4
0169: */
0170: public void flip(int bitIndex) {
0171: if (bitIndex < 0)
0172: throw new IndexOutOfBoundsException("bitIndex < 0: "
0173: + bitIndex);
0174:
0175: int unitIndex = unitIndex(bitIndex);
0176: int unitsRequired = unitIndex + 1;
0177:
0178: if (unitsInUse < unitsRequired) {
0179: ensureCapacity(unitsRequired);
0180: bits[unitIndex] ^= bit(bitIndex);
0181: unitsInUse = unitsRequired;
0182: } else {
0183: bits[unitIndex] ^= bit(bitIndex);
0184: if (bits[unitsInUse - 1] == 0)
0185: recalculateUnitsInUse();
0186: }
0187: }
0188:
0189: /**
0190: * Sets each bit from the specified fromIndex(inclusive) to the
0191: * specified toIndex(exclusive) to the complement of its current
0192: * value.
0193: *
0194: * @param fromIndex index of the first bit to flip.
0195: * @param toIndex index after the last bit to flip.
0196: * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
0197: * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
0198: * larger than <tt>toIndex</tt>.
0199: * @since 1.4
0200: */
0201: public void flip(int fromIndex, int toIndex) {
0202: if (fromIndex < 0)
0203: throw new IndexOutOfBoundsException("fromIndex < 0: "
0204: + fromIndex);
0205: if (toIndex < 0)
0206: throw new IndexOutOfBoundsException("toIndex < 0: "
0207: + toIndex);
0208: if (fromIndex > toIndex)
0209: throw new IndexOutOfBoundsException("fromIndex: "
0210: + fromIndex + " > toIndex: " + toIndex);
0211:
0212: // Increase capacity if necessary
0213: int endUnitIndex = unitIndex(toIndex);
0214: int unitsRequired = endUnitIndex + 1;
0215:
0216: if (unitsInUse < unitsRequired) {
0217: ensureCapacity(unitsRequired);
0218: unitsInUse = unitsRequired;
0219: }
0220:
0221: int startUnitIndex = unitIndex(fromIndex);
0222: long bitMask = 0;
0223: if (startUnitIndex == endUnitIndex) {
0224: // Case 1: One word
0225: bitMask = (1L << (toIndex & BIT_INDEX_MASK))
0226: - (1L << (fromIndex & BIT_INDEX_MASK));
0227: bits[startUnitIndex] ^= bitMask;
0228: if (bits[unitsInUse - 1] == 0)
0229: recalculateUnitsInUse();
0230: return;
0231: }
0232:
0233: // Case 2: Multiple words
0234: // Handle first word
0235: bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
0236: bits[startUnitIndex] ^= bitMask;
0237:
0238: // Handle intermediate words, if any
0239: if (endUnitIndex - startUnitIndex > 1) {
0240: for (int i = startUnitIndex + 1; i < endUnitIndex; i++)
0241: bits[i] ^= WORD_MASK;
0242: }
0243:
0244: // Handle last word
0245: bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
0246: bits[endUnitIndex] ^= bitMask;
0247:
0248: // Check to see if we reduced size
0249: if (bits[unitsInUse - 1] == 0)
0250: recalculateUnitsInUse();
0251: }
0252:
0253: /**
0254: * Returns a long that has all bits that are less significant
0255: * than the specified index set to 1. All other bits are 0.
0256: */
0257: private static long bitsRightOf(int x) {
0258: return (x == 0 ? 0 : WORD_MASK >>> (64 - x));
0259: }
0260:
0261: /**
0262: * Returns a long that has all the bits that are more significant
0263: * than or equal to the specified index set to 1. All other bits are 0.
0264: */
0265: private static long bitsLeftOf(int x) {
0266: return WORD_MASK << x;
0267: }
0268:
0269: /**
0270: * Sets the bit at the specified index to <code>true</code>.
0271: *
0272: * @param bitIndex a bit index.
0273: * @exception IndexOutOfBoundsException if the specified index is negative.
0274: * @since JDK1.0
0275: */
0276: public void set(int bitIndex) {
0277: if (bitIndex < 0)
0278: throw new IndexOutOfBoundsException("bitIndex < 0: "
0279: + bitIndex);
0280:
0281: int unitIndex = unitIndex(bitIndex);
0282: int unitsRequired = unitIndex + 1;
0283:
0284: if (unitsInUse < unitsRequired) {
0285: ensureCapacity(unitsRequired);
0286: bits[unitIndex] |= bit(bitIndex);
0287: unitsInUse = unitsRequired;
0288: } else {
0289: bits[unitIndex] |= bit(bitIndex);
0290: }
0291: }
0292:
0293: /**
0294: * Sets the bit at the specified index to the specified value.
0295: *
0296: * @param bitIndex a bit index.
0297: * @param value a boolean value to set.
0298: * @exception IndexOutOfBoundsException if the specified index is negative.
0299: * @since 1.4
0300: */
0301: public void set(int bitIndex, boolean value) {
0302: if (value)
0303: set(bitIndex);
0304: else
0305: clear(bitIndex);
0306: }
0307:
0308: /**
0309: * Sets the bits from the specified fromIndex(inclusive) to the
0310: * specified toIndex(exclusive) to <code>true</code>.
0311: *
0312: * @param fromIndex index of the first bit to be set.
0313: * @param toIndex index after the last bit to be set.
0314: * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
0315: * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
0316: * larger than <tt>toIndex</tt>.
0317: * @since 1.4
0318: */
0319: public void set(int fromIndex, int toIndex) {
0320: if (fromIndex < 0)
0321: throw new IndexOutOfBoundsException("fromIndex < 0: "
0322: + fromIndex);
0323: if (toIndex < 0)
0324: throw new IndexOutOfBoundsException("toIndex < 0: "
0325: + toIndex);
0326: if (fromIndex > toIndex)
0327: throw new IndexOutOfBoundsException("fromIndex: "
0328: + fromIndex + " > toIndex: " + toIndex);
0329:
0330: // Increase capacity if necessary
0331: int endUnitIndex = unitIndex(toIndex);
0332: int unitsRequired = endUnitIndex + 1;
0333:
0334: if (unitsInUse < unitsRequired) {
0335: ensureCapacity(unitsRequired);
0336: unitsInUse = unitsRequired;
0337: }
0338:
0339: int startUnitIndex = unitIndex(fromIndex);
0340: long bitMask = 0;
0341: if (startUnitIndex == endUnitIndex) {
0342: // Case 1: One word
0343: bitMask = (1L << (toIndex & BIT_INDEX_MASK))
0344: - (1L << (fromIndex & BIT_INDEX_MASK));
0345: bits[startUnitIndex] |= bitMask;
0346: return;
0347: }
0348:
0349: // Case 2: Multiple words
0350: // Handle first word
0351: bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
0352: bits[startUnitIndex] |= bitMask;
0353:
0354: // Handle intermediate words, if any
0355: if (endUnitIndex - startUnitIndex > 1) {
0356: for (int i = startUnitIndex + 1; i < endUnitIndex; i++)
0357: bits[i] |= WORD_MASK;
0358: }
0359:
0360: // Handle last word
0361: bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
0362: bits[endUnitIndex] |= bitMask;
0363: }
0364:
0365: /**
0366: * Sets the bits from the specified fromIndex(inclusive) to the
0367: * specified toIndex(exclusive) to the specified value.
0368: *
0369: * @param fromIndex index of the first bit to be set.
0370: * @param toIndex index after the last bit to be set
0371: * @param value value to set the selected bits to
0372: * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
0373: * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
0374: * larger than <tt>toIndex</tt>.
0375: * @since 1.4
0376: */
0377: public void set(int fromIndex, int toIndex, boolean value) {
0378: if (value)
0379: set(fromIndex, toIndex);
0380: else
0381: clear(fromIndex, toIndex);
0382: }
0383:
0384: /**
0385: * Sets the bit specified by the index to <code>false</code>.
0386: *
0387: * @param bitIndex the index of the bit to be cleared.
0388: * @exception IndexOutOfBoundsException if the specified index is negative.
0389: * @since JDK1.0
0390: */
0391: public void clear(int bitIndex) {
0392: if (bitIndex < 0)
0393: throw new IndexOutOfBoundsException("bitIndex < 0: "
0394: + bitIndex);
0395:
0396: int unitIndex = unitIndex(bitIndex);
0397: if (unitIndex >= unitsInUse)
0398: return;
0399:
0400: bits[unitIndex] &= ~bit(bitIndex);
0401: if (bits[unitsInUse - 1] == 0)
0402: recalculateUnitsInUse();
0403: }
0404:
0405: /**
0406: * Sets the bits from the specified fromIndex(inclusive) to the
0407: * specified toIndex(exclusive) to <code>false</code>.
0408: *
0409: * @param fromIndex index of the first bit to be cleared.
0410: * @param toIndex index after the last bit to be cleared.
0411: * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
0412: * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
0413: * larger than <tt>toIndex</tt>.
0414: * @since 1.4
0415: */
0416: public void clear(int fromIndex, int toIndex) {
0417: if (fromIndex < 0)
0418: throw new IndexOutOfBoundsException("fromIndex < 0: "
0419: + fromIndex);
0420: if (toIndex < 0)
0421: throw new IndexOutOfBoundsException("toIndex < 0: "
0422: + toIndex);
0423: if (fromIndex > toIndex)
0424: throw new IndexOutOfBoundsException("fromIndex: "
0425: + fromIndex + " > toIndex: " + toIndex);
0426:
0427: int startUnitIndex = unitIndex(fromIndex);
0428: if (startUnitIndex >= unitsInUse)
0429: return;
0430: int endUnitIndex = unitIndex(toIndex);
0431:
0432: long bitMask = 0;
0433: if (startUnitIndex == endUnitIndex) {
0434: // Case 1: One word
0435: bitMask = (1L << (toIndex & BIT_INDEX_MASK))
0436: - (1L << (fromIndex & BIT_INDEX_MASK));
0437: bits[startUnitIndex] &= ~bitMask;
0438: if (bits[unitsInUse - 1] == 0)
0439: recalculateUnitsInUse();
0440: return;
0441: }
0442:
0443: // Case 2: Multiple words
0444: // Handle first word
0445: bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
0446: bits[startUnitIndex] &= ~bitMask;
0447:
0448: // Handle intermediate words, if any
0449: if (endUnitIndex - startUnitIndex > 1) {
0450: for (int i = startUnitIndex + 1; i < endUnitIndex; i++) {
0451: if (i < unitsInUse)
0452: bits[i] = 0;
0453: }
0454: }
0455:
0456: // Handle last word
0457: if (endUnitIndex < unitsInUse) {
0458: bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
0459: bits[endUnitIndex] &= ~bitMask;
0460: }
0461:
0462: if (bits[unitsInUse - 1] == 0)
0463: recalculateUnitsInUse();
0464: }
0465:
0466: /**
0467: * Sets all of the bits in this BitSet to <code>false</code>.
0468: *
0469: * @since 1.4
0470: */
0471: public void clear() {
0472: while (unitsInUse > 0)
0473: bits[--unitsInUse] = 0;
0474: }
0475:
0476: /**
0477: * Returns the value of the bit with the specified index. The value
0478: * is <code>true</code> if the bit with the index <code>bitIndex</code>
0479: * is currently set in this <code>BitSet</code>; otherwise, the result
0480: * is <code>false</code>.
0481: *
0482: * @param bitIndex the bit index.
0483: * @return the value of the bit with the specified index.
0484: * @exception IndexOutOfBoundsException if the specified index is negative.
0485: */
0486: public boolean get(int bitIndex) {
0487: if (bitIndex < 0)
0488: throw new IndexOutOfBoundsException("bitIndex < 0: "
0489: + bitIndex);
0490:
0491: boolean result = false;
0492: int unitIndex = unitIndex(bitIndex);
0493: if (unitIndex < unitsInUse)
0494: result = ((bits[unitIndex] & bit(bitIndex)) != 0);
0495:
0496: return result;
0497: }
0498:
0499: /**
0500: * Returns a new <tt>BitSet</tt> composed of bits from this <tt>BitSet</tt>
0501: * from <tt>fromIndex</tt>(inclusive) to <tt>toIndex</tt>(exclusive).
0502: *
0503: * @param fromIndex index of the first bit to include.
0504: * @param toIndex index after the last bit to include.
0505: * @return a new <tt>BitSet</tt> from a range of this <tt>BitSet</tt>.
0506: * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
0507: * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
0508: * larger than <tt>toIndex</tt>.
0509: * @since 1.4
0510: */
0511: public BitSet get(int fromIndex, int toIndex) {
0512: if (fromIndex < 0)
0513: throw new IndexOutOfBoundsException("fromIndex < 0: "
0514: + fromIndex);
0515: if (toIndex < 0)
0516: throw new IndexOutOfBoundsException("toIndex < 0: "
0517: + toIndex);
0518: if (fromIndex > toIndex)
0519: throw new IndexOutOfBoundsException("fromIndex: "
0520: + fromIndex + " > toIndex: " + toIndex);
0521:
0522: // If no set bits in range return empty bitset
0523: if (length() <= fromIndex || fromIndex == toIndex)
0524: return new BitSet(0);
0525:
0526: // An optimization
0527: if (length() < toIndex)
0528: toIndex = length();
0529:
0530: BitSet result = new BitSet(toIndex - fromIndex);
0531: int startBitIndex = fromIndex & BIT_INDEX_MASK;
0532: int endBitIndex = toIndex & BIT_INDEX_MASK;
0533: int targetWords = (toIndex - fromIndex + 63) / 64;
0534: int sourceWords = unitIndex(toIndex) - unitIndex(fromIndex) + 1;
0535: int inverseIndex = 64 - startBitIndex;
0536: int targetIndex = 0;
0537: int sourceIndex = unitIndex(fromIndex);
0538:
0539: // Process all words but the last word
0540: while (targetIndex < targetWords - 1)
0541: result.bits[targetIndex++] = (bits[sourceIndex++] >>> startBitIndex)
0542: | ((inverseIndex == 64) ? 0
0543: : bits[sourceIndex] << inverseIndex);
0544:
0545: // Process the last word
0546: result.bits[targetIndex] = (sourceWords == targetWords ? (bits[sourceIndex] & bitsRightOf(endBitIndex)) >>> startBitIndex
0547: : (bits[sourceIndex++] >>> startBitIndex)
0548: | ((inverseIndex == 64) ? 0
0549: : (getBits(sourceIndex) & bitsRightOf(endBitIndex)) << inverseIndex));
0550:
0551: // Set unitsInUse correctly
0552: result.unitsInUse = targetWords;
0553: result.recalculateUnitsInUse();
0554: return result;
0555: }
0556:
0557: /**
0558: * Returns the unit of this bitset at index j as if this bitset had an
0559: * infinite amount of storage.
0560: */
0561: private long getBits(int j) {
0562: return (j < unitsInUse) ? bits[j] : 0;
0563: }
0564:
0565: /**
0566: * Returns the index of the first bit that is set to <code>true</code>
0567: * that occurs on or after the specified starting index. If no such
0568: * bit exists then -1 is returned.
0569: *
0570: * To iterate over the <code>true</code> bits in a <code>BitSet</code>,
0571: * use the following loop:
0572: *
0573: * for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) {
0574: * // operate on index i here
0575: * }
0576: *
0577: * @param fromIndex the index to start checking from (inclusive).
0578: * @return the index of the next set bit.
0579: * @throws IndexOutOfBoundsException if the specified index is negative.
0580: * @since 1.4
0581: */
0582: public int nextSetBit(int fromIndex) {
0583: if (fromIndex < 0)
0584: throw new IndexOutOfBoundsException("fromIndex < 0: "
0585: + fromIndex);
0586: int u = unitIndex(fromIndex);
0587: if (u >= unitsInUse)
0588: return -1;
0589: int testIndex = (fromIndex & BIT_INDEX_MASK);
0590: long unit = bits[u] >> testIndex;
0591:
0592: if (unit == 0)
0593: testIndex = 0;
0594:
0595: while ((unit == 0) && (u < unitsInUse - 1))
0596: unit = bits[++u];
0597:
0598: if (unit == 0)
0599: return -1;
0600:
0601: testIndex += trailingZeroCnt(unit);
0602: return ((u * BITS_PER_UNIT) + testIndex);
0603: }
0604:
0605: private static int trailingZeroCnt(long val) {
0606: // Loop unrolled for performance
0607: int byteVal = (int) val & 0xff;
0608: if (byteVal != 0)
0609: return trailingZeroTable[byteVal];
0610:
0611: byteVal = (int) (val >>> 8) & 0xff;
0612: if (byteVal != 0)
0613: return trailingZeroTable[byteVal] + 8;
0614:
0615: byteVal = (int) (val >>> 16) & 0xff;
0616: if (byteVal != 0)
0617: return trailingZeroTable[byteVal] + 16;
0618:
0619: byteVal = (int) (val >>> 24) & 0xff;
0620: if (byteVal != 0)
0621: return trailingZeroTable[byteVal] + 24;
0622:
0623: byteVal = (int) (val >>> 32) & 0xff;
0624: if (byteVal != 0)
0625: return trailingZeroTable[byteVal] + 32;
0626:
0627: byteVal = (int) (val >>> 40) & 0xff;
0628: if (byteVal != 0)
0629: return trailingZeroTable[byteVal] + 40;
0630:
0631: byteVal = (int) (val >>> 48) & 0xff;
0632: if (byteVal != 0)
0633: return trailingZeroTable[byteVal] + 48;
0634:
0635: byteVal = (int) (val >>> 56) & 0xff;
0636: return trailingZeroTable[byteVal] + 56;
0637: }
0638:
0639: /*
0640: * trailingZeroTable[i] is the number of trailing zero bits in the binary
0641: * representaion of i.
0642: */
0643: private final static byte trailingZeroTable[] = { -25, 0, 1, 0, 2,
0644: 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,
0645: 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,
0646: 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
0647: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,
0648: 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3,
0649: 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,
0650: 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0651: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2,
0652: 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,
0653: 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,
0654: 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
0655: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,
0656: 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 };
0657:
0658: /**
0659: * Returns the index of the first bit that is set to <code>false</code>
0660: * that occurs on or after the specified starting index.
0661: *
0662: * @param fromIndex the index to start checking from (inclusive).
0663: * @return the index of the next clear bit.
0664: * @throws IndexOutOfBoundsException if the specified index is negative.
0665: * @since 1.4
0666: */
0667: public int nextClearBit(int fromIndex) {
0668: if (fromIndex < 0)
0669: throw new IndexOutOfBoundsException("fromIndex < 0: "
0670: + fromIndex);
0671:
0672: int u = unitIndex(fromIndex);
0673: if (u >= unitsInUse)
0674: return fromIndex;
0675: int testIndex = (fromIndex & BIT_INDEX_MASK);
0676: long unit = bits[u] >> testIndex;
0677:
0678: if (unit == (WORD_MASK >> testIndex))
0679: testIndex = 0;
0680:
0681: while ((unit == WORD_MASK) && (u < unitsInUse - 1))
0682: unit = bits[++u];
0683:
0684: if (unit == WORD_MASK)
0685: return length();
0686:
0687: if (unit == 0)
0688: return u * BITS_PER_UNIT + testIndex;
0689:
0690: testIndex += trailingZeroCnt(~unit);
0691: return ((u * BITS_PER_UNIT) + testIndex);
0692: }
0693:
0694: /**
0695: * Returns the "logical size" of this <code>BitSet</code>: the index of
0696: * the highest set bit in the <code>BitSet</code> plus one. Returns zero
0697: * if the <code>BitSet</code> contains no set bits.
0698: *
0699: * @return the logical size of this <code>BitSet</code>.
0700: * @since 1.2
0701: */
0702: public int length() {
0703: if (unitsInUse == 0)
0704: return 0;
0705:
0706: long highestUnit = bits[unitsInUse - 1];
0707: int highPart = (int) (highestUnit >>> 32);
0708: return 64
0709: * (unitsInUse - 1)
0710: + (highPart == 0 ? bitLen((int) highestUnit)
0711: : 32 + bitLen((int) highPart));
0712: }
0713:
0714: /**
0715: * bitLen(val) is the number of bits in val.
0716: */
0717: private static int bitLen(int w) {
0718: // Binary search - decision tree (5 tests, rarely 6)
0719: return (w < 1 << 15 ? (w < 1 << 7 ? (w < 1 << 3 ? (w < 1 << 1 ? (w < 1 << 0 ? (w < 0 ? 32
0720: : 0)
0721: : 1)
0722: : (w < 1 << 2 ? 2 : 3))
0723: : (w < 1 << 5 ? (w < 1 << 4 ? 4 : 5) : (w < 1 << 6 ? 6
0724: : 7)))
0725: : (w < 1 << 11 ? (w < 1 << 9 ? (w < 1 << 8 ? 8 : 9)
0726: : (w < 1 << 10 ? 10 : 11))
0727: : (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13)
0728: : (w < 1 << 14 ? 14 : 15))))
0729: : (w < 1 << 23 ? (w < 1 << 19 ? (w < 1 << 17 ? (w < 1 << 16 ? 16
0730: : 17)
0731: : (w < 1 << 18 ? 18 : 19))
0732: : (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21)
0733: : (w < 1 << 22 ? 22 : 23)))
0734: : (w < 1 << 27 ? (w < 1 << 25 ? (w < 1 << 24 ? 24
0735: : 25)
0736: : (w < 1 << 26 ? 26 : 27))
0737: : (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29)
0738: : (w < 1 << 30 ? 30 : 31)))));
0739: }
0740:
0741: /**
0742: * Returns true if this <code>BitSet</code> contains no bits that are set
0743: * to <code>true</code>.
0744: *
0745: * @return boolean indicating whether this <code>BitSet</code> is empty.
0746: * @since 1.4
0747: */
0748: public boolean isEmpty() {
0749: return (unitsInUse == 0);
0750: }
0751:
0752: /**
0753: * Returns true if the specified <code>BitSet</code> has any bits set to
0754: * <code>true</code> that are also set to <code>true</code> in this
0755: * <code>BitSet</code>.
0756: *
0757: * @param set <code>BitSet</code> to intersect with
0758: * @return boolean indicating whether this <code>BitSet</code> intersects
0759: * the specified <code>BitSet</code>.
0760: * @since 1.4
0761: */
0762: public boolean intersects(BitSet set) {
0763: for (int i = Math.min(unitsInUse, set.unitsInUse) - 1; i >= 0; i--)
0764: if ((bits[i] & set.bits[i]) != 0)
0765: return true;
0766: return false;
0767: }
0768:
0769: /**
0770: * Returns the number of bits set to <tt>true</tt> in this
0771: * <code>BitSet</code>.
0772: *
0773: * @return the number of bits set to <tt>true</tt> in this
0774: * <code>BitSet</code>.
0775: * @since 1.4
0776: */
0777: public int cardinality() {
0778: int sum = 0;
0779: for (int i = 0; i < unitsInUse; i++)
0780: sum += bitCount(bits[i]);
0781: return sum;
0782: }
0783:
0784: /**
0785: * Returns the number of bits set in val.
0786: * For a derivation of this algorithm, see
0787: * "Algorithms and data structures with applications to
0788: * graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs,
0789: * Prentice Hall, 1993.
0790: */
0791: private static int bitCount(long val) {
0792: val -= (val & 0xaaaaaaaaaaaaaaaaL) >>> 1;
0793: val = (val & 0x3333333333333333L)
0794: + ((val >>> 2) & 0x3333333333333333L);
0795: val = (val + (val >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
0796: val += val >>> 8;
0797: val += val >>> 16;
0798: return ((int) (val) + (int) (val >>> 32)) & 0xff;
0799: }
0800:
0801: /**
0802: * Performs a logical <b>AND</b> of this target bit set with the
0803: * argument bit set. This bit set is modified so that each bit in it
0804: * has the value <code>true</code> if and only if it both initially
0805: * had the value <code>true</code> and the corresponding bit in the
0806: * bit set argument also had the value <code>true</code>.
0807: *
0808: * @param set a bit set.
0809: */
0810: public void and(BitSet set) {
0811: if (this == set)
0812: return;
0813:
0814: // Perform logical AND on bits in common
0815: int oldUnitsInUse = unitsInUse;
0816: unitsInUse = Math.min(unitsInUse, set.unitsInUse);
0817: int i;
0818: for (i = 0; i < unitsInUse; i++)
0819: bits[i] &= set.bits[i];
0820:
0821: // Clear out units no longer used
0822: for (; i < oldUnitsInUse; i++)
0823: bits[i] = 0;
0824:
0825: // Recalculate units in use if necessary
0826: if (unitsInUse > 0 && bits[unitsInUse - 1] == 0)
0827: recalculateUnitsInUse();
0828: }
0829:
0830: /**
0831: * Performs a logical <b>OR</b> of this bit set with the bit set
0832: * argument. This bit set is modified so that a bit in it has the
0833: * value <code>true</code> if and only if it either already had the
0834: * value <code>true</code> or the corresponding bit in the bit set
0835: * argument has the value <code>true</code>.
0836: *
0837: * @param set a bit set.
0838: */
0839: public void or(BitSet set) {
0840: if (this == set)
0841: return;
0842:
0843: ensureCapacity(set.unitsInUse);
0844:
0845: // Perform logical OR on bits in common
0846: int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);
0847: int i;
0848: for (i = 0; i < unitsInCommon; i++)
0849: bits[i] |= set.bits[i];
0850:
0851: // Copy any remaining bits
0852: for (; i < set.unitsInUse; i++)
0853: bits[i] = set.bits[i];
0854:
0855: if (unitsInUse < set.unitsInUse)
0856: unitsInUse = set.unitsInUse;
0857: }
0858:
0859: /**
0860: * Performs a logical <b>XOR</b> of this bit set with the bit set
0861: * argument. This bit set is modified so that a bit in it has the
0862: * value <code>true</code> if and only if one of the following
0863: * statements holds:
0864: * <ul>
0865: * <li>The bit initially has the value <code>true</code>, and the
0866: * corresponding bit in the argument has the value <code>false</code>.
0867: * <li>The bit initially has the value <code>false</code>, and the
0868: * corresponding bit in the argument has the value <code>true</code>.
0869: * </ul>
0870: *
0871: * @param set a bit set.
0872: */
0873: public void xor(BitSet set) {
0874: int unitsInCommon;
0875:
0876: if (unitsInUse >= set.unitsInUse) {
0877: unitsInCommon = set.unitsInUse;
0878: } else {
0879: unitsInCommon = unitsInUse;
0880: int newUnitsInUse = set.unitsInUse;
0881: ensureCapacity(newUnitsInUse);
0882: unitsInUse = newUnitsInUse;
0883: }
0884:
0885: // Perform logical XOR on bits in common
0886: int i;
0887: for (i = 0; i < unitsInCommon; i++)
0888: bits[i] ^= set.bits[i];
0889:
0890: // Copy any remaining bits
0891: for (; i < set.unitsInUse; i++)
0892: bits[i] = set.bits[i];
0893:
0894: recalculateUnitsInUse();
0895: }
0896:
0897: /**
0898: * Clears all of the bits in this <code>BitSet</code> whose corresponding
0899: * bit is set in the specified <code>BitSet</code>.
0900: *
0901: * @param set the <code>BitSet</code> with which to mask this
0902: * <code>BitSet</code>.
0903: * @since JDK1.2
0904: */
0905: public void andNot(BitSet set) {
0906: int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);
0907:
0908: // Perform logical (a & !b) on bits in common
0909: for (int i = 0; i < unitsInCommon; i++) {
0910: bits[i] &= ~set.bits[i];
0911: }
0912:
0913: recalculateUnitsInUse();
0914: }
0915:
0916: /**
0917: * Returns a hash code value for this bit set. The has code
0918: * depends only on which bits have been set within this
0919: * <code>BitSet</code>. The algorithm used to compute it may
0920: * be described as follows.<p>
0921: * Suppose the bits in the <code>BitSet</code> were to be stored
0922: * in an array of <code>long</code> integers called, say,
0923: * <code>bits</code>, in such a manner that bit <code>k</code> is
0924: * set in the <code>BitSet</code> (for nonnegative values of
0925: * <code>k</code>) if and only if the expression
0926: * <pre>((k>>6) < bits.length) && ((bits[k>>6] & (1L << (bit & 0x3F))) != 0)</pre>
0927: * is true. Then the following definition of the <code>hashCode</code>
0928: * method would be a correct implementation of the actual algorithm:
0929: * <pre>
0930: * public int hashCode() {
0931: * long h = 1234;
0932: * for (int i = bits.length; --i >= 0; ) {
0933: * h ^= bits[i] * (i + 1);
0934: * }
0935: * return (int)((h >> 32) ^ h);
0936: * }</pre>
0937: * Note that the hash code values change if the set of bits is altered.
0938: * <p>Overrides the <code>hashCode</code> method of <code>Object</code>.
0939: *
0940: * @return a hash code value for this bit set.
0941: */
0942: public int hashCode() {
0943: long h = 1234;
0944: for (int i = bits.length; --i >= 0;)
0945: h ^= bits[i] * (i + 1);
0946:
0947: return (int) ((h >> 32) ^ h);
0948: }
0949:
0950: /**
0951: * Returns the number of bits of space actually in use by this
0952: * <code>BitSet</code> to represent bit values.
0953: * The maximum element in the set is the size - 1st element.
0954: *
0955: * @return the number of bits currently in this bit set.
0956: */
0957: public int size() {
0958: return bits.length << ADDRESS_BITS_PER_UNIT;
0959: }
0960:
0961: /**
0962: * Compares this object against the specified object.
0963: * The result is <code>true</code> if and only if the argument is
0964: * not <code>null</code> and is a <code>Bitset</code> object that has
0965: * exactly the same set of bits set to <code>true</code> as this bit
0966: * set. That is, for every nonnegative <code>int</code> index <code>k</code>,
0967: * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
0968: * must be true. The current sizes of the two bit sets are not compared.
0969: * <p>Overrides the <code>equals</code> method of <code>Object</code>.
0970: *
0971: * @param obj the object to compare with.
0972: * @return <code>true</code> if the objects are the same;
0973: * <code>false</code> otherwise.
0974: * @see java.util.BitSet#size()
0975: */
0976: public boolean equals(Object obj) {
0977: if (!(obj instanceof BitSet))
0978: return false;
0979: if (this == obj)
0980: return true;
0981:
0982: BitSet set = (BitSet) obj;
0983: int minUnitsInUse = Math.min(unitsInUse, set.unitsInUse);
0984:
0985: // Check units in use by both BitSets
0986: for (int i = 0; i < minUnitsInUse; i++)
0987: if (bits[i] != set.bits[i])
0988: return false;
0989:
0990: // Check any units in use by only one BitSet (must be 0 in other)
0991: if (unitsInUse > minUnitsInUse) {
0992: for (int i = minUnitsInUse; i < unitsInUse; i++)
0993: if (bits[i] != 0)
0994: return false;
0995: } else {
0996: for (int i = minUnitsInUse; i < set.unitsInUse; i++)
0997: if (set.bits[i] != 0)
0998: return false;
0999: }
1000:
1001: return true;
1002: }
1003:
1004: /**
1005: * Cloning this <code>BitSet</code> produces a new <code>BitSet</code>
1006: * that is equal to it.
1007: * The clone of the bit set is another bit set that has exactly the
1008: * same bits set to <code>true</code> as this bit set and the same
1009: * current size.
1010: * <p>Overrides the <code>clone</code> method of <code>Object</code>.
1011: *
1012: * @return a clone of this bit set.
1013: * @see java.util.BitSet#size()
1014: */
1015: public Object clone() {
1016: BitSet result = null;
1017: try {
1018: result = (BitSet) super .clone();
1019: } catch (CloneNotSupportedException e) {
1020: throw new InternalError();
1021: }
1022: result.bits = new long[bits.length];
1023: System.arraycopy(bits, 0, result.bits, 0, unitsInUse);
1024: return result;
1025: }
1026:
1027: /**
1028: * This override of readObject makes sure unitsInUse is set properly
1029: * when deserializing a bitset
1030: *
1031: */
1032: private void readObject(java.io.ObjectInputStream in)
1033: throws IOException, ClassNotFoundException {
1034:
1035: in.defaultReadObject();
1036: // Assume maximum length then find real length
1037: // because recalculateUnitsInUse assumes maintenance
1038: // or reduction in logical size
1039: unitsInUse = bits.length;
1040: recalculateUnitsInUse();
1041: }
1042:
1043: /**
1044: * Returns a string representation of this bit set. For every index
1045: * for which this <code>BitSet</code> contains a bit in the set
1046: * state, the decimal representation of that index is included in
1047: * the result. Such indices are listed in order from lowest to
1048: * highest, separated by ", " (a comma and a space) and
1049: * surrounded by braces, resulting in the usual mathematical
1050: * notation for a set of integers.<p>
1051: * Overrides the <code>toString</code> method of <code>Object</code>.
1052: * <p>Example:
1053: * <pre>
1054: * BitSet drPepper = new BitSet();</pre>
1055: * Now <code>drPepper.toString()</code> returns "<code>{}</code>".<p>
1056: * <pre>
1057: * drPepper.set(2);</pre>
1058: * Now <code>drPepper.toString()</code> returns "<code>{2}</code>".<p>
1059: * <pre>
1060: * drPepper.set(4);
1061: * drPepper.set(10);</pre>
1062: * Now <code>drPepper.toString()</code> returns "<code>{2, 4, 10}</code>".
1063: *
1064: * @return a string representation of this bit set.
1065: */
1066: public String toString() {
1067: int numBits = unitsInUse << ADDRESS_BITS_PER_UNIT;
1068: StringBuffer buffer = new StringBuffer(8 * numBits + 2);
1069: String separator = "";
1070: buffer.append('{');
1071:
1072: for (int i = 0; i < numBits; i++) {
1073: if (get(i)) {
1074: buffer.append(separator);
1075: separator = ", ";
1076: buffer.append(i);
1077: }
1078: }
1079:
1080: buffer.append('}');
1081: return buffer.toString();
1082: }
1083: }
|