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

    1   /* Licensed to the Apache Software Foundation (ASF) under one or more
    2    * contributor license agreements.  See the NOTICE file distributed with
    3    * this work for additional information regarding copyright ownership.
    4    * The ASF licenses this file to You under the Apache License, Version 2.0
    5    * (the "License"); you may not use this file except in compliance with
    6    * the License.  You may obtain a copy of the License at
    7    * 
    8    *     http://www.apache.org/licenses/LICENSE-2.0
    9    * 
   10    * Unless required by applicable law or agreed to in writing, software
   11    * distributed under the License is distributed on an "AS IS" BASIS,
   12    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   13    * See the License for the specific language governing permissions and
   14    * limitations under the License.
   15    */
   16   
   17   package java.util;
   18   
   19   
   20   /**
   21    * A concrete EnumSet for enums with more than 64 elements.
   22    */
   23   @SuppressWarnings("serial")
   24   final class HugeEnumSet<E extends Enum<E>> extends EnumSet<E> {
   25       
   26       private static final int BIT_IN_LONG = 64;
   27   
   28       final private E[] enums;
   29       
   30       private long[] bits;
   31       
   32       private int size;
   33       
   34       HugeEnumSet(Class<E> elementType) {
   35           super(elementType);
   36           enums = elementType.getEnumConstants();
   37           bits = new long[(enums.length + BIT_IN_LONG - 1) / BIT_IN_LONG];
   38       }
   39       
   40       private class HugeEnumSetIterator implements Iterator<E> {
   41   
   42           /**
   43            * The bits yet to be returned for the long in bits[index]. As values from the current index
   44            * are returned, their bits are zeroed out. When this reaches zero, the index must be
   45            * incremented.
   46            */
   47           private long currentBits = bits[0];
   48   
   49           /**
   50            * The index into HugeEnumSet.bits of the next value to return.
   51            */
   52           private int index;
   53   
   54           /**
   55            * The single bit of the next value to return.
   56            */
   57           private long mask;
   58   
   59           /**
   60            * The candidate for removal. If null, no value may be removed.
   61            */
   62           private E last;
   63   
   64           private HugeEnumSetIterator() {
   65               computeNextElement();
   66           }
   67   
   68           /**
   69            * Assigns mask and index to the next available value, cycling currentBits as necessary.
   70            */
   71           void computeNextElement() {
   72               while (true) {
   73                   if (currentBits != 0) {
   74                       mask = currentBits & -currentBits; // the lowest 1 bit in currentBits
   75                       return;
   76                   } else if (++index < bits.length) {
   77                       currentBits = bits[index];
   78                   } else {
   79                       mask = 0;
   80                       return;
   81                   }
   82               }
   83           }
   84   
   85           public boolean hasNext() {
   86               return mask != 0;
   87           }
   88   
   89           public E next() {
   90               if (mask == 0) {
   91                   throw new NoSuchElementException();
   92               }
   93   
   94               int ordinal = Long.numberOfTrailingZeros(mask) + index * BIT_IN_LONG;
   95               last = enums[ordinal];
   96   
   97               currentBits &= ~mask;
   98               computeNextElement();
   99   
  100               return last;
  101           }
  102   
  103           public void remove() {
  104               if (last == null) {
  105                   throw new IllegalStateException();
  106               }
  107   
  108               HugeEnumSet.this.remove(last);
  109               last = null;
  110           }
  111       }
  112       
  113       @Override
  114       public boolean add(E element) {
  115           if (!isValidType(element.getDeclaringClass())) {
  116               throw new ClassCastException();
  117           }
  118   
  119           int ordinal = element.ordinal();
  120           int index = ordinal / BIT_IN_LONG;
  121           int inBits = ordinal % BIT_IN_LONG;
  122           long oldBits = bits[index];
  123           long newBits = oldBits | (1L << inBits);
  124           if (oldBits != newBits) {
  125               bits[index] = newBits;
  126               size++;
  127               return true;
  128           }
  129           return false;
  130       }
  131       
  132       @Override
  133       public boolean addAll(Collection<? extends E> collection) {
  134           if (collection.isEmpty() || collection == this) {
  135               return false;
  136           }
  137   
  138           if (collection instanceof EnumSet) {
  139               EnumSet<?> set = (EnumSet<?>) collection;
  140               if (!isValidType(set.elementClass)) {
  141                   throw new ClassCastException();
  142               }
  143   
  144               HugeEnumSet<E> hugeSet = (HugeEnumSet<E>) set;
  145               boolean changed = false;
  146               for (int i = 0; i < bits.length; i++) {
  147                   long oldBits = bits[i];
  148                   long newBits = oldBits | hugeSet.bits[i];
  149                   if (oldBits != newBits) {
  150                       bits[i] = newBits;
  151                       size += Long.bitCount(newBits) - Long.bitCount(oldBits);
  152                       changed = true;
  153                   }
  154               }
  155               return changed;
  156           }
  157           return super.addAll(collection);
  158       }
  159       
  160       @Override
  161       public int size() {
  162           return size;
  163       }
  164       
  165       @Override
  166       public void clear() {
  167           Arrays.fill(bits, 0);
  168           size = 0;
  169       }
  170       
  171       @Override
  172       protected void complement() {
  173           size = 0;
  174           for (int i = 0, length = bits.length; i < length; i++) {
  175               long b = ~bits[i];
  176   
  177               // zero out unused bits on the last element
  178               if (i == length - 1) {
  179                   b &= -1L >>> (BIT_IN_LONG - (enums.length % BIT_IN_LONG));
  180               }
  181   
  182               size += Long.bitCount(b);
  183               bits[i] = b;
  184           }
  185       }
  186       
  187       @Override
  188       public boolean contains(Object object) {
  189           if (object == null || !isValidType(object.getClass())) {
  190               return false;
  191           }
  192   
  193           @SuppressWarnings("unchecked") // guarded by isValidType()
  194           int ordinal = ((E) object).ordinal();
  195           int index = ordinal / BIT_IN_LONG;
  196           int inBits = ordinal % BIT_IN_LONG;
  197           return (bits[index] & (1L << inBits)) != 0;
  198       }
  199       
  200       @Override
  201       public HugeEnumSet<E> clone() {
  202           HugeEnumSet<E> set = (HugeEnumSet<E>) super.clone();
  203           set.bits = bits.clone();
  204           return set;
  205       }
  206       
  207       @Override
  208       public boolean containsAll(Collection<?> collection) {
  209           if (collection.isEmpty()) {
  210               return true;
  211           }
  212           if (collection instanceof HugeEnumSet) {
  213               HugeEnumSet<?> set = (HugeEnumSet<?>) collection;
  214               if (isValidType(set.elementClass)) {
  215                   for (int i = 0; i < bits.length; i++) {
  216                       long setBits = set.bits[i];
  217                       if ((bits[i] & setBits) != setBits) {
  218                           return false;
  219                       }
  220                   }
  221                   return true;
  222               }
  223           }
  224           return !(collection instanceof EnumSet) && super.containsAll(collection);
  225       }
  226       
  227       @Override
  228       public boolean equals(Object object) {
  229           if (object == null) {
  230               return false;
  231           }
  232           if (!isValidType(object.getClass())) {
  233               return super.equals(object);
  234           }
  235           return Arrays.equals(bits, ((HugeEnumSet<?>) object).bits);
  236       }
  237       
  238       @Override
  239       public Iterator<E> iterator() {
  240           return new HugeEnumSetIterator();
  241       }
  242       
  243       @Override
  244       public boolean remove(Object object) {
  245           if (object == null || !isValidType(object.getClass())) {
  246               return false;
  247           }
  248   
  249           @SuppressWarnings("unchecked") // guarded by isValidType()
  250           int ordinal = ((E) object).ordinal();
  251           int index = ordinal / BIT_IN_LONG;
  252           int inBits = ordinal % BIT_IN_LONG;
  253           long oldBits = bits[index];
  254           long newBits = oldBits & ~(1L << inBits);
  255           if (oldBits != newBits) {
  256               bits[index] = newBits;
  257               size--;
  258               return true;
  259           }
  260           return false;
  261       }
  262       
  263       @Override
  264       public boolean removeAll(Collection<?> collection) {
  265           if (collection.isEmpty()) {
  266               return false;
  267           }
  268           
  269           if (collection instanceof EnumSet) {
  270               EnumSet<?> set = (EnumSet<?>) collection;
  271               if (!isValidType(set.elementClass)) {
  272                   return false;
  273               }
  274   
  275               HugeEnumSet<E> hugeSet = (HugeEnumSet<E>) set;
  276               boolean changed = false;
  277               for (int i = 0; i < bits.length; i++) {
  278                   long oldBits = bits[i];
  279                   long newBits = oldBits & ~hugeSet.bits[i];
  280                   if (oldBits != newBits) {
  281                       bits[i] = newBits;
  282                       size += Long.bitCount(newBits) - Long.bitCount(oldBits);
  283                       changed = true;
  284                   }
  285               }
  286               return changed;
  287           }
  288           return super.removeAll(collection);
  289       }
  290       
  291       @Override
  292       public boolean retainAll(Collection<?> collection) {
  293           if (collection instanceof EnumSet) {
  294               EnumSet<?> set = (EnumSet<?>) collection;
  295               if (!isValidType(set.elementClass)) {
  296                   if (size > 0) {
  297                       clear();
  298                       return true;
  299                   } else {
  300                       return false;
  301                   }
  302               }
  303   
  304               HugeEnumSet<E> hugeSet = (HugeEnumSet<E>) set;
  305               boolean changed = false;
  306               for (int i = 0; i < bits.length; i++) {
  307                   long oldBits = bits[i];
  308                   long newBits = oldBits & hugeSet.bits[i];
  309                   if (oldBits != newBits) {
  310                       bits[i] = newBits;
  311                       size += Long.bitCount(newBits) - Long.bitCount(oldBits);
  312                       changed = true;
  313                   }
  314               }
  315               return changed;
  316           }
  317           return super.retainAll(collection);
  318       }
  319       
  320       @Override
  321       void setRange(E start, E end) {
  322           int startOrdinal = start.ordinal();
  323           int startIndex = startOrdinal / BIT_IN_LONG;
  324           int startInBits = startOrdinal % BIT_IN_LONG;
  325   
  326           int endOrdinal = end.ordinal();
  327           int endIndex = endOrdinal / BIT_IN_LONG;
  328           int endInBits = endOrdinal % BIT_IN_LONG;
  329   
  330           if (startIndex == endIndex) {
  331               long range = (-1L >>> (BIT_IN_LONG -(endInBits - startInBits + 1))) << startInBits;
  332               size -= Long.bitCount(bits[startIndex]);
  333               bits[startIndex] |= range;
  334               size += Long.bitCount(bits[startIndex]);
  335   
  336           } else {
  337               long range = (-1L >>> startInBits) << startInBits;
  338               size -= Long.bitCount(bits[startIndex]);
  339               bits[startIndex] |= range;
  340               size += Long.bitCount(bits[startIndex]);
  341   
  342               // endInBits + 1 is the number of consecutive ones.
  343               // 63 - endInBits is the following zeros of the right most one.
  344               range = -1L >>> (BIT_IN_LONG - (endInBits + 1));
  345               size -= Long.bitCount(bits[endIndex]);
  346               bits[endIndex] |= range;
  347               size += Long.bitCount(bits[endIndex]);
  348               for (int i = (startIndex + 1); i <= (endIndex - 1); i++) {
  349                   size -= Long.bitCount(bits[i]);
  350                   bits[i] = -1L;
  351                   size += Long.bitCount(bits[i]);
  352               }
  353           }
  354       }
  355   }

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