Robust/src/ClassLibrary/MGC/gnu/Collections.java

   1 /* Collections.java -- Utility class with methods to operate on collections
   2    Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GNU Classpath.
   6
   7 GNU Classpath is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU Classpath is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU Classpath; see the file COPYING.  If not, write to the
  19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301 USA.
  21
  22 Linking this library statically or dynamically with other modules is
  23 making a combined work based on this library.  Thus, the terms and
  24 conditions of the GNU General Public License cover the whole
  25 combination.
  26
  27 As a special exception, the copyright holders of this library give you
  28 permission to link this library with independent modules to produce an
  29 executable, regardless of the license terms of these independent
  30 modules, and to copy and distribute the resulting executable under
  31 terms of your choice, provided that you also meet, for each linked
  32 independent module, the terms and conditions of the license of that
  33 module.  An independent module is a module which is not derived from
  34 or based on this library.  If you modify this library, you may extend
  35 this exception to your version of the library, but you are not
  36 obligated to do so.  If you do not wish to do so, delete this
  37 exception statement from your version. */
  38
  39 /**
  40  * Utility class consisting of static methods that operate on, or return
  41  * Collections. Contains methods to sort, search, reverse, fill and shuffle
  42  * Collections, methods to facilitate interoperability with legacy APIs that
  43  * are unaware of collections, a method to return a list which consists of
  44  * multiple copies of one element, and methods which "wrap" collections to give
  45  * them extra properties, such as thread-safety and unmodifiability.
  46  * <p>
  47  *
  48  * All methods which take a collection throw a {@link NullPointerException} if
  49  * that collection is null. Algorithms which can change a collection may, but
  50  * are not required, to throw the {@link UnsupportedOperationException} that
  51  * the underlying collection would throw during an attempt at modification.
  52  * For example,
  53  * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)</code>
  54  * does not throw a exception, even though addAll is an unsupported operation
  55  * on a singleton; the reason for this is that addAll did not attempt to
  56  * modify the set.
  57  *
  58  * @author Original author unknown
  59  * @author Eric Blake (ebb9@email.byu.edu)
  60  * @author Tom Tromey (tromey@redhat.com)
  61  * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
  62  * @see Collection
  63  * @see Set
  64  * @see List
  65  * @see Map
  66  * @see Arrays
  67  * @since 1.2
  68  * @status updated to 1.5
  69  */
  70 public class Collections
  71 {
  72   /**
  73    * Sort a list according to the natural ordering of its elements. The list
  74    * must be modifiable, but can be of fixed size. The sort algorithm is
  75    * precisely that used by Arrays.sort(Object[]), which offers guaranteed
  76    * nlog(n) performance. This implementation dumps the list into an array,
  77    * sorts the array, and then iterates over the list setting each element from
  78    * the array.
  79    *
  80    * @param l the List to sort (<code>null</code> not permitted)
  81    * @throws ClassCastException if some items are not mutually comparable
  82    * @throws UnsupportedOperationException if the List is not modifiable
  83    * @throws NullPointerException if the list is <code>null</code>, or contains
  84    *     some element that is <code>null</code>.
  85    * @see Arrays#sort(Object[])
  86    */
  87   public static void sort(Vector l)
  88   {
  89     /*T[] a = (T[]) l.toArray();
  90     Arrays.sort(a, c);
  91     ListIterator<T> i = l.listIterator();
  92     for (int pos = 0, alen = a.length;  pos < alen;  pos++)
  93       {
  94         i.next();
  95         i.set(a[pos]);
  96       }*/
  97     //TODO System.println("Collections.sort() invoked");
  98   }
  99
 100   static final /*<T>*/ int compare(Object/*T*/ o1, Object/*T*/ o2, Comparator/*<? super T>*/ c)
 101   {
 102     return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2);
 103   }
 104
 105   public static /*<T extends Object & Comparable<? super T>>*/
 106   Object/*T*/ min(Collection/*<? extends T>*/ c)
 107   {
 108     return min(c, null);
 109   }
 110
 111   /**
 112    * Find the minimum element in a Collection, according to a specified
 113    * Comparator. This implementation iterates over the Collection, so it
 114    * works in linear time.
 115    *
 116    * @param c the Collection to find the minimum element of
 117    * @param order the Comparator to order the elements by, or null for natural
 118    *        ordering
 119    * @return the minimum element of c
 120    * @throws NoSuchElementException if c is empty
 121    * @throws ClassCastException if elements in c are not mutually comparable
 122    * @throws NullPointerException if null is compared by natural ordering
 123    *        (only possible when order is null)
 124    */
 125   public static /*<T> T*/Object min(Collection/*<? extends T>*/ c,
 126         Comparator/*<? super T>*/ order)
 127   {
 128     Iterator/*<? extends T>*/ itr = c.iterator();
 129     Object/*T*/ min = itr.next(); // throws NoSuchElementExcception
 130     int csize = c.size();
 131     for (int i = 1; i < csize; i++)
 132       {
 133   Object/*T*/ o = itr.next();
 134   if (compare(min, o, order) > 0)
 135     min = o;
 136       }
 137     return min;
 138   }
 139
 140   public static /*<T extends Object & Comparable<? super T>>
 141   T*/Object max(Collection/*<? extends T>*/ c)
 142   {
 143     return max(c, null);
 144   }
 145
 146   /**
 147    * Find the maximum element in a Collection, according to a specified
 148    * Comparator. This implementation iterates over the Collection, so it
 149    * works in linear time.
 150    *
 151    * @param c the Collection to find the maximum element of
 152    * @param order the Comparator to order the elements by, or null for natural
 153    *        ordering
 154    * @return the maximum element of c
 155    * @throws NoSuchElementException if c is empty
 156    * @throws ClassCastException if elements in c are not mutually comparable
 157    * @throws NullPointerException if null is compared by natural ordering
 158    *        (only possible when order is null)
 159    */
 160   public static /*<T> T*/Object max(Collection/*<? extends T>*/ c,
 161         Comparator/*<? super T>*/ order)
 162   {
 163     Iterator/*<? extends T>*/ itr = c.iterator();
 164     Object/*T*/ max = itr.next(); // throws NoSuchElementException
 165     int csize = c.size();
 166     for (int i = 1; i < csize; i++)
 167       {
 168   Object/*T*/ o = itr.next();
 169   if (compare(max, o, order) < 0)
 170     max = o;
 171       }
 172     return max;
 173   }
 174 } // class Collections