001    /* EnumSet.java - Set of enum objects
002       Copyright (C) 2004, 2005 Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    
039    package java.util;
040    
041    import java.io.Serializable;
042    
043    /**
044     * <p>
045     * Provides an efficient mechanism for recording a set of enumeration
046     * constants.  As enumerations have a known set of possible values, certain
047     * assumptions can be made when creating a set of constants.  The maximum
048     * size of the set will always be equal to the number of constants, and each
049     * value will always be one of these constants.  As a result, the set only needs
050     * to store whether a particular constant is present or not rather than the
051     * values themselves.  Each constant can thus be represented by a single bit.
052     * </p>
053     * <p>
054     * This class is designed to provide an alternative to using integer bit flags
055     * by providing a typesafe {@link Collection} interface with an underlying
056     * implementation that utilises the assumptions above to give an equivalent level
057     * of efficiency.  The values in a {@link EnumSet} must all be from the same
058     * {@link Enum} type, which allows the contents to be packed into a bit vector.
059     * A containment test is then simply a matter of inspecting the appropriate bit, while
060     * addition involves setting the same.  Such basic operations take place in constant
061     * time.
062     * </p>
063     * <p>
064     * The {@link Iterator} implementation traverses the values in the natural order
065     * of the enumeration provided by each constant's {@link Enum#ordinal()}.  It is
066     * <emph>weakly consistent</emph> and will not throw a {@link ConcurrentModificationException}.
067     * This means that concurrent changes to the set may or may not be noticeable during
068     * traversal.
069     * </p>
070     * <p>
071     * As is usual with most collections, the set is not synchronized by default.  This
072     * can be remedied by using the {@link Collections#synchronizedSet(Set)} method.  Null
073     * elements are not supported and attempts to add one will throw a {@link NullPointerException}.
074     * </p>
075     *
076     * @author Tom Tromey (tromey@redhat.com)
077     * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
078     * @author Dalibor Topic (robilad@kaffe.org)
079     * @since 1.5
080     */
081    
082    // FIXME: serialization is special, uses SerializationProxy.
083    // of(E e) is the 'bottom' method that creates a real EnumSet.
084    public abstract class EnumSet<T extends Enum<T>>
085      extends AbstractSet<T>
086      implements Cloneable, Serializable
087    {
088      private static final long serialVersionUID = 4782406773684236311L;
089    
090      // These fields could go into the anonymous inner class in of(E),
091      // complementOf would need to be refactored then, though.
092      /**
093       * The store which maintains the bits used to represent
094       * the enumeration constants.
095       */
096      BitSet store;
097    
098      /**
099       * The cardinality of the set (the current number
100       * of bits set).
101       */
102      int cardinality;
103    
104      /**
105       * The enumeration used by this set.
106       */
107      Class<T> enumClass;
108    
109      /**
110       * Empty package-private constructor
111       */
112      EnumSet()
113      {
114      }
115    
116      /**
117       * Returns a clone of the set.
118       *
119       * @return a clone of the set.
120       */
121      public EnumSet<T> clone()
122      {
123        EnumSet<T> r;
124    
125        try
126          {
127            r = (EnumSet<T>) super.clone();
128          }
129        catch (CloneNotSupportedException _)
130          {
131            /* Can't happen */
132            return null;
133          }
134        r.store = (BitSet) store.clone();
135        return r;
136      }
137    
138      /**
139       * Returns a set for the given enumeration type where
140       * all the constants are present.
141       *
142       * @param eltType the type of enumeration to use for the set.
143       * @return an {@link EnumSet} with all the bits set.
144       * @throws NullPointerException if the element type is <code>null</code>.
145       */
146      public static <T extends Enum<T>> EnumSet<T> allOf(Class<T> eltType)
147      {
148        // create an EnumSet from the list of values of the type
149        return copyOf(Arrays.asList(eltType.getEnumConstants()));
150      }
151    
152      /**
153       * Returns a set for the given enumeration type where
154       * none of the constants are present.
155       *
156       * @param eltType the type of enumeration to use for the set.
157       * @return an {@link EnumSet} with none of the bits set.
158       * @throws NullPointerException if the element type is <code>null</code>.
159       */
160      public static <T extends Enum<T>> EnumSet<T> noneOf(Class<T> eltType)
161      {
162        return complementOf(allOf(eltType));
163      }
164    
165      /**
166       * Returns a clone of the given set.
167       *
168       * @param other the set to clone.
169       * @return an {@link EnumSet} that is a clone of the given set.
170       * @throws NullPointerException if <code>other</code> is <code>null</code>.
171       */
172      public static <T extends Enum<T>> EnumSet<T> copyOf(EnumSet<T> other)
173      {
174        return other.clone();
175      }
176    
177      /**
178       * Creates an {@link EnumSet} using the contents of the given collection.
179       * If the collection is also an {@link EnumSet}, this method works the
180       * same as {@link #copyOf(EnumSet)}.  Otherwise, the elements of the collection
181       * are inspected and used to populate the new set.
182       *
183       * @param other the collection to use to populate the new set.
184       * @return an {@link EnumSet} containing elements from the given collection.
185       * @throws NullPointerException if <code>other</code> is <code>null</code>.
186       * @throws IllegalArgumentException if the collection is empty.
187       */
188      public static <T extends Enum<T>> EnumSet<T> copyOf(Collection<T> other)
189      {
190        if (other instanceof EnumSet)
191          return copyOf((EnumSet<T>) other);
192        if (other.isEmpty())
193            throw new IllegalArgumentException("Collection is empty");
194    
195        EnumSet<T> r = null;
196    
197        for (T val : other)
198          {
199            if (r == null)
200              r = of(val);
201            else
202              r.add(val);
203          }
204    
205        return r;
206      }
207    
208      /**
209       * Returns a set which is the inverse of the supplied set.
210       * If a constant is present in the current set, it will not be
211       * present in the new set and vice versa.
212       *
213       * @param other the set to provide the complement of.
214       * @return an {@link EnumSet} which is the inverse of the current one.
215       * @throws NullPointerException if <code>other</code> is <code>null</code>.
216       */
217      public static <T extends Enum<T>> EnumSet<T> complementOf(EnumSet<T> other)
218      {
219        EnumSet<T> r = other.clone();
220        int numConstants = r.enumClass.getEnumConstants().length;
221        r.store.flip(0, numConstants);
222        r.cardinality = numConstants - other.cardinality;
223        return r;
224      }
225    
226      /**
227       * Creates a new {@link EnumSet} populated with the given element.
228       *
229       * @param first the element to use to populate the new set.
230       * @return an {@link EnumSet} containing the element.
231       * @throws NullPointerException if <code>first</code> is <code>null</code>.
232       */
233      public static <T extends Enum<T>> EnumSet<T> of(T first)
234      {
235        EnumSet<T> r = new EnumSet<T>()
236        {
237          public boolean add(T val)
238          {
239            if (store.get(val.ordinal()))
240              return false;
241    
242            store.set(val.ordinal());
243            ++cardinality;
244            return true;
245          }
246    
247          public boolean addAll(Collection<? extends T> c)
248          {
249            boolean result = false;
250            if (c instanceof EnumSet)
251            {
252              EnumSet<T> other = (EnumSet<T>) c;
253              if (enumClass == other.enumClass)
254              {
255                store.or(other.store);
256                int save = cardinality;
257                cardinality = store.cardinality();
258                result = save != cardinality;
259              }
260            }
261            else
262            {
263              for (T val : c)
264              {
265                if (add (val))
266                result = true;
267              }
268            }
269            return result;
270          }
271    
272          public void clear()
273          {
274            store.clear();
275            cardinality = 0;
276          }
277    
278          public boolean contains(Object o)
279          {
280            if (! (o instanceof Enum))
281              return false;
282    
283            Enum<T> e = (Enum<T>) o;
284            if (e.getDeclaringClass() != enumClass)
285              return false;
286    
287            return store.get(e.ordinal());
288          }
289    
290          public boolean containsAll(Collection<?> c)
291          {
292            if (c instanceof EnumSet)
293            {
294              EnumSet<T> other = (EnumSet<T>) c;
295              if (enumClass == other.enumClass)
296                return store.containsAll(other.store);
297    
298              return false;
299            }
300            return super.containsAll(c);
301          }
302    
303          public Iterator<T> iterator()
304          {
305            return new Iterator<T>()
306            {
307              int next = -1;
308              int count = 0;
309    
310              public boolean hasNext()
311              {
312                return count < cardinality;
313              }
314    
315              public T next()
316              {
317                next = store.nextSetBit(next + 1);
318                ++count;
319                return enumClass.getEnumConstants()[next];
320              }
321    
322              public void remove()
323              {
324                if (! store.get(next))
325                {
326                    store.clear(next);
327                    --cardinality;
328                }
329              }
330            };
331          }
332    
333          public boolean remove(Object o)
334          {
335            if (! (o instanceof Enum))
336              return false;
337    
338            Enum<T> e = (Enum<T>) o;
339            if (e.getDeclaringClass() != enumClass)
340              return false;
341    
342            store.clear(e.ordinal());
343            --cardinality;
344            return true;
345          }
346    
347          public boolean removeAll(Collection<?> c)
348          {
349            if (c instanceof EnumSet)
350            {
351              EnumSet<T> other = (EnumSet<T>) c;
352              if (enumClass != other.enumClass)
353                return false;
354    
355              store.andNot(other.store);
356              int save = cardinality;
357              cardinality = store.cardinality();
358              return save != cardinality;
359            }
360            return super.removeAll(c);
361          }
362    
363          public boolean retainAll(Collection<?> c)
364          {
365            if (c instanceof EnumSet)
366            {
367              EnumSet<T> other = (EnumSet<T>) c;
368              if (enumClass != other.enumClass)
369                return false;
370    
371              store.and(other.store);
372              int save = cardinality;
373              cardinality = store.cardinality();
374              return save != cardinality;
375            }
376            return super.retainAll(c);
377          }
378    
379          public int size()
380          {
381            return cardinality;
382          }
383        };
384    
385        // initialize the class
386        r.enumClass = first.getDeclaringClass();
387        r.store = new BitSet(r.enumClass.getEnumConstants().length);
388    
389        r.add(first);
390        return r;
391      }
392    
393      /**
394       * Creates a new {@link EnumSet} populated with the given two elements.
395       *
396       * @param first the first element to use to populate the new set.
397       * @param second the second element to use.
398       * @return an {@link EnumSet} containing the elements.
399       * @throws NullPointerException if any of the parameters are <code>null</code>.
400       */
401      public static <T extends Enum<T>> EnumSet<T> of(T first, T second)
402      {
403        EnumSet<T> r = of(first);
404        r.add(second);
405        return r;
406      }
407    
408      /**
409       * Creates a new {@link EnumSet} populated with the given three elements.
410       *
411       * @param first the first element to use to populate the new set.
412       * @param second the second element to use.
413       * @param third the third element to use.
414       * @return an {@link EnumSet} containing the elements.
415       * @throws NullPointerException if any of the parameters are <code>null</code>.
416       */
417      public static <T extends Enum<T>> EnumSet<T> of(T first, T second, T third)
418      {
419        EnumSet<T> r = of(first, second);
420        r.add(third);
421        return r;
422      }
423    
424      /**
425       * Creates a new {@link EnumSet} populated with the given four elements.
426       *
427       * @param first the first element to use to populate the new set.
428       * @param second the second element to use.
429       * @param third the third element to use.
430       * @param fourth the fourth element to use.
431       * @return an {@link EnumSet} containing the elements.
432       * @throws NullPointerException if any of the parameters are <code>null</code>.
433       */
434      public static <T extends Enum<T>> EnumSet<T> of(T first, T second, T third,
435                                                      T fourth)
436      {
437        EnumSet<T> r = of(first, second, third);
438        r.add(fourth);
439        return r;
440      }
441    
442      /**
443       * Creates a new {@link EnumSet} populated with the given five elements.
444       *
445       * @param first the first element to use to populate the new set.
446       * @param second the second element to use.
447       * @param third the third element to use.
448       * @param fourth the fourth element to use.
449       * @param fifth the fifth element to use.
450       * @return an {@link EnumSet} containing the elements.
451       * @throws NullPointerException if any of the parameters are <code>null</code>.
452       */
453      public static <T extends Enum<T>> EnumSet<T> of(T first, T second, T third,
454                                                      T fourth, T fifth)
455      {
456        EnumSet<T> r = of(first, second, third, fourth);
457        r.add(fifth);
458        return r;
459      }
460    
461      /**
462       * Creates a new {@link EnumSet} populated with the given elements.
463       *
464       * @param first the first element to use to populate the new set.
465       * @param rest the other elements to use.
466       * @return an {@link EnumSet} containing the elements.
467       * @throws NullPointerException if any of the parameters are <code>null</code>.
468       */
469      public static <T extends Enum<T>> EnumSet<T> of(T first, T... rest)
470      {
471        EnumSet<T> r = noneOf(first.getDeclaringClass());
472        r.add(first);
473        for (T val : rest)
474          r.add(val);
475        return r;
476      }
477    
478      /**
479       * Creates a new {@link EnumSet} using the enumeration constants
480       * starting from {@code from} and ending at {@code to} inclusive.
481       * The two may be the same, but they must be in the correct order.
482       * So giving the first constant twice would give a set with just that
483       * constant set, while supplying the first and second constant will give
484       * a set with those two elements.  However, specifying the second as
485       * the {@code from} element followed by an earlier element as the
486       * {@code to} element will result in an error.
487       *
488       * @param from the element to start from.
489       * @param to the element to end at (may be the same as {@code from}.
490       * @return an {@link EnumSet} containing the specified range of elements.
491       * @throws NullPointerException if any of the parameters are <code>null</code>.
492       * @throws IllegalArgumentException if {@code first.compareTo(last) > 0}.
493       */
494      public static <T extends Enum<T>> EnumSet<T> range(T from, T to)
495      {
496        if (from.compareTo(to) > 0)
497          throw new IllegalArgumentException();
498        Class<T> type = from.getDeclaringClass();
499        EnumSet<T> r = noneOf(type);
500    
501        T[] values = type.getEnumConstants();
502        // skip over values until start of range is found
503        int i = 0;
504        while (from != values[i])
505          i++;
506    
507        // add values until end of range is found
508        while (to != values[i]) {
509          r.add(values[i]);
510          i++;
511        }
512    
513        // add end of range
514        r.add(to);
515    
516        return r;
517      }
518    }