JGL - The Generic Collection Library for Java

Algorithms

Iterators

Function Objects

Predicates

General Functions

Binders

Composers

Creating your own Function Objects

Many of the JGL algorithms and containers require you to specify a function object (sometimes known as a functor) to perform their operation. A function object can have instance variables and may be created and stored just like any other kind of object. A function object that processes one parameter is called a unary function, whereas a function that processes two parameters is called a binary function. There are two main types of function object:

Predicates always return a boolean, and are used for ordering elements or triggering actions. These classes are located in the com.objectspace.jgl.predicates package.
General functions perform an arbitrary operation on one or more arguments and return an Object. These classes are located in the com.objectspace.jgl.functions package.

The rest of this chapter describes predicates and general functions in more detail.

Predicates

Predicates are function objects that are used to trigger actions or order elements, and always return a boolean. For example, the countIf() algorithm allows you to count all of the values in a sequence that satisfy a user-supplied unary predicate, and the sort() algorithm orders the elements of a sequence using a user-supplied binary predicate.

JGL defines interfaces for unary and binary predicates. The UnaryPredicate interface defines a single method called execute() that takes a single Object parameter and returns a boolean. The BinaryPredicate interface defines a single method also called execute() that takes two Object parameters and returns a boolean. For example, here is the source code for the unary predicate object LogicalNot:

package com.objectspace.jgl.predicates;



import com.objectspace.jgl.*;



/**

 * LogicalNot is a unary predicate that returns true if its operand is equal to false.

 */



public final class LogicalNot implements UnaryPredicate

  {

  /**

   * Perform a logical NOT.

   * @param object The operand, which must be an instance of Boolean.

   * @return true if the operand is equal to Boolean.FALSE.

   */

  public boolean execute( Object object )

    {

    return !( (Boolean)object ).booleanValue();

    }

  }

The following example uses PositiveNumber to count the number of positive integers in a Vector:

Example Functions1.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.algorithms.*;

import com.objectspace.jgl.predicates.*;



public class Functions1

  {

  public static void main( String[] args )

    {

    Array array = new Array();

    array.add( new Integer( 3 ) );

    array.add( new Integer( -2 ) );

    array.add( new Integer( 3 ) );

    array.add( new Integer( -5 ) );

    array.add( new Integer( -4 ) );



    UnaryPredicate predicate = new PositiveNumber();

    int n = Counting.countIf( array, predicate );

    System.out.println( "Number of positive Integers in " + array + " = " + n );

    }

  }

Output
Number of positive Integers in Array( 3, -2, 3, -5, -4 ) = 2

Earlier in this document you saw the class called LogicalNot. This is a unary predicate that returns true if its single operand is false. The following example uses an instance of this class to count all of the false elements in a native Java array:

Example Functions2.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.adapters.*;

import com.objectspace.jgl.algorithms.*;

import com.objectspace.jgl.predicates.*;



public class Functions2

  {

  public static void main( String[] args )

    {

    boolean array[] = { false, false, true, false, true };

    BooleanArray bools = new BooleanArray( array );

    UnaryPredicate predicate = new LogicalNot();

    int n = Counting.countIf( bools, predicate );

    System.out.println( "Number of false in " + bools + " = " + n );

    }

  }

Output
Number of false in boolean[]( false, false, true, false, true ) = 3

Predicates are often used as a comparator for ordering elements. An object A will be placed to the left of an object B if the predicate object returns true when executed with A as the first operand and B as the second operand. Note that a properly designed comparator should always return false when comparing two objects that are equal. Here is the source code for an example comparator, GreaterString.


package com.objectspace.jgl.predicates;



import com.objectspace.jgl.*;



/**

 * GreaterString is a binary predicate that

 * returns true if the first operand as a string

 * is greater than the second operand as a string.

 */



public final class GreaterString implements BinaryPredicate

  {

  /**

   * Return true if the first operand is greater than the second operand.

   * @param first The first operand, which is converted into a String if necessary.

   * @param second The second operand, which is converted into a String if necessary.

   * @return first.toString() > second.toString()

   */

  public boolean execute( Object first, Object second )

    {

    return first.toString().compareTo( second.toString() ) > 0;

    }

  }

One variation of sort() allows you to specify a function that is used to control the order of sorting. In the following example, GreaterString tells sort() to place the first operand to the left of the second operand if the first operand is greater than the second operand.

Example Functions3.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.algorithms.*;

import com.objectspace.jgl.predicates.*;



public class Functions3

  {

  public static void main( String[] args )

    {

    Deque deque = new Deque();

    deque.add( "cat" );

    deque.add( "ape" );

    deque.add( "dog" );

    deque.add( "bat" );

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

    BinaryPredicate comparator = new GreaterString();

    Sorting.sort( deque, comparator );

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

    }

  }

Output
unsorted = Deque( cat, ape, dog, bat ) sorted = Deque( dog, cat, bat, ape )

The next example uses the binary predicate LessNumber to sort a native array of bytes. Passing the Class object for the Long class to LessNumber causes the longValue() method of java.lang.Number to be used instead of the default intValue().

Example Functions4.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.adapters.*;

import com.objectspace.jgl.algorithms.*;

import com.objectspace.jgl.predicates.*;



public class Functions4

  {

  public static void main( String[] args )

    {

    long array[] = { 3, 1, 5, -2, 7, 9 };

    LongArray longArray = new LongArray( array );

    BinaryPredicate comparator = new LessNumber( Long.class );

    System.out.println( "unsorted = " + longArray );

    Sorting.sort( longArray, comparator );

    System.out.println( "sorted = " + longArray );

    }

  }

Output
unsorted = long[]( 3, 1, 5, -2, 7, 9 ) sorted = long[]( -2, 1, 3, 5, 7, 9 )

For reference, here is a list of all the standard JGL function predicate objects.

Unary Predicates

x represents argument to `execute()`
P, Q, and R represent other predicate objects
C represents an instance of a `java.lang.Class` object
V represents a constant value
Name	Operation
`BindFirstPredicate`	P( V, x )
`BindSecondPredicate`	P( x, V )
`ConstantPredicate`	V
`InstanceOf`	x instanceof C
`LogicalNot`	!x
`NegativeNumber`	x < 0
`PositiveNumber`	x > 0
`UnaryAnd`	P( x ) && Q( x )
`UnaryComposePredicate`	P( Q( x ) )
`UnaryNot`	!P( x )
`UnaryOr`	P( x ) \|\| Q( x )
`UnaryTern`	P( x ) ? Q( x ) : R( x )

Binary Predicates

x and y represent arguments to `execute()`
P, Q, and R represent other predicate objects
V represents a constant value
Name	Operation
`BinaryAnd`	P( x, y ) && Q( x, y )
`BinaryComposePredicate`	P( Q( x ), R( y ) )
`BinaryNot`	!P( x, y )
`BinaryOr`	P( x, y ) \|\| Q( x, y )
`BinaryTern`	P( x, y ) ? Q( x, y ) : R( x, y )
`ConstantPredicate`	V
`EqualCollationKey`	x.compareTo( y ) == 0
`EqualCollator`	collator.compare( x, y ) == 0
`EqualNumber`	x == y
`EqualString`	x.toString().equals( y.toString() )
`EqualTo`	x.equals( y )
`GreaterEqualCollationKey`	( collator.getCollationKey( x.toString() ) ).compare( collator.getCollationKey( y.toString() ) ) >= 0
`GreaterEqualCollator`	collator.compare( x.toString(), y.toString() ) <= 0
`GreaterEqualNumber`	x >= y
`GreaterEqualString`	x.toString().compareTo( y.toString() ) >= 0
`GreaterCollationKey`	( collator.getCollationKey( x.toString() ) ).compare( collator.getCollationKey( y.toString() ) ) > 0
`GreaterCollator`	collator.compare( x.toString(), y.toString() ) > 0
`GreaterNumber`	x > y
`GreaterString`	x.toString().compareTo( y.toString() ) > 0
`HashComparator`	x.hashCode() < y.hashCode()
`IdenticalTo`	x == y
`LessEqualCollationKey`	( collator.getCollationKey( x.toString() ) ).compare( collator.getCollationKey( y.toString() ) ) <= 0
`LessEqualCollator`	collator.compare( x.toString(), y.toString() ) <= 0
`LessEqualNumber`	x <= y
`LessEqualString`	x.toString().compareTo( y.toString() ) <= 0
`LessCollationKey`	( collator.getCollationKey( x.toString() ) ).compare( collator.getCollationKey( y.toString() ) ) < 0
`LessCollator`	collator.compare( x.toString(), y.toString() ) < 0
`LessNumber`	x < y
`LessString`	x.toString().compareTo( y.toString() ) < 0
`LogicalAnd`	x && y
`LogicalOr`	x \|\| y
`NotEqualCollationKey`	x.compareTo( y ) != 0
`NotEqualCollator`	collator.compare( x, y ) != 0
`NotEqualNumber`	x != y
`NotEqualString`	!x.toString().equals( y.toString() )
`NotEqualTo`	!x.equals( y )
`NotIdenticalTo`	x != y
`SwappedBinaryPredicate`	P( y, x )

In addition, here is a list of the standard JGL algorithms that accept a predicate:

adjacentFind()
countIf()
detect()
every()
findIf()
includes()
iterSort()
makeHeap()
median()
nextPermutation()
popHeap()
prevPermutation()
pushHeap()
reject()
removeCopyIf()
removeIf()
replaceCopyIf()
replaceIf()
select()
setDifference()
setIntersection()
setSymmetricDifference()
setUnion()
some()
sort()
sortHeap()
unique()
uniqueCopy()

General Functions

General functions are function objects that take objects as parameters and return another object. They are often used to apply a mathematical operation to every element in a collection. JGL defines interfaces for unary and binary general functions. The UnaryFunction interface defines a single method called execute() that takes a single Object parameter and returns an Object. The BinaryFunction interface defines a single method also called execute() that takes two Object parameters and returns an Object. For example, here's the source code of an example general function, LengthString.


package com.objectspace.jgl.functions;



import com.objectspace.jgl.*;



/**

 * LengthString is a unary function that returns the length of

 * its operand as a string.

 */



public final class LengthString implements UnaryFunction

  {

  /**

   * Return the length of my operand's string as an Integer.

   * @param object The operand

   * @return The length of the operand.toString().

   */

  public Object execute( Object object )

    {

    return new Integer( object.toString().length() );

    }

  }

This function object can be used by transform() to negate every object in a sequence and store the result into another sequence. The follow example uses NegateNumber to negate every element in a Deque:

Example Functions5.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.algorithms.*;

import com.objectspace.jgl.functions.*;



public class Functions5

  {

  public static void main( String[] args )

    {

    Deque deque = new Deque();

    deque.add( new Integer( 4 ) );

    deque.add( new Integer( -2 ) );

    deque.add( new Integer( 3 ) );

    UnaryFunction function = new NegateNumber();

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

    Transforming.transform( deque, deque.begin(), function );

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

    }

  }

Output
before = Deque( 4, -2, 3 ) after = Deque( -4, 2, -3 )

For reference, here's a list of all standard JGL general functions. A later section explains how you can add further variations of your own.

Unary Functions

x represents argument to `execute()`
P and Q represent other function objects
V represents a constant value
Name	Operation
`BindFirst`	P( V, x )
`BindSecond`	P( x, V )
`ConstantFunction`	V
`Hash`	x.hashCode()
`IdentityFunction`	x
`LengthString`	x.toString().length()
`NegateNumber`	-x
`SelectFirst`	x.first
`SelectSecond`	x.second
`ToString`	x.toString()
`UnaryCompose`	P( Q( x ) )
`UnaryPredicateFunction`	P( x )

Binary Functions

x and y represent arguments to `execute()`
P, Q, and R represent other function objects
V represents a constant value
Name	Operation
`BinaryCompose`	P( Q( x ), R( y ) )
`BinaryPredicateFunction`	P( x, y )
`ConstantFunction`	V
`DividesNumber`	x / y
`MinusNumber`	x - y
`ModulusNumber`	x % y
`PlusNumber`	x + y
`PlusString`	x.toString() + y.toString()
`SwappedBinaryFunction`	P( y, x )
`TimesNumber`	x * y

In addition, here's a list of all the standard JGL algorithms that accept general functions:

transform()
accumulate()
adjacentDifference()

Binders

The predicate objects BindFirstPredicate and BindSecondPredicate allow you to give a fixed value to either the 1^st or the 2^nd argument of a binary predicate, respectively. For example, here's how you can use BindSecondPredicate to count all of the strings in a DList that are greater than "bat".

Example Functions6.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.algorithms.*;

import com.objectspace.jgl.predicates.*;



public class Functions6

  {

  public static void main( String[] args )

    {

    DList list = new DList();

    list.add( "dog" );

    list.add( "ape" );

    list.add( "emu" );

    UnaryPredicate predicate = new BindSecondPredicate( new GreaterString(), "bat" );

    int n = Counting.countIf( list, predicate );

    System.out.println( "The number of strings in " + list + " > bat = " + n );

    }

  }

Output
The number of strings in DList( dog, ape, emu ) > bat = 2

The function objects BindFirst and BindSecond allow you to bind operands to general function objects.

Composers

The UnaryComposePredicate and BinaryComposePredicate function objects allow you to apply a secondary function to each operand before applying the main predicate. For example, to sort strings based on their length, use BinaryComposePredicate as follows.

Example Functions7.java

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

import com.objectspace.jgl.*;

import com.objectspace.jgl.algorithms.*;

import com.objectspace.jgl.functions.*;

import com.objectspace.jgl.predicates.*;



public class Functions7

  {

  public static void main( String[] args )

    {

    Array array = new Array();

    array.add( "ape" );

    array.add( "giraffe" );

    array.add( "lizard" );



    BinaryPredicate comparator = new BinaryComposePredicate

      ( 

      new GreaterNumber(), 

      new LengthString(), 

      new LengthString() 

      );

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



    Sorting.sort( array, comparator );

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

    }

  }

Output
before = Array( ape, giraffe, lizard ) after = Array( giraffe, lizard, ape )

The function objects UnaryCompose and BinaryCompose allow you to apply a secondary function to each operand before applying the main general function.

Creating your own Function Objects

To create your own function object, use the following rules:

If the function object you want to create is a predicate that must process one argument, implement the UnaryPredicate interface and define an execute() method that takes one Object argument and returns a boolean.

If the function object you want to create is a predicate that must process two arguments, implement the BinaryPredicate interface and define an execute() method that takes two Object arguments and returns a boolean.

If the function object you want to create is a general function that must process one argument, implement the UnaryFunction interface and define an execute() method that takes one Object argument and returns an Object.

If the function object you want to create is a general function that must process two arguments, implement the BinaryFunction interface and define an execute() method that takes two Object arguments and returns an Object.

Cast the input objects as necessary. If the method must return a number or character, make sure the primitive value is converted into its object equivalent using the primitive wrapper classes in java.lang.

Contents Algorithms Iterators