collections.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 2,446 行 · 第 1/5 页

   * @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.
   *
   * @return a comparator that imposes reverse natural ordering
   * @see Comparable
   * @see Serializable
   */
  public static Comparator reverseOrder()
  {
    return rcInstance;
  }

  /**
   * The object for {@link #reverseOrder()}.
   */
  static private 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.
     */
    static private 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();
    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];
            a[swap] = i.previous();
          }
        else
          o = l.set(swap, i.previous());

	i.set(o);
      }
  }


  /**
   * Obtain an immutable Set consisting of a single element. The return value
   * of this method is Serializable.
   *
   * @param o the single element
   * @return an immutable Set containing only o
   * @see Serializable
   */
  public static Set singleton(Object o)
  {
    return new SingletonSet(o);
  }

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


    /**
     * The single element; package visible for use in nested class.
     * @serial the singleton
     */
    final Object element;

    /**
     * Construct a singleton.
     * @param o the element
     */
    SingletonSet(Object o)
    {
      element = o;
    }

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

    /**
     * Returns an iterator over the lone element.
     */
    public Iterator iterator()
    {
      return new Iterator()
      {
        private boolean hasNext = true;

        public boolean hasNext()
        {
          return hasNext;
        }

        public Object next()
        {
          if (hasNext)
          {
            hasNext = false;
            return element;
          }
          else
            throw new NoSuchElementException();
        }

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

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

    /**
     * This is true if the other collection only contains the element.
     */
    public boolean containsAll(Collection c)
    {
      Iterator i = c.iterator();
      int pos = c.size();
      while (--pos >= 0)
        if (! equals(i.next(), element))
          return false;
      return true;
    }

    /**
     * The hash is just that of the element.
     */
    public int hashCode()
    {
      return hashCode(element);
    }

    /**
     * Returning an array is simple.
     */
    public Object[] toArray()
    {
      return new Object[] {element};
    }

    /**
     * Obvious string.
     */
    public String toString()
    {
      return "[" + element + "]";
    }
  } // class SingletonSet

  /**
   * Obtain an immutable List consisting of a single element. The return value
   * of this method is Serializable, and implements RandomAccess.
   *
   * @param o the single element
   * @return an immutable List containing only o
   * @see Serializable
   * @see RandomAccess
   * @since 1.3
   */
  public static List singletonList(Object o)
  {
    return new SingletonList(o);
  }

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

    /**
     * The single element.
     * @serial the singleton
     */
    private final Object element;

    /**
     * Construct a singleton.
     * @param o the element
     */
    SingletonList(Object o)
    {
      element = o;
    }

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

    /**
     * Only index 0 is valid.
     */
    public Object get(int index)
    {
      if (index == 0)
        return element;
      throw new IndexOutOfBoundsException();
    }

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

    /**
     * This is true if the other collection only contains the element.
     */
    public boolean containsAll(Collection c)
    {
      Iterator i = c.iterator();
      int pos = c.size();
      while (--pos >= 0)
        if (! equals(i.next(), element))
          return false;
      return true;
    }

    /**
     * Speed up the hashcode computation.
     */
    public int hashCode()
    {
      return 31 + hashCode(element);
    }

    /**