SCJP : java.util package

Use capabilities in the java.util package to write code to manipulate a list by sorting, performing a binary search, or converting the list to an array. Use capabilities in the java.util package to write code to manipulate an array by sorting, performing a binary search, or converting the array to a list. Use the java.util.Comparator and java.lang.Comparable interfaces to affect the sorting of lists and arrays. Furthermore, recognize the effect of the "natural ordering" of primitive wrapper classes and java.lang.String on sorting.

Interface Collection<E>

The following method from Collection interface returns an array containing all of the elements in this collection. If the collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

The returned array will be "safe" in that no references to it are maintained by this collection. (In other words, this method must allocate a new array even if this collection is backed by an array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs:

Object[] toArray()
					
					

The following method from Collection interface returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array. If the collection fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this collection:

<T> T[] toArray(T[] a)
					
					

If this collection fits in the specified array with room to spare (i.e., the array has more elements than this collection), the element in the array immediately following the end of the collection is set to null. This is useful in determining the length of this collection only if the caller knows that this collection does not contain any null elements.)

If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

Like the toArray method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.

Suppose l is a List known to contain only strings. The following code can be used to dump the list into a newly allocated array of String:

String[] x = (String[]) v.toArray(new String[0]);
					

java.util.Arrays.sort()

The sort methods for the primitive types look like:

void sort (type[] array)
void sort (type[] array, int fromIndex, int toIndex)
					

The second version sorts those elements between the given indices.

For sorting Object types, there are two approaches. For the first approach there are two methods available:

void sort (Object[] array)
void sort (Object[] array, int fromIndex, int toIndex)
					

int compareTo (Object)
					

NOTE, String class implements Comparable interface.

This method defines the "natural ordering" such that comparing object x to y results in a negative number if x is lower than y (on a scale that makes sense for the class), equal to 0 if the objects are identical, and a positive number if x is greater than y.

Your compareTo() method must be written to return a negative, zero, or positive integer according to the ordering rules that make sense for the nature of the objects that the class describes.

For the ALTERNATIVE approach to comparing Object arrays, you create an auxiliary class that implements the java.util.Comparator interface and that knows how to compare and order two objects of interest. This technique is particularly useful if you need to sort classes that you CANNOT RE-WRITE to implement the Comparable interface. The Comparator class has two methods:

int compare (Object obj1, Object obj2)
boolean equals (Object obj1, Object obj2)
					

The compare() method should return a negative, zero, or positive integer, according to the ordering rules that you implement, if obj1 is less than, equal to, or greater than obj2. Similarly, the equals() method compares the objects for equality according to the rules you implement. When using the Comparator technique, the two object array sorting methods are:

void sort (Object[] array, Comparator comp)
void sort (Object[] array, int fromIndex, int toIndex, Comparator comp)
					

java.util.Arrays.binarySearch()

Another useful set of overloaded methods in the Arrays class is the set of binary searching methods:

int binarySearch (type[] array, type key)
int binarySearch (Object[] array, Object key, Comparator comp)
					

There is an overloaded binarySearch() method for each primitive type except boolean and one more for Object. These methods search an array for the given key value. Returns index of the search key, if it is contained in the list. The array to be searched *MUST* be sorted first in ascending order, perhaps by using one of the sort() methods. If it is not sorted, the results are UNDEFINED. If the array contains multiple elements with the specified value, there is NO guarantee which one will be found.

The methods return the index of the search key, if it is contained in the list; otherwise, (-(insertion_point) - 1). The insertion_point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or array.length, if all elements in the array are less than the specified key.

NOTE, this guarantees that the return value will be >= 0 if and only if the key is found.

For the case of Object arrays and the first type of binarySearch() method above, the elements must implement the Comparable interface. If you cannot change the classes to implement this interface, then you can provide a Comparator and use the second type of binarySearch() method shown above.

The class Arrays, provides useful algorithms that operate on arrays. It also provides the static asList() method, which can be used to create List views of arrays. Changes to the List view affects the array and vice versa. The List size is the array size and CANNOT be modified. The asList() method in the Arrays class and the toArray() method in the Collection interface provide the bridge between arrays and collections:

Set mySet = new HashSet(Arrays.asList(myArray));
					

String[] strArray = (String[]) mySet.toArray();
					

The asList(...) method of java.util.Arrays class returns a fixed-size list backed by the specified array. Changes to the returned list "write through" to the array. This method acts as bridge between array-based and collection-based APIs, in combination with Collection.toArray. The returned list is serializable and implements RandomAccess.

This method also provides a convenient way to create a fixed-size list initialized to contain several elements:

List stooges = Arrays.asList("Larry", "Moe", "Curly");
					

public static <T> List<T> asList(T... a)
					
					

java.util.Comparator interface:

					
package java.util;

public interface Comparator<T> {
	int compare(T o1, T o2);
	boolean equals(Object obj);
}

					

java.lang.Comparable interface:

					
package java.lang;

public interface Comparable<T> {
	public int compareTo(T o);
}

					

java.util.Collections

This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.

The following method sorts the specified list into ascending order, according to the natural ordering of its elements. All elements in the list MUST implement the 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).

The specified list must be modifiable, but need not be resizable.

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array:

public static <T extends Comparable<? super T>> void sort(List<T> list)

					

The following method sorts the specified list according to the order induced by the specified comparator. All elements in the list MUST implement the 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).

The specified list must be modifiable, but need not be resizable.

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array:

public static <T> void sort(List<T> list, Comparator<? super T> c)

					

With the help of the method sort(list, comparator) you can for example sort the list in reverse order:

/** Non-Comparable class */
public class WeirdString { 
	private String str;
	
	WeirdString(String str ){
		this.str = str;
	}
}					
					

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class ReverseClient {
	
	public static void main(String ... sss) {
		List myList = new LinkedList();
		String s1 = new String("2345");
		String s2 = new String("12345");		
		String s3 = new String("45");
		String s4 = new String("345");
		WeirdString s5 = new WeirdString("345");
		
		myList.add(s1);
		myList.add(s2);
		myList.add(s3);
		myList.add(s4);
		// myList.add(s5); // WRONG ! See *)
		
		System.out.println("Original list : " + myList);		
		Comparator cmp = Collections.reverseOrder();
		// *) The 'sort(list, comp)' method may throw ClassCastException 
		// if the list contains elements that are not *mutually* 
		// comparable using the specified comparator
		Collections.sort(myList, cmp); 		
		System.out.println("Sorted list (descending order) : " + myList);
	}	
}					
					

Original list : [2345, 12345, 45, 345]
Sorted list (descending order) : [45, 345, 2345, 12345]					
					

The following method searches the specified list for the specified object using the binary search algorithm. The list MUST be sorted into ascending order according to the natural ordering of its elements (as by the 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.

Returns index of the search key, if it is contained in the list; otherwise, (-(insertion_point) - 1). The insertion_point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list are less than the specified key. NOTE, that this guarantees that the return value will be >= 0 if and only if the key is found:

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)

					

This code sample demonstrates sort(...) and binarySearch(...) methods:

/** Non-Comparable class */
public class WeirdString { 
	private String str;
	
	WeirdString(String str ){
		this.str = str;
	}
}					
					

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class CollClient {
	
	public static void main(String ... sss) {
		List myList = new LinkedList();
		String s1 = new String("2345");
		String s2 = new String("12345");		
		String s3 = new String("45");
		String s4 = new String("345");
		WeirdString s5 = new WeirdString("345");
		
		myList.add(s1);
		myList.add(s2);
		myList.add(s3);
		myList.add(s4);
		// myList.add(s5); // WRONG ! See *)
		
		System.out.println("Original list : " + myList); 
		// Result may be invalid if collection unsorted in *ascending* order!!!
		// *) May throw ClassCastException if the list contains 
		//    elements that are not *mutually* comparable !!!
		System.out.println("45 : " + Collections.binarySearch(myList, "45"));
		System.out.println("99 : " + Collections.binarySearch(myList, "99"));
		// *) May throw ClassCastException if the list contains 
		//    elements that are not *mutually* comparable !!!
		Collections.sort(myList); // sort in ascending order 
		System.out.println("Sorted list (ascending order): " + myList);
		System.out.println("45 : " + Collections.binarySearch(myList, "45"));
		System.out.println("99 : " + Collections.binarySearch(myList, "99"));
	}	
}
					

Original list : [2345, 12345, 45, 345]
45 : 2
99 : -5
Sorted list (ascending order): [12345, 2345, 345, 45]
45 : 3
99 : -5					
					

The following method searches the specified list for the specified object using the binary search algorithm. The list MUST be sorted into ascending order according to the specified comparator (as by the 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.

c - the comparator by which the list is ordered. A null value indicates that the elements' natural ordering should be used.

The method returns index of the search key, if it is contained in the list; otherwise, (-(insertion_point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list are less than the specified key. NOTE, this guarantees that the return value will be >= 0 if and only if the key is found.

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

					

The following code sample shows how to reverse the list of objects:

/** Non-Comparable class */
public class WeirdString { 
	private String str;
	
	WeirdString(String str ){
		this.str = str;
	}
}					
					

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class ReverseListClient {
	
	public static void main(String ... sss) {
		List myList = new LinkedList();
		String s1 = new String("2345");
		String s2 = new String("12345");		
		String s3 = new String("45");
		String s4 = new String("345");
		WeirdString s5 = new WeirdString("345"); 
		
		myList.add(s1);
		myList.add(s2);
		myList.add(s3);
		myList.add(s4);
		myList.add(s5); // OK, no need to be mutually comparable
		
		System.out.println("Original list : " + myList);
		Collections.reverse(myList); // OK
		System.out.println("Reversed list : " + myList);
	}	
}					
					

Original list : [2345, 12345, 45, 345, WeirdString@1f6a7b9]
Reversed list : [WeirdString@1f6a7b9, 345, 45, 12345, 2345]