Lab #4: The Comparator interface and inner classes

Assigned: Mon 23 Feb 04
Due: Mon 1 Mar 04

Background on comparison interfaces

Many programming tasks require different objects to be compared with each other in some way: we have already seen examples involving sorting and binary search where the ability to compare objects is crucial. In both cases we used the Comparable interface to facilitate comparison: a class whose objects will need to be compared implements this interface and thus must supply a compareTo method which we can depend on to be there (i.e., if something is a Comparable, we know it will have the method).

But it was understood fairly early in the evolution of Java's libraries that this is not enough for every situation. In many cases, the same objects must be compared at different times by different criteria. For example, we might need to compare books or CDs by title at one time, by price at another and by author (or artist) at yet another time, say to sort these same items by different criteria. This is where the Comparator interface comes into play.

Java's original Comparable interface follows a typical object-oriented pattern: we call one object's compareTo method with the other object as a parameter. But the Comparator interface takes a different tack: an object that implements this interface is in some sense independent of any particular object. That is to say, the notion of comparison itself is realized as a separate object, one which holds a single compare method, which can then be used to compare two objects passed as parameters to the method. In this way, the new interface makes it possible to compare the same objects by different criteria: each notion of comparison is realized as a separate object implementing the Comparator interface.

Technically, the Comparator interface is contained in the java.util library, and looks like this:

public interface Comparator
   int compare(Object object1, Object object2);
The sort routines in the java.util.Arrays package will allow you to sort an array based on a comparator object; see these documents at Sun's java site for usage (note that binary search routines are also kept here).

Composition (or "association") versus inheritance

Another issue which has evolved along with the Java language concerns "best design practices". Early Java design practices encouraged the use of inheritance as a means of solving many problems, sometimes to the detriment of the design. Many of the problems of over-use of inheritance in Java stem from the fact that Java supports only single inheritance, rather than multiple inheritance. That is, a class in Java can be a direct sub-class of only one super-class (some other languages allow multiple super-classes).

How do we "register" the fact that a class implements a number of different behaviors in Java? The right way is often to use interfaces, and we have learned this semester how to do this to good effect. However, there are other kinds of relationships that we may need to encode, such as "part-whole" relationships, which are best represented neither with inheritance nor with interfaces, but by using a third technique, called composition (or sometimes also association). The idea is that we can represent an object as being composed from several sub-objects, not in the sense of sub-classes, but in the sense of a whole built from parts. This is done by maintaining references (object variables) in a class which refer to the objects which represent their parts. For example, a car might be built from a body, four wheels, a trunk, etc. The relationship between the whole and the parts can be thought of as a "has-a" relationship (a car "has a" body) rather than an "is-a" relationship (a car "is a" vehicle): "is-a" relationships are better represented via inheritance or interface implementation. Another useful perspective here is that the parts are "associated with" the whole, or perhaps that several "equals" are associated with each other (e.g., partners in a relationship). This perspective emphasizes the possibility that the relationships might be construed as running in both directions, i.e., that the two objects might refer to each other (take care in this case; see below).

One reason to prefer compositional (or associational) representation is that it allows dynamic changes in relationships which is not possible in a static inheritance hierarchy, at least in Java. (Recall that static properties are those which can be verified at compile-time, by looking at the program text, while dynamic properties are those which change more fluidly at run-time, depending on the behavior of the program as it runs.) This flexibility makes sense in many situations in which we are modeling relationships between real objects or entities in the real world, since these often change dynamically over time. It also highlights why some care must be taken, however, when we represent relationships symmetrically with references in both directions: we must be sure to update both references when we break or change a relationship between objects, or we may end up with an inconsistent system (e.g., the car "thinks" it has a new wheel, but the old wheel "thinks" it is still on the car).

The structure of pizza

What does all this have to do with pizza?? Well, we want to use pizzas as a foil for working out some of these issues, and specifically to explore the idea of complex comparison criteria. The idea is that we can often express the criteria for preference of one pizza over another in terms of our preferences for different aspects (size, crust type, presence or absence of certain toppings, etc.). Furthermore, these preferences are sometimes organized into hierarchies, so that one person might prefer a thin-crust pizza over a thick-crust one, and this might be more important to them than which toppings the pizza has. Another person might prefer certain toppings, but as long as those criteria are satisfied, might then defer to preferring a larger pizza, or a square one versus round one, etc. In Java, we can represent each person's preferences as a Comparator object,

For the purposes of the assignment, I will lay out a general pizza structure and give some hints about how it might be represented in terms of Java structures, but I will expect different students to make different implementation choices. I will also give some specific pizza-comparison criteria: these criteria will be construed as the preferences of named people, so that we can more easily refer to them here and in discussion (not that a person should be reduced to their pizza preferences any more than they should be reduced to a number ...). You will then be charged with defining a list of pizzas and choosing a "best pizza" from among the list according to a certain ranking algorithm described below. (You may define any pizzas you wish into your list, but you should be able to add a new pizza (or a new person) easily during your demo.) The actual algorithm for choosing a pizza will have its drawbacks, but has the practical benefit of being well-defined (unlike many algorithms actually used at dorm parties) and also the pedagogical benefit of using sorting and search methods.

The "pizza features" we will focus on are these:

Here is some advice about possible representations of these pizza features in Java:

Here are some sample "people" (really, pizza preferences personified) which you should include in your program. You should also implement at least one other pizza comparator, namely one representing your own personal preferences in pizza.

You may of course add to this list if you wish, but you should include at least preferences (i.e., Comparator objects) for all of these and yourself.

Pizza ranking and choice algorithm

So, given the structure of a pizza and the preferences espoused by our hungry crowd of party-goers, how shall we decide on a pizza to order? We will assume as mentioned above that we have a certain list of candidates (perhaps these represent some list of weekly specials at Lefty's). We will then sort this list of candidates separately according to the criteria of each person, and give each pizza a "score" based on that person's rankings. A given pizza scores "n" if it is first on a person's list, "n-1" if it is second, and so on, down to a score of "1" if it is last on their list (in other words, bigger numbers are better scores). A pizza will accumulate scores from among all the people involved to achieve a total score, i.e., the sum of its individual scores for each person. Finally, we will sort the pizzas by score and report them from highest to lowest score, showing the scores along with the pizzas (this might allow us to choose a couple to order from the top of the list).

Realistically, this is not a very good choice algorithm: it ignores the difference between strict criteria (such as Alicia's vegan diet) and "looser" ones (such as Catelin's flexibility). The whole notion of score is rather unjustified in terms of numeric significance (why "n" versus "1"?). And the ranking notion ignores the fact that pizzas which compare equal by one person's criteria will nevertheless be placed in different positions in the sorted list, and thus receive different scores, despite being "equal" in preference.

Well, hey, it's the best we could come up with in the heat of the party!

On the other hand, it leads to a fairly clear implementation strategy, and one that takes good advantage of prior work in the class. More specifically, you could proceed as follows:

Note that a binary search based on an incomplete preference will not be accurate as far as the actual rank of the pizza on the list. For example, Catelin's criteria will tend to consider many pizzas the same, since she won't have a preference either way. But perhaps this "feature" of the algorithm will help off-set the other problem identified above where similar pizzas are nevertheless forced into an arbitrary rank order.

Assignment summary

Your assignment is thus as follows:

You should make your own design decisions about class structure, although of course I will be available for help and discussion, and also design your own graphical or command-line interface. But please try to take the following issues into account:

Dynamic data criterion: rather than "baking" a specific set of pizzas and people into your code, it would be nice if you could read the information in from a file. At the least, it would be nice if you could put people and pizza descriptions into their own files, separate from the rest of the algorithm, so that you can easily add to or modify the input data (if you must use fixed-size arrays, at least use a variable for their size; use array lengths for loops bounds; etc.). For the pizzas, this is pretty straightforward, although I would recommend (1) putting the pizza shape first, since this will determine the cosntructor you want to call and (2) using a constructor which takes the (rest of the) string as an argument, since the constructor has easy access to all the parts which need to be filled in while parsing the string. Regarding people (who are really mostly their preferences), it's possible that you would implement each person as a separate class or sub-class, in which case they would naturally go in a separate file. But I think it is better to implement them as instances of a Person class, with a String name and a Comparator (as discussed in lab). In this case, reading a person's preferences in from a text file would be too hard: even designing a language which would describe the preferences would be a big task (much less parsing it). So you may "bake" in the people, just not the pizzas : ) .

Extensibility: try to consider how you might add new toppings, new pizza shapes (e.g., rectangles), new crust types, etc.

Using anonymous inner classes to create preferences

Speaking of people and their preferences, how do you create a person's preferences? The recommended approach here is to use anonymous inner classes, which sound worse than they are. The basic idea is that you can create a new Comprarator class (for example) on the fly, in the middle of code in another class. What will be in this anonymous, on-the-fly class? Well, for Comparator it will be just a compare method--the fact that it is so short is one reason why it makes sense to create it on the fly. The syntax is a bit odd, but looks like this, for example:

	// in the middle of initializing some people
	Person Jane = new Person("Jane", new Comparator() {
		public int compare(Object a, Object b) {
			... // code to compare a and b, as per Jane's prefs
		);	// note: this closes the constructor *method call* 
	... // next person, etc.

Reading in files (of pizzas)

If you have never used Java to read input data from a file, you may wish to take a look at the following sample file, which reads in tab-delimited input (as we will use in the assignment):

Many of you will have access to Professor Levenick's "" utility from last semester: this should serve fine to read in the data for this assignment (though you may still want to use the "tab-delimitation" code from the previous example. For those of you who don't have, you can find it here:
(Note: Professor Levenick cautions me that the version of the constructor for this class that takes an Applet as argument can behave somewhat erratically if the file being read is not in the same directory as the Applet code. In any case, proceed with caution ...)