text:
The Way of the Java/Arrays of Objects

Composition
composition nested structure

By now we have seen several examples of composition (the ability to combine language features in a variety of arrangements). One of the first examples we saw was using a method invocation as part of an expression. Another example is the nested structure of statements: you can put an if statement within a while loop, or within another if statement, etc.

Having seen this pattern, and having learned about arrays and objects, you should not be surprised to learn that you can have arrays of objects. In fact, you can also have objects that contain arrays (as instance variables); you can have arrays that contain arrays; you can have objects that contain objects, and so on.

In the next two chapters we will look at some examples of these combinations, using Card objects as an example.

Card objects Card class!Card

If you are not familiar with common playing cards, now would be a good time to get a deck, or else this chapter might not make much sense. There are 52 cards in a deck, each of which belongs to one of four suits and one of 13 ranks. The suits are Spades, Hearts, Diamonds and Clubs (in descending order in Bridge). The ranks are Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen and King. Depending on what game you are playing, the rank of the Ace may be higher than King or lower than 2.

rank suit

If we want to define a new object to represent a playing card, it is pretty obvious what the instance variables should be: rank and suit. It is not as obvious what type the instance variables should be. One possibility is Strings, containing things like "Spade" for suits and "Queen" for ranks. One problem with this implementation is that it would not be easy to compare cards to see which had higher rank or suit.

encode encrypt map to

An alternative is to use integers to encode the ranks and suits. By ``encode,'' I do not mean what some people think, which is to encrypt, or translate into a secret code. What a computer scientist means by ``encode'' is something like ``define a mapping between a sequence of numbers and the things I want to represent.'' For example,

tabularl c l

Hearts & & 2 Diamonds & & 1 Clubs & & 0 tabular

The obvious feature of this mapping is that the suits map to integers in order, so we can compare suits by comparing integers. The mapping for ranks is fairly obvious; each of the numerical ranks maps to the corresponding integer, and for face cards:

tabularl c l

Queen & & 12 King & & 13 tabular

that they are not part of the Java program. They are part of the program design, but they never appear explicitly in the code. The class definition for the Card type looks like this:

verbatim class Card

int suit, rank;

public Card this.suit = 0; this.rank = 0;

public Card (int suit, int rank) this.suit = suit; this.rank = rank;

verbatim

As usual, I am providing two constructors, one of which takes a parameter for each instance variable and the other of which takes no parameters.

constructor

To create an object that represents the 3 of Clubs, we would use the new command:

verbatim Card threeOfClubs = new Card (0, 3); verbatim

The first argument, 0 represents the suit Clubs.

The printCard method
printCard print!Card

When you create a new class, the first step is usually to declare the instance variables and write constructors. The second step is often to write the standard methods that every object should have, including one that prints the object, and one or two that compare objects. I will start with printCard.

String!array of array!of String

In order to print Card objects in a way that humans can read easily, we want to map the integer codes onto words. A natural way to do that is with an array of Strings. You can create an array of Strings the same way you create an array of primitive types:

verbatim String[] suits = new String [4]; verbatim

Then we can set the values of the elements of the array.

verbatim suits[0] = "Clubs"; suits[1] = "Diamonds"; suits[2] = "Hearts"; suits[3] = "Spades"; verbatim

Creating an array and initializing the elements is such a common operation that Java provides a special syntax for it:

verbatim String[] suits = "Clubs", "Diamonds", "Hearts", "Spades" ; verbatim

The effect of this statement is identical to that of the separate declaration, allocation, and assignment. A state diagram of this array might look like:

state diagram

figure=figs/stringarray.eps

reference String!reference to

The elements of the array are references to the Strings, rather than Strings themselves. This is true of all arrays of objects, as I will discuss in more detail later. For now, all we need is another array of Strings to decode the ranks:

verbatim String[] ranks = "narf", "Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King" ; verbatim

The reason for the "narf" is to act as a place-keeper for the zeroeth element of the array, which will never be used. The only valid ranks are 1--13. This wasted entry is not necessary, of course. We could have started at 0, as usual, but it is best to encode 2 as 2, and 3 as 3, etc.

Using these arrays, we can select the appropriate Strings by using the suit and rank as indices. In the method printCard,

verbatim public static void printCard (Card c)    String[] suits =  "Clubs", "Diamonds", "Hearts", "Spades" ; String[] ranks = "narf", "Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King" ;

System.out.println (ranks[c.rank] + " of " + suits[c.suit]);

verbatim

the expression suits[c.suit] means ``use the instance variable suit from the object c as an index into the array named suits, and select the appropriate string.'' The output of this code

verbatim Card card = new Card (1, 11); printCard (card); verbatim

is Jack of Diamonds.

The sameCard method sameCard

The word ``same'' is one of those things that occur in natural language that seem perfectly clear until you give it some thought, and then you realize there is more to it than you expected.

ambiguity natural language language!

For example, if I say ``Chris and I have the same car,'' I mean that his car and mine are the same make and model, but they are two different cars. If I say ``Chris and I have the same mother,'' I mean that his mother and mine are one and the same. So the idea of ``sameness'' is different depending on the context.

When you talk about objects, there is a similar ambiguity. For example, if two Cards are the same, does that mean they contain the same data (rank and suit), or they are actually the same Card object?

To see if two references refer to the same object, we can use the == operator. For example:

verbatim Card card1 = new Card (1, 11); Card card2 = card1;

if (card1 == card2) System.out.println ("card1 and card2 are the same object."); verbatim

This type of equality is called shallow equality because it only compares the references, not the contents of the objects.

equality identity shallow equality deep equality

To compare the contents of the objects---deep equality---it is common to write a method with a name like sameCard.

verbatim public static boolean sameCard (Card c1, Card c2) return (c1.suit == c2.suit && c1.rank == c2.rank);

verbatim

Now if we create two different objects that contain the same data, we can use sameCard to see if they represent the same card:

verbatim Card card1 = new Card (1, 11); Card card2 = new Card (1, 11);

if (sameCard (card1, card2)) System.out.println ("card1 and card2 are the same card."); verbatim

In this case, card1 and card2 are two different objects that contain the same data

figure=figs/card.eps

so the condition is true. What does the state diagram look like when card1 == card2 is true?

aliasing

In Section incomparable I said that you should never use the == operator on Strings because it does not do what you expect. Instead of comparing the contents of the String (deep equality), it checks whether the two Strings are the same object (shallow equality).

The compareCard method
compareCard operator!conditional conditional operator

For primitive types, there are conditional operators that compare values and determine when one is greater or less than another. These operators ( and the others) don't work for object types. For Strings there is a built-in compareTo method. For Cards we have to write our own, which we will call compareCard. Later, we will use this method to sort a deck of cards.

ordering complete ordering partial ordering

Some sets are completely ordered, which means that you can compare any two elements and tell which is bigger. For example, the integers and the floating-point numbers are totally ordered. Some sets are unordered, which means that there is no meaningful way to say that one element is bigger than another. For example, the fruits are unordered, which is why we cannot compare apples and oranges. In Java, the boolean type is unordered; we cannot say that true is greater than false.

The set of playing cards is partially ordered, which means that sometimes we can compare cards and sometimes not. For example, I know that the 3 of Clubs is higher than the 2 of Clubs, and the 3 of Diamonds is higher than the 3 of Clubs. But which is better, the 3 of Clubs or the 2 of Diamonds? One has a higher rank, but the other has a higher suit.

comparable

In order to make cards comparable, we have to decide which is more important, rank or suit. To be honest, the choice is completely arbitrary. For the sake of choosing, I will say that suit is more important, because when you buy a new deck of cards, it comes sorted with all the Clubs together, followed by all the Diamonds, and so on.

With that decided, we can write compareCard. It will take two Cards as parameters and return 1 if the first card wins, -1 if the second card wins, and 0 if they tie (indicating deep equality). It is sometimes confusing to keep those return values straight, but they are pretty standard for comparison methods.

First we compare the suits:

verbatim if (c1.suit > c2.suit) return 1; if (c1.suit < c2.suit) return -1; verbatim

If neither statement is true, then the suits must be equal, and we have to compare ranks:

verbatim if (c1.rank > c2.rank) return 1; if (c1.rank < c2.rank) return -1; verbatim

If neither of these is true, the ranks must be equal, so we return 0. In this ordering, aces will appear lower than deuces (2s).

As an exercise, fix it so that aces are ranked higher than Kings, and encapsulate this code in a method.

Arrays of cards
array!of object object!array of deck

The reason I chose Cards as the objects for this chapter is that there is an obvious use for an array of cards---a deck. Here is some code that creates a new deck of 52 cards:

verbatim Card[] deck = new Card [52]; verbatim

Here is the state diagram for this object:

state diagram

figure=figs/cardarray.eps

The important thing to see here is that the array contains only references to objects; it does not contain any Card objects. The values of the array elements are initialized to null. You can access the elements of the array in the usual way:

verbatim if (deck[3] == null) System.out.println ("No cards yet!"); verbatim

But if you try to access the instance variables of the non-existent Cards, you will get a NullPointerException.

exception!NullPointer run-time error null

verbatim deck[2].rank;            // NullPointerException verbatim

Nevertheless, that is the correct syntax for accessing the rank of the ``twoeth'' card in the deck (really the third---we started at zero, remember?). This is another example of composition, the combination of the syntax for accessing an element of an array and an instance variable of an object.

composition loop!nested

The easiest way to populate the deck with Card objects is to write a nested loop:

verbatim int index = 0; for (int suit = 0; suit <= 3; suit++) for (int rank = 1; rank <= 13; rank++) deck[index] = new Card (suit, rank); index++; verbatim

The outer loop enumerates the suits, from 0 to 3. For each suit, the inner loop enumerates the ranks, from 1 to 13. Since the outer loop iterates 4 times, and the inner loop iterates 13 times, the total number of times the body is executed is 52 (13 times 4).

index

I used the variable index to keep track of where in the deck the next card should go. The following state diagram shows what the deck looks like after the first two cards have been allocated:

figure=figs/cardarray2.eps

As an exercise, encapsulate this deck-building code in a method called buildDeck that takes no parameters and that returns a fully-populated array of Cards.

encapsulation

The printDeck method
printdeck printDeck print!array of Cards

Whenever you are working with arrays, it is convenient to have a method that will print the contents of the array. We have seen the pattern for traversing an array several times, so the following method should be familiar:

verbatim public static void printDeck (Card[] deck) for (int i=0; i<deck.length; i++) printCard (deck[i]); verbatim

Since deck has type Card[], an element of deck has type Card. Therefore, deck[i] is a legal argument for printCard.

Searching
findcard searching linear search findCard

The next method I want to write is findCard, which searches through an array of Cards to see whether it contains a certain card. It may not be obvious why this method would be useful, but it gives me a chance to demonstrate two ways to go searching for things, a linear search and a bisection search.

traverse loop!search

Linear search is the more obvious of the two; it involves traversing the deck and comparing each card to the one we are looking for. If we find it we return the index where the card appears. If it is not in the deck, we return -1.

verbatim public static int findCard (Card[] deck, Card card) for (int i = 0; i< deck.length; i++) if (sameCard (deck[i], card)) return i;   return -1; verbatim

The arguments of findCard are named card and deck. It might seem odd to have a variable with the same name as a type (the card variable has type Card). This is legal and common, although it can sometimes make code hard to read. In this case, though, I think it works.

statement!return return!inside loop

The method returns as soon as it discovers the card, which means that we do not have to traverse the entire deck if we find the card we are looking for. If the loop terminates without finding the card, we know the card is not in the deck and return -1.

If the cards in the deck are not in order, there is no way to search that is faster than this. We have to look at every card, since otherwise there is no way to be certain the card we want is not there.

bisection search

But when you look for a word in a dictionary, you don't search linearly through every word. The reason is that the words are in alphabetical order. As a result, you probably use an algorithm that is similar to a bisection search:

enumerate

Start in the middle somewhere.

Choose a word on the page and compare it to the word you are looking for.

If you found the word you are looking for, stop.

If the word you are looking for comes after the word on the page, flip to somewhere later in the dictionary and go to step 2.

If the word you are looking for comes before the word on the page, flip to somewhere earlier in the dictionary and go to step 2.

enumerate

If you ever get to the point where there are two adjacent words on the page and your word comes between them, you can conclude that your word is not in the dictionary. The only alternative is that your word has been misfiled somewhere, but that contradicts our assumption that the words are in alphabetical order.

In the case of a deck of cards, if we know that the cards are in order, we can write a version of findCard that is much faster. The best way to write a bisection search is with a recursive method. That's because bisection is naturally recursive.

findBisect

The trick is to write a method called findBisect that takes two indices as parameters, low and high, indicating the segment of the array that should be searched (including both low and high).

enumerate

To search the array, choose an index between low and high (call it mid) and compare it to the card you are looking for.

If you found it, stop.

If the card at mid is higher than your card, search in the range from low to mid-1.

If the card at mid is lower than your card, search in the range from mid+1 to high.

enumerate

Steps 3 and 4 look suspiciously like recursive invocations. Here's what this all looks like translated into Java code:

verbatim public static int findBisect (Card[] deck, Card card, int low, int high) int mid = (high + low) / 2; int comp = compareCard (deck[mid], card);

if (comp == 0) return mid; else if (comp > 0) return findBisect (deck, card, low, mid-1); else return findBisect (deck, card, mid+1, high); verbatim

Rather than call compareCard three times, I called it once and stored the result.

Although this code contains the kernel of a bisection search, it is still missing a piece. As it is currently written, if the card is not in the deck, it will recurse forever. We need a way to detect this condition and deal with it properly (by returning -1).

recursion

The easiest way to tell that your card is not in the deck is if there are no cards in the deck, which is the case if high is less than low. Well, there are still cards in the deck, of course, but what I mean is that there are no cards in the segment of the deck indicated by low and high.

With that line added, the method works correctly:

verbatim public static int findBisect (Card[] deck, Card card, int low, int high) System.out.println (low + ", " + high);

if (high < low) return -1;

int mid = (high + low) / 2; int comp = deck[mid].compareCard (card);

if (comp == 0) return mid; else if (comp > 0) return findBisect (deck, card, low, mid-1); else return findBisect (deck, card, mid+1, high); verbatim

I added a print statement at the beginning so I could watch the sequence of recursive calls and convince myself that it would eventually reach the base case. I tried out the following code:

verbatim Card card1 = new Card (1, 11); System.out.println (findBisect (deck, card1, 0, 51)); verbatim

And got the following output:

verbatim 0, 51 0, 24 13, 24 19, 24 22, 24 23 verbatim

Then I made up a card that is not in the deck (the 15 of Diamonds), and tried to find it. I got the following:

verbatim 0, 51 0, 24 13, 24 13, 17 13, 14 13, 12 -1 verbatim

These tests don't prove that this program is correct. In fact, no amount of testing can prove that a program is correct. On the other hand, by looking at a few cases and examining the code, you might be able to convince yourself.

testing correctness

The number of recursive calls is fairly small, typically 6 or 7. That means we only had to invoke compareCard 6 or 7 times, compared to up to 52 times if we did a linear search. In general, bisection is much faster than a linear search, especially for large arrays.

Two common errors in recursive programs are forgetting to include a base case and writing the recursive call so that the base case is never reached. Either error will cause an infinite recursion, in which case Java will (eventually) throw a StackOverflowException.

recursion!infinite infinite recursion exception!StackOverflow

Decks and subdecks
deck subdeck

Looking at the interface to findBisect

verbatim public static int findBisect (Card[] deck, Card card, int low, int high) verbatim

it might make sense to treat three of the parameters, deck, low and high, as a single parameter that specifies a subdeck. We took a similar view in Section graphics when we were talking about bounding boxes. In that case I referred to x, y, width and height as if they were a single parameter, a bounding box.

parameter!abstract abstract parameter

This kind of thing is quite common, and I sometimes think of it as an abstract parameter. What I mean by ``abstract,'' is something that is not literally part of the program text, but which describes the function of the program at a higher level.

For example, when you invoke a method and pass an array and the bounds low and high, there is nothing that prevents the invoked method from accessing parts of the array that are out of bounds. So you are not literally sending a subset of the deck; you are really sending the whole deck. But as long as the recipient plays by the rules, it makes sense to think of it, abstractly, as a subdeck.

There is one other example of this kind of abstraction that you might have noticed in Section objectops, when I referred to an ``empty'' data structure. The reason I put ``empty'' in quotation marks was to suggest that it is not literally accurate. All variables have values all the time. When you create them, they are given default values. So there is no such thing as an empty object.

But if the program guarantees that the current value of a variable is never read before it is written, then the current value is irrelevant. Abstractly, it makes sense to think of such a variable as ``empty.''

This kind of thinking, in which a program comes to take on meaning beyond what is literally encoded, is a very important part of thinking like a computer scientist. Sometimes, the word ``abstract'' gets used so often and in so many contexts that it comes to lose its meaning. Nevertheless, abstraction is a central idea in computer science (as well as many other fields).

abstraction

A more general definition of ``abstraction is ``The process of modeling a complex system with a simplified description in order to suppress unnecessary details while capturing relevant behavior.

Glossary
description

[encode:] To represent one set of values using another set of values, by constructing a mapping between them.

[shallow equality:] Equality of references. Two references that point to the same object.

[deep equality:] Equality of values. Two references that point to objects that have the same value.

[abstract parameter:] A set of parameters that act together as a single parameter.

[abstraction:] The process of interpreting a program (or anything else) at a higher level than what is literally represented by the code.

encode shallow equality deep equality abstract parameter abstraction

description

title: The Way of the Java/Arrays of Objects


text: Python Programming/Print version

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Python Programming/Print version


text:
The Way of the Java/Objects of Arrays

Objects of Arrays
deck deck array!of Cards

In the previous chapter, we worked with an array of objects, but I also mentioned that it is possible to have an object that contains an array as an instance variable. In this chapter I am going to create a new object, called a Deck, that contains an array of Cards as an instance variable.

instance variable variable!instance

The class definition looks like this

verbatim class Deck Card[] cards;

public Deck (int n)    cards = new Card[n];

verbatim

The name of the instance variable is cards to help distinguish the Deck object from the array of Cards that it contains. Here is a state diagram showing what a Deck object looks like with no cards allocated:

state diagram constructor

figure=figs/deckobject.eps

As usual, the constructor initializes the instance variable, but in this case it uses the new command to create the array of cards. It doesn't create any cards to go in it, though. For that we could write another constructor that creates a standard 52-card deck and populates it with Card objects:

verbatim public Deck cards = new Card[52]; int index = 0; for (int suit = 0; suit <= 3; suit++) for (int rank = 1; rank <= 13; rank++) cards[index] = new Card (suit, rank); index++; verbatim

Notice how similar this method is to buildDeck, except that we had to change the syntax to make it a constructor. To invoke it, we use the new command:

new statement!new

verbatim Deck deck = new Deck ; verbatim

Now that we have a Deck class, it makes sense to put all the methods that pertain to Decks in the Deck class definition. Looking at the methods we have written so far, one obvious candidate is printDeck (Section printdeck). Here's how it looks, rewritten to work with a Deck object:

printDeck

verbatim public static void printDeck (Deck deck) for (int i=0; i<deck.cards.length; i++) Card.printCard (deck.cards[i]); verbatim

The most obvious thing we have to change is the type of the parameter, from Card[] to Deck. The second change is that we can no longer use deck.length to get the length of the array, because deck is a Deck object now, not an array. It contains an array, but it is not, itself, an array. Therefore, we have to write deck.cards.length to extract the array from the Deck object and get the length of the array.

For the same reason, we have to use deck.cards[i] to access an element of the array, rather than just deck[i]. The last change is that the invocation of printCard has to say explicitly that printCard is defined in the Card class.

For some of the other methods, it is not obvious whether they should be included in the Card class or the Deck class. For example, findCard takes a Card and a Deck as arguments; you could reasonably put it in either class. As an exercise, move findCard into the Deck class and rewrite it so that the first parameter is a Deck object rather than an array of Cards.

Shuffling
shuffle shuffling

For most card games you need to be able to shuffle the deck; that is, put the cards in a random order. In Section random we saw how to generate random numbers, but it is not obvious how to use them to shuffle a deck.

One possibility is to model the way humans shuffle, which is usually by dividing the deck in two and then reassembling the deck by choosing alternately from each deck. Since humans usually don't shuffle perfectly, after about 7 iterations the order of the deck is pretty well randomized. But a computer program would have the annoying property of doing a perfect shuffle every time, which is not really very random. In fact, after 8 perfect shuffles, you would find the deck back in the same order you started in. For a discussion of that claim, see http://www.wiskit.com/marilyn/craig.html or do a web search with the keywords ``perfect shuffle.''

A better shuffling algorithm is to traverse the deck one card at a time, and at each iteration choose two cards and swap them.

pseudocode

Here is an outline of how this algorithm works. To sketch the program, I am using a combination of Java statements and English words that is sometimes called pseudocode:

verbatim for (int i=0; i<deck.cards.length; i++) // choose a random number between i and deck.cards.length // swap the ith card and the randomly-chosen card verbatim

The nice thing about using pseudocode is that it often makes it clear what methods you are going to need. In this case, we need something like randomInt, which chooses a random integer between the parameters low and high, and swapCards which takes two indices and switches the cards at the indicated positions.

random number

You can probably figure out how to write randomInt by looking at Section random, although you will have to be careful about possibly generating indices that are out of range.

swapCards reference

You can also figure out swapCards yourself. The only tricky thing is to decide whether to swap just the references to the cards or the contents of the cards. Does it matter which one you choose? Which is faster?

I will leave the remaining implementation of these methods as an exercise to the reader.

Sorting
sorting sorting

Now that we have messed up the deck, we need a way to put it back in order. Ironically, there is an algorithm for sorting that is very similar to the algorithm for shuffling. This algorithm is sometimes called selection sort because it works by traversing the array repeatedly and selecting the lowest remaining card each time.

selection sort

During the first iteration we find the lowest card and swap it with the card in the 0th position. During the ith, we find the lowest card to the right of i and swap it with the ith card.

Here is pseudocode for selection sort:

verbatim for (int i=0; i<deck.cards.length; i++) // find the lowest card at or to the right of i     // swap the ith card and the lowest card verbatim

Again, the pseudocode helps with the design of the helper methods. In this case we can use swapCards again, so we only need one new one, called findLowestCard, that takes an array of cards and an index where it should start looking.

helper method method!helper

Once again, I am going to leave the implementation up to the reader.

Subdecks
subdeck

How should we represent a hand or some other subset of a full deck? One good choice is to make a Deck object that has fewer than 52 cards.

We might want a method, subdeck, that takes an array of cards and a range of indices, and that returns a new array of cards that contains the specified subset of the deck:

verbatim public static Deck subdeck (Deck deck, int low, int high) Deck sub = new Deck (high-low+1); for (int i = 0; i<sub.cards.length; i++) sub.cards[i] = deck.cards[low+i]; return sub; verbatim

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.

constructor overloading

Because we provide an argument with the new command, the constructor that gets invoked will be the first one, which only allocates the array and doesn't allocate any cards. Inside the for loop, the subdeck gets populated with copies of the references from the deck.

The following is a state diagram of a 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; i.e. they are aliased.

figure=figs/subdeck.eps

aliasing reference

I have suggested that aliasing is not generally a good idea, since changes in one subdeck will be reflected in others, 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. So for Cards aliasing is a reasonable choice.

As an exercise, write a version of findBisect that takes a subdeck as an argument, rather than a deck and an index range. Which version is more error-prone? Which version do you think is more efficient?

Shuffling and dealing
shuffling dealing

In Section shuffle I wrote pseudocode for a shuffling algorithm. Assuming that we have a method called shuffleDeck that takes a deck as an argument and shuffles it, we can create and shuffle a deck:

verbatim Deck deck = new Deck ; shuffleDeck (deck); verbatim

Then, to deal out several hands, we can use subdeck:

verbatim Deck hand1 = subdeck (deck, 0, 4); Deck hand2 = subdeck (deck, 5, 9); Deck pack = subdeck (deck, 10, 51); verbatim

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 common 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 engineering metaphors: 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.

Mergesort
mergesort efficiency sorting mergesort

In Section sorting, we saw a simple sorting algorithm that turns out not to be very efficient. In order to sort items, it has to traverse the array  times, and each traversal takes an amount of time that is proportional to. The total time, therefore, is proportional to.

In this section I will sketch a more efficient algorithm called mergesort. To sort items, mergesort takes time proportional to .  That may not seem impressive, but as  gets big, the difference between and  can be enormous. Try out a few values of 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:

enumerate

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.

enumerate

The result should be a single sorted deck. Here's what this looks like in pseudocode:

verbatim 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; verbatim

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.

testing

If you can get that working, try a simple implementation of mergeSort:

verbatim public static Deck mergeSort (Deck deck) // find the midpoint of the deck // divide the deck into two subdecks // sort the subdecks using sortDeck // merge the two halves and return the result verbatim

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?

recursion

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:

verbatim public static Deck mergeSort (Deck deck) // 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 verbatim

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.

leap of faith

When you were using sortDeck to sort the subdecks, you didn't feel compelled to follow the flow of execution, right? You just assumed that the sortDeck method would work because you already debugged it. 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!

Glossary
description

[pseudocode:] A way of designing programs by writing rough drafts in a combination of English and Java.

[helper method:] Often a small method that does not do anything enormously useful by itself, but which helps another, more useful, method.

pseudocode helper method method!helper

description

title: The Way of the Java/Objects of Arrays


text:
The Way of the Java/Object-oriented programming

Programming languages and styles
programming language language!programming programming style object-oriented programming functional programming procedural programming programming!object-oriented programming!functional programming!procedural

There are many programming languages in the world, and almost as many programming styles (sometimes called paradigms). Three styles that have appeared in this book are 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. The style I have demonstrated in this book is pretty much procedural. Existing Java programs and the built-in Java packages are written in a mixture of all three styles, but they tend to be more object-oriented than the programs in this book.

It's not easy to define what object-oriented programming is, but here are some of its characteristics:

itemize

Object definitions (classes) usually correspond to relevant real-world objects. For example, in Chapter deck, the creation of the Deck class was a step toward object-oriented programming.

The majority of methods are object methods (the kind you invoke on an object) rather than class methods (the kind you just invoke). So far all the methods we have written have been class methods. In this chapter we will write some object methods.

The language feature most associated with object-oriented programming is inheritance. I will cover inheritance later in this chapter.

itemize

inheritance

Recently object-oriented programming has become quite popular, and there are 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.

Object and class methods
object method method!object class method method!class static

There are two types of methods in Java, called class methods and object methods. So far, every method we have written has been a class method. Class methods are identified by the keyword static in the first line. Any method that does not have the keyword static is an object method.

Although we have not written any object methods, we have invoked some. Whenever you invoke a method ``on'' an object, it's an object method. For example, drawOval is an object method we invoked on g, which is a Graphics object. Also, the methods we invoked on Strings in Chapter strings were object methods.

Graphics class!Graphics

Anything that can be written as a class method can also be written as an object method, and vice versa. Sometimes it is just more natural to use one or the other. For reasons that will be clear soon, object methods are often shorter than the corresponding class methods.

The current object
current object object!current this

When you invoke a method on an object, that object becomes the current object. Inside the method, you can refer to the instance variables of the current object by name, without having to specify the name of the object.

constructor

Also, you can refer to the current object using the keyword this. We have already seen this used in constructors. In fact, you can think of constructors as being a special kind of object method.

Complex numbers
complex number Complex class!Complex arithmetic!complex

As a running example for the rest of this chapter we will consider a class definition for complex numbers. Complex numbers are useful for many branches of mathematics and engineering, and many computations are performed using complex arithmetic. A complex number is the sum of a real part and an imaginary part, and is usually written in the form, where is the real part,  is the imaginary part, and represents the square root of -1. Thus,.

The following is a class definition for a new object type called Complex:

verbatim class Complex

// instance variables double real, imag;

// constructor public Complex this.real = 0.0; this.imag = 0.0; // constructor public Complex (double real, double imag) this.real = real; this.imag = imag;

verbatim

There should be nothing surprising here. The instance variables are two doubles that contain the real and imaginary parts. The two constructors are the usual kind: one takes no parameters and assigns default values to the instance variables, the other takes parameters that are identical to the instance variables. As we have seen before, the keyword this is used to refer to the object being initialized.

instance variable variable!instance constructor

In main, or anywhere else we want to create Complex objects, we have the option of creating the object and then setting the instance variables, or doing both at the same time:

verbatim Complex x = new Complex ; x.real = 1.0; x.imag = 2.0; Complex y = new Complex (3.0, 4.0); verbatim

A function on Complex numbers
operator!Complex method!function pure function

Let's look at some of the operations we might want to perform on complex numbers. The absolute value of a complex number is defined to be. The abs method is a pure function that computes the absolute value. Written as a class method, it looks like this:

verbatim // class method public static double abs (Complex c)    return Math.sqrt (c.real * c.real + c.imag * c.imag); verbatim

This version of abs calculates the absolute value of c, the Complex object it receives as a parameter. The next version of abs is an object method; it calculates the absolute value of the current object (the object the method was invoked on). Thus, it does not receive any parameters:

verbatim // object method public double abs return Math.sqrt (real*real + imag*imag); verbatim

I removed the keyword static to indicate that this is an object method. Also, I eliminated the unnecessary parameter. Inside the method, I can refer to the instance variables real and imag by name without having to specify an object. Java knows implicitly that I am referring to the instance variables of the current object. If I wanted to make it explicit, I could have used the keyword this:

verbatim // object method public double abs return Math.sqrt (this.real * this.real + this.imag * this.imag); verbatim

But that would be longer and not really any clearer. To invoke this method, we invoke it on an object, for example

verbatim Complex y = new Complex (3.0, 4.0); double result = y.abs; verbatim

Another function on Complex numbers
Another operation we might want to perform on complex numbers is addition. You can add complex numbers by adding the real parts and adding the imaginary parts. Written as a class method, that looks like:

verbatim public static Complex add (Complex a, Complex b)    return new Complex (a.real + b.real, a.imag + b.imag); verbatim

To invoke this method, we would pass both operands as arguments:

verbatim Complex sum = add (x, y); verbatim

Written as an object method, it would take only one argument, which it would add to the current object:

verbatim public Complex add (Complex b)    return new Complex (real + b.real, imag + b.imag); verbatim

Again, we can refer to the instance variables of the current object implicitly, but to refer to the instance variables of b we have to name b explicitly using dot notation. To invoke this method, you invoke it on one of the operands and pass the other as an argument.

dot notation

verbatim Complex sum = x.add (y); verbatim

From these examples you can see that the current object (this) can take the place of one of the parameters. For this reason, the current object is sometimes called an implicit parameter.

A modifier modifier method!modifier

As yet another example, we'll look at conjugate, which is a modifier method that transforms a Complex number into its complex conjugate. The complex conjugate of is.

As a class method, this looks like:

verbatim public static void conjugate (Complex c)    c.imag = -c.imag; verbatim

As an object method, it looks like

verbatim public void conjugate imag = -imag; verbatim

By now you should be getting the sense that converting a method from one kind to another is a mechanical process. With a little practice, you will be able to do it without giving it much thought, which is good because you should not be constrained to writing one kind of method or the other. You should be equally familiar with both so that you can choose whichever one seems most appropriate for the operation you are writing.

For example, I think that add should be written as a class method because it is a symmetric operation of two operands, and it makes sense for both operands to appear as parameters. It just seems odd to invoke the method on one of the operands and pass the other as an argument.

On the other hand, simple operations that apply to a single object can be written most concisely as object methods (even if they take some additional arguments).

The toString method
toString method!toString

There are two object methods that are common to many object types: toString and equals. toString converts the object to some reasonable string representation that can be printed. equals is used to compare objects.

When you print an object using print or println, Java checks to see whether you have provided an object method named toString, and if so it invokes it. If not, it invokes a default version of toString that produces the output described in Section printobject.

Here is what toString might look like for the Complex class:

verbatim public String toString return real + " + " + imag + "i"; verbatim

The return type for toString is String, naturally, and it takes no parameters. You can invoke toString in the usual way:

verbatim Complex x = new Complex (1.0, 2.0); String s = x.toString ; verbatim

or you can invoke it indirectly through print:

verbatim System.out.println (x); verbatim

Whenever you pass an object to print or println, Java invokes the toString method on that object and prints the result. In this case, the output is 1.0 + 2.0i.

This version of toString does not look good if the imaginary part is negative. As an exercise, fix it.

The equals method
equals method!equals

When you use the == operator to compare two objects, what you are really asking is, ``Are these two things the same object?'' That is, do both objects refer to the same location in memory.

For many types, that is not the appropriate definition of equality. For example, two complex numbers are equal if their real parts are equal and their imaginary parts are equal.

type!object

When you create a new object type, you can provide your own definition of equality by providing an object method called equals. For the Complex class, this looks like:

verbatim public boolean equals (Complex b)    return (real == b.real && imag == b.imag); verbatim

By convention, equals is always an object method. The return type has to be boolean.

The documentation of equals in the Object class provides some guidelines you should keep in mind when you make up your own definition of equality:

quote

The equals method implements an equivalence relation:

equality identity

itemize

It is reflexive: for any reference value x, x.equals(x) should return true.

It is symmetric: for any reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.

It is transitive: for any reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.

It is consistent: for any reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false.

For any reference value x, x.equals(null) should return false.

itemize

quote

The definition of equals I provided satisfies all these conditions except one. Which one? As an exercise, fix it.

Invoking one object method from another method!invoking

As you might expect, it is legal and common to invoke one object method from another. For example, to normalize a complex number, you divide through (both parts) by the absolute value. It may not be obvious why this is useful, but it is.

Let's write the method normalize as an object method, and let's make it a modifier.

verbatim public void normalize double d = this.abs; real = real/d; imag = imag/d; verbatim

The first line finds the absolute value of the current object by invoking abs on the current object. In this case I named the current object explicitly, but I could have left it out. If you invoke one object method within another, Java assumes that you are invoking it on the current object.

As an exercise, rewrite normalize as a pure function. Then rewrite it as a class method.

Oddities and errors
method!object method!class overloading

If you have both object methods and class methods in the same class definition, it is easy to get confused. A common way to organize a class definition is to put all the constructors at the beginning, followed by all the object methods and then all the class methods.

You can have an object method and a class method with the same name, as long as they do not have the same number and types of parameters. As with other kinds of overloading, Java decides which version to invoke by looking at the arguments you provide.

static

Now that we know what the keyword static means, you have probably figured out that main is a class method, which means that there is no ``current object'' when it is invoked.

current object this instance variable variable!instance

Since there is no current object in a class method, it is an error to use the keyword this. If you try, you might get an error message like: ``Undefined variable: this.'' Also, you cannot refer to instance variables without using dot notation and providing an object name. If you try, you might get ``Can't make a static reference to nonstatic variable...'' This is not one of the better error messages, since it uses some non-standard language. For example, by ``nonstatic variable it means ``instance variable. But once you know what it means, you know what it means.

Inheritance
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.

Drawable rectangles
Rectangle class!Rectangle drawable

An an example of inheritance, 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:

verbatim import java.awt.*;

class DrawableRectangle extends Rectangle

public void draw (Graphics g)    g.drawRect (x, y, width, height);

verbatim

Yes, that's really all there is in the whole class definition. The first line imports the java.awt package, which is where Rectangle and Graphics are defined.

AWT import statement!import

The next line indicates that DrawableRectangle inherits from Rectangle. The keyword extends is used to identify the parent class.

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:

verbatim public static void draw (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); verbatim

The parameters of draw are a Graphics object and the bounding box of the drawing area (not the coordinates of the rectangle).

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.

constructor

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.

The class hierarchy
class hierarchy Object parent class class!parent

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 almost all of the classes we have written 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. For example, Slate extends Frame (see Appendix slate), which 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.

Object-oriented design
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, one of the methods you can invoke on a Slate is getBounds. 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 Slate.

Also, many of the things that can be done using inheritance can be done almost as elegantly (or more so) without it.

Glossary
description

[object method:] A method that is invoked on an object, and that operates on that object, which is referred to by the keyword this in Java or ``the current object'' in English. Object methods do not have the keyword static.

[class method:] A method with the keyword static. Class methods are not invoked on objects and they do not have a current object.

[current object:] The object on which an object method is invoked. Inside the method, the current object is referred to by this.

[this:] The keyword that refers to the current object.

[implicit:] Anything that is left unsaid or implied. Within an object method, you can refer to the instance variables implicitly (without naming the object).

[explicit:] Anything that is spelled out completely. Within a class method, all references to the instance variables have to be explicit.

object method class method current object this implicit explicit


text:
The Way of the Java/Linked lists

References in objects
reference embedded reference reference!embedded node cargo

In the last chapter we saw that the instance variables of an object can be arrays, and I mentioned that they can be objects, too.

One of the more interesting possibilities is that an object can contain a reference to another object of the same type. There is a common data structure, the list, that takes advantage of this feature.

Lists are made up of nodes, where each node contains a reference to the next node in the list. In addition, each node usually contains a unit of data called the cargo. In our first example, the cargo will be a single integer, but later we will write a generic list that can contain objects of any type.

generic data structure data structure!generic

The Node class
Node class class!Node

As usual when we write a new class, we'll start with the instance variables, one or two constructors and toString so that we can test the basic mechanism of creating and displaying the new type.

verbatim public class Node int cargo; Node next;

public Node cargo = 0; next = null;

public Node (int cargo, Node next) this.cargo = cargo; this.next = next;

public String toString return cargo + "";

verbatim

The declarations of the instance variables follow naturally from the specification, and the rest follows mechanically from the instance variables. The expression cargo + "" is an awkward but concise way to convert an integer to a String.

To test the implementation so far, we would put something like this in main:

verbatim Node node = new Node (1, null); System.out.println (node); verbatim

The result is simply

verbatim 1 verbatim

To make it interesting, we need a list with more than one node!

verbatim Node node1 = new Node (1, null); Node node2 = new Node (2, null); Node node3 = new Node (3, null); verbatim

This code creates three nodes, but we don't have a list yet because the nodes are not linked. The state diagram looks like this:

figure=figs/list1.eps

To link up the nodes, we have to make the first node refer to the second and the second node refer to the third.

verbatim node1.next = node2; node2.next = node3; node3.next = null; verbatim

The reference of the third node is null, which indicates that it is the end of the list. Now the state diagram looks like:

figure=figs/list2.eps

Now we know how to create nodes and link them into lists. What might be less clear at this point is why.

Lists as collections
collection

The thing that makes lists useful is that they are a way of assembling multiple objects into a single entity, sometimes called a collection. In the example, the first node of the list serves as a reference to the entire list.

list!printing list!as parameter

If we want to pass the list as a parameter, all we have to pass is a reference to the first node. For example, the method printList takes a single node as an argument. Starting with the head of the list, it prints each node until it gets to the end (indicated by the null reference).

verbatim public static void printList (Node list) Node node = list;

while (node != null) System.out.print (node); node = node.next; System.out.println ; verbatim

To invoke this method we just have to pass a reference to the first node:

verbatim printList (node1); verbatim

Inside printList we have a reference to the first node of the list, but there is no variable that refers to the other nodes. We have to use the next value from each node to get to the next node.

This diagram shows the value of list and the values that node takes on:

figure=figs/list3.eps

This way of moving through a list is called a traversal, just like the similar pattern of moving through the elements of an array. It is common to use a loop variable like node to refer to each of the nodes in the list in succession.

loop variable list!traversal traverse

The output of this method is

verbatim 123 verbatim

By convention, lists are printed in parentheses with commas between the elements, as in (1, 2, 3). As an exercise, modify printList so that it generates output in this format.

As another exercise, rewrite printList using a for loop instead of a while loop.

Lists and recursion
list!traverse recursively traverse

Recursion and lists go together like fava beans and a nice Chianti. For example, here is a recursive algorithm for printing a list backwards:

fava beans Chianti

enumerate

Separate the list into two pieces: the first node (called the head) and the rest (called the tail).

Print the tail backwards.

Print the head.

enumerate

Of course, Step 2, the recursive call, assumes that we have a way of printing a list backwards. But if we assume that the recursive call works---the leap of faith---then we can convince ourselves that this algorithm works.

leap of faith list!printing backwards

All we need is a base case, and a way of proving that for any list we will eventually get to the base case. A natural choice for the base case is a list with a single element, but an even better choice is the empty list, represented by null.

verbatim public static void printBackward (Node list) if (list == null) return;

Node head = list; Node tail = list.next;

printBackward (tail); System.out.print (head); verbatim

The first line handles the base case by doing nothing. The next two lines split the list into head and tail. The last two lines print the list.

We invoke this method exactly as we invoked printList:

verbatim printBackward (node1); verbatim

The result is a backwards list.

Can we prove that this method will always terminate? In other words, will it always reach the base case? In fact, the answer is no. There are some lists that will make this method crash.

Infinite lists
infinite list list!infinite loop!in list list!loop

There is nothing to prevent a node from referring back to an earlier node in the list, including itself. For example, this figure shows a list with two nodes, one of which refers to itself.

figure=figs/list4.eps

If we invoke printList on this list, it will loop forever. If we invoke printBackward it will recurse infinitely. This sort of behavior makes infinite lists difficult to work with.

Nevertheless, they are occasionally useful. For example, we might represent a number as a list of digits and use an infinite list to represent a repeating fraction.

Regardless, it is problematic that we cannot prove that printList and printBackward terminate. The best we can do is the hypothetical statement, ``If the list contains no loops, then these methods will terminate.'' This sort of claim is called a precondition. It imposes a constraint on one of the parameters and describes the behavior of the method if the constraint is satisfied. We will see more examples soon.

precondition

The fundamental ambiguity theorem
ambiguity!fundamental theorem theorem!fundamental ambiguity

There is a part of printBackward that might have raised an eyebrow:

verbatim Node head = list; Node tail = list.next; verbatim

After the first assignment, head and list have the same type and the same value. So why did I create a new variable?

The reason is that the two variables play different roles. We think of head as a reference to a single node, and we think of list as a reference to the first node of a list. These ``roles'' are not part of the program; they are in the mind of the programmer.

variable!roles role!variable

The second assignment creates a new reference to the second node in the list, but in this case we think of it as a list. So, even though head and tail have the same type, they play different roles.

This ambiguity is useful, but it can make programs with lists difficult to read. I often use variable names like node and list to document how I intend to use a variable, and sometimes I create additional variables to disambiguate.

I could have written printBackward without head and tail, but I think it makes it harder to understand:

verbatim public static void printBackward (Node list) if (list == null) return;

printBackward (list.next); System.out.print (list);

verbatim

Looking at the two function calls, we have to remember that printBackward treats its argument as a list and print treats its argument as a single object.

Always keep in mind the fundamental ambiguity theorem:

quote A variable that refers to a node might treat the node as a single object or as the first in a list of nodes. quote

Object methods for nodes
method!object node!object method

You might have wondered why printList and printBackward are class methods. I have made the claim that anything that can be done with class methods can also be done with object methods; it's just a question of which form is cleaner.

In this case there is a legitimate reason to choose class methods. It is legal to send null as an argument to a class method, but it is not legal to invoke an object method on a null object.

verbatim Node node = null; printList (node);      // legal node.printList ;     // NullPointerException verbatim

This limitation makes it awkward to write list-manipulating code in a clean, object-oriented style. A little later we will see a way to get around this, though.

Modifying lists
list!modifying modifying lists

Obviously one way to modify a list is to change the cargo of one of the nodes, but the more interesting operations are the ones that add, remove, or reorder the nodes.

As an example, we'll write a method that removes the second node in the list and returns a reference to the removed node.

verbatim public static Node removeSecond (Node list) Node first = list; Node second = list.next;

// make the first node refer to the third first.next = second.next;

// separate the second node from the rest of the list second.next = null; return second; verbatim

Again, I am using temporary variables to make the code more readable. Here is how to use this method.

verbatim printList (node1); Node removed = removeSecond (node1); printList (removed); printList (node1); verbatim

The output is

verbatim (1, 2, 3)          the original list (2)                the removed node (1, 3)             the modified list verbatim

Here is a state diagram showing the effect of this operation.

figure=figs/list5.eps

What happens if we invoke this method and pass a list with only one element (a singleton)? What happens if we pass the empty list as an argument? Is there a precondition for this method?

singleton

Wrappers and helpers
wrapper methods method!wrapper helper method method!helper

For some list operations it is useful to divide the labor into two methods. For example, to print a list backwards in the conventional list format, (3, 2, 1) we can use the printBackwards method to print 3, 2, but we need a separate method to print the parentheses and the first node. We'll call it printBackwardNicely.

verbatim public static void printBackwardNicely (Node list) System.out.print ("(");

if (list != null) Node head = list; Node tail = list.next; printBackward (tail); System.out.print (head); System.out.println (")"); verbatim

Again, it is a good idea to check methods like this to see if they work with special cases like an empty list or a singleton.

singleton

Elsewhere in the program, when we use this method, we will invoke printBackwardNicely directly and it will invoke printBackward on our behalf. In that sense, printBackwardNicely acts as a wrapper, and it uses printBackward as a helper.

The LinkedList class
LinkedList class!LinkedList

There are a number of subtle problems with the way we have been implementing lists. In a reversal of cause and effect, I will propose an alternative implementation first and then explain what problems it solves.

First, we will create a new class called LinkedList. Its instance variables are an integer that contains the length of the list and a reference to the first node in the list. LinkedList objects serve as handles for manipulating lists of Node objects.

verbatim public class LinkedList int length; Node head;

public LinkedList length = 0; head = null;

verbatim

One nice thing about the LinkedList class is that it gives us a natural place to put wrapper functions like printBackwardNicely, which we can make an object method in the LinkedList class.

verbatim public void printBackward System.out.print ("(");

if (head != null) Node tail = head.next; Node.printBackward (tail); System.out.print (head); System.out.println (")"); verbatim

Just to make things confusing, I renamed printBackwardNicely. Now there are two methods named printBackward: one in the Node class (the helper) and one in the LinkedList class (the wrapper). In order for the wrapper to invoke the helper, it has to identify the class explicitly (Node.printBackward).

So, one of the benefits of the LinkedList class is that it provides a nice place to put wrapper functions. Another is that it makes it easier to add or remove the first element of a list. For example, addFirst is an object method for LinkedLists; it takes an int as an argument and puts it at the beginning of the list.

verbatim public void addFirst (int i)        Node node = new Node (i, head); head = node; length++; verbatim

As always, to check code like this it is a good idea to think about the special cases. For example, what happens if the list is initially empty?

Invariants
invariant object invariant list!well-formed

Some lists are ``well-formed;'' others are not. For example, if a list contains a loop, it will cause many of our methods to crash, so we might want to require that lists contain no loops. Another requirement is that the length value in the LinkedList object should be equal to the actual number of nodes in the list.

Requirements like this are called invariants because, ideally, they should be true of every object all the time. Specifying invariants for objects is a useful programming practice because it makes it easier to prove the correctness of code, check the integrity of data structures, and detect errors.

One thing that is sometimes confusing about invariants is that there are some times when they are violated. For example, in the middle of addFirst, after we have added the node, but before we have incremented length, the invariant is violated. This kind of violation is acceptable; in fact, it is often impossible to modify an object without violating an invariant for at least a little while. Normally the requirement is that every method that violates an invariant must restore the invariant.

If there is any significant stretch of code in which the invariant is violated, it is important for the comments to make that clear, so that no operations are performed that depend on the invariant.

documentation

Glossary
list node cargo link generic data structure precondition invariant wrapper

description

[list:] A data structure that implements a collection using a sequence of linked nodes.

[node:] An element of a list, usually implemented as an object that contains a reference to another object of the same type.

[cargo:] An item of data contained in a node.

[link:] An object reference embedded in an object.

[generic data structure:] A kind of data structure that can contain data of any type.

[precondition:] An assertion that must be true in order for a method to work correctly.

[invariant:] An assertion that should be true of an object at all times (except maybe while the object is being modified).

[wrapper method:] A method that acts as a middle-man between a caller and a helper method, often offering an interface that is cleaner than the helper method's.

title: The Way of the Java/Linked lists


text:
The Way of the Java/Stacks

Abstract data types
abstract data typeseeADT ADT encapsulation

The data types we have looked at so far are all concrete, in the sense that we have completely specified how they are implemented. For example, the Card class represents a card using two integers. As I discussed at the time, that is not the only way to represent a card; there are many alternative implementations.

An abstract data type, or ADT, specifies a set of operations (or methods) and the semantics of the operations (what they do) but it does not specify the implementation of the operations. That's what makes it abstract.

Why is that useful?
itemize

It simplifies the task of specifying an algorithm if you can denote the operations you need without having to think at the same time about how the operations are performed.

Since there are usually many ways to implement an ADT, it might be useful to write an algorithm that can be used with any of the possible implementations.

Well-known ADTs, like the Stack ADT in this chapter, are often implemented in standard libraries so they can be written once and used by many programmers.

The operations on ADTs provide a common high-level language for specifying and talking about algorithms.

itemize

When we talk about ADTs, we often distinguish the code that uses the ADT, called the client code, from the code that implements the ADT, called provider code because it provides a standard set of services.

client provider

The Stack ADT
stack collection ADT!Stack

In this chapter we will look at one common ADT, the stack. A stack is a collection, meaning that it is a data structure that contains multiple elements. Other collections we have seen include arrays and lists.

As I said, an ADT is defined by a set of operations. Stacks can perform the following set of operations:

description

[constructor:] Create a new, empty stack.

[push:] Add a new item to the stack.

[pop:] Remove and return an item from the stack. The item that is returned is always the last one that was added.

[empty:] Check whether the stack is empty.

description

A stack is sometimes called a ``last in, first out,'' or LIFO data structure, because the last item added is the first to be removed.

The Java Stack Object
Stack class!Stack generic data structure data structure!generic

Java provides a built-in object type called Stack that implements the Stack ADT. You should make some effort to keep these two things---the ADT and the Java implementation---straight. Before using the Stack class, we have to import it from java.util.

Then the syntax for constructing a new Stack is

verbatim Stack stack = new Stack ; verbatim

Initially the stack is empty, as we can confirm with the empty method, which returns a boolean:

verbatim System.out.println (stack.empty ); verbatim

A stack is a generic data structure, which means that we can add any type of item to it. In the Java implementation, though, we can only add object types. For our first example, we'll use Node objects, as defined in the previous chapter. Let's start by creating and printing a short list.

verbatim LinkedList list = new LinkedList ; list.addFirst (3); list.addFirst (2); list.addFirst (1); list.print ; verbatim

The output is (1, 2, 3). To put a Node object onto the stack, use the push method:

verbatim stack.push (list.head); verbatim

The following loop traverses the list and pushes all the nodes onto the stack:

verbatim for (Node node = list.head; node != null; node = node.next) stack.push (node); verbatim

We can remove an element from the stack with the pop method.

verbatim Object obj = stack.pop ; verbatim

The return type from pop is Object! That's because the stack implementation doesn't really know the type of the objects it contains. When we pushed the Node objects, they were automatically converted to Objects. When we get them back from the stack, we have to cast them back to Nodes.

verbatim Node node = (Node) obj; System.out.println (node); verbatim

Unfortunately, the burden falls on the programmer to keep track of the objects in the stack and cast them back to the right type when they are removed. If you try to cast an object to the wrong type, you get a ClassCastException.

The following loop is a common idiom for popping all the elements from a stack, stopping when it is empty:

verbatim while (!stack.empty ) Node node = (Node) stack.pop ; System.out.print (node + " ");

verbatim

The output is 3 2 1. In other words, we just used a stack to print the elements of a list backwards! Granted, it's not the standard format for printing a list, but using a stack it was remarkably easy to do.

You should compare this code to the implementations of printBackward in the previous chapter. There is a natural parallel between the recursive version of printBackward and the stack algorithm here. The difference is that printBackward uses the run-time stack to keep track of the nodes while it traverses the list, and then prints them on the way back from the recursion. The stack algorithm does the same thing, just using a Stack object instead of the run-time stack.

Wrapper classes
wrapper class class!wrapper object type primitive type

For every primitive type in Java, there is a built-in object type called a wrapper class. For example, the wrapper class for int is called Integer; for double it is called Double.

Wrapper classes are useful for several reasons:

itemize

You can instantiate wrapper classes and create objects that contain primitive values. In other words, you can wrap a primitive value up in an object, which is useful if you want to invoke a method that requires an object type.

Each wrapper class contains special values (like the minimum and maximum values for the type), and methods that are useful for converting between types.

itemize

Creating wrapper objects
wrapper class!instantiating

The most straightforward way to create a wrapper object is to use its constructor:

verbatim Integer i = new Integer (17); Double d = new Double (3.14159); Character c = new Character ('b'); verbatim

Technically String is not a wrapper class, because there is no corresponding primitive type, but the syntax for creating a String object is the same:

verbatim String s = new String ("fred"); verbatim

On the other hand, no one ever uses the constructor for String objects, because you can get the same effect with a simple String value:

verbatim String s = "fred"; verbatim

Creating more wrapper objects
Some of the wrapper classes have a second constructor that takes a String as an argument and tries to convert to the appropriate type. For example:

verbatim Integer i = new Integer ("17"); Double d = new Double ("3.14159"); verbatim

The type conversion process is not very robust. For example, if the Strings are not in the right format, they will cause a NumberFormatException. Any non-numeric character in the String, including a space, will cause the conversion to fail.

NumberFormatException exception!NumberFormat

verbatim Integer i = new Integer ("17.1");       // WRONG!! Double d = new Double ("3.1459 ");      // WRONG!! verbatim

It is usually a good idea to check the format of the String before you try to convert it.

Getting the values out
wrapper class!extracting value

Java knows how to print wrapper objects, so the easiest way to extract a value is just to print the object:

verbatim Integer i = new Integer (17); Double d = new Double (3.14159); System.out.println (i); System.out.println (d); verbatim

Alternatively, you can use the toString method to convert the contents of the wrapper object to a String

verbatim String istring = i.toString; String dstring = d.toString; verbatim

Finally, if you just want to extract the primitive value from the object, there is an object method in each wrapper class that does the job:

verbatim int iprim = i.intValue ; double dprim = d.doubleValue ; verbatim

There are also methods for converting wrapper objects into different primitive types. You should check out the documentation for each wrapper class to see what is available.

Useful methods in the wrapper classes
wrapper class!methods

As I mentioned, the wrapper classes contain useful methods that pertain to each type. For example, the Character class contains lots of methods for converting characters to upper and lower case, and for checking whether a character is a number, letter, or symbol.

The String class also contains methods for converting to upper and lower case. Keep in mind, though, that they are functions, not modifiers (see Section immutable).

As another example, the Integer class contains methods for interpreting and printing integers in different bases. If you have a String that contains a number in base 6, you can convert to base 10 using parseInt.

verbatim String base6 = "12345"; int base10 = Integer.parseInt (base6, 6); System.out.println (base10); verbatim

Since parseInt is a class method, you invoke it by naming the class and the method in dot notation.

Base 6 might not be all that useful, but hexadecimal (base 16) and octal (base 8) are common for computer science related things.

Postfix expressions
postfix infix expressions

In most programming languages, mathematical expressions are written with the operator between the two operands, as in 1+2. This format is called infix. An alternate format used by some calculators is called postfix. In postfix, the operator follows the operands, as in 1 2+.

The reason postfix is sometimes useful is that there is a natural way to evaluate a postfix expression using a stack.

itemize

Starting at the beginning of the expression, get one term (operator or operand) at a time.

itemize

If the term is an operand, push it on the stack.

If the term is an operator, pop two operands off the stack, perform the operation on them, and push the result back on the stack.

itemize

When we get to the end of the expression, there should be exactly one operand left on the stack. That operand is the result.

itemize

As an exercise, apply this algorithm to the expression 1 2 + 3 *.

This example demonstrates one of the advantages of postfix: there is no need to use parentheses to control the order of operations. To get the same result in infix, we would have to write (1 + 2) * 3. As an exercise, write a postfix expression that is equivalent to 1 + 2 * 3?

Parsing
parse token delimiter class!StringTokenizer StringTokenizer class

In order to implement the algorithm from the previous section, we need to be able to traverse a string and break it into operands and operators. This process is an example of parsing, and the results---the individual chunks of the string---are called tokens.

Java provides a built-in class called a StringTokenizer that parses strings and breaks them into tokens. To use it, you have to import it from java.util.

In its simplest form, the StringTokenizer uses spaces to mark the boundaries between tokens. A character that marks a boundary is called a delimiter.

We can create a StringTokenizer in the usual way, passing as an argument the string we want to parse.

verbatim StringTokenizer st = new StringTokenizer ("Here are four tokens."); verbatim

The following loop is a standard idiom for extracting the tokens from a StringTokenizer.

verbatim while (st.hasMoreTokens ) System.out.println (st.nextToken); verbatim

The output is

verbatim Here are four tokens. verbatim

For parsing expressions, we have the option of specifying additional characters that will be used as delimiters:

verbatim StringTokenizer st = new StringTokenizer ("11 22+33*", " +-*/"); verbatim

The second argument is a String that contains all the characters that will be used as delimiters. Now the output is:

verbatim 11 22 33 verbatim

This succeeds at extracting all the operands but we have lost the operators. Fortunately, there is one more option for StringTokenizers.

verbatim StringTokenizer st = new StringTokenizer ("11 22+33*", " +-*/", true); verbatim

The third argument says, ``Yes, we would like to treat the delimiters as tokens.'' Now the output is

verbatim 11 22 + 33 verbatim

This is just the stream of tokens we would like for evaluating this expression.

Implementing ADTs
encapsulation ADT

One of the fundamental goals of an ADT is to separate the interests of the provider, who writes the code that implements the ADT, and the client, who uses the ADT. The provider only has to worry about whether the implementation is correct---in accord with the specification of the ADT---and not how it will be used.

Conversely, the client assumes that the implementation of the ADT is correct and doesn't worry about the details. When you are using one of Java's built-in classes, you have the luxury of thinking exclusively as a client.

When you implement an ADT, on the other hand, you also have to write client code to test it. In that case, you sometimes have to think carefully about which role you are playing at a given instant.

In the next few sections we will switch gears and look at one way of implementing the Stack ADT, using an array. Start thinking like a provider.

Array implementation of the Stack ADT
arraystack implementation!Stack stack!array implementation

The instance variables for this implementation are an array of Objects, which will contain the items on the stack, and an integer index which will keep track of the next available space in the array. Initially, the array is empty and the index is 0.

To add an element to the stack (push), we'll copy a reference to it onto the stack and increment the index. To remove an element (pop) we have to decrement the index first and then copy the element out.

Here is the class definition:

verbatim public class Stack Object[] array; int index;

public Stack this.array = new Object[128]; this.index = 0;

verbatim

As usual, once we have chosen the instance variables, it is a mechanical process to write a constructor. For now, the default size is 128 items. Later we will consider better ways of handling this.

Checking for an empty stack is trivial.

verbatim public boolean empty return index == 0; verbatim

It is important to remember, though, that the number of elements in the stack is not the same as the size of the array. Initially the size is 128, but the number of elements is 0.

The implementations of push and pop follow naturally from the specification.

verbatim public void push (Object item) array[index] = item; index++;

public Object pop index--; return array[index]; verbatim

To test these methods, we can take advantage of the client code we used to exercise the built-in Stack. All we have to do is comment out the line import java.util.Stack. Then, instead of using the stack implementation from java.util the program will use the implementation we just wrote.

If everything goes according to plan, the program should work without any additional changes. Again, one of the strengths of using an ADT is that you can change implementations without changing client code.

Resizing arrays
resize array!resizing ArrayIndexOutOfBounds exception!ArrayIndexOutOfBounds

A weakness of this implementation is that it chooses an arbitrary size for the array when the Stack is created. If the user pushes more than 128 items onto the stack, it will cause an ArrayIndexOutOfBounds exception.

ArrayIndexOutOfBounds exception!ArrayIndexOutOfBounds

An alternative is to let the client code specify the size of the array. This alleviates the problem, but it requires the client to know ahead of time how many items are needed, and that is not always possible.

A better solution is to check whether the array is full and make it bigger when necessary. Since we have no idea how big the array needs to be, it is a reasonable strategy to start with a small size and double it each time it overflows.

Here's the improved version of push:

verbatim public void push (Object item) if (full ) resize ;

// at this point we can prove that index < array.length

array[index] = item; index++; verbatim

Before putting the new item in the array, we check if the array is full. If so, we invoke resize. After the if statement, we know that either (1) there was room in the array, or (2) the array has been resized and there is room. If full and resize are correct, then we can prove that index < array.length, and therefore the next statement cannot cause an exception.

Now all we have to do is implement full and resize.

verbatim private boolean full return index == array.length;

private void resize Object[] newArray = new Object[array.length * 2];

// we assume that the old array is full for (int i=0; i<array.length; i++) newArray[i] = array[i]; array = newArray; verbatim

Both methods are declared private, which means that they cannot be invoked from another class, only from within this one. This is acceptable, since there is no reason for client code to use these functions, and desirable, since it enforces the boundary between the implementation and the client.

method!private private method

The implementation of full is trivial; it just checks whether the index has gone beyond the range of valid indices.

The implementation of resize is straightforward, with the caveat that it assumes that the old array is full. In other words, that assumption is a precondition of this method. It is easy to see that this precondition is satisfied, since the only way resize is invoked is if full returns true, which can only happen if index == array.length.

At the end of resize, we replace the old array with the new one (causing the old to be garbage collected). The new array.length is twice as big as the old, and index hasn't changed, so now it must be true that index < array.length. This assertion is a postcondition of resize: something that must be true when the method is complete (as long as its preconditions were satisfied).

Preconditions, postconditions, and invariants are useful tools for analyzing programs and demonstrating their correctness. In this example I have demonstrated a programming style that facilitates program analysis and a style of documentation that helps demonstrate correctness.

precondition postcondition invariant

Glossary
ADT client provider wrapper class infix postfix parse token delimiter predicate postcondition

description

[abstract data type (ADT):] A data type (usually a collection of objects) that is defined by a set of operations, but that can be implemented in a variety of ways.

[client:] A program that uses an ADT (or the person who wrote the program).

[provider:] The code that implements an ADT (or the person who wrote it).

[wrapper class:] One of the Java classes, like Double and Integer that provide objects to contain primitive types, and methods that operate on primitives.

[private:] A Java keyword that indicates that a method or instance variable cannot be accessed from outside the current class definition.

[infix:] A way of writing mathematical expressions with the operators between the operands.

[postfix:] A way of writing mathematical expressions with the operators after the operands.

[parse:] To read a string of characters or tokens and analyze their grammatical structure.

[token:] A set of characters that are treated as a unit for purposes of parsing, like the words in a natural language.

[delimiter:] A character that is used to separate tokens, like the punctuation in a natural language.

[predicate:] A mathematical statement that is either true or false.

[postcondition:] A predicate that must be true at the end of a method (provided that the preconditions were true at the beginning).

title: The Way of the Java/Stacks