JGL - The Generic Collection Library for Java

Sequences

Sets

Maps

Putting and Getting

Enumerating

Ordering

Removing and Counting

Matching Keys

Pairs

A map is a data structure that allows you to associate a key with one or more values and then quickly retrieve those values using the key. JGL includes two kinds of maps:

HashMaps store key-value pairs in an internal hash table that does not maintain the pairs in any particular order. However, key-value pairs with matching keys are guaranteed to be adjacent. A HashMap obtains the hash value of a key by using the standard hashCode() method, whose default implementation in Object returns a number that is unique for each object in the system. A HashMap is not allowed to hold duplicate keys by default.

OrderedMaps store key-value pairs in an internal tree structure. By default, the key-value pairs are ordered based on the hash code of the key, although this criterion can easily be changed. Key-value pairs with matching keys are guaranteed to be adjacent. An OrderedMap is not allowed to hold duplicate keys by default.

Each of these classes derive from the abstract Map class, which in turn implements the Container interface and extends the abstract JDK Dictionary class. Here is a diagram that illustrates these relationships:

Under normal circumstances, hashing maps are faster than ordered maps. However, there are some occasions when it is preferred that the contents of a map are kept sorted. All classes that extend the Map class support the following methods:

put - replace the first value associated with a particular key or add it if none exists
get - return the first value associated with a particular key
elements/keys/values - return a JDK Enumeration over the container's values/keys
remove - remove all the key-value pairs with a particular key
count/countValues - return the number of elements that match a particular key or value

By default, JGL maps use the standard equals() method for comparing keys and values. This behavior may be overridden using techniques that are described later in this chapter.

Please note that the most common JGL user error is forgetting to properly define the hashCode() function in a user-defined class. See Storing User-Defined Objects for more information.

The rest of this chapter describes maps in detail.

Putting and Getting

There are two ways to associate a value with a particular key:

add() - if the key doesn't exist or duplicates are allowed, associate the value with the key and return null, otherwise don't modify the map and return the current value associated with the key.

put() - if the key doesn't exist, associate the value with the key and return null, otherwise replace the first value associated with the key and return the old value.

Any attempt to add a null key or value causes a NullPointerException to be thrown. To retrieve the first value associated with a key, use get(). If no value is associated with the key, get() returns null.

The first example illustrates these behaviors for a HashMap that does not allow duplicates.

Example Maps1.java

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

import com.objectspace.jgl.*;



public class Maps1

  {

  public static void main( String[] args )

    {

    HashMap map = new HashMap();

    Object value;



    value = map.add( "Dog", "Marble" );

    System.out.println( "value from add = " + value );



    value = map.add( "Cat", "Beauty" );

    System.out.println( "value from add = " + value );

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



    value = map.add( "Cat", "Agatha" );

    System.out.println( "value from add = " + value );

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



    value = map.get( "Cat" );

    System.out.println( "Cat name is " + value );



    value = map.get( "Ape" );

    System.out.println( "Ape name is " + value );



    value = map.put( "Cat", "Agatha" );

    System.out.println( "value from put = " + value );

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



    String name3 = (String)map.get( "Cat" );

    System.out.println( "Cat name is " + name3 );

    }

  }

Output
value from add = null value from add = null map = HashMap( Pair( Cat, Beauty ), Pair( Dog, Marble ) ) value from add = Beauty map = HashMap( Pair( Cat, Beauty ), Pair( Dog, Marble ) ) Cat name is Beauty Ape name is null value from put = Beauty map = HashMap( Pair( Cat, Agatha ), Pair( Dog, Marble ) ) Cat name is Agatha

The next example is the same as Maps1.java except that duplicates are allowed.

Example Maps2.java

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

import com.objectspace.jgl.*;



public class Maps2

  {

  public static void main( String[] args )

    {

    HashMap map = new HashMap( true ); // allow duplicates

    Object value;



    value = map.add( "Dog", "Marble" );

    System.out.println( "value from add = " + value );



    value = map.add( "Cat", "Beauty" );

    System.out.println( "value from add = " + value );

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



    value = map.add( "Cat", "Agatha" );

    System.out.println( "value from add = " + value );

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



    value = map.get( "Cat" );

    System.out.println( "Cat name is " + value );



    value = map.get( "Ape" );

    System.out.println( "Ape name is " + value );



    value = map.put( "Cat", "Agatha" );

    System.out.println( "value from put = " + value );

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



    String name3 = (String) map.get( "Cat" );

    System.out.println( "Cat name is " + name3 );

    }

  }

Output
value from add = null value from add = null map = HashMap( Pair( Cat, Beauty ), Pair( Dog, Marble ) ) value from add = null map = HashMap( Pair( Cat, Beauty ), Pair( Cat, Agatha ), Pair( Dog, Marble ) ) Cat name is Beauty Ape name is null value from put = Beauty map = HashMap( Pair( Cat, Agatha ), Pair( Cat, Agatha ), Pair( Dog, Marble ) ) Cat name is Agatha

Enumerating

For compatibility with the JDK, elements() returns a Enumeration over every value in a map and keys() returns a Enumeration over every key in a map. There are variations of these functions that enumerate over all keys with a specified value and all values with a particular key. The following example illustrates elements() and keys().

Example Maps3.java

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

import com.objectspace.jgl.*;

import java.util.Enumeration;



public class Maps3

  {

  public static void main( String[] args )

    {

    HashMap map = new HashMap( true ); // allow duplicates

    map.add( new Pair( "Dog", "Marble" ) );

    map.add( new Pair( "Cat", "Beauty" ) );

    map.add( new Pair( "Cat", "Agatha" ) );

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



    System.out.println( "Enumerator through values..." );

    Enumeration values = map.elements();

    while ( values.hasMoreElements() )

      System.out.println( "  " + values.nextElement() );



    System.out.println( "Enumerate through keys..." );

    Enumeration keys = map.keys();

    while ( keys.hasMoreElements() )

      System.out.println( "  " + keys.nextElement() );

    }

  }

Output
map = HashMap( Pair( Cat, Beauty ), Pair( Cat, Agatha ), Pair( Dog, Marble ) ) Enumerator through values... Beauty Agatha Marble Enumerate through keys... Cat Cat Dog

Ordering

By default, OrderedMap collections order key-value pairs in ascending order based on the hash codes of their keys. For example, when Integer objects are stored into an ordered map, they appear in sorted order because the hash code of an Integer is equal to its value. You can change the ordering criterion by supplying a function object with the required sorting criterion. A key-value pair A is placed to the left of the key-value pair B if the function object returns true when passed A's key as its first operand and B's key as its second operand. For more information about function objects, consult the Function Objects chapter. The following example uses a GreaterNumber object to order elements in descending order instead of ascending order.

Example Maps4.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.predicates.*;



public class Maps4

  {

  public static void main( String[] args )

    {

    // Order key-value pairs based on the hash value of the key.

    OrderedMap map1 = new OrderedMap();

    map1.put( new Integer( 1 ), "one" );

    map1.put( new Integer( 3 ), "three" );

    map1.put( new Integer( 2 ), "two" );

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



    // Order key-value pairs in descending numeric order of key.

    OrderedMap map2 = new OrderedMap( new GreaterNumber() );

    map2.put( new Integer( 1 ), "one" );

    map2.put( new Integer( 3 ), "three" );

    map2.put( new Integer( 2 ), "two" );

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

    }

  }

Output
map1 = OrderedMap( Pair( 1, one ), Pair( 2, two ), Pair( 3, three ) ) map2 = OrderedMap( Pair( 3, three ), Pair( 2, two ), Pair( 1, one ) )

Removing and Counting

All maps include operations for counting and removing all the key-value pairs that have a certain key. The following example illustrates these methods.

Example Maps5.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.predicates.*;



public class Maps5

  {

  public static void main( String[] args )

    {

    // Order key-value pairs in descending lexicographical order of keys.

    OrderedMap map = new OrderedMap( new GreaterString(), true );

    map.add( "10", "X" );

    map.add( "10", "ten" );

    map.add( "5", "V" );

    map.add( "5", "five" );



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

    int n = map.count( "10" );

    System.out.println( "There are " + n + " key-value pairs with key 10" );



    System.out.println( "Removing all occurrences of 10..." );

    map.remove( "10" );



    n = map.count( "10" );

    System.out.println( "There are now " + n + " key-value pairs with key 10" );

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

    }

  }

Output
map = OrderedMap( Pair( 5, V ), Pair( 5, five ), Pair( 10, X ), Pair( 10, ten ) ) There are 2 key-value pairs with key 10 Removing all occurrences of 10... There are now 0 key-value pairs with key 10 map = OrderedMap( Pair( 5, V ), Pair( 5, five ) )

Matching Keys

By default, HashMap collections use the standard equals() method for matching keys. To override the way that keys are compared, use a constructor that allows you to specify a binary predicate for matching keys. JGL includes several pre-defined binary predicates. For example, IdenticalTo uses == to compare objects and therefore only considers two keys to match if they are the same object. Consult the Function Objects chapter for more information about binary predicates.

The following example illustrates the difference between using equals() and == when matching keys.

Example Maps6.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.predicates.*;



public class Maps6

  {

  public static void main( String[] args )

    {

    Integer i1 = new Integer( 2 );

    Integer i2 = new Integer( 2 );



    HashMap map1 = new HashMap();

    System.out.println( "Using equals() to compare elements..." );

    System.out.println( "map1.add( i1, two ) = " + map1.add( i1, "two" ) );

    System.out.println( "map1.add( i1, two ) = " + map1.add( i1, "two" ) );

    System.out.println( "map1.add( i2, TWO ) = " + map1.add( i2, "TWO" ) );

    System.out.println( "map1.get( i1 ) = " + map1.get( i1 ) );

    System.out.println( "map1.get( i2 ) = " + map1.get( i2 ) );



    HashMap map2 = new HashMap( new IdenticalTo() );

    System.out.println( "Using == to compare elements..." );

    System.out.println( "map2.add( i1, two ) = " + map2.add( i1, "two" ) );

    System.out.println( "map2.add( i1, two ) = " + map2.add( i1, "two" ) );

    System.out.println( "map2.add( i2, TWO ) = " + map2.add( i2, "TWO" ) );

    System.out.println( "map2.get( i1 ) = " + map2.get( i1 ) );

    System.out.println( "map2.get( i2 ) = " + map2.get( i2 ) );

    }

  }

Output
Using equals() to compare elements... map1.add( i1, two ) = null map1.add( i1, two ) = two map1.add( i2, TWO ) = two map1.get( i1 ) = two map1.get( i2 ) = two Using == to compare elements... map2.add( i1, two ) = null map2.add( i1, two ) = two map2.add( i2, TWO ) = null map2.get( i1 ) = two map2.get( i2 ) = TWO

Pairs

A Pair is a simple object that binds two objects together. After a Pair is constructed with two objects, the objects can be accessed using the public variables first and second.

For compatibility with the Container interface, there is a variation of add() that operates just like the version of add() that takes a key and a value except that it accepts an Object that it casts to a Pairwhose first variable is assumed to be a key and whose second variable is assumed to be a value. An InvalidOperationException is thrown if you attempt to pass in an object that is not a Pair.

The following example illustrates how Pairs may be added to a map.

Example Maps7.java

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

import com.objectspace.jgl.*;



public class Maps7

  {

  public static void main( String[] args )

    {

    Pair pair1 = new Pair( "CAT", "Agatha" );

    Pair pair2 = new Pair( "DOG", "Marble" );

    HashMap map = new HashMap();

    map.add( pair1 );

    map.add( pair2 );

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

    }

  }

Output
map = HashMap( Pair( CAT, Agatha ), Pair( DOG, Marble ) )

Contents

Sequence

Sets