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 "regular sized" enum types
30  * (i.e., those with 64 or fewer enum constants).
31  *
32  * @author Josh Bloch
33  * @since 1.5
34  * @serial exclude
35  */
36 class RegularEnumSet<E extends Enum<E>> extends EnumSet<E> {
37     private static final long serialVersionUID = 3411599620347842686L;
38     /**
39      * Bit vector representation of this set.  The 2^k bit indicates the
40      * presence of universe[k] in this set.
41      */
42     private long elements = 0L;
43 
RegularEnumSet(Class<E>elementType, Enum<?>[] universe)44     RegularEnumSet(Class<E>elementType, Enum<?>[] universe) {
45         super(elementType, universe);
46     }
47 
addRange(E from, E to)48     void addRange(E from, E to) {
49         elements = (-1L >>>  (from.ordinal() - to.ordinal() - 1)) << from.ordinal();
50     }
51 
addAll()52     void addAll() {
53         if (universe.length != 0)
54             elements = -1L >>> -universe.length;
55     }
56 
complement()57     void complement() {
58         if (universe.length != 0) {
59             elements = ~elements;
60             elements &= -1L >>> -universe.length;  // Mask unused bits
61         }
62     }
63 
64     /**
65      * Returns an iterator over the elements contained in this set.  The
66      * iterator traverses the elements in their <i>natural order</i> (which is
67      * the order in which the enum constants are declared). The returned
68      * Iterator is a "snapshot" iterator that will never throw {@link
69      * ConcurrentModificationException}; the elements are traversed as they
70      * existed when this call was invoked.
71      *
72      * @return an iterator over the elements contained in this set
73      */
iterator()74     public Iterator<E> iterator() {
75         return new EnumSetIterator<>();
76     }
77 
78     private class EnumSetIterator<E extends Enum<E>> implements Iterator<E> {
79         /**
80          * A bit vector representing the elements in the set not yet
81          * returned by this iterator.
82          */
83         long unseen;
84 
85         /**
86          * The bit representing the last element returned by this iterator
87          * but not removed, or zero if no such element exists.
88          */
89         long lastReturned = 0;
90 
EnumSetIterator()91         EnumSetIterator() {
92             unseen = elements;
93         }
94 
hasNext()95         public boolean hasNext() {
96             return unseen != 0;
97         }
98 
99         @SuppressWarnings("unchecked")
next()100         public E next() {
101             if (unseen == 0)
102                 throw new NoSuchElementException();
103             lastReturned = unseen & -unseen;
104             unseen -= lastReturned;
105             return (E) universe[Long.numberOfTrailingZeros(lastReturned)];
106         }
107 
remove()108         public void remove() {
109             if (lastReturned == 0)
110                 throw new IllegalStateException();
111             elements &= ~lastReturned;
112             lastReturned = 0;
113         }
114     }
115 
116     /**
117      * Returns the number of elements in this set.
118      *
119      * @return the number of elements in this set
120      */
size()121     public int size() {
122         return Long.bitCount(elements);
123     }
124 
125     /**
126      * Returns <tt>true</tt> if this set contains no elements.
127      *
128      * @return <tt>true</tt> if this set contains no elements
129      */
isEmpty()130     public boolean isEmpty() {
131         return elements == 0;
132     }
133 
134     /**
135      * Returns <tt>true</tt> if this set contains the specified element.
136      *
137      * @param e element to be checked for containment in this collection
138      * @return <tt>true</tt> if this set contains the specified element
139      */
contains(Object e)140     public boolean contains(Object e) {
141         if (e == null)
142             return false;
143         Class<?> eClass = e.getClass();
144         if (eClass != elementType && eClass.getSuperclass() != elementType)
145             return false;
146 
147         return (elements & (1L << ((Enum<?>)e).ordinal())) != 0;
148     }
149 
150     // Modification Operations
151 
152     /**
153      * Adds the specified element to this set if it is not already present.
154      *
155      * @param e element to be added to this set
156      * @return <tt>true</tt> if the set changed as a result of the call
157      *
158      * @throws NullPointerException if <tt>e</tt> is null
159      */
add(E e)160     public boolean add(E e) {
161         typeCheck(e);
162 
163         long oldElements = elements;
164         elements |= (1L << ((Enum<?>)e).ordinal());
165         return elements != oldElements;
166     }
167 
168     /**
169      * Removes the specified element from this set if it is present.
170      *
171      * @param e element to be removed from this set, if present
172      * @return <tt>true</tt> if the set contained the specified element
173      */
remove(Object e)174     public boolean remove(Object e) {
175         if (e == null)
176             return false;
177         Class<?> eClass = e.getClass();
178         if (eClass != elementType && eClass.getSuperclass() != elementType)
179             return false;
180 
181         long oldElements = elements;
182         elements &= ~(1L << ((Enum<?>)e).ordinal());
183         return elements != oldElements;
184     }
185 
186     // Bulk Operations
187 
188     /**
189      * Returns <tt>true</tt> if this set contains all of the elements
190      * in the specified collection.
191      *
192      * @param c collection to be checked for containment in this set
193      * @return <tt>true</tt> if this set contains all of the elements
194      *        in the specified collection
195      * @throws NullPointerException if the specified collection is null
196      */
containsAll(Collection<?> c)197     public boolean containsAll(Collection<?> c) {
198         if (!(c instanceof RegularEnumSet))
199             return super.containsAll(c);
200 
201         RegularEnumSet<?> es = (RegularEnumSet<?>)c;
202         if (es.elementType != elementType)
203             return es.isEmpty();
204 
205         return (es.elements & ~elements) == 0;
206     }
207 
208     /**
209      * Adds all of the elements in the specified collection to this set.
210      *
211      * @param c collection whose elements are to be added to this set
212      * @return <tt>true</tt> if this set changed as a result of the call
213      * @throws NullPointerException if the specified collection or any
214      *     of its elements are null
215      */
addAll(Collection<? extends E> c)216     public boolean addAll(Collection<? extends E> c) {
217         if (!(c instanceof RegularEnumSet))
218             return super.addAll(c);
219 
220         RegularEnumSet<?> es = (RegularEnumSet<?>)c;
221         if (es.elementType != elementType) {
222             if (es.isEmpty())
223                 return false;
224             else
225                 throw new ClassCastException(
226                     es.elementType + " != " + elementType);
227         }
228 
229         long oldElements = elements;
230         elements |= es.elements;
231         return elements != oldElements;
232     }
233 
234     /**
235      * Removes from this set all of its elements that are contained in
236      * the specified collection.
237      *
238      * @param c elements to be removed from this set
239      * @return <tt>true</tt> if this set changed as a result of the call
240      * @throws NullPointerException if the specified collection is null
241      */
removeAll(Collection<?> c)242     public boolean removeAll(Collection<?> c) {
243         if (!(c instanceof RegularEnumSet))
244             return super.removeAll(c);
245 
246         RegularEnumSet<?> es = (RegularEnumSet<?>)c;
247         if (es.elementType != elementType)
248             return false;
249 
250         long oldElements = elements;
251         elements &= ~es.elements;
252         return elements != oldElements;
253     }
254 
255     /**
256      * Retains only the elements in this set that are contained in the
257      * specified collection.
258      *
259      * @param c elements to be retained in this set
260      * @return <tt>true</tt> if this set changed as a result of the call
261      * @throws NullPointerException if the specified collection is null
262      */
retainAll(Collection<?> c)263     public boolean retainAll(Collection<?> c) {
264         if (!(c instanceof RegularEnumSet))
265             return super.retainAll(c);
266 
267         RegularEnumSet<?> es = (RegularEnumSet<?>)c;
268         if (es.elementType != elementType) {
269             boolean changed = (elements != 0);
270             elements = 0;
271             return changed;
272         }
273 
274         long oldElements = elements;
275         elements &= es.elements;
276         return elements != oldElements;
277     }
278 
279     /**
280      * Removes all of the elements from this set.
281      */
clear()282     public void clear() {
283         elements = 0;
284     }
285 
286     /**
287      * Compares the specified object with this set for equality.  Returns
288      * <tt>true</tt> if the given object is also a set, the two sets have
289      * the same size, and every member of the given set is contained in
290      * this set.
291      *
292      * @param o object to be compared for equality with this set
293      * @return <tt>true</tt> if the specified object is equal to this set
294      */
equals(Object o)295     public boolean equals(Object o) {
296         if (!(o instanceof RegularEnumSet))
297             return super.equals(o);
298 
299         RegularEnumSet<?> es = (RegularEnumSet<?>)o;
300         if (es.elementType != elementType)
301             return elements == 0 && es.elements == 0;
302         return es.elements == elements;
303     }
304 }
305