Thursday, November 29, 2007

Filter Iterators Using Predicates

Processing arrays is a simple affair: you can access elements directly by using their indexes, or iterate these simple data structures from start to end. Pretty soon though, you'll begin wishing for more flexibility with the use of more complex data structures and business rules. For example, if you wish to process only elements with a certain attribute, or exclude elements based on some selection criteria, or write applications that do not need to copy entire contents into arrays before processing, simple arrays are not what you need.
The solution is to write customized iterators that can manipulate your basic array without creating duplicate data, minimize having to write duplicate code if you wish to process the array in more than one place, and really separate logic for selecting data from code that processes the data. The easy way is to couple an iterator with a predicate: the iterator can visit any of the elements of the array, while the predicate evaluates whether the elements visited meet some criteria for selection.

Here's an implementation of this idea: this driver class shows how you can filter elements of an array based on a simple criterion. The program generates randomly an array of graph coordinates, and uses a predicate iterator to select only coordinates in the first quadrant.


package com.strive.research.algorithms.iteration;

public class PredicateIteration {

/**
* Generates an array of coordinates.
* @param number Number of coordinates to generate.
* @return Array of coordinates.
*/
public Coordinate[] generateCoordinates(int number) {
Coordinate[] array = new Coordinate[number];
for(int i = 0; i < array.length; i++) {
array[i] = new Coordinate();
}
return array;
}

/**
* Prints the contents of an iterator by calling elements' toString() method.
* @param label Label to prefix ahead of iterator contents.
* @param iterator The iterator with contents to print
*/
public void print(String label, Iterator iterator) {
String contents = "{";
boolean comma = false;
for(iterator.first(); !iterator.isDone(); iterator.next(), comma = true) {
if(comma) {
contents += ", ";
}
contents += iterator.current().toString();
}
contents += "}";
System.out.println(label + ": " + contents);
}

/**
* Demo and test ...
* @param args (Not used).
*/
public static void main(String[] args) {
PredicateIteration prediter = new PredicateIteration();
// How many test items to use
int number = 10;
// Generate the coordinates
Coordinate[] coordinates = prediter.generateCoordinates(number);
// Print the generated list
Iterator general = new ArrayIterator(coordinates);
prediter.print("Original", general);
// Use predicate to show only coordinates in first quadrant
FilterIterator filtered = new FilterIterator(general, new FirstQuadrantPredicate());
prediter.print("Filtered", filtered);
// Exit
System.exit(0);
}
}


These projects are built using Eclipse 3.3.x (Europa) with JDK 1.6.x. You can find complete source code here:
Base project (AlgorithmsInJava) = defines the interfaces and base implementations that largely implement the idea above.
Demo project (IterationWithPredicates) = references the base project and implements a class the shows how to use iterators and predicates to filter data in arrays.