collections.java

this gcc-g++-3.3.1.tar.gz is a source file of gcc, you can learn more about gcc through this codes f

/* Collections.java -- Utility class with methods to operate on collections
   Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */


package java.util;

import java.io.Serializable;

/**
 * Utility class consisting of static methods that operate on, or return
 * Collections. Contains methods to sort, search, reverse, fill and shuffle
 * Collections, methods to facilitate interoperability with legacy APIs that
 * are unaware of collections, a method to return a list which consists of
 * multiple copies of one element, and methods which "wrap" collections to give
 * them extra properties, such as thread-safety and unmodifiability.
 * <p>
 *
 * All methods which take a collection throw a {@link NullPointerException} if
 * that collection is null. Algorithms which can change a collection may, but
 * are not required, to throw the {@link UnsupportedOperationException} that
 * the underlying collection would throw during an attempt at modification.
 * For example,
 * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)<code>
 * does not throw a exception, even though addAll is an unsupported operation
 * on a singleton; the reason for this is that addAll did not attempt to
 * modify the set.
 *
 * @author Original author unknown
 * @author Eric Blake <[e-mail]>
 * @see Collection
 * @see Set
 * @see List
 * @see Map
 * @see Arrays
 * @since 1.2
 * @status updated to 1.4
 */
public class Collections
{
  /**
   * Constant used to decide cutoff for when a non-RandomAccess list should
   * be treated as sequential-access. Basically, quadratic behavior is
   * acceptible for small lists when the overhead is so small in the first
   * place. I arbitrarily set it to 16, so it may need some tuning.
   */
  private static final int LARGE_LIST_SIZE = 16;

  /**
   * Determines if a list should be treated as a sequential-access one.
   * Rather than the old method of JDK 1.3 of assuming only instanceof
   * AbstractSequentialList should be sequential, this uses the new method
   * of JDK 1.4 of assuming anything that does NOT implement RandomAccess
   * and exceeds a large (unspecified) size should be sequential.
   *
   * @param l the list to check
   * @return true if it should be treated as sequential-access
   */
  private static boolean isSequential(List l)
  {
    return ! (l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE;
  }

  /**
   * This class is non-instantiable.
   */
  private Collections()
  {
  }

  /**
   * An immutable, serializable, empty Set.
   * @see Serializable
   */
  public static final Set EMPTY_SET = new EmptySet();

  /**
   * The implementation of {@link #EMPTY_SET}. This class name is required
   * for compatibility with Sun's JDK serializability.
   *
   * @author Eric Blake <[e-mail]>
   */
  private static final class EmptySet extends AbstractSet
    implements Serializable
  {
    /**
     * Compatible with JDK 1.4.
     */
    private static final long serialVersionUID = 1582296315990362920L;

    /**
     * A private constructor adds overhead.
     */
    EmptySet()
    {
    }

    /**
     * The size: always 0!
     */
    public int size()
    {
      return 0;
    }

    /**
     * Returns an iterator that does not iterate.
     */
    // This is really cheating! I think it's perfectly valid, though.
    public Iterator iterator()
    {
      return EMPTY_LIST.iterator();
    }

    // The remaining methods are optional, but provide a performance
    // advantage by not allocating unnecessary iterators in AbstractSet.
    /**
     * The empty set never contains anything.
     */
    public boolean contains(Object o)
    {
      return false;
    }

    /**
     * This is true only if the given collection is also empty.
     */
    public boolean containsAll(Collection c)
    {
      return c.isEmpty();
    }

    /**
     * Equal only if the other set is empty.
     */
    public boolean equals(Object o)
    {
      return o instanceof Set && ((Set) o).isEmpty();
    }

    /**
     * The hashcode is always 0.
     */
    public int hashCode()
    {
      return 0;
    }

    /**
     * Always succeeds with false result.
     */
    public boolean remove(Object o)
    {
      return false;
    }

    /**
     * Always succeeds with false result.
     */
    public boolean removeAll(Collection c)
    {
      return false;
    }

    /**
     * Always succeeds with false result.
     */
    public boolean retainAll(Collection c)
    {
      return false;
    }

    /**
     * The array is always empty.
     */
    public Object[] toArray()
    {
      return new Object[0];
    }

    /**
     * We don't even need to use reflection!
     */
    public Object[] toArray(Object[] a)
    {
      if (a.length > 0)
        a[0] = null;
      return a;
    }

    /**
     * The string never changes.
     */
    public String toString()
    {
      return "[]";
    }
  } // class EmptySet

  /**
   * An immutable, serializable, empty List, which implements RandomAccess.
   * @see Serializable
   * @see RandomAccess
   */
  public static final List EMPTY_LIST = new EmptyList();

  /**
   * The implementation of {@link #EMPTY_LIST}. This class name is required
   * for compatibility with Sun's JDK serializability.
   *
   * @author Eric Blake <[e-mail]>
   */
  private static final class EmptyList extends AbstractList
    implements Serializable, RandomAccess
  {
    /**
     * Compatible with JDK 1.4.
     */
    private static final long serialVersionUID = 8842843931221139166L;

    /**
     * A private constructor adds overhead.
     */
    EmptyList()
    {
    }

    /**
     * The size is always 0.
     */
    public int size()
    {
      return 0;
    }

    /**
     * No matter the index, it is out of bounds.
     */
    public Object get(int index)
    {
      throw new IndexOutOfBoundsException();
    }

    // The remaining methods are optional, but provide a performance
    // advantage by not allocating unnecessary iterators in AbstractList.
    /**
     * Never contains anything.
     */
    public boolean contains(Object o)
    {
      return false;
    }

    /**
     * This is true only if the given collection is also empty.
     */
    public boolean containsAll(Collection c)
    {
      return c.isEmpty();
    }

    /**
     * Equal only if the other set is empty.
     */
    public boolean equals(Object o)
    {
      return o instanceof List && ((List) o).isEmpty();
    }

    /**
     * The hashcode is always 1.
     */
    public int hashCode()
    {
      return 1;
    }

    /**
     * Returns -1.
     */
    public int indexOf(Object o)
    {
      return -1;
    }

    /**
     * Returns -1.
     */
    public int lastIndexOf(Object o)
    {
      return -1;
    }

    /**
     * Always succeeds with false result.
     */
    public boolean remove(Object o)
    {
      return false;
    }

    /**
     * Always succeeds with false result.
     */
    public boolean removeAll(Collection c)
    {
      return false;
    }

    /**
     * Always succeeds with false result.
     */
    public boolean retainAll(Collection c)
    {
      return false;
    }

    /**
     * The array is always empty.
     */
    public Object[] toArray()
    {
      return new Object[0];
    }

    /**
     * We don't even need to use reflection!
     */
    public Object[] toArray(Object[] a)
    {
      if (a.length > 0)
        a[0] = null;
      return a;
    }

    /**
     * The string never changes.
     */
    public String toString()
    {
      return "[]";
    }
  } // class EmptyList

  /**
   * An immutable, serializable, empty Map.
   * @see Serializable
   */
  public static final Map EMPTY_MAP = new EmptyMap();

  /**
   * The implementation of {@link #EMPTY_MAP}. This class name is required
   * for compatibility with Sun's JDK serializability.
   *
   * @author Eric Blake <[e-mail]>
   */
  private static final class EmptyMap extends AbstractMap
    implements Serializable
  {
    /**
     * Compatible with JDK 1.4.
     */
    private static final long serialVersionUID = 6428348081105594320L;

    /**
     * A private constructor adds overhead.
     */
    EmptyMap()
    {
    }

    /**
     * There are no entries.
     */
    public Set entrySet()
    {
      return EMPTY_SET;
    }

    // The remaining methods are optional, but provide a performance
    // advantage by not allocating unnecessary iterators in AbstractMap.
    /**
     * No entries!
     */
    public boolean containsKey(Object key)
    {
      return false;
    }

    /**
     * No entries!
     */
    public boolean containsValue(Object value)
    {
      return false;
    }

    /**
     * Equal to all empty maps.
     */
    public boolean equals(Object o)
    {
      return o instanceof Map && ((Map) o).isEmpty();
    }

    /**
     * No mappings, so this returns null.
     */
    public Object get(Object o)
    {
      return null;
    }

    /**
     * The hashcode is always 0.
     */
    public int hashCode()
    {
      return 0;
    }

    /**
     * No entries.
     */
    public Set keySet()
    {
      return EMPTY_SET;
    }

    /**
     * Remove always succeeds, with null result.
     */
    public Object remove(Object o)
    {
      return null;
    }

    /**
     * Size is always 0.
     */
    public int size()
    {
      return 0;
    }

    /**
     * No entries. Technically, EMPTY_SET, while more specific than a general
     * Collection, will work. Besides, that's what the JDK uses!
     */
    public Collection values()
    {
      return EMPTY_SET;
    }

    /**
     * The string never changes.
     */
    public String toString()
    {
      return "[]";
    }
  } // class EmptyMap


  /**
   * Compare two objects with or without a Comparator. If c is null, uses the
   * natural ordering. Slightly slower than doing it inline if the JVM isn't
   * clever, but worth it for removing a duplicate of the search code.
   * Note: This code is also used in Arrays (for sort as well as search).
   */
  static final int compare(Object o1, Object o2, Comparator c)
  {
    return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2);
  }

  /**
   * Perform a binary search of a List for a key, using the natural ordering of
   * the elements. The list must be sorted (as by the sort() method) - if it is
   * not, the behavior of this method is undefined, and may be an infinite
   * loop. Further, the key must be comparable with every item in the list. If
   * the list contains the key more than once, any one of them may be found.
   * <p>