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 two data structures - a Vector 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 Java Generic Library (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 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 ObjectSpace, Inc.
import 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 ObjectSpace, Inc.
import 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 ObjectSpace, Inc.
import 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

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 ObjectSpace, Inc.
import 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 ); // Sort the 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 ObjectSpace, Inc.
import jgl.*;
import java.util.Vector;

public class Overview5
  {
  public static void main( String[] args )
    {
    Vector vector = new 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 ); // Sort the JDK Vector.
    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 ObjectSpace, Inc.
import 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 ); // Sort the primitive Java array of ints.
    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

import 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( jim, your, mission )

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 GreaterInteger function object to make the sorting algorithm order elements in descending order.

Example Overview8.java

// Copyright(c) 1996 ObjectSpace, Inc.
import 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 GreaterInteger();
    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 ObjectSpace, Inc.
import 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 PositiveInteger();
    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 ObjectSpace, Inc.
import 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