JumboEnumSet


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