1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Licensed to the Apache Software Foundation (ASF) under one or more 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * contributor license agreements. See the NOTICE file distributed with 4adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this work for additional information regarding copyright ownership. 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The ASF licenses this file to You under the Apache License, Version 2.0 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (the "License"); you may not use this file except in compliance with 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the License. You may obtain a copy of the License at 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 9adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 10adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unless required by applicable law or agreed to in writing, software 12adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * See the License for the specific language governing permissions and 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * limitations under the License. 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util; 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilsonimport java.io.IOException; 21f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilsonimport java.io.ObjectInputStream; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.Serializable; 2327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughesimport java.nio.ByteBuffer; 2427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughesimport java.nio.ByteOrder; 2527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughesimport java.nio.LongBuffer; 2627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughesimport libcore.io.SizeOf; 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 2927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * The {@code BitSet} class implements a 3027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * <a href="http://en.wikipedia.org/wiki/Bit_array">bit array</a>. 3127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Each element is either true or false. A {@code BitSet} is created with a given size and grows 3227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * automatically if this size is exceeded. 33adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class BitSet implements Serializable, Cloneable { 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = 7997698588986878753L; 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 3727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes private static final long ALL_ONES = ~0L; 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 3927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 4027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * The bits. Access bit n thus: 4127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * 4227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * boolean bit = (bits[n / 64] | (1 << n)) != 0; 4327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * 4427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Note that Java's shift operators truncate their rhs to the log2 size of the lhs. 4527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * That is, there's no "% 64" needed because it's implicit in the shift. 4627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * 4727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * TODO: would int[] be significantly more efficient for Android at the moment? 4827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private long[] bits; 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 5127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 5227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * The number of elements of 'bits' that are actually in use (non-zero). Amongst other 5327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * things, this guarantees that isEmpty is cheap, because we never have to examine the array. 5427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 5527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes private transient int longCount; 56f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 5727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 5827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Updates 'longCount' by inspecting 'bits'. Assumes that the new longCount is <= the current 5927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * longCount, to avoid scanning large tracts of empty array. This means it's safe to call 6027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * directly after a clear operation that may have cleared the highest set bit, but 6127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * not safe after an xor operation that may have cleared the highest set bit or 6227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * made a new highest set bit. In that case, you'd need to set 'longCount' to a conservative 6327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * estimate before calling this method. 6427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 6527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes private void shrinkSize() { 6627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int i = longCount - 1; 6727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes while (i >= 0 && bits[i] == 0) { 6827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes --i; 6927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 7027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes this.longCount = i + 1; 7127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 72f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 7427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Creates a new {@code BitSet} with size equal to 64 bits. 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BitSet() { 7727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes this(new long[1]); 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 79adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 8127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Creates a new {@code BitSet} with size equal to {@code bitCount}, rounded up to 8227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * a multiple of 64. 83f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 8452c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws NegativeArraySizeException if {@code bitCount < 0}. 8527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 8627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public BitSet(int bitCount) { 8727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (bitCount < 0) { 88834ce234b54466ba230b3c7199d4363a837c5628Elliott Hughes throw new NegativeArraySizeException(Integer.toString(bitCount)); 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 9027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes this.bits = arrayForBits(bitCount); 9127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes this.longCount = 0; 92adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 93adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 9427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes private BitSet(long[] bits) { 95adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this.bits = bits; 9627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes this.longCount = bits.length; 9727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes shrinkSize(); 98adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 10027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes private static long[] arrayForBits(int bitCount) { 10152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes return new long[(bitCount + 63)/ 64]; 10227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 10327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 10427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes @Override public Object clone() { 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project BitSet clone = (BitSet) super.clone(); 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project clone.bits = bits.clone(); 10827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes clone.shrinkSize(); 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return clone; 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } catch (CloneNotSupportedException e) { 111fb0ec0e650bf8be35acb0d47da0311a7c446aa33Elliott Hughes throw new AssertionError(e); 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 113adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 11527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes @Override public boolean equals(Object o) { 11627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (this == o) { 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 11927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (!(o instanceof BitSet)) { 12027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return false; 12127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 12227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes BitSet lhs = (BitSet) o; 12327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (this.longCount != lhs.longCount) { 12427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return false; 12527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 12627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 0; i < longCount; ++i) { 12727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (bits[i] != lhs.bits[i]) { 128f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return false; 129f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 13127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return true; 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 13527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Ensures that our long[] can hold at least 64 * desiredLongCount bits. 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 13727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes private void ensureCapacity(int desiredLongCount) { 13827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (desiredLongCount <= bits.length) { 13927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return; 14027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 14127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int newLength = Math.max(desiredLongCount, bits.length * 2); 14227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long[] newBits = new long[newLength]; 14327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes System.arraycopy(bits, 0, newBits, 0, longCount); 14427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes this.bits = newBits; 14527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // 'longCount' is unchanged by this operation: the long[] is larger, 14627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // but you're not yet using any more of it. 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 14927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes @Override public int hashCode() { 15027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // The RI doesn't use Arrays.hashCode, and explicitly specifies this algorithm. 151adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long x = 1234; 15227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 0; i < longCount; ++i) { 153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project x ^= bits[i] * (i + 1); 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 155adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return (int) ((x >> 32) ^ x); 156adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 15927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Returns the bit at index {@code index}. Indexes greater than the current length return false. 160f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 16152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws IndexOutOfBoundsException if {@code index < 0}. 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 163b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes public boolean get(int index) { 16427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (index < 0) { // TODO: until we have an inlining JIT. 16527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes checkIndex(index); 166f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 16727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int arrayIndex = index / 64; 16827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (arrayIndex >= longCount) { 16927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return false; 17027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 17127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return (bits[arrayIndex] & (1L << index)) != 0; 17227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 17327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 17427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 17527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Sets the bit at index {@code index} to true. 17627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * 17752c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws IndexOutOfBoundsException if {@code index < 0}. 17827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 17927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public void set(int index) { 18027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (index < 0) { // TODO: until we have an inlining JIT. 18127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes checkIndex(index); 18227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 18327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int arrayIndex = index / 64; 18427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (arrayIndex >= bits.length) { 18527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes ensureCapacity(arrayIndex + 1); 18627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 18727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[arrayIndex] |= (1L << index); 18827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes longCount = Math.max(longCount, arrayIndex + 1); 18927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 19027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 19127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 19227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Clears the bit at index {@code index}. 19327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * 19452c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws IndexOutOfBoundsException if {@code index < 0}. 19527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 19627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public void clear(int index) { 19727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (index < 0) { // TODO: until we have an inlining JIT. 19827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes checkIndex(index); 19927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 20027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int arrayIndex = index / 64; 20127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (arrayIndex >= longCount) { 20227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return; 20327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 20427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[arrayIndex] &= ~(1L << index); 20527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes shrinkSize(); 20627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 20727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 20827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 20927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Flips the bit at index {@code index}. 21027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * 21152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws IndexOutOfBoundsException if {@code index < 0}. 21227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 21327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public void flip(int index) { 21427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (index < 0) { // TODO: until we have an inlining JIT. 21527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes checkIndex(index); 21627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 21727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int arrayIndex = index / 64; 21827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (arrayIndex >= bits.length) { 21927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes ensureCapacity(arrayIndex + 1); 22027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 22127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[arrayIndex] ^= (1L << index); 22227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes longCount = Math.max(longCount, arrayIndex + 1); 22327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes shrinkSize(); 224adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 225adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 226b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes private void checkIndex(int index) { 227b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes if (index < 0) { 228a1603838fe9e865575c87982e32c6343740e464cElliott Hughes throw new IndexOutOfBoundsException("index < 0: " + index); 229b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes } 230b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes } 231b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes 232b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes private void checkRange(int fromIndex, int toIndex) { 233a1603838fe9e865575c87982e32c6343740e464cElliott Hughes if ((fromIndex | toIndex) < 0 || toIndex < fromIndex) { 234b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes throw new IndexOutOfBoundsException("fromIndex=" + fromIndex + " toIndex=" + toIndex); 235b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes } 236b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes } 237b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes 238adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 23927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Returns a new {@code BitSet} containing the 24027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * range of bits {@code [fromIndex, toIndex)}, shifted down so that the bit 24127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * at {@code fromIndex} is at bit 0 in the new {@code BitSet}. 242f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 243adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 244b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes * if {@code fromIndex} or {@code toIndex} is negative, or if 245b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes * {@code toIndex} is smaller than {@code fromIndex}. 246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 247b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes public BitSet get(int fromIndex, int toIndex) { 248b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes checkRange(fromIndex, toIndex); 249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 25027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int last = 64 * longCount; 251b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes if (fromIndex >= last || fromIndex == toIndex) { 252f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return new BitSet(0); 253f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 254b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes if (toIndex > last) { 255b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes toIndex = last; 256f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 257adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 25827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int firstArrayIndex = fromIndex / 64; 25927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int lastArrayIndex = (toIndex - 1) / 64; 26027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long lowMask = ALL_ONES << fromIndex; 26127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long highMask = ALL_ONES >>> -toIndex; 262f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 26327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (firstArrayIndex == lastArrayIndex) { 26427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long result = (bits[firstArrayIndex] & (lowMask & highMask)) >>> fromIndex; 265f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson if (result == 0) { 266f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return new BitSet(0); 267adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 26827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return new BitSet(new long[] { result }); 269f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 270f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 27127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long[] newBits = new long[lastArrayIndex - firstArrayIndex + 1]; 27227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 27327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // first fill in the first and last indexes in the new BitSet 27427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes newBits[0] = bits[firstArrayIndex] & lowMask; 27527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes newBits[newBits.length - 1] = bits[lastArrayIndex] & highMask; 27627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 27727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // fill in the in between elements of the new BitSet 27827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 1; i < lastArrayIndex - firstArrayIndex; i++) { 27927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes newBits[i] = bits[firstArrayIndex + i]; 280f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 281adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 28227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // shift all the elements in the new BitSet to the right 28327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int numBitsToShift = fromIndex % 64; 28427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int actualLen = newBits.length; 285f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson if (numBitsToShift != 0) { 28627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 0; i < newBits.length; i++) { 287f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson // shift the current element to the right regardless of 288f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson // sign 28927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes newBits[i] = newBits[i] >>> (numBitsToShift); 290f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 29127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // apply the last x bits of newBits[i+1] to the current 292f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson // element 29327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (i != newBits.length - 1) { 29427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes newBits[i] |= newBits[i + 1] << -numBitsToShift; 295f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 29627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (newBits[i] != 0) { 297f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson actualLen = i + 1; 298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 299adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 300adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 30127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return new BitSet(newBits); 302adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 303adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 304adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 30527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Sets the bit at index {@code index} to {@code state}. 306f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 30752c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws IndexOutOfBoundsException if {@code index < 0}. 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 30927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public void set(int index, boolean state) { 31027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (state) { 311b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes set(index); 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 313b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes clear(index); 314adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 315adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 316adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 317adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 31827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Sets the range of bits {@code [fromIndex, toIndex)} to {@code state}. 319f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 320adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 321b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes * if {@code fromIndex} or {@code toIndex} is negative, or if 322b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes * {@code toIndex} is smaller than {@code fromIndex}. 323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 32427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public void set(int fromIndex, int toIndex, boolean state) { 32527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (state) { 326b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes set(fromIndex, toIndex); 327adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 328b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes clear(fromIndex, toIndex); 329adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 33327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Clears all the bits in this {@code BitSet}. This method does not change the capacity. 33427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Use {@code clear} if you want to reuse this {@code BitSet} with the same capacity, but 33527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * create a new {@code BitSet} if you're trying to potentially reclaim memory. 336adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 337adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 33827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes Arrays.fill(bits, 0, longCount, 0L); 33927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes longCount = 0; 340adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 341adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 342adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 34327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Sets the range of bits {@code [fromIndex, toIndex)}. 344f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 34627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * if {@code fromIndex} or {@code toIndex} is negative, or if 34727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * {@code toIndex} is smaller than {@code fromIndex}. 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 34927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public void set(int fromIndex, int toIndex) { 35027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes checkRange(fromIndex, toIndex); 35127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (fromIndex == toIndex) { 352f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return; 353f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 35427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int firstArrayIndex = fromIndex / 64; 35527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int lastArrayIndex = (toIndex - 1) / 64; 35627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (lastArrayIndex >= bits.length) { 35727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes ensureCapacity(lastArrayIndex + 1); 35827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 35927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 36027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long lowMask = ALL_ONES << fromIndex; 36127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long highMask = ALL_ONES >>> -toIndex; 36227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (firstArrayIndex == lastArrayIndex) { 36327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[firstArrayIndex] |= (lowMask & highMask); 36427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } else { 36527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int i = firstArrayIndex; 36627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i++] |= lowMask; 36727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes while (i < lastArrayIndex) { 36827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i++] |= ALL_ONES; 369f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 37027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i++] |= highMask; 371f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 37227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes longCount = Math.max(longCount, lastArrayIndex + 1); 373adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 37627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Clears the range of bits {@code [fromIndex, toIndex)}. 377f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 379b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes * if {@code fromIndex} or {@code toIndex} is negative, or if 380b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes * {@code toIndex} is smaller than {@code fromIndex}. 381adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 382b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes public void clear(int fromIndex, int toIndex) { 383b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes checkRange(fromIndex, toIndex); 38427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (fromIndex == toIndex || longCount == 0) { 385f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return; 386f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 38727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int last = 64 * longCount; 38827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (fromIndex >= last) { 389f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return; 390f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 391b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes if (toIndex > last) { 392b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes toIndex = last; 393f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 39427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int firstArrayIndex = fromIndex / 64; 39527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int lastArrayIndex = (toIndex - 1) / 64; 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 39727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long lowMask = ALL_ONES << fromIndex; 39827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long highMask = ALL_ONES >>> -toIndex; 39927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (firstArrayIndex == lastArrayIndex) { 40027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[firstArrayIndex] &= ~(lowMask & highMask); 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 40227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int i = firstArrayIndex; 40327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i++] &= ~lowMask; 40427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes while (i < lastArrayIndex) { 40527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i++] = 0L; 406f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 40727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i++] &= ~highMask; 408f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 40927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes shrinkSize(); 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 411adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 412adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 41327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Flips the range of bits {@code [fromIndex, toIndex)}. 414f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IndexOutOfBoundsException 416b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes * if {@code fromIndex} or {@code toIndex} is negative, or if 417b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes * {@code toIndex} is smaller than {@code fromIndex}. 418adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 419b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes public void flip(int fromIndex, int toIndex) { 420b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes checkRange(fromIndex, toIndex); 421b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes if (fromIndex == toIndex) { 422f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return; 423f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 42427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int firstArrayIndex = fromIndex / 64; 42527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int lastArrayIndex = (toIndex - 1) / 64; 42627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (lastArrayIndex >= bits.length) { 42727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes ensureCapacity(lastArrayIndex + 1); 428f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 429adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 43027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long lowMask = ALL_ONES << fromIndex; 43127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long highMask = ALL_ONES >>> -toIndex; 43227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (firstArrayIndex == lastArrayIndex) { 43327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[firstArrayIndex] ^= (lowMask & highMask); 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 43527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int i = firstArrayIndex; 43627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i++] ^= lowMask; 43727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes while (i < lastArrayIndex) { 43827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i++] ^= ALL_ONES; 439f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 44027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i++] ^= highMask; 441adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 44227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes longCount = Math.max(longCount, lastArrayIndex + 1); 44327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes shrinkSize(); 444adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 446adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 44727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Returns true if {@code this.and(bs)} is non-empty, but may be faster than computing that. 448adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 449adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean intersects(BitSet bs) { 450adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long[] bsBits = bs.bits; 45127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int length = Math.min(this.longCount, bs.longCount); 45227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 0; i < length; ++i) { 45327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if ((bits[i] & bsBits[i]) != 0L) { 45427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return true; 455adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 456adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 457adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 458adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 459adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 460adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 46127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Logically ands the bits of this {@code BitSet} with {@code bs}. 462adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 463adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void and(BitSet bs) { 46427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int minSize = Math.min(this.longCount, bs.longCount); 46527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 0; i < minSize; ++i) { 46627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i] &= bs.bits[i]; 467f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 46827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes Arrays.fill(bits, minSize, longCount, 0L); 46927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes shrinkSize(); 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 47327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Clears all bits in this {@code BitSet} which are also set in {@code bs}. 474adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 475adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void andNot(BitSet bs) { 47627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int minSize = Math.min(this.longCount, bs.longCount); 47727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 0; i < minSize; ++i) { 47827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i] &= ~bs.bits[i]; 479adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 48027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes shrinkSize(); 481adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 483adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 48427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Logically ors the bits of this {@code BitSet} with {@code bs}. 485adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void or(BitSet bs) { 48752c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes int minSize = Math.min(this.longCount, bs.longCount); 48827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int maxSize = Math.max(this.longCount, bs.longCount); 48927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes ensureCapacity(maxSize); 49052c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes for (int i = 0; i < minSize; ++i) { 49127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i] |= bs.bits[i]; 492adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 49352c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes if (bs.longCount > minSize) { 49452c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes System.arraycopy(bs.bits, minSize, bits, minSize, maxSize - minSize); 49552c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 49627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes longCount = maxSize; 497adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 499adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 50027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Logically xors the bits of this {@code BitSet} with {@code bs}. 501adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 502adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void xor(BitSet bs) { 50352c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes int minSize = Math.min(this.longCount, bs.longCount); 50427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int maxSize = Math.max(this.longCount, bs.longCount); 50527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes ensureCapacity(maxSize); 50652c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes for (int i = 0; i < minSize; ++i) { 50727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes bits[i] ^= bs.bits[i]; 508adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 50952c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes if (bs.longCount > minSize) { 51052c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes System.arraycopy(bs.bits, minSize, bits, minSize, maxSize - minSize); 51152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 51227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes longCount = maxSize; 51327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes shrinkSize(); 514adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 516adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 51727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Returns the capacity in bits of the array implementing this {@code BitSet}. This is 51827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * unrelated to the length of the {@code BitSet}, and not generally useful. 51927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Use {@link #nextSetBit} to iterate, or {@link #length} to find the highest set bit. 520adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 521adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 52227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return bits.length * 64; 523adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 524adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 525adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 52627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Returns the number of bits up to and including the highest bit set. This is unrelated to 52727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * the {@link #size} of the {@code BitSet}. 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 529adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int length() { 53027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (longCount == 0) { 531adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return 0; 532adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 53327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return 64 * (longCount - 1) + (64 - Long.numberOfLeadingZeros(bits[longCount - 1])); 534adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 535adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 536adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 537adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a string containing a concise, human-readable description of the 53827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * receiver: a comma-delimited list of the indexes of all set bits. 53927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * For example: {@code "{0,1,8}"}. 540adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 54127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes @Override public String toString() { 54227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes //System.err.println("BitSet[longCount=" + longCount + ",bits=" + Arrays.toString(bits) + "]"); 54327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes StringBuilder sb = new StringBuilder(longCount / 2); 544adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project sb.append('{'); 545adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean comma = false; 54627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 0; i < longCount; ++i) { 54727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (bits[i] != 0) { 54827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int j = 0; j < 64; ++j) { 54927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if ((bits[i] & 1L << j) != 0) { 55027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (comma) { 55127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes sb.append(", "); 55227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } else { 55327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes comma = true; 55427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 55527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes sb.append(64 * i + j); 556adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 557adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 558adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 559adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 560adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project sb.append('}'); 561adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return sb.toString(); 562adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 563adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 564adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 56552c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * Returns the index of the first bit that is set on or after {@code index}, or -1 56652c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * if no higher bits are set. 56752c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws IndexOutOfBoundsException if {@code index < 0}. 568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 569b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes public int nextSetBit(int index) { 570b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes checkIndex(index); 57127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int arrayIndex = index / 64; 57227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (arrayIndex >= longCount) { 573f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return -1; 574f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 57527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long mask = ALL_ONES << index; 57627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if ((bits[arrayIndex] & mask) != 0) { 57727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return 64 * arrayIndex + Long.numberOfTrailingZeros(bits[arrayIndex] & mask); 578f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 57927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes while (++arrayIndex < longCount && bits[arrayIndex] == 0) { 580f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 58127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (arrayIndex == longCount) { 582adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return -1; 583adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 58427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return 64 * arrayIndex + Long.numberOfTrailingZeros(bits[arrayIndex]); 585adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 586adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 587adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 58852c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * Returns the index of the first bit that is clear on or after {@code index}. 58927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Since all bits past the end are implicitly clear, this never returns -1. 59052c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws IndexOutOfBoundsException if {@code index < 0}. 591adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 592b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes public int nextClearBit(int index) { 593b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes checkIndex(index); 59427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int arrayIndex = index / 64; 59527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (arrayIndex >= longCount) { 596b1396870f92135aa140bd2b86221768dea5bc11dElliott Hughes return index; 597f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 59827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long mask = ALL_ONES << index; 59927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if ((~bits[arrayIndex] & mask) != 0) { 60027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return 64 * arrayIndex + Long.numberOfTrailingZeros(~bits[arrayIndex] & mask); 601f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 60227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes while (++arrayIndex < longCount && bits[arrayIndex] == ALL_ONES) { 603f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 60427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes if (arrayIndex == longCount) { 605049ddf9438b4707faccf7bf01abcc3a24eaf9978Elliott Hughes return 64 * longCount; 606adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 60727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return 64 * arrayIndex + Long.numberOfTrailingZeros(~bits[arrayIndex]); 608adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 61152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * Returns the index of the first bit that is set on or before {@code index}, or -1 if 61252c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * no lower bits are set or {@code index == -1}. 61352c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws IndexOutOfBoundsException if {@code index < -1}. 6148ffa0b68c9fd3f722bee2bcd94b1d38151a0791dElliott Hughes * @since 1.7 61552c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes */ 61652c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes public int previousSetBit(int index) { 61752c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes if (index == -1) { 61852c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes return -1; 61952c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 62052c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes checkIndex(index); 62152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes // TODO: optimize this. 62252c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes for (int i = index; i >= 0; --i) { 62352c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes if (get(i)) { 62452c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes return i; 62552c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 62652c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 62752c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes return -1; 62852c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 62952c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes 63052c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes /** 63152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * Returns the index of the first bit that is clear on or before {@code index}, or -1 if 63252c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * no lower bits are clear or {@code index == -1}. 63352c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * @throws IndexOutOfBoundsException if {@code index < -1}. 6348ffa0b68c9fd3f722bee2bcd94b1d38151a0791dElliott Hughes * @since 1.7 63552c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes */ 63652c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes public int previousClearBit(int index) { 63752c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes if (index == -1) { 63852c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes return -1; 63952c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 64052c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes checkIndex(index); 64152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes // TODO: optimize this. 64252c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes for (int i = index; i >= 0; --i) { 64352c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes if (!get(i)) { 64452c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes return i; 64552c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 64652c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 64752c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes return -1; 64852c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 64952c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes 65052c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes /** 65127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Returns true if all the bits in this {@code BitSet} are set to false, false otherwise. 652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 653adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean isEmpty() { 65427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return (longCount == 0); 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of bits that are {@code true} in this {@code BitSet}. 659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int cardinality() { 661df1414c93940bc672af318237a8a5e38e0b64e70Elliott Hughes int result = 0; 66227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 0; i < longCount; ++i) { 663df1414c93940bc672af318237a8a5e38e0b64e70Elliott Hughes result += Long.bitCount(bits[i]); 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 665df1414c93940bc672af318237a8a5e38e0b64e70Elliott Hughes return result; 666f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 667f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 66827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 66927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Equivalent to {@code BitSet.valueOf(LongBuffer.wrap(longs))}, but likely to be faster. 67027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * This is likely to be the fastest way to create a {@code BitSet} because it's closest 67127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * to the internal representation. 6728ffa0b68c9fd3f722bee2bcd94b1d38151a0791dElliott Hughes * @since 1.7 67327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 67427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public static BitSet valueOf(long[] longs) { 67527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return new BitSet(longs.clone()); 67627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 67727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 67827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 67927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Returns a {@code BitSet} corresponding to {@code longBuffer}, interpreted as a little-endian 68027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * sequence of bits. This method does not alter the {@code LongBuffer}. 6818ffa0b68c9fd3f722bee2bcd94b1d38151a0791dElliott Hughes * @since 1.7 68227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 68327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public static BitSet valueOf(LongBuffer longBuffer) { 68427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // The bulk get would mutate LongBuffer (even if we reset position later), and it's not 68527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // clear that's allowed. My assumption is that it's the long[] variant that's the common 68627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // case anyway, so copy the buffer into a long[]. 68727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long[] longs = new long[longBuffer.remaining()]; 68827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes for (int i = 0; i < longs.length; ++i) { 68927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes longs[i] = longBuffer.get(longBuffer.position() + i); 69027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 69127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return BitSet.valueOf(longs); 69227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 69327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 69427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 69527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Equivalent to {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}. 6968ffa0b68c9fd3f722bee2bcd94b1d38151a0791dElliott Hughes * @since 1.7 69727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 69827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public static BitSet valueOf(byte[] bytes) { 69927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return BitSet.valueOf(ByteBuffer.wrap(bytes)); 70027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 70127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 70227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 70327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * Returns a {@code BitSet} corresponding to {@code byteBuffer}, interpreted as a little-endian 70427a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes * sequence of bits. This method does not alter the {@code ByteBuffer}. 7058ffa0b68c9fd3f722bee2bcd94b1d38151a0791dElliott Hughes * @since 1.7 70627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 70727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public static BitSet valueOf(ByteBuffer byteBuffer) { 70827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes byteBuffer = byteBuffer.slice().order(ByteOrder.LITTLE_ENDIAN); 70927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes long[] longs = arrayForBits(byteBuffer.remaining() * 8); 71027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes int i = 0; 71127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes while (byteBuffer.remaining() >= SizeOf.LONG) { 71227a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes longs[i++] = byteBuffer.getLong(); 71327a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 71452c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes for (int j = 0; byteBuffer.hasRemaining(); ++j) { 71552c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes longs[i] |= ((((long) byteBuffer.get()) & 0xff) << (8*j)); 71627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 71727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return BitSet.valueOf(longs); 71827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 71927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 72027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes /** 72152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * Returns a new {@code long[]} containing a little-endian representation of the bits of 72252c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * this {@code BitSet}, suitable for passing to {@code valueOf} to reconstruct 72352c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * this {@code BitSet}. 7248ffa0b68c9fd3f722bee2bcd94b1d38151a0791dElliott Hughes * @since 1.7 72527a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes */ 72627a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes public long[] toLongArray() { 72727a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes return Arrays.copyOf(bits, longCount); 72827a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes } 72927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes 73052c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes /** 73152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * Returns a new {@code byte[]} containing a little-endian representation the bits of 73252c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * this {@code BitSet}, suitable for passing to {@code valueOf} to reconstruct 73352c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes * this {@code BitSet}. 7348ffa0b68c9fd3f722bee2bcd94b1d38151a0791dElliott Hughes * @since 1.7 73552c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes */ 73652c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes public byte[] toByteArray() { 73752c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes int bitCount = length(); 73852c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes byte[] result = new byte[(bitCount + 7)/ 8]; 73952c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes for (int i = 0; i < result.length; ++i) { 74052c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes int lowBit = 8 * i; 74152c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes int arrayIndex = lowBit / 64; 74252c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes result[i] = (byte) (bits[arrayIndex] >>> lowBit); 74352c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 74452c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes return result; 74552c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes } 74652c4cc5aa39d8e64cb7d57a86fa712ddb316d89dElliott Hughes 747df1414c93940bc672af318237a8a5e38e0b64e70Elliott Hughes private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException { 748f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson ois.defaultReadObject(); 74927a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes // The serialized form doesn't include a 'longCount' field, so we'll have to scan the array. 75027a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes this.longCount = this.bits.length; 75127a5b793cc7ae8a72ba2f767214a828becdc64cdElliott Hughes shrinkSize(); 752f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 753adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 754