Solution for Programmming Exercise 10.4
This page contains a sample solution to one of the exercises from Introduction to Programming Using Java.
Exercise 10.4:
A predicate is a boolean-valued function with one parameter. Some languages use predicates in generic programming. Java doesn't, but this exercise looks at how predicates might work in Java.
In Java, we could implement "predicate objects" by defining a generic interface:
public interface Predicate<T> {
public boolean test( T obj );
}
The idea is that an object that implements this interface knows how to "test" objects of type T in some way. Define a class that contains the following generic static methods for working with predicate objects. The name of the class should be Predicates, in analogy with the standard class Collections that provides various static methods for working with collections.
public static <T> void remove(Collection<T> coll, Predicate<T> pred) // Remove every object, obj, from coll for which // pred.test(obj) is true. public static <T> void retain(Collection<T> coll, Predicate<T> pred) // Remove every object, obj, from coll for which // pred.test(obj) is false. (That is, retain the // objects for which the predicate is true.) public static <T> List<T> collect(Collection<T> coll, Predicate<T> pred) // Return a List that contains all the objects, obj, // from the collection, coll, such that pred.test(obj) // is true. public static <T> int find(ArrayList<T> list, Predicate<T> pred) // Return the index of the first item in list // for which the predicate is true, if any. // If there is no such item, return -1.
(In C++, methods similar to these are included as a standard part of the generic programming framework.)
The code for this exercises is pretty short, but it involves some advanced ideas, including methods with bounded type parameters (from Subsection 10.5.4). Aside from that, the main point of the exercise is to introduce predicates and show how they might be useful in generic programming. The operation of finding all the items in a collection that satisfy some condition is very common. The code to do it is not hard to write, but even so, it is nice to have it done once and for all. In this exercise, the condition that the items have to satisfy is represented as a Predicate. The collect() method provides a general way to find all the items that satisfy the condition. The items are dumped into a collection, which can then be processed further if necessary. If I wanted to carry this generic programming thing even further, I would define another interface:
public interface Processor<T> {
public void process( T obj );
}
and define a generic method for applying a Processor object to each item in a collection. With Predicates and Processors in hand, it would hardly ever be necessary to write a loop for iterating through all the items in a collection.
The implementation of the collect() method simply uses a for-each loop to go through the collection, coll, and puts every item that satisfies the predicate into a list. The method returns an object of type List, but List is only an interface. Any real list must belong to one of the classes that implement this interface, such as LinkedList or ArrayList. I create the list as an ArrayList, but a LinkedList would also be reasonable. (Perhaps the return type of the method should have been specified as ArrayList rather than List so that users of the method would know exactly what they are getting.)
/**
* Return a List that contains all the objects, obj, from the collection,
* coll, for which pred.test(obj) is true.
*/
public static <T> List<T> collect(Collection<T> coll, Predicate<T> pred) {
List<T> list = new ArrayList<T>();
for ( T item : coll ) {
if (pred.test(item))
list.add(item);
}
return list;
} // end collect()
The remove() and retain() methods are similar to collect(), except that instead of making a new collection, they modify the collection, coll. A for-each loop cannot modify the collection over which it is iterating, so the remove() and retain() methods will have to use Iterators. Recall that if iter is an Iterator for a collection, then the method iter.remove() will remove from the collection the item that was seen most recently by the iterator. The remove() method can be written as:
/**
* Remove every object, obj, from coll for which pred.test(obj) is true.
*/
public static <T> void remove(Collection<T> coll, Predicate<T> pred) {
Iterator<T> iter = coll.iterator();
while (iter.hasNext()) {
T item = iter.next();
if (pred.test(item))
iter.remove();
}
} // end remove()
The retain() method is almost identical to this, and the find() method is easy to write using an ordinary for loop. See my solution, below.
My test program simply creates some collections and applies the methods from the Predicates class to them. My collections contain objects of type Integer and I made two Predicates that work on objects of this type. To define such a predicate, we need a class that implements the interface Predicate<Integer>, and then we have to make an object belonging to that class. For example, I define the class:
/**
* An object of type Even tests an Object of type Integer to see whether the
* integer that it represents is an even number. Note that the test() method
* should only be applied to non-null values of type Integer.
*/
static class Even implements Predicate<Integer> {
public boolean test(Integer i) {
if ( i % 2 == 0 )
return true;
else
return false;
}
} // end class Even
The predicate object is then created with a command:
Predicate<Integer> pred = new Even():
A predicate object belonging to class Even will throw an exception if its test() method is applied to a null value. If this class were meant for more general use, it might be better to define test() so that it simply returns the answer "false" in this cases:
/** * An object of type Even tests an Object of type Integer to see whether the * integer that it represents is an even number. When applied to a null * object, the test returns the value false. */ static class Even implements Predicate<Integer> { public boolean test(Integer i) { if (i == null) return false; else if ( i % 2 == 0 ) return true; else return false; } } // end class Even
Note that a Predicate is an object, but we are really only interested in the test() method of the object. In some languages, including C++, it is possible to pass a function as a parameter to another function. In those languages, predicates are simply functions that return boolean values, and working with predicates does not require the overhead of making classes and objects. Of course, things are not so bad in Java if you make use of an anonymous nested class to define the predicate. In fact, you can define the predicate right in the function call where you need it. For example:
result = Predicates.collect( coll,
new Predicate<Integer>() {
public boolean test(Integer i) {
return (i != null && i > 100);
}
} );
The Predicate interface must be defined:
interface Predicate<T> {
public boolean test( T obj );
}
The Predicates class:
import java.util.*;
/**
* This class defines some static methods for working
* with Collections and Predicates. (The Predicate
* interface is NOT a standard part of Java.)
*/
public class Predicates {
/**
* Remove every object, obj, from coll for which pred.test(obj) is true.
*/
public static <T> void remove(Collection<T> coll, Predicate<T> pred) {
Iterator<T> iter = coll.iterator();
while (iter.hasNext()) {
T item = iter.next();
if (pred.test(item))
iter.remove();
}
} // end remove()
/**
* Remove every object, obj, from coll for which pred.test(obj) is false.
* (That is, retain the objects for which the predicate is true.)
*/
public static <T> void retain(Collection<T> coll, Predicate<T> pred){
Iterator<T> iter = coll.iterator();
while (iter.hasNext()) {
T item = iter.next();
if ( ! pred.test(item) )
iter.remove();
}
} // end retain()
/**
* Return a List that contains all the objects, obj, from the collection,
* coll, for which pred.test(obj) is true.
*/
public static <T> List<T> collect(Collection<T> coll, Predicate<T> pred) {
List<T> list = new ArrayList<T>();
for ( T item : coll ) {
if (pred.test(item))
list.add(item);
}
return list;
} // end collect()
/**
* Return the index of the first item in list for which the predicate is true, if any.
* If there is no such item, return -1.
*/
public static <T> int find(ArrayList<T> list, Predicate<T> pred) {
//
for (int i = 0; i < list.size(); i++) {
T item = list.get(i);
if (pred.test(item))
return i;
}
return -1;
} // end find()
} // end class Predicates
The Test program:
import java.util.*;
/**
* Perform some simple tests on the Predicates class.
*/
public class TestPred {
/**
* An object of type Even tests an Object of type Integer to see whether the
* integer that it represents is an even number. Note that the test() method
* should only be applied to non-null values of type Integer.
*/
static class Even implements Predicate<Integer> {
public boolean test(Integer i) {
if ( i % 2 == 0 )
return true;
else
return false;
}
} // end class Even
/**
* An object of type Big tests an Object of type Integer to see whether the
* integer that it represents is bigger than 100. Note that the test() method
* should only be applied to non-null values of type Integer.
*/
static class Big implements Predicate<Integer> {
public boolean test(Integer i) {
if ( i > 100 )
return true;
else
return false;
}
} // end class Big
/**
* For convenience make a Collection containing some integers. The Collection
* is actually a TreeSet, but that is not relevant to the main program.
*/
static Collection<Integer> makeSet() {
Collection<Integer> set = new TreeSet<Integer>();
set.add(new Integer(32));
set.add(new Integer(17));
set.add(new Integer(142));
set.add(new Integer(56));
set.add(new Integer(1899));
set.add(new Integer(57));
set.add(new Integer(999));
set.add(new Integer(86));
set.add(new Integer(83));
set.add(new Integer(100));
return set;
} // end makeSet()
/**
* Main routine tests the Predicates class by making Collections of Integers
* and applying the methods from the Predicates class to them.
*/
public static void main(String[] args) {
Collection<Integer> coll; // A collection (from makeSet() method).
List<Integer> result; // The result of applying collect() to coll.
Predicate<Integer> pred = new Even(); // Tests if an Integer is even.
coll = makeSet();
System.out.println("Original collection: " + coll);
Predicates.remove(coll,pred);
System.out.println("Remove evens: " + coll);
coll = makeSet();
Predicates.retain(coll,pred);
System.out.println("Retain evens: " + coll);
coll = makeSet();
result = Predicates.collect(coll,pred);
System.out.println("Collect evens: " + result);
ArrayList<Integer> list = new ArrayList<Integer>(coll);
int i = Predicates.find(list,pred);
System.out.println("Find first even: at index " + i);
pred = new Big(); // Tests if an Integer is bigger than 100.
coll = makeSet();
System.out.println("Original collection: " + coll);
Predicates.remove(coll,pred);
System.out.println("Remove big: " + coll);
coll = makeSet();
Predicates.retain(coll,pred);
System.out.println("Retain big: " + coll);
coll = makeSet();
result = Predicates.collect(coll,pred);
System.out.println("Collect big: " + result);
list = new ArrayList<Integer>(coll);
i = Predicates.find(list,pred);
System.out.println("Find first big: at index " + i);
} // end main()
} // end class TestPred