Queues and Stacks

Sets

Putting and Getting

Ordering

Removing and Counting

Matching Objects

Union, Intersection, and other Set Operations

A set is a data structure that allows you to add objects into it and then quickly test for their presence. JGL includes two kinds of set:

A HashSet stores objects in an internal hash table that does not maintain the objects in any particular order. However, matching objects are guaranteed to be adjacent. HashSet obtains the hash value of an object by using the standard hashCode() method whose default implementation in Object returns a number that is unique for each object in the system.

An OrderedSet stores objects in an internal tree structure. By default, the objects are ordered based on their hash code, although this criterion can easily be changed. Matching objects are guaranteed to be adjacent.

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

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

put - replace the first matching object or add it if none exists
get - return the first matching object
remove - remove all matching objects

By default, sets do not allow duplicate objects and use the standard equals() method for comparing objects. Both of these behaviors 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 sets in detail.

Putting and Getting

By default, sets do not allow duplicate objects. If you wish a set to allow duplicates, use a constructor that allows you to specify true for the flag allowDuplicates.

There are two ways to add an object to a set:

add() - if the object doesn't exist or duplicates are allowed, add the object and return null, otherwise don't modify the set and return the matching object.

put() - if the object doesn't exist, add the object and return null, otherwise replace the first object that matches and return the old object.

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

The first example illustrates these behaviors for a HashSet that does not allow duplicates. It uses an auxiliary Widget class which defines its equals() method to return true if the names of two widgets are the same.

Widget.java

// Copyright(c) 1996 ObjectSpace, Inc.
public class Widget
  {
  public String myName; // public for demo only.
  public int myPrice; // public for demo only.

  public Widget( String name, int price )
    {
    myName = name;
    myPrice = price;
    }

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

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

  public String toString()
    {
    return "Widget( " + myName + ", " + myPrice + " )";
    }
  }

Example Sets1.java

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

public class Sets1
  {
  public static void main( String[] args )
    {
    HashSet set = new HashSet(); // Don't allow duplicates.
    Object value;

    value = set.add( new Widget( "button", 100 ) );
    System.out.println( "value from add = " + value );
    value = set.add( new Widget( "menu", 200 ) );
    System.out.println( "value from add = " + value );
    System.out.println( "set = " + set );

    value = set.add( new Widget( "button", 300 ) );
    System.out.println( "value from add = " + value );
    System.out.println( "set = " + set );

    value = set.put( new Widget( "button", 300 ) );
    System.out.println( "value from put = " + value );
    System.out.println( "set = " + set );
    }
  }

Output

value from add = null
value from add = null
set = HashSet( Widget( button, 100 ), Widget( menu, 200 ) )
value from add = Widget( button, 100 )
set = HashSet( Widget( button, 100 ), Widget( menu, 200 ) )
value from add = Widget( button, 100 )
set = HashSet( Widget( button, 300 ), Widget( menu, 200 ) )

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

Example Sets2.java

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

public class Sets2
  {
  public static void main( String[] args )
    {
    HashSet set = new HashSet( true ); // Allow duplicates.
    Object value;

    value = set.add( new Widget( "button", 100 ) );
    System.out.println( "value from add = " + value );
    value = set.add( new Widget( "menu", 200 ) );
    System.out.println( "value from add = " + value );
    System.out.println( "set = " + set );

    value = set.add( new Widget( "button", 300 ) );
    System.out.println( "value from add = " + value );
    System.out.println( "set = " + set );

    value = set.put( new Widget( "button", 300 ) );
    System.out.println( "value from put = " + value );
    System.out.println( "set = " + set );
    }
  }

Output

value from add = null
value from add = null
set = HashSet( Widget( button, 100 ), Widget( menu, 200 ) )
value from add = null
set = HashSet(Widget( button, 100 ), Widget( button, 300 ), Widget( menu, 200 ))
value from put = Widget( button, 100 )
set = HashSet(Widget( button, 300 ), Widget( button, 300 ), Widget( menu, 200 ))

Ordering

By default, OrderedSet orders objects in ascending order based on their hash codes. For example, when Integer objects are stored into an ordered set, 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. An object A is placed to the left of object B if the function object returns true when passed A as its first operand and B as its second operand. For more information about function objects, consult the Function Objects chapter. The following example uses a GreaterInteger object to order elements in descending order instead of ascending order.

Example Sets3.java

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

public class Sets3
  {
  public static void main( String[] args )
    {  
    // Order elements based on their hash value.
    OrderedSet set1 = new OrderedSet();
    set1.add( new Integer( 1 ) );
    set1.add( new Integer( 3 ) );
    set1.add( new Integer( 2 ) );
    System.out.println( "set1 = " + set1 );

    // Order elements in descending numeric order.
    OrderedSet set2 = new OrderedSet( new GreaterInteger() );
    set2.add( new Integer( 1 ) );
    set2.add( new Integer( 3 ) );
    set2.add( new Integer( 2 ) );
    System.out.println( "set2 = " + set2 );
    }
  }

Output

set1 = OrderedSet( 1, 2, 3 )
set2 = OrderedSet( 3, 2, 1 )

Removing and Counting

All sets include operations for counting and removing all the objects that match a particular object. The following example illustrates these methods.

Example Sets4.java

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

public class Sets4
  {
  public static void main( String[] args )
    {
    // Order objects in descending lexicographical order 
    // Note that "1" comes before "5".
    OrderedSet set = new OrderedSet( new GreaterString(), true ); // Allow dups.
    set.add( "10" );
    set.add( "10" );
    set.add( "5" );
    set.add( "5" );
    
    System.out.println( "set = " + set );
    int n = set.count( "10" );  
    System.out.println( "There are " + n + " objects that match 10" );

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

    n = set.count( "10" );
    System.out.println( "There are now " + n + " objects that match 10" );
    System.out.println( "set = " + set );
    }
  }

Output

set = OrderedSet( 5, 5, 10, 10 )
There are 2 objects that match 10
Removing all occurrences of 10...
There are now 0 objects that match 10
set = OrderedSet( 5, 5 )

Matching Objects

By default, HashSet use the standard equals() method for matching objects. To override the way that objects are compared, use a constructor that allows you to specify a binary predicate for matching objects. JGL includes several pre-defined binary predicates. For example, IdenticalTo uses == to compare objects and therefore only considers two objects 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 objects.

Example Sets5.java

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

public class Sets5
  {
  public static void main( String[] args )
    {
    Integer i1 = new Integer( 2 );
    Integer i2 = new Integer( 2 );

    HashSet set1 = new HashSet();
    System.out.println( "Using equals() to compare elements..." );
    System.out.println( "set1.add( i1 ) = " + set1.add( i1 ) );
    System.out.println( "set1.add( i1 ) = " + set1.add( i1 ) );
    System.out.println( "set1.add( i2 ) = " + set1.add( i2 ) );
    System.out.println( "set1.get( i1 ) = " + set1.get( i1 ) );
    System.out.println( "set1.get( i2 ) = " + set1.get( i2 ) );

    HashSet set2 = new HashSet( new IdenticalTo() );
    System.out.println( "Using == to compare elements..." );
    System.out.println( "set2.add( i1 ) = " + set2.add( i1 ) );
    System.out.println( "set2.add( i1 ) = " + set2.add( i1 ) );
    System.out.println( "set2.add( i2 ) = " + set2.add( i2 ) );
    System.out.println( "set2.get( i1 ) = " + set2.get( i1 ) );
    System.out.println( "set2.get( i2 ) = " + set2.get( i2 ) );
    }
  }

Output

Using equals() to compare elements...
set1.add( i1 ) = null // succeed
set1.add( i1 ) = 2 // fail
set1.add( i2 ) = 2 // fail
set1.get( i1 ) = 2
set1.get( i2 ) = 2
Using == to compare elements...
set2.add( i1 ) = null // succeed
set2.add( i1 ) = 2 // fail
set2.add( i2 ) = null // succeed
set2.get( i1 ) = 2
set2.get( i2 ) = 2

Union, Intersection, and other Set Operations

The HashSet and OrderedSet classes include a useful collection of set operations, including union(), intersection(), and difference(). Note that these methods return their result in a new set and do not affect the contents of the receiver or the argument. The set operations are only defined for sets that do not allow duplicates. Any attempt to perform a set operation with a set that allows duplicates causes a InvalidOperationException to be thrown. All of the set operations are illustrated by the following example.

Example Sets6.java

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

public class Sets6
  {
  public static void main( String[] args )
    {
    HashSet set1 = new HashSet();
    set1.insert( "ape" );
    set1.insert( "cat" );
    set1.insert( "bat" );

    HashSet set2 = new HashSet();
    set2.insert( "bat" );
    set2.insert( "fox" );
    set2.insert( "ape" );
    System.out.println( "set1 = " + set1 + ", set2 = " + set2 );

    HashSet set3 = set1.union( set2 );
    System.out.println( "set3 = set1.union( set2 ) = " + set3 );

    HashSet set4 = set1.intersection( set2 );
    System.out.println( "set4 = set1.intersection( set2 ) = " + set4 );

    HashSet set5 = set1.difference( set2 );
    System.out.println( "set5 = set1.difference( set2 ) = " + set5 );

    HashSet set6 = set1.symmetricDifference( set2 );
    System.out.println( "set6 = set1.symmetricDifference( set2 ) = " + set6 );

    System.out.println( "set4.subsetOf( set3 ) = " + set4.subsetOf( set3 ) );
    System.out.println( "set3.subsetOf( set4 ) = " + set3.subsetOf( set4 ) );
    }
  }

Output

set1 = HashSet( ape, bat, cat ), set2 = HashSet( ape, bat, fox )
set3 = set1.union( set2 ) = HashSet( ape, bat, fox, cat )
set4 = set1.intersection( set2 ) = HashSet( ape, bat )
set5 = set1.difference( set2 ) = HashSet( cat )
set6 = set1.symmetricDifference( set2 ) = HashSet( fox, cat )
set4.subsetOf( set3 ) = true
set3.subsetOf( set4 ) = false

Contents

Maps

Queues and Stacks