 | How to Think Like a Computer Scientist source ref: ebookit.html |
 |
|
Chapter 13:Object-oriented programming
Chapter 13
Object-oriented programming
13.1 Decks, take two
In the previous chapter we defined a new type, Card to represent a playing card, and wrote several methods that operate on Cards. At the simplest level, this process demonstrates object-oriented programming, which is characterized by the construction and interaction of data objects that represent real-world objects, processes, computations, etc.
Also in the previous chapter, we used an array of Cards to represent a deck. This decision was not in line with object-oriented design, since a card and a deck are really different objects, with different operations. It makes more sense for decks to be an object type, too.
The to do that is to make a Deck class that contains the cards in an instance variable. To contain multiple objects of the same type, the obvious choice is an array of Cards. To make things confusing, I called the array cards:
public class Deck
{
Card[] cards;
public Deck (int length) {
cards = new Card [length];
}
}
As usual, the constructor initializes the instance variables. This example is different from some of the others we have looked at, though, where the parameters of the constructor contain values for the instance variables. Here, the parameter is the length of the array and we use the new command to create the array. Initially the elements of this array are null; there are no cards in the deck.
To build a fully-populated deck, we can write a second constructor that takes no arguments. It creates a standard 52-card deck and allocates 52 card objects to put in the deck.
public Deck () {
int index = 0;
cards = new Card [52];
for (int suit = 0; suit <= 3; suit++) {
for (int rank = 1; rank <= 13; rank++) {
cards[index] = new Card (suit, rank);
index++;
}
}
}
13.2 Deck methods
The next step is to look again at the methods we wrote in the last chapter and see if it makes sense to rewrite them as object methods in the Deck class, instead of class methods in the Card class. Some of them, like shuffle are clearly operations that act on decks and not cards. findCard is less clear-cut; there are at least three reasonable choices.
- Leave it as a class method in Card.
- Move it into Deck or make a copy in Deck. (It is possible to have identical class methods in multiple classes. Java always knows which one to invoke.)
- Write an object method in Card, called find, that takes a Deck as a parameter and an object method in Deck, called search, that takes a Card as a parameter.
The third option might be regarded as the most purely object-oriented design, since it is based on the model that objects are active entities that perform operations on themselves and other objects, rather than passive entities that get passed around as arguments. In one case you send a message to the card and tell it to find itself in the given deck. In the other case you send a message to a deck and tell it to search itself for a card.
The choices here are largely aesthetic, though. There are no performance advantages, and I don't find any of them significantly easier to write, debug or use. But thinking about the possibilities might give you a sense of what people mean when they talk about object-oriented style.
13.3 Subdecks and hands
A natural next question is, "How should we represent a hand (a small number of cards), or some other subset of a full deck?" Since hands are an important part of many card games, we might want to create a Hand class. There are many operations that apply to a Hand that do not make sense to apply to a Deck. For example, in bridge, you can evaluate a hand and give it a score (according to one of many systems) in order to determine your bid. For poker, you might want methods like isStraight and isFlush that would determine whether or not a hand contained a straight or a flush.
On the other hand, the representation of a Hand is likely to be identical to the representation of a Deck: an array of cards. Also, there are many operations that apply to both Decks and Hands. For our purposes, it is probably best to use the Deck class to represent a deck, a subdeck, or a hand.
This sort of decision, choosing a set of classes that form a natural and convenient model of the real world, is an important part of object-oriented design.
If we implement hands as small Deck objects, we might want a method, subdeck, that takes a Deck of any size and returns a new Deck that contains a subset of the cards, as specified by the bounds low and high:
public Deck subdeck (int low, int high) {
Deck d = new Deck (high-low+1);
for (int i = 0; i<d.cards.length; i++) {
d.cards[i] = cards[low+i];
}
return d;
}
To get the length of a Deck, you have to get the length of the array named cards: d.cards.length. The expression d.length is illegal because d is a Deck, not an array. That might be confusing because a Deck is represented as an array. Nevertheless, the type Deck and the type Card[] (array of cards) are not the same, and they do not support the same operations.
The length of the subdeck is high-low+1, because both the low card and high card are included. This sort of computation can be confusing, and lead to "off-by-one" errors. Drawing a picture is usually the best way to avoid them.
Notice that subdeck invokes the first form of the constructor, which creates the array but does not create any cards. As a result, the original deck and the subdeck share some cards. This is a form of aliasing, where more than one reference points to the same object.
The following is a state diagram of subdeck being created with the parameters low=3 and high=7. The result is a hand with 5 cards that are shared with the original deck (named this, since it is the current object in subdeck).
I have suggested that aliasing is not generally a good idea, since changes in one deck will be reflected in another, which is not the behavior you would expect from real cards and decks. But if the objects in question are immutable, then aliasing can be a reasonable choice. In this case, there is probably no reason ever to change the rank or suit of a card. Instead we will create each card once and then treat it as an immutable object.
13.4 Shuffling and dealing
In Section 12.8 I wrote pseudocode for a shuffling algorithm, and you may have written an implementation as a class method in the Card class. Now that Deck is a full-fledged class, it would be better to make shuffle an object method in the deck class.
You might give some thought about whether to write shuffle as a modifier or an operator. In other words, should it modify the deck on which it is invoked, by shuffling the references to cards, or should it create and return a new deck (albeit with references to the same old set of cards). I will assume that it is written as a modifier. Thus, the code to create and shuffle a deck would look like:
Deck d = new Deck ();
d.shuffle ();
To deal out several hands, we can use subdeck:
Deck hand1 = d.subdeck (0, 4);
Deck hand2 = d.subdeck (5, 9);
Deck pack = d.subdeck (10, 51);
This code puts the first 5 cards in one hand, the next 5 cards in the other, and the rest into the pack.
When you thought about dealing, did you think we should give out one card at a time to each player in the round-robin style that is typical in real card games? I thought about it, but then realized that it is unnecessary for a computer program. The round-robin convention is intended to mitigate imperfect shuffling and make it more difficult for the dealer to cheat. Neither of these is an issue for a computer.
This example is a useful reminder of one of the dangers of object-oriented thinking, and engineering metaphors in general: sometimes we impose restrictions on computers that are unnecessary, or expect capabilities that are lacking, because we unthinkingly extend a metaphor past its breaking point. Beware of misleading analogies.
13.5 Projects with more than one class
This is the first program we have looked at that contains more than one class. You might want to review Section 9.1 where it talks about the startup file. You can have more than one main method, one in each class definition. The startup file designates which one gets executed.
This feature can be useful for developing and debugging new classes. For example, while you are working on the Card class you can write test code in Card.main. Then when you are debugging Deck you can write Deck.main without having to remove Card.main.
This feature can also be confusing. Make sure that you always know which file is the startup file. Also, review Section 5.4, which talks about making sure you are really executing the code you think you are executing.
13.6 Mergesort
In Section 12.9, we saw a simple sorting algorithm that turns out not to be very efficient. In order to sort n items, it has to traverse the array n times, and each traversal takes an amount of time that is proportional to n. The total time, therefore, is proportional to n2.
In this section I will sketch a more efficient algorithm called mergesort. To sort n items, mergesort takes time proportional to n log n. That may not seem impressive, but as n gets big, the difference between n2 and n log n can be enormous. Try out a few values of n and see.
The basic idea behind mergesort is this: if you have two subdecks, each of which has been sorted, it is easy (and fast) to merge them into a single, sorted deck. Try this out with a deck of cards:
- Form two subdecks with about 10 cards each and sort them so that when they are face up the lowest cards are on top. Place both decks face up in front of you.
- Compare the top card from each deck and choose the lower one. Flip it over and add it to the merged deck.
- Repeat step two until one of the decks is empty. Then take the remaining cards and add them to the merged deck.
The result should be a single sorted deck. Here's what this looks like in pseudocode:
public static Deck merge (Deck d1, Deck d2) {
// create a new deck big enough for all the cards
Deck result = new Deck (d1.cards.length + d2.cards.length);
// use the index i to keep track of where we are in
// the first deck, and the index j for the second deck
int i = 0;
int j = 0;
// the index k traverses the result deck
for (int k = 0; k<result.cards.length; k++) {
// if d1 is empty, d2 wins; if d2 is empty, d1 wins;
// otherwise, compare the two cards
// add the winner to the new deck
}
return result;
}
The best way to test merge is to build and shuffle a deck, use subdeck to form two (small) hands, and then use the sort routine from the previous chapter to sort the two halves. Then you can pass the two halves to merge to see if it works.
If you can get that working, try a simple implementation of mergeSort:
public Deck mergeSort () {
// find the midpoint of the deck
// divide the deck into two subdecks
// sort the subdecks using the simple sort algorithm
// merge the two halves and return the result
}
Then, if you get that working, the real fun begins! The magical thing about mergesort is that it is recursive. At the point where you sort the subdecks, why should you invoke the old, slow version of sort? Why not invoke the spiffy new mergeSort you are in the process of writing?
Not only is that a good idea, it is necessary in order to achieve the performance advantage I promised. In order to make it work, though, you have to add a base case so that it doesn't recurse forever. A simple base case is a subdeck with 0 or 1 cards. If mergesort receives such a small subdeck, it can return it unmodified, since it is already sorted.
The recursive version of mergesort should look something like this:
public Deck mergeSort () {
// if the deck is 0 or 1 cards, return it
// find the midpoint of the deck
// divide the deck into two subdecks
// sort the subdecks using mergesort
// merge the two halves and return the result
}
As usual, there are two ways to think about recursive programs: you can think through the entire flow of execution, or you can make the "leap of faith." I have deliberately constructed this example to encourage you to make the leap of faith.
When you were using the old version of sort to sort the subdecks, you didn't feel compelled to follow the flow of execution, right? You just assumed that the sort method would work because it worked in the last chapter. Well, all you did to make mergeSort recursive was replace one sort algorithm with another. There is no reason to read the program differently.
Well, actually you have to give some thought to getting the base case right and making sure that you reach it eventually, but other than that, writing the recursive version should be no problem. Good luck!
13.7 Inheritance
The language feature that is most often associated with object-oriented programming is inheritance. Inheritance is the ability to define a new class that is a modified version of a previously-defined class (including built-in classes).
The primary advantage of this feature is that you can add new methods or instance variables to an existing class without modifying the existing class. This is particularly useful for built-in classes, since you can't modify them even if you want to.
The reason inheritance is called "inheritance" is that the new class inherits all the instance variables and methods of the existing class. Extending this metaphor, the existing class is sometimes called the parent class.
We have already seen one example of inheritance, in Section 4.8. The Circle class is based on the Frame class, as indicated by the first line of the class definition:
public class Circle extends Frame {
public static void paintBox
(Graphics g, int x, int y, int width, int height) {
// you put your code here
g.setColor (Color.black);
g.drawOval (x, y, width, height);
}
public static void main(String[] args) {
Circle c = new Circle (); // create a window
c.setSize (400, 400); // set its size
c.setBackground (Color.white); // set the background color
c.show (); // display the window
}
public void paint (Graphics g) {
Rectangle bbox = getBounds (); // find the window size
paintBox (g, 0, 0, bbox.width, bbox.height); // draw something!
}
}
The keyword extends indicates the parent class. If you look at the documentation of the Frame class, you will see all the methods that can be invoked on a Frame object. Since Circle extends Frame, you can also invoke any of these methods on a Circle.
That's why, in paint, we can invoke getBounds, which is an object method of the Frame class.
Looking at paint again, you might notice that it is an object method (since it lacks the keyword static). You might wonder, then, what object it gets invoked on. The answer is that it gets invoked on c, the Circle object you created in main. Then when you invoke getBounds, Java implicitly invokes it on the current object, which is c.
You might also wonder when the system invokes paint. The first time is when you invoke show in main. Then, any time the window needs to be redrawn, for example if the window is covered up and then revealed, Java invokes paint again, each time invoking it on the Circle object you created.
13.8 A less complicated example
It's probably good that you finally get to understand a piece of code I threw at you in Chapter 4. On the other hand, it is not the clearest example of inheritance. Let's look at a less complicated case where we extend a built-in class by adding a new method.
Specifically, we are going to take the existing Rectangle class and make it "drawable." That is, we are going to create a new class called DrawableRectangle that will have all the instance variables and methods of a Rectangle, plus an additional method called draw that will take a Graphics object as a parameter and draw the rectangle.
The class definition looks like this:
import java.awt.*;
public class DrawableRectangle extends Rectangle {
public void draw (Graphics g) {
g.drawRect (x, y, width, height);
}
}
Yes, that's really all there is in the whole class definition. The first line imports the java.awt package, which is where Rectangle is defined. The next line indicates that DrawableRectangle inherits from Rectangle. The rest is the definition of the draw method, which refers to the instance variables x, y, width and height. It might seem odd to refer to instance variables that don't appear in this class definition, but remember that they are inherited from the parent class.
To create and draw a DrawableRectangle, you could use the following:
public static void paintBox
(Graphics g, int x, int y, int width, int height) {
DrawableRectangle dr = new DrawableRectangle ();
dr.x = 10; dr.y = 10;
dr.width = 200; dr.height = 200;
dr.draw (g);
}
Again, it might seem odd to use the new command for a class that has no constructors. DrawableRectangle inherits the default constructor of its parent class, so there is no problem there.
We can set the instance variables of dr and invoke methods on it in the usual way. When we invoke draw, Java invokes the method we defined in DrawableRectangle. If we invoked grow or some other Rectangle method on dr, Java would know to use the method defined in the parent class.
13.9 The class hierarchy
In Java, all classes extend some other class. The most basic class is called Object. It contains no instance variables, but it does provide the methods equals and toString, among others.
Many classes extend Object, including most of the classes we have written (except Circle and DrawableRectangle) and many of the built-in classes, like Rectangle. Any class that does not explicitly name a parent inherits from Object by default.
Some inheritance chains are longer, though. Frame extends Window, which extends Container, which extends Component, which extends Object. No matter how long the chain, Object is the ultimate parent of all classes.
All the classes in Java can be organized into a "family tree" that is called the class hierarchy. Object usually appears at the top, with all the "child" classes below. If you look at the documentation of Frame, for example, you will see the part of the hierarchy that makes up Frame's pedigree.
13.10 Object-oriented design
Inheritance is a powerful feature. Some programs that would be complicated without inheritance can be written concisely and simply with it. Also, inheritance can facilitate code reuse, since you can customize the behavior of build-in classes without having to modify them.
On the other hand, inheritance can make programs difficult to read, since it is sometimes not clear, when a method is invoked, where to find the definition. For example, in a previous section, we invoked the getBounds method on a Circle object. Can you find the documentation for getBounds? It turns out that getBounds is defined in the parent of the parent of the parent of the parent of Circle.
Also, many of the things that can be done using inheritance can be done almost as elegantly (or more so) without it.
13.11 Programming languages and programming style
At various points in this book I have discussed three different programming styles (sometimes called paradigms): procedural, functional, and object-oriented. Although Java is usually thought of as an object-oriented language, it is possible to write Java programs in any style.
In fact, existing Java programs and the built-in Java packages are written in a mixture of these three styles. As you write more Java programs, and you learn to program in other languages, you will discover a style that works for you.
Recently object-oriented programming has become quite popular, and there are many people who claim that it is superior to other styles in various ways. I hope that by exposing you to a variety of styles I have given you the tools you need to understand and evaluate these claims.
13.12 Program development
I have also tried, in various places, to demonstrate a variety of styles of program development, including incremental changes, rough prototyping with correction, generalization, and planning using pseudocode.
Again, there are a lot of people with strong feelings about which of these is best, and there are specific cases where one or the other is clearly better. But again, your experiences as a programmer will guide you toward one style or another, or to some combination.
13.13 Glossary
- object-oriented:
- A style of programming or program design that is characterized by data objects that model real-world objects, and computations that are expressed in terms of the interaction of objects (rather than the processing of data).
- mergesort:
- An algorithm for sorting that recursively sorts two subsets and then merges the results into a single, sorted set.
- inheritance:
- A feature of many object-oriented languages in which a new class can inherit the instance variables and methods of an existing class without modifying the existing class.
- parent class:
- The existing class on which a new class is based. Sometimes called "base class."
- Object:
- The ultimate parent class from which all classes are descended, directly or indirectly.
 |
|
|