|How to Think Like a Computer Scientist|
source ref: ebookit.html
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:
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.
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.
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.
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:
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.
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:
To deal out several hands, we can use subdeck:
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.
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.
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:
The result should be a single sorted deck. Here's what this looks like in pseudocode:
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:
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:
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!
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:
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.
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:
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:
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.
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.
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.
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.
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.