Home | History | Annotate | Download | only in util 
      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      */
     34     public BitIntSet(int max) {
     35         bits = Bits.makeBitSet(max);
     36     }
     37 
     38     /** @inheritDoc */
     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      */
     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 */
     59     public void remove(int value) {
     60         if (value < Bits.getMax(bits)) {
     61             Bits.set(bits, value, false);
     62         }
     63     }
     64 
     65     /** @inheritDoc */
     66     public boolean has(int value) {
     67         return (value < Bits.getMax(bits)) && Bits.get(bits, value);
     68     }
     69 
     70     /** @inheritDoc */
     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 */
     95     public int elements() {
     96         return Bits.bitCount(bits);
     97     }
     98 
     99     /** @inheritDoc */
    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 */
    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