1 /*
2  * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.  Oracle designates this
8  * particular file as subject to the "Classpath" exception as provided
9  * by Oracle in the LICENSE file that accompanied this code.
10  *
11  * This code is distributed in the hope that it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14  * version 2 for more details (a copy is included in the LICENSE file that
15  * accompanied this code).
16  *
17  * You should have received a copy of the GNU General Public License version
18  * 2 along with this work; if not, write to the Free Software Foundation,
19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20  *
21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22  * or visit www.oracle.com if you need additional information or have any
23  * questions.
24  */
25 
26 package java.util;
27 
28 /**
29  * Private implementation class for EnumSet, for "jumbo" enum types
30  * (i.e., those with more than 64 elements).
31  *
32  * @author Josh Bloch
33  * @since 1.5
34  * @serial exclude
35  */
36 class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> {
37     private static final long serialVersionUID = 334349849919042784L;
38 
39     /**
40      * Bit vector representation of this set.  The ith bit of the jth
41      * element of this array represents the  presence of universe[64*j +i]
42      * in this set.
43      */
44     private long elements[];
45 
46     // Redundant - maintained for performance
47     private int size = 0;
48 
JumboEnumSet(Class<E>elementType, Enum<?>[] universe)49     JumboEnumSet(Class<E>elementType, Enum<?>[] universe) {
50         super(elementType, universe);
51         elements = new long[(universe.length + 63) >>> 6];
52     }
53 
addRange(E from, E to)54     void addRange(E from, E to) {
55         int fromIndex = from.ordinal() >>> 6;
56         int toIndex = to.ordinal() >>> 6;
57 
58         if (fromIndex == toIndex) {
59             elements[fromIndex] = (-1L >>>  (from.ordinal() - to.ordinal() - 1))
60                             << from.ordinal();
61         } else {
62             elements[fromIndex] = (-1L << from.ordinal());
63             for (int i = fromIndex + 1; i < toIndex; i++)
64                 elements[i] = -1;
65             elements[toIndex] = -1L >>> (63 - to.ordinal());
66         }
67         size = to.ordinal() - from.ordinal() + 1;
68     }
69 
addAll()70     void addAll() {
71         for (int i = 0; i < elements.length; i++)
72             elements[i] = -1;
73         elements[elements.length - 1] >>>= -universe.length;
74         size = universe.length;
75     }
76 
complement()77     void complement() {
78         for (int i = 0; i < elements.length; i++)
79             elements[i] = ~elements[i];
80         elements[elements.length - 1] &= (-1L >>> -universe.length);
81         size = universe.length - size;
82     }
83 
84     /**
85      * Returns an iterator over the elements contained in this set.  The
86      * iterator traverses the elements in their <i>natural order</i> (which is
87      * the order in which the enum constants are declared). The returned
88      * Iterator is a "weakly consistent" iterator that will never throw {@link
89      * ConcurrentModificationException}.
90      *
91      * @return an iterator over the elements contained in this set
92      */
iterator()93     public Iterator<E> iterator() {
94         return new EnumSetIterator<>();
95     }
96 
97     private class EnumSetIterator<E extends Enum<E>> implements Iterator<E> {
98         /**
99          * A bit vector representing the elements in the current "word"
100          * of the set not yet returned by this iterator.
101          */
102         long unseen;
103 
104         /**
105          * The index corresponding to unseen in the elements array.
106          */
107         int unseenIndex = 0;
108 
109         /**
110          * The bit representing the last element returned by this iterator
111          * but not removed, or zero if no such element exists.
112          */
113         long lastReturned = 0;
114 
115         /**
116          * The index corresponding to lastReturned in the elements array.
117          */
118         int lastReturnedIndex = 0;
119 
EnumSetIterator()120         EnumSetIterator() {
121             unseen = elements[0];
122         }
123 
124         @Override
hasNext()125         public boolean hasNext() {
126             while (unseen == 0 && unseenIndex < elements.length - 1)
127                 unseen = elements[++unseenIndex];
128             return unseen != 0;
129         }
130 
131         @Override
132         @SuppressWarnings("unchecked")
next()133         public E next() {
134             if (!hasNext())
135                 throw new NoSuchElementException();
136             lastReturned = unseen & -unseen;
137             lastReturnedIndex = unseenIndex;
138             unseen -= lastReturned;
139             return (E) universe[(lastReturnedIndex << 6)
140                                 + Long.numberOfTrailingZeros(lastReturned)];
141         }
142 
143         @Override
remove()144         public void remove() {
145             if (lastReturned == 0)
146                 throw new IllegalStateException();
147             final long oldElements = elements[lastReturnedIndex];
148             elements[lastReturnedIndex] &= ~lastReturned;
149             if (oldElements != elements[lastReturnedIndex]) {
150                 size--;
151             }
152             lastReturned = 0;
153         }
154     }
155 
156     /**
157      * Returns the number of elements in this set.
158      *
159      * @return the number of elements in this set
160      */
size()161     public int size() {
162         return size;
163     }
164 
165     /**
166      * Returns <tt>true</tt> if this set contains no elements.
167      *
168      * @return <tt>true</tt> if this set contains no elements
169      */
isEmpty()170     public boolean isEmpty() {
171         return size == 0;
172     }
173 
174     /**
175      * Returns <tt>true</tt> if this set contains the specified element.
176      *
177      * @param e element to be checked for containment in this collection
178      * @return <tt>true</tt> if this set contains the specified element
179      */
contains(Object e)180     public boolean contains(Object e) {
181         if (e == null)
182             return false;
183         Class<?> eClass = e.getClass();
184         if (eClass != elementType && eClass.getSuperclass() != elementType)
185             return false;
186 
187         int eOrdinal = ((Enum<?>)e).ordinal();
188         return (elements[eOrdinal >>> 6] & (1L << eOrdinal)) != 0;
189     }
190 
191     // Modification Operations
192 
193     /**
194      * Adds the specified element to this set if it is not already present.
195      *
196      * @param e element to be added to this set
197      * @return <tt>true</tt> if the set changed as a result of the call
198      *
199      * @throws NullPointerException if <tt>e</tt> is null
200      */
add(E e)201     public boolean add(E e) {
202         typeCheck(e);
203 
204         int eOrdinal = e.ordinal();
205         int eWordNum = eOrdinal >>> 6;
206 
207         long oldElements = elements[eWordNum];
208         elements[eWordNum] |= (1L << eOrdinal);
209         boolean result = (elements[eWordNum] != oldElements);
210         if (result)
211             size++;
212         return result;
213     }
214 
215     /**
216      * Removes the specified element from this set if it is present.
217      *
218      * @param e element to be removed from this set, if present
219      * @return <tt>true</tt> if the set contained the specified element
220      */
remove(Object e)221     public boolean remove(Object e) {
222         if (e == null)
223             return false;
224         Class<?> eClass = e.getClass();
225         if (eClass != elementType && eClass.getSuperclass() != elementType)
226             return false;
227         int eOrdinal = ((Enum<?>)e).ordinal();
228         int eWordNum = eOrdinal >>> 6;
229 
230         long oldElements = elements[eWordNum];
231         elements[eWordNum] &= ~(1L << eOrdinal);
232         boolean result = (elements[eWordNum] != oldElements);
233         if (result)
234             size--;
235         return result;
236     }
237 
238     // Bulk Operations
239 
240     /**
241      * Returns <tt>true</tt> if this set contains all of the elements
242      * in the specified collection.
243      *
244      * @param c collection to be checked for containment in this set
245      * @return <tt>true</tt> if this set contains all of the elements
246      *        in the specified collection
247      * @throws NullPointerException if the specified collection is null
248      */
containsAll(Collection<?> c)249     public boolean containsAll(Collection<?> c) {
250         if (!(c instanceof JumboEnumSet))
251             return super.containsAll(c);
252 
253         JumboEnumSet<?> es = (JumboEnumSet<?>)c;
254         if (es.elementType != elementType)
255             return es.isEmpty();
256 
257         for (int i = 0; i < elements.length; i++)
258             if ((es.elements[i] & ~elements[i]) != 0)
259                 return false;
260         return true;
261     }
262 
263     /**
264      * Adds all of the elements in the specified collection to this set.
265      *
266      * @param c collection whose elements are to be added to this set
267      * @return <tt>true</tt> if this set changed as a result of the call
268      * @throws NullPointerException if the specified collection or any of
269      *     its elements are null
270      */
addAll(Collection<? extends E> c)271     public boolean addAll(Collection<? extends E> c) {
272         if (!(c instanceof JumboEnumSet))
273             return super.addAll(c);
274 
275         JumboEnumSet<?> es = (JumboEnumSet<?>)c;
276         if (es.elementType != elementType) {
277             if (es.isEmpty())
278                 return false;
279             else
280                 throw new ClassCastException(
281                     es.elementType + " != " + elementType);
282         }
283 
284         for (int i = 0; i < elements.length; i++)
285             elements[i] |= es.elements[i];
286         return recalculateSize();
287     }
288 
289     /**
290      * Removes from this set all of its elements that are contained in
291      * the specified collection.
292      *
293      * @param c elements to be removed from this set
294      * @return <tt>true</tt> if this set changed as a result of the call
295      * @throws NullPointerException if the specified collection is null
296      */
removeAll(Collection<?> c)297     public boolean removeAll(Collection<?> c) {
298         if (!(c instanceof JumboEnumSet))
299             return super.removeAll(c);
300 
301         JumboEnumSet<?> es = (JumboEnumSet<?>)c;
302         if (es.elementType != elementType)
303             return false;
304 
305         for (int i = 0; i < elements.length; i++)
306             elements[i] &= ~es.elements[i];
307         return recalculateSize();
308     }
309 
310     /**
311      * Retains only the elements in this set that are contained in the
312      * specified collection.
313      *
314      * @param c elements to be retained in this set
315      * @return <tt>true</tt> if this set changed as a result of the call
316      * @throws NullPointerException if the specified collection is null
317      */
retainAll(Collection<?> c)318     public boolean retainAll(Collection<?> c) {
319         if (!(c instanceof JumboEnumSet))
320             return super.retainAll(c);
321 
322         JumboEnumSet<?> es = (JumboEnumSet<?>)c;
323         if (es.elementType != elementType) {
324             boolean changed = (size != 0);
325             clear();
326             return changed;
327         }
328 
329         for (int i = 0; i < elements.length; i++)
330             elements[i] &= es.elements[i];
331         return recalculateSize();
332     }
333 
334     /**
335      * Removes all of the elements from this set.
336      */
clear()337     public void clear() {
338         Arrays.fill(elements, 0);
339         size = 0;
340     }
341 
342     /**
343      * Compares the specified object with this set for equality.  Returns
344      * <tt>true</tt> if the given object is also a set, the two sets have
345      * the same size, and every member of the given set is contained in
346      * this set.
347      *
348      * @param o object to be compared for equality with this set
349      * @return <tt>true</tt> if the specified object is equal to this set
350      */
equals(Object o)351     public boolean equals(Object o) {
352         if (!(o instanceof JumboEnumSet))
353             return super.equals(o);
354 
355         JumboEnumSet<?> es = (JumboEnumSet<?>)o;
356         if (es.elementType != elementType)
357             return size == 0 && es.size == 0;
358 
359         return Arrays.equals(es.elements, elements);
360     }
361 
362     /**
363      * Recalculates the size of the set.  Returns true if it's changed.
364      */
recalculateSize()365     private boolean recalculateSize() {
366         int oldSize = size;
367         size = 0;
368         for (long elt : elements)
369             size += Long.bitCount(elt);
370 
371         return size != oldSize;
372     }
373 
clone()374     public EnumSet<E> clone() {
375         JumboEnumSet<E> result = (JumboEnumSet<E>) super.clone();
376         result.elements = result.elements.clone();
377         return result;
378     }
379 }
380