| /* |
| * 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; |
| } |
| } |
