| JGL - The Generic Collection Library for Java |
| JGL - The Generic Collection Library for Java |
Contents
Maps
Queues and Stacks
Putting and GettingOrderingRemoving and CountingMatching ObjectsUnion, 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 sets:
HashSets
store objects in an internal hash table that does not maintain
the objects in any particular order. However, matching objects
are guaranteed to be adjacent. A 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.
OrderedSets
store 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
count - count the number of matching objects
remove - remove all matching objects
HashSets by default do not allow duplicate objects and
use the standard equals() method for comparing objects.
These behaviors may be overriden by
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
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,1997 ObjectSpace, Inc.
public class Widget
{
public String name; // public for demo only.
public int price; // public for demo only.
public Widget( String name, int price )
{
this.name = name;
this.price = price;
}
public int hashCode()
{
return name.hashCode();
}
public boolean equals( Object object )
{
return
object instanceof Widget
&& name.equals( ( (Widget)object ).name );
}
public String toString()
{
return "Widget( " + name + ", " + price + " )";
}
}
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
import Widget;
import java.util.Enumeration;
public class Sets1
{
public static void main( String[] args )
{
HashSet set = new HashSet();
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 put = 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.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.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 collections
order 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 GreaterNumber
object to order elements in descending order instead of ascending
order.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
import com.objectspace.jgl.predicates.*;
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 GreaterNumber() );
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.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
import com.objectspace.jgl.predicates.*;
public class Sets4
{
public static void main( String[] args )
{
// Order elements in descending lexicographical order.
// Note that "1" comes before "5".
OrderedSet set = new OrderedSet( new GreaterString(), true );
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 collections
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.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
import com.objectspace.jgl.predicates.*;
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
set1.add( i1 ) = 2
set1.add( i2 ) = 2
set1.get( i1 ) = 2
set1.get( i2 ) = 2
Using == to compare elements...
set2.add( i1 ) = null
set2.add( i1 ) = 2
set2.add( i2 ) = null
set2.get( i1 ) = 2
set2.get( i2 ) = 2
Union, Intersection, and other Set Operations
The HashSet and OrderedSet family of
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.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import com.objectspace.jgl.*;
public class Sets6
{
public static void main( String[] args )
{
HashSet set1 = new HashSet();
set1.add( "ape" );
set1.add( "dog" );
set1.add( "bat" );
HashSet set2 = new HashSet();
set2.add( "bat" );
set2.add( "fox" );
set2.add( "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, dog, bat ), set2 = HashSet( ape, bat, fox )
set3 = set1.union( set2 ) = HashSet( ape, dog, bat, fox )
set4 = set1.intersection( set2 ) = HashSet( ape, bat )
set5 = set1.difference( set2 ) = HashSet( dog )
set6 = set1.symmetricDifference( set2 ) = HashSet( dog, fox )
set4.subsetOf( set3 ) = true
set3.subsetOf( set4 ) = false
Contents
Maps
Queues and Stacks