1/* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements.  See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License.  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 java.util;
18
19
20/**
21 * A concrete EnumSet for enums with more than 64 elements.
22 */
23@SuppressWarnings("serial")
24final class HugeEnumSet<E extends Enum<E>> extends EnumSet<E> {
25
26    private static final int BIT_IN_LONG = 64;
27
28    final private E[] enums;
29
30    private long[] bits;
31
32    private int size;
33
34    /**
35     * Constructs an instance.
36     *
37     * @param elementType non-null; type of the elements
38     * @param enums non-null; pre-populated array of constants in ordinal
39     * order
40     */
41    HugeEnumSet(Class<E> elementType, E[] enums) {
42        super(elementType);
43        this.enums = enums;
44        bits = new long[(enums.length + BIT_IN_LONG - 1) / BIT_IN_LONG];
45    }
46
47    private class HugeEnumSetIterator implements Iterator<E> {
48
49        /**
50         * The bits yet to be returned for the long in bits[index]. As values from the current index
51         * are returned, their bits are zeroed out. When this reaches zero, the index must be
52         * incremented.
53         */
54        private long currentBits = bits[0];
55
56        /**
57         * The index into HugeEnumSet.bits of the next value to return.
58         */
59        private int index;
60
61        /**
62         * The single bit of the next value to return.
63         */
64        private long mask;
65
66        /**
67         * The candidate for removal. If null, no value may be removed.
68         */
69        private E last;
70
71        private HugeEnumSetIterator() {
72            computeNextElement();
73        }
74
75        /**
76         * Assigns mask and index to the next available value, cycling currentBits as necessary.
77         */
78        void computeNextElement() {
79            while (true) {
80                if (currentBits != 0) {
81                    mask = currentBits & -currentBits; // the lowest 1 bit in currentBits
82                    return;
83                } else if (++index < bits.length) {
84                    currentBits = bits[index];
85                } else {
86                    mask = 0;
87                    return;
88                }
89            }
90        }
91
92        public boolean hasNext() {
93            return mask != 0;
94        }
95
96        public E next() {
97            if (mask == 0) {
98                throw new NoSuchElementException();
99            }
100
101            int ordinal = Long.numberOfTrailingZeros(mask) + index * BIT_IN_LONG;
102            last = enums[ordinal];
103
104            currentBits &= ~mask;
105            computeNextElement();
106
107            return last;
108        }
109
110        public void remove() {
111            if (last == null) {
112                throw new IllegalStateException();
113            }
114
115            HugeEnumSet.this.remove(last);
116            last = null;
117        }
118    }
119
120    @Override
121    public boolean add(E element) {
122        elementClass.cast(element); // Called to throw ClassCastException.
123        int ordinal = element.ordinal();
124        int index = ordinal / BIT_IN_LONG;
125        int inBits = ordinal % BIT_IN_LONG;
126        long oldBits = bits[index];
127        long newBits = oldBits | (1L << inBits);
128        if (oldBits != newBits) {
129            bits[index] = newBits;
130            size++;
131            return true;
132        }
133        return false;
134    }
135
136    @Override
137    public boolean addAll(Collection<? extends E> collection) {
138        if (collection.isEmpty() || collection == this) {
139            return false;
140        }
141
142        if (collection instanceof EnumSet) {
143            EnumSet<?> set = (EnumSet) collection; // raw type due to javac bug 6548436
144            set.elementClass.asSubclass(elementClass); // Called to throw ClassCastException.
145
146            HugeEnumSet<E> hugeSet = (HugeEnumSet<E>) set;
147            boolean changed = false;
148            for (int i = 0; i < bits.length; i++) {
149                long oldBits = bits[i];
150                long newBits = oldBits | hugeSet.bits[i];
151                if (oldBits != newBits) {
152                    bits[i] = newBits;
153                    size += Long.bitCount(newBits) - Long.bitCount(oldBits);
154                    changed = true;
155                }
156            }
157            return changed;
158        }
159        return super.addAll(collection);
160    }
161
162    @Override
163    public int size() {
164        return size;
165    }
166
167    @Override
168    public void clear() {
169        Arrays.fill(bits, 0);
170        size = 0;
171    }
172
173    @Override
174    protected void complement() {
175        size = 0;
176        for (int i = 0, length = bits.length; i < length; i++) {
177            long b = ~bits[i];
178
179            // zero out unused bits on the last element
180            if (i == length - 1) {
181                b &= -1L >>> (BIT_IN_LONG - (enums.length % BIT_IN_LONG));
182            }
183
184            size += Long.bitCount(b);
185            bits[i] = b;
186        }
187    }
188
189    @Override
190    public boolean contains(Object object) {
191        if (object == null || !isValidType(object.getClass())) {
192            return false;
193        }
194
195        @SuppressWarnings("unchecked") // guarded by isValidType()
196        int ordinal = ((E) object).ordinal();
197        int index = ordinal / BIT_IN_LONG;
198        int inBits = ordinal % BIT_IN_LONG;
199        return (bits[index] & (1L << inBits)) != 0;
200    }
201
202    @Override
203    public HugeEnumSet<E> clone() {
204        HugeEnumSet<E> set = (HugeEnumSet<E>) super.clone();
205        set.bits = bits.clone();
206        return set;
207    }
208
209    @Override
210    public boolean containsAll(Collection<?> collection) {
211        if (collection.isEmpty()) {
212            return true;
213        }
214        if (collection instanceof HugeEnumSet) {
215            HugeEnumSet<?> set = (HugeEnumSet<?>) collection;
216            if (isValidType(set.elementClass)) {
217                for (int i = 0; i < bits.length; i++) {
218                    long setBits = set.bits[i];
219                    if ((bits[i] & setBits) != setBits) {
220                        return false;
221                    }
222                }
223                return true;
224            }
225        }
226        return !(collection instanceof EnumSet) && super.containsAll(collection);
227    }
228
229    @Override
230    public boolean equals(Object object) {
231        if (object == null) {
232            return false;
233        }
234        if (!isValidType(object.getClass())) {
235            return super.equals(object);
236        }
237        return Arrays.equals(bits, ((HugeEnumSet<?>) object).bits);
238    }
239
240    @Override
241    public Iterator<E> iterator() {
242        return new HugeEnumSetIterator();
243    }
244
245    @Override
246    public boolean remove(Object object) {
247        if (object == null || !isValidType(object.getClass())) {
248            return false;
249        }
250
251        @SuppressWarnings("unchecked") // guarded by isValidType()
252        int ordinal = ((E) object).ordinal();
253        int index = ordinal / BIT_IN_LONG;
254        int inBits = ordinal % BIT_IN_LONG;
255        long oldBits = bits[index];
256        long newBits = oldBits & ~(1L << inBits);
257        if (oldBits != newBits) {
258            bits[index] = newBits;
259            size--;
260            return true;
261        }
262        return false;
263    }
264
265    @Override
266    public boolean removeAll(Collection<?> collection) {
267        if (collection.isEmpty()) {
268            return false;
269        }
270
271        if (collection instanceof EnumSet) {
272            EnumSet<?> set = (EnumSet<?>) collection;
273            if (!isValidType(set.elementClass)) {
274                return false;
275            }
276
277            HugeEnumSet<E> hugeSet = (HugeEnumSet<E>) set;
278            boolean changed = false;
279            for (int i = 0; i < bits.length; i++) {
280                long oldBits = bits[i];
281                long newBits = oldBits & ~hugeSet.bits[i];
282                if (oldBits != newBits) {
283                    bits[i] = newBits;
284                    size += Long.bitCount(newBits) - Long.bitCount(oldBits);
285                    changed = true;
286                }
287            }
288            return changed;
289        }
290        return super.removeAll(collection);
291    }
292
293    @Override
294    public boolean retainAll(Collection<?> collection) {
295        if (collection instanceof EnumSet) {
296            EnumSet<?> set = (EnumSet<?>) collection;
297            if (!isValidType(set.elementClass)) {
298                if (size > 0) {
299                    clear();
300                    return true;
301                } else {
302                    return false;
303                }
304            }
305
306            HugeEnumSet<E> hugeSet = (HugeEnumSet<E>) set;
307            boolean changed = false;
308            for (int i = 0; i < bits.length; i++) {
309                long oldBits = bits[i];
310                long newBits = oldBits & hugeSet.bits[i];
311                if (oldBits != newBits) {
312                    bits[i] = newBits;
313                    size += Long.bitCount(newBits) - Long.bitCount(oldBits);
314                    changed = true;
315                }
316            }
317            return changed;
318        }
319        return super.retainAll(collection);
320    }
321
322    @Override
323    void setRange(E start, E end) {
324        int startOrdinal = start.ordinal();
325        int startIndex = startOrdinal / BIT_IN_LONG;
326        int startInBits = startOrdinal % BIT_IN_LONG;
327
328        int endOrdinal = end.ordinal();
329        int endIndex = endOrdinal / BIT_IN_LONG;
330        int endInBits = endOrdinal % BIT_IN_LONG;
331
332        if (startIndex == endIndex) {
333            long range = (-1L >>> (BIT_IN_LONG -(endInBits - startInBits + 1))) << startInBits;
334            size -= Long.bitCount(bits[startIndex]);
335            bits[startIndex] |= range;
336            size += Long.bitCount(bits[startIndex]);
337
338        } else {
339            long range = (-1L >>> startInBits) << startInBits;
340            size -= Long.bitCount(bits[startIndex]);
341            bits[startIndex] |= range;
342            size += Long.bitCount(bits[startIndex]);
343
344            // endInBits + 1 is the number of consecutive ones.
345            // 63 - endInBits is the following zeros of the right most one.
346            range = -1L >>> (BIT_IN_LONG - (endInBits + 1));
347            size -= Long.bitCount(bits[endIndex]);
348            bits[endIndex] |= range;
349            size += Long.bitCount(bits[endIndex]);
350            for (int i = (startIndex + 1); i <= (endIndex - 1); i++) {
351                size -= Long.bitCount(bits[i]);
352                bits[i] = -1L;
353                size += Long.bitCount(bits[i]);
354            }
355        }
356    }
357}
358