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 }