1 /*
   2  * Copyright (c) 2003, 2011, 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 
  44     RegularEnumSet(Class<E>elementType, Enum<?>[] universe) {
  45         super(elementType, universe);
  46     }
  47 
  48     void addRange(E from, E to) {
  49         elements = (-1L >>>  (from.ordinal() - to.ordinal() - 1)) << from.ordinal();
  50     }
  51 
  52     void addAll() {
  53         if (universe.length != 0)
  54             elements = -1L >>> -universe.length;
  55     }
  56 
  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      */
  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 
  91         EnumSetIterator() {
  92             unseen = elements;
  93         }
  94 
  95         public boolean hasNext() {
  96             return unseen != 0;
  97         }
  98 
  99         @SuppressWarnings("unchecked")
 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 
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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 }