1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2008 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.util; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.NoSuchElementException; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * A set of integers, represented by a bit set 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class BitIntSet implements IntSet { 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** also accessed in ListIntSet */ 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] bits; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param max the maximum value of ints in this set. 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BitIntSet(int max) { 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bits = Bits.makeBitSet(max); 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void add(int value) { 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ensureCapacity(value); 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(bits, value, true); 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Ensures that the bit set has the capacity to represent the given value. 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param value {@code >= 0;} value to represent 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void ensureCapacity(int value) { 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (value >= Bits.getMax(bits)) { 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] newBits = Bits.makeBitSet( 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Math.max(value + 1, 2 * Bits.getMax(bits))); 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.arraycopy(bits, 0, newBits, 0, bits.length); 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bits = newBits; 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void remove(int value) { 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (value < Bits.getMax(bits)) { 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(bits, value, false); 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean has(int value) { 67de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro return (value < Bits.getMax(bits)) && Bits.get(bits, value); 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void merge(IntSet other) { 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (other instanceof BitIntSet) { 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitIntSet o = (BitIntSet) other; 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ensureCapacity(Bits.getMax(o.bits) + 1); 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.or(bits, o.bits); 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (other instanceof ListIntSet) { 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ListIntSet o = (ListIntSet) other; 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = o.ints.size(); 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (sz > 0) { 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ensureCapacity(o.ints.get(sz - 1)); 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < o.ints.size(); i++) { 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Bits.set(bits, o.ints.get(i), true); 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntIterator iter = other.iterator(); 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (iter.hasNext()) { 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project add(iter.next()); 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int elements() { 96de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro return Bits.bitCount(bits); 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntIterator iterator() { 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new IntIterator() { 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int idx = Bits.findFirst(bits, 0); 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean hasNext() { 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return idx >= 0; 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int next() { 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!hasNext()) { 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NoSuchElementException(); 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ret = idx; 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project idx = Bits.findFirst(bits, idx+1); 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ret; 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project }; 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** @inheritDoc */ 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public String toString() { 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StringBuilder sb = new StringBuilder(); 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sb.append('{'); 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean first = true; 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = Bits.findFirst(bits, 0) 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ; i >= 0 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ; i = Bits.findFirst(bits, i + 1)) { 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!first) { 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sb.append(", "); 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project first = false; 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sb.append(i); 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sb.append('}'); 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return sb.toString(); 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 146