| /* |
| * Copyright (C) 2008 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.dx.util; |
| |
| import java.util.NoSuchElementException; |
| |
| /** |
| * A set of integers, represented by a bit set |
| */ |
| public class BitIntSet implements IntSet { |
| |
| /** also accessed in ListIntSet */ |
| int[] bits; |
| |
| /** |
| * Constructs an instance. |
| * |
| * @param max the maximum value of ints in this set. |
| */ |
| public BitIntSet(int max) { |
| bits = Bits.makeBitSet(max); |
| } |
| |
| /** @inheritDoc */ |
| public void add(int value) { |
| ensureCapacity(value); |
| Bits.set(bits, value, true); |
| } |
| |
| /** |
| * Ensures that the bit set has the capacity to represent the given value. |
| * |
| * @param value {@code >= 0;} value to represent |
| */ |
| private void ensureCapacity(int value) { |
| if (value >= Bits.getMax(bits)) { |
| int[] newBits = Bits.makeBitSet( |
| Math.max(value + 1, 2 * Bits.getMax(bits))); |
| System.arraycopy(bits, 0, newBits, 0, bits.length); |
| bits = newBits; |
| } |
| } |
| |
| /** @inheritDoc */ |
| public void remove(int value) { |
| if (value < Bits.getMax(bits)) { |
| Bits.set(bits, value, false); |
| } |
| } |
| |
| /** @inheritDoc */ |
| public boolean has(int value) { |
| return (value < Bits.getMax(bits)) && Bits.get(bits, value); |
| } |
| |
| /** @inheritDoc */ |
| public void merge(IntSet other) { |
| if (other instanceof BitIntSet) { |
| BitIntSet o = (BitIntSet) other; |
| ensureCapacity(Bits.getMax(o.bits) + 1); |
| Bits.or(bits, o.bits); |
| } else if (other instanceof ListIntSet) { |
| ListIntSet o = (ListIntSet) other; |
| int sz = o.ints.size(); |
| |
| if (sz > 0) { |
| ensureCapacity(o.ints.get(sz - 1)); |
| } |
| for (int i = 0; i < o.ints.size(); i++) { |
| Bits.set(bits, o.ints.get(i), true); |
| } |
| } else { |
| IntIterator iter = other.iterator(); |
| while (iter.hasNext()) { |
| add(iter.next()); |
| } |
| } |
| } |
| |
| /** @inheritDoc */ |
| public int elements() { |
| return Bits.bitCount(bits); |
| } |
| |
| /** @inheritDoc */ |
| public IntIterator iterator() { |
| return new IntIterator() { |
| private int idx = Bits.findFirst(bits, 0); |
| |
| /** @inheritDoc */ |
| public boolean hasNext() { |
| return idx >= 0; |
| } |
| |
| /** @inheritDoc */ |
| public int next() { |
| if (!hasNext()) { |
| throw new NoSuchElementException(); |
| } |
| |
| int ret = idx; |
| |
| idx = Bits.findFirst(bits, idx+1); |
| |
| return ret; |
| } |
| }; |
| } |
| |
| /** @inheritDoc */ |
| public String toString() { |
| StringBuilder sb = new StringBuilder(); |
| |
| sb.append('{'); |
| |
| boolean first = true; |
| for (int i = Bits.findFirst(bits, 0) |
| ; i >= 0 |
| ; i = Bits.findFirst(bits, i + 1)) { |
| if (!first) { |
| sb.append(", "); |
| } |
| first = false; |
| sb.append(i); |
| } |
| |
| sb.append('}'); |
| |
| return sb.toString(); |
| } |
| } |