1 /* 2 * Copyright (c) 2003, 2012, 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 @java.io.Serial 38 private static final long serialVersionUID = 334349849919042784L; 39 40 /** 41 * Bit vector representation of this set. The ith bit of the jth 42 * element of this array represents the presence of universe[64*j +i] 43 * in this set. 44 */ 45 private long elements[]; 46 47 // Redundant - maintained for performance 48 private int size = 0; 49 50 JumboEnumSet(Class<E>elementType, Enum<?>[] universe) { 51 super(elementType, universe); 52 elements = new long[(universe.length + 63) >>> 6]; 53 } 54 55 void addRange(E from, E to) { 56 int fromIndex = from.ordinal() >>> 6; 57 int toIndex = to.ordinal() >>> 6; 58 59 if (fromIndex == toIndex) { 60 elements[fromIndex] = (-1L >>> (from.ordinal() - to.ordinal() - 1)) 61 << from.ordinal(); 62 } else { 63 elements[fromIndex] = (-1L << from.ordinal()); 64 for (int i = fromIndex + 1; i < toIndex; i++) 65 elements[i] = -1; 66 elements[toIndex] = -1L >>> (63 - to.ordinal()); 67 } 68 size = to.ordinal() - from.ordinal() + 1; 69 } 70 71 void addAll() { 72 for (int i = 0; i < elements.length; i++) 73 elements[i] = -1; 74 elements[elements.length - 1] >>>= -universe.length; 75 size = universe.length; 76 } 77 78 void complement() { 79 for (int i = 0; i < elements.length; i++) 80 elements[i] = ~elements[i]; 81 elements[elements.length - 1] &= (-1L >>> -universe.length); 82 size = universe.length - size; 83 } 84 85 /** 86 * Returns an iterator over the elements contained in this set. The 87 * iterator traverses the elements in their <i>natural order</i> (which is 88 * the order in which the enum constants are declared). The returned 89 * Iterator is a "weakly consistent" iterator that will never throw {@link 90 * ConcurrentModificationException}. 91 * 92 * @return an iterator over the elements contained in this set 93 */ 94 public Iterator<E> iterator() { 95 return new EnumSetIterator<>(); 96 } 97 98 private class EnumSetIterator<E extends Enum<E>> implements Iterator<E> { 99 /** 100 * A bit vector representing the elements in the current "word" 101 * of the set not yet returned by this iterator. 102 */ 103 long unseen; 104 105 /** 106 * The index corresponding to unseen in the elements array. 107 */ 108 int unseenIndex = 0; 109 110 /** 111 * The bit representing the last element returned by this iterator 112 * but not removed, or zero if no such element exists. 113 */ 114 long lastReturned = 0; 115 116 /** 117 * The index corresponding to lastReturned in the elements array. 118 */ 119 int lastReturnedIndex = 0; 120 121 EnumSetIterator() { 122 unseen = elements[0]; 123 } 124 125 @Override 126 public boolean hasNext() { 127 while (unseen == 0 && unseenIndex < elements.length - 1) 128 unseen = elements[++unseenIndex]; 129 return unseen != 0; 130 } 131 132 @Override 133 @SuppressWarnings("unchecked") 134 public E next() { 135 if (!hasNext()) 136 throw new NoSuchElementException(); 137 lastReturned = unseen & -unseen; 138 lastReturnedIndex = unseenIndex; 139 unseen -= lastReturned; 140 return (E) universe[(lastReturnedIndex << 6) 141 + Long.numberOfTrailingZeros(lastReturned)]; 142 } 143 144 @Override 145 public void remove() { 146 if (lastReturned == 0) 147 throw new IllegalStateException(); 148 final long oldElements = elements[lastReturnedIndex]; 149 elements[lastReturnedIndex] &= ~lastReturned; 150 if (oldElements != elements[lastReturnedIndex]) { 151 size--; 152 } 153 lastReturned = 0; 154 } 155 } 156 157 /** 158 * Returns the number of elements in this set. 159 * 160 * @return the number of elements in this set 161 */ 162 public int size() { 163 return size; 164 } 165 166 /** 167 * Returns {@code true} if this set contains no elements. 168 * 169 * @return {@code true} if this set contains no elements 170 */ 171 public boolean isEmpty() { 172 return size == 0; 173 } 174 175 /** 176 * Returns {@code true} if this set contains the specified element. 177 * 178 * @param e element to be checked for containment in this collection 179 * @return {@code true} if this set contains the specified element 180 */ 181 public boolean contains(Object e) { 182 if (e == null) 183 return false; 184 Class<?> eClass = e.getClass(); 185 if (eClass != elementType && eClass.getSuperclass() != elementType) 186 return false; 187 188 int eOrdinal = ((Enum<?>)e).ordinal(); 189 return (elements[eOrdinal >>> 6] & (1L << eOrdinal)) != 0; 190 } 191 192 // Modification Operations 193 194 /** 195 * Adds the specified element to this set if it is not already present. 196 * 197 * @param e element to be added to this set 198 * @return {@code true} if the set changed as a result of the call 199 * 200 * @throws NullPointerException if {@code e} is null 201 */ 202 public boolean add(E e) { 203 typeCheck(e); 204 205 int eOrdinal = e.ordinal(); 206 int eWordNum = eOrdinal >>> 6; 207 208 long oldElements = elements[eWordNum]; 209 elements[eWordNum] |= (1L << eOrdinal); 210 boolean result = (elements[eWordNum] != oldElements); 211 if (result) 212 size++; 213 return result; 214 } 215 216 /** 217 * Removes the specified element from this set if it is present. 218 * 219 * @param e element to be removed from this set, if present 220 * @return {@code true} if the set contained the specified element 221 */ 222 public boolean remove(Object e) { 223 if (e == null) 224 return false; 225 Class<?> eClass = e.getClass(); 226 if (eClass != elementType && eClass.getSuperclass() != elementType) 227 return false; 228 int eOrdinal = ((Enum<?>)e).ordinal(); 229 int eWordNum = eOrdinal >>> 6; 230 231 long oldElements = elements[eWordNum]; 232 elements[eWordNum] &= ~(1L << eOrdinal); 233 boolean result = (elements[eWordNum] != oldElements); 234 if (result) 235 size--; 236 return result; 237 } 238 239 // Bulk Operations 240 241 /** 242 * Returns {@code true} if this set contains all of the elements 243 * in the specified collection. 244 * 245 * @param c collection to be checked for containment in this set 246 * @return {@code true} if this set contains all of the elements 247 * in the specified collection 248 * @throws NullPointerException if the specified collection is null 249 */ 250 public boolean containsAll(Collection<?> c) { 251 if (!(c instanceof JumboEnumSet)) 252 return super.containsAll(c); 253 254 JumboEnumSet<?> es = (JumboEnumSet<?>)c; 255 if (es.elementType != elementType) 256 return es.isEmpty(); 257 258 for (int i = 0; i < elements.length; i++) 259 if ((es.elements[i] & ~elements[i]) != 0) 260 return false; 261 return true; 262 } 263 264 /** 265 * Adds all of the elements in the specified collection to this set. 266 * 267 * @param c collection whose elements are to be added to this set 268 * @return {@code true} if this set changed as a result of the call 269 * @throws NullPointerException if the specified collection or any of 270 * its elements are null 271 */ 272 public boolean addAll(Collection<? extends E> c) { 273 if (!(c instanceof JumboEnumSet)) 274 return super.addAll(c); 275 276 JumboEnumSet<?> es = (JumboEnumSet<?>)c; 277 if (es.elementType != elementType) { 278 if (es.isEmpty()) 279 return false; 280 else 281 throw new ClassCastException( 282 es.elementType + " != " + elementType); 283 } 284 285 for (int i = 0; i < elements.length; i++) 286 elements[i] |= es.elements[i]; 287 return recalculateSize(); 288 } 289 290 /** 291 * Removes from this set all of its elements that are contained in 292 * the specified collection. 293 * 294 * @param c elements to be removed from this set 295 * @return {@code true} if this set changed as a result of the call 296 * @throws NullPointerException if the specified collection is null 297 */ 298 public boolean removeAll(Collection<?> c) { 299 if (!(c instanceof JumboEnumSet)) 300 return super.removeAll(c); 301 302 JumboEnumSet<?> es = (JumboEnumSet<?>)c; 303 if (es.elementType != elementType) 304 return false; 305 306 for (int i = 0; i < elements.length; i++) 307 elements[i] &= ~es.elements[i]; 308 return recalculateSize(); 309 } 310 311 /** 312 * Retains only the elements in this set that are contained in the 313 * specified collection. 314 * 315 * @param c elements to be retained in this set 316 * @return {@code true} if this set changed as a result of the call 317 * @throws NullPointerException if the specified collection is null 318 */ 319 public boolean retainAll(Collection<?> c) { 320 if (!(c instanceof JumboEnumSet)) 321 return super.retainAll(c); 322 323 JumboEnumSet<?> es = (JumboEnumSet<?>)c; 324 if (es.elementType != elementType) { 325 boolean changed = (size != 0); 326 clear(); 327 return changed; 328 } 329 330 for (int i = 0; i < elements.length; i++) 331 elements[i] &= es.elements[i]; 332 return recalculateSize(); 333 } 334 335 /** 336 * Removes all of the elements from this set. 337 */ 338 public void clear() { 339 Arrays.fill(elements, 0); 340 size = 0; 341 } 342 343 /** 344 * Compares the specified object with this set for equality. Returns 345 * {@code true} if the given object is also a set, the two sets have 346 * the same size, and every member of the given set is contained in 347 * this set. 348 * 349 * @param o object to be compared for equality with this set 350 * @return {@code true} if the specified object is equal to this set 351 */ 352 public boolean equals(Object o) { 353 if (!(o instanceof JumboEnumSet)) 354 return super.equals(o); 355 356 JumboEnumSet<?> es = (JumboEnumSet<?>)o; 357 if (es.elementType != elementType) 358 return size == 0 && es.size == 0; 359 360 return Arrays.equals(es.elements, elements); 361 } 362 363 /** 364 * Recalculates the size of the set. Returns true if it's changed. 365 */ 366 private boolean recalculateSize() { 367 int oldSize = size; 368 size = 0; 369 for (long elt : elements) 370 size += Long.bitCount(elt); 371 372 return size != oldSize; 373 } 374 375 public EnumSet<E> clone() { 376 JumboEnumSet<E> result = (JumboEnumSet<E>) super.clone(); 377 result.elements = result.elements.clone(); 378 return result; 379 } 380 }