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 "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 
  49     JumboEnumSet(Class<E>elementType, Enum<?>[] universe) {
  50         super(elementType, universe);
  51         elements = new long[(universe.length + 63) >>> 6];
  52     }
  53 
  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 
  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 
  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      */
  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 
 120         EnumSetIterator() {
 121             unseen = elements[0];
 122         }
 123 
 124         public boolean hasNext() {
 125             while (unseen == 0 && unseenIndex < elements.length - 1)
 126                 unseen = elements[++unseenIndex];
 127             return unseen != 0;
 128         }
 129 
 130         @Override
 131         public E next() {
 132             if (!hasNext())
 133                 throw new NoSuchElementException();
 134             lastReturned = unseen & -unseen;
 135             lastReturnedIndex = unseenIndex;
 136             unseen -= lastReturned;
 137             return (E) universe[(lastReturnedIndex << 6)
 138                                 + Long.numberOfTrailingZeros(lastReturned)];
 139         }
 140 
 141         public void remove() {
 142             if (lastReturned == 0)
 143                 throw new IllegalStateException();
 144             final long oldElements = elements[lastReturnedIndex];
 145             elements[lastReturnedIndex] &= ~lastReturned;
 146             if (oldElements != elements[lastReturnedIndex]) {
 147                 size--;
 148             }
 149             lastReturned = 0;
 150         }
 151     }
 152 
 153     /**
 154      * Returns the number of elements in this set.
 155      *
 156      * @return the number of elements in this set
 157      */
 158     public int size() {
 159         return size;
 160     }
 161 
 162     /**
 163      * Returns <tt>true</tt> if this set contains no elements.
 164      *
 165      * @return <tt>true</tt> if this set contains no elements
 166      */
 167     public boolean isEmpty() {
 168         return size == 0;
 169     }
 170 
 171     /**
 172      * Returns <tt>true</tt> if this set contains the specified element.
 173      *
 174      * @param e element to be checked for containment in this collection
 175      * @return <tt>true</tt> if this set contains the specified element
 176      */
 177     public boolean contains(Object e) {
 178         if (e == null)
 179             return false;
 180         Class<?> eClass = e.getClass();
 181         if (eClass != elementType && eClass.getSuperclass() != elementType)
 182             return false;
 183 
 184         int eOrdinal = ((Enum<?>)e).ordinal();
 185         return (elements[eOrdinal >>> 6] & (1L << eOrdinal)) != 0;
 186     }
 187 
 188     // Modification Operations
 189 
 190     /**
 191      * Adds the specified element to this set if it is not already present.
 192      *
 193      * @param e element to be added to this set
 194      * @return <tt>true</tt> if the set changed as a result of the call
 195      *
 196      * @throws NullPointerException if <tt>e</tt> is null
 197      */
 198     public boolean add(E e) {
 199         typeCheck(e);
 200 
 201         int eOrdinal = e.ordinal();
 202         int eWordNum = eOrdinal >>> 6;
 203 
 204         long oldElements = elements[eWordNum];
 205         elements[eWordNum] |= (1L << eOrdinal);
 206         boolean result = (elements[eWordNum] != oldElements);
 207         if (result)
 208             size++;
 209         return result;
 210     }
 211 
 212     /**
 213      * Removes the specified element from this set if it is present.
 214      *
 215      * @param e element to be removed from this set, if present
 216      * @return <tt>true</tt> if the set contained the specified element
 217      */
 218     public boolean remove(Object e) {
 219         if (e == null)
 220             return false;
 221         Class<?> eClass = e.getClass();
 222         if (eClass != elementType && eClass.getSuperclass() != elementType)
 223             return false;
 224         int eOrdinal = ((Enum<?>)e).ordinal();
 225         int eWordNum = eOrdinal >>> 6;
 226 
 227         long oldElements = elements[eWordNum];
 228         elements[eWordNum] &= ~(1L << eOrdinal);
 229         boolean result = (elements[eWordNum] != oldElements);
 230         if (result)
 231             size--;
 232         return result;
 233     }
 234 
 235     // Bulk Operations
 236 
 237     /**
 238      * Returns <tt>true</tt> if this set contains all of the elements
 239      * in the specified collection.
 240      *
 241      * @param c collection to be checked for containment in this set
 242      * @return <tt>true</tt> if this set contains all of the elements
 243      *        in the specified collection
 244      * @throws NullPointerException if the specified collection is null
 245      */
 246     public boolean containsAll(Collection<?> c) {
 247         if (!(c instanceof JumboEnumSet))
 248             return super.containsAll(c);
 249 
 250         JumboEnumSet<?> es = (JumboEnumSet<?>)c;
 251         if (es.elementType != elementType)
 252             return es.isEmpty();
 253 
 254         for (int i = 0; i < elements.length; i++)
 255             if ((es.elements[i] & ~elements[i]) != 0)
 256                 return false;
 257         return true;
 258     }
 259 
 260     /**
 261      * Adds all of the elements in the specified collection to this set.
 262      *
 263      * @param c collection whose elements are to be added to this set
 264      * @return <tt>true</tt> if this set changed as a result of the call
 265      * @throws NullPointerException if the specified collection or any of
 266      *     its elements are null
 267      */
 268     public boolean addAll(Collection<? extends E> c) {
 269         if (!(c instanceof JumboEnumSet))
 270             return super.addAll(c);
 271 
 272         JumboEnumSet<?> es = (JumboEnumSet<?>)c;
 273         if (es.elementType != elementType) {
 274             if (es.isEmpty())
 275                 return false;
 276             else
 277                 throw new ClassCastException(
 278                     es.elementType + " != " + elementType);
 279         }
 280 
 281         for (int i = 0; i < elements.length; i++)
 282             elements[i] |= es.elements[i];
 283         return recalculateSize();
 284     }
 285 
 286     /**
 287      * Removes from this set all of its elements that are contained in
 288      * the specified collection.
 289      *
 290      * @param c elements to be removed from this set
 291      * @return <tt>true</tt> if this set changed as a result of the call
 292      * @throws NullPointerException if the specified collection is null
 293      */
 294     public boolean removeAll(Collection<?> c) {
 295         if (!(c instanceof JumboEnumSet))
 296             return super.removeAll(c);
 297 
 298         JumboEnumSet<?> es = (JumboEnumSet<?>)c;
 299         if (es.elementType != elementType)
 300             return false;
 301 
 302         for (int i = 0; i < elements.length; i++)
 303             elements[i] &= ~es.elements[i];
 304         return recalculateSize();
 305     }
 306 
 307     /**
 308      * Retains only the elements in this set that are contained in the
 309      * specified collection.
 310      *
 311      * @param c elements to be retained in this set
 312      * @return <tt>true</tt> if this set changed as a result of the call
 313      * @throws NullPointerException if the specified collection is null
 314      */
 315     public boolean retainAll(Collection<?> c) {
 316         if (!(c instanceof JumboEnumSet))
 317             return super.retainAll(c);
 318 
 319         JumboEnumSet<?> es = (JumboEnumSet<?>)c;
 320         if (es.elementType != elementType) {
 321             boolean changed = (size != 0);
 322             clear();
 323             return changed;
 324         }
 325 
 326         for (int i = 0; i < elements.length; i++)
 327             elements[i] &= es.elements[i];
 328         return recalculateSize();
 329     }
 330 
 331     /**
 332      * Removes all of the elements from this set.
 333      */
 334     public void clear() {
 335         Arrays.fill(elements, 0);
 336         size = 0;
 337     }
 338 
 339     /**
 340      * Compares the specified object with this set for equality.  Returns
 341      * <tt>true</tt> if the given object is also a set, the two sets have
 342      * the same size, and every member of the given set is contained in
 343      * this set.
 344      *
 345      * @param e object to be compared for equality with this set
 346      * @return <tt>true</tt> if the specified object is equal to this set
 347      */
 348     public boolean equals(Object o) {
 349         if (!(o instanceof JumboEnumSet))
 350             return super.equals(o);
 351 
 352         JumboEnumSet<?> es = (JumboEnumSet<?>)o;
 353         if (es.elementType != elementType)
 354             return size == 0 && es.size == 0;
 355 
 356         return Arrays.equals(es.elements, elements);
 357     }
 358 
 359     /**
 360      * Recalculates the size of the set.  Returns true if it's changed.
 361      */
 362     private boolean recalculateSize() {
 363         int oldSize = size;
 364         size = 0;
 365         for (long elt : elements)
 366             size += Long.bitCount(elt);
 367 
 368         return size != oldSize;
 369     }
 370 
 371     public EnumSet<E> clone() {
 372         JumboEnumSet<E> result = (JumboEnumSet<E>) super.clone();
 373         result.elements = result.elements.clone();
 374         return result;
 375     }
 376 }