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 }