Section 17.1. Generic Algorithms

17.1. Generic Algorithms

The generic algorithms fall into four major categories: changing element order in a list, changing the contents of a list, finding extreme values in a collection, and finding specific values in a list. They represent reusable functionality, in that they can be applied to Lists (or in some cases to Collections) of any type. Generifying the types of these methods has led to some fairly complicated declarations, so each section discusses the declarations briefly after presenting them.

17.1.1. Changing the Order of List Elements

There are seven methods for reordering lists in various ways. The simplest of these is swap, which exchanges two elements and, in the case of a List which implements RandomAccess, executes in constant time. The most complex is sort, which transfers the elements into an array, applies a merge sort to them in time O(n log n), and then returns them to the List. All of the remaining methods execute in time O(n).

 void reverse(List<?> list)           // reverse the order of the elements void rotate(List<?> list, int distance)           // rotate the elements of the list; the element at index           // i is moved to index (distance + i) % list.size() void shuffle(List<?> list)           // randomly permute the list elements void shuffle(List<?> list, Random rnd)           // randomly permute the list using the randomness source rnd <T extends Comparable<? super T>> void sort(List<T> list)           // sort the supplied list using natural ordering <T> void sort(List<T> list, Comparator<? super T> c)           // sort the supplied list using the supplied ordering void swap(List<?> list, int i, int j)           // swap the elements at the specified positions 

For each of these methods, except sort and swap, there are two algorithms, one using iteration and another using random access. The method sort TRansfers the List elements to an array, where they are sorted usingin the current implementationa mergesort algorithm with n log n performance. The method swap always uses random access. The standard implementations for the other methods in this section use either iteration or random access, depending on whether the list implements the RandomAccess interface (see Section 8.3). If it does, the implementation chooses the random-access algorithm; even for a list that does not implement RandomAccess, however, the random-access algorithms are used if the list size is below a given threshold, determined on a per-method basis by performance testing.

17.1.2. Changing the Contents of a List

These methods change some or all of the elements of a list. The method copy transfers elements from the source list into an initial sublist of the destination list (which has to be long enough to accommodate them), leaving any remaining elements of the destination list unchanged. The method fill replaces every element of a list with a specified object, and replaceAll replaces every occurrence of one value in a list with anotherwhere either the old or new value can be nullreturning TRue if any replacements were made.

 <T> void copy(List<? super T> dest, List<? extends T> src)           // copy all of the elements from one list into another <T> void fill(List<? super T> list, T obj)           // replace every element of list with obj <T> boolean replaceAll(List<T> list, T oldVal, T newVal)           // replace all occurrences of oldVal in list with newVal 

The signatures of these methods can be explained using the Get and Put Principle (see Section 2.4). The signature of copy was discussed in Section 2.3. It gets elements from the source list and puts them into the destination, so the types of these lists are, respectively, ? extends T and ? super T. This fits with the intuition that the type of the source list elements should be a subtype of the destination list. Although there are simpler alternatives for the signature of copy, Section 2.3 makes the case that using wildcards where possible widens the range of permissible calls.

For fill, the Get and Put Principle dictates that you should use super if you are putting values into a parameterized collection and, for replaceAll, it states that if you are putting values into and getting values out of the same structure, you should not use wildcards at all.

17.1.3. Finding Extreme Values in a Collection

The methods min and max are supplied for this purpose, each with two overloadsone using natural ordering of the elements, and one accepting a Comparator to impose an ordering. They execute in linear time.

 <T extends Object & Comparable<? super T>>   T max(Collection<? extends T> coll)  // return the maximum element                                        // using natural ordering <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)                                        // return the maximum element                                        // using the supplied comparator <T extends Object & Comparable<? super T>>   T min(Collection<? extends T> coll)  // return the minimum element                                        // using natural ordering <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)                                        // return the minimum element                                        // using the supplied comparator 

Sections 3.6 and 8.4 explain these methods and the types assigned to them.

17.1.4. Finding Specific Values in a List

Methods in this group locate elements or groups of elements in a List, again choosing between alternative algorithms on the basis of the list's size and whether it implements RandomAccess.

 <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)           // search for key using binary search        <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)           // search for key using binary search int indexOfSubList(List<?> source, List<?> target)           // find the first sublist of source which matches target int lastIndexOfSubList(List<?> source, List<?> target)           // find the last sublist of source which matches target 

The signature of the first binarySearch overload says that you can use it to search for a key of type T in a list of objects that can have any type that can be compared with objects of type T. The second is like the Comparator overloads of min and max except that, in this case, the type parameter of the Collection must be a subtype of the type of the key, which in turn must be a subtype of the type parameter of the Comparator.

Binary search requires a sorted list for its operation. At the start of a search, the range of indices in which the search value may occur corresponds to the entire list. The binary search algorithm samples an element in the middle of this range, using the value of the sampled element to determine whether the new range should be the part of the old range above or the part below the index of the element. A third possibility is that the sampled value is equal to the search value, in which case the search is complete. Since each step halves the size of the range, m steps are required to find a search value in a list of length 2^m, and the time complexity for a list of length n is O(log n).

The methods indexOfSubList and lastIndexOfSubList do not require sorted lists for their operation. Their signatures allow the source and target lists to contain elements of any type (remember that the two wildcards may stand for two different types). The design decision behind these signatures is the same as that behind the Collection methods containsAll, retainAll, and removeAll (see Section 2.6).