Algorithms in collections

The polymorphic algorithms described in this section are pieces of reusable functionality provided by the JDK. All of them come from the Collectionsclass. All take the form of static methods whose first argument is the collection on which the operation is to be performed. The great majority of the algorithms provided by the Java platform operate on Listobjects, but a couple of them (min and max) operate on arbitrary Collectionobjects. The algorithms are described below.

Sorting

The sort algorithm reorders a List so that its elements are ascending order according to some ordering relation. Two forms of the operation are provided. The simple form just takes a List and sorts it according to its elements' natural ordering. If you're unfamiliar with the concept of natural ordering, now would be a good time to read the Object Ordering lesson. The sort operation uses a slightly optimized merge sort algorithm. If you don't know what this means but you do care, see any basic textbook on algorithms. The important things to know about this algorithm are that it is:

• Fast: This algorithm is guaranteed to run in n log(n) time, and runs substantially faster on nearly sorted lists. Empirical studies showed it to be as fast as a highly optimized quicksort. Quicksort is generally regarded to be faster than merge sort, but isn't stable, and doesn't guarantee n log(n) performance.
• Stable: That is to say, it doesn't reorder equal elements. This is important if you sort the same list repeatedly on different attributes. If a user of a mail program sorts his in-box by mailing date, and then sorts it by sender, the user naturally expects that the now-contiguous list of messages from a given sender will (still) be sorted by mailing date. This is only guaranteed if the second sort was stable.

Here's a trivial little program that prints out its arguments in lexicographic (alphabetical) order.

import java.util.*;

public class Sort {
public static void main(String args[]) {
List l = Arrays.asList(args);
Collections.sort(l);
System.out.println(l);
}
}

Let's run the program:

% java Sort i walk the line

[i, line, the, walk]

The program was included only to show you that I have nothing up my sleeve: The algorithms really are as easy to use as they appear to be. I won't insult your intelligence by including any more silly examples. The second form of sort takes a Comparatorin addition to a List and sorts the elements with the Comparator. Remember the permutation group example at the end of the Map lesson? It printed out the permutation groups in no particular order. Suppose you wanted to print them out in reverse order of size, largest permutation group first. The following example below shows you how to achieve this with the help of the second form of the sort method.
Recall that the permutation groups are stored as values in a Map, in the form of List objects. The revised printing code iterates through the Map's values-view, putting every List that passes the minimum-size test into a List of Lists. Then, the code sorts this List using a Comparator that expects List objects, and implements reverse-size ordering. Finally, the code iterates through the now-sorted List, printing its elements (the permutation groups). This code replaces the printing code at the end of Perm's main method:

// Make a List of all permutation groups above size threshold
List winners = new ArrayList();
for (Iterator i = m.values().iterator(); i.hasNext(); ) {
List l = (List) i.next();
if (l.size() >= minGroupSize)
winners.add(l);
}

// Sort permutation groups according to size
Collections.sort(winners, new Comparator() {
public int compare(Object o1, Object o2) {
return ((List)o2).size() - ((List)o1).size();
}
});

// Print permutation groups
for (Iterator i=winners.iterator(); i.hasNext(); ) {
List l = (List) i.next();
System.out.println(l.size() + ": " + l);
}

Running this program on the same dictionary in the Map lesson, with the same minimum permutation group size (eight) produces the following output:

% java Perm dictionary.txt 8

12: [apers, apres, asper, pares, parse, pears, prase, presa, rapes,
reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels, salter, slater,
staler, stelar, talers]
10: [least, setal, slate, stale, steal, stela, taels, tales, teals,
tesla]
9: [estrin, inerts, insert, inters, niters, nitres, sinter, triens,
trines]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape, secpar,
spacer]
9: [anestri, antsier, nastier, ratines, retains, retinas, retsina,
stainer, stearin]
9: [palest, palets, pastel, petals, plates, pleats, septal, staple,
tepals]
8: [carets, cartes, caster, caters, crates, reacts, recast, traces]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares, sparse, spears]
8: [earings, erasing, gainers, reagins, regains, reginas, searing,
seringa]
8: [enters, nester, renest, rentes, resent, tenser, ternes, treens]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]

Shuffling

The shuffle algorithm does the opposite of what sort does: it destroys any trace of order that may have been present in a List. That is to say, it reorders the List, based on input from a source of randomness, such that all possible permutations occur with equal likelihood (assuming a fair source of randomness). This algorithm is useful in implementing games of chance. For example, it could be used to shuffle a List of Card objects representing a deck. Also, it's useful for generating test cases. There are two forms of this operation. The first just takes a List and uses a default source of randomness. The second requires the caller to provide a Randomobject to use as a source of randomness. The actual code for this algorithm is used as an example in the List lesson.

Routine Data Manipulation

The Collections class provides three algorithms for doing routine data manipulation on List objects. All of these algorithms are pretty straightforward:

• reverse: Reverses the order of the elements in a List.
• fill: Overwrites every element in a List with the specified value. This operation is useful for re-initializing a List.
• copy: Takes two arguments, a destination List and a source List, and copies the elements of the source into the destination, overwriting its contents. The destination List must be at least as long as the source. If it is longer, the remaining elements in the destination List are unaffected.

Searching

The binary search algorithm searches for a specified element in a sorted List using the binary search algorithm. There are two forms of this algorithm. The first takes a List and an element to search for (the "search key"). This form assumes that the List is sorted into ascending order according to the natural ordering of its elements. The second form of the call takes a Comparator in addition to the List and the search key, and assumes that the List is sorted into ascending order according to the specified Comparator. The sort algorithm (described above) can be used to sort the List prior to calling binarySearch. The return value is the same for both forms: if the List contains the search key, its index is returned. If not, the return value is (-(insertion point) - 1), where the insertion point is defined as the the point at which the value would be inserted into the List: the index of the first element greater than the value, or list.size() if all elements in the List are less than the specified value. This admittedly ugly formula was chosen to guarantee that the return value will be >= 0 if and only if the search key is found. It's basically a hack to combine a boolean ("found") and an integer ("index") into a single int return value.
The following idiom, usable with both forms of the binarySearch operation, looks for the specified search key, and inserts it at the appropriate position if it's not already present:

int pos = Collections.binarySearch(l, key);
if (pos < 0)
l.add(-pos-1, key);

Finding Extreme Values

The min and max algorithms return, respectively, the minimum and maximum element contained in a specified Collection. Both of these operations come in two forms. The simple form takes only a Collection, and returns the minimum (or maximum) element according to the elements' natural ordering. The second form takes a Comparator in addition to the Collection and returns the minimum (or maximum) element according to the specified Comparator. These are the only algorithms provided by the Java platform that work on arbitrary Collection objects, as opposed to List objects. Like the fill algorithm above, these algorithms are quite straightforward to implement. They are included in the Java platform solely as a convenience to programmers.

Creating class instance using Constructors that Have Arguments

To create an object with a constructor that has arguments, you invoke the newInstance method upon a Constructor  object, not a Class object. This technique involves several steps:

1. Create a Class object for the object you want to create.
2. Create a Constructor object by invoking getConstructor upon the Class object. The getConstructor method has one parameter: an array of Class objects that correspond to the constructor's parameters.
3. Create the object by invoking newInstance upon the Constructor object. The newInstance method has one parameter: an Object array whose elements are the argument values being passed to the constructor.

The sample program that follows creates a Rectangle with the constructor that accepts two integers as parameters. Invoking newInstance upon this constructor is analagous to this statement:

Rectangle rectangle = new Rectangle(12, 34);

This constructor's arguments are primitive types, but the argument values passed to newInstance must be objects. Therefore, each of the primitive int types is wrapped in an Integer object. The sample program hardcodes the argument passed to the getConstructor method. In a real-life application such as a debugger, you would probably let the user select the constructor. To verify the user's selection, you could use the methods described in Discovering Class Constructors.
The source code for the sample program is:

import java.lang.reflect.*;
import java.awt.*;

class SampleInstance {

public static void main(String[] args) {

Rectangle rectangle;
Class rectangleDefinition;
Class[] intArgsClass = new Class[] {int.class, int.class};
Integer height = new Integer(12);
Integer width = new Integer(34);
Object[] intArgs = new Object[] {height, width};
Constructor intArgsConstructor;

try {
rectangleDefinition = Class.forName("java.awt.Rectangle");
intArgsConstructor = 
rectangleDefinition.getConstructor(intArgsClass);
rectangle = 
(Rectangle) createObject(intArgsConstructor, intArgs);
} catch (ClassNotFoundException e) {
System.out.println(e);
} catch (NoSuchMethodException e) {
System.out.println(e);
}
}

public static Object createObject(Constructor constructor, 
Object[] arguments) {

System.out.println ("Constructor: " + constructor.toString());
Object object = null;

try {
object = constructor.newInstance(arguments);
System.out.println ("Object: " + object.toString());
return object;
} catch (InstantiationException e) {
System.out.println(e);
} catch (IllegalAccessException e) {
System.out.println(e);
} catch (IllegalArgumentException e) {
System.out.println(e);
} catch (InvocationTargetException e) {
System.out.println(e);
}
return object;
}
}

The sample program prints a description of the constructor and the object that it creates:

Constructor: public java.awt.Rectangle(int,int)
Object: java.awt.Rectangle[x=0,y=0,width=12,height=34]

Creating class instance using No-Argument Constructors using reflection in java

If you need to create an object with the no-argument constructor, you can invoke the newInstance method upon a Class object. The newInstance method throws a NoSuchMethodException if the class does not have a no-argument constructor. For more information on working with Constructor objects, see Discovering Class Constructors.
The following sample program creates an instance of the Rectangle class using the no-argument constructor by calling the newInstance method:

import java.lang.reflect.*;
import java.awt.*;

class SampleNoArg {

public static void main(String[] args) {
Rectangle r = (Rectangle) createObject("java.awt.Rectangle");
System.out.println(r.toString());
}

static Object createObject(String className) {
Object object = null;
try {
Class classDefinition = Class.forName(className);
object = classDefinition.newInstance();
} catch (InstantiationException e) {
System.out.println(e);
} catch (IllegalAccessException e) {
System.out.println(e);
} catch (ClassNotFoundException e) {
System.out.println(e);
}
return object;
}
}

The output of the preceding program is:

java.awt.Rectangle[x=0,y=0,width=0,height=0]

Threads in java

What Is a Thread?

A thread--sometimes called an execution context or a lightweight process--is a single sequential flow of control within a program. You use threads to isolate tasks. When you run one of these sorting applets, it creates a thread that performs the sort operation. Each thread is a sequential flow of control within the same program (the browser). Each sort operation runs independently from the others, but at the same time.

Customizing a Thread's run Method

First, you need to get a thread to do something by providing the run method for a thread. This section shows you two different ways to do this.

The Life Cycle of a Thread

Once you know how to get a thread to do something, you need to understand the life cycle of a Thread

Understanding Thread Priority

A thread's priority affects when it runs in relation to other threads. This section talks about how this affects your programs.

Synchronizing Threads

The first sample programs in this lesson use either one thread or multiple threads that run asynchronously. However, it is often useful to use multiple threads that share data and therefore must synchronize their activities. In this section you will learn how to synchronize threads and how to avoid problems such as starvation and deadlock.

Grouping Threads

This section shows you how to group threads and what you can do with a group of threads.

Summary

When you've completed this lesson on threads, you will have toured the intricacies of Java threads including the life cycle of a Java thread (as represented by its state), scheduling, thread groups, and synchronization. The Java development environment supports multithreaded programs through the language, the libraries, and the runtime system. This summary page highlights the features in the Java development environment that support threads and gives you links to further documentation about those features.

Summary of threads

 This lesson has provided a great deal of information about using threads in the Java development environment. Threads are supported by various components of the Java development environment, and it can be hard to find the features that you need. This section summarizes where in the Java environment you can find various classes, methods, and language features that participate in the Java threads story.

Package Support of Threads

java.lang.Thread

In the Java development enviroment, threads are objects that derive from java.lang's Thread class. The Thread class defines and implements Java threads. You can subclass the Thread class to provide your own thread implementations or you can use the Runnable interface.

java.lang.Runnable

The Java language library also defines the Runnable interface, which allows any class to provide the body (the run method) for a thread.

java.lang.Object

The root class, Object, defines three methods you can use to synchronize methods around a condition variable: wait, notify, and notifyAll.

java.lang.ThreadGroup

All threads belong to a thread group, which typically contains related threads. The ThreadGroup class in the java.lang package implements groups of threads.

java.lang.ThreadDeath

A thread is normally killed by throwing a ThreadDeath object at it. Rarely, a thread might need to catch ThreadDeath to clean up before it dies.

Language Support of Threads

The Java language has two keywords related to the synchronization of threads: volatile (which is not implemented in JDK 1.0) and synchronized. Both of these language features help ensure the integrity of data that is shared between two concurrently running threads. Multithreaded Programs discusses thread synchronization issues.

Runtime Support of Threads

The Java runtime system contains the scheduler, which is responsible for running all the existing threads. The Java scheduler uses a fixed priority scheduling algorithm which boils down to this simple rule of thumb:

---

Rule of thumb: At any given time, the highest priority thread is running. However, this is not guaranteed. The thread scheduler may choose to run a lower priority thread to avoid starvation. For this reason, use priority only to affect scheduling policy for efficiency purposes. Do not rely on thread priority for algorithm correctness.

---

Other Thread Information

Threads in Applets

When you write applets that use threads, you may have to make special provisions, such as ensuring that your applet is well-behaved. Also, some browsers impose security restrictions for applets based on which thread group a thread is in.

Grouping Threads

Every Java thread is a member of a thread group. Thread groups provide a mechanism for collecting multiple threads into a single object and manipulating those threads all at once, rather than individually. For example, you can start or suspend all the threads within a group with a single method call. Java thread groups are implemented by the ThreadGroup class in the java.lang package.
The runtime system puts a thread into a thread group during thread construction. When you create a thread, you can either allow the runtime system to put the new thread in some reasonable default group or you can explicitly set the new thread's group. The thread is a permanent member of whatever thread group it joins upon its creation--you cannot move a thread to a new group after the thread has been created.

The Default Thread Group

If you create a new Thread without specifying its group in the constructor, the runtime system automatically places the new thread in the same group as the thread that created it (known as the current thread group and the current thread, respectively). So, if you leave the thread group unspecified when you create your thread, what group contains your thread? When a Java application first starts up, the Java runtime system creates a ThreadGroup named main. Unless specified otherwise, all new threads that you create become members of the main thread group.

---

Note: If you create a thread within an applet, the new thread's group may be something other than main, depending on the browser or viewer that the applet is running in. Refer to Threads in Applets for information about thread groups in applets.

---

Many Java programmers ignore thread groups altogether and allow the runtime system to handle all of the details regarding thread groups. However, if your program creates a lot of threads that should be manipulated as a group, or if you are implementing a custom security manager, you will likely want more control over thread groups. Continue reading for more details!

Creating a Thread Explicitly in a Group

As mentioned previously, a thread is a permanent member of whatever thread group it joins when its created--you cannot move a thread to a new group after the thread has been created. Thus, if you wish to put your new thread in a thread group other than the default, you must specify the thread group explicitly when you create the thread. The Thread class has three constructors that let you set a new thread's group:

public Thread(ThreadGroup group, Runnable target)
public Thread(ThreadGroup group, String name)
public Thread(ThreadGroup group, Runnable target, String name)

Each of these constructors creates a new thread, initializes it based on the Runnable and String parameters, and makes the new thread a member of the specified group. For example, the following code sample creates a thread group (myThreadGroup) and then creates a thread (myThread) in that group.

ThreadGroup myThreadGroup = new ThreadGroup("My Group of Threads");
Thread myThread = new Thread(myThreadGroup, "a thread for my group");

The ThreadGroup passed into a Thread constructor does not necessarily have to be a group that you create--it can be a group created by the Java runtime system, or a group created by the application in which your applet is running.

Getting a Thread's Group

To find out what group a thread is in, you can call its getThreadGroup method:

theGroup = myThread.getThreadGroup();

The ThreadGroup Class

Once you've obtained a thread's ThreadGroup, you can query the group for information, such as what other threads are in the group. You can also modify the threads in that group, such as suspending, resuming, or stopping them, with a single method invocation.

Avoiding Starvation and Deadlock

The dining philosophers are often used to illustrate various problems that can occur when many synchronized threads are competing for limited resources.
The story goes like this: Five philosophers are sitting at a round table. In front of each philosopher is a bowl of rice. Between each pair of philosophers is one chopstick. Before an individual philosopher can take a bite of rice he must have two chopsticks--one taken from the left, and one taken from the right. The philosophers must find some way to share chopsticks such that they all get to eat.
The following applet does a rough animation using an image of Duke for the dining philosophers. This particular algorithm works as follows: Duke always reaches for the chopstick on his right first. If the chopstick is there, Duke takes it and raises his right hand. Next, Duke tries for the left chopstick. If the chopstick is available, Duke picks it up and raises his other hand. Now that Duke has both chopsticks, he takes a bite of rice and says "Mmm!" He then puts both chopsticks down, allowing either of his two neighbors to get the chopsticks. Duke then starts all over again by trying for the right chopstick. Between each attempt to grab a chopstick, each Duke pauses for a random period of time.

The slider controls the amount of time that each philosopher will wait before attempting to pick up a chopstick. When the slider is set to 0, the philosophers don't wait--they just grab--and the applet ends up in deadlock: all the philosophers are frozen with their right hand in the air. Why? Because each philosopher immediately has one chopstick and is waiting on a condition that cannot be satisfied--they are all waiting for the left chopstick, which is held by the philosopher to their left.
When you move the slider so that the waiting period is longer, the applet may proceed for a while without deadlocking. However, deadlock is always possible with this particular implementation of the dining philosophers problem because it is possible for all five philosophers to be holding their right chopsticks. Rather than rely on luck to prevent deadlock, you must either prevent it or detect it.
For most Java programmers, the best choice is to prevent deadlock rather than to try and detect it. Deadlock detection is complicated and beyond the scope of this tutorial. The simplest approach to to preventing deadlock is to impose ordering on the condition variables. In the dining philosopher applet, there is no ordering imposed on the condition variables because the philosophers and the chopsticks are arranged in a circle. All chopsticks are equal.
However, we can change the rules in the applet by numbering the chopsticks 1 through 5 and insisting that the philosophers pick up the chopstick with the lower number first. The philosopher who is sitting between chopsticks 1 and 2 and the philosopher who is sitting between chopsticks 1 and 5 must now reach for the same chopstick first (chopstick 1) rather than picking up the one on the right. Whoever gets chopstick 1 first is now free to take another one. Whoever doesn't get chopstick 1 must now wait for the first philosopher to release it. Deadlock is not possible.