Containers

Overview

Containers

Algorithms

Function Objects

Iterators

All Java programmers need a library of reusable data structures. The Java Developer's Kit (JDK) only contains three data structures - a Vector, a Stack, and a Hashtable - which is hardly sufficient for serious software development. In addition, the JDK does not include algorithms for sorting, filtering, and other common tasks.

In response to this situation, a collaboration was initiated between the ObjectSpace Components Group and the ObjectSpace Research Group to create the Generic Collection Library for Java™ (JGL, pronounced "Juggle"). In order to accelerate the spread of Java as a powerful general purpose programming language, ObjectSpace has decided to make JGL absolutely free for commercial use! This guarantees that all Java programmers will have instant access to the most sophisticated containers and algorithms on the market. Here is a list of reasons why all Java programmers should use JGL as one of their Java libraries:

Comprehensive Features

JGL includes 11 highly optimized data structures including sequences, maps, sets, queues, and a stack. Both ordered and hashing versions of set and maps are available.
JGL containers support Serialization, a new (with the JDK 1.1 release) lightweight object persistence layer built into the Java language. The iterators for all JGL Sequences are also serializable.
JGL contains over 40 reusable algorithms such as sorting, union, intersection, and many more.
JGL is multi-thread safe. JGL containers protect their methods with the synchronized keyword so that they work correctly in the presence of multiple threads.

Easy to Use

With complete HTML API documentation and a comprehensive HTML user guide packed with over 100 examples, JGL is very easy to learn and use.
With thousands of users already, ObjectSpace has been able to gather rapid feedback to fine-tune the usability of JGL.
Although a small and efficient library is critical, ObjectSpace has paid close attention to meeting usability requirements without sacrificing the performance.

Performance

JGL has been continually optimized for performance. In almost every case it either meets or beats any equivalent functionality available today.
Don't just take our word for it! ObjectSpace ships a suite of performance benchmarks with JGL. These benchmarks compare JGL performance with the JDK data structures.
JGL is architected to be lean and mean, making it ideal for Internet distribution.

Compatibility

JGL embraces and extends the JDK. It is compatible with the Exception, Enumeration, Vector, and Dictionary classes.
All JGL algorithms operate not only on JGL containers, but also on Java arrays of objects, Java arrays of primitives, and any JDK Vector.
As long as you adhere to standard Java language conventions, you don't have to add any code to your classes in order to store them in a JGL container.

This user guide describes the use of JGL using a mix of text and example programs. The rest of this chapter provides an overview of the main features of JGL - containers, algorithms, function objects and iterators. Subsequent chapters describe each JGL topic in detail.

Containers

This section contains some examples of JGL containers. See the Containers chapter for more details.

JGL includes 11 highly optimized data structures that satisfy most programmers' needs. Their performance either meets or beats any other commercially available Java container library, and have been engineered for performance and ease of use. In addition, all JGL containers work correctly in multithreaded situations.

The following example uses a JGL HashMap to associate a chemical symbol with its full name. Note that the entire container can be printed easily using the println() function.

Example Overview1.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;

public class Overview1
  {
  public static void main( String[] args )
    {
    HashMap chemicals = new HashMap();
    chemicals.put( "Ca", "Calcium" );
    chemicals.put( "Au", "Gold" );
    chemicals.put( "He", "Helium" );
    System.out.println( "chemicals = " + chemicals );
    System.out.println( "Au means " + chemicals.get( "Au" ) );
    }
  }

Output


chemicals = HashMap( Pair( Au, Gold ), Pair( He, Helium ), Pair( Ca, Calcium ) )
Au means Gold

The next example illustrates some set operations using the HashSet class. Note how simple it is to obtain the union and intersection of two sets.

Example Overview2.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;

public class Overview2
  {
  public static void main( String[] args )
    {
    HashSet set1 = new HashSet();
    set1.add( "red" );
    set1.add( "blue" );
    set1.add( "green" );

    HashSet set2 = new HashSet();
    set2.add( "yellow" );
    set2.add( "blue" );

    HashSet set3 = set1.union( set2 );
    HashSet set4 = set1.intersection( set2 );

    System.out.println( "set1 = " + set1 );
    System.out.println( "set2 = " + set2 );
    System.out.println( "union of set1 and set2 = " + set3 );
    System.out.println( "intersection of set1 and set2 = " + set4 );
    }
  }

Output


set1 = HashSet( blue, green, red )
set2 = HashSet( blue, yellow )
union of set1 and set2 = HashSet( blue, green, red, yellow )
intersection of set1 and set2 = HashSet( blue )

One of JGL's strengths is its seamless compatibility with the existing JDK utility classes. For example, you can use a standard JDK Enumeration object to iterate through every element of any JGL container. The following example uses an Enumeration to enumerate the contents of an Array (growable array) and a DList (doubly-linked list).

Example Overview3.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
import java.util.Enumeration; // JDK enumeration class.

public class Overview3
  {
  public static void main( String[] args )
    {
    Array array = new Array(); // Growable array.
    array.add( "nemesis" );
    array.add( "dig" );
    array.add( "myst" );

    Enumeration iterator = array.elements();
    while ( iterator.hasMoreElements() )
      System.out.println( iterator.nextElement() );
    System.out.println();

    DList list = new DList(); // Doubly-linked list.
    list.add( "agatha" );
    list.add( "beauty" );
    list.add( "truth" );

    iterator = list.elements();
    while ( iterator.hasMoreElements() )
      System.out.println( iterator.nextElement() );
    }
  }

Output


nemesis
dig
myst

agatha
beauty
truth

One of the exciting new features of the 1.1 version of the JDK is Object Serialization. Beginning with the 2.0 release of JGL, this feature is implemented in all containers. This means you can stream a container and all its contents out over a socket or into a persistent file with ease.

Example Serial1.java


// Copyright(c) 1997 ObjectSpace, Inc.

import COM.objectspace.jgl.*;
import java.io.*;
import java.util.*;

public class Serial1
  {
  static public void write()
    {
    try
      {
      // create a map of acronyms
      HashMap map = new HashMap();
      map.add( "FAQ", "Frequently Asked Questions" );
      map.add( "OMG", "Object Management Group" );
      map.add( "ORB", "Object Request Broker" );

      // save map to a file
      ObjectOutput s =  new ObjectOutputStream( new FileOutputStream( "Serial1.bin" ) );
      s.writeObject( map );
      }
    catch ( IOException e )
      {
      System.out.println( "caught: " + e );
      }
    }

  static public void read()
    {
    try
      {
      // read map from file
      ObjectInputStream s = new ObjectInputStream( new FileInputStream( "Serial1.bin" ) );
      HashMap map = (HashMap)s.readObject();
      System.out.println( "ORB means " + map.get( "ORB" ) );
      System.out.println( "FAQ means " + map.get( "FAQ" ) );
      }
    catch ( IOException e1 )
      {
      System.out.println( "caught: " + e1 );
      }
    catch ( ClassNotFoundException e2 )
      {
      System.out.println( "caught: " + e2 );
      }
    }

  public static void main( String args[] )
    {
    write();
    read();
    }
  }

Output


ORB means Object Request Broker
FAQ means Frequently Asked Questions

For the sequential containers in JGL (Deque, SList, DList, Array, and the array adapters) iterators may be serialized as well as the containers themselves.

Example Serial2.java


// Copyright(c) 1997 ObjectSpace, Inc.

import COM.objectspace.jgl.*;
import java.io.*;
import java.util.*;

public class Serial2
  {
  static public void write()
    {
    try
      {
      // create a list of names
      DList names = new DList();
      names.add( "Peter Parker" );
      names.add( "Frank Castle" );
      names.add( "Logan" );
      names.add( "Steve Rogers" );

      // save names to a file
      ObjectOutput s =  new ObjectOutputStream( new FileOutputStream( "Serial2.bin" ) );
      s.writeObject( names );

      // search for some particular entries
      ForwardIterator wolverine = names.find( "Logan" );
      ForwardIterator hulk = names.find( "Bruce Banner" );

      // write the iterators to the file as well
      s.writeObject( wolverine );
      s.writeObject( hulk );
      }
    catch ( IOException e )
      {
      System.out.println( "caught: " + e );
      }
    }

  static public void read()
    {
    try
      {
      // read sequence and iterator from file
      ObjectInputStream s = new ObjectInputStream( new FileInputStream( "Serial2.bin" ) );
      DList names = (DList)s.readObject();
      ForwardIterator wolverine = (ForwardIterator)s.readObject();
      ForwardIterator hulk = (ForwardIterator)s.readObject();

      // check the iterators
      if ( wolverine.equals( names.end() ) )
        System.out.println( "Don't know who Wolverine is" );
      else
        System.out.println( "Wolverine is also known as " + wolverine.get() );
      if ( hulk.equals( names.end() ) )
        System.out.println( "Don't know who the Hulk is" );
      else
        System.out.println( "Hulk is also known as " + hulk.get() );
      }
    catch ( IOException e1 )
      {
      System.out.println( "caught: " + e1 );
      }
    catch ( ClassNotFoundException e2 )
      {
      System.out.println( "caught: " + e2 );
      }
    }

  public static void main( String args[] )
    {
    write();
    read();
    }
  }

Output


Wolverine is also known as Logan
Don't know who the Hulk is

Algorithms

This section contains some examples of the power of JGL algorithms. See the Algorithms chapter for more details.

One of the main strengths of JGL is its complement of 40+ reusable algorithms that can perform tasks ranging from a simple filtering operation to a complex quicksort. Instead of embedding algorithms into a containers, JGL algorithms are encapsulated within their own class and can operate upon a wide variety of data structures, including JGL containers, JDK containers, and native Java arrays. All algorithms that are closely related are encapsulated as class methods of a single class. For example, all of the sorting algorithms are methods in Sorting.

To demonstrate the power and flexibility of this approach, the next three sections apply the single JGL reusable sorting algorithm to three different kinds of data structures.

Example Overview4.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;

public class Overview4
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( new Integer( 3 ) );
    array.add( new Integer( -1 ) );
    array.add( new Integer( 2 ) );
    System.out.println( "Unsorted Array = " + array );
    Sorting.sort( array );
    System.out.println( "Sorted = " + array );
    }
  }

Output


Unsorted Array = Array( 3, -1, 2 )
Sorted = Array( -1, 2, 3 )

The second example in this series uses the same sorting algorithm to sort a JDK Vector. JGL supplies simple "wrapper" classes to make a JDK Vector look like a JGL container so that the algorithms can work directly upon them.

Example Overview5.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
import java.util.Vector;

public class Overview5
  {
  public static void main( String[] args )
    {
    Vector vector = new Vector(); // JDK Vector.
    vector.addElement( new Integer( 3 ) );
    vector.addElement( new Integer( -1 ) );
    vector.addElement( new Integer( 2 ) );
    System.out.println( "Unsorted java.util.Vector = " + vector );
    // A VectorArray makes a JDK vector look like a JGL container.
    VectorArray vectorArray = new VectorArray( vector );
    Sorting.sort( vectorArray );
    System.out.println( "Sorted = " + vector );
    }
  }

Output


Unsorted java.util.Vector = [3, -1, 2]
Sorted = [-1, 2, 3]

The third and final example uses the same sorting algorithm to sort a native Java array of ints. In a similar manner to the last example, JGL supplies simple "wrapper" classes to make native Java arrays look like a JGL container.

Example Overview6.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;

public class Overview6
  {
  public static void main( String[] args )
    {
    int ints[] = { 3, -1, 2 };
    IntArray intArray = new IntArray( ints );
    System.out.println( "Unsorted native int array = " + intArray );
    Sorting.sort( intArray );
    System.out.print( "Sorted native array = " );
    for ( int i = 0; i < ints.length; i++ )
      System.out.print( ints[ i ] + " " );
    System.out.println();
    }
  }

Output


Unsorted native int array = int[]( 3, -1, 2 )
Sorted native array = -1 2 3

JGL includes many different kinds of algorithm. This last example uses the random shuffling algorithm to shuffle the contents of a Deque (double-ended queue).

Example Overview7.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;

public class Overview7
  {
  public static void main( String[] args )
    {
    Deque deque = new Deque();
    deque.add( "your" );
    deque.add( "mission" );
    deque.add( "jim" );
    System.out.println( "Original deque = " + deque );
    Shuffling.randomShuffle( deque );
    System.out.println( "Shuffled deque = " + deque );
    }
  }

Output


Original deque = Deque( your, mission, jim )
Shuffled deque = Deque( mission, jim, your )

Function Objects

This section contains a few examples of JGL function objects. See the Function Objects chapter for more details.

Many algorithms can accept an optional function object to modify the way that they work. A function object is an object that encapsulates a single function and can execute it on one or more arguments. JGL contains over 30+ reusable function objects.

The default sorting algorithm orders elements in ascending order based on their hash code. The following example uses a GreaterNumber function object to make the sorting algorithm order elements in descending order.

Example Overview8.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;

public class Overview8
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( new Integer( 3 ) );
    array.add( new Integer( -1 ) );
    array.add( new Integer( 2 ) );
    System.out.println( "Unsorted Array = " + array );
    BinaryPredicate predicate = new GreaterNumber();
    Sorting.sort( array, predicate ); // Sort in descending order.
    System.out.println( "Sorted = " + array );
    }
  }

Output


Unsorted Array = Array( 3, -1, 2 )
Sorted = Array( 3, 2, -1 )

Another couple of algorithms that can accept a function object are countIf() and removeCopyIf(). countIf() counts the elements in a container that satisfy a given condition, and removeCopyIf() copies elements that don't satisfy a condition from one container to another. Both of these algorithms are illustrated by the following example.

Example Overview9.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;

public class Overview9
  {
  public static void main( String[] args )
    {
    Array array1 = new Array();
    array1.add( new Integer( 3 ) );
    array1.add( new Integer( -1 ) );
    array1.add( new Integer( 2 ) );
    UnaryPredicate predicate = new PositiveNumber();
    int n = Counting.countIf( array1, predicate );
    System.out.println( "# of positive numbers in " + array1 + " = " + n );
    Array array2 = new Array();
    Removing.removeCopyIf( array1, array2, predicate );
    System.out.println( "Array without positive numbers = " + array2 );
    }
  }

Output


# of positive numbers in Array( 3, -1, 2 ) = 2
Array without positive numbers = Array( -1 )

Iterators

This section contains a brief overview of JGL iterators. See the Iterators chapter for more details.

In addition to supporting the JDK Enumeration type, JGL includes several more powerful classes of iterator. For example, a ReverseIterator allows you to iterate backwards over a container. JGL also includes an iterator for iterating through an I/O stream. The following example uses a reverse iterator to enumerate the contents of an Array in reverse order.

Example Overview10.java


// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;

public class Overview10
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "jolly" );
    array.add( "good" );
    array.add( "show" );

    // Create a reverse iterator positioned at the end of the array.
    ReverseIterator iterator = new ReverseIterator( array.end() );
    while ( iterator.hasMoreElements() )
      System.out.println( iterator.nextElement() );
    }
  }

Output


show
good
jolly

Contents

Preface

Containers