Home » openjdk-7 » java » util » [javadoc | source]

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

Home » openjdk-7 » java » util » [javadoc | source]