Encapsulation Pattern: Nested Loops Pattern Name: Encapsulation Pattern: Inner Loop Author




Дата канвертавання22.04.2016
Памер36 Kb.

Encapsulation Pattern: Nested Loops

Pattern Name:


Encapsulation Pattern: Inner Loop
Author:

Viera K. Proulx


Intent and Motivation:

Often the program requires that we repeat a task that itself contains repetition. For example, writing a table of numbers consists of the task to write a row of numbers (repeating the same operation for each number) that is repeated for every row. We can think of it as a loop nested inside another loop (the terminology names them the outer loop and the inner loop).

The design of this kind of repetition can be quite confusing. Sometimes the design of the loop control is not trivial, or the outer loop needs to perform some other tasks before the inner loop is performed. In that case it is best to separate the two loops by writing a function that encapsulates the inner loop.
Problem Examples:


  1. Paint a wallpaper design repeating the same image across each row for several rows.

  2. Print a multiplication table.

  3. Print a grading sheet with student name, grades for assignments, totals in the last column.


Problem and Context:

When designing a nested loop make sure you design each loop independently. Often, the considerations related to the design of the inner loop interfere with thinking about the outer loop. At that point it is best to imagine that the entire problem of performing the inner loop can be done exactly as we want it, and design the outer loop on that assumption. That sets the stage for designing the inner loop to the correct specifications - as a separate function.


Required Elements and Structure:

Nested loop requires that we design the loop control for the outer loop as well as the loop control structure for the inner loop. Often, the counting method for the inner loop is dependent on the outer loop. It is very difficult to read code with all but simplest nested loops. As a result, it is also very difficult to make sure that each loop performs the desired task. Good programmers almost always encapsulate the task of the inner loop in a separate function.

When designing the function that performs the inner loop task, we must identify clearly how what is the nature of repetition in the inner loop, how are the bounds and increments (or updates) determined and what initialization and post-mortem operations are a natural part of the inner loop. Once the design is competed, the outer loop only needs to perform the appropriate function call.

Implementation Examples:

Example 1;

We are asked to print n rows with m stars in each row. This requires an outer loop that prints n rows and the inner loop that prints m stars in each row (across m columns).
Our first attempt at the solution would be:

for (int row = 1; row <= n; row++){

for (int col = 1; col <=m; col++){

cout << "*";

};

};
However, here all the m * n stars would be printed in one line. The outer loop needs to perform two tasks: print a line of stars and advance to the next line. This can be done directly:


for (int row = 1; row <= n; row++){

// Print one line of stars

for (int col = 1; col <= m; col++){

cout << "*";

};

//Advance to the next line



cout << endl;

};
or we can write a function to print one line as follows:

void PrintStars(int m){

for (int col = 1; col <= m; col++){

cout << "*";

};

};


for (int row = 1; row <= n; row++){

PrintStars(m); // Print one line of stars

cout << endl; //Advance to the next line

};
We see that even in this simple case it is easier to read and verify correctness of the second solution. Typically the outer loop has other responsibilities besides invoking the inner loop. By delegating the responsibility for the inner loop to a separate function, the flow of thought for the designer and for the reader focuses on one task at a time.


Example 2;

In this example we print the multiplication table. Again, the task is straightforward. However, we want to include the row and column labels in the printout. We start with printing the header line. This is a separate loop - traversing over the line, printing each number with proper spacing. Next we design one line of the actual table. It starts with the number whose multiples will be printed, followed by the formatted sequence of multiples, followed by the advance to the next line and printing of a separator line. Even in this simple example, the outer loop has three tasks: print the line header, print the line contents, print a separator line. Note, that the function that will print the row of multiples needs to know which row is being printed. We decided to give the function PrintRow the responsibility for the final end of line. So the code will be:


// main program:

PrintLineHeader(); // print the header line

PrintLineSeparator(); // Advance to the next line

for (int row = 1; row <= 10; row++){

cout << setw(4) <

PrintRow(row); // Print one line of multiples

PrintLineSeparator(); // Advance to the next line

};

};


void PrintRow(int m){ // print row of multiples of m

for (int i = 1; i <= 10; i++){

cout << setw(4) << m * i << " |";

};

cout << endl; // post-mortem appropriate here



};
void PrintLineHeader(){

cout << "******||"; // No header for the first column

for (int i = 1; i <=10; i++){

cout << setw(4) << i << " |";

};

cout << endl; // post-mortem appropriate here



};
void PrintLineSeparator(){

cout << "------||";

for (int i = 1; i <=10; i++){

cout << "------" << "+";

};

cout << endl;



};

The output would look as follows:


******|| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

------||------+------+------+------+------+------+------+------+------+------+

1 || 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

------||------+------+------+------+------+------+------+------+------+------+

2 || 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 |

------||------+------+------+------+------+------+------+------+------+------+

3 || 3 | 6 | 9 | 12 | 15 | 18 | 21 | 24 | 27 | 30 |

------||------+------+------+------+------+------+------+------+------+------+

4 || 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 | 40 |

------||------+------+------+------+------+------+------+------+------+------+

5 || 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 |

------||------+------+------+------+------+------+------+------+------+------+

6 || 6 | 12 | 18 | 24 | 30 | 36 | 42 | 48 | 54 | 60 |

------||------+------+------+------+------+------+------+------+------+------+

7 || 7 | 14 | 21 | 28 | 35 | 42 | 49 | 56 | 63 | 70 |

------||------+------+------+------+------+------+------+------+------+------+

8 || 8 | 16 | 24 | 32 | 40 | 48 | 56 | 64 | 72 | 80 |

------||------+------+------+------+------+------+------+------+------+------+

9 || 9 | 18 | 27 | 36 | 45 | 54 | 63 | 72 | 81 | 90 |

------||------+------+------+------+------+------+------+------+------+------+

10 || 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 |

------||------+------+------+------+------+------+------+------+------+------+


Example 3.

This is a series of exercises that involve a combination of several loops inside the main loop and exhibit iteration dependencies.

The goal is to print the following four patterns of stars:

* * * * * * * * * * * *

* * * * * * * * * * * *

* * * * * * * * * * * *

* * * * * * * * * * * *

* * * * * * * * * * * *



A B C D
The user selects how many rows will be printed. In this case user selected five rows. To solve the problem write down the columns of numbers that tell us how many stars are in each row. We discover for Pattern 1 that there are k stars in row k. The program follows:

void PatternA(int n){

// There are k stars in row k, starting on the left.

// *


// * *

// * * *
for (int k = 1; k <= n; k++){

// print k stars in this row

for (int col = 1; col <= k; col++){

cout << "* ";

};

// advance to the next line



cout << endl;

};

PressReturn("Pattern A Completed");



};
In Pattern B, using the same strategy, we realize that in row one there are n stars, in row 2 there are n - 1 stars, in row 3 there are n - 3 stars - deriving a formula that there are n + 1 - k stars in row k:

void PatternB(int n){

// There are n + 1 - k stars in row k, starting on the left.

// * * *


// * *

// *


for (int k = 1; k <= n; k++){

// print n + 1 - k stars in this row

for (int col = 1; col <= n + 1 - k; col++){

cout << "* ";

};

// advance to the next line



cout << endl;

};

PressReturn("Pattern B Completed");


};

In the Pattern C the stars do not start on the left. We need to find out how many spaces have to be printed before the star pattern starts. We see right away that the number of the stars in Pattern C is the same as the number of stars in Pattern A and similarly, the number of stars in Pattern D is the same as the number of stars in Pattern B. If we write two functions PrintStars(int cnt) and PrintBlanks(int cnt) the problem is almost solved. We only need to realize that there are n - k blanks in row k of Pattern C and k - 1 blanks is row k of Pattern D.

void PrintStars(int cnt){

for (int i = 1; i <= cnt; i++){

cout << "* ";

};


};
void PrintBlanks(int cnt){

for (int i = 1; i <= cnt; i++){

cout << " ";

};

};


void PatternC(int n){

// There are n - k blanks in row k, starting on the left

// followed by k stars

// (we used + signs to show where the stars are missing)

// + + + *

// + + * *

// + * * *

// * * * *

for (int k = 1; k <= n; k++){

PrintBlanks(n - k); // print n - k blanks in this row

PrintStars(k); // print k stars in this row

cout << endl; // advance to the next line

};

PressReturn("Pattern C Completed");



};

void PatternD(int n){

// There are k - 1 blanks in row k

// followed by n + 1 - k stars

// * * * *

// + * * *

// + + * *

// + + + *

for (int k = 1; k <= n; k++){

PrintBlanks(k - 1); // print k - 1 blanks in row k

PrintStars(n + 1 - k); // print n + 1 - k stars row k

cout << endl; // advance to the next line

};

PressReturn("Pattern D Completed");



};
If we compare the code for the first two patterns with the code for the last two patterns we see that even though the last two patterns are harder, the code is easier to read. We can even verify readily that in each row we printed n items (stars and spaces).

Note: The two functions PrintBlanks and PrintStars are identical except for the character they print (a star or a blank). They can be combined into one function PrintChars(char c, int cnt) that will print cnt characters c.


Forces and Variations:

Nested loops with while statements

Triply nested loops

Arrays of arrays


Summary:

When a repeated task itself contains a repetition, the design of the loop control structure can be quite complex. Often the main repetition consists of several tasks, only one of which is a task with repetition within it. To make the program readable and to help the designer in focusing on the key design issues, it is nearly always better to encapsulate the inner loop as a separate function.




File Name: EncapsulateLoop.doc Page Sept 99



База данных защищена авторским правом ©shkola.of.by 2016
звярнуцца да адміністрацыі

    Галоўная старонка