Containers

As their name implies, containers are objects that contain other objects. You are familiar with the most common of all containers, the array. A positive feature of arrays is that they are efficient, both in how they are allocated and in how they are accessed. A negative feature is that arrays are not convenient: they are fixed in size and they are not indexed, so it is difficult to find specific elements within an array.

The WFC util package provides a number of other container types. No single container type solves all of the problems of the array—there is no perfect container. However, each container class provides some unique advantage. In addition, the utility package provides a number of utilities that aid in sorting the contents of a container.

NOTE
As WFC grows, other forms of containers will likely be added to those currently present.

Arrays

Mechanisms for creating an array and accessing its members are built into the Java language. There is no keyword for sorting an array, however. Fortunately, the ArraySorter class is provided to sort arrays of objects.

Since we will need something to sort, let's begin by defining a Student class.

Creating the Student class

The following Student class is the most rudimentary class I could devise to define a student. This class is stored in the file Student.java.

/**
 * A generic Student class.
 */
public class Student
{
 String name = null;
 int ssNumber = 0;
 /**
 * Create a real student.
 * * @param name - the name of the student to create
 * @param ssNumber - the Social Security number
 */
 Student(String name, int ssNumber)
 {
 this.name = name;
 this.ssNumber = ssNumber;
 }
 /**
 * Retrieve the Social Security number.
 */
 int getSSNumber()
 {
 return ssNumber;
 }
 /**
 * Convert Student into an informative string.
 */
 public String toString()
 {
 String s = name + "(" + ssNumber + ")";
 return s;
 }
}


The Student class must of course have a name member to record the student's name. Since students at our school are registered by Social Security number, the Student class needs an ssNumber data member as well. The Student constructor initializes these two data fields, while the getSSNumber() and toString() methods allow access to the values stored in the data fields. A host of other fields and associated methods might be required by a real student class, but these will do for the examples in this chapter.

Sorting an array of objects

Sorting arrays of information is a common problem—so common, in fact, that com.ms.wfc.util includes an ArraySorter class. This class can sort an array of any type of objects as long as you can provide a comparison function. You do this by creating a class that implements the IComparer interface. This interface defines only a single method, int compare(Object o1, Object o2).This method returns a value of 1 if o1 is greater than o2, -1 if o2 is greater than o1, and 0 if the two values are equal. Exactly what is meant by the phrase "o1 is greater than o2" is up to you to define.

The following SortStudent program creates an array of Student objects and then sorts it using the ArraySorter class.

import com.ms.wfc.io.*;
import com.ms.wfc.util.*;
/**
 * Sort a Student class using the ArraySorter class.
 */
public class SortStudent
{
 /**
 * The main entry point for the app. *
 * @param args Array of parameters passed to the app
 * via the command line.
 */
 public static void main (String[] args)
 {
 // create an array of students
 Student[] array = new Student[]
 {
 new Student("Shepherd, James", 234567890),
 new Student("Smith, Harold", 123456789),
 new Student("Davis, Stephen", 345678901)
 };
 // output the unsorted array
 output("Unsorted array", array);
 // sort the array
 ArraySorter.sort(array, new StudentComparer());
 // now output again
 output("Sorted array", array);
 }
 /**
 * Output an array.toString() to standard output.
 * * @param msg - message to tack onto output
 * @param array - array to output
 */
 static void output(String msg, Object[] array)
 {
 Text.out.writeLine(msg);
 for (int i = 0; i < array.length; i++)
 {
 Text.out.writeLine(array[i].toString());
 }
 Text.out.writeLine();
 }
}
/**
 * A class to provide the Student comparer method.
 */
class StudentComparer implements IComparer
{
 /**
 * Compares two students by comparing their ssNumbers.
 * * @param o1 - first student
 * @param o2 - second student
 * @return 1, 0, or -1 depending on relationship of o1 to o2
 */
 public int compare(Object o1, Object o2)
 {
 Student s1 = (Student)o1;
 Student s2 = (Student)o2;
 if (s1.ssNumber < s2.ssNumber)
 {
 return -1;
 }
 if (s1.ssNumber > s2.ssNumber)
 {
 return 1;
 }
 return 0;
 }
}


As always, control begins with the method main(). The program begins by creating an array of three Student objects.

NOTE
The definition of the array variable demonstrates a syntax unique to Java. The first line declares an array of class Student[]. The calls to new within the braces initializes the array to contain three Student objects.
NOTE
I used the Add Class command on the Project menu to add the Student.java file to the project. This ensures that there is always an up-to-date copy of Student.class in the same directory as the remainder of the project.

Once it is created, the array is output to standard output using the local static output() method. The array of Student objects is then sorted by invoking the sole method of ArraySorter, the public static method sort(). The first argument is the array of Student objects. The second argument is an object that implements the IComparer interface.

The class StudentComparer implements the IComparer interface by providing a compare(Object, Object) function capable of sorting students. The compare() function begins by casting the o1 and o2 objects into the Student objects s1 and s2. This cast is justified because we know that this class is used only on arrays of Student objects. Once the two objects s1 and s2 have been created, compare() returns a -1, 0, or 1 based on a comparison of the objects' Social Security number values.

The output() method is then called again to output the sorted array and demonstrate that ArraySorter worked as planned.

The output of the SortStudent program is shown in Figure 3-6.

Java Click to view at full size.

Screenshot-6. The ArraySorter class makes it easy to sort arrays of objects, like the Student objects shown here.

NOTE
C++ programmers will recognize this definition of an interface with a single method as Java's replacement for function pointers. The Java approach is both more type safe and safer. You'll see Java defining an interface with a single method again in the discussion of event handlers in Part II.

Sorting an array of strings

In the StudentSort example, I chose to sort the students by Social Security number. The most common approach to sorting, however, is to put objects in alphabetical order based on their string representation. Accordingly, the WFC util package includes the StringSorter class. This class serves a number of functions related to sorting strings.

You can use the StringSorter class to sort arrays of String objects as follows:

// create an array String[] stringArray = {"array1",
 "array3",
 "array2"
 };
// now sort the array StringSorter.sort(stringArray);


The StringSorter class can also be used to sort other types of objects. For objects other than String objects, StringSorter.sort() invokes the toString() method to convert the objects to String objects and then sorts the objects based on the returned strings.

For example, the following code segment would sort the students in alphabetical order based on their names followed by Social Security number, since this is the value returned by Student.toString().

// declare an array of Students Student[] array = new Student[]
 {
 new Student("Shepherd, James", 234567890),
 new Student("Smith, Harold", 123456789),
 new Student("Davis, Stephen", 345678901)
 };
// now sort them based on value returned by toString()
StringSorter.sort(array);


The StringSorter.sort() method provides other syntaxes, some of which allow for the inclusion of sort options. The options are defined as final static fields within the StringSorter class itself. Since these fields are defined as bit fields, multiple options can be combined with an OR ( | ) operator to increase the amount of control the app program has over the sort.

For example, the following call is identical to the previous example except it sorts the Student objects based on the name values without regard to case or any special symbols that might appear in their names.

StringSorter.sort(array, StringSorter.IGNORECASE |
 StringSorter.IGNORESYMBOLS);


The StringSorter class can handle a large percentage of array sorting problems.

Lists

A list is similar to an array except that a list isn't a fixed size. In many apps, the program doesn't know beforehand how many objects it needs to contain.

There are two flavors of lists. The generic list is contained in java.util.Vector. The version specific to WFC is com.ms.wfc.util.List. Although the methods of these classes are not identical, they share most of the same features.

A common use for a list might be in a program that reads student names from a file. Such a program doesn't know how many student names are in the file until it has gone through the process of reading them. With a list, the program can read each student name and add it to the list. With an array, the program would have to make two passes through the file: an initial pass to count the number of student names so that the program would know how big to allocate the array, followed by a second pass to actually read the names and assign them to the array.

NOTE
For really large data files, your app should use a database rather than a list.

Sorting lists of students

The following example reads student information from the keyboard and then sorts it. This version uses a list because it doesn't know how many students the user is likely to enter.

import com.ms.wfc.io.*;
import com.ms.wfc.util.*;
/**
 * Add a series of Student objects to a list and then output
 * the list.
 */
public class StudentList
{
 /**
 * The main entry point for the app. */
 public static void main (String[] args)
 {
 // create an empty list
 List list = new List();
 // enter Student objects until user enters null
 for (;;)
 {
 Text.out.writeLine(
 "Enter student name (blank line to terminate)");
 String name = Text.in.readLine();
 if (name.equals(""))
 {
 break;
 }
 Text.out.writeLine("Enter Social Security number:");
 int ssNumber = Integer.parseInt(Text.in.readLine());
 Student s = new Student(name, ssNumber);
 list.addItem(s);
 }
 // output the list
 output("Unsorted list", list);
 // now sort the list
 list.sort(new StudentComparer());
 // output the sorted list
 output("Sorted list", list);
 }
 /**
 * Output the contents of a list to standard output.
 * * @param label - message to tack onto output
 * @param list - list to output
 */
 static void output(String label, List list)
 {
 Text.out.writeLine();
 Text.out.writeLine(label);
 int length = list.getSize();
 for (int i = 0; i < length; i++)
 {
 Object o = list.getItem(i);
 Text.out.writeLine(o.toString());
 }
 }
}
/**
 * A class to provide the Student comparer method.
 */
class StudentComparer implements IComparer
{
 // same as in StudentSort example…
}


The program begins by creating an empty list. It then enters a loop that prompts the user for the student's name. If the user enters an empty line, control exits from the loop. Once the program has read the name, it then prompts for and reads the student's Social Security number, which it converts into an integer. The name and Social Security number are used to create a Student object which is appended to the list by calling list.addItem(). (Note that the program is not tolerant of illegal input.) Once the list has been created, main() continues as in the previous example by displaying the unsorted list, sorting the list, and then displaying the sorted list.

The List.sort() method is similar to the ArraySorter.sort() method in that it relies on a user-defined IComparer object to sort whatever type of object is contained in the list. The StudentComparer class used in this example is identical to the version used in the SortStudent example.

One other difference between lists and arrays is in the way that the elements of the list are accessed in the output() method. List.getItem(i) returns the ith member in the list, whereas an array would be accessed directly, as in Array[i].

Screenshot-7 shows the output from a trial run of the StudentList example.

Java Click to view at full size.

Screenshot-7. An example run of StudentList showing the sorted output following the unsorted output.

Using StringSorter to sort lists

In the StudentList example, I could have sorted the list by simply changing the StudentComparer class as follows:

/**
 * The following StudentComparer sorts the students by
 * name while ignoring the case of the letters used.
 */
class StudentComparer implements IComparer
{
 public int compare(Object o1, Object o2)
 {
 return StringSorter.compare(o1.toString(),
 o2.toString(),
 StringSorter.IGNORECASE);
 }
}


This version of StudentComparer uses the StringSorter.compare() routine to perform a comparison of the string returned by Student.toString() while ignoring the case.

Enumerating through a list

In the two student program examples, you might have noticed how it was necessary to modify the output() function to match the particular type of container we were using. Wouldn't it be nice if there was a way to access all types of containers irrespective of their internal details? In fact, there is.

The IEnumerator interface provides universal access to all types of containers. This interface provides three methods for navigating the contents of a container, as shown in the following table.

Method Description
hasMoreItems() Returns true as long as the enumerator isn't pointing to the last member.
nextItem() Returns a reference to the object pointed at by the enumerator, and moves the enumerator to the next object in the container.
reset() Resets the enumerator to the beginning of the container.

The following version of output() works for arrays, lists, and other types of containers:

static void output(String label, IEnumerator enum)
{
 Text.out.writeLine();
 Text.out.writeLine(label);
 while(enum.hasMoreItems())
 {
 Object o = enum.nextItem();
 Text.out.writeLine(o.toString());
 }
}


Rather than accept a reference to the container itself, this version of output() accepts an enumerator that has been initialized to point to the container. After outputting the preamble, output() iterates through the container using nextItem() until hasMoreItems() returns false.

To invoke this version of output(), the array-based SortStudent class would use the following:

// create an enumerator for the array output("Sorted list", new ArrayEnumerator(array));


The list-based StudentList would make the following call:

// pass a List enumerator to output output("Sorted list", list.getItemEnumerator());


The actual class of enumerator being passed to output() is different in the two cases, but since both implement the IEnumerator interface, output() doesn't care.

NOTE
Arrays are handled differently than other types of containers, because arrays are an intrinsic part of Java and can't be subclassed. All other container types work like List by providing a getEnumerator()-type method.

Hash Tables

Neither the array nor the list are convenient for looking up items. In the case of the unsorted student list, if the user wanted to look up a student by Social Security number, the program would be forced to perform a linear search until the Social Security number is found.

The HashTable class is particularly convenient and computationally quick for looking up items. The following example program demonstrates the use of the HashTable class to store Student objects and then recall them rapidly:

import com.ms.wfc.io.*;
import com.ms.wfc.util.*;
/**
 * Add a series of Student objects to a hashed dictionary.
 */
public class StudentHash
{
 /**
 * The main entry point for the app. */
 public static void main (String[] args)
 {
 // create a default-sized hash table
 HashTable table = new HashTable();
 // enter Student objects until user enters null
 for (;;)
 {
 // get the Student object
 Text.out.writeLine(
 "Enter student name (blank line to terminate)");
 String name = Text.in.readLine();
 if (name.equals(""))
 {
 break;
 }
 Text.out.writeLine("Enter Social Security number:");
 int ssNumber = Integer.parseInt(Text.in.readLine());
 Student student = new Student(name, ssNumber);
 // add it to the table using the Social
 // Security number as the key
 Integer key = new Integer(student.getSSNumber());
 table.setValue(key, student);
 }
 // now look up entries in the hash table by Social
 // Security number
 for(;;)
 {
 // get the Social Security number
 Text.out.writeLine("Enter S. S. number to look up entry:");
 String keyString = Text.in.readLine();
 if (keyString.equals(""))
 {
 break;
 }
 // look up the student by number entered
 Integer key = new Integer(keyString);
 Student s = (Student)table.getValue(key);
 // output the student value returned
 if (s == null)
 {
 Text.out.writeLine("Entry not found");
 }
 else
 {
 Text.out.writeLine(s.toString());
 }
 }
 }
}


This version reads entries similarly to its list-based predecessor. To add the student entries to the container, this version uses the HastTable.setValue(Object key, Object value) method. The key argument will be used to look up the value argument later. Since we want to look up students by Social Security number, the program uses the int returned from getSSNumber() as the key; however, since the key must be an object, the program must first convert the int into an Integer.

Once the student information has been stored in the hash table, the program uses HastTable.getValue(key) to look up the student. The Social Security number read from the user entry is converted into an Integer object, which is passed to getValue(). If getValue() returns a null, no student was found with that Social Security number.

Comments