collections.java

gcc的组建

  }

  /**
   * 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.
     * @return The size of the list.
     */
    public int size()
    {
      return n;
    }

    /**
     * The same element is returned.
     * @param index The index of the element to be returned (irrelevant
     *        as the list contains only copies of <code>element</code>).
     * @return The element used by this list.
     */
    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.
     * @param o The object to search for.
     * @return <code>true</code> if o is the element used by this list.
     */
    public boolean contains(Object o)
    {
      return n > 0 && equals(o, element);
    }

    /**
     * The index is either 0 or -1.
     * @param o The object to find the index of.
     * @return 0 if <code>o == element</code>, -1 if not.
     */
    public int indexOf(Object o)
    {
      return (n > 0 && equals(o, element)) ? 0 : -1;
    }

    /**
     * The index is either n-1 or -1.
     * @param o The object to find the last index of.
     * @return The last index in the list if <code>o == element</code>,
     *         -1 if not.
     */
    public int lastIndexOf(Object o)
    {
      return equals(o, element) ? n - 1 : -1;
    }

    /**
     * A subList is just another CopiesList.
     * @param from The starting bound of the sublist.
     * @param to The ending bound of the sublist.
     * @return A list of copies containing <code>from - to</code>
     *         elements, all of which are equal to the element
     *         used by this list.
     */
    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.
     * @return An array of size n filled with copies of
     *         the element used by this list.
     */
    public Object[] toArray()
    {
      Object[] a = new Object[n];
      Arrays.fill(a, element);
      return a;
    }

    /**
     * The string is easy to generate.
     * @return A string representation of the list.
     */
    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 <code>true</code> if a replacement occurred.
   * @throws UnsupportedOperationException if the list iterator does not allow
   *         for the set operation
   * @throws ClassCastException if newval is of a type which cannot be added
   *         to the list
   * @throws IllegalArgumentException if 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.
   *
   * @return a comparator that imposes reverse natural ordering
   * @see Comparable
   * @see Serializable
   */
  public static Comparator reverseOrder()
  {
    return rcInstance;
  }

  /**
   * The object for {@link #reverseOrder()}.
   */
  private static final ReverseComparator rcInstance = new ReverseComparator();

  /**
   * The implementation of {@link #reverseOrder()}. This class name
   * is required for compatibility with Sun's JDK serializability.
   *
   * @author Eric Blake ([e-mail])
   */
  private static final class ReverseComparator
    implements Comparator, Serializable
  {
    /**
     * Compatible with JDK 1.4.
     */
    private static final long serialVersionUID = 7207038068494060240L;

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

    /**
     * Compare two objects in reverse natural order.
     *
     * @param a the first object
     * @param b the second object
     * @return &lt;, ==, or &gt; 0 according to b.compareTo(a)
     */
    public int compare(Object a, Object b)
    {
      return ((Comparable) b).compareTo(a);
    }
  }

  /**
   * Rotate the elements in a list by a specified distance. After calling this
   * method, the element now at index <code>i</code> was formerly at index
   * <code>(i - distance) mod list.size()</code>. The list size is unchanged.
   * <p>
   *
   * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After
   * either <code>Collections.rotate(l, 4)</code> or
   * <code>Collections.rotate(l, -1)</code>, the new contents are
   * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate
   * just a portion of the list. For example, to move element <code>a</code>
   * forward two positions in the original example, use
   * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will
   * result in <code>[t, n, k, a, s]</code>.
   * <p>
   *
   * If the list is small or implements {@link RandomAccess}, the
   * implementation exchanges the first element to its destination, then the
   * displaced element, and so on until a circuit has been completed. The
   * process is repeated if needed on the second element, and so forth, until
   * all elements have been swapped.  For large non-random lists, the
   * implementation breaks the list into two sublists at index
   * <code>-distance mod size</code>, calls {@link #reverse(List)} on the
   * pieces, then reverses the overall list.
   *
   * @param list the list to rotate
   * @param distance the distance to rotate by; unrestricted in value
   * @throws UnsupportedOperationException if the list does not support set
   * @since 1.4
   */
  public static void rotate(List list, int distance)
  {
    int size = list.size();
    if (size == 0)
      return;
    distance %= size;
    if (distance == 0)
      return;
    if (distance < 0)
      distance += size;

    if (isSequential(list))
      {
        reverse(list);
        reverse(list.subList(0, distance));
        reverse(list.subList(distance, size));
      }
    else
      {
        // Determine the least common multiple of distance and size, as there
        // are (distance / LCM) loops to cycle through.
        int a = size;
        int lcm = distance;
        int b = a % lcm;
        while (b != 0)
          {
            a = lcm;
            lcm = b;
            b = a % lcm;
          }

        // Now, make the swaps. We must take the remainder every time through
        // the inner loop so that we don't overflow i to negative values.
        while (--lcm >= 0)
          {
            Object o = list.get(lcm);
            for (int i = lcm + distance; i != lcm; i = (i + distance) % size)
              o = list.set(i, o);
            list.set(lcm, o);
          }
      }
  }

  /**
   * Shuffle a list according to a default source of randomness. The algorithm
   * used iterates backwards over the list, swapping each element with an
   * element randomly selected from the elements in positions less than or
   * equal to it (using r.nextInt(int)).
   * <p>
   *
   * This algorithm would result in a perfectly fair shuffle (that is, each
   * element would have an equal chance of ending up in any position) if r were
   * a perfect source of randomness. In practice the results are merely very
   * close to perfect.
   * <p>
   *
   * This method operates in linear time. To do this on large lists which do
   * not implement {@link RandomAccess}, a temporary array is used to acheive
   * this speed, since it would be quadratic access otherwise.
   *
   * @param l the list to shuffle
   * @throws UnsupportedOperationException if l.listIterator() does not
   *         support the set operation
   */
  public static void shuffle(List l)
  {
    if (defaultRandom == null)
      {
        synchronized (Collections.class)
	{
	  if (defaultRandom == null)
            defaultRandom = new Random();
	}
      }
    shuffle(l, defaultRandom);
  }

  /**
   * Cache a single Random object for use by shuffle(List). This improves
   * performance as well as ensuring that sequential calls to shuffle() will
   * not result in the same shuffle order occurring: the resolution of
   * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
   */
  private static Random defaultRandom = null;

  /**
   * Shuffle a list according to a given source of randomness. The algorithm
   * used iterates backwards over the list, swapping each element with an
   * element randomly selected from the elements in positions less than or
   * equal to it (using r.nextInt(int)).
   * <p>
   *
   * This algorithm would result in a perfectly fair shuffle (that is, each
   * element would have an equal chance of ending up in any position) if r were
   * a perfect source of randomness. In practise (eg if r = new Random()) the
   * results are merely very close to perfect.
   * <p>
   *
   * This method operates in linear time. To do this on large lists which do
   * not implement {@link RandomAccess}, a temporary array is used to acheive
   * this speed, since it would be quadratic access otherwise.
   *
   * @param l the list to shuffle
   * @param r the source of randomness to use for the shuffle
   * @throws UnsupportedOperationException if l.listIterator() does not
   *         support the set operation
   */
  public static void shuffle(List l, Random r)
  {
    int lsize = l.size();
    ListIterator i = l.listIterator(lsize);
    boolean sequential = isSequential(l);
    Object[] a = null; // stores a copy of the list for the sequential case

    if (sequential)
      a = l.toArray();

    for (int pos = lsize - 1; pos > 0; --pos)
      {
	// Obtain a random position to swap with. pos + 1 is used so that the
	// range of the random number includes the current position.
	int swap = r.nextInt(pos + 1);

	// Swap the desired element.
	Object o;
        if (sequential)
          {
            o = a[swap];