Using threads with collections, Part 1

Threads add a new degree of complexity to otherwise straightforward design issues

1 2 Page 2
Page 2 of 2

The class is very straightforward; it has two basic constructors. The first creates an instance without a Comparator object. Using this constructor, the SynchroList behaves very much like a Vector, except that it stores its elements in a linked list rather than in an array. The class becomes more interesting with the second constructor. Using the second constructor, the class is initialized with an object that implements the Comparator interface. Using the Comparator object, the logic in the add method compares the object that is being added with the objects that are already on the list. This comparison is done with the line that reads if (cmp.lessThan(...)). That line of code checks each object until the Comparator's test returns true, then inserts the new object into the list just before the current Link. This algorithm results in a list that is sorted in ascending order. The delete method is only possible if you have a Comparator, because it is a requirement that you test for equality between the object passed and the objects in the list.

The last two methods, size and elements, mirror the methods of the same name in the Vector class. The size method is used by applications to get the total size of the list. This allows the application to open a file or perhaps allocate an array of the right size before iterating over all the elements in the list. The final method, elements, provides the Enumeration object that is used by the application to retrieve each object, in sorted order, from the list.

Tying it together

In order to put the list into practice, we must build an application or applet that uses it. For the basic list described here, I've written a simple example application that illustrates its use.

The application consists of two component classes -- the Comparator class and the application itself. The Comparator class is called IntCompare and is shown below.

    public class IntCompare implements Comparator {
    public boolean lessThan(Object a, Object b) {
        return ((Integer) a).intValue() < ((Integer) b).intValue();
    }
    public boolean greaterThan(Object a, Object b) {
        return ((Integer) a).intValue() > ((Integer) b).intValue();
    }
    public boolean equalTo(Object a, Object b) {
        return ((Integer) a).intValue() == ((Integer) b).intValue();
    }
    void typeCheck(Object a) {
        if (a instanceof Integer) return;
        throw new RuntimeException("Type violation!");
    }
}

As you can see in the code above, this comparator was built to compare two objects of type Integer. Now, take a look at the typeCheck method. The typeCheck method will throw an exception when the type of the object passed is not Integer. Further, if you go back and look at the add method of SynchroList, you will see that typeCheck is called before the object is inserted into the linked list. The check done in the add method means that the methods lessThan, greaterThan, and equalTo can cast the objects they are passed to Integer and not worry about Java throwing a class cast exception. Without this guarantee of type safety, the comparison methods in IntCompare would have to be written with checks like this:

   
    public boolean lessThan(Object a, Object b) {
        if (! (a instanceof Integer))
            return false;
        if (! (b instanceof Integer))
            return false;
        return ((Integer) a).intValue() < ((Integer) b).intValue();
    }

The example application is pretty trivial and is shown below.

     import java.util.Enumeration;
public class SynchroTest {
     static int data[] = {
            1, 0, 25, 20, 3, 45, 6, 2, 5, 17, 49, 24, 55, 12, 30, 31,
            32, 33, 34, 45, 46, 47, 10, 40 };
     public static void main(String args[]) {
         SynchroList sl = new SynchroList(new IntCompare());
         for (int i = 0; i < data.length; i++) {
             sl.add(new Integer(data[i]));
         }
         System.out.println("Total list size was "+sl.size()+" elements.");
         int lineNum = 1;
         for (Enumeration e = sl.elements(); e.hasMoreElements(); ) {
             Integer ii = (Integer)(e.nextElement());
             System.out.println("ELEMENT["+lineNum+"] - "+ii);
             lineNum++;
         }
     }
}

This application inserts a sequence of integers into a SynchroList object and then enumerates and prints the results to the console.

When considering a small number of elements, such as a few dozen values, this design would be an elegant, if simple, form for a collection class. However, as with the Vector class, our collection doesn't handle multiple threads very well. Further, when the collection gets to be very large, I would like to design it such that it could return only a piece of the collection instead of the whole thing.

Wrapping up

Now is a good place to pause and consider what we've covered. First, we looked at the issue of multiple threads and the collection classes that are available today in Java. Then we went through the design of a new collection class that provides some fundamental infrastructure on which we can build a much more powerful collection. Next month, we will start with the SynchroList collection and develop it in two ways. The first will be to increase the utility of the collection when its size gets quite large. The larger collection sizes, however, will increase the risk of multiple thread collisions because enumerating the collection will take so much longer. So, the next step will be to take our large-size collection and make it thread-aware. It's not easy to make it completely thread-safe, but we will be able to make it quite usable if we follow a few simple rules.

Chuck McManis currently is the director of system software at FreeGate Corp., a venture-funded start-up that is exploring opportunities in the Internet marketplace. Before joining FreeGate, Chuck was a member of the Java Group. He joined the Java Group just after the formation of FirstPerson Inc. and was a member of the portable OS group (the group responsible for the OS portion of Java). Later, when FirstPerson was dissolved, he stayed with the group through the development of the alpha and beta versions of the Java platform. He created the first "all Java" home page on the Internet when he did the programming for the Java version of the Sun home page in May 1995. He also developed a cryptographic library for Java and versions of the Java class loader that could screen classes based on digital signatures. Before joining FirstPerson, Chuck worked in the operating systems area of SunSoft, developing networking applications, where he did the initial design of NIS+.

Learn more about this topic

  • Generically Speaking -- a column on designing collections from December 1996 http://www.javaworld.com/jw-12-1996/jw-12-indepth.html
  • Java's new Collections Framework for 1.2 http://java.sun.com/products/jdk/1.2/docs/guide/collections/index.html
  • Concurrent Programming in Java by Doug Lea, published by Addison-Wesley ISBN 0-201-69581-2 -- An excellent source of information on issues surrounding the use of multiple threads in your Java applets and applications.
  • Design Patterns Elements of Reusable Object-Oriented Software by Gamma et al, published by Addison-Wesley, ISBN 0-201-63361-2 -- This book shows how valuable the separation of "what" and object does and "how" a particular class design does it.
  • "An in-depth look at Java's character type"
    Eight (bits) is not enough -- Java's character type adds another eight. http://www.javaworld.com/javaworld/jw-01-1998/jw-01-indepth.html
  • "A first look at Borland's JBuilder IDE" http://www.javaworld.com/jw-11-1997/jw-11-indepth.html
  • "A look at inner classes"
    Reduce class clutter in your Java designsUse inner classes. http://www.javaworld.com/javaworld/jw-10-1997/jw-10-indepth.html
  • "Take an in-depth look at the Java Reflection API"
    Learn about the new Java 1.1 tools for finding out information about classes. http://www.javaworld.com/javaworld/jw-09-1997/jw-09-indepth.html
  • "Take a look inside Java classes"
    Learn to deduce properties of a Java class from inside a Java program. http://www.javaworld.com/javaworld/jw-08-1997/jw-08-indepth.html
  • "Build an interpreter in Java -- Implement the execution engine"
    Here's how to take the interpreter classes and run with them. http://www.javaworld.com/javaworld/jw-07-1997/jw-07-indepth.html
  • "How to build an interpreter in Java, Part 2The structure"
    The trick to assembling the foundation classes for a simple interpreter. http://www.javaworld.com/javaworld/jw-06-1997/jw-06-indepth.html
  • "How to build an interpreter in Java, Part 1The BASICs"
    For complex applications requiring a scripting language, Java can be used to implement the interpreter, adding scripting abilities to any Java app. http://www.javaworld.com/javaworld/jw-05-1997/jw-05-indepth.html
  • "Lexical analysis, Part 2Build an application"
    How to use the StreamTokenizer object to implement an interactive calculator. http://www.javaworld.com/javaworld/jw-02-1997/jw-02-indepth.html
  • "Lexical analysis and JavaPart 1"
    Learn how to convert human-readable text into machine-readable data using the StringTokenizer and StreamTokenizer classes. http://www.javaworld.com/javaworld/jw-01-1997/jw-01-indepth.html
  • "Code reuse and object-oriented systems"
    Use a helper class to enforce dynamic behavior. http://www.javaworld.com/javaworld/jw-12-1996/jw-12-indepth.html
  • "Container support for objects in Java 1.0.2"
    Organizing objects is easy when you put them into containers. This article walks you through the design and implementation of a container. http://www.javaworld.com/javaworld/jw-11-1996/jw-11-indepth.html
  • "The basics of Java class loaders"
    The fundamentals of this key component of the Java architecture. http://www.javaworld.com/javaworld/jw-10-1996/jw-10-indepth.html
  • "Not using garbage collection"
    Minimize heap thrashing in your Java programs. http://www.javaworld.com/javaworld/jw-09-1996/jw-09-indepth.html
  • "Threads and applets and visual controls"
    This final part of the series explores reading multiple data channels. http://www.javaworld.com/javaworld/jw-07-1996/jw-07-mcmanis.html
  • "Using communication channels in applets, Part 3"
    Develop Visual Basic-style techniques to applet design -- and convert temperatures in the process. http://www.javaworld.com/javaworld/jw-06-1996/jw-06-mcmanis.html
  • "Synchronizing threads in Java, Part 2"
    Learn how to write a data channel class, and then create a simple example application that illustrates a real-world implementation of the class. http://www.javaworld.com/javaworld/jw-05-1996/jw-05-mcmanis.html
  • "Synchronizing threads in Java"
    Former Java team developer Chuck McManis walks you through a simple example illustrating how to synchronize threads to assure reliable and predictable applet behavior. http://www.javaworld.com/javaworld/jw-04-1996/jw-04-synch.html

1 2 Page 2
Page 2 of 2