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
17package com.android.dexgen.util;
18
19import java.util.NoSuchElementException;
20
21/**
22 * A set of integers, represented by a bit set
23 */
24public 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