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.
5 This file is part of GNU Classpath.
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)
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.
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
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
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. */
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.
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.
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
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)
68 * @status updated to 1.5
70 public class Collections
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
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[])
87 public static void sort(Vector l)
89 /*T[] a = (T[]) l.toArray();
91 ListIterator<T> i = l.listIterator();
92 for (int pos = 0, alen = a.length; pos < alen; pos++)
98 System.println("Unimplemented Collections.sort() invoked");
101 public static void sort(List l, Comparator c)
103 /*Object[] a = l.toArray();
105 ListIterator i = l.listIterator();
106 for (int pos = 0, alen = a.length; pos < alen; pos++)
112 System.println("Unimplemented Collections.sort(l, c) invoked");
116 static final /*<T>*/ int compare(Object/*T*/ o1, Object/*T*/ o2, Comparator/*<? super T>*/ c)
118 return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2);
121 public static /*<T extends Object & Comparable<? super T>>*/
122 Object/*T*/ min(Collection/*<? extends T>*/ c)
128 * Find the minimum element in a Collection, according to a specified
129 * Comparator. This implementation iterates over the Collection, so it
130 * works in linear time.
132 * @param c the Collection to find the minimum element of
133 * @param order the Comparator to order the elements by, or null for natural
135 * @return the minimum element of c
136 * @throws NoSuchElementException if c is empty
137 * @throws ClassCastException if elements in c are not mutually comparable
138 * @throws NullPointerException if null is compared by natural ordering
139 * (only possible when order is null)
141 public static /*<T> T*/Object min(Collection/*<? extends T>*/ c,
142 Comparator/*<? super T>*/ order)
144 Iterator/*<? extends T>*/ itr = c.iterator();
145 Object/*T*/ min = itr.next(); // throws NoSuchElementExcception
146 int csize = c.size();
147 for (int i = 1; i < csize; i++)
149 Object/*T*/ o = itr.next();
150 if (compare(min, o, order) > 0)
156 public static /*<T extends Object & Comparable<? super T>>
157 T*/Object max(Collection/*<? extends T>*/ c)
163 * Find the maximum element in a Collection, according to a specified
164 * Comparator. This implementation iterates over the Collection, so it
165 * works in linear time.
167 * @param c the Collection to find the maximum element of
168 * @param order the Comparator to order the elements by, or null for natural
170 * @return the maximum element of c
171 * @throws NoSuchElementException if c is empty
172 * @throws ClassCastException if elements in c are not mutually comparable
173 * @throws NullPointerException if null is compared by natural ordering
174 * (only possible when order is null)
176 public static /*<T> T*/Object max(Collection/*<? extends T>*/ c,
177 Comparator/*<? super T>*/ order)
179 Iterator/*<? extends T>*/ itr = c.iterator();
180 Object/*T*/ max = itr.next(); // throws NoSuchElementException
181 int csize = c.size();
182 for (int i = 1; i < csize; i++)
184 Object/*T*/ o = itr.next();
185 if (compare(max, o, order) < 0)
190 } // class Collections