1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2008 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.util; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.NoSuchElementException; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * A set of integers, represented by a bit set 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic class BitIntSet implements IntSet { 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** also accessed in ListIntSet */ 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int[] bits; 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance. 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param max the maximum value of ints in this set. 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public BitIntSet(int max) { 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bits = Bits.makeBitSet(max); 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** @inheritDoc */ 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void add(int value) { 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ensureCapacity(value); 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Bits.set(bits, value, true); 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Ensures that the bit set has the capacity to represent the given value. 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value {@code >= 0;} value to represent 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void ensureCapacity(int value) { 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (value >= Bits.getMax(bits)) { 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int[] newBits = Bits.makeBitSet( 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Math.max(value + 1, 2 * Bits.getMax(bits))); 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.arraycopy(bits, 0, newBits, 0, bits.length); 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bits = newBits; 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** @inheritDoc */ 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void remove(int value) { 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (value < Bits.getMax(bits)) { 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Bits.set(bits, value, false); 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** @inheritDoc */ 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public boolean has(int value) { 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return (value < Bits.getMax(bits)) && Bits.get(bits, value); 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** @inheritDoc */ 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void merge(IntSet other) { 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (other instanceof BitIntSet) { 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitIntSet o = (BitIntSet) other; 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ensureCapacity(Bits.getMax(o.bits) + 1); 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Bits.or(bits, o.bits); 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else if (other instanceof ListIntSet) { 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ListIntSet o = (ListIntSet) other; 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = o.ints.size(); 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (sz > 0) { 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ensureCapacity(o.ints.get(sz - 1)); 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < o.ints.size(); i++) { 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Bits.set(bits, o.ints.get(i), true); 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntIterator iter = other.iterator(); 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (iter.hasNext()) { 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson add(iter.next()); 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** @inheritDoc */ 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int elements() { 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return Bits.bitCount(bits); 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** @inheritDoc */ 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntIterator iterator() { 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return new IntIterator() { 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int idx = Bits.findFirst(bits, 0); 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** @inheritDoc */ 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public boolean hasNext() { 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return idx >= 0; 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** @inheritDoc */ 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int next() { 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!hasNext()) { 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new NoSuchElementException(); 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int ret = idx; 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson idx = Bits.findFirst(bits, idx+1); 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return ret; 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson }; 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** @inheritDoc */ 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public String toString() { 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson StringBuilder sb = new StringBuilder(); 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append('{'); 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean first = true; 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = Bits.findFirst(bits, 0) 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ; i >= 0 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ; i = Bits.findFirst(bits, i + 1)) { 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!first) { 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(", "); 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson first = false; 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(i); 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append('}'); 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return sb.toString(); 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 146