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