Solution for Programming 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. Java has the parameterized functional interface Predicate<T>, from package java.util.function, to represent predicates. The definition of Predicate<T> could be:
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. Java already has some methods that use predicates, such as the removeIf(p) method that is defined for any Collection. (See Subsection 10.6.1). However, this exercise asks you to write a few similar methods yourself. 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. You should not use the stream API for this exercise.
public static <T> void remove(Collection<T> coll, Predicate<T> pred) // Remove every object, obj, from coll for which pred.test(obj) // is true. (This does the same thing as coll.removeIf(pred).) 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.
The code for this exercise is pretty short, but it involves some advanced ideas, including writing generic methods (from Subsection 10.5.2). Aside from that, the main point of the exercise is to work with predicates and to see how they are 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, in this case, are to be dumped into a List.
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.
/**
* 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.
If you look at the documentation for Predicate<T>, you will see that it defines a method negate(). (It is defined in the interface as a default method. A functional interface can only define one abstract method, but it can define additional methods if they are default methods.) If pred is a predicate, then pred.negate() is a predicate that is true when pred is false and is false when pred is true. This means that retain() could actually be defined simply as
public static <T> void retain(Collection<T> coll, Predicate<T> pred) {
remove( coll, pred.negate() );
}
My test program 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. One way to create such a predicate is to write a class that implements the interface Predicate<Integer>, and then to make an object belonging to that class. For example, I could have defined 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 could then created with a command:
Predicate<Integer> pred = new Even():
But of course, it is also possible to define the predicate more simply as a lambda expression:
Predicate<Integer> pred = i -> (i % 2 == 0);
or, of course, we could simply use the lambda expression at the point where the predicate is needed. For example:
result = Predicates.collect(coll, i -> (i % 2 == 0) )
I hope that you can see how using the lambda expression simplifies the code quite a bit!
The Predicates Class:
import java.util.Collection;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Predicate;
/**
* 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.*;
import java.util.function.Predicate;
/**
* Perform some simple tests on the Predicates class.
*/
public class TestPredicates {
/**
* 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(Integer.valueOf(32));
set.add(Integer.valueOf(17));
set.add(Integer.valueOf(142));
set.add(Integer.valueOf(56));
set.add(Integer.valueOf(1899));
set.add(Integer.valueOf(57));
set.add(Integer.valueOf(999));
set.add(Integer.valueOf(86));
set.add(Integer.valueOf(83));
set.add(Integer.valueOf(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 = i -> (i % 2 == 0); // 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>();
int i = Predicates.find(list,pred);
System.out.println("Find first even: at index " + i);
pred = n -> (n > 100); // 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 TestPredicates