List of Algorithms by CategoryContents
Array Adapters
Function Objects
List of Algorithms by CategoryApplyingCopyingCountingFindingFilteringReplacingReversingSortingTransformingApplying an Algorithm to a Sub-Range of a Container
One of JGL's primary strengths is its comprehensive
set of reusable algorithms that can be applied to a wide variety
of data structures, including JGL containers, JDK containers,
and native Java arrays. Because JGL algorithms are stand-alone
and are not part of any JGL container, you can add new algorithms
to JGL without changing any of the existing code. We hope that
users of JGL will send new algorithms to ObjectSpace so that they
can be incorporated into subsequent releases of JGL. Significant
contributions will always be acknowledged in our documentation.
All JGL algorithms are categorized and packaged as
public static methods of a class that represents the category.
For example, the remove(),
removeIf(),
removeCopy(),
and removeCopyIf()
algorithms are all public static methods of the Removing
class.
The next section contains a list of all the JGL algorithm classes and methods. Subsequent chapters contain examples of several common algorithms at work.
List of Algorithms by Category
This section lists all of the JGL algorithms by class,
together with a brief synopsis. Each algorithm is implemented
as a public static method of its associated class - you cannot
create instances of any algorithm class. For detailed information
about a particular algorithm, consult the online class catalog.
forEach | apply a function to every item in a range |
inject | iteratively apply a binary function to every item in a range |
Comparing
equal | check that two sequences match |
lexicographicalCompare | lexicographically compare two sequences |
median | return the median of three values |
mismatch | search two sequences for a mismatched item |
Copying
copy | copy a range of items to another area |
copyBackward | copy a range of items backwards to another area |
Counting
accumulate | sum the values in a range |
adjacentDifference | calculate and sum the difference between adjacent values |
count | count items in a range that match a value |
countIf | count items in a range that satisfy a predicate |
Filling
fill | set every item in a range to a particular value |
fillN | set n items to a particular value |
Filtering
reject | return all values that do not satisfy a predicate |
select | return all values that satisfy a predicate |
unique | collapse all consecutive values in a sequence |
uniqueCopy | copy a sequence, collapsing consecutive values |
Finding
adjacentFind | locate consecutive sequence in a range |
detect | return first item that satisfies a predicate |
every | return true if every item in a range satisfies a predicate |
find | locate an item in a sequence |
findIf | locate an item that satisfies a predicate in a range |
some | return true if at least one item in a range satisfies a predicate |
Heap
makeHeap | make a sequence into a heap |
popHeap | pop the top value from a heap |
pushHeap | place the last element into a heap |
sortHeap | sort a heap |
MinMax
minElement | return the minimum item within a range |
maxElement | return the maximum item within a range |
Permuting
nextPermutation | change sequence to next lexicographic permutation |
prevPermutation | change sequence to previous lexicographic permutation |
Printing
print | prints a sequence to standard output |
println | prints a sequence to standard output followed by a newline |
toString | returns a description of a sequence |
Removing
remove | remove all matching items from a sequence |
removeCopy | copy a sequence, removing all matching items |
removeCopyIf | copy sequence, removing all that satisfy predicate |
removeIf | remove items that satisfy predicate from sequence |
Replacing
replace | replace specified value in a sequence with another |
replaceCopy | copy sequence, replacing matching values |
replaceCopyIf | copy sequence, replacing values that satisfy predicate |
replaceIf | replace specified values that satisfy a predicate |
Reversing
reverse | reverse the items in a sequence |
reverseCopy | create a reversed copy of a sequence |
Rotating
rotate | rotate a sequence by n positions |
rotateCopy | copy a sequence, rotating it by n positions |
SetOperations
includes | search for one sequence in another sequence |
setDifference | create set of elements in 1st sequence that are not in 2nd |
setIntersection | create set of elements that are in both sequences |
setSymmetricDifference | create set of elements that not in both sequences |
setUnion | create set of elements that are in either sequence |
Shuffling
randomShuffle | randomize sequence using random shuffles |
Sorting
sort | sort a sequence |
Swapping
iterSwap | swap the values indicated by two iterators |
swapRanges | swap two ranges of items |
Transforming
collect | return result of applying a function to every item in a range |
transform | transform one sequence into another |
Applying
The Applying
class has a couple of algorithms for applying a function to every element of
a container. forEach() applies a unary function to every element of a
container. inject() calculates an initial result by calling a binary function with the
initial value as the first parameter and the first element as the second parameter.
It then applies the function to the remaining elements, using the previous result as the
first parameter and the next element as the second parameter. The last result is then
returned. For more information about unary and binary functions,
refer to the Function Objects chapter. The following
example illustrates both of the applying algorithms.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
public class Algorithms1
{
public static void main( String[] args )
{
Array array1 = new Array();
array1.add( "cat" );
array1.add( "monkey" );
array1.add( "goat" );
Applying.forEach( array1, new PrintFunction() );
SList list = new SList();
list.add( new Integer( 3 ) );
list.add( new Integer( 7 ) );
list.add( new Integer( 4 ) );
Integer total = (Integer) Applying.inject( list, new Integer( 0 ), new PlusNumber() );
System.out.println( "list = " + list + ", total = " + total );
}
}
class PrintFunction implements UnaryFunction
{
public Object execute( Object object )
{
System.out.println( "PRINT " + object );
return null; // Not used.
}
}
Output
PRINT cat
PRINT monkey
PRINT goat
list = SList( 3, 7, 4 ), total = 14
The Copying
class contains a variety of copying algorithms for adding the
contents of one container to another container. Behind the scenes,
the algorithms use the destination's add()
method to perform the copy. The following example uses container
adapters to copy the contents of a native Java array of ints
into a JDK Vector.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
import java.util.Vector;
public class Algorithms2
{
public static void main( String[] args )
{
int ints[] = { 2, 6, 3, 7 };
Vector vector = new Vector();
vector.addElement( new Integer( 1 ) );
vector.addElement( new Integer( 4 ) );
// Create container adapters.
IntArray intArray = new IntArray( ints );
VectorArray vectorArray = new VectorArray( vector );
System.out.println( "vector before copying = " + vector );
Copying.copy( intArray, vectorArray );
System.out.println( "vector after copying = " + vector );
}
}
Output
vector before copying = [1, 4]
vector after copying = [1, 4, 2, 6, 3, 7]
The Counting
class has several algorithms for involving counting the elements in
a container that either match a particular value or satisfy a
specified unary predicate. For more information about predicates,
refer to the Function Objects chapter. The following
example illustrates the most common varieties of the counting algorithms.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
public class Algorithms3
{
public static void main( String[] args )
{
SList list = new SList();
list.add( new Integer( -1 ) );
list.add( new Integer( 1 ) );
list.add( new Integer( -2 ) );
list.add( new Integer( 1 ) );
list.add( new Integer( -3 ) );
System.out.println( "list = " + list );
Object value = new Integer( 1 );
int n1 = Counting.count( list, value );
System.out.println( "Occurences of " + value + " = " + n1 );
int n2 = Counting.countIf( list, new NegativeNumber() );
System.out.println( "Occurences of a negative = " + n2 );
}
}
Output
list = SList( -1, 1, -2, 1, -3 )
Occurences of 1 = 2
Occurences of a negative = 3
The Finding
class has several algorithms for locating elements in
a container that either match a particular value or satisfy a
specified unary predicate. For example, detect() returns the first
object that satisfies a unary predicate, and some() returns true
if at least one object in the container satisfies a unary predicate. For more information
about predicates, refer to the Function Objects chapter.
The following example illustrates two of the finding algorithms.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
public class Algorithms4
{
public static void main( String[] args )
{
int ints[] = { 3, 7, 8, 2, -5, 8, 9, -2 };
IntArray array = new IntArray( ints );
System.out.println( "array = " + array );
Integer negative = (Integer) Finding.detect( array, new NegativeNumber() );
System.out.println( "first negative = " + negative );
boolean some = Finding.some( array, new NegativeNumber() );
System.out.println( "some items are negative = " + some );
}
}
Output
array = int[]( 3, 7, 8, 2, -5, 8, 9, -2 )
first negative = -5
some items are negative = true
The Filtering
class has several algorithms for creating a copy of a sequence whilst performing
a filtering operation. For example, select() and reject() return
a copy of a sequence that only contains the elements that do/don't satisfy a predicate,
respectively. For more information about predicates,
refer to the Function Objects chapter. The following
example illustrates a couple of the filtering algorithms.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
public class Algorithms5
{
public static void main( String[] args )
{
Array array1 = new Array();
array1.add( "cat" );
array1.add( "monkey" );
array1.add( "goat" );
array1.add( "elephant" );
System.out.println( "array1 = " + array1 );
// Predicate that returns true if a string is greater than 4 characters long.
UnaryPredicate predicate = new UnaryComposePredicate
(
new BindSecondPredicate( new GreaterNumber(), new Integer( 4 ) ),
new LengthString()
);
Array array2 = (Array) Filtering.select( array1, predicate );
System.out.println( "strings with length > 4 = " + array2 );
Array array3 = (Array) Filtering.reject( array1, predicate );
System.out.println( "strings with length <= 4 = " + array3 );
}
}
Output
array1 = Array( cat, monkey, goat, elephant )
strings with length > 4 = Array( monkey, elephant )
strings with length <= 4 = Array( cat, goat )
The Replacing
class contains generic algorithms for replacing objects that have
a particular value or that satisfy a particular unary predicate.
There are versions of the algorithm that modify the source container
and others that copy the result into a separate container. The
following example demonstrates two of these variations.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
public class Algorithms6
{
public static void main( String[] args )
{
DList list = new DList();
list.add( new Integer( -1 ) );
list.add( new Integer( 1 ) );
list.add( new Integer( -2 ) );
list.add( new Integer( 1 ) );
list.add( new Integer( -3 ) );
System.out.println( "list = " + list );
Object oldValue = new Integer( 1 );
Object newValue = new Integer( 4 );
int n1 = Replacing.replace( list, oldValue, newValue );
System.out.println( "after 1 -> 4, list = " + list );
Array array = new Array();
UnaryPredicate predicate = new NegativeNumber();
newValue = new Integer( 0 );
Replacing.replaceCopyIf( list, array, predicate, newValue );
System.out.println( "list = " + list );
System.out.println( "array = " + array );
}
}
Output
list = DList( -1, 1, -2, 1, -3 )
after 1 -> 4, list = DList( -1, 4, -2, 4, -3 )
list = DList( -1, 4, -2, 4, -3 )
array = Array( 0, 4, 0, 4, 0 )
The Reversing
class contains algorithms for reversing the contents of a container,
as demonstrated by the following example.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
public class Algorithms7
{
public static void main( String[] args )
{
Deque deque = new Deque();
deque.add( "Batman" );
deque.add( "Superman" );
deque.add( "Phantom" );
deque.add( "Spider-Man" );
System.out.println( "before reverse = " + deque );
Reversing.reverse( deque );
System.out.println( "after reverse = " + deque );
}
}
Output
before reverse = Deque( Batman, Superman, Phantom, Spider-Man )
after reverse = Deque( Spider-Man, Phantom, Superman, Batman )
The Sorting
class contains a highly efficient quicksort-based algorithm for
sorting any Sequence.
By default, elements are sorted in increasing order of hash value.
This default behavior works well for sorting Integer
objects, since their hash value is equal to their actual integer
value. To change this default behavior, supply the sort algorithm
with a binary predicate object. 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. For more information about predicates,
refer to the chapter called Function Objects. The
following example illustrates both uses of the sorting algorithm.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
public class Algorithms8
{
public static void main( String[] args )
{
Array array = new Array();
array.add( new Integer( 3 ) );
array.add( new Integer( -2 ) );
array.add( new Integer( 4 ) );
array.add( new Integer( -5 ) );
System.out.println( "unsorted array = " + array );
Sorting.sort( array );
System.out.println( "sorted array = " + array );
Deque deque = new Deque();
deque.add( "triangle" );
deque.add( "square" );
deque.add( "pentagon" );
deque.add( "hexagon" );
System.out.println( "unsorted deque = " + deque );
Sorting.sort( deque, new LessString() );
System.out.println( "sorted deque = " + deque );
}
}
Output
unsorted array = Array( 3, -2, 4, -5 )
sorted array = Array( -5, -2, 3, 4 )
unsorted deque = Deque( triangle, square, pentagon, hexagon )
sorted deque = Deque( hexagon, pentagon, square, triangle )
The Transforming
class contains a couple of algorithms for replacing every element of a container
with a transformed version of itself. The transformation is specified
with a unary function object. It also contains an algorithm for applying
a binary function in a pair-wise fashion to every element in two containers and
storing the results into a third container. For more information
about function objects, consult the Function Objects
chapter. The following example illustrates these algorithms.
// Copyright(c) 1996,1997 ObjectSpace, Inc.
import COM.objectspace.jgl.*;
public class Algorithms9
{
public static void main( String[] args )
{
int ints1[] = { 1, 3, 5, 2 };
Array array = new Array();
IntArray intArray1 = new IntArray( ints1 );
UnaryFunction function = new NegateNumber();
Transforming.transform( intArray1, array, function );
System.out.println( "ints1 = " + intArray1 );
System.out.println( "array = " + array );
System.out.println();
int ints2[] = { 2, 4, 2, 3 };
int ints3[] = { 3, 6, 2, 1 };
SList list = new SList();
IntArray intArray2 = new IntArray( ints2 );
IntArray intArray3 = new IntArray( ints3 );
BinaryFunction function2 = new TimesNumber();
Transforming.transform( intArray2, intArray3, list, function2 );
System.out.println( "ints2 = " + intArray2 );
System.out.println( "ints3 = " + intArray3 );
System.out.println( "list = " + list );
System.out.println();
Array array1 = new Array();
array1.add( "cat" );
array1.add( "monkey" );
array1.add( "goat" );
System.out.println( "array1 = " + array1 );
Array array2 = (Array) Transforming.collect( array1, new LengthString() );
System.out.println( "array2 = " + array2 );
}
}
Output
ints1 = int[]( 1, 3, 5, 2 )
array = Array( -1, -3, -5, -2 )
ints2 = int[]( 2, 4, 2, 3 )
ints3 = int[]( 3, 6, 2, 1 )
list = SList( 6, 24, 4, 3 )
array1 = Array( cat, monkey, goat )
array2 = Array( 3, 6, 4 )
All of the algorithm examples in this section
apply an algorithm to an entire container. If you wish you apply
an algorithm to a sub-range of a container, you must take advantage
of the JGL iterators. These are described fully in the Iterators
chapter.
Contents
Array Adapters
Function Objects
