Section 4.6
More on Program Design
UNDERSTANDING HOW PROGRAMS WORK IS ONE THING. Designing a program to perform some particular task is another thing altogether. In Section 3.2, I discussed how stepwise refinement can be used to methodically develop an algorithm. We can now see how subroutines can fit into the process.
Stepwise refinement is inherently a top-down process, but the process does have a "bottom," that is, a point at which you stop refining the pseudocode algorithm and translate what you have directly into proper programming language. In the absence of subroutines, the process would not bottom out until you get down to the level of assignment statements and very primitive input/output operations. But if you have subroutines lying around to perform certain useful tasks, you can stop refining as soon as you've managed to express your algorithm in terms of those tasks.
This allows you to add a bottom-up element to the top-down approach of stepwise refinement. Given a problem, you might start by writing some subroutines that perform tasks relevant to the problem domain. The subroutines become a toolbox of ready-made tools that you can integrate into your algorithm as you develop it. (Alternatively, you might be able to buy or find a software toolbox written by someone else, containing subroutines that you can use in your project as black boxes.)
Subroutines can also be helpful even in a strict top-down approach. As you refine your algorithm, you are free at any point to take any sub-task in the algorithm and make it into a subroutine. Developing that subroutine then becomes a separate problem, which you can work on separately. Your main algorithm will merely call the subroutine. This, of course, is just a way of breaking your problem down into separate, smaller problems. It is still a top-down approach because the top-down analysis of the problem tells you what subroutines to write. In the bottom-up approach, you start by writing or obtaining subroutines that are relevant to the problem domain, and you build your solution to the problem on top of that foundation of subroutines.
Let's work through an example. Suppose that I have found an already-written class called Mosaic. This class allows a program to work with a window that displays little colored rectangles arranged in rows and columns. The window can be opened, closed, and otherwise manipulated with static member subroutines defined in the Mosaic class. Here are some of the available routines:
Mosaic.open(rows,cols,w,h); where rows, cols, w, and h are of type int. This will open the window with rows rows and cols columns of rectangles. The size of each little rectangle will be w pixels wide by h pixels high. Initially, all the rectangles are black. Note that for purposes of referring to a specific rectangle, rows are numbered from 0 to rows-1, and columns are numbered from 0 to cols-1.
Mosaic.setColor(row,col,r,g,b); where all the parameters are of type int. This will set the color of the rectangle in row number row and column number col. Any color can be considered to be a combination of the primary colors red, blue, and green. The parameters r, g, and b are integers in the range from 0 to 255 that specify the red, green, and blue components of the color. The larger the value of r, the more red there is in the color. Black has all three color components equal to 0. White has all three color components equal to 255.
Mosaic.getRed(row,col); where row and col are integers specifying one of the rectangles. This is a function that returns a value of type int. The returned value is an integer in the range from 0 to 255 that specifies the red component of the color of the specified square. There are also functions Mosaic.getBlue(row,col); and Mosaic.getGreen(row,col); for retrieving the other two color components.
Mosaic.delay(millis); where millis is of type int. This can be used to insert a time delay in the program (to regulate the speed at which the colors are changed, for example). The parameter millis is an integer that gives the number of milliseconds to delay. One thousand milliseconds equal one second.
Mosaic.isOpen(); is a function that returns a boolean value. If the mosaic window is open, the value is true; otherwise it is false. The user can close the window by clicking its closebox. A program can close the window by calling Mosaic.close(). If you call Mosaic.setColor() when there is no window open, it will have no effect. If you call Mosaic.getRed() when there is no window, a value of 0 is returned.
My idea is to use the Mosaic class as the basis for a neat animation. I want to fill the window with randomly colored squares, and then randomly change the colors in a loop that continues as long as the window is open. "Randomly change the colors" could mean a lot of different things, but after thinking for a while, I decide it would be interesting to have a "disturbance" that wanders randomly around the window, changing the color of each square that it encounters. Here's an applet that shows what the program will do:
With basic routines for manipulating the window as a foundation, I can turn to the specific problem at hand. A basic outline for my program is
Open a Mosaic window Fill window with random colors; Move around, changing squares at random.Filling the window with random colors seems like a nice coherent task that I can work on separately, so let's decide that I'll write a separate subroutine to do it. The third step can be expanded a bit more, into the steps: Start in the middle of the window, then keep moving to a new square and changing the color of that square. This should continue as long as the mosaic window is still open. Thus we can refine the algorithm to:
Open a Mosaic window Fill window with random colors; Set the current position to the middle square in the window; As long as the mosaic window is open: Randomly change color of current square; Move current position up, down, left, or right, at random;I need to represent the current position in some way. That can be done with two int variables named currentRow and currentColumn. I'll use 10 rows and 20 columns of squares in my mosaic, so setting the current position to be in the center means setting currentRow to 5 and currentColumn to 10. I already have a subroutine, Mosaic.open(), to open the window, and I have a function, Mosaic.isOpen(), to test whether the window is open. To keep the main routine simple, I decide that I will write two more subroutines of my own to carry out the two tasks in the while loop. The algorithm can then be written in Java as:
Mosaic.open(10,20,10,10) fillWithRandomColors(); currentRow = 5; // Middle row, halfway down the window. currentColumn = 10; // Middle column. while ( Mosaic.isOpen() ) { changeToRandomColor(currentRow, currentColumn); randomMove(); }With the proper wrapper, this is essentially the main() routine of my program. It turns out I have to make one small modification: To prevent the animation from running too fast, the line "Mosaic.delay(20);" is added to the while loop.
The main() routine is taken care of, but to complete the program, I still have to write the subroutines fillWithRandomColors(), changeToRandomColor(int,int), and randomMove(). Writing each of these subroutines is a separate, small task. Pseudocode for fillWithRandomColors() could be given as:
For each row: For each column: set square in that row and column to a random color"For each row" and "for each column" can be implemented as for loops. We've already planned to write a subroutine changeToRandomColor that can be used to set the color. (The possibility of reusing subroutines in several places is one of the big payoffs of using them!) So, fillWithRandomColors() can be written in proper Java as:
static void fillWithRandomColors() { for (int row = 0; row < 10; row++) for (int column = 0; column < 20; column++) changeToRandomColor(row,column); }Turning to the changeToRandomColor subroutine, we already have a method, mosaic.setColor(row,col,r,g,b), that can be used to change the color of a square. If we want a random color, we just have to choose random values for r, g, and b. The random values must be integers in the range from 0 to 255. A formula for selecting such an integer is "(int)(256*Math.random())". So the random color subroutine becomes:
static void changeToRandomColor(int rowNum, int colNum) { int red = (int)(256*Math.random()); int green = (int)(256*Math.random()); int blue = (int)(256*Math.random()); mosaic.setColor(rowNum,colNum,red,green,blue); }Finally, consider the randomMove subroutine, which is supposed to randomly move the disturbance up, down, left, or right. To make a random choice among four directions, we can choose a random integer in the range 0 to 3. If the integer is 0, move in one direction; if it is 1, move in another direction; and so on. The position of the disturbance is given by the variables currentRow and currentColumn. To "move up" means to subtract 1 from currentRow. This leaves open the question of what to do if currentRow becomes -1, which would put the disturbance above the window. Rather than let this happen, I decide to move the disturbance to the opposite edge of the applet by setting currentRow to 9. (Remember that the 10 rows are numbered from 0 to 9.) Moving the disturbance down, left, or right is handled similarly. If we use a switch statement to decide which direction to move, the code for randomMove becomes:
int directionNum; directoinNum = (int)(4*Math.random()); switch (directionNum) { case 0: // move up currentRow--; if (currentRow < 0) // CurrentRow is outside the mosaic; currentRow = 9; // move it to the opposite edge. break; case 1: // move right currentColumn++; if (currentColumn >= 20) currentColumn = 0; break; case 2: // move down currentRow++; if (currentRow >= 10) currentRow = 0; break; case 3: // move left currentColumn--; if (currentColumn < 0) currentColumn = 19; break; }Putting this all together, we get the following complete program. The variables currentRow and currentColumn are defined as static members of the class, rather than local variables, because each of them is used in several different subroutines. This program actually depends on two other classes, Mosaic and another class called MosaicCanvas that is used by Mosaic. If you want to compile and run this program, both of these classes must be available to the program.
public class RandomMosaicWalk { /* This program shows a window full of randomly colored squares. A "disturbance" moves randomly around in the window, randomly changing the color of each square that it visits. The program runs until the user closes the window. */ static int currentRow; // Row currently containing the disturbance static int currentColumn; // Column currently containing disturbance public static void main(String[] args) { // Main program creates the window, fills it with // random colors, then moves the disturbance in // a random walk around the window. Mosaic.open(10,20,10,10); fillWithRandomColors(); currentRow = 5; // start at center of window currentColumn = 10; while (Mosaic.isOpen()) { changeToRandomColor(currentRow, currentColumn); randomMove(); Mosaic.delay(20); } } // end of main() static void fillWithRandomColors() { // fill every square, in each row and column, // with a random color for (int row=0; row < 10; row++) { for (int column=0; column < 20; column++) { changeToRandomColor(row, column); } } } // end of fillWithRandomColors() static void changeToRandomColor(int rowNum, int colNum) { // Change the square in row number rowNum and // column number colNum to a random color. // Random colors in the range 0 to 255 are // chosen for the red, green, and blue components // of the color. int red = (int)(256*Math.random()); int green = (int)(256*Math.random()); int blue = (int)(256*Math.random()); Mosaic.setColor(rowNum,colNum,red,green,blue); } // end of changeToRandomColor() static void randomMove() { // Randomly move the disturbance in one of // four possible directions: up, down, left, or right; // if this moves the disturbance outside the window, // then move it to the opposite edge of the window. int directionNum; // Randomly set to 0, 1, 2, or 3 // to choose the direction. directionNum = (int)(4*Math.random()); switch (directionNum) { case 0: // move up currentRow--; if (currentRow < 0) currentRow = 9; break; case 1: // move right currentColumn++; if (currentColumn >= 20) currentColumn = 0; break; case 2: // move down currentRow++; if (currentRow >= 10) currentRow = 0; break; case 3: currentColumn--; if (currentColumn < 0) currentColumn = 19; break; } } // end of randomMove() } // end of class RandomMosaicWalk
[ Next Section | Previous Section | Chapter Index | Main Index ]