Sequences

Containers

Container Interfaces

Storing Objects and Primitives

Adding, Printing, Clearing, and Sizing

Enumerating

Copying, Comparing, Assigning, and Cloning

Swapping

Storing Primitives

Storing User-Defined Objects

Error Handling

Adapters

JGL includes 11 highly optimized data structures for general purpose programming. It also includes 10 array adapters that allow you to apply JGL algorithms to native arrays and JDK Vectors. The following diagram shows all of the container classes in JGL and how they relate to the container classes that are already part of the JDK. Interfaces are indicated using italics and classes are indicated using courier. Classes that are already part of JDK are indicated by (JDK).

Note how tightly JDK integration has been achieved. For example, the JGL HashMap and OrderedMap extend the existing JDK Dictionary class. The only time there is overlap between JGL and JDK is when the JGL container has significantly more functionality or higher performance than its JDK equivalent.

The rest of this chapter contains information pertinent to every JGL container. The Sequences, Maps, Sets, Queues and Stacks, and Array Adapters chapters describe the methods and interfaces specific to each category of container.

1. There are ten array adapters, one for each primitive data type, one for an array of Objects, and one for a JDK Vector.

Container Interfaces

Every JGL container implements the Container interface, which defines the methods that are common to all JGL containers. In addition, most JGL containers implement a more specialized interface related to their category. For example, Array, Deque, DList, and SList all implement the Sequence interface.

The Container interface defines the following methods:

add - adds an element to the container
clear - removes every element from the container
clone - returns a shallow copy of the container
elements - returns an Enumeration positioned at the start of the container
empty - returns true if the container contains no elements
equals - returns true if the contents match those of another container of the same type
size/maxSize - returns the current/maximum number of elements in the container
start/finish - returns an iterator positioned at the start/finish of the container
toString - returns a string that describes the container

The rest of this chapter describes all of these methods except for start() and finish(), which are described in the Iterators chapter.

Storing Objects and Primitives

JGL follows the same philosophy as the JDK when it comes to the way that objects and primitives are stored:

A container can store instances of any Java class. For example, you can store a String, a Date, and an Integer in the same container. When you retrieve an object, you must cast the object back to the required type before applying a type-specific method. Java's dynamic cast-checking mechanism ensures that any attempt to cast an object to the wrong type causes a runtime exception.

A container cannot directly store a primitive. Primitives can only be stored in containers using a special technique described in the Storing Primitives section of this chapter.

Note that unlike C++ template containers, you cannot create a JDK or JGL container that can only hold instances of a specific class of object.

Adding, Printing, Clearing, and Sizing

Every JGL container allows you to add an object, print the container, clear the container, and size the container. These behaviors are illustrated by the following example.

Example Container1.java

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

public class Container1
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "triangle" );
    array.add( "square" );
    array.add( "pentagon" );
    array.add( "hexagon" );
    System.out.println( "array = " + array );
    System.out.println( "array.size() = " + array.size() );
    System.out.println( "array.empty() = " + array.isEmpty() );
    array.clear();
    System.out.println( "after array is cleared..." );
    System.out.println( "array.size() = " + array.size() );
    System.out.println( "array.empty() = " + array.isEmpty() );
    }
  }

Output

array = Array( triangle, square, pentagon, hexagon )
array.size() = 4
array.isEmpty() = false
after array is cleared…
array.size() = 0
array.isEmpty() = true

Enumerating

Every JDK container defines a method called elements() that returns a JDK Enumeration object positioned at its first element. Once this object is obtained, you may enumerate every element of the container by using the hasMoreElements() and nextElement() methods. For ease of use and backwards compatibility, every JGL container also defines an elements() method that returns an Enumeration. The following example uses an Enumeration object to enumerate every object in an Array.

Example Container2.java

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

public class Container2
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "triangle" );
    array.add( "square" );
    array.add( "pentagon" );
    array.add( "hexagon" );
    
    Enumeration iterator = array.elements();
    while( iterator.hasMoreElements() )
      System.out.println( iterator.nextElement() );
    }
  }

Output

triangle
square
pentagon
hexagon

Copying, Comparing, Assignment, and Cloning

There are two well-known ways to copy a container:

A shallow copy means that the original container and the copy share references to the same objects. This is the fastest kind of copy and is sufficient for most programming purposes.

A deep copy means that the original container and the copy do not share references to the same objects. Instead, every element of the original container is copied as it is added to the new container.

The JGL copy constructors always perform a shallow copy. In addition, you may replace the contents of a container with a shallow copy of another container by using the copy() method, or obtain a shallow clone of a container using the standard clone() method.

To compare two containers of the same type for equality, use the standard equals() method. JGL follows the standard Java convention and extends Container from Cloneable. The following example illustrates all of these methods.

Example Container3.java

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

public class Container3
  {
  public static void main( String[] args )
    {
    Array array1 = new Array();
    array1.add( "triangle" );
    array1.add( "square" );
    array1.add( "pentagon" );
    System.out.println( "array1 = " + array1 );

    // Illustrate copy construction.
    Array array2 = new Array( array1 );
    System.out.println( "array2 = " + array2 );
    System.out.println( "array1.equals( array2 ) = "+ array1.equals( array2 ) );

    // Illustrate assignment using copy().
    Array array3 = new Array();
    array3.add( "heptagon" );
    array3.add( "octagon" );
    System.out.println( "before copy, array3 = " + array3 );
    array3.copy( array1 );
    System.out.println( "after copy, array3 = " + array3 );

    // Illustrate cloning.
    Array array4 = (Array) array1.clone();
    System.out.println( "array4 = " + array4 );
    }
  }

Output

array1 = Array( triangle, square, pentagon )
array2 = Array( triangle, square, pentagon )
array1.equals( array2 ) = true
before copy, array3 = Array( heptagon, octagon )
after copy, array3 = Array( triangle, square, pentagon )
array4 = Array( triangle, square, pentagon )

Swapping

Every JGL container allows you to efficiently exchange its contents with those of another container of the same type by using the swap() method. This is illustrated by the following example.

Example Container4.java

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

public class Container4
  {
  public static void main( String[] args )
    {
    Array array1 = new Array();
    array1.add( "ape" );
    array1.add( "bat" );
    array1.add( "cat" );

    Array array2 = new Array();
    array2.add( "red" );
    array2.add( "blue" );

    // Illustrate swapping.    
    System.out.println( "array1 = " + array1 + ", array2 = " + array2 );
    array1.swap( array2 );
    System.out.println( "array1 = " + array1 + ", array2 = " + array2 );
    }
  }

Output

array1 = Array( ape, bat, cat ), array2 = Array( red, blue )
array1 = Array( red, blue ), array2 = Array( ape, bat, cat )

Storing Primitives

The JGL containers can only contain objects. To store primitives, "wrap" them in their object equivalents defined in java.lang. Here is a table of primitives and their object equivalents:

Primitive Object Equivalent

boolean Boolean

char Character

byte Byte

short Short

int Integer

long Long

float Float

double Double

The following example shows how an Array can be used to store a variety of primitives.

ExampleContainer5.java

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

public class Container5
  {
  public static void main( String[] args )
    {
    Array Array = new Array();
    Array.add( new Integer( 2 ) );
    Array.add( new Boolean( false ) );
    Array.add( new Character( 'x' ) );
    Array.add( new Float( 3.14F ) );
    System.out.println( "Array = " + Array );
    }
  }

Output

Array = Array( 2, false, x, 3.14 )

Note that the JGL algorithms are smart enough to convert these "wrapper" objects to and from their primitive equivalents when necessary. See the "Algorithms" and "Iterators" chapters for examples.

Storing User-Defined Objects

There are three special methods that are invoked by JGL containers on the objects they contain:

boolean equals( Object object ) - return true if I am equal to the specified object. By default, JGL algorithms and containers use this function when comparing elements.

int hashCode() - return my hash code. HashMap and HashSet use this value to store and locate objects. In addition, OrderedMap and OrderedSet use this value by default to order their elements. Note that if two objects match using equals(), their hash codes must be identical.

String toString() - return a string that describes me. JGL uses this function when printing containers.

Each of these methods has a default implementation in java.lang.Object. If you wish to store instances of your classes into any JGL container, you should override these methods when necessary.

For example, here is a Company class that overrides each of these methods appropriately. Note that two companies are considered to match when their names are the same.

Company.java

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

public class Company
  {
  String myName;

  public Company( String name )
    {
    myName = name;
    }

  public String toString()
    {
    return "Company( " + myName + " )";
    }

  public int hashCode()
    {
    return myName.hashCode();
    }

  public boolean equals( Object object )
    {
    return object instanceof Company && 
           myName.equals(((Company) object).myName);
    }
  }

The following example stores instances of Company into a HashMap. Each instance of Company is placed into the HashMap's underlying hash structure using its hashCode() function.

Example Container6.java

// Copyright(c) 1996 ObjectSpace, Inc.
import jgl.*;
import Company;

public class Container6
  {
  public static void main( String[] args )
    {
    Company company1 = new Company( "ObjectSpace" );
    Company company2 = new Company( "Sun Microsystems" );

    HashMap headquarters = new HashMap();
    headquarters.put( company1, "Texas" );
    headquarters.put( company2, "California" );

    String location = (String) headquarters.get( company1 );
    System.out.println( "Headquarters of " + company1 + " = " + location );
    }
  }

Output

The headquarters of Company( ObjectSpace ) = Texas

Error Handling

A JGL error causes a Java exception to be thrown. Methods that can cause an exception are commented in the source code using the @exception tag and are documented in the online help. Whenever possible, JGL throws the standard JDK exceptions that are defined in java.lang. The only exception that is unique to JGL is InvalidOperationException.

Here is a hierarchy of the exceptions that JGL can throw, together with a brief description of when the exception is thrown. All of these exception classes are part of the JDK except for the bolded class.

Class                                  Description
Throwable                              the root of all throwable objects 
  Exception                            the root of all exceptions
    RuntimeException                   the root of all runtime exceptions
      InvalidOperationException        invalid operation attempted on a JGL container
      IllegalArgumentException         an illegal argument was supplied to a method
      IndexOutOfBoundsException        an illegal index was supplied to an operation
      NullPointerException             attempt to add a null key or value

Because all JGL exceptions inherit from RuntimeException, methods that can generate them do not have to explicitly declare them using throws.

The following example catches an IndexOutOfBoundsException.

Example Container7.java

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

public class Container7
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    array.add( "ape" );
    array.add( "cat" );
    try
      {
      Object object = array.at( 5 );
      }
    catch( IndexOutOfBoundsException exception )
      {
      System.out.println( "Caught " + exception );
      }
    }
  }

Output

Caught java.lang.IndexOutOfBoundsException: Attempt to access index 5 when valid range is 0..1

The next example catches an InvalidOperationException.

Example Container8.java

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

public class Container8
  {
  public static void main( String[] args )
    {
    Array array = new Array();
    try
      {
      Object object = array.front();
      }
    catch( InvalidOperationException exception )
      {
      System.out.println( "Caught " + exception );
      }
    }
  }

Output

Caught jgl.InvalidOperationException: Array is empty

The last example in this series catches an IllegalArgumentException.

Example Container9.java

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

public class Container9
  {
  public static void main( String[] args )
    {
    try
      {
      Array array = new Array( -2 );
      }
    catch( IllegalArgumentException exception )
      {
      System.out.println( "Caught " + exception );
      }
    }
  }

Output

Caught java.lang.IllegalArgumentException: Attempt to create an Array with a negative size

Array Adapters

Most of the JGL algorithms such as sort() and countIf() can operate directly on a JGL container. In order for the algorithms to also work with JDK Vectors and native Java arrays, JGL includes special array adapter classes that wrap them in a Container-compliant interface. The following example uses an IntArray adapter to allow sort() to operate on a native array of ints.

Example Container10.java

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

public class Container10
  {
  public static void main( String[] args )
    {
    int ints[] = { 3, -1, 2, 0, -6 };
    IntArray intArray = new IntArray( ints ); // Construct adapter class.
    System.out.println( "unsorted native int array = " + intArray );
    Sorting.sort( intArray ); // Sort native array.
    System.out.print( "sorted = " );
    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, 0, -6 )
sorted = -6 -1 0 2 3

For more information about array adapters, read the chapter called Array Adapters.

Contents Overview Sequences

Primitive	Object Equivalent
`boolean`	`Boolean`
`char`	`Character`
`byte`	`Byte`
`short`	`Short`
`int`	`Integer`
`long`	`Long`
`float`	`Float`
`double`	`Double`