collections.java

gcc的组建

     */
    private static final long serialVersionUID = 6428348081105594320L;

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

    /**
     * There are no entries.
     * @return The empty set.
     */
    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!
     * @param key The key to search for.
     * @return <code>false</code>.
     */
    public boolean containsKey(Object key)
    {
      return false;
    }

    /**
     * No entries!
     * @param value The value to search for.
     * @return <code>false</code>.
     */
    public boolean containsValue(Object value)
    {
      return false;
    }

    /**
     * Equal to all empty maps.
     * @param o The object o to compare against this map.
     * @return <code>true</code> if o is also an empty instance of
     *         <code>Map</code>.
     */
    public boolean equals(Object o)
    {
      return o instanceof Map && ((Map) o).isEmpty();
    }

    /**
     * No mappings, so this returns null.
     * @param o The key of the object to retrieve.
     * @return null. 
     */
    public Object get(Object o)
    {
      return null;
    }

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

    /**
     * No entries.
     * @return The empty set.
     */
    public Set keySet()
    {
      return EMPTY_SET;
    }

    /**
     * Remove always succeeds, with null result.
     * @param o The key of the mapping to remove.
     * @return null, as there is never a mapping for o.
     */
    public Object remove(Object o)
    {
      return null;
    }

    /**
     * Size is always 0.
     * @return 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!
     * @return The empty set.
     */
    public Collection values()
    {
      return EMPTY_SET;
    }

    /**
     * The string never changes.
     *
     * @return the string "[]".
     */
    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>
   *
   * 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;
	Object o = itr.next(); // Assumes list is not empty (see isSequential)
	boolean forward = true;
        while (low <= hi)
          {
            pos = (low + hi) >> 1;
            if (i < pos)
	      {
		if (!forward)
		  itr.next(); // Changing direction first.
		for ( ; i != pos; i++, o = itr.next());
		forward = true;
	      }
            else
	      {
		if (forward)
		  itr.previous(); // Changing direction first.
		for ( ; i != pos; i--, o = itr.previous());
		forward = false;
	      }
	    final int d = compare(o, key, 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(l.get(pos), key, 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()
    {
      /**
       * Returns <code>true</code> if there are more elements to
       * be enumerated.
       *
       * @return The result of <code>hasNext()</code>
       *         called on the underlying iterator.
       */
      public final boolean hasMoreElements()
      {
	return i.hasNext();
      }

      /**
       * Returns the next element to be enumerated.
       *
       * @return The result of <code>next()</code>
       *         called on the underlying iterator.
       */
      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);