COLLECTION UTILITIES
These tips were developed using Java(tm) 2 SDK, Standard Edition,
v 1.3.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Collection classes like ArrayList and HashMap are used heavily in
Java programming. Associated with these classes are what might be
called utility methods. These methods add functionality to the
collection classes. This tip looks at some of these utilities.
The first utility method is one that provides a synchronization
wrapper on top of an existing collection. A wrapper is an
alternate view of a collection. You can still access and modify
the original collection, but the wrapped collection provides some
other desirable property.
Here's a demonstration of using synchronization wrappers:
import java.util.*;
public class UtilDemo1 {
public static void main(String args[]) {
Object obj = new Object();
// create a list
List list = new ArrayList();
// put a wrapper on top of it
List synclist = Collections.synchronizedList(list);
// add some objects to the list
long start = System.currentTimeMillis();
for (int i = 1; i <= 1000000; i++) {
synclist.add(obj);
}
long elapsed = System.currentTimeMillis() - start;
System.out.println(elapsed);
}
}
By default, collection classes such as ArrayList are not
thread-safe (unlike the older Vector class). A thread-safe
implementation does more for you, but costs more in return. If
you have multiple threads sharing a single collection, then you
need to worry about synchronization, that is, you need to be
aware of potential problems and deal with them.
In the example above, the collection is wrapped, and so, method
calls such as add will be synchronized. The synchronization is done
by first obtaining a lock on the wrapper (synclist). If you really
want to thwart synchronization, you can still access the list
directly using "list" instead of "synclist". However, this is
probably not a good idea.
Another way of tackling the same problem of adding objects to
a list looks like this:
import java.util.*;
public class UtilDemo2 {
public static void main(String args[]) {
Object obj = new Object();
// create a list
List list = new ArrayList();
// add some objects to it
long start = System.currentTimeMillis();
synchronized (list) {
for (int i = 1; i <= 1000000; i++) {
list.add(obj);
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println(elapsed);
}
}
In this example, no synchronization wrapper is used, but the list
is locked while objects are added to it. This demo runs about 25%
faster than the previous one, but at the expense of keeping the
list locked throughout the update operation.
The Collection class also has methods that return unmodifiable
(as opposed to synchronized) wrappers. One of these methods is
Collections.unmodifiableList; you can use it to create a read-only
view of a list. The list can still be modified, but not through
the wrapper interface. This is especially useful if you want to
pass a list to some other function, but you want to prevent the
other function from modifying the list. To do this, you simply
use a lightweight wrapper to make the list read only.
Here's an example that uses Collections.unmodifiableList:
import java.util.*;
public class UtilDemo3 {
public static void main(String args[]) {
// create a list and add some items to it
List stringlist = new ArrayList();
stringlist.add("alpha");
stringlist.add("beta");
stringlist.add("gamma");
// create an unmodifiable view of the list
List rolist = Collections.unmodifiableList(stringlist);
// add to the original list (works OK)
stringlist.add("delta");
// add through the read-only view (gives an exception)
rolist.add("delta");
}
}
This example program creates a list and adds some items to it. It
then creates an unmodifiable view of the list. When you run the
program, you'll see that an additional item can be added to the
original list. However the program throws an exception when it
attempts to add an item to the read-only view.
Another kind of operation provided by the utility methods is
min/max. Here's an example using min:
import java.util.*;
public class UtilDemo4 {
public static void main(String args[]) {
// create a list and add some objects to it
List list = new ArrayList();
list.add("alpha");
list.add("Beta");
list.add("gamma");
list.add("Delta");
// compute the minimum element, case sensitive
String str = (String)Collections.min(list);
System.out.println(str);
// compute the minimum element, case insensitive
str = (String)Collections.min(list,
String.CASE_INSENSITIVE_ORDER);
System.out.println(str);
}
}
This program computes the minimum value of a set of strings, using
the natural ordering of strings (see java.lang.Comparable). Then
it computes the minimum value using an implementation of the
java.util.Comparator interface. In this example, a special
comparator String.CASE_INSENSITIVE_ORDER is used. A comparator
allows you to specify a particular ordering of elements. The output
of the program is:
Beta
alpha
You can use the shuffle utility method to randomly shuffle the
elements of a list. For example, this program reads a text file and
then displays its lines in random order:
import java.io.*;
import java.util.*;
public class UtilDemo5 {
public static void main(String args[]) throws IOException {
// check command line argument
if (args.length != 1) {
System.err.println("missing input file");
System.exit(1);
}
// open file
FileReader fr = new FileReader(args[0]);
BufferedReader br = new BufferedReader(fr);
// read lines from file
List list = new ArrayList();
String ln;
while ((ln = br.readLine()) != null) {
list.add(ln);
}
br.close();
// shuffle the lines
Collections.shuffle(list);
// print the result
Iterator it = list.iterator();
while (it.hasNext()) {
System.out.println((String)it.next());
}
}
}
For input like:
1
2
3
4
5
output might be:
3
2
1
5
4
A program like this one is useful in generating test data.
A final example shows how to do binary searching in a list:
import java.util.*;
public class UtilDemo6 {
public static void main(String args[]) {
// create list and add elements to it
List list = new ArrayList();
list.add("alpha");
list.add("Beta");
list.add("Delta");
list.add("gamma");
// do the search
int i = Collections.binarySearch(list, "chi",
String.CASE_INSENSITIVE_ORDER);
i = -(i + 1);
// display the result
System.out.println("insertion point = " + i);
}
}
The list is searched (case insensitive) for an occurrence of the
string "chi", which is not found. When a key is not found, the
return value from binarySearch is -(i + 1), where i is the
appropriate insertion point to maintain the list in proper order.
When run, the UtilDemo6 program prints:
insertion point = 2
In other words, "chi" should be inserted at location 2, just
before "Delta".
The collection utilities also contain methods for sorting lists,
reversing the order of lists, filling, and copying.
To learn more about collection utilities, see section 16.8
Wrapped Collections and the Collections Class in "The Java
Programming Language, Third Edition" by Arnold, Gosling, and
Holmes (http://java.sun.com/docs/books/javaprog/thirdedition/).
|
