java.util
Class Collections
Utility class consisting of static methods that operate on, or return
Collections. Contains methods to sort, search, reverse, fill and shuffle
Collections, methods to facilitate interoperability with legacy APIs that
are unaware of collections, a method to return a list which consists of
multiple copies of one element, and methods which "wrap" collections to give
them extra properties, such as thread-safety and unmodifiability.
All methods which take a collection throw a
NullPointerException
if
that collection is null. Algorithms which can change a collection may, but
are not required, to throw the
UnsupportedOperationException
that
the underlying collection would throw during an attempt at modification.
For example,
Collections.singleton("").addAll(Collections.EMPTY_SET)
does not throw a exception, even though addAll is an unsupported operation
on a singleton; the reason for this is that addAll did not attempt to
modify the set.
static List | EMPTY_LIST - An immutable, serializable, empty List, which implements RandomAccess.
|
static Map | EMPTY_MAP - An immutable, serializable, empty Map.
|
static Set | EMPTY_SET - An immutable, serializable, empty Set.
|
static int | binarySearch(List l, Object key) - Perform a binary search of a List for a key, using the natural ordering of
the elements.
|
static int | binarySearch(List l, Object key, Comparator c) - Perform a binary search of a List for a key, using a supplied Comparator.
|
static void | copy(List dest, List source) - Copy one list to another.
|
static Enumeration | enumeration(Collection c) - Returns an Enumeration over a collection.
|
static void | fill(List l, Object val) - Replace every element of a list with a given value.
|
static int | indexOfSubList(List source, List target) - Returns the starting index where the specified sublist first occurs
in a larger list, or -1 if there is no matching position.
|
static int | lastIndexOfSubList(List source, List target) - Returns the starting index where the specified sublist last occurs
in a larger list, or -1 if there is no matching position.
|
static ArrayList | list(Enumeration e) - Returns an ArrayList holding the elements visited by a given
Enumeration.
|
static Object | max(Collection c) - Find the maximum element in a Collection, according to the natural
ordering of the elements.
|
static Object | max(Collection c, Comparator order) - Find the maximum element in a Collection, according to a specified
Comparator.
|
static Object | min(Collection c) - Find the minimum element in a Collection, according to the natural
ordering of the elements.
|
static Object | min(Collection c, Comparator order) - Find the minimum element in a Collection, according to a specified
Comparator.
|
static List | nCopies(int n, Object o) - Creates an immutable list consisting of the same object repeated n times.
|
static boolean | replaceAll(List list, Object oldval, Object newval) - Replace all instances of one object with another in the specified list.
|
static void | reverse(List l) - Reverse a given list.
|
static Comparator | reverseOrder() - Get a comparator that implements the reverse of natural ordering.
|
static void | rotate(List list, int distance) - Rotate the elements in a list by a specified distance.
|
static void | shuffle(List l) - Shuffle a list according to a default source of randomness.
|
static void | shuffle(List l, Random r) - Shuffle a list according to a given source of randomness.
|
static Set | singleton(Object o) - Obtain an immutable Set consisting of a single element.
|
static List | singletonList(Object o) - Obtain an immutable List consisting of a single element.
|
static Map | singletonMap(Object key, Object value) - Obtain an immutable Map consisting of a single key-value pair.
|
static void | sort(List l) - Sort a list according to the natural ordering of its elements.
|
static void | sort(List l, Comparator c) - Sort a list according to a specified Comparator.
|
static void | swap(List l, int i, int j) - Swaps the elements at the specified positions within the list.
|
static Collection | synchronizedCollection(Collection c) - Returns a synchronized (thread-safe) collection wrapper backed by the
given collection.
|
static List | synchronizedList(List l) - Returns a synchronized (thread-safe) list wrapper backed by the
given list.
|
static Map | synchronizedMap(Map m) - Returns a synchronized (thread-safe) map wrapper backed by the given
map.
|
static Set | synchronizedSet(Set s) - Returns a synchronized (thread-safe) set wrapper backed by the given
set.
|
static SortedMap | synchronizedSortedMap(SortedMap m) - Returns a synchronized (thread-safe) sorted map wrapper backed by the
given map.
|
static SortedSet | synchronizedSortedSet(SortedSet s) - Returns a synchronized (thread-safe) sorted set wrapper backed by the
given set.
|
static Collection | unmodifiableCollection(Collection c) - Returns an unmodifiable view of the given collection.
|
static List | unmodifiableList(List l) - Returns an unmodifiable view of the given list.
|
static Map | unmodifiableMap(Map m) - Returns an unmodifiable view of the given map.
|
static Set | unmodifiableSet(Set s) - Returns an unmodifiable view of the given set.
|
static SortedMap | unmodifiableSortedMap(SortedMap m) - Returns an unmodifiable view of the given sorted map.
|
static SortedSet | unmodifiableSortedSet(SortedSet s) - Returns an unmodifiable view of the given sorted set.
|
clone , equals , finalize , getClass , hashCode , notify , notifyAll , toString , wait , wait , wait |
EMPTY_LIST
public static final List EMPTY_LIST
An immutable, serializable, empty List, which implements RandomAccess.
EMPTY_MAP
public static final Map EMPTY_MAP
An immutable, serializable, empty Map.
EMPTY_SET
public static final Set EMPTY_SET
An immutable, serializable, empty Set.
binarySearch
public static int binarySearch(List l,
Object key)
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.
This algorithm behaves in log(n) time for
RandomAccess
lists,
and uses a linear search with O(n) link traversals and log(n) comparisons
with
AbstractSequentialList
lists. Note: although the
specification allows for an infinite loop if the list is unsorted, it will
not happen in this (Classpath) implementation.
l
- the list to search (must be sorted)key
- the value to search for
- 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
binarySearch
public static int binarySearch(List l,
Object key,
Comparator c)
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.
This algorithm behaves in log(n) time for
RandomAccess
lists,
and uses a linear search with O(n) link traversals and log(n) comparisons
with
AbstractSequentialList
lists. Note: although the
specification allows for an infinite loop if the list is unsorted, it will
not happen in this (Classpath) implementation.
l
- the list to search (must be sorted)key
- the value to search forc
- the comparator by which the list is sorted
- 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
copy
public static void copy(List dest,
List source)
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.
dest
- the destination listsource
- the source list
enumeration
public static Enumeration enumeration(Collection c)
Returns an Enumeration over a collection. This allows interoperability
with legacy APIs that require an Enumeration as input.
c
- the Collection to iterate over
- an Enumeration backed by an Iterator over c
fill
public static void fill(List l,
Object val)
Replace every element of a list with a given value. This method runs in
linear time.
l
- the list to fill.val
- the object to vill the list with.
indexOfSubList
public static int indexOfSubList(List source,
List target)
Returns the starting index where the specified sublist first occurs
in a larger list, or -1 if there is no matching position. If
target.size() > source.size()
, this returns -1,
otherwise this implementation uses brute force, checking for
source.sublist(i, i + target.size()).equals(target)
for all possible i.
source
- the list to searchtarget
- the sublist to search for
- the index where found, or -1
lastIndexOfSubList
public static int lastIndexOfSubList(List source,
List target)
Returns the starting index where the specified sublist last occurs
in a larger list, or -1 if there is no matching position. If
target.size() > source.size()
, this returns -1,
otherwise this implementation uses brute force, checking for
source.sublist(i, i + target.size()).equals(target)
for all possible i.
source
- the list to searchtarget
- the sublist to search for
- the index where found, or -1
list
public static ArrayList list(Enumeration e)
Returns an ArrayList holding the elements visited by a given
Enumeration. This method exists for interoperability between legacy
APIs and the new Collection API.
e
- the enumeration to put in a list
- a list containing the enumeration elements
max
public static Object max(Collection c)
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.
c
- the Collection to find the maximum element of
max
public static Object max(Collection c,
Comparator order)
Find the maximum element in a Collection, according to a specified
Comparator. This implementation iterates over the Collection, so it
works in linear time.
c
- the Collection to find the maximum element oforder
- the Comparator to order the elements by, or null for natural
ordering
min
public static Object min(Collection c)
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.
c
- the Collection to find the minimum element of
min
public static Object min(Collection c,
Comparator order)
Find the minimum element in a Collection, according to a specified
Comparator. This implementation iterates over the Collection, so it
works in linear time.
c
- the Collection to find the minimum element oforder
- the Comparator to order the elements by, or null for natural
ordering
nCopies
public static List nCopies(int n,
Object o)
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.
n
- the number of times to repeat the objecto
- the object to repeat
- a List consisting of n copies of o
replaceAll
public static boolean replaceAll(List list,
Object oldval,
Object newval)
Replace all instances of one object with another in the specified list.
The list does not change size. An element e is replaced if
oldval == null ? e == null : oldval.equals(e)
.
list
- the list to iterate overoldval
- the element to replacenewval
- the new value for the element
true
if a replacement occurred.
reverse
public static void reverse(List l)
Reverse a given list. This method works in linear time.
reverseOrder
public static Comparator reverseOrder()
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.
- a comparator that imposes reverse natural ordering
rotate
public static void rotate(List list,
int distance)
Rotate the elements in a list by a specified distance. After calling this
method, the element now at index
i
was formerly at index
(i - distance) mod list.size()
. The list size is unchanged.
For example, suppose a list contains
[t, a, n, k, s]
. After
either
Collections.rotate(l, 4)
or
Collections.rotate(l, -1)
, the new contents are
[s, t, a, n, k]
. This can be applied to sublists to rotate
just a portion of the list. For example, to move element
a
forward two positions in the original example, use
Collections.rotate(l.subList(1, 3+1), -1)
, which will
result in
[t, n, k, a, s]
.
If the list is small or implements
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
-distance mod size
, calls
reverse(List)
on the
pieces, then reverses the overall list.
list
- the list to rotatedistance
- the distance to rotate by; unrestricted in value
shuffle
public static void shuffle(List l)
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)).
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.
This method operates in linear time. To do this on large lists which do
not implement
RandomAccess
, a temporary array is used to acheive
this speed, since it would be quadratic access otherwise.
shuffle
public static void shuffle(List l,
Random r)
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)).
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.
This method operates in linear time. To do this on large lists which do
not implement
RandomAccess
, a temporary array is used to acheive
this speed, since it would be quadratic access otherwise.
l
- the list to shuffler
- the source of randomness to use for the shuffle
singleton
public static Set singleton(Object o)
Obtain an immutable Set consisting of a single element. The return value
of this method is Serializable.
- an immutable Set containing only o
singletonList
public static List singletonList(Object o)
Obtain an immutable List consisting of a single element. The return value
of this method is Serializable, and implements RandomAccess.
- an immutable List containing only o
singletonMap
public static Map singletonMap(Object key,
Object value)
Obtain an immutable Map consisting of a single key-value pair.
The return value of this method is Serializable.
key
- the single keyvalue
- the single value
- an immutable Map containing only the single key-value pair
sort
public static void sort(List l)
Sort a list according to the natural ordering of its elements. The list
must be modifiable, but can be of fixed size. The sort algorithm is
precisely that used by Arrays.sort(Object[]), which offers guaranteed
nlog(n) performance. This implementation dumps the list into an array,
sorts the array, and then iterates over the list setting each element from
the array.
sort
public static void sort(List l,
Comparator c)
Sort a list according to a specified Comparator. The list must be
modifiable, but can be of fixed size. The sort algorithm is precisely that
used by Arrays.sort(Object[], Comparator), which offers guaranteed
nlog(n) performance. This implementation dumps the list into an array,
sorts the array, and then iterates over the list setting each element from
the array.
l
- the List to sortc
- the Comparator specifying the ordering for the elements, or
null for natural ordering
swap
public static void swap(List l,
int i,
int j)
Swaps the elements at the specified positions within the list. Equal
positions have no effect.
l
- the list to work oni
- the first index to swapj
- the second index
synchronizedCollection
public static Collection synchronizedCollection(Collection c)
Returns a synchronized (thread-safe) collection wrapper backed by the
given collection. Notice that element access through the iterators
is thread-safe, but if the collection can be structurally modified
(adding or removing elements) then you should synchronize around the
iteration to avoid non-deterministic behavior:
Collection c = Collections.synchronizedCollection(new Collection(...));
...
synchronized (c)
{
Iterator i = c.iterator();
while (i.hasNext())
foo(i.next());
}
Since the collection might be a List or a Set, and those have incompatible
equals and hashCode requirements, this relies on Object's implementation
rather than passing those calls on to the wrapped collection. The returned
Collection implements Serializable, but can only be serialized if
the collection it wraps is likewise Serializable.
c
- the collection to wrap
- a synchronized view of the collection
synchronizedList
public static List synchronizedList(List l)
Returns a synchronized (thread-safe) list wrapper backed by the
given list. Notice that element access through the iterators
is thread-safe, but if the list can be structurally modified
(adding or removing elements) then you should synchronize around the
iteration to avoid non-deterministic behavior:
List l = Collections.synchronizedList(new List(...));
...
synchronized (l)
{
Iterator i = l.iterator();
while (i.hasNext())
foo(i.next());
}
The returned List implements Serializable, but can only be serialized if
the list it wraps is likewise Serializable. In addition, if the wrapped
list implements RandomAccess, this does too.
- a synchronized view of the list
synchronizedMap
public static Map synchronizedMap(Map m)
Returns a synchronized (thread-safe) map wrapper backed by the given
map. Notice that element access through the collection views and their
iterators are thread-safe, but if the map can be structurally modified
(adding or removing elements) then you should synchronize around the
iteration to avoid non-deterministic behavior:
Map m = Collections.synchronizedMap(new Map(...));
...
Set s = m.keySet(); // safe outside a synchronized block
synchronized (m) // synch on m, not s
{
Iterator i = s.iterator();
while (i.hasNext())
foo(i.next());
}
The returned Map implements Serializable, but can only be serialized if
the map it wraps is likewise Serializable.
- a synchronized view of the map
synchronizedSet
public static Set synchronizedSet(Set s)
Returns a synchronized (thread-safe) set wrapper backed by the given
set. Notice that element access through the iterator is thread-safe, but
if the set can be structurally modified (adding or removing elements)
then you should synchronize around the iteration to avoid
non-deterministic behavior:
Set s = Collections.synchronizedSet(new Set(...));
...
synchronized (s)
{
Iterator i = s.iterator();
while (i.hasNext())
foo(i.next());
}
The returned Set implements Serializable, but can only be serialized if
the set it wraps is likewise Serializable.
- a synchronized view of the set
synchronizedSortedMap
public static SortedMap synchronizedSortedMap(SortedMap m)
Returns a synchronized (thread-safe) sorted map wrapper backed by the
given map. Notice that element access through the collection views,
subviews, and their iterators are thread-safe, but if the map can be
structurally modified (adding or removing elements) then you should
synchronize around the iteration to avoid non-deterministic behavior:
SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...));
...
Set s = m.keySet(); // safe outside a synchronized block
SortedMap m2 = m.headMap(foo); // safe outside a synchronized block
Set s2 = m2.keySet(); // safe outside a synchronized block
synchronized (m) // synch on m, not m2, s or s2
{
Iterator i = s.iterator();
while (i.hasNext())
foo(i.next());
i = s2.iterator();
while (i.hasNext())
bar(i.next());
}
The returned SortedMap implements Serializable, but can only be
serialized if the map it wraps is likewise Serializable.
m
- the sorted map to wrap
- a synchronized view of the sorted map
synchronizedSortedSet
public static SortedSet synchronizedSortedSet(SortedSet s)
Returns a synchronized (thread-safe) sorted set wrapper backed by the
given set. Notice that element access through the iterator and through
subviews are thread-safe, but if the set can be structurally modified
(adding or removing elements) then you should synchronize around the
iteration to avoid non-deterministic behavior:
SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...));
...
SortedSet s2 = s.headSet(foo); // safe outside a synchronized block
synchronized (s) // synch on s, not s2
{
Iterator i = s2.iterator();
while (i.hasNext())
foo(i.next());
}
The returned SortedSet implements Serializable, but can only be
serialized if the set it wraps is likewise Serializable.
s
- the sorted set to wrap
- a synchronized view of the sorted set
unmodifiableCollection
public static Collection unmodifiableCollection(Collection c)
Returns an unmodifiable view of the given collection. This allows
"read-only" access, although changes in the backing collection show up
in this view. Attempts to modify the collection directly or via iterators
will fail with
UnsupportedOperationException
. Although this view
prevents changes to the structure of the collection and its elements, the values
referenced by the objects in the collection can still be modified.
Since the collection might be a List or a Set, and those have incompatible
equals and hashCode requirements, this relies on Object's implementation
rather than passing those calls on to the wrapped collection. The returned
Collection implements Serializable, but can only be serialized if
the collection it wraps is likewise Serializable.
c
- the collection to wrap
- a read-only view of the collection
unmodifiableList
public static List unmodifiableList(List l)
Returns an unmodifiable view of the given list. This allows
"read-only" access, although changes in the backing list show up
in this view. Attempts to modify the list directly, via iterators, or
via sublists, will fail with
UnsupportedOperationException
.
Although this view prevents changes to the structure of the list and
its elements, the values referenced by the objects in the list can
still be modified.
The returned List implements Serializable, but can only be serialized if
the list it wraps is likewise Serializable. In addition, if the wrapped
list implements RandomAccess, this does too.
- a read-only view of the list
unmodifiableMap
public static Map unmodifiableMap(Map m)
Returns an unmodifiable view of the given map. This allows "read-only"
access, although changes in the backing map show up in this view.
Attempts to modify the map directly, or via collection views or their
iterators will fail with
UnsupportedOperationException
.
Although this view prevents changes to the structure of the map and its
entries, the values referenced by the objects in the map can still be
modified.
The returned Map implements Serializable, but can only be serialized if
the map it wraps is likewise Serializable.
- a read-only view of the map
unmodifiableSet
public static Set unmodifiableSet(Set s)
Returns an unmodifiable view of the given set. This allows
"read-only" access, although changes in the backing set show up
in this view. Attempts to modify the set directly or via iterators
will fail with
UnsupportedOperationException
.
Although this view prevents changes to the structure of the set and its
entries, the values referenced by the objects in the set can still be
modified.
The returned Set implements Serializable, but can only be serialized if
the set it wraps is likewise Serializable.
- a read-only view of the set
unmodifiableSortedMap
public static SortedMap unmodifiableSortedMap(SortedMap m)
Returns an unmodifiable view of the given sorted map. This allows
"read-only" access, although changes in the backing map show up in this
view. Attempts to modify the map directly, via subviews, via collection
views, or iterators, will fail with
UnsupportedOperationException
.
Although this view prevents changes to the structure of the map and its
entries, the values referenced by the objects in the map can still be
modified.
The returned SortedMap implements Serializable, but can only be
serialized if the map it wraps is likewise Serializable.
- a read-only view of the map
unmodifiableSortedSet
public static SortedSet unmodifiableSortedSet(SortedSet s)
Returns an unmodifiable view of the given sorted set. This allows
"read-only" access, although changes in the backing set show up
in this view. Attempts to modify the set directly, via subsets, or via
iterators, will fail with
UnsupportedOperationException
.
Although this view prevents changes to the structure of the set and its
entries, the values referenced by the objects in the set can still be
modified.
The returns SortedSet implements Serializable, but can only be
serialized if the set it wraps is likewise Serializable.
- a read-only view of the set
Collections.java -- Utility class with methods to operate on collections
Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005
Free Software Foundation, Inc.
This file is part of GNU Classpath.
GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING. If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.
Linking this library statically or dynamically with other modules is
making a combined work based on this library. Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.
As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module. An independent module is a module which is not derived from
or based on this library. If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so. If you do not wish to do so, delete this
exception statement from your version.