1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/JumboEnumSet.java Sun Sep 22 21:51:56 2013 +0200
1.3 @@ -0,0 +1,375 @@
1.4 +/*
1.5 + * Copyright (c) 2003, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.util;
1.30 +
1.31 +/**
1.32 + * Private implementation class for EnumSet, for "jumbo" enum types
1.33 + * (i.e., those with more than 64 elements).
1.34 + *
1.35 + * @author Josh Bloch
1.36 + * @since 1.5
1.37 + * @serial exclude
1.38 + */
1.39 +class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> {
1.40 + private static final long serialVersionUID = 334349849919042784L;
1.41 +
1.42 + /**
1.43 + * Bit vector representation of this set. The ith bit of the jth
1.44 + * element of this array represents the presence of universe[64*j +i]
1.45 + * in this set.
1.46 + */
1.47 + private long elements[];
1.48 +
1.49 + // Redundant - maintained for performance
1.50 + private int size = 0;
1.51 +
1.52 + JumboEnumSet(Class<E>elementType, Enum[] universe) {
1.53 + super(elementType, universe);
1.54 + elements = new long[(universe.length + 63) >>> 6];
1.55 + }
1.56 +
1.57 + void addRange(E from, E to) {
1.58 + int fromIndex = from.ordinal() >>> 6;
1.59 + int toIndex = to.ordinal() >>> 6;
1.60 +
1.61 + if (fromIndex == toIndex) {
1.62 + elements[fromIndex] = (-1L >>> (from.ordinal() - to.ordinal() - 1))
1.63 + << from.ordinal();
1.64 + } else {
1.65 + elements[fromIndex] = (-1L << from.ordinal());
1.66 + for (int i = fromIndex + 1; i < toIndex; i++)
1.67 + elements[i] = -1;
1.68 + elements[toIndex] = -1L >>> (63 - to.ordinal());
1.69 + }
1.70 + size = to.ordinal() - from.ordinal() + 1;
1.71 + }
1.72 +
1.73 + void addAll() {
1.74 + for (int i = 0; i < elements.length; i++)
1.75 + elements[i] = -1;
1.76 + elements[elements.length - 1] >>>= -universe.length;
1.77 + size = universe.length;
1.78 + }
1.79 +
1.80 + void complement() {
1.81 + for (int i = 0; i < elements.length; i++)
1.82 + elements[i] = ~elements[i];
1.83 + elements[elements.length - 1] &= (-1L >>> -universe.length);
1.84 + size = universe.length - size;
1.85 + }
1.86 +
1.87 + /**
1.88 + * Returns an iterator over the elements contained in this set. The
1.89 + * iterator traverses the elements in their <i>natural order</i> (which is
1.90 + * the order in which the enum constants are declared). The returned
1.91 + * Iterator is a "weakly consistent" iterator that will never throw {@link
1.92 + * ConcurrentModificationException}.
1.93 + *
1.94 + * @return an iterator over the elements contained in this set
1.95 + */
1.96 + public Iterator<E> iterator() {
1.97 + return new EnumSetIterator<>();
1.98 + }
1.99 +
1.100 + private class EnumSetIterator<E extends Enum<E>> implements Iterator<E> {
1.101 + /**
1.102 + * A bit vector representing the elements in the current "word"
1.103 + * of the set not yet returned by this iterator.
1.104 + */
1.105 + long unseen;
1.106 +
1.107 + /**
1.108 + * The index corresponding to unseen in the elements array.
1.109 + */
1.110 + int unseenIndex = 0;
1.111 +
1.112 + /**
1.113 + * The bit representing the last element returned by this iterator
1.114 + * but not removed, or zero if no such element exists.
1.115 + */
1.116 + long lastReturned = 0;
1.117 +
1.118 + /**
1.119 + * The index corresponding to lastReturned in the elements array.
1.120 + */
1.121 + int lastReturnedIndex = 0;
1.122 +
1.123 + EnumSetIterator() {
1.124 + unseen = elements[0];
1.125 + }
1.126 +
1.127 + public boolean hasNext() {
1.128 + while (unseen == 0 && unseenIndex < elements.length - 1)
1.129 + unseen = elements[++unseenIndex];
1.130 + return unseen != 0;
1.131 + }
1.132 +
1.133 + public E next() {
1.134 + if (!hasNext())
1.135 + throw new NoSuchElementException();
1.136 + lastReturned = unseen & -unseen;
1.137 + lastReturnedIndex = unseenIndex;
1.138 + unseen -= lastReturned;
1.139 + return (E) universe[(lastReturnedIndex << 6)
1.140 + + Long.numberOfTrailingZeros(lastReturned)];
1.141 + }
1.142 +
1.143 + public void remove() {
1.144 + if (lastReturned == 0)
1.145 + throw new IllegalStateException();
1.146 + final long oldElements = elements[lastReturnedIndex];
1.147 + elements[lastReturnedIndex] &= ~lastReturned;
1.148 + if (oldElements != elements[lastReturnedIndex]) {
1.149 + size--;
1.150 + }
1.151 + lastReturned = 0;
1.152 + }
1.153 + }
1.154 +
1.155 + /**
1.156 + * Returns the number of elements in this set.
1.157 + *
1.158 + * @return the number of elements in this set
1.159 + */
1.160 + public int size() {
1.161 + return size;
1.162 + }
1.163 +
1.164 + /**
1.165 + * Returns <tt>true</tt> if this set contains no elements.
1.166 + *
1.167 + * @return <tt>true</tt> if this set contains no elements
1.168 + */
1.169 + public boolean isEmpty() {
1.170 + return size == 0;
1.171 + }
1.172 +
1.173 + /**
1.174 + * Returns <tt>true</tt> if this set contains the specified element.
1.175 + *
1.176 + * @param e element to be checked for containment in this collection
1.177 + * @return <tt>true</tt> if this set contains the specified element
1.178 + */
1.179 + public boolean contains(Object e) {
1.180 + if (e == null)
1.181 + return false;
1.182 + Class eClass = e.getClass();
1.183 + if (eClass != elementType && eClass.getSuperclass() != elementType)
1.184 + return false;
1.185 +
1.186 + int eOrdinal = ((Enum)e).ordinal();
1.187 + return (elements[eOrdinal >>> 6] & (1L << eOrdinal)) != 0;
1.188 + }
1.189 +
1.190 + // Modification Operations
1.191 +
1.192 + /**
1.193 + * Adds the specified element to this set if it is not already present.
1.194 + *
1.195 + * @param e element to be added to this set
1.196 + * @return <tt>true</tt> if the set changed as a result of the call
1.197 + *
1.198 + * @throws NullPointerException if <tt>e</tt> is null
1.199 + */
1.200 + public boolean add(E e) {
1.201 + typeCheck(e);
1.202 +
1.203 + int eOrdinal = e.ordinal();
1.204 + int eWordNum = eOrdinal >>> 6;
1.205 +
1.206 + long oldElements = elements[eWordNum];
1.207 + elements[eWordNum] |= (1L << eOrdinal);
1.208 + boolean result = (elements[eWordNum] != oldElements);
1.209 + if (result)
1.210 + size++;
1.211 + return result;
1.212 + }
1.213 +
1.214 + /**
1.215 + * Removes the specified element from this set if it is present.
1.216 + *
1.217 + * @param e element to be removed from this set, if present
1.218 + * @return <tt>true</tt> if the set contained the specified element
1.219 + */
1.220 + public boolean remove(Object e) {
1.221 + if (e == null)
1.222 + return false;
1.223 + Class eClass = e.getClass();
1.224 + if (eClass != elementType && eClass.getSuperclass() != elementType)
1.225 + return false;
1.226 + int eOrdinal = ((Enum)e).ordinal();
1.227 + int eWordNum = eOrdinal >>> 6;
1.228 +
1.229 + long oldElements = elements[eWordNum];
1.230 + elements[eWordNum] &= ~(1L << eOrdinal);
1.231 + boolean result = (elements[eWordNum] != oldElements);
1.232 + if (result)
1.233 + size--;
1.234 + return result;
1.235 + }
1.236 +
1.237 + // Bulk Operations
1.238 +
1.239 + /**
1.240 + * Returns <tt>true</tt> if this set contains all of the elements
1.241 + * in the specified collection.
1.242 + *
1.243 + * @param c collection to be checked for containment in this set
1.244 + * @return <tt>true</tt> if this set contains all of the elements
1.245 + * in the specified collection
1.246 + * @throws NullPointerException if the specified collection is null
1.247 + */
1.248 + public boolean containsAll(Collection<?> c) {
1.249 + if (!(c instanceof JumboEnumSet))
1.250 + return super.containsAll(c);
1.251 +
1.252 + JumboEnumSet es = (JumboEnumSet)c;
1.253 + if (es.elementType != elementType)
1.254 + return es.isEmpty();
1.255 +
1.256 + for (int i = 0; i < elements.length; i++)
1.257 + if ((es.elements[i] & ~elements[i]) != 0)
1.258 + return false;
1.259 + return true;
1.260 + }
1.261 +
1.262 + /**
1.263 + * Adds all of the elements in the specified collection to this set.
1.264 + *
1.265 + * @param c collection whose elements are to be added to this set
1.266 + * @return <tt>true</tt> if this set changed as a result of the call
1.267 + * @throws NullPointerException if the specified collection or any of
1.268 + * its elements are null
1.269 + */
1.270 + public boolean addAll(Collection<? extends E> c) {
1.271 + if (!(c instanceof JumboEnumSet))
1.272 + return super.addAll(c);
1.273 +
1.274 + JumboEnumSet es = (JumboEnumSet)c;
1.275 + if (es.elementType != elementType) {
1.276 + if (es.isEmpty())
1.277 + return false;
1.278 + else
1.279 + throw new ClassCastException(
1.280 + es.elementType + " != " + elementType);
1.281 + }
1.282 +
1.283 + for (int i = 0; i < elements.length; i++)
1.284 + elements[i] |= es.elements[i];
1.285 + return recalculateSize();
1.286 + }
1.287 +
1.288 + /**
1.289 + * Removes from this set all of its elements that are contained in
1.290 + * the specified collection.
1.291 + *
1.292 + * @param c elements to be removed from this set
1.293 + * @return <tt>true</tt> if this set changed as a result of the call
1.294 + * @throws NullPointerException if the specified collection is null
1.295 + */
1.296 + public boolean removeAll(Collection<?> c) {
1.297 + if (!(c instanceof JumboEnumSet))
1.298 + return super.removeAll(c);
1.299 +
1.300 + JumboEnumSet es = (JumboEnumSet)c;
1.301 + if (es.elementType != elementType)
1.302 + return false;
1.303 +
1.304 + for (int i = 0; i < elements.length; i++)
1.305 + elements[i] &= ~es.elements[i];
1.306 + return recalculateSize();
1.307 + }
1.308 +
1.309 + /**
1.310 + * Retains only the elements in this set that are contained in the
1.311 + * specified collection.
1.312 + *
1.313 + * @param c elements to be retained in this set
1.314 + * @return <tt>true</tt> if this set changed as a result of the call
1.315 + * @throws NullPointerException if the specified collection is null
1.316 + */
1.317 + public boolean retainAll(Collection<?> c) {
1.318 + if (!(c instanceof JumboEnumSet))
1.319 + return super.retainAll(c);
1.320 +
1.321 + JumboEnumSet<?> es = (JumboEnumSet<?>)c;
1.322 + if (es.elementType != elementType) {
1.323 + boolean changed = (size != 0);
1.324 + clear();
1.325 + return changed;
1.326 + }
1.327 +
1.328 + for (int i = 0; i < elements.length; i++)
1.329 + elements[i] &= es.elements[i];
1.330 + return recalculateSize();
1.331 + }
1.332 +
1.333 + /**
1.334 + * Removes all of the elements from this set.
1.335 + */
1.336 + public void clear() {
1.337 + Arrays.fill(elements, 0);
1.338 + size = 0;
1.339 + }
1.340 +
1.341 + /**
1.342 + * Compares the specified object with this set for equality. Returns
1.343 + * <tt>true</tt> if the given object is also a set, the two sets have
1.344 + * the same size, and every member of the given set is contained in
1.345 + * this set.
1.346 + *
1.347 + * @param e object to be compared for equality with this set
1.348 + * @return <tt>true</tt> if the specified object is equal to this set
1.349 + */
1.350 + public boolean equals(Object o) {
1.351 + if (!(o instanceof JumboEnumSet))
1.352 + return super.equals(o);
1.353 +
1.354 + JumboEnumSet es = (JumboEnumSet)o;
1.355 + if (es.elementType != elementType)
1.356 + return size == 0 && es.size == 0;
1.357 +
1.358 + return Arrays.equals(es.elements, elements);
1.359 + }
1.360 +
1.361 + /**
1.362 + * Recalculates the size of the set. Returns true if it's changed.
1.363 + */
1.364 + private boolean recalculateSize() {
1.365 + int oldSize = size;
1.366 + size = 0;
1.367 + for (long elt : elements)
1.368 + size += Long.bitCount(elt);
1.369 +
1.370 + return size != oldSize;
1.371 + }
1.372 +
1.373 + public EnumSet<E> clone() {
1.374 + JumboEnumSet<E> result = (JumboEnumSet<E>) super.clone();
1.375 + result.elements = result.elements.clone();
1.376 + return result;
1.377 + }
1.378 +}