001package org.clafer.collection;
002
003import gnu.trove.TIntCollection;
004import gnu.trove.iterator.TIntIterator;
005import gnu.trove.procedure.TIntProcedure;
006import gnu.trove.set.TIntSet;
007import java.util.Arrays;
008import java.util.Collection;
009import org.clafer.common.Util;
010
011/**
012 * For small, fixed-capacity sets. Only purpose of this class is better
013 * performance than TIntHashSet for small cases, which happens to be most of
014 * them.
015 *
016 * @author jimmy
017 */
018public class FixedCapacityIntSet implements TIntSet {
019
020    private final int[] array;
021    private int size = 0;
022
023    public FixedCapacityIntSet(int capacity) {
024        this.array = new int[capacity];
025    }
026
027    public FixedCapacityIntSet(int... values) {
028        this(values.length);
029        addAll(values);
030    }
031
032    public FixedCapacityIntSet(FixedCapacityIntSet set) {
033        this(set.size);
034        System.arraycopy(set.array, 0, array, 0, size);
035    }
036
037    /**
038     * {@inheritDoc}
039     */
040    @Override
041    public int getNoEntryValue() {
042        throw new UnsupportedOperationException();
043    }
044
045    /**
046     * {@inheritDoc}
047     */
048    @Override
049    public int size() {
050        return size;
051    }
052
053    /**
054     * {@inheritDoc}
055     */
056    @Override
057    public boolean isEmpty() {
058        return size == 0;
059    }
060
061    /**
062     * {@inheritDoc}
063     */
064    @Override
065    public boolean contains(int entry) {
066        for (int i = 0; i < size; i++) {
067            if (array[i] == entry) {
068                return true;
069            }
070        }
071        return false;
072    }
073
074    /**
075     * {@inheritDoc}
076     */
077    @Override
078    public TIntIterator iterator() {
079        return new FixedCapacityIntSetIterator();
080    }
081
082    /**
083     * {@inheritDoc}
084     */
085    @Override
086    public int[] toArray() {
087        return Arrays.copyOf(array, size);
088    }
089
090    /**
091     * {@inheritDoc}
092     */
093    @Override
094    public int[] toArray(int[] dest) {
095        System.arraycopy(array, 0, dest, 0, Math.min(size, dest.length));
096        return dest;
097    }
098
099    /**
100     * {@inheritDoc}
101     */
102    @Override
103    public boolean add(int entry) {
104        for (int i = 0; i < size; i++) {
105            if (array[i] == entry) {
106                return false;
107            }
108        }
109        if (size == array.length) {
110            throw new IllegalStateException();
111        }
112        array[size++] = entry;
113        return true;
114    }
115
116    /**
117     * {@inheritDoc}
118     */
119    @Override
120    public boolean remove(int entry) {
121        for (int i = 0; i < size; i++) {
122            if (array[i] == entry) {
123                size--;
124                array[i] = array[size];
125                return true;
126            }
127        }
128        return false;
129    }
130
131    /**
132     * {@inheritDoc}
133     */
134    @Override
135    public boolean containsAll(Collection<?> collection) {
136        for (Object element : collection) {
137            if (element instanceof Integer) {
138                if (!contains(((Integer) element).intValue())) {
139                    return false;
140                }
141            } else {
142                return false;
143            }
144
145        }
146        return true;
147    }
148
149    /**
150     * {@inheritDoc}
151     */
152    @Override
153    public boolean containsAll(TIntCollection collection) {
154        TIntIterator iter = collection.iterator();
155        while (iter.hasNext()) {
156            if (!contains(iter.next())) {
157                return false;
158            }
159        }
160        return true;
161    }
162
163    /**
164     * {@inheritDoc}
165     */
166    @Override
167    public boolean containsAll(int[] array) {
168        for (int i : array) {
169            if (!contains(i)) {
170                return false;
171            }
172        }
173        return true;
174    }
175
176    /**
177     * {@inheritDoc}
178     */
179    @Override
180    public boolean addAll(Collection<? extends Integer> collection) {
181        boolean changed = false;
182        for (Integer element : collection) {
183            changed |= add(element.intValue());
184        }
185        return changed;
186    }
187
188    /**
189     * {@inheritDoc}
190     */
191    @Override
192    public boolean addAll(TIntCollection collection) {
193        boolean changed = false;
194        TIntIterator iter = collection.iterator();
195        while (iter.hasNext()) {
196            changed |= add(iter.next());
197        }
198        return changed;
199    }
200
201    /**
202     * {@inheritDoc}
203     */
204    @Override
205    public boolean addAll(int[] array) {
206        boolean changed = false;
207        for (int i : array) {
208            changed |= add(i);
209        }
210        return changed;
211    }
212
213    /**
214     * {@inheritDoc}
215     */
216    @Override
217    public boolean retainAll(Collection<?> collection) {
218        boolean changed = false;
219        TIntIterator iter = iterator();
220        while (iter.hasNext()) {
221            if (!collection.contains(Integer.valueOf(iter.next()))) {
222                iter.remove();
223                changed = true;
224            }
225        }
226        return changed;
227    }
228
229    /**
230     * {@inheritDoc}
231     */
232    @Override
233    public boolean retainAll(TIntCollection collection) {
234        boolean changed = false;
235        TIntIterator iter = iterator();
236        while (iter.hasNext()) {
237            if (!collection.contains(iter.next())) {
238                iter.remove();
239                changed = true;
240            }
241        }
242        return changed;
243    }
244
245    /**
246     * {@inheritDoc}
247     */
248    @Override
249    public boolean retainAll(int[] array) {
250        boolean changed = false;
251        TIntIterator iter = iterator();
252        while (iter.hasNext()) {
253            if (!Util.in(iter.next(), array)) {
254                iter.remove();
255                changed = true;
256            }
257        }
258        return changed;
259    }
260
261    /**
262     * {@inheritDoc}
263     */
264    @Override
265    public boolean removeAll(Collection<?> collection) {
266        boolean changed = false;
267        for (Object element : collection) {
268            if (element instanceof Integer) {
269                changed |= remove(((Integer) element).intValue());
270            }
271        }
272        return changed;
273    }
274
275    /**
276     * {@inheritDoc}
277     */
278    @Override
279    public boolean removeAll(TIntCollection collection) {
280        boolean changed = false;
281        TIntIterator iter = collection.iterator();
282        while (iter.hasNext()) {
283            changed |= remove(iter.next());
284        }
285        return changed;
286    }
287
288    /**
289     * {@inheritDoc}
290     */
291    @Override
292    public boolean removeAll(int[] array) {
293        boolean changed = false;
294        for (int i : array) {
295            changed |= remove(i);
296        }
297        return changed;
298    }
299
300    /**
301     * {@inheritDoc}
302     */
303    @Override
304    public void clear() {
305        size = 0;
306    }
307
308    /**
309     * {@inheritDoc}
310     */
311    @Override
312    public boolean forEach(TIntProcedure procedure) {
313        for (int i = 0; i < size; i++) {
314            if (!procedure.execute(array[i])) {
315                return false;
316            }
317        }
318        return true;
319    }
320
321    /**
322     * {@inheritDoc}
323     */
324    @Override
325    public boolean equals(Object obj) {
326        if (obj instanceof TIntSet) {
327            TIntSet other = (TIntSet) obj;
328            return size() == other.size() && containsAll(other);
329        }
330        return false;
331    }
332
333    /**
334     * {@inheritDoc}
335     */
336    @Override
337    public int hashCode() {
338        int result = 0;
339        for (int i = 0; i < size; i++) {
340            // Needs to be commutative since the array might not be sorted yet
341            // the arrays [1, 2, 3] and [2, 3, 1] need to have the same hash code.
342            result = result + array[i];
343        }
344        return result;
345    }
346
347    @Override
348    public String toString() {
349        StringBuilder result = new StringBuilder();
350        result.append('{');
351        if (size > 0) {
352            result.append(array[0]);
353            for (int i = 1; i < size; i++) {
354                result.append(", ").append(array[i]);
355            }
356        }
357        result.append('}');
358        return result.toString();
359    }
360
361    private class FixedCapacityIntSetIterator implements TIntIterator {
362
363        private int index = 0;
364
365        /**
366         * {@inheritDoc}
367         */
368        @Override
369        public boolean hasNext() {
370            return index < size;
371        }
372
373        /**
374         * {@inheritDoc}
375         */
376        @Override
377        public int next() {
378            return array[index++];
379        }
380
381        /**
382         * {@inheritDoc}
383         */
384        @Override
385        public void remove() {
386            for (int i = index - 1; i < size - 1; i++) {
387                array[i] = array[i + 1];
388            }
389            index--;
390            size--;
391        }
392    }
393}