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

   *
   * 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();
    for (int i = ssize - target.size(), j = ssize; i >= 0; i--, j--)
      if (source.subList(i, j).equals(target))
        return i;
    return -1;
  }

  /**
   * Returns an ArrayList holding the elements visited by a given
   * Enumeration. This method exists for interoperability between legacy
   * APIs and the new Collection API.
   *
   * @param e the enumeration to put in a list
   * @return a list containing the enumeration elements
   * @see ArrayList
   * @since 1.4
   */
  public static ArrayList list(Enumeration e)
  {
    ArrayList l = new ArrayList();
    while (e.hasMoreElements())
      l.add(e.nextElement());
    return l;
  }

  /**
   * Find the maximum element in a Collection, according to the natural
   * ordering of the elements. This implementation iterates over the
   * Collection, so it works in linear time.
   *
   * @param c the Collection to find the maximum element of
   * @return the maximum element of c
   * @exception NoSuchElementException if c is empty
   * @exception ClassCastException if elements in c are not mutually comparable
   * @exception NullPointerException if null.compareTo is called
   */
  public static Object max(Collection c)
  {
    return max(c, null);
  }

  /**
   * Find the maximum element in a Collection, according to a specified
   * Comparator. This implementation iterates over the Collection, so it
   * works in linear time.
   *
   * @param c the Collection to find the maximum element of
   * @param order the Comparator to order the elements by, or null for natural
   *        ordering
   * @return the maximum element of c
   * @throws NoSuchElementException if c is empty
   * @throws ClassCastException if elements in c are not mutually comparable
   * @throws NullPointerException if null is compared by natural ordering
   *        (only possible when order is null)
   */
  public static Object max(Collection c, Comparator order)
  {
    Iterator itr = c.iterator();
    Object max = itr.next(); // throws NoSuchElementException
    int csize = c.size();
    for (int i = 1; i < csize; i++)
      {
	Object o = itr.next();
	if (compare(max, o, order) < 0)
	  max = o;
      }
    return max;
  }

  /**
   * Find the minimum element in a Collection, according to the natural
   * ordering of the elements. This implementation iterates over the
   * Collection, so it works in linear time.
   *
   * @param c the Collection to find the minimum element of
   * @return the minimum element of c
   * @throws NoSuchElementException if c is empty
   * @throws ClassCastException if elements in c are not mutually comparable
   * @throws NullPointerException if null.compareTo is called
   */
  public static Object min(Collection c)
  {
    return min(c, null);
  }

  /**
   * Find the minimum element in a Collection, according to a specified
   * Comparator. This implementation iterates over the Collection, so it
   * works in linear time.
   *
   * @param c the Collection to find the minimum element of
   * @param order the Comparator to order the elements by, or null for natural
   *        ordering
   * @return the minimum element of c
   * @throws NoSuchElementException if c is empty
   * @throws ClassCastException if elements in c are not mutually comparable
   * @throws NullPointerException if null is compared by natural ordering
   *        (only possible when order is null)
   */
  public static Object min(Collection c, Comparator order)
  {
    Iterator itr = c.iterator();
    Object min = itr.next();	// throws NoSuchElementExcception
    int csize = c.size();
    for (int i = 1; i < csize; i++)
      {
	Object o = itr.next();
	if (compare(min, o, order) > 0)
	  min = o;
      }
    return min;
  }

  /**
   * Creates an immutable list consisting of the same object repeated n times.
   * The returned object is tiny, consisting of only a single reference to the
   * object and a count of the number of elements. It is Serializable, and
   * implements RandomAccess. You can use it in tandem with List.addAll for
   * fast list construction.
   *
   * @param n the number of times to repeat the object
   * @param o the object to repeat
   * @return a List consisting of n copies of o
   * @throws IllegalArgumentException if n &lt; 0
   * @see List#addAll(Collection)
   * @see Serializable
   * @see RandomAccess
   */
  public static List nCopies(final int n, final Object o)
  {
    return new CopiesList(n, o);
  }

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

    /**
     * The count of elements in this list.
     * @serial the list size
     */
    private final int n;

    /**
     * The repeated list element.
     * @serial the list contents
     */
    private final Object element;

    /**
     * Constructs the list.
     *
     * @param n the count
     * @param o the object
     * @throws IllegalArgumentException if n &lt; 0
     */
    CopiesList(int n, Object o)
    {
      if (n < 0)
	throw new IllegalArgumentException();
      this.n = n;
      element = o;
    }

    /**
     * The size is fixed.
     */
    public int size()
    {
      return n;
    }

    /**
     * The same element is returned.
     */
    public Object get(int index)
    {
      if (index < 0 || index >= n)
        throw new IndexOutOfBoundsException();
      return element;
    }

    // The remaining methods are optional, but provide a performance
    // advantage by not allocating unnecessary iterators in AbstractList.
    /**
     * This list only contains one element.
     */
    public boolean contains(Object o)
    {
      return n > 0 && equals(o, element);
    }

    /**
     * The index is either 0 or -1.
     */
    public int indexOf(Object o)
    {
      return (n > 0 && equals(o, element)) ? 0 : -1;
    }

    /**
     * The index is either n-1 or -1.
     */
    public int lastIndexOf(Object o)
    {
      return equals(o, element) ? n - 1 : -1;
    }

    /**
     * A subList is just another CopiesList.
     */
    public List subList(int from, int to)
    {
      if (from < 0 || to > n)
        throw new IndexOutOfBoundsException();
      return new CopiesList(to - from, element);
    }

    /**
     * The array is easy.
     */
    public Object[] toArray()
    {
      Object[] a = new Object[n];
      Arrays.fill(a, element);
      return a;
    }

    /**
     * The string is easy to generate.
     */
    public String toString()
    {
      StringBuffer r = new StringBuffer("{");
      for (int i = n - 1; --i > 0; )
        r.append(element).append(", ");
      r.append(element).append("}");
      return r.toString();
    }
  } // class CopiesList

  /**
   * Replace all instances of one object with another in the specified list.
   * The list does not change size. An element e is replaced if
   * <code>oldval == null ? e == null : oldval.equals(e)</code>.
   *
   * @param list the list to iterate over
   * @param oldval the element to replace
   * @param newval the new value for the element
   * @return true if a replacement occurred
   * @throws UnsupportedOperationException if the list iterator does not allow
   *         for the set operation
   * @throws ClassCastException newval is of a type which cannot be added
   *         to the list
   * @throws IllegalArgumentException some other aspect of newval stops
   *         it being added to the list
   * @since 1.4
   */
  public static boolean replaceAll(List list, Object oldval, Object newval)
  {
    ListIterator itr = list.listIterator();
    boolean replace_occured = false;
    for (int i = list.size(); --i >= 0; )
      if (AbstractCollection.equals(oldval, itr.next()))
        {
          itr.set(newval);
          replace_occured = true;
        }
    return replace_occured;
  }

  /**
   * Reverse a given list. This method works in linear time.
   *
   * @param l the list to reverse
   * @throws UnsupportedOperationException if l.listIterator() does not
   *         support the set operation
   */
  public static void reverse(List l)
  {
    ListIterator i1 = l.listIterator();
    int pos1 = 1;
    int pos2 = l.size();
    ListIterator i2 = l.listIterator(pos2);
    while (pos1 < pos2)
      {
	Object o = i1.next();
	i1.set(i2.previous());
	i2.set(o);
	++pos1;
	--pos2;
      }
  }

  /**
   * Get a comparator that implements the reverse of natural ordering. In
   * other words, this sorts Comparable objects opposite of how their
   * compareTo method would sort. This makes it easy to sort into reverse
   * order, by simply passing Collections.reverseOrder() to the sort method.
   * The return value of this method is Serializable.