1917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/* 2917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Copyright (C) 2008 The Android Open Source Project 3917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 4917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Licensed under the Apache License, Version 2.0 (the "License"); 5917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * you may not use this file except in compliance with the License. 6917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * You may obtain a copy of the License at 7917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 8917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * http://www.apache.org/licenses/LICENSE-2.0 9917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 10917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Unless required by applicable law or agreed to in writing, software 11917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * distributed under the License is distributed on an "AS IS" BASIS, 12917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * See the License for the specific language governing permissions and 14917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * limitations under the License. 15917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 16917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 17917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpackage com.android.dexgen.util; 18917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 19917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulimport java.util.NoSuchElementException; 20917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 21917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/** 22917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * A set of integers, represented by a bit set 23917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 24917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpublic class BitIntSet implements IntSet { 25917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 26917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** also accessed in ListIntSet */ 27917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int[] bits; 28917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 29917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 30917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Constructs an instance. 31917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 32917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param max the maximum value of ints in this set. 33917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 34917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public BitIntSet(int max) { 35917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul bits = Bits.makeBitSet(max); 36917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 37917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 38917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 39917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void add(int value) { 40917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ensureCapacity(value); 41917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul Bits.set(bits, value, true); 42917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 43917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 44917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 45917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Ensures that the bit set has the capacity to represent the given value. 46917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 47917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value {@code >= 0;} value to represent 48917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 49917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private void ensureCapacity(int value) { 50917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (value >= Bits.getMax(bits)) { 51917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int[] newBits = Bits.makeBitSet( 52917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul Math.max(value + 1, 2 * Bits.getMax(bits))); 53917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul System.arraycopy(bits, 0, newBits, 0, bits.length); 54917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul bits = newBits; 55917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 56917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 57917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 58917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 59917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void remove(int value) { 60917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (value < Bits.getMax(bits)) { 61917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul Bits.set(bits, value, false); 62917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 63917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 64917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 65917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 66917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public boolean has(int value) { 67917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return (value < Bits.getMax(bits)) && Bits.get(bits, value); 68917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 69917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 70917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 71917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void merge(IntSet other) { 72917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (other instanceof BitIntSet) { 73917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul BitIntSet o = (BitIntSet) other; 74917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ensureCapacity(Bits.getMax(o.bits) + 1); 75917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul Bits.or(bits, o.bits); 76917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } else if (other instanceof ListIntSet) { 77917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ListIntSet o = (ListIntSet) other; 78917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int sz = o.ints.size(); 79917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 80917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (sz > 0) { 81917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ensureCapacity(o.ints.get(sz - 1)); 82917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 83917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < o.ints.size(); i++) { 84917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul Bits.set(bits, o.ints.get(i), true); 85917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 86917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } else { 87917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntIterator iter = other.iterator(); 88917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul while (iter.hasNext()) { 89917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul add(iter.next()); 90917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 91917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 92917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 93917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 94917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 95917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int elements() { 96917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return Bits.bitCount(bits); 97917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 98917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 99917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 100917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public IntIterator iterator() { 101917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return new IntIterator() { 102917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private int idx = Bits.findFirst(bits, 0); 103917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 104917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 105917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public boolean hasNext() { 106917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return idx >= 0; 107917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 108917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 109917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 110917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int next() { 111917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (!hasNext()) { 112917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new NoSuchElementException(); 113917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 114917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 115917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int ret = idx; 116917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 117917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul idx = Bits.findFirst(bits, idx+1); 118917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 119917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return ret; 120917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 121917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul }; 122917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 123917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 124917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** @inheritDoc */ 125917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public String toString() { 126917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul StringBuilder sb = new StringBuilder(); 127917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 128917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sb.append('{'); 129917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 130917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul boolean first = true; 131917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = Bits.findFirst(bits, 0) 132917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ; i >= 0 133917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul ; i = Bits.findFirst(bits, i + 1)) { 134917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (!first) { 135917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sb.append(", "); 136917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 137917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul first = false; 138917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sb.append(i); 139917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 140917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 141917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sb.append('}'); 142917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 143917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return sb.toString(); 144917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 145917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul} 146