diff options
Diffstat (limited to 'luni/src/main/java/java/util/BitSet.java')
| -rw-r--r-- | luni/src/main/java/java/util/BitSet.java | 861 |
1 files changed, 861 insertions, 0 deletions
diff --git a/luni/src/main/java/java/util/BitSet.java b/luni/src/main/java/java/util/BitSet.java new file mode 100644 index 0000000..aa60be0 --- /dev/null +++ b/luni/src/main/java/java/util/BitSet.java @@ -0,0 +1,861 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package java.util; + +import java.io.Serializable; + +import org.apache.harmony.luni.util.Msg; + +/** + * The {@code BitSet} class implements a bit field. Each element in a + * {@code BitSet} can be on(1) or off(0). A {@code BitSet} is created with a + * given size and grows if this size is exceeded. Growth is always rounded to a + * 64 bit boundary. + * + * @since Android 1.0 + */ +public class BitSet implements Serializable, Cloneable { + private static final long serialVersionUID = 7997698588986878753L; + + // Size in bits of the data type being used in the bits array + private static final int ELM_SIZE = 64; + + private long[] bits; + + /** + * Create a new {@code BitSet} with size equal to 64 bits. + * + * @see #clear(int) + * @see #set(int) + * @see #clear() + * @see #clear(int, int) + * @see #set(int, boolean) + * @see #set(int, int) + * @see #set(int, int, boolean) + * @since Android 1.0 + */ + public BitSet() { + this(64); + } + + /** + * Create a new {@code BitSet} with size equal to nbits. If nbits is not a + * multiple of 64, then create a {@code BitSet} with size nbits rounded to + * the next closest multiple of 64. + * + * @param nbits + * the size of the bit set. + * @throws NegativeArraySizeException + * if {@code nbits} is negative. + * @see #clear(int) + * @see #set(int) + * @see #clear() + * @see #clear(int, int) + * @see #set(int, boolean) + * @see #set(int, int) + * @see #set(int, int, boolean) + * @since Android 1.0 + */ + public BitSet(int nbits) { + if (nbits >= 0) { + bits = new long[(nbits / ELM_SIZE) + (nbits % ELM_SIZE > 0 ? 1 : 0)]; + } else { + throw new NegativeArraySizeException(); + } + } + + /** + * Private constructor called from get(int, int) method + * + * @param bits + * the size of the bit set + */ + private BitSet(long[] bits) { + this.bits = bits; + } + + /** + * Creates a copy of this {@code BitSet}. + * + * @return a copy of this {@code BitSet}. + * @since Android 1.0 + */ + @Override + public Object clone() { + try { + BitSet clone = (BitSet) super.clone(); + clone.bits = bits.clone(); + return clone; + } catch (CloneNotSupportedException e) { + return null; + } + } + + /** + * Compares the argument to this {@code BitSet} and returns whether they are + * equal. The object must be an instance of {@code BitSet} with the same + * bits set. + * + * @param obj + * the {@code BitSet} object to compare. + * @return a {@code boolean} indicating whether or not this {@code BitSet} and + * {@code obj} are equal. + * @see #hashCode + * @since Android 1.0 + */ + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof BitSet) { + long[] bsBits = ((BitSet) obj).bits; + int length1 = bits.length, length2 = bsBits.length; + // If one of the BitSets is larger than the other, check to see if + // any of + // its extra bits are set. If so return false. + if (length1 <= length2) { + for (int i = 0; i < length1; i++) { + if (bits[i] != bsBits[i]) { + return false; + } + } + for (int i = length1; i < length2; i++) { + if (bsBits[i] != 0) { + return false; + } + } + } else { + for (int i = 0; i < length2; i++) { + if (bits[i] != bsBits[i]) { + return false; + } + } + for (int i = length2; i < length1; i++) { + if (bits[i] != 0) { + return false; + } + } + } + return true; + } + return false; + } + + /** + * Increase the size of the internal array to accommodate {@code pos} bits. + * The new array max index will be a multiple of 64. + * + * @param pos + * the index the new array needs to be able to access. + * @since Android 1.0 + */ + private void growBits(int pos) { + pos++; // Inc to get correct bit count + long[] tempBits = new long[(pos / ELM_SIZE) + + (pos % ELM_SIZE > 0 ? 1 : 0)]; + System.arraycopy(bits, 0, tempBits, 0, bits.length); + bits = tempBits; + } + + /** + * Computes the hash code for this {@code BitSet}. If two {@code BitSet}s are equal + * the have to return the same result for {@code hashCode()}. + * + * @return the {@code int} representing the hash code for this bit + * set. + * @see #equals + * @see java.util.Hashtable + * @since Android 1.0 + */ + @Override + public int hashCode() { + long x = 1234; + // for (int i = 0, length = bits.length; i < length; i+=2) + // x ^= (bits[i] + ((long)bits[i+1] << 32)) * (i/2 + 1); + for (int i = 0, length = bits.length; i < length; i++) { + x ^= bits[i] * (i + 1); + } + return (int) ((x >> 32) ^ x); + } + + /** + * Retrieves the bit at index {@code pos}. Grows the {@code BitSet} if + * {@code pos > size}. + * + * @param pos + * the index of the bit to be retrieved. + * @return {@code true} if the bit at {@code pos} is set, + * {@code false} otherwise. + * @throws IndexOutOfBoundsException + * if {@code pos} is negative. + * @see #clear(int) + * @see #set(int) + * @see #clear() + * @see #clear(int, int) + * @see #set(int, boolean) + * @see #set(int, int) + * @see #set(int, int, boolean) + * @since Android 1.0 + */ + public boolean get(int pos) { + if (pos >= 0) { + if (pos < bits.length * ELM_SIZE) { + return (bits[pos / ELM_SIZE] & (1L << (pos % ELM_SIZE))) != 0; + } + return false; + } + // Negative index specified + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + + /** + * Retrieves the bits starting from {@code pos1} to {@code pos2} and returns + * back a new bitset made of these bits. Grows the {@code BitSet} if + * {@code pos2 > size}. + * + * @param pos1 + * beginning position. + * @param pos2 + * ending position. + * @return new bitset of the range specified. + * @throws IndexOutOfBoundsException + * if {@code pos1} or {@code pos2} is negative, or if + * {@code pos2} is smaller than {@code pos1}. + * @see #get(int) + * @since Android 1.0 + */ + public BitSet get(int pos1, int pos2) { + if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) { + int last = (bits.length * ELM_SIZE); + if (pos1 >= last || pos1 == pos2) { + return new BitSet(0); + } + if (pos2 > last) { + pos2 = last; + } + + int idx1 = pos1 / ELM_SIZE; + int idx2 = (pos2 - 1) / ELM_SIZE; + long factor1 = (~0L) << (pos1 % ELM_SIZE); + long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE)); + + if (idx1 == idx2) { + long result = (bits[idx1] & (factor1 & factor2)) >>> (pos1 % ELM_SIZE); + return new BitSet(new long[] { result }); + } + long[] newbits = new long[idx2 - idx1 + 1]; + // first fill in the first and last indexes in the new bitset + newbits[0] = bits[idx1] & factor1; + newbits[newbits.length - 1] = bits[idx2] & factor2; + + // fill in the in between elements of the new bitset + for (int i = 1; i < idx2 - idx1; i++) { + newbits[i] = bits[idx1 + i]; + } + + // shift all the elements in the new bitset to the right by pos1 + // % ELM_SIZE + int numBitsToShift = pos1 % ELM_SIZE; + if (numBitsToShift != 0) { + for (int i = 0; i < newbits.length; i++) { + // shift the current element to the right regardless of + // sign + newbits[i] = newbits[i] >>> (numBitsToShift); + + // apply the last x bits of newbits[i+1] to the current + // element + if (i != newbits.length - 1) { + newbits[i] |= newbits[i + 1] << (ELM_SIZE - (numBitsToShift)); + } + } + } + return new BitSet(newbits); + } + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + + /** + * Sets the bit at index {@code pos} to 1. Grows the {@code BitSet} if + * {@code pos > size}. + * + * @param pos + * the index of the bit to set. + * @throws IndexOutOfBoundsException + * if {@code pos} is negative. + * @see #clear(int) + * @see #clear() + * @see #clear(int, int) + * @since Android 1.0 + */ + public void set(int pos) { + if (pos >= 0) { + if (pos >= bits.length * ELM_SIZE) { + growBits(pos); + } + bits[pos / ELM_SIZE] |= 1L << (pos % ELM_SIZE); + } else { + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + } + + /** + * Sets the bit at index {@code pos} to {@code val}. Grows the + * {@code BitSet} if {@code pos > size}. + * + * @param pos + * the index of the bit to set. + * @param val + * value to set the bit. + * @throws IndexOutOfBoundsException + * if {@code pos} is negative. + * @see #set(int) + * @since Android 1.0 + */ + public void set(int pos, boolean val) { + if (val) { + set(pos); + } else { + clear(pos); + } + } + + /** + * Sets the bits starting from {@code pos1} to {@code pos2}. Grows the + * {@code BitSet} if {@code pos2 > size}. + * + * @param pos1 + * beginning position. + * @param pos2 + * ending position. + * @throws IndexOutOfBoundsException + * if {@code pos1} or {@code pos2} is negative, or if + * {@code pos2} is smaller than {@code pos1}. + * @see #set(int) + * @since Android 1.0 + */ + public void set(int pos1, int pos2) { + if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) { + if (pos1 == pos2) { + return; + } + if (pos2 >= bits.length * ELM_SIZE) { + growBits(pos2); + } + + int idx1 = pos1 / ELM_SIZE; + int idx2 = (pos2 - 1) / ELM_SIZE; + long factor1 = (~0L) << (pos1 % ELM_SIZE); + long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE)); + + if (idx1 == idx2) { + bits[idx1] |= (factor1 & factor2); + } else { + bits[idx1] |= factor1; + bits[idx2] |= factor2; + for (int i = idx1 + 1; i < idx2; i++) { + bits[i] |= (~0L); + } + } + } else { + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + } + + /** + * Sets the bits starting from {@code pos1} to {@code pos2} to the given + * {@code val}. Grows the {@code BitSet} if {@code pos2 > size}. + * + * @param pos1 + * beginning position. + * @param pos2 + * ending position. + * @param val + * value to set these bits. + * @throws IndexOutOfBoundsException + * if {@code pos1} or {@code pos2} is negative, or if + * {@code pos2} is smaller than {@code pos1}. + * @see #set(int,int) + * @since Android 1.0 + */ + public void set(int pos1, int pos2, boolean val) { + if (val) { + set(pos1, pos2); + } else { + clear(pos1, pos2); + } + } + + /** + * Clears all the bits in this {@code BitSet}. + * + * @see #clear(int) + * @see #clear(int, int) + * @since Android 1.0 + */ + public void clear() { + for (int i = 0; i < bits.length; i++) { + bits[i] = 0L; + } + } + + /** + * Clears the bit at index {@code pos}. Grows the {@code BitSet} if + * {@code pos > size}. + * + * @param pos + * the index of the bit to clear. + * @throws IndexOutOfBoundsException + * if {@code pos} is negative. + * @see #clear(int, int) + * @since Android 1.0 + */ + public void clear(int pos) { + if (pos >= 0) { + if (pos < bits.length * ELM_SIZE) { + bits[pos / ELM_SIZE] &= ~(1L << (pos % ELM_SIZE)); + } + } else { + // Negative index specified + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + } + + /** + * Clears the bits starting from {@code pos1} to {@code pos2}. Grows the + * {@code BitSet} if {@code pos2 > size}. + * + * @param pos1 + * beginning position. + * @param pos2 + * ending position. + * @throws IndexOutOfBoundsException + * if {@code pos1} or {@code pos2} is negative, or if + * {@code pos2} is smaller than {@code pos1}. + * @see #clear(int) + * @since Android 1.0 + */ + public void clear(int pos1, int pos2) { + if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) { + int last = (bits.length * ELM_SIZE); + if (pos1 >= last || pos1 == pos2) { + return; + } + if (pos2 > last) { + pos2 = last; + } + + int idx1 = pos1 / ELM_SIZE; + int idx2 = (pos2 - 1) / ELM_SIZE; + long factor1 = (~0L) << (pos1 % ELM_SIZE); + long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE)); + + if (idx1 == idx2) { + bits[idx1] &= ~(factor1 & factor2); + } else { + bits[idx1] &= ~factor1; + bits[idx2] &= ~factor2; + for (int i = idx1 + 1; i < idx2; i++) { + bits[i] = 0L; + } + } + } else { + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + } + + /** + * Flips the bit at index {@code pos}. Grows the {@code BitSet} if + * {@code pos > size}. + * + * @param pos + * the index of the bit to flip. + * @throws IndexOutOfBoundsException + * if {@code pos} is negative. + * @see #flip(int, int) + * @since Android 1.0 + */ + public void flip(int pos) { + if (pos >= 0) { + if (pos >= bits.length * ELM_SIZE) { + growBits(pos); + } + bits[pos / ELM_SIZE] ^= 1L << (pos % ELM_SIZE); + } else { + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + } + + /** + * Flips the bits starting from {@code pos1} to {@code pos2}. Grows the + * {@code BitSet} if {@code pos2 > size}. + * + * @param pos1 + * beginning position. + * @param pos2 + * ending position. + * @throws IndexOutOfBoundsException + * if {@code pos1} or {@code pos2} is negative, or if + * {@code pos2} is smaller than {@code pos1}. + * @see #flip(int) + * @since Android 1.0 + */ + public void flip(int pos1, int pos2) { + if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) { + if (pos1 == pos2) { + return; + } + if (pos2 >= bits.length * ELM_SIZE) { + growBits(pos2); + } + + int idx1 = pos1 / ELM_SIZE; + int idx2 = (pos2 - 1) / ELM_SIZE; + long factor1 = (~0L) << (pos1 % ELM_SIZE); + long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE)); + + if (idx1 == idx2) { + bits[idx1] ^= (factor1 & factor2); + } else { + bits[idx1] ^= factor1; + bits[idx2] ^= factor2; + for (int i = idx1 + 1; i < idx2; i++) { + bits[i] ^= (~0L); + } + } + } else { + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + } + + /** + * Checks if these two {@code BitSet}s have at least one bit set to true in the same + * position. + * + * @param bs + * {@code BitSet} used to calculate the intersection. + * @return {@code true} if bs intersects with this {@code BitSet}, + * {@code false} otherwise. + * @since Android 1.0 + */ + public boolean intersects(BitSet bs) { + long[] bsBits = bs.bits; + int length1 = bits.length, length2 = bsBits.length; + + if (length1 <= length2) { + for (int i = 0; i < length1; i++) { + if ((bits[i] & bsBits[i]) != 0L) { + return true; + } + } + } else { + for (int i = 0; i < length2; i++) { + if ((bits[i] & bsBits[i]) != 0L) { + return true; + } + } + } + + return false; + } + + /** + * Performs the logical AND of this {@code BitSet} with another + * {@code BitSet}. The values of this {@code BitSet} are changed accordingly. + * + * @param bs + * {@code BitSet} to AND with. + * @see #or + * @see #xor + * @since Android 1.0 + */ + + public void and(BitSet bs) { + long[] bsBits = bs.bits; + int length1 = bits.length, length2 = bsBits.length; + if (length1 <= length2) { + for (int i = 0; i < length1; i++) { + bits[i] &= bsBits[i]; + } + } else { + for (int i = 0; i < length2; i++) { + bits[i] &= bsBits[i]; + } + for (int i = length2; i < length1; i++) { + bits[i] = 0; + } + } + } + + /** + * Clears all bits in the receiver which are also set in the parameter + * {@code BitSet}. The values of this {@code BitSet} are changed accordingly. + * + * @param bs + * {@code BitSet} to ANDNOT with. + * @since Android 1.0 + */ + public void andNot(BitSet bs) { + long[] bsBits = bs.bits; + int range = bits.length < bsBits.length ? bits.length : bsBits.length; + for (int i = 0; i < range; i++) { + bits[i] &= ~bsBits[i]; + } + } + + /** + * Performs the logical OR of this {@code BitSet} with another {@code BitSet}. + * The values of this {@code BitSet} are changed accordingly. + * + * @param bs + * {@code BitSet} to OR with. + * @see #xor + * @see #and + * @since Android 1.0 + */ + public void or(BitSet bs) { + int nbits = bs.length(); + int length = nbits / ELM_SIZE + (nbits % ELM_SIZE > 0 ? 1 : 0); + if (length > bits.length) { + growBits(nbits - 1); + } + long[] bsBits = bs.bits; + for (int i = 0; i < length; i++) { + bits[i] |= bsBits[i]; + } + } + + /** + * Performs the logical XOR of this {@code BitSet} with another {@code BitSet}. + * The values of this {@code BitSet} are changed accordingly. + * + * @param bs + * {@code BitSet} to XOR with. + * @see #or + * @see #and + * @since Android 1.0 + */ + public void xor(BitSet bs) { + int nbits = bs.length(); + int length = nbits / ELM_SIZE + (nbits % ELM_SIZE > 0 ? 1 : 0); + if (length > bits.length) { + growBits(nbits - 1); + } + long[] bsBits = bs.bits; + for (int i = 0; i < length; i++) { + bits[i] ^= bsBits[i]; + } + + } + + /** + * Returns the number of bits this {@code BitSet} has. + * + * @return the number of bits contained in this {@code BitSet}. + * @see #length + * @since Android 1.0 + */ + public int size() { + return bits.length * ELM_SIZE; + } + + /** + * Returns the number of bits up to and including the highest bit set. + * + * @return the length of the {@code BitSet}. + * @since Android 1.0 + */ + public int length() { + int idx = bits.length - 1; + while (idx >= 0 && bits[idx] == 0) { + --idx; + } + if (idx == -1) { + return 0; + } + int i = ELM_SIZE - 1; + long val = bits[idx]; + while ((val & (1L << i)) == 0 && i > 0) { + i--; + } + return idx * ELM_SIZE + i + 1; + } + + /** + * Returns a string containing a concise, human-readable description of the + * receiver. + * + * @return a comma delimited list of the indices of all bits that are set. + * @since Android 1.0 + */ + @Override + public String toString() { + StringBuffer sb = new StringBuffer(bits.length / 2); + int bitCount = 0; + sb.append('{'); + boolean comma = false; + for (int i = 0; i < bits.length; i++) { + if (bits[i] == 0) { + bitCount += ELM_SIZE; + continue; + } + for (int j = 0; j < ELM_SIZE; j++) { + if (((bits[i] & (1L << j)) != 0)) { + if (comma) { + sb.append(", "); //$NON-NLS-1$ + } + sb.append(bitCount); + comma = true; + } + bitCount++; + } + } + sb.append('}'); + return sb.toString(); + } + + /** + * Returns the position of the first bit that is {@code true} on or after {@code pos}. + * + * @param pos + * the starting position (inclusive). + * @return -1 if there is no bits that are set to {@code true} on or after {@code pos}. + * @since Android 1.0 + */ + public int nextSetBit(int pos) { + if (pos >= 0) { + if (pos >= bits.length * ELM_SIZE) { + return -1; + } + + int idx = pos / ELM_SIZE; + // first check in the same bit set element + if (bits[idx] != 0L) { + for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++) { + if (((bits[idx] & (1L << j)) != 0)) { + return idx * ELM_SIZE + j; + } + } + + } + idx++; + while (idx < bits.length && bits[idx] == 0L) { + idx++; + } + if (idx == bits.length) { + return -1; + } + + // we know for sure there is a bit set to true in this element + // since the bitset value is not 0L + for (int j = 0; j < ELM_SIZE; j++) { + if (((bits[idx] & (1L << j)) != 0)) { + return idx * ELM_SIZE + j; + } + } + + return -1; + } + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + + /** + * Returns the position of the first bit that is {@code false} on or after {@code pos}. + * + * @param pos + * the starting position (inclusive). + * @return the position of the next bit set to {@code false}, even if it is further + * than this {@code BitSet}'s size. + * @since Android 1.0 + */ + public int nextClearBit(int pos) { + if (pos >= 0) { + int bssize = bits.length * ELM_SIZE; + if (pos >= bssize) { + return pos; + } + + int idx = pos / ELM_SIZE; + // first check in the same bit set element + if (bits[idx] != (~0L)) { + for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++) { + if (((bits[idx] & (1L << j)) == 0)) { + return idx * ELM_SIZE + j; + } + } + + } + idx++; + while (idx < bits.length && bits[idx] == (~0L)) { + idx++; + } + if (idx == bits.length) { + return bssize; + } + + // we know for sure there is a bit set to true in this element + // since the bitset value is not 0L + for (int j = 0; j < ELM_SIZE; j++) { + if (((bits[idx] & (1L << j)) == 0)) { + return idx * ELM_SIZE + j; + } + } + + return bssize; + } + throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$ + } + + /** + * Returns true if all the bits in this {@code BitSet} are set to false. + * + * @return {@code true} if the {@code BitSet} is empty, + * {@code false} otherwise. + * @since Android 1.0 + */ + public boolean isEmpty() { + for (int idx = 0; idx < bits.length; idx++) { + if (bits[idx] != 0L) { + return false; + } + } + + return true; + } + + /** + * Returns the number of bits that are {@code true} in this {@code BitSet}. + * + * @return the number of {@code true} bits in the set. + * @since Android 1.0 + */ + public int cardinality() { + int count = 0; + for (int idx = 0; idx < bits.length; idx++) { + long temp = bits[idx]; + if (temp != 0L) { + for (int i = 0; i < ELM_SIZE; i++) { + if ((temp & (1L << i)) != 0L) { + count++; + } + } + } + } + return count; + } +} |