001/* EnumSet.java - Set of enum objects
002   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038
039package java.util;
040
041import 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.
084public 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}