Need a good set of abstract data structures? ObjectSpace's JGL packs a punch!

With the Java Generic Library, you get a valuable package of data structures, algorithms, and helper classes

During the past year, Java programmers have been frustrated -- and quite legitimately -- with a lack of punch when it comes to abstract data structures in the java.lang and java.util packages. Well, fret no more: ObjectSpace Inc., developer of object-oriented software, is distributing a free, large, and well-designed package of generic data structures, algorithms, and helper classes. Called the Java Generic Library (JGL), this Java package (import COM.objectspace.jgl.*) is Java's timely and hard-hitting answer to C++'s Standard Template Library (STL).

Unlike other commercial offerings, like Thought Inc.'s Nutmeg library (reviewed by Doug Garrett in the October 1996 issue of Dr.Dobb's Journal), the JGL is free to anyone and is meant to be used for any purpose -- in the same spirit as Sun's Java programming language and Java development kit (JDK). Java developers accustomed to the JDK way of developing (that is, in a non-visual way) will be right at home with the Java Generic Library's distribution approach: the archive contains an excellent and comprehensive HTML-based user guide and API reference manual, pre-compiled .class files (the library itself), 170+ examples on how to use the classes, and, as rich icing on the cake, the complete source code to the entire library!

JGL: An overview

The problem domain JGL focuses on can be expressed in Niklaus Wirth's immortal formula: algorithms + data structures. Or rather, in this object-oriented era: data structures + algorithms.

On the data structures side, JGL makes available a set of Abstract Data Types (ADTs) that are derived from an abstract class called Container -- actually defined as a Java interface. Containers are further sub-categorized into the following (as shown also in Figure 1):

  • Sequences -- comprising arrays, single/double linked lists, and Dequeues (double-ended queues)
  • Sets -- hashing and ordered
  • Maps -- hashing and ordered
  • Queue
  • Stack

All sequences (containers in which element ordering plays a role) and sets (containers in which element ordering is unimportant) "descend" from their respective interfaces -- that is, Sequence and Set -- which inherit from interface Container. (Do not confuse the AWT Container class with JGL's Container: The two classes are unrelated.)

On the algorithms side, object-oriented inheritance is much less useful, so JGL's algorithms are simply grouped loosely into unrelated classes with names generally ending in -ing. Here are some of the main algorithm classes:

  • Sorting
  • Finding
  • Filtering
  • Counting
  • Replacing
  • Reversing
  • Applying
  • Transforming
  • Copying

Both groups of classes, data structures, and algorithms, can be coupled together with the help of a host of helper classes: iterator and function classes.

Iterator classes will be familiar to most experienced object-oriented programmers: They are abstract pointers to elements of abstract data structures. The JGL provides iterator classes not only for each of its Container classes but also for every native Java array variety and for java.util's Vector class. JGL lets you use native Java arrays and class Vector as first-class JGL citizens, via mediating classes called array adapters.

Function classes let you encapsulate "functions" (method calls, condition functions) as objects that you can then apply "in bulk" to containers in myriad different ways. For example, if you had a "convert to uppercase" function, you could convert every string in any container to uppercase, irrespective of whether the container is a linked list, a native Java array, a hashtable, or a set, and so on.

Now that I've given you a bird's-eye view of the JGL, let's swoop down and analyze these class groups in more detail.

Generic containers

Figure 1 shows the

Container

hierarchy and how it partially meshes with the java.util hierarchy. Note all JGL containers inherit from a single parent interface; thus all containers share a common subset of methods.

Java Generic Library
Figure 1. The JGL Container Hierarchy

This common subset of methods that all containers share are enumerated in the definition for interface Container, shown in Listing 1.

// Copyright(c) 1996,1997 ObjectSpace, Inc.

// Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.

package COM.objectspace.jgl;

import java.util.Enumeration; import java.io.Serializable;

/* * Container is the interface that is implemented by all of the * Java Generic Library containers. * @version 2.0 * @author ObjectSpace, Inc. */

public interface Container extends Cloneable, Serializable { public Object add( Object object ); // Add an object to myself. public void clear(); // Remove all of my objects. public boolean isEmpty(); // Return true if I contain no objects. public Enumeration elements(); // Return an Enumeration of the components in this container public ForwardIterator start(); // Return an iterator positioned at my first item. public ForwardIterator finish(); // Return an iterator positioned immediately after my last item. public boolean equals( Object object ); // Return true if I'm equal to a specified object. public int size(); // Return the number of objects that I contain. public int maxSize(); // Return the maximum number of objects that I can contain. public Object clone(); // Return a shallow copy of myself. public String toString(); // Return a string that describes me. }

Listing 1. Container interface definition

At this abstraction level, the main methods of a Container are its add() method and the start() and finish() methods that return iterators. Further down the hierarchy, every concrete Container provides more specialized methods to actually retrieve objects from itself, in addition to more tailored object adding methods. As with the java.util containers, JGL containers can only contain objects, so if you need to store primitives, you may have to wrap them in their equivalent object forms (but check if an array adapter can't provide a simpler solution, indirectly wrapping the primitives at the higher level of an entire array instead).

Sets are very basic containers; their main methods are simply put() and get(). Sequences, on the other hand, give you pushFront()/popFront(), pushBack()/popBack(), front()/back(), at(), and put(), clearly reflecting their more flexible random access container nature.

Initially, JGL's Array class is probably the most approachable Container: It is the JGL equivalent of java.util.Vector. The exception, of course, that Array is a JGL Sequence (and hence also a Container) and can therefore easily be substituted by other Sequences, or Containers, if random access is not important.

ObjectSpace's JGL philosophy is not to compete with Sun's java.util package but to complement it, and JGL allows you to leave most of your Vector-based code as is. Nevertheless, you can use JGL to enhance it by providing an adapter class, VectorArray. This adapter wraps a Vector up in some JGL clothes, turning it into a Sequence, the far-reaching implications being that JGL algorithms can be applied to java.util.Vectors, as can JGL iterators. This simple fact alone should be reason enough to adopt JGL.

JGL has an even more powerful compatibility trick up its sleeve: Any native Java arrays can be adapted and turned into a JGL Sequence! To fit into the JGL scheme of things, you do not need to rewrite your code, which uses plain arrays: You just wrap some adapter classes around the arrays and let JGL loose on your existing code. Example 1 shows you how to use a JGL enumerator on the standard command-line arguments array that is passed to every Java application.

import jgl.ObjectArray; import java.util.Enumeration;

class Native {

public static void main (String[] args) {

ObjectArray cmdArgs; // an array adapter to adapt native obj arrays

cmdArgs = new ObjectArray(args); // wrap args array

// from now on, cmdArgs is a JGL-compatible array, so we can use // any of the Sequence/Container methods on it.

if ( ! cmdArgs.isEmpty() ) { Enumeration enum = cmdArgs.elements(); int i = 0; while ( enum.hasMoreElements() ) { String cmdLineArg = (String) enum.nextElement(); System.out.println( "Command line argument " + i + " = " + cmdLineArg); i++; } } } } // End of Class Native

Example 1: Turning the (native Strings) command-line arguments array into a JGL Container

Very much like Java's own java.lang wrapper classes (Boolean, Character, Float, and so on), JGL's adapter class nomenclature is perfectly regular (all classnames ending in -Array), so you do not need to look up the class you should use. An array of booleans simply requires a BooleanArray, an array of chars requires a CharArray, and so on.

If you are familiar with Java's java.util.Hashtable class, you will easily adopt JGL's Map classes. These take key-value pairs as their unit of storage, a key associating with a value as in a dictionary. You can use the generic add() method to add a key-value pair (that is, two objects) as a single object, courtesy of class Pair which simply glues two objects into a bigger object. Alternatively, you use put(Object key, Object value) to add entries as explicit pairs.

Of note is the ability of the map classes to handle one-to-one mappings, like java.util.Hashtable (HashMap and OrderedMap), and one-to-many mappings (HashMultiMap and OrderedMultiMap). For the *MultiMap classes that allow key duplicates, the list of matching values can not be returned via the usual single value-producing get(Object key). A more appropriate equalRange(key) method returns two iterators (that is, pointers) that together define a range of objects with identical keys.

While giving away as few implementation details as possible, the general online description for all these classes provides the time and space attributes for each ADT. A DList, for example (doubly linked list), comes with the following explanation: "Removing a single element is a constant time operation." These performance specs of course are vital to determine which of the JGL structures you should deploy. If you need fast adding of elements at an extremity, you should go for one of the Queue-type classes. If random access is additionally required, then Array is your best choice. If fast finding is critical, then you probably need a HashMap or HashSet, and so on.

Algorithm classEncapsulated algorithms
ApplyingforEach, inject
Comparingequal, lexicographicalCompare, median, mismatch
Copyingcopy, copyBackward
Countingcount, countIf
Fillingfill, fillN
Filteringreject, select, unique, uniqueCopy
FindingadjacentFind, detect, every, find, findIf, some
HashingorderedHash, unorderedHash
MinMaxmaxElement, minElement
SetOperations and OrderedSetOperationsincludes, setDifference, setIntersection, setSymmetricDifference, setUnion
PermutingnextPermutation, prevPermutation
Removingremove, removeIf, removeCopy, removeCopyIf
Replacingreplace, replaceIf, replaceCopy, replaceCopyIf
Reversingreverse, reverseCopy
Rotatingrotate, rotateCopy
ShufflingrandomShuffle
Sortingsort
SwappingiterSwap, swapRanges
Transformingcollect, transform

Table 1: Algorithm classes and their encapsulated algorithms provided by JGL

Algorithms

Complementing data structures are the algorithms that can optionally operate on them. JGL packs forty-plus different algorithms, as shown in Table 1 above, that can be applied to any of JGL's Containers. Herein lies JGL's phenomenal power and flexibility, as it means you can:

  • Find items in a deck
  • Swap items in singly linked list
  • Extract a subset of an array
  • Get the difference between a doubly linked list and a hashtable
  • Sort a stack frame
  • Rotate a queue, and so on, virtually ad infinitum

The combinations are almost endless. You may think they are far from infinite because the roughly 20 types of Containers, multiplied by roughly 40 algorithms, produces some 800 different combinations. In fact, this number ends up looking very small when you factor in the extra dimension of function objects that can customize most of the algorithms.

This distinctly non-object-oriented, orthogonal separation of algorithms from data structures is not done entirely consistently within JGL: For programmers' convenience, many Containers do encapsulate common algorithms applicable to them. The Set classes, for example, contain methods to calculate the union, difference, and intersection of two sets. But these set algorithms also are present in the SetOperations algorithms class -- meaning these set operations can be equally applied to any other two Containers! This hybrid approach proves that in the design of JGL, pragmatism was favored over philosophical purity.

Actual invocation of an algorithm is done via a static (class) method call. This means that you never instantiate one of the algorithm classes. See the examples later on in this article.

The Glue classes: functions and iterators

While you can use Containers purely on their own, or apply JGL algorithms to Containers without any other helper class lubricants, the inherent power of the two main groups of classes can only be fully realized when more classes are called upon -- the function and iterator classes.

Function classes

JGL's function class mechanism allows you to unleash the full potential of the JGL. Unfortunately, this is also JGL's most complex aspect.

Unary and binary functions

1 2 Page
Recommended
Join the discussion
Be the first to comment on this article. Our Commenting Policies
See more