1. /*
  2. * @(#)JumboEnumSet.java 1.8 04/05/28
  3. *
  4. * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
  5. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  6. */
  7. package java.util;
  8. /**
  9. * Private implementation class for EnumSet, for "jumbo" enum types
  10. * (i.e., those with more than 64 elements).
  11. *
  12. * @author Josh Bloch
  13. * @since 1.5
  14. * @serial exclude
  15. */
  16. class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> {
  17. /**
  18. * Bit vector representation of this set. The ith bit of the jth
  19. * element of this array represents the presence of universe[64*j +i]
  20. * in this set.
  21. */
  22. private long elements[];
  23. // Redundant - maintained for performance
  24. private int size = 0;
  25. JumboEnumSet(Class<E>elementType, Enum[] universe) {
  26. super(elementType, universe);
  27. elements = new long[(universe.length + 63) >>> 6];
  28. }
  29. void addRange(E from, E to) {
  30. int fromIndex = from.ordinal() >>> 6;
  31. int toIndex = to.ordinal() >>> 6;
  32. if (fromIndex == toIndex) {
  33. elements[fromIndex] = (-1L >>> (from.ordinal() - to.ordinal() - 1))
  34. << from.ordinal();
  35. } else {
  36. elements[fromIndex] = (-1L << from.ordinal());
  37. for (int i = fromIndex + 1; i < toIndex; i++)
  38. elements[i] = -1;
  39. elements[toIndex] = -1L >>> (63 - to.ordinal());
  40. }
  41. size = to.ordinal() - from.ordinal() + 1;
  42. }
  43. void addAll() {
  44. for (int i = 0; i < elements.length; i++)
  45. elements[i] = -1;
  46. elements[elements.length - 1] >>>= -universe.length;
  47. size = universe.length;
  48. }
  49. void complement() {
  50. for (int i = 0; i < elements.length; i++)
  51. elements[i] = ~elements[i];
  52. elements[elements.length - 1] &= (-1L >>> -universe.length);
  53. size = universe.length - size;
  54. }
  55. /**
  56. * Returns an iterator over the elements contained in this set. The
  57. * iterator traverses the elements in their <i>natural order</i> (which is
  58. * the order in which the enum constants are declared). The returned
  59. * Iterator is a "weakly consistent" iterator that will never throw {@link
  60. * ConcurrentModificationException}.
  61. *
  62. * @return an iterator over the elements contained in this set
  63. */
  64. public Iterator<E> iterator() {
  65. return new EnumSetIterator<E>();
  66. }
  67. private class EnumSetIterator<E extends Enum<E>> implements Iterator<E> {
  68. /**
  69. * A bit vector representing the elements in the current "word"
  70. * of the set not yet returned by this iterator.
  71. */
  72. long unseen;
  73. /**
  74. * The index corresponding to unseen in the elements array.
  75. */
  76. int unseenIndex = 0;
  77. /**
  78. * The bit representing the last element returned by this iterator
  79. * but not removed, or zero if no such element exists.
  80. */
  81. long lastReturned = 0;
  82. /**
  83. * The index corresponding to lastReturned in the elements array.
  84. */
  85. int lastReturnedIndex = 0;
  86. EnumSetIterator() {
  87. unseen = elements[0];
  88. }
  89. public boolean hasNext() {
  90. while (unseen == 0 && unseenIndex < elements.length - 1)
  91. unseen = elements[++unseenIndex];
  92. return unseen != 0;
  93. }
  94. public E next() {
  95. if (!hasNext())
  96. throw new NoSuchElementException();
  97. lastReturned = unseen & -unseen;
  98. lastReturnedIndex = unseenIndex;
  99. unseen -= lastReturned;
  100. return (E) universe[(lastReturnedIndex << 6)
  101. + Long.numberOfTrailingZeros(lastReturned)];
  102. }
  103. public void remove() {
  104. if (lastReturned == 0)
  105. throw new IllegalStateException();
  106. elements[lastReturnedIndex] -= lastReturned;
  107. size--;
  108. lastReturned = 0;
  109. }
  110. }
  111. /**
  112. * Returns the number of elements in this set.
  113. *
  114. * @return the number of elements in this set
  115. */
  116. public int size() {
  117. return size;
  118. }
  119. /**
  120. * Returns <tt>true</tt> if this set contains no elements.
  121. *
  122. * @return <tt>true</tt> if this set contains no elements
  123. */
  124. public boolean isEmpty() {
  125. return size == 0;
  126. }
  127. /**
  128. * Returns <tt>true</tt> if this set contains the specified element.
  129. *
  130. * @param e element to be checked for containment in this collection
  131. * @return <tt>true</tt> if this set contains the specified element
  132. */
  133. public boolean contains(Object e) {
  134. if (e == null)
  135. return false;
  136. Class eClass = e.getClass();
  137. if (eClass != elementType && eClass.getSuperclass() != elementType)
  138. return false;
  139. int eOrdinal = ((Enum)e).ordinal();
  140. return (elements[eOrdinal >>> 6] & (1L << eOrdinal)) != 0;
  141. }
  142. // Modification Operations
  143. /**
  144. * Adds the specified element to this set if it is not already present.
  145. *
  146. * @param e element to be added to this set
  147. * @return <tt>true</tt> if the set changed as a result of the call
  148. *
  149. * @throws NullPointerException if <tt>e</tt> is null
  150. */
  151. public boolean add(E e) {
  152. typeCheck(e);
  153. int eOrdinal = e.ordinal();
  154. int eWordNum = eOrdinal >>> 6;
  155. long oldElements = elements[eWordNum];
  156. elements[eWordNum] |= (1L << eOrdinal);
  157. boolean result = (elements[eWordNum] != oldElements);
  158. if (result)
  159. size++;
  160. return result;
  161. }
  162. /**
  163. * Removes the specified element from this set if it is present.
  164. *
  165. * @param e element to be removed from this set, if present
  166. * @return <tt>true</tt> if the set contained the specified element
  167. */
  168. public boolean remove(Object e) {
  169. if (e == null)
  170. return false;
  171. Class eClass = e.getClass();
  172. if (eClass != elementType && eClass.getSuperclass() != elementType)
  173. return false;
  174. int eOrdinal = ((Enum)e).ordinal();
  175. int eWordNum = eOrdinal >>> 6;
  176. long oldElements = elements[eWordNum];
  177. elements[eWordNum] &= ~(1L << eOrdinal);
  178. boolean result = (elements[eWordNum] != oldElements);
  179. if (result)
  180. size--;
  181. return result;
  182. }
  183. // Bulk Operations
  184. /**
  185. * Returns <tt>true</tt> if this set contains all of the elements
  186. * in the specified collection.
  187. *
  188. * @param c collection to be checked for containment in this set
  189. * @return <tt>true</tt> if this set contains all of the elements
  190. * in the specified collection
  191. * @throws NullPointerException if the specified collection is null
  192. */
  193. public boolean containsAll(Collection<?> c) {
  194. if (!(c instanceof JumboEnumSet))
  195. return super.containsAll(c);
  196. JumboEnumSet es = (JumboEnumSet)c;
  197. if (es.elementType != elementType)
  198. return es.isEmpty();
  199. for (int i = 0; i < elements.length; i++)
  200. if ((es.elements[i] & ~elements[i]) != 0)
  201. return false;
  202. return true;
  203. }
  204. /**
  205. * Adds all of the elements in the specified collection to this set.
  206. *
  207. * @param c collection whose elements are to be added to this set
  208. * @return <tt>true</tt> if this set changed as a result of the call
  209. * @throws NullPointerException if the specified collection or any of
  210. * its elements are null
  211. */
  212. public boolean addAll(Collection<? extends E> c) {
  213. if (!(c instanceof JumboEnumSet))
  214. return super.addAll(c);
  215. JumboEnumSet es = (JumboEnumSet)c;
  216. if (es.elementType != elementType) {
  217. if (es.isEmpty())
  218. return false;
  219. else
  220. throw new ClassCastException(
  221. es.elementType + " != " + elementType);
  222. }
  223. for (int i = 0; i < elements.length; i++)
  224. elements[i] |= es.elements[i];
  225. return recalculateSize();
  226. }
  227. /**
  228. * Removes from this set all of its elements that are contained in
  229. * the specified collection.
  230. *
  231. * @param c elements to be removed from this set
  232. * @return <tt>true</tt> if this set changed as a result of the call
  233. * @throws NullPointerException if the specified collection is null
  234. */
  235. public boolean removeAll(Collection<?> c) {
  236. if (!(c instanceof JumboEnumSet))
  237. return super.removeAll(c);
  238. JumboEnumSet es = (JumboEnumSet)c;
  239. if (es.elementType != elementType)
  240. return false;
  241. for (int i = 0; i < elements.length; i++)
  242. elements[i] &= ~es.elements[i];
  243. return recalculateSize();
  244. }
  245. /**
  246. * Retains only the elements in this set that are contained in the
  247. * specified collection.
  248. *
  249. * @param c elements to be retained in this set
  250. * @return <tt>true</tt> if this set changed as a result of the call
  251. * @throws NullPointerException if the specified collection is null
  252. */
  253. public boolean retainAll(Collection<?> c) {
  254. if (!(c instanceof JumboEnumSet))
  255. return super.retainAll(c);
  256. JumboEnumSet es = (JumboEnumSet)c;
  257. if (es.elementType != elementType) {
  258. clear();
  259. return true;
  260. }
  261. for (int i = 0; i < elements.length; i++)
  262. elements[i] &= es.elements[i];
  263. return recalculateSize();
  264. }
  265. /**
  266. * Removes all of the elements from this set.
  267. */
  268. public void clear() {
  269. Arrays.fill(elements, 0);
  270. size = 0;
  271. }
  272. /**
  273. * Compares the specified object with this set for equality. Returns
  274. * <tt>true</tt> if the given object is also a set, the two sets have
  275. * the same size, and every member of the given set is contained in
  276. * this set.
  277. *
  278. * @param e object to be compared for equality with this set
  279. * @return <tt>true</tt> if the specified object is equal to this set
  280. */
  281. public boolean equals(Object o) {
  282. if (!(o instanceof JumboEnumSet))
  283. return super.equals(o);
  284. JumboEnumSet es = (JumboEnumSet)o;
  285. if (es.elementType != elementType)
  286. return size == 0 && es.size == 0;
  287. return Arrays.equals(es.elements, elements);
  288. }
  289. /**
  290. * Recalculates the size of the set. Returns true if it's changed.
  291. */
  292. private boolean recalculateSize() {
  293. int oldSize = size;
  294. size = 0;
  295. for (long elt : elements)
  296. size += Long.bitCount(elt);
  297. return size != oldSize;
  298. }
  299. public EnumSet<E> clone() {
  300. JumboEnumSet<E> result = (JumboEnumSet<E>) super.clone();
  301. result.elements = (long[]) result.elements.clone();
  302. return result;
  303. }
  304. }