public class Collections extends Object
The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null.
The documentation for the polymorphic algorithms contained in this class generally includes a brief description of the implementation. Such descriptions should be regarded as implementation notes, rather than parts of the specification. Implementors should feel free to substitute other algorithms, so long as the specification itself is adhered to.
The "destructive" algorithms contained in this class, that is, the algorithms that modify the collection on which they operate, are specified to throw UnsupportedOperationException if the collection does not support the appropriate mutation primitive(s), such as the set method. These algorithms may, but are not required to, throw this exception if an invocation would have no effect on the collection. For example, invoking the sort method on an unmodifiable list that is already sorted may or may not throw UnsupportedOperationException.
This class is a member of the Java Collections Framework.
Collection
,
Set
,
List
,
Map
Modifier and Type | Method and Description |
---|---|
static <T> boolean |
addAll(Collection<? super T> c,
T... elements)
Adds all of the specified elements to the specified collection.
|
static <T> int |
binarySearch(List<? extends Comparable<? super T>> list,
T key)
Searches the specified list for the specified object using the binary
search algorithm.
|
static <T> int |
binarySearch(List<? extends T> list,
T key,
Comparator<? super T> c)
Searches the specified list for the specified object using the binary
search algorithm.
|
static <T> void |
copy(List<? super T> dest,
List<? extends T> src)
Copies all of the elements from one list into another.
|
static boolean |
disjoint(Collection<?> c1,
Collection<?> c2)
Returns
true if the two specified collections have no
elements in common. |
static <T> Enumeration<T> |
enumeration(Collection<T> c)
Returns an enumeration over the specified collection.
|
static <T> void |
fill(List<? super T> list,
T obj)
Replaces all of the elements of the specified list with the specified
element.
|
static int |
frequency(Collection<?> c,
Object o)
Returns the number of elements in the specified collection equal to the
specified object.
|
static int |
indexOfSubList(List<?> source,
List<?> target)
Returns the starting position of the first occurrence of the specified
target list within the specified source list, or -1 if there is no
such occurrence.
|
static int |
lastIndexOfSubList(List<?> source,
List<?> target)
Returns the starting position of the last occurrence of the specified
target list within the specified source list, or -1 if there is no such
occurrence.
|
static <T> ArrayList<T> |
list(Enumeration<T> e)
Returns an array list containing the elements returned by the
specified enumeration in the order they are returned by the
enumeration.
|
static <T extends Object & Comparable<? super T>> |
max(Collection<? extends T> coll)
Returns the maximum element of the given collection, according to the
natural ordering of its elements.
|
static <T> T |
max(Collection<? extends T> coll,
Comparator<? super T> comp)
Returns the maximum element of the given collection, according to the
order induced by the specified comparator.
|
static <T extends Object & Comparable<? super T>> |
min(Collection<? extends T> coll)
Returns the minimum element of the given collection, according to the
natural ordering of its elements.
|
static <T> T |
min(Collection<? extends T> coll,
Comparator<? super T> comp)
Returns the minimum element of the given collection, according to the
order induced by the specified comparator.
|
static <T> boolean |
replaceAll(List<T> list,
T oldVal,
T newVal)
Replaces all occurrences of one specified value in a list with another.
|
static void |
reverse(List<?> list)
Reverses the order of the elements in the specified list.
|
static <T> Comparator<T> |
reverseOrder()
Returns a comparator that imposes the reverse of the natural
ordering on a collection of objects that implement the
Comparable interface. |
static <T> Comparator<T> |
reverseOrder(Comparator<T> cmp)
Returns a comparator that imposes the reverse ordering of the specified
comparator.
|
static void |
rotate(List<?> list,
int distance)
Rotates the elements in the specified list by the specified distance.
|
static void |
shuffle(List<?> list)
Randomly permutes the specified list using a default source of
randomness.
|
static void |
shuffle(List<?> list,
Random rnd)
Randomly permute the specified list using the specified source of
randomness.
|
static <T extends Comparable<? super T>> |
sort(List<T> list)
Sorts the specified list into ascending order, according to the
natural ordering of its elements.
|
static <T> void |
sort(List<T> list,
Comparator<? super T> c)
Sorts the specified list according to the order induced by the
specified comparator.
|
static void |
swap(List<?> list,
int i,
int j)
Swaps the elements at the specified positions in the specified list.
|
public static <T> boolean addAll(Collection<? super T> c, T... elements)
When elements are specified individually, this method provides a convenient way to add a few elements to an existing collection:
Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
T
- the class of the elements to add and of the collectionc
- the collection into which elements are to be insertedelements
- the elements to insert into cUnsupportedOperationException
- if c does not support
the add operationNullPointerException
- if elements contains one or more
null values and c does not permit null elements, or
if c or elements are nullIllegalArgumentException
- if some property of a value in
elements prevents it from being added to cCollection.addAll(Collection)
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
sort(List)
method) prior to making this
call. If it is not sorted, the results are undefined. If the list
contains multiple elements equal to the specified object, there is no
guarantee which one will be found.
This method runs in log(n) time for a "random access" list (which
provides near-constant-time positional access). If the specified list
does not implement the RandomAccess
interface and is large,
this method will do an iterator-based binary search that performs
O(n) link traversals and O(log n) element comparisons.
T
- the class of the objects in the listlist
- the list to be searched.key
- the key to be searched for.ClassCastException
- if the list contains elements that are not
mutually comparable (for example, strings and
integers), or the search key is not mutually comparable
with the elements of the list.public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
sort(List, Comparator)
method), prior to making this call. If it is
not sorted, the results are undefined. If the list contains multiple
elements equal to the specified object, there is no guarantee which one
will be found.
This method runs in log(n) time for a "random access" list (which
provides near-constant-time positional access). If the specified list
does not implement the RandomAccess
interface and is large,
this method will do an iterator-based binary search that performs
O(n) link traversals and O(log n) element comparisons.
T
- the class of the objects in the listlist
- the list to be searched.key
- the key to be searched for.c
- the comparator by which the list is ordered.
A null value indicates that the elements'
natural ordering should be used.ClassCastException
- if the list contains elements that are not
mutually comparable using the specified comparator,
or the search key is not mutually comparable with the
elements of the list using this comparator.public static <T> void copy(List<? super T> dest, List<? extends T> src)
This method runs in linear time.
T
- the class of the objects in the listdest
- The destination list.src
- The source list.IndexOutOfBoundsException
- if the destination list is too small
to contain the entire source List.UnsupportedOperationException
- if the destination list's
list-iterator does not support the set operation.public static boolean disjoint(Collection<?> c1, Collection<?> c2)
true
if the two specified collections have no
elements in common.
Care must be exercised if this method is used on collections that
do not comply with the general contract for Collection
.
Implementations may elect to iterate over either collection and test
for containment in the other collection (or to perform any equivalent
computation). If either collection uses a nonstandard equality test
whose ordering is not compatible with equals, both
collections must use the same nonstandard equality test, or the
result of this method is undefined.
Care must also be exercised when using collections that have restrictions on the elements that they may contain. Collection implementations are allowed to throw exceptions for any operation involving elements they deem ineligible. For absolute safety the specified collections should contain only elements which are eligible elements for both collections.
Note that it is permissible to pass the same collection in both
parameters, in which case the method will return true
if and
only if the collection is empty.
c1
- a collectionc2
- a collectiontrue
if the two specified collections have no
elements in common.NullPointerException
- if either collection is null
.NullPointerException
- if one collection contains a null
element and null
is not an eligible element for the other collection.
(optional)ClassCastException
- if one collection contains an element that is
of a type which is ineligible for the other collection.
(optional)public static <T> Enumeration<T> enumeration(Collection<T> c)
T
- the class of the objects in the listc
- the collection for which an enumeration is to be returned.Enumeration
public static <T> void fill(List<? super T> list, T obj)
This method runs in linear time.
T
- the class of the objects in the listlist
- the list to be filled with the specified element.obj
- The element with which to fill the specified list.UnsupportedOperationException
- if the specified list or its
list-iterator does not support the set operation.public static int frequency(Collection<?> c, Object o)
c
- the collection in which to determine the frequency
of oo
- the object whose frequency is to be determinedNullPointerException
- if c is nullpublic static int indexOfSubList(List<?> source, List<?> target)
i
such that source.subList(i, i+target.size()).equals(target)
,
or -1 if there is no such index. (Returns -1 if
target.size() > source.size()
.)
This implementation uses the "brute force" technique of scanning over the source list, looking for a match with the target at each location in turn.
source
- the list in which to search for the first occurrence
of target.target
- the list to search for as a subList of source.public static int lastIndexOfSubList(List<?> source, List<?> target)
i
such that source.subList(i, i+target.size()).equals(target)
,
or -1 if there is no such index. (Returns -1 if
target.size() > source.size()
.)
This implementation uses the "brute force" technique of iterating over the source list, looking for a match with the target at each location in turn.
source
- the list in which to search for the last occurrence
of target.target
- the list to search for as a subList of source.public static <T> ArrayList<T> list(Enumeration<T> e)
T
- the class of the objects in the liste
- enumeration providing elements for the returned
array listEnumeration
,
ArrayList
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
This method iterates over the entire collection, hence it requires time proportional to the size of the collection.
T
- the class of the objects in the collectioncoll
- the collection whose maximum element is to be determined.ClassCastException
- if the collection contains elements that are
not mutually comparable (for example, strings and
integers).NoSuchElementException
- if the collection is empty.Comparable
public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
This method iterates over the entire collection, hence it requires time proportional to the size of the collection.
T
- the class of the objects in the collectioncoll
- the collection whose maximum element is to be determined.comp
- the comparator with which to determine the maximum element.
A null value indicates that the elements' natural
ordering should be used.ClassCastException
- if the collection contains elements that are
not mutually comparable using the specified comparator.NoSuchElementException
- if the collection is empty.Comparable
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
This method iterates over the entire collection, hence it requires time proportional to the size of the collection.
T
- the class of the objects in the collectioncoll
- the collection whose minimum element is to be determined.ClassCastException
- if the collection contains elements that are
not mutually comparable (for example, strings and
integers).NoSuchElementException
- if the collection is empty.Comparable
public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
This method iterates over the entire collection, hence it requires time proportional to the size of the collection.
T
- the class of the objects in the collectioncoll
- the collection whose minimum element is to be determined.comp
- the comparator with which to determine the minimum element.
A null value indicates that the elements' natural
ordering should be used.ClassCastException
- if the collection contains elements that are
not mutually comparable using the specified comparator.NoSuchElementException
- if the collection is empty.Comparable
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)
T
- the class of the objects in the listlist
- the list in which replacement is to occur.oldVal
- the old value to be replaced.newVal
- the new value with which oldVal is to be
replaced.UnsupportedOperationException
- if the specified list or
its list-iterator does not support the set operation.public static void reverse(List<?> list)
This method runs in linear time.
list
- the list whose elements are to be reversed.UnsupportedOperationException
- if the specified list or
its list-iterator does not support the set operation.public static <T> Comparator<T> reverseOrder()
Comparable
interface. (The natural ordering is the ordering
imposed by the objects' own compareTo
method.) This enables a
simple idiom for sorting (or maintaining) collections (or arrays) of
objects that implement the Comparable
interface in
reverse-natural-order. For example, suppose a
is an array of
strings. Then: Arrays.sort(a, Collections.reverseOrder());sorts the array in reverse-lexicographic (alphabetical) order.
T
- the class of the objects in the listComparable
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)
null
, this method is
equivalent to reverseOrder()
(in other words, it returns a
comparator that imposes the reverse of the natural ordering on
a collection of objects that implement the Comparable interface).T
- the class of the objects in the listcmp
- a comparator who's ordering is to be reversed by the returned
comparator or null
public static void rotate(List<?> list, int distance)
For example, suppose list comprises [t, a, n, k, s]. After invoking Collections.rotate(list, 1) (or Collections.rotate(list, -4)), list will comprise [s, t, a, n, k].
Note that this method can usefully be applied to sublists to move one or more elements within a list while preserving the order of the remaining elements. For example, the following idiom moves the element at index j forward to position k (which must be greater than or equal to j):
Collections.rotate(list.subList(j, k+1), -1);To make this concrete, suppose list comprises [a, b, c, d, e]. To move the element at index 1 (b) forward two positions, perform the following invocation:
Collections.rotate(l.subList(1, 4), -1);The resulting list is [a, c, d, b, e].
To move more than one element forward, increase the absolute value of the rotation distance. To move elements backward, use a positive shift distance.
If the specified list is small or implements the RandomAccess
interface, this implementation exchanges the first
element into the location it should go, and then repeatedly exchanges
the displaced element into the location it should go until a displaced
element is swapped into the first element. If necessary, the process
is repeated on the second and successive elements, until the rotation
is complete. If the specified list is large and doesn't implement the
RandomAccess interface, this implementation breaks the
list into two sublist views around index -distance mod size.
Then the reverse(List)
method is invoked on each sublist view,
and finally it is invoked on the entire list. For a more complete
description of both algorithms, see Section 2.3 of Jon Bentley's
Programming Pearls (Addison-Wesley, 1986).
list
- the list to be rotated.distance
- the distance to rotate the list. There are no
constraints on this value; it may be zero, negative, or
greater than list.size().UnsupportedOperationException
- if the specified list or
its list-iterator does not support the set operation.public static void shuffle(List<?> list)
The hedge "approximately" is used in the foregoing description because default source of randomness is only approximately an unbiased source of independently chosen bits. If it were a perfect source of randomly chosen bits, then the algorithm would choose permutations with perfect uniformity.
This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.
This method runs in linear time. If the specified list does not
implement the RandomAccess
interface and is large, this
implementation dumps the specified list into an array before shuffling
it, and dumps the shuffled array back into the list. This avoids the
quadratic behavior that would result from shuffling a "sequential
access" list in place.
list
- the list to be shuffled.UnsupportedOperationException
- if the specified list or
its list-iterator does not support the set operation.public static void shuffle(List<?> list, Random rnd)
This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.
This method runs in linear time. If the specified list does not
implement the RandomAccess
interface and is large, this
implementation dumps the specified list into an array before shuffling
it, and dumps the shuffled array back into the list. This avoids the
quadratic behavior that would result from shuffling a "sequential
access" list in place.
list
- the list to be shuffled.rnd
- the source of randomness to use to shuffle the list.UnsupportedOperationException
- if the specified list or its
list-iterator does not support the set operation.public static <T extends Comparable<? super T>> void sort(List<T> list)
Comparable
interface. Furthermore, all elements in the list must be
mutually comparable (that is, e1.compareTo(e2)
must not throw a ClassCastException
for any elements
e1
and e2
in the list).
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
The specified list must be modifiable, but need not be resizable.
T
- the class of the objects in the listlist
- the list to be sorted.ClassCastException
- if the list contains elements that are not
mutually comparable (for example, strings and integers).UnsupportedOperationException
- if the specified list's
list-iterator does not support the set
operation.IllegalArgumentException
- (optional) if the implementation
detects that the natural ordering of the list elements is
found to violate the Comparable
contractpublic static <T> void sort(List<T> list, Comparator<? super T> c)
c.compare(e1, e2)
must not throw a ClassCastException
for any elements e1
and e2
in the list).
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
The specified list must be modifiable, but need not be resizable.
T
- the class of the objects in the listlist
- the list to be sorted.c
- the comparator to determine the order of the list. A
null
value indicates that the elements' natural
ordering should be used.ClassCastException
- if the list contains elements that are not
mutually comparable using the specified comparator.UnsupportedOperationException
- if the specified list's
list-iterator does not support the set
operation.IllegalArgumentException
- (optional) if the comparator is
found to violate the Comparator
contractpublic static void swap(List<?> list, int i, int j)
list
- The list in which to swap elements.i
- the index of one element to be swapped.j
- the index of the other element to be swapped.IndexOutOfBoundsException
- if either i or j
is out of range (i < 0 || i >= list.size()
|| j < 0 || j >= list.size()).Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved. Use of this specification is subject to license terms.