collections.java

来自「gcc3.2.1源代码」· Java 代码 · 共 2,481 行 · 第 1/5 页

/* Collections.java -- Utility class with methods to operate on collections
   Copyright (C) 1998, 1999, 2000, 2001 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 Bryce McKinlay
 * @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();

  private static final Iterator EMPTY_ITERATOR = new Iterator()
    {
      public boolean hasNext()
      {
	return false;
      }

      public Object next()
      {
	throw new NoSuchElementException();
      }

      public void remove()
      {
	throw new UnsupportedOperationException();
      }
    };

  /**
   * 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.
     */
    public Iterator iterator()
    {
      return EMPTY_ITERATOR;
    }
  } // 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();
    }
    
    /**
     * Returns an iterator that does not iterate. Optional, but avoids 
     * allocation of an iterator in AbstractList.
     */
    public Iterator iterator()
    {
      return EMPTY_ITERATOR;
    }    
  } // 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;
    }

    /**
     * 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;
    }
  } // 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>
   *
   * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
   * and uses a linear search with O(n) link traversals and log(n) comparisons
   * with {@link AbstractSequentialList} lists. Note: although the
   * specification allows for an infinite loop if the list is unsorted, it will
   * not happen in this (Classpath) implementation.
   *
   * @param l the list to search (must be sorted)
   * @param key the value to search for
   * @return the index at which the key was found, or -n-1 if it was not
   *         found, where n is the index of the first value higher than key or
   *         a.length if there is no such value
   * @throws ClassCastException if key could not be compared with one of the
   *         elements of l
   * @throws NullPointerException if a null element has compareTo called
   * @see #sort(List)
   */
  public static int binarySearch(List l, Object key)
  {
    return binarySearch(l, key, null);
  }

  /**
   * Perform a binary search of a List for a key, using a supplied Comparator.
   * The list must be sorted (as by the sort() method with the same Comparator)
   * - 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. If the comparator is null, the elements' natural ordering is used.
   * <p>
   *
   * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
   * and uses a linear search with O(n) link traversals and log(n) comparisons
   * with {@link AbstractSequentialList} lists. Note: although the
   * specification allows for an infinite loop if the list is unsorted, it will
   * not happen in this (Classpath) implementation.
   *
   * @param l the list to search (must be sorted)
   * @param key the value to search for
   * @param c the comparator by which the list is sorted
   * @return the index at which the key was found, or -n-1 if it was not
   *         found, where n is the index of the first value higher than key or
   *         a.length if there is no such value
   * @throws ClassCastException if key could not be compared with one of the
   *         elements of l
   * @throws NullPointerException if a null element is compared with natural
   *         ordering (only possible when c is null)
   * @see #sort(List, Comparator)
   */
  public static int binarySearch(List l, Object key, Comparator c)
  {
    int pos = 0;
    int low = 0;
    int hi = l.size() - 1;

    // We use a linear search with log(n) comparisons using an iterator
    // if the list is sequential-access.
    if (isSequential(l))
      {
	ListIterator itr = l.listIterator();
        int i = 0;
        while (low <= hi)
          {
            pos = (low + hi) >> 1;
            if (i < pos)
              for ( ; i != pos; i++, itr.next());
            else
              for ( ; i != pos; i--, itr.previous());
	    final int d = compare(key, itr.next(), c);
	    if (d == 0)
              return pos;
	    else if (d < 0)
              hi = pos - 1;
	    else
              // This gets the insertion point right on the last loop
              low = ++pos;
          }
      }
    else
      {
	while (low <= hi)
	  {
	    pos = (low + hi) >> 1;
	    final int d = compare(key, l.get(pos), c);
	    if (d == 0)
              return pos;
	    else if (d < 0)
              hi = pos - 1;
	    else
              // This gets the insertion point right on the last loop
              low = ++pos;
	  }
      }

    // If we failed to find it, we do the same whichever search we did.
    return -pos - 1;
  }

  /**
   * Copy one list to another. If the destination list is longer than the
   * source list, the remaining elements are unaffected. This method runs in
   * linear time.
   *
   * @param dest the destination list
   * @param source the source list
   * @throws IndexOutOfBoundsException if the destination list is shorter
   *         than the source list (the destination will be unmodified)
   * @throws UnsupportedOperationException if dest.listIterator() does not
   *         support the set operation
   */
  public static void copy(List dest, List source)
  {
    int pos = source.size();
    if (dest.size() < pos)
      throw new IndexOutOfBoundsException("Source does not fit in dest");

    Iterator i1 = source.iterator();
    ListIterator i2 = dest.listIterator();

    while (--pos >= 0)
      {
        i2.next();
        i2.set(i1.next());
      }
  }

  /**
   * Returns an Enumeration over a collection. This allows interoperability
   * with legacy APIs that require an Enumeration as input.
   *
   * @param c the Collection to iterate over
   * @return an Enumeration backed by an Iterator over c
   */
  public static Enumeration enumeration(Collection c)
  {
    final Iterator i = c.iterator();
    return new Enumeration()
    {
      public final boolean hasMoreElements()
      {
	return i.hasNext();
      }
      public final Object nextElement()
      {
	return i.next();
      }
    };
  }

  /**
   * Replace every element of a list with a given value. This method runs in
   * linear time.
   *
   * @param l the list to fill.
   * @param val the object to vill the list with.
   * @throws UnsupportedOperationException if l.listIterator() does not
   *         support the set operation.
   */
  public static void fill(List l, Object val)
  {
    ListIterator itr = l.listIterator();
    for (int i = l.size() - 1; i >= 0; --i)
      {
	itr.next();
	itr.set(val);
      }
  }

  /**
   * Returns the starting index where the specified sublist first occurs
   * in a larger list, or -1 if there is no matching position. If
   * <code>target.size() &gt; source.size()</code>, this returns -1,
   * otherwise this implementation uses brute force, checking for
   * <code>source.sublist(i, i + target.size()).equals(target)</code>
   * for all possible i.
   *
   * @param source the list to search
   * @param target the sublist to search for
   * @return the index where found, or -1
   * @since 1.4
   */
  public static int indexOfSubList(List source, List target)
  {
    int ssize = source.size();
    for (int i = 0, j = target.size(); j <= ssize; i++, j++)
      if (source.subList(i, j).equals(target))
        return i;
    return -1;
  }

  /**
   * Returns the starting index where the specified sublist last occurs
   * in a larger list, or -1 if there is no matching position. If
   * <code>target.size() &gt; source.size()</code>, this returns -1,
   * otherwise this implementation uses brute force, checking for
   * <code>source.sublist(i, i + target.size()).equals(target)</code>
   * for all possible i.
   *
   * @param source the list to search
   * @param target the sublist to search for
   * @return the index where found, or -1
   * @since 1.4
   */
  public static int lastIndexOfSubList(List source, List target)
  {
    int ssize = source.size();