0001: /*
0002: * Licensed to the Apache Software Foundation (ASF) under one or more
0003: * contributor license agreements. See the NOTICE file distributed with
0004: * this work for additional information regarding copyright ownership.
0005: * The ASF licenses this file to You under the Apache License, Version 2.0
0006: * (the "License"); you may not use this file except in compliance with
0007: * the License. You may obtain a copy of the License at
0008: *
0009: * http://www.apache.org/licenses/LICENSE-2.0
0010: *
0011: * Unless required by applicable law or agreed to in writing, software
0012: * distributed under the License is distributed on an "AS IS" BASIS,
0013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014: * See the License for the specific language governing permissions and
0015: * limitations under the License.
0016: */
0017:
0018: package java.util;
0019:
0020: import java.io.IOException;
0021: import java.io.ObjectInputStream;
0022: import java.io.Serializable;
0023:
0024: import org.apache.harmony.luni.util.Msg;
0025:
0026: /**
0027: * The BitSet class implements a bit field. Each element in a BitSet can be
0028: * on(1) or off(0). A BitSet is created with a given size and grows when this
0029: * size is exceeded. Growth is always rounded to a 64 bit boundary.
0030: */
0031: public class BitSet implements Serializable, Cloneable {
0032: private static final long serialVersionUID = 7997698588986878753L;
0033:
0034: private static final int OFFSET = 6;
0035:
0036: private static final int ELM_SIZE = 1 << OFFSET;
0037:
0038: private static final int RIGHT_BITS = ELM_SIZE - 1;
0039:
0040: private static final long[] TWO_N_ARRAY = new long[] { 0x1L, 0x2L,
0041: 0x4L, 0x8L, 0x10L, 0x20L, 0x40L, 0x80L, 0x100L, 0x200L,
0042: 0x400L, 0x800L, 0x1000L, 0x2000L, 0x4000L, 0x8000L,
0043: 0x10000L, 0x20000L, 0x40000L, 0x80000L, 0x100000L,
0044: 0x200000L, 0x400000L, 0x800000L, 0x1000000L, 0x2000000L,
0045: 0x4000000L, 0x8000000L, 0x10000000L, 0x20000000L,
0046: 0x40000000L, 0x80000000L, 0x100000000L, 0x200000000L,
0047: 0x400000000L, 0x800000000L, 0x1000000000L, 0x2000000000L,
0048: 0x4000000000L, 0x8000000000L, 0x10000000000L,
0049: 0x20000000000L, 0x40000000000L, 0x80000000000L,
0050: 0x100000000000L, 0x200000000000L, 0x400000000000L,
0051: 0x800000000000L, 0x1000000000000L, 0x2000000000000L,
0052: 0x4000000000000L, 0x8000000000000L, 0x10000000000000L,
0053: 0x20000000000000L, 0x40000000000000L, 0x80000000000000L,
0054: 0x100000000000000L, 0x200000000000000L, 0x400000000000000L,
0055: 0x800000000000000L, 0x1000000000000000L,
0056: 0x2000000000000000L, 0x4000000000000000L,
0057: 0x8000000000000000L };
0058:
0059: private long[] bits;
0060:
0061: private transient boolean needClear;
0062:
0063: private transient int actualArrayLength;
0064:
0065: private transient boolean isLengthActual;
0066:
0067: /**
0068: * Create a new BitSet with size equal to 64 bits
0069: *
0070: * @see #clear(int)
0071: * @see #set(int)
0072: * @see #clear()
0073: * @see #clear(int, int)
0074: * @see #set(int, boolean)
0075: * @see #set(int, int)
0076: * @see #set(int, int, boolean)
0077: */
0078: public BitSet() {
0079: bits = new long[1];
0080: actualArrayLength = 0;
0081: isLengthActual = true;
0082: }
0083:
0084: /**
0085: * Create a new BitSet with size equal to nbits. If nbits is not a multiple
0086: * of 64, then create a BitSet with size nbits rounded to the next closest
0087: * multiple of 64.
0088: *
0089: * @param nbits
0090: * the size of the bit set
0091: * @throws NegativeArraySizeException
0092: * if nbits < 0.
0093: *
0094: * @see #clear(int)
0095: * @see #set(int)
0096: * @see #clear()
0097: * @see #clear(int, int)
0098: * @see #set(int, boolean)
0099: * @see #set(int, int)
0100: * @see #set(int, int, boolean)
0101: */
0102: public BitSet(int nbits) {
0103: if (nbits < 0) {
0104: throw new NegativeArraySizeException();
0105: }
0106: bits = new long[(nbits >> OFFSET)
0107: + ((nbits & RIGHT_BITS) > 0 ? 1 : 0)];
0108: actualArrayLength = 0;
0109: isLengthActual = true;
0110: }
0111:
0112: /**
0113: * Private constructor called from get(int, int) method
0114: *
0115: * @param bits
0116: * the size of the bit set
0117: * @param needClear
0118: */
0119: private BitSet(long[] bits, boolean needClear,
0120: int actualArrayLength, boolean isLengthActual) {
0121: this .bits = bits;
0122: this .needClear = needClear;
0123: this .actualArrayLength = actualArrayLength;
0124: this .isLengthActual = isLengthActual;
0125: }
0126:
0127: /**
0128: * Create a copy of this BitSet
0129: *
0130: * @return A copy of this BitSet.
0131: */
0132: @Override
0133: public Object clone() {
0134: try {
0135: BitSet clone = (BitSet) super .clone();
0136: clone.bits = bits.clone();
0137: return clone;
0138: } catch (CloneNotSupportedException e) {
0139: return null;
0140: }
0141: }
0142:
0143: /**
0144: * Compares the argument to this BitSet and answer if they are equal. The
0145: * object must be an instance of BitSet with the same bits set.
0146: *
0147: * @param obj
0148: * the <code>BitSet</code> object to compare
0149: * @return A boolean indicating whether or not this BitSet and obj are equal
0150: *
0151: * @see #hashCode
0152: */
0153: @Override
0154: public boolean equals(Object obj) {
0155: if (this == obj) {
0156: return true;
0157: }
0158: if (obj instanceof BitSet) {
0159: long[] bsBits = ((BitSet) obj).bits;
0160: int length1 = this .actualArrayLength, length2 = ((BitSet) obj).actualArrayLength;
0161: if (this .isLengthActual && ((BitSet) obj).isLengthActual
0162: && length1 != length2) {
0163: return false;
0164: }
0165: // If one of the BitSets is larger than the other, check to see if
0166: // any of its extra bits are set. If so return false.
0167: if (length1 <= length2) {
0168: for (int i = 0; i < length1; i++) {
0169: if (bits[i] != bsBits[i]) {
0170: return false;
0171: }
0172: }
0173: for (int i = length1; i < length2; i++) {
0174: if (bsBits[i] != 0) {
0175: return false;
0176: }
0177: }
0178: } else {
0179: for (int i = 0; i < length2; i++) {
0180: if (bits[i] != bsBits[i]) {
0181: return false;
0182: }
0183: }
0184: for (int i = length2; i < length1; i++) {
0185: if (bits[i] != 0) {
0186: return false;
0187: }
0188: }
0189: }
0190: return true;
0191: }
0192: return false;
0193: }
0194:
0195: /**
0196: * Increase the size of the internal array to accommodate pos bits. The new
0197: * array max index will be a multiple of 64
0198: *
0199: * @param pos
0200: * the index the new array needs to be able to access
0201: */
0202: private final void growLength(int len) {
0203: long[] tempBits = new long[Math.max(len, bits.length * 2)];
0204: System.arraycopy(bits, 0, tempBits, 0, this .actualArrayLength);
0205: bits = tempBits;
0206: }
0207:
0208: /**
0209: * Computes the hash code for this BitSet.
0210: *
0211: * @return The <code>int</code> representing the hash code for this bit
0212: * set.
0213: *
0214: * @see #equals
0215: * @see java.util.Hashtable
0216: */
0217: @Override
0218: public int hashCode() {
0219: long x = 1234;
0220: for (int i = 0, length = actualArrayLength; i < length; i++) {
0221: x ^= bits[i] * (i + 1);
0222: }
0223: return (int) ((x >> 32) ^ x);
0224: }
0225:
0226: /**
0227: * Retrieve the bit at index pos. Grows the BitSet if pos > size.
0228: *
0229: * @param pos
0230: * the index of the bit to be retrieved
0231: * @return <code>true</code> if the bit at <code>pos</code> is set,
0232: * <code>false</code> otherwise
0233: * @throws IndexOutOfBoundsException
0234: * when <code>pos</code> < 0
0235: *
0236: * @see #clear(int)
0237: * @see #set(int)
0238: * @see #clear()
0239: * @see #clear(int, int)
0240: * @see #set(int, boolean)
0241: * @see #set(int, int)
0242: * @see #set(int, int, boolean)
0243: */
0244: public boolean get(int pos) {
0245: if (pos < 0) {
0246: // Negative index specified
0247: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0248: }
0249:
0250: int arrayPos = pos >> OFFSET;
0251: if (arrayPos < actualArrayLength) {
0252: return (bits[arrayPos] & TWO_N_ARRAY[pos & RIGHT_BITS]) != 0;
0253: }
0254: return false;
0255: }
0256:
0257: /**
0258: * Retrieves the bits starting from pos1 to pos2 and answers back a new
0259: * bitset made of these bits. Grows the BitSet if pos2 > size.
0260: *
0261: * @param pos1
0262: * beginning position
0263: * @param pos2
0264: * ending position
0265: * @return new bitset
0266: * @throws IndexOutOfBoundsException
0267: * when pos1 or pos2 is negative, or when pos2 is not smaller
0268: * than pos1
0269: *
0270: * @see #get(int)
0271: */
0272: public BitSet get(int pos1, int pos2) {
0273: if (pos1 < 0 || pos2 < 0 || pos2 < pos1) {
0274: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0275: }
0276:
0277: int last = actualArrayLength << OFFSET;
0278: if (pos1 >= last || pos1 == pos2) {
0279: return new BitSet(0);
0280: }
0281: if (pos2 > last) {
0282: pos2 = last;
0283: }
0284:
0285: int idx1 = pos1 >> OFFSET;
0286: int idx2 = (pos2 - 1) >> OFFSET;
0287: long factor1 = (~0L) << (pos1 & RIGHT_BITS);
0288: long factor2 = (~0L) >>> (ELM_SIZE - (pos2 & RIGHT_BITS));
0289:
0290: if (idx1 == idx2) {
0291: long result = (bits[idx1] & (factor1 & factor2)) >>> (pos1 % ELM_SIZE);
0292: if (result == 0) {
0293: return new BitSet(0);
0294: }
0295: return new BitSet(new long[] { result }, needClear, 1, true);
0296: }
0297: long[] newbits = new long[idx2 - idx1 + 1];
0298: // first fill in the first and last indexes in the new bitset
0299: newbits[0] = bits[idx1] & factor1;
0300: newbits[newbits.length - 1] = bits[idx2] & factor2;
0301:
0302: // fill in the in between elements of the new bitset
0303: for (int i = 1; i < idx2 - idx1; i++) {
0304: newbits[i] = bits[idx1 + i];
0305: }
0306:
0307: // shift all the elements in the new bitset to the right by pos1
0308: // % ELM_SIZE
0309: int numBitsToShift = pos1 & RIGHT_BITS;
0310: int actualLen = newbits.length;
0311: if (numBitsToShift != 0) {
0312: for (int i = 0; i < newbits.length; i++) {
0313: // shift the current element to the right regardless of
0314: // sign
0315: newbits[i] = newbits[i] >>> (numBitsToShift);
0316:
0317: // apply the last x bits of newbits[i+1] to the current
0318: // element
0319: if (i != newbits.length - 1) {
0320: newbits[i] |= newbits[i + 1] << (ELM_SIZE - (numBitsToShift));
0321: }
0322: if (newbits[i] != 0) {
0323: actualLen = i + 1;
0324: }
0325: }
0326: }
0327: return new BitSet(newbits, needClear, actualLen,
0328: newbits[actualLen - 1] != 0);
0329: }
0330:
0331: /**
0332: * Sets the bit at index pos to 1. Grows the BitSet if pos > size.
0333: *
0334: * @param pos
0335: * the index of the bit to set
0336: * @throws IndexOutOfBoundsException
0337: * when pos < 0
0338: *
0339: * @see #clear(int)
0340: * @see #clear()
0341: * @see #clear(int, int)
0342: */
0343: public void set(int pos) {
0344: if (pos < 0) {
0345: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0346: }
0347:
0348: int len = (pos >> OFFSET) + 1;
0349: if (len > bits.length) {
0350: growLength(len);
0351: }
0352: bits[len - 1] |= TWO_N_ARRAY[pos & RIGHT_BITS];
0353: if (len > actualArrayLength) {
0354: actualArrayLength = len;
0355: isLengthActual = true;
0356: }
0357: needClear();
0358: }
0359:
0360: /**
0361: * Sets the bit at index pos to the value. Grows the BitSet if pos > size.
0362: *
0363: * @param pos
0364: * the index of the bit to set
0365: * @param val
0366: * value to set the bit
0367: * @throws IndexOutOfBoundsException
0368: * when pos < 0
0369: *
0370: * @see #set(int)
0371: */
0372: public void set(int pos, boolean val) {
0373: if (val) {
0374: set(pos);
0375: } else {
0376: clear(pos);
0377: }
0378: }
0379:
0380: /**
0381: * Sets the bits starting from pos1 to pos2. Grows the BitSet if pos2 >
0382: * size.
0383: *
0384: * @param pos1
0385: * beginning position
0386: * @param pos2
0387: * ending position
0388: * @throws IndexOutOfBoundsException
0389: * when pos1 or pos2 is negative, or when pos2 is not smaller
0390: * than pos1
0391: *
0392: * @see #set(int)
0393: */
0394: public void set(int pos1, int pos2) {
0395: if (pos1 < 0 || pos2 < 0 || pos2 < pos1) {
0396: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0397: }
0398:
0399: if (pos1 == pos2) {
0400: return;
0401: }
0402: int len2 = ((pos2 - 1) >> OFFSET) + 1;
0403: if (len2 > bits.length) {
0404: growLength(len2);
0405: }
0406:
0407: int idx1 = pos1 >> OFFSET;
0408: int idx2 = (pos2 - 1) >> OFFSET;
0409: long factor1 = (~0L) << (pos1 & RIGHT_BITS);
0410: long factor2 = (~0L) >>> (ELM_SIZE - (pos2 & RIGHT_BITS));
0411:
0412: if (idx1 == idx2) {
0413: bits[idx1] |= (factor1 & factor2);
0414: } else {
0415: bits[idx1] |= factor1;
0416: bits[idx2] |= factor2;
0417: for (int i = idx1 + 1; i < idx2; i++) {
0418: bits[i] |= (~0L);
0419: }
0420: }
0421: if (idx2 + 1 > actualArrayLength) {
0422: actualArrayLength = idx2 + 1;
0423: isLengthActual = true;
0424: }
0425: needClear();
0426: }
0427:
0428: private void needClear() {
0429: this .needClear = true;
0430: }
0431:
0432: /**
0433: * Sets the bits starting from pos1 to pos2 to the given boolean value.
0434: * Grows the BitSet if pos2 > size.
0435: *
0436: * @param pos1
0437: * beginning position
0438: * @param pos2
0439: * ending position
0440: * @param val
0441: * value to set these bits
0442: *
0443: * @throws IndexOutOfBoundsException
0444: * when pos1 or pos2 is negative, or when pos2 is not smaller
0445: * than pos1
0446: * @see #set(int,int)
0447: */
0448: public void set(int pos1, int pos2, boolean val) {
0449: if (val) {
0450: set(pos1, pos2);
0451: } else {
0452: clear(pos1, pos2);
0453: }
0454: }
0455:
0456: /**
0457: * Clears all the bits in this bitset.
0458: *
0459: * @see #clear(int)
0460: * @see #clear(int, int)
0461: */
0462: public void clear() {
0463: if (needClear) {
0464: for (int i = 0; i < bits.length; i++) {
0465: bits[i] = 0L;
0466: }
0467: actualArrayLength = 0;
0468: isLengthActual = true;
0469: needClear = false;
0470: }
0471: }
0472:
0473: /**
0474: * Clears the bit at index pos. Grows the BitSet if pos > size.
0475: *
0476: * @param pos
0477: * the index of the bit to clear
0478: * @throws IndexOutOfBoundsException
0479: * when pos < 0
0480: *
0481: * @see #clear(int, int)
0482: */
0483: public void clear(int pos) {
0484: if (pos < 0) {
0485: // Negative index specified
0486: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0487: }
0488:
0489: if (!needClear) {
0490: return;
0491: }
0492: int arrayPos = pos >> OFFSET;
0493: if (arrayPos < actualArrayLength) {
0494: bits[arrayPos] &= ~(TWO_N_ARRAY[pos & RIGHT_BITS]);
0495: if (bits[actualArrayLength - 1] == 0) {
0496: isLengthActual = false;
0497: }
0498: }
0499: }
0500:
0501: /**
0502: * Clears the bits starting from pos1 to pos2. Grows the BitSet if pos2 >
0503: * size.
0504: *
0505: * @param pos1
0506: * beginning position
0507: * @param pos2
0508: * ending position
0509: * @throws IndexOutOfBoundsException
0510: * when pos1 or pos2 is negative, or when pos2 is not smaller
0511: * than pos1
0512: * @see #clear(int)
0513: */
0514: public void clear(int pos1, int pos2) {
0515: if (pos1 < 0 || pos2 < 0 || pos2 < pos1) {
0516: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0517: }
0518:
0519: if (!needClear) {
0520: return;
0521: }
0522: int last = (actualArrayLength << OFFSET);
0523: if (pos1 >= last || pos1 == pos2) {
0524: return;
0525: }
0526: if (pos2 > last) {
0527: pos2 = last;
0528: }
0529:
0530: int idx1 = pos1 >> OFFSET;
0531: int idx2 = (pos2 - 1) >> OFFSET;
0532: long factor1 = (~0L) << (pos1 & RIGHT_BITS);
0533: long factor2 = (~0L) >>> (ELM_SIZE - (pos2 & RIGHT_BITS));
0534:
0535: if (idx1 == idx2) {
0536: bits[idx1] &= ~(factor1 & factor2);
0537: } else {
0538: bits[idx1] &= ~factor1;
0539: bits[idx2] &= ~factor2;
0540: for (int i = idx1 + 1; i < idx2; i++) {
0541: bits[i] = 0L;
0542: }
0543: }
0544: if ((actualArrayLength > 0)
0545: && (bits[actualArrayLength - 1] == 0)) {
0546: isLengthActual = false;
0547: }
0548: }
0549:
0550: /**
0551: * Flips the bit at index pos. Grows the BitSet if pos > size.
0552: *
0553: * @param pos
0554: * the index of the bit to flip
0555: *
0556: * @throws IndexOutOfBoundsException
0557: * when pos < 0
0558: * @see #flip(int, int)
0559: */
0560: public void flip(int pos) {
0561: if (pos < 0) {
0562: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0563: }
0564:
0565: int len = (pos >> OFFSET) + 1;
0566: if (len > bits.length) {
0567: growLength(len);
0568: }
0569: bits[len - 1] ^= TWO_N_ARRAY[pos & RIGHT_BITS];
0570: if (len > actualArrayLength) {
0571: actualArrayLength = len;
0572: }
0573: isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
0574: needClear();
0575: }
0576:
0577: /**
0578: * Flips the bits starting from pos1 to pos2. Grows the BitSet if pos2 >
0579: * size.
0580: *
0581: * @param pos1
0582: * beginning position
0583: * @param pos2
0584: * ending position
0585: * @throws IndexOutOfBoundsException
0586: * when pos1 or pos2 is negative, or when pos2 is not smaller
0587: * than pos1
0588: *
0589: * @see #flip(int)
0590: */
0591: public void flip(int pos1, int pos2) {
0592: if (pos1 < 0 || pos2 < 0 || pos2 < pos1) {
0593: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0594: }
0595:
0596: if (pos1 == pos2) {
0597: return;
0598: }
0599: int len2 = ((pos2 - 1) >> OFFSET) + 1;
0600: if (len2 > bits.length) {
0601: growLength(len2);
0602: }
0603:
0604: int idx1 = pos1 >> OFFSET;
0605: int idx2 = (pos2 - 1) >> OFFSET;
0606: long factor1 = (~0L) << (pos1 & RIGHT_BITS);
0607: long factor2 = (~0L) >>> (ELM_SIZE - (pos2 & RIGHT_BITS));
0608:
0609: if (idx1 == idx2) {
0610: bits[idx1] ^= (factor1 & factor2);
0611: } else {
0612: bits[idx1] ^= factor1;
0613: bits[idx2] ^= factor2;
0614: for (int i = idx1 + 1; i < idx2; i++) {
0615: bits[i] ^= (~0L);
0616: }
0617: }
0618: if (len2 > actualArrayLength) {
0619: actualArrayLength = len2;
0620: }
0621: isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
0622: needClear();
0623: }
0624:
0625: /**
0626: * Checks if these two bitsets have at least one bit set to true in the same
0627: * position.
0628: *
0629: * @param bs
0630: * BitSet used to calculate intersect
0631: * @return <code>true</code> if bs intersects with this BitSet,
0632: * <code>false</code> otherwise
0633: */
0634: public boolean intersects(BitSet bs) {
0635: long[] bsBits = bs.bits;
0636: int length1 = actualArrayLength, length2 = bs.actualArrayLength;
0637:
0638: if (length1 <= length2) {
0639: for (int i = 0; i < length1; i++) {
0640: if ((bits[i] & bsBits[i]) != 0L) {
0641: return true;
0642: }
0643: }
0644: } else {
0645: for (int i = 0; i < length2; i++) {
0646: if ((bits[i] & bsBits[i]) != 0L) {
0647: return true;
0648: }
0649: }
0650: }
0651:
0652: return false;
0653: }
0654:
0655: /**
0656: * Performs the logical AND of this BitSet with another BitSet.
0657: *
0658: * @param bs
0659: * BitSet to AND with
0660: *
0661: * @see #or
0662: * @see #xor
0663: */
0664: public void and(BitSet bs) {
0665: long[] bsBits = bs.bits;
0666: if (!needClear) {
0667: return;
0668: }
0669: int length1 = actualArrayLength, length2 = bs.actualArrayLength;
0670: if (length1 <= length2) {
0671: for (int i = 0; i < length1; i++) {
0672: bits[i] &= bsBits[i];
0673: }
0674: } else {
0675: for (int i = 0; i < length2; i++) {
0676: bits[i] &= bsBits[i];
0677: }
0678: for (int i = length2; i < length1; i++) {
0679: bits[i] = 0;
0680: }
0681: actualArrayLength = length2;
0682: }
0683: isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
0684: }
0685:
0686: /**
0687: * Clears all bits in the receiver which are also set in the parameter
0688: * BitSet.
0689: *
0690: * @param bs
0691: * BitSet to ANDNOT with
0692: */
0693: public void andNot(BitSet bs) {
0694: long[] bsBits = bs.bits;
0695: if (!needClear) {
0696: return;
0697: }
0698: int range = actualArrayLength < bs.actualArrayLength ? actualArrayLength
0699: : bs.actualArrayLength;
0700: for (int i = 0; i < range; i++) {
0701: bits[i] &= ~bsBits[i];
0702: }
0703:
0704: if (actualArrayLength < range) {
0705: actualArrayLength = range;
0706: }
0707: isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
0708: }
0709:
0710: /**
0711: * Performs the logical OR of this BitSet with another BitSet.
0712: *
0713: * @param bs
0714: * BitSet to OR with
0715: *
0716: * @see #xor
0717: * @see #and
0718: */
0719: public void or(BitSet bs) {
0720: int bsActualLen = bs.getActualArrayLength();
0721: if (bsActualLen > bits.length) {
0722: long[] tempBits = new long[bsActualLen];
0723: System.arraycopy(bs.bits, 0, tempBits, 0,
0724: bs.actualArrayLength);
0725: for (int i = 0; i < actualArrayLength; i++) {
0726: tempBits[i] |= bits[i];
0727: }
0728: bits = tempBits;
0729: actualArrayLength = bsActualLen;
0730: isLengthActual = true;
0731: } else {
0732: long[] bsBits = bs.bits;
0733: for (int i = 0; i < bsActualLen; i++) {
0734: bits[i] |= bsBits[i];
0735: }
0736: if (bsActualLen > actualArrayLength) {
0737: actualArrayLength = bsActualLen;
0738: isLengthActual = true;
0739: }
0740: }
0741: needClear();
0742: }
0743:
0744: /**
0745: * Performs the logical XOR of this BitSet with another BitSet.
0746: *
0747: * @param bs
0748: * BitSet to XOR with
0749: *
0750: * @see #or
0751: * @see #and
0752: */
0753: public void xor(BitSet bs) {
0754: int bsActualLen = bs.getActualArrayLength();
0755: if (bsActualLen > bits.length) {
0756: long[] tempBits = new long[bsActualLen];
0757: System.arraycopy(bs.bits, 0, tempBits, 0,
0758: bs.actualArrayLength);
0759: for (int i = 0; i < actualArrayLength; i++) {
0760: tempBits[i] ^= bits[i];
0761: }
0762: bits = tempBits;
0763: actualArrayLength = bsActualLen;
0764: isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
0765: } else {
0766: long[] bsBits = bs.bits;
0767: for (int i = 0; i < bsActualLen; i++) {
0768: bits[i] ^= bsBits[i];
0769: }
0770: if (bsActualLen > actualArrayLength) {
0771: actualArrayLength = bsActualLen;
0772: isLengthActual = true;
0773: }
0774: }
0775: needClear();
0776: }
0777:
0778: /**
0779: * Answers the number of bits this bitset has.
0780: *
0781: * @return The number of bits contained in this BitSet.
0782: *
0783: * @see #length
0784: */
0785: public int size() {
0786: return bits.length << OFFSET;
0787: }
0788:
0789: /**
0790: * Returns the number of bits up to and including the highest bit set.
0791: *
0792: * @return the length of the BitSet
0793: */
0794: public int length() {
0795: int idx = actualArrayLength - 1;
0796: while (idx >= 0 && bits[idx] == 0) {
0797: --idx;
0798: }
0799: actualArrayLength = idx + 1;
0800: if (idx == -1) {
0801: return 0;
0802: }
0803: int i = ELM_SIZE - 1;
0804: long val = bits[idx];
0805: while ((val & (TWO_N_ARRAY[i])) == 0 && i > 0) {
0806: i--;
0807: }
0808: return (idx << OFFSET) + i + 1;
0809: }
0810:
0811: private final int getActualArrayLength() {
0812: if (isLengthActual) {
0813: return actualArrayLength;
0814: }
0815: int idx = actualArrayLength - 1;
0816: while (idx >= 0 && bits[idx] == 0) {
0817: --idx;
0818: }
0819: actualArrayLength = idx + 1;
0820: isLengthActual = true;
0821: return actualArrayLength;
0822: }
0823:
0824: /**
0825: * Answers a string containing a concise, human-readable description of the
0826: * receiver.
0827: *
0828: * @return A comma delimited list of the indices of all bits that are set.
0829: */
0830: @Override
0831: public String toString() {
0832: StringBuffer sb = new StringBuffer(bits.length / 2);
0833: int bitCount = 0;
0834: sb.append('{');
0835: boolean comma = false;
0836: for (int i = 0; i < bits.length; i++) {
0837: if (bits[i] == 0) {
0838: bitCount += ELM_SIZE;
0839: continue;
0840: }
0841: for (int j = 0; j < ELM_SIZE; j++) {
0842: if (((bits[i] & (TWO_N_ARRAY[j])) != 0)) {
0843: if (comma) {
0844: sb.append(", "); //$NON-NLS-1$
0845: }
0846: sb.append(bitCount);
0847: comma = true;
0848: }
0849: bitCount++;
0850: }
0851: }
0852: sb.append('}');
0853: return sb.toString();
0854: }
0855:
0856: /**
0857: * Answers the position of the first bit that is true on or after pos
0858: *
0859: * @param pos
0860: * the starting position (inclusive)
0861: * @return -1 if there is no bits that are set to true on or after pos.
0862: */
0863: public int nextSetBit(int pos) {
0864: if (pos < 0) {
0865: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0866: }
0867:
0868: if (pos >= actualArrayLength << OFFSET) {
0869: return -1;
0870: }
0871:
0872: int idx = pos >> OFFSET;
0873: // first check in the same bit set element
0874: if (bits[idx] != 0L) {
0875: for (int j = pos & RIGHT_BITS; j < ELM_SIZE; j++) {
0876: if (((bits[idx] & (TWO_N_ARRAY[j])) != 0)) {
0877: return (idx << OFFSET) + j;
0878: }
0879: }
0880:
0881: }
0882: idx++;
0883: while (idx < actualArrayLength && bits[idx] == 0L) {
0884: idx++;
0885: }
0886: if (idx == actualArrayLength) {
0887: return -1;
0888: }
0889:
0890: // we know for sure there is a bit set to true in this element
0891: // since the bitset value is not 0L
0892: for (int j = 0; j < ELM_SIZE; j++) {
0893: if (((bits[idx] & (TWO_N_ARRAY[j])) != 0)) {
0894: return (idx << OFFSET) + j;
0895: }
0896: }
0897:
0898: return -1;
0899: }
0900:
0901: /**
0902: * Answers the position of the first bit that is false on or after pos
0903: *
0904: * @param pos
0905: * the starting position (inclusive)
0906: * @return the position of the next bit set to false, even if it is further
0907: * than this bitset's size.
0908: */
0909: public int nextClearBit(int pos) {
0910: if (pos < 0) {
0911: throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
0912: }
0913:
0914: int length = actualArrayLength;
0915: int bssize = length << OFFSET;
0916: if (pos >= bssize) {
0917: return pos;
0918: }
0919:
0920: int idx = pos >> OFFSET;
0921: // first check in the same bit set element
0922: if (bits[idx] != (~0L)) {
0923: for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++) {
0924: if (((bits[idx] & (TWO_N_ARRAY[j])) == 0)) {
0925: return idx * ELM_SIZE + j;
0926: }
0927: }
0928: }
0929: idx++;
0930: while (idx < length && bits[idx] == (~0L)) {
0931: idx++;
0932: }
0933: if (idx == length) {
0934: return bssize;
0935: }
0936:
0937: // we know for sure there is a bit set to true in this element
0938: // since the bitset value is not 0L
0939: for (int j = 0; j < ELM_SIZE; j++) {
0940: if (((bits[idx] & (TWO_N_ARRAY[j])) == 0)) {
0941: return (idx << OFFSET) + j;
0942: }
0943: }
0944:
0945: return bssize;
0946: }
0947:
0948: /**
0949: * Answers true if all the bits in this bitset are set to false.
0950: *
0951: * @return <code>true</code> if the BitSet is empty, <code>false</code>
0952: * otherwise
0953: */
0954: public boolean isEmpty() {
0955: if (!needClear) {
0956: return true;
0957: }
0958: int length = bits.length;
0959: for (int idx = 0; idx < length; idx++) {
0960: if (bits[idx] != 0L) {
0961: return false;
0962: }
0963: }
0964: return true;
0965: }
0966:
0967: /**
0968: * Answers the number of bits that are true in this bitset.
0969: *
0970: * @return the number of true bits in the set
0971: */
0972: public int cardinality() {
0973: if (!needClear) {
0974: return 0;
0975: }
0976: int count = 0;
0977: int length = bits.length;
0978: // FIXME: need to test performance, if still not satisfied, change it to
0979: // 256-bits table based
0980: for (int idx = 0; idx < length; idx++) {
0981: count += pop(bits[idx] & 0xffffffffL);
0982: count += pop(bits[idx] >>> 32);
0983: }
0984: return count;
0985: }
0986:
0987: private final int pop(long x) {
0988: x = x - ((x >>> 1) & 0x55555555);
0989: x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
0990: x = (x + (x >>> 4)) & 0x0f0f0f0f;
0991: x = x + (x >>> 8);
0992: x = x + (x >>> 16);
0993: return (int) x & 0x0000003f;
0994: }
0995:
0996: private void readObject(ObjectInputStream ois) throws IOException,
0997: ClassNotFoundException {
0998: ois.defaultReadObject();
0999: this .isLengthActual = false;
1000: this .actualArrayLength = bits.length;
1001: this .needClear = this .getActualArrayLength() != 0;
1002: }
1003: }
|