Solution for
Programming Exercise 12.4
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to the following exercise from this on-line Java textbook.
Exercise 12.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 use "predicate objects" by defining an interface:
public interface Predicate { public boolean test(Object obj); }The idea is that an object that implements this interface knows how to "test" objects in some way. Define a class Predicates that contains the following generic methods for working with predicate objects:
public static void remove(Collection coll, Predicate pred) // Remove every object, obj, from coll for which // pred.test(obj) is true. public static void retain(Collection coll, Predicate 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 List collect(Collection coll, Predicate pred) // Return a List that contains all the objects, obj, // from the collection, coll, such that pred.test(obj) // is true. public static int find(ArrayList list, Predicate 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.)
Discussion
This exercises is not particularly difficult, but the concepts are new. 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 { public void process(Object 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 an Iterator 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 specifiedas ArrayList rather than List so that users of the method would know exactly what they are getting.)
public static List collect(Collection coll, Predicate pred) { // Return a List that contains all the objects, obj, // from the collection, coll, such that pred.test(obj) // is true. List list = new ArrayList(); Iterator iter = coll.iterator(); while (iter.hasNext()) { Object item = iter.next(); 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. These methods use the fact 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. You can check the source code for these methods, as well as for find(), in 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 a predicate, we need a class that implements the Predicate interface, and then we have to make an object belonging to that class. For example, I define the class:
static class Even implements Predicate { // 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. public boolean test(Object obj) { Integer i = (Integer)obj; if ( i.intValue() % 2 == 0 ) return true; else return false; } } // end class EvenThe predicate object is then created with a command:
Predicate pred = new Even():A predicate object belonging to class Even will throw an exception if its test() method is applied to a null value or to an object that is not of type Integer. 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 these cases:
static class BetterEven implements Predicate { // An object of type BetterEven tests a value // to see whether it is an object of type // Integer that contains an even integer. // In all other cases, the answer is false. public boolean test(Object obj) { if (obj == null) return false; if ( ! obj instanceof Integer ) return false; Integer i = (Integer)obj; if ( i.intValue() % 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() { public boolean test(Object obj) { return ((Integer)obj).intValue() > 100; } } );
The Solution
The Predicate Interface must be defined: public interface Predicate { public boolean test(Object obj); } The Predicates Class: import java.util.*; public class Predicates { // This class defines some static methods for working // with Collections and Predicates. (The Predicate // interface is NOT a standard part of Java.) public static void remove(Collection coll, Predicate pred) { // Remove every object, obj, from coll for which // pred.test(obj) is true. Iterator iter = coll.iterator(); while (iter.hasNext()) { Object item = iter.next(); if (pred.test(item)) iter.remove(); } } // end remove() public static void retain(Collection coll, Predicate 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.) Iterator iter = coll.iterator(); while (iter.hasNext()) { Object item = iter.next(); if ( ! pred.test(item) ) iter.remove(); } } // end retain() public static List collect(Collection coll, Predicate pred) { // Return a List that contains all the objects, obj, // from the collection, coll, such that pred.test(obj) // is true. List list = new ArrayList(); Iterator iter = coll.iterator(); while (iter.hasNext()) { Object item = iter.next(); if (pred.test(item)) list.add(item); } return list; } // end collect() public static int find(ArrayList list, Predicate 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. for (int i = 0; i < list.size(); i++) { Object item = list.get(i); if (pred.test(item)) return i; } return -1; } // end find() } // end class Predicates Main Program for Testing the Class: import java.util.*; public class testpred { static class Even implements Predicate { // 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. public boolean test(Object obj) { Integer i = (Integer)obj; if ( i.intValue() % 2 == 0 ) return true; else return false; } } // end class Even static class Big implements Predicate { // 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. public boolean test(Object obj) { Integer i = (Integer)obj; if ( i.intValue() > 100 ) return true; else return false; } } // end class Big static Collection makeSet() { // For convenience make a Collection containing // some integers. The Collection is actually a // TreeSet, but that is not relevant to the main // program. Collection set = new TreeSet(); 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() public static void main(String[] args) { // Main routine tests the Predicates class by // making Collections of Integers and applying // the methods from the Predicates class to them. Collection coll; // A collection (from makeSet() method). Collection result; // The result of applying one of the // methods from class Predicates to coll. Predicate 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 list = new ArrayList(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(coll); i = Predicates.find(list,pred); System.out.println("Find first big: at index " + i); } // end main() } // end class testpred
[ Exercises | Chapter Index | Main Index ]