Section 3.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 2.5, 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, that 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. This 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 a have found an already-written class called MosaicFrame. This class allows a program to work with windows that display little colored squares arranged in rows and columns. The documentation for the class includes the following information:
A programmer who wants to use a MosaicFrame in a program should include the following line in the main program class:
static MosaicFrame mosaic = new MosaicFrame(R,C);
where R and C are integers specifying how many rows and columns of squares should be displayed in the window. This line creates the window and gives it the name mosaic. The rows of the mosaic are numbered from 0 to R-1, and the columns are numbered from 0 to C-1. (The mosaic is actually an object, so you won't understand exactly what this line does until you read the next chapter.)
To change the color of one of the squares in the window, the programmer can use the subroutine call statement "mosaic.setColor(row,col,r,g,b);". The first two parameters, row and col are integers that give the row number and the column number of the square whose color is to be set. 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 user will be able to close the window by clicking in its closebox. A program that needs to know whether the window is still open can call the boolean-valued function mosaic.stillOpen(). This method returns true if the window is open and returns false if the user has closed the window.
The subroutine call "mosaic.delay(millis);" can be used to insert a 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.
The documentation discusses other subroutines, but these are the ones that are useful for the project I have in mind. My idea is to use the MosaicFrame class as the basis for a neat animation. The idea is to fill the window with randomly colored squares, and then to 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 neat to have a "disturbance" that wanders randomly around the window, changing the color of each square that it encounters.
With basic routines for manipulating the window in hand as a foundation, I can turn to the specific problem at hand. A basic outline for my program is
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:
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. For the sake of good programming style, let's represent the number of rows and the number of columns in the mosaic with constants named ROWS and COLUMNS. I already have a method, mosaic.stillOpen(), to test whether the window is open. I decide to write two more subroutines of my own to carry out the last two tasks in the pseudocode. The algorithm can then be written in Java as:
fillWithRandomColors(); currentRow = ROWS / 2; // middle row, halfway down the window currentColumn = COLUMNS / 2; // middle column while (mosaic.stillOpen()) { 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(10);" 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 < ROWS; row++) for (int column = 0; column < COLUMNS; 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())". (See the discussion in Section 2.7 about using type casts to pick random integers.) 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 ROWS-1. 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 = (int)(4*Math.random()); switch (directionNum) { case 0: // move up currentRow--; if (currentRow < 0) // currentRow is outside the mosaic; currentRow = ROWS - 1; // move it to the opposite edge break; case 1: // move right currentColumn++; if (currentColumn >= COLUMNS) currentColumn = 0; break; case 2: // move down currentRow ++; if (currentRow >= ROWS) currentRow = 0; break; case 3: // move left currentColumn--; if (currentColumn < 0) currentColumn = COLUMNS - 1; break; }Putting this all together, we get the following complete program. Note that I've defined ROWS and COLUMNS as constants. The variables mosaic, 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.
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 in an infinite loop, and so will never end on its own. */ final static int ROWS = 10; // number of rows of squares // (The rows of squares are numbered from 0 to ROWS-1) final static int COLUMNS = 20; // number of columns of squares // (The columns of squares are numbered from 0 to COLUMNS-1) static MosaicFrame mosaic = new MosaicFrame(ROWS,COLUMNS); // the actual 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. fillWithRandomColors(); currentRow = ROWS / 2; // start at center of window currentColumn = COLUMNS / 2; while (mosaic.stillOpen()) { changeToRandomColor(currentRow, currentColumn); randomMove(); mosaic.delay(10); } } // end of main() static void fillWithRandomColors() { // fill every square, in each row and column, // with a random color for (int row=0; row < ROWS; row++) { for (int column=0; column < COLUMNS; 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. int red = (int)(256*Math.random()); // choose random levels in range int green = (int)(256*Math.random()); // 0 to 255 for red, green, int blue = (int)(256*Math.random()); // and blue color components 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 = (int)(4*Math.random()); // directionNum is randomly set to 0, 1, 2, or 3 switch (directionNum) { case 0: // move up currentRow--; if (currentRow < 0) currentRow = ROWS - 1; break; case 1: // move right currentColumn++; if (currentColumn >= COLUMNS) currentColumn = 0; break; case 2: // move down currentRow ++; if (currentRow >= ROWS) currentRow = 0; break; case 3: // move left currentColumn--; if (currentColumn < 0) currentColumn = COLUMNS - 1; break; } } // end of randomMove() } // end of class RandomMosaicWalk
End of Chapter 3
[ Next Chapter | Previous Section | Chapter Index | Main Index ]