JGL - The Generic Collection Library for Java

Containers

Maps

Sequences

Pushing, Popping, and Index-Based Access

Counting, Finding, Removing, and Replacing

Inserting

Ensuring Capacity

Constructing from a Native Java Array

Splicing

Miscellaneous

A sequence is a linear container that allows index-based access and automatically expands to accommodate new elements. JGL includes four different kinds of sequences:

An Array stores its elements internally in a single contiguous structure for very high performance random access. This storage approach allows elements to be added very efficiently to the end of the container, but much slower in other places. An Array is similar to a JDK Vector except that it is easier to apply JGL algorithms to an Array and it is possible to construct an Array from an existing native Java array.

A Deque is a double-ended queue that has almost the same interface as an Array but stores its elements internally in an array of arrays. This implementation difference results in random access that is slower than that of an Array but allows fast insertion at its beginning or end.

A DList stores its elements internally as a doubly linked list of nodes in which every node has a reference to a single element and a reference to its next and previous nodes. This approach yields very fast insertion at any point in the data structure but relatively slow random access as the DList must be traversed from its beginning to the target node.

An SList stores its elements internally as a singly linked list of nodes in which every node has a reference to a single element and a reference to the next node. This approach uses less storage space than a DList but only allows high performance insertion at its beginning or its end.

Each of these classes implements the Sequence interface, which in turn extends the Container interface. Here is a diagram that illustrates these relationships:

All classes that implement the Sequence interface support the following methods:

pushFront/pushBack - insert an item at the beginning/end
popFront/popBack - remove and return the item at the beginning/end
front/back - return the first/last item
at/put - return/replace the item at a specified index
remove - remove a particular value
replace - replace one value with another
count - count the number of matching elements
indexOf - return the index of a particular element
contains - return true if a particular element is present

Array, DList, and SList include additional functionality that is unique to their class. The rest of this chapter describes these classes and methods in detail.

Pushing, Popping, and Index-based Access

All sequences allow you to read/write an element at a particular index using at() and put(), respectively. The first element of a sequence has index 0. If an attempt is made to access an element at an illegal index, an IndexOutOfBoundsException is thrown. add() and pushBack() are synonymous. The following example demonstrates all of the functions for pushing, popping, and index-based access using an Array.

Example Sequences1.java

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

import com.objectspace.jgl.*;



public class Sequences1

  {

  public static void main( String[] args )

    {

    Array array = new Array();

    array.pushBack( "bat" ); // Add to end of array.

    array.add( "cat" ); // Synonym for pushBack().

    array.pushFront( "ape" ); // Insert at beginning of array.

    System.out.println( "array = " + array );

    System.out.println();



    System.out.println( "Demonstrate access" );

    System.out.println( "array.at( 0 ) = " + array.at( 0 ) );

    System.out.println( "array.front() = " + array.front() );

    System.out.println( "array.at( 2 ) = " + array.at( 2 ) );

    System.out.println( "array.back() = " + array.back() );



    System.out.println( "array.put( 1, \"fox\" )" );

    array.put( 1, "fox" );

    System.out.println( "array = " + array );



    array.popFront();

    System.out.println( "After popFront() = " + array );



    array.popBack();

    System.out.println( "After popBack() = " + array );

    }

  }

Output
array = Array( ape, bat, cat ) Demonstrate access array.at( 0 ) = ape array.front() = ape array.at( 2 ) = cat array.back() = cat array.put( 1, "fox" ) array = Array( ape, fox, cat ) After popFront() = Array( fox, cat ) After popBack() = Array( fox )

Counting, Finding, Removing, and Replacing

All sequences include a wide range of useful methods for counting, finding, removing, and replacing elements. Many of these methods have two variations - one for performing the operation on the entire container, and another for performing the operation on a sub-range. The following example shows some of these variations in action using a Deque.

Example Sequences2.java

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

import com.objectspace.jgl.*;



public class Sequences2

  {

  public static void main( String[] args )

    {

    Deque deque = new Deque();

    deque.add( "ape" );

    deque.add( "bat" );

    deque.add( "cat" );

    deque.add( "bat" );

    deque.add( "bat" );

    deque.add( "cat" );

    System.out.println( "deque = " + deque );



    System.out.println( "deque.count( bat ) = " + deque.count( "bat" ) );



    int index = deque.indexOf( "bat" );

    System.out.println( "deque.indexOf( bat ) = " + index );



    deque.remove( index );

    System.out.println( "After deque.remove( " + index + " ) = " + deque );



    deque.replace( 0, 2, "bat", "BAT" );

    System.out.println( "After deque.replace( 0, 2, bat, BAT ) = " + deque );

    System.out.println( "deque.remove( cat ) = " + deque.remove( "cat" ) );

    System.out.println( "After deque.remove( cat ) = " + deque );

    }

  }

Output
deque = Deque( ape, bat, cat, bat, bat, cat ) deque.count( bat ) = 3 deque.indexOf( bat ) = 1 After deque.remove( 1 ) = Deque( ape, cat, bat, bat, cat ) After deque.replace( 0, 2, bat, BAT ) = Deque( ape, cat, BAT, bat, cat ) deque.remove( cat ) = 2 After deque.remove( cat ) = Deque( ape, BAT, bat )

Inserting

All sequences support a comprehensive range of insert methods that allow you to insert one or more elements at a specific index. The following example illustrates these features using a DList.

Example Sequences3.java

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

import com.objectspace.jgl.*;



public class Sequences3

  {

  public static void main( String[] args )

    {

    DList list = new DList();

    list.add( "bat" );

    list.add( "cat" );

    list.add( "dog" );

    System.out.println( "list = " + list );



    list.insert( 0, "ape" );

    System.out.println( "After insert at begin = " + list );



    list.insert( list.size(), "emu" );

    System.out.println( "After insert at end = " + list );



    list.insert( 3, 2, "fox" );

    System.out.println( "After list.insert( 3, 2, fox ) = " + list );

    }

  }

Output
list = DList( bat, cat, dog ) After insert at begin = DList( ape, bat, cat, dog ) After insert at end = DList( ape, bat, cat, dog, emu ) After list.insert( 3, 2, fox ) = DList( ape, bat, cat, fox, fox, dog, emu )

Ensuring Capacity

An Array has a greater control of its underlying storage capacity than any other sequence. An Array's internal storage is a native Java array of objects whose default size is 10. When an element is added that causes the internal storage to overflow, an Array automatically allocates another native Java array with additional capacity and then copies the contents of the old array into the new array using the fast System.arraycopy() method. The old storage is then discarded. This process is repeated when necessary. Note that the current implementation only ever expands the internal storage capacity of an Array, and never shrinks it.

Although this process is generally very efficient, you may manually force an Array to pre-allocate a specified amount of internal storage by using ensureCapacity(). This function is useful if you know in advance the eventual size of a large Array. You can find out the current size of an Array's internal storage by using the capacity() method. To set an Array's capacity to the minimum amount of space required to hold its elements, use trimToSize(). The next example illustrates the automatic capacity increase and the effect that ensureCapacity() and trimToSize() have on the amount of internal storage.

Example Sequences4.java

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

import com.objectspace.jgl.*;



public class Sequences4

  {

  public static void main( String[] args )

    {

    Array array = new Array();

    System.out.print( "array = " + array + ", size = " + array.size() );

    System.out.println( ", capacity = " + array.capacity() );



    array.insert( 0, 9, "x" );

    System.out.print( "array = " + array + ", size = " + array.size() );

    System.out.println( ", capacity = " + array.capacity() );



    for ( int i = 0; i < 2; i++ )

      {

      array.add( "x" ); // Causes reallocation of internal storage.

      System.out.print( "array = " + array + ", size = " + array.size() );

      System.out.println( ", capacity = " + array.capacity() );

      }



    array.ensureCapacity( 1000 ); // Force reallocation of internal storage.

    System.out.print( "array = " + array + ", size = " + array.size() );

    System.out.println( ", capacity = " + array.capacity() );



    array.trimToSize(); // Reduce capacity to the minimum required.

    System.out.print( "array = " + array + ", size = " + array.size() );

    System.out.println( ", capacity = " + array.capacity() );

    }

  }

Output
array = Array(), size = 0, capacity = 10 array = Array( x, x, x, x, x, x, x, x, x ), size = 9, capacity = 10 array = Array( x, x, x, x, x, x, x, x, x, x ), size = 10, capacity = 10 array = Array( x, x, x, x, x, x, x, x, x, x, x ), size = 11, capacity = 20 array = Array( x, x, x, x, x, x, x, x, x, x, x ), size = 11, capacity = 1000 array = Array( x, x, x, x, x, x, x, x, x, x, x ), size = 11, capacity = 11

Constructing From a Native Java array

JGL makes it very easy and efficient to construct an Array from a native Java array of objects. If you pass the Array constructor an existing array, the Array will copy the elements, preserving the state of the original Java array. You may efficiently copy an Array's elements into a native Java array by using copyTo(). The following example illustrates these features.

Example Sequences5.java

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

import com.objectspace.jgl.*;



public class Sequences5

  {

  public static void main( String[] args )

    {

    String strings1[] = { "ape", "bat", "cat" };

    Array array = new Array( strings1 );



    System.out.print( "array = " + array + ", size = " + array.size() );

    System.out.println( ", capacity = " + array.capacity() );



    array.put( 2, "CAT" );

    System.out.println( "array = " + array );

    System.out.print( "Original = " );

    for ( int i = 0; i < strings1.length; i++ )

      System.out.print( strings1[ i ] + " " );

    System.out.println();



    array.add( "dog" ); // Forces reallocation of storage.

    System.out.print( "array = " + array + ", size = " + array.size() );

    System.out.println( ", capacity = " + array.capacity() );

    System.out.print( "Original = " );

    for ( int i = 0; i < strings1.length; i++ )

      System.out.print( strings1[ i ] + " " );

    System.out.println();



    String string2[] = new String[ array.size() ];

    array.copyTo( string2 ); // Copy contents of array into native array.



    for ( int i = 0; i < string2.length; i++ )

      System.out.print( string2[ i ] + " " );

    System.out.println();

    }

  }

Output
array = Array( ape, bat, cat ), size = 3, capacity = 3 array = Array( ape, bat, CAT ) Original = ape bat cat array = Array( ape, bat, CAT, dog ), size = 4, capacity = 6 Original = ape bat cat ape bat CAT dog

Splicing

The DList and SList classes support splicing operations that allow you to cut a single node or range of nodes from one list and paste them into another list. The following example uses an SList to show splicing in action.

Example Sequences6.java

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

import com.objectspace.jgl.*;



public class Sequences6

  {

  public static void main( String[] args )

    {

    SList slist1 = new SList();

    slist1.add( "D" );

    slist1.add( "B" );

    SList slist2 = new SList();

    slist2.add( "E" );

    slist2.add( "A" );

    slist2.add( "C" );

    System.out.println( "slist1 = " + slist1 + ", slist2 = " + slist2 );



    // Insert the whole of slist2 in front of the 1st element of slist1.

    slist1.splice( 0, slist2 );

    System.out.println( "slist1 = " + slist1 + ", slist2 = " + slist2 );



    // Move the 1st element to the end of the slist.

    slist1.splice( 5, slist1, 0 );

    System.out.println( "slist1 = " + slist1 + ", slist2 = " + slist2 );



    // Move the 2nd and 3rd elements to be in front of the last element.

    slist1.splice( 4, slist1, 1, 2 );

    System.out.println( "slist1 = " + slist1 + ", slist2 = " + slist2 );

    }

  }

Output
slist1 = SList( D, B ), slist2 = SList( E, A, C ) slist1 = SList( E, A, C, D, B ), slist2 = SList() slist1 = SList( A, C, D, B, E ), slist2 = SList() slist1 = SList( A, B, C, D, E ), slist2 = SList()

Miscellaneous

The DList class supports a couple of miscellaneous operations. unique() collapses neighboring nodes that contain the same element into a single node, and reverse() efficiently reverses the elements of a list. The following example illustrates both of these methods.

Example Sequences7.java

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

import com.objectspace.jgl.*;



public class Sequences7

  {

  public static void main( String[] args )

    {

    DList list = new DList();

    list.add( "D" );

    list.add( "C" );

    list.add( "C" );

    list.add( "B" );

    list.add( "A" );

    list.add( "A" );

    System.out.println( "list = " + list );



    list.unique();

    System.out.println( "list = " + list );



    list.reverse();

    System.out.println( "list = " + list );

    }

  }

Output
list = DList( D, C, C, B, A, A ) list = DList( D, C, B, A ) list = DList( A, B, C, D )

Contents

Containers

Maps