Composition (or "association") versus inheritance

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

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:

• Shape and "width"

  Our pizzas may be either square or round, and they have a single dimension, corresponding to either the length of a side (if square) or the diameter (not the radius!) if round. From these two criteria you should be able to compute the area of any pizza.

• Crust type

  Our pizzas may have thick, thin or stuffed crusts.

• Toppings

  Our pizzas may have any, all or none of the following toppings: anchovies, beef, cheese, ham, mushrooms, olives, peppers, tomatoes.

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

• Shape and "width"

  The different shapes of pizzas might be most easily represented as two different sub-classes of a general pizza class. The general class could be an abstract class which requires (but does not specify) a method for determining area (implemented differently for each sub-class).

• Crust type

  Since crust type is just a simple distinction, it might be represented in terms of a method call which returns a string or even an integer. A private member/field of the appropriate type could be included in the definition of the pizza class. The use of a private field and a method call prevents someone on the outside from changing the pizzas crust, either by accident or on purpose; this makes sense since it is unlikely that we need to model situations where pizzas change their crust type dynamically after they have been made.

• Toppings

  Probably the easiest way to represent a pizza's toppings is to use the old trick of using an array of booleans to represent a set: each position in the array represents a fixed topping type, and the boolean entry in the array tells whether this pizza has that item or not. SInce it is possible that a pizza's toppings might change over time (well, more so than crust type or shape), we can implement this by way of a reference to an associated Toppings object. In other words, define a separate Toppings class which holds an array of the appropriate kind and perhaps even implements such methods as hasBeef(), hasOlives(), etc.

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.

• Alicia

  Alicia is a vegan, so her main criteria are that pizzas have no meat or cheese, but if pressed, she would say that beef, ham, anchovies and cheese are the worst offenders, in that order (i.e., she would prefer a pizza with no beef to one with beef, etc.). Beyond that, she feels that round pizzas better reflect the cyclic nature of the cosmos, so she prefers round to square ones. She has no preference on crust type.
  (Fritz is mean to vegans … )

• Bobby

  Bobby is on a low-carb diet, so he first of all prefers a thin crust pizza to a stuffed crust one to a thick crust one. Beyond that, he always prefers pizzas of smaller overall area (less carbs, after all), and he has a special dis-like for anchovies.

• Catelin

  Catelin is pretty easy-going about her pizza: she hates anchovies, though, so she prefers any pizza without them to any that has them. She does like a stuffed crust, so if the anchovies are not an issue (i.e., if two pizzas are the same on that score), she'll prefer the one with a stuffed crust.

• Darryl

  Darryl has a big appetite and makes no bones about it: he prefers a pizza with a larger area first and foremost, then one with a greater number of toppings (it doesn't matter what they are), and finally prefers stuffed to thick to thin crusts, in that order.

• Eleanor

  Eleanor hails from Chicago, where they like their pizzas square, and thick-crusted next (no preference for stuffed versus thin). She likes olives and peppers equally over any other toppings (i.e., she'll prefer any pizza with these over any that lacks them, and especially likes pizzas with both).

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:

• Loop through each person, re-sorting the list of pizzas by their criteria;

• Once the list is sorted for a given person, loop through each pizza and have it locate itself on the list by binary search (possible problem here, note below), adding in its rank-based score to a running total kept in the pizza object;

• After all people have been accounted for, re-sort the list of pizzas according to their total accumulated score, and print the results.

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

• define a class structure (abstract classes, regular classes, methods, private fields, interfaces) which implement pizzas, pizza sub-types, crust types, topping sets and (most importantly) the comparator objects representing different people's preferences about pizzas;

• define a list of pizzas to be compared and ranked, preferably not a fixed list, but one which you can change "externally" (see below);

• define the individual people/comparator objects to be used to rank the pizzas;

• run the ranking algorithm and print out the sorted list of pizzas with their scores (it might be good to print out individual people's rank lists, too, so that you can tell that the algorithm is working properly).

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):