Utilities

The collections framework would not be complete without its Arrays and Collections utility classes. Each class supplies various utility (static) methods that implement useful algorithms in the contexts of arrays and collections.

Following is a sampling of the Arrays class's array-oriented utility methods:

■ static <T> List<T> asList(T... array) returns a fixed-size list backed by the specified array. (Changes to the returned list "write through" to the array.) For example, List<String> birds = Arrays.asList("Robin", "Oriole", "Bluejay"); converts the three-element array of Strings (recall that a variable sequence of arguments is implemented as an array) to a List whose reference is assigned to birds.

■ static int binarySearch(int[] array, int key) searches array for entry key using the binary search algorithm (explained following this list). The array must be sorted before calling this method; otherwise, the results are undefined. This method returns the index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1) is returned. The insertion point is the point at which key would be inserted into the array (the index of the first element greater than key, or array.length if all elements in the array are less than key) and guarantees that the return value will be greater than or equal to 0 if and only if key is found. For example, Arrays.binarySearch(new String[] {"Robin", "Oriole", "Bluejay"}, "Oriole") returns 1, "Oriole"'s index.

■ static void fill(char[] array, char character) stores character in each element of the specified character array. For example, Arrays.fill(screen[i], ' '); fills the ith row of a 2D screen array with spaces.

■ static void sort(long[] array) sorts the elements in the long integer array into ascending numerical order; for example, long lArray = new long[] { 20000L, 89L, 66L, 33L}; Arrays.sort(lArray);.

■ static <T> void sort(T[] array, Comparator<? super T> comparator) sorts the elements in array using comparator to order them. For example, when given Comparator<String> cmp = new Comparator<String>() { public int compare(String el, String e2) { return e2.compareTo(el); } }; String[] innerPlanets = { "Mercury", "Venus", "Earth", "Mars" };, Arrays.sort(innerPlanets, cmp); uses cmp to help in sorting innerPlanets into descending order of its elements: Venus, Mercury, Mars, Earth is the result.

There are two common algorithms for searching an array for a specific element. Linear search searches the array element by element from index 0 to the index of the searched for element or the end of the array. On average, half of the elements must be searched; larger arrays take longer to search. However, the arrays do not need to be sorted.

In contrast, binary search searches ordered array a's n items for element e in a much faster amount of time. It works by recursively performing the following steps:

3. If low index > high index, then Print "Unable to find " e. End.

4. Set middle index to (low index+high index)/2.

5. If e > a[middle index], then set low index to middle index+1. Go to 3.

6. If e < a[middle index], then set high index to middle index-1. Go to 3.

7. Print "Found " e "at index " middle index.

The algorithm is similar to optimally looking for a name in a phone book. Start by opening the book to the exact middle. If the name is not on that page, proceed to open the book to the exact middle of the first half or the second half, depending on in which half the name occurs. Repeat until you find the name (or not).

Applying a linear search to 4,000,000,000 elements results in approximately 2,000,000,000 comparisons (on average), which takes time. In contrast, applying a binary search to 4,000,000,000 elements results in a maximum of 32 comparisons. This is why Arrays contains binarySearch() methods and not also linearSearch() methods.

Following is a sampling of the Collections class's collection-oriented utility methods:

■ static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> collection) returns the minimum element of collection collection according to the natural ordering of its elements. For example,

System.out.println(Collections.min(Arrays.asList(l0, 3, 18, 25))); outputs 3. All of collection's elements must implement the Comparable interface. Furthermore, all elements must be mutually comparable. This method throws NoSuchElementException when collection is empty.

■ static void reverse(List<?> list) reverses the order of list's elements. For example, List<String> birds = Arrays.asList("Robin", "Oriole", "Bluejay"); Collections.reverse(birds); System.out.println(birds); results in [Bluejay, Oriole, Robin] as the output.

■ static <T> List<T> singletonList(T o) returns an immutable list containing only object o. For example, list.removeAll(Collections.singletonList(null)); removes all null elements from list.

■ static <T> Set<T> synchronizedSet(Set<T> set) returns a synchronized (thread-safe) set backed by the specified set; for example, Set<String> ss = Collections.synchronizedSet(new HashSet<String>());. In order to guarantee serial access, it is critical that all access to the backing set is accomplished through the returned set.

■ static <K,V> Map<K,V> unmodifiableMap(Map<? extends K,? extends V> map) returns an unmodifiable view of the specified map; for example, Map<String, Integer> msi = Collections.synchronizedMap(new HashMap<String, Integer>());. Query operations on the returned map "read through" to the specified map, and attempts to modify the returned map, whether direct or via its collection views, result in an UnsupportedOperationException.

NOTE: For performance reasons, collections implementations are unsynchronized— unsynchronized collections have better performance than synchronized collections. To use a collection in a multithreaded context, however, you need to obtain a synchronized version of that collection. You obtain that version by calling a method such as synchronizedSet().

Was this article helpful?

0 0

Post a comment