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 Even
The 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 void test(Object obj) {
return ((Integer)obj).integerValue() > 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
]
