This document will be a collection of elementary patterns by various authors to use in writing code that requires repeating actions.

The Repetition patterns are:

• For/Repeat: Repetition with Well-defined Step
• While/Do-while: General Repetition
• Recursive Repetition
• Overall Loop Patterns

For/Repeat: Repetition with Well-defined Step
General pattern for repetition with a well-defined step to the next iteration
EXCEPTION: Well-defined step that is equivalent to the initialization (implemented as a while-loop)

Special Cases:

• Counted Repetition, Reverse Counted Repetition (Brady)
  
  Special Cases: Linear Indexed Traversal, Reverse Linear Indexed Traversal (Brady), 2-D Indexed Traversal
  Note: Astrachan and Wallingford's Definite Process All Items is similar to my Linear Indexed Traversal.
• Linear Linked Traversal
• Iterator Process All Items (Astrachan & Wallingford)
• Linear Search, Guarded Linear Search (Astrachan & Wallingford)
• Extreme Values (Astrachan & Wallingford) -- find max/min in a collection
• etc.

While/Do-while: General Repetition (good name?)
General pattern for repetition

Special Cases:

• Loop and a Half, Polling Loop (Astrachan & Wallingford)
• Infinite Loop, Infinite Loop Until Exception/Event
• Step In Body (e.g., binary search) -- i.e., Step depends on calculations in body, or step is purpose of body
• Step In Condition (e.g., while ((c = getchar()) != EOF)
• Step Equals Init (Don't Repeat Code implies while-loop rather than for-loop)
• Execution At Least Once
• etc.

Recursive Repetition:

• Roundabout (Wallingford)

Overall Loop Patterns:

• One Loop for Linear Structures (Astrachan & Wallingford)
• Loop Invariant/Loop Initialization (Astrachan & Wallingford)

Counted Repetition (Repetition)

You are in a situation in which some action should be repeated a known number (N) of times, where N might be a constant number or a value in a variable. The number of repetitions does not depend on any aspect of the repeated action, i.e., you know the value of N before you start the repetition.

Therefore, use a FOR statement that creates a variable to count the number of times the action has been repeated. The counting variable is created and initialized and then, so long as the action has not been repeated too many times (the "test"), the action is done and the count is incremented (the "step"). Express the test as a Positive Condition if possible.

The structure of a FOR loop is:

 for (initialization ; condition ; step)
        <repeated action>

Need text that recommends FOR statement in C-based languages, REPEAT statement in languages that support that construct. Repeat statements, in particular, are "safer" than while loops because the initialization and step are automatic (or have automatic defaults). C-ish FOR loops are also "safer" because they make the critical initialization and step aspects of the loop control explicit and up-front (follows Local Variables Reassigned Above Their Uses (Gabriel)).

There are two common idioms for controlling the loop. The first is to count from 0 to N-1, which is the idiom used to ensure a Valid Index in a Linear Indexed Traversal (see below for more details). For example, at the beginning of a card game each player is dealt a hand of cards:

for (int i = 0; i < nbrPlayers; i++)
{       dealHand();
}

[Future: Describe: Under what circumstances do you declare i as part of the initialization in the for loop?]

The second common idiom for controlling the loop is to count from 1 to N. For example,

for (int i = 1; i <= nbrPlayers; i++)
{       dealHand();
}

You might choose to use the second alternative because it corresponds more closely with counting. On the other hand, the Linear Indexed Traversal pattern is a very common, and important, pattern because it is used to step through one of the most common data structures.

WARNING: It is important to note that your loop will have an off-by-one boundary error if you mix the two idioms. If, for example, you write

for (int i = 0; i <= nbrPlayers; i++)             INCORRECT!
{       dealHand();
}

your action will be repeated nbrPlayers+1 times, not nbrPlayers times. If, on the other hand, you write

for (int i = 1; i < nbrPlayers; i++)              INCORRECT!
{       dealHand();
}

your action will be repeated nbrPlayers-1 times. To avoid these kinds of mistakes many people find it easiest to consistently use the Linear Indexed Traversal
(i = 0; i < N; i++)
pattern for counting as well as for accessing indexable structures.

Another alternative is to count down rather than counting up. This alternative is the Reverse Counted Repetition Pattern.

Reverse Counted Repetition (Repetition)

You are in a situation in which a Counted Repetition is appropriate, but it is important that you count down as you repeat the action.

Therefore, use a FOR statement that creates a counting variable that is initialized to the high end of its range and is decremented in the loop "step." The loop condition should test whether the counting variable has reached the low end of its range. Express the test as a Positive Condition if possible.

There are two possible idioms for controlling the loop, similar to the loop control idioms in Counted Repetition. The first, which is analagous to Reverse Linear Indexed Traversal is to count from N-1 to 0.

For example, [Need example!]

The second obvious idiom for controlling the loop is to count from N to 1. For example, [Need example!]

The likelihood for error if you do not consistently stick with one idiom is similar to that with Counted Repetition. To avoid these types of errors many people find it easiest to consistently use the Reverse Linear Indexed Traversal pattern for counting down as well as for accessing indexable structures in reverse order.

Linear Indexed Traversal (Repetition)

Author: Alyce Faulstich Brady

You need to access (add, set, or retrieve) all entries of a Linear Indexed Data Structure exactly once, and, if the order matters, from first to last. You know or can determine the number of elements in the Linear Indexed Data Structure in constant time.

Note that the loop control idioms and examples in this pattern are currently all C-based, i.e., they assume that valid indices range from 0 to N-1.

Therefore, use a FOR statement in which the loop control variable is a Valid Index into the linear data structure. The variable should be initialized to the index of the first element in the linear data structure, the step should increment the index by one, and the test should make sure that the index is not used in the loop body if it goes beyond the last element in the data structure.
(If your data structure is an STL or Java Vector, do not use this pattern to add new entries to the structure; use the Appended Item instead.)

The common idiom for Linear Indexed Traversal to ensure a Valid Index in a C-based language (C, C++, Objective C, Java, etc.), assuming that V is the linear indexed data structure and N is the number of elements to be accessed in V, is

for (int i = 0; i < N; i++)
{       // body of loop accesses or sets the element at index i in V
}

If your data structure V is an STL or Java Vector, or if it is a full apvector (that is, the size of the vector accurately describes the number of meaningful entries in it), then you should use V.size() (STL or Java Vector) or V.length() (apvector) for N. If your data structure is a built-in array, or if the size of an apvector is larger than the actual number of (meaningful) elements in it, then you must keep track of the number of elements as a separate variable.

For example, if hand is an STL Vector of playing cards, then one might use the following loop to display the cards in the hand:

for (int i = 0; i < hand.size(); i++)
{       hand[i].displayCard();
}

for (int i = 0; i < hand.size(); i++)
{       ((Card)hand.elementAt(i)).displayCard();
}

This pattern could also be used to modify the value of elements of the collection. For example, to replace existing cards in the hand with new cards obtained from a CardDeck object, deck, the following C++ code might be used:

for (int i = 0; i < hand.size(); i++)
{       hand[i] = deck.dealCard();
}

for (int i = 0; i < hand.size(); i++)
{       hand.setElementAt(deck.dealCard(), i);
}

Note the condition in the FOR loop: i < N. This is the common idiom in C-based languages to ensure that the index i is always a Valid Index inside the loop. Another, logically equivalent, condition would be i <= N-1, but the common idiom is more succinct, possibly more efficient (depending on your compiler), and draws attention more clearly to the number of elements in the structure (N).

WARNING: It is important to note that your loop will have an off-by-one boundary error if you mix the logical expression of one condition with the stopping point of the other. If, for example, you write

for (int i = 0; i <= hand.size(); i++)              INCORRECT!
{       // code to display a single card
}

you will attempt to display one card too many, going beyond the range of the data structure. If, on the other hand, you write

for (int i = 0; i < hand.size() - 1; i++)           INCORRECT!
{       // code to display a single card
}

you will not display the last card. To avoid these kinds of errors, consistently use the common idiom for Linear Indexed Traversal:
(i = 0; i < N; i++)

See Reverse Linear Indexed Traversal if you need to access all the entries of an indexed data structure from last to first.

Reverse Linear Indexed Traversal (Repetition)

You need to access (add, set, or retrieve) all entries of a Linear Indexed Data Structure exactly once from last to first.

Note that the loop control idioms and examples in this pattern are currently all C-based, i.e., they assume that valid indices range from 0 to N-1.

Therefore, use a FOR statement in which the loop control variable is a Valid Index into the linear data structure. The variable should be initialized to the index of the last element in the linear data structure, the step should decrement the index by one, and the test should make sure that the index is not used in the loop body if it goes "in front of" the first element in the data structure.

The common idiom for Reverse Linear Indexed Traversal to ensure a Valid Index in a C-based language (C, C++, Objective C, Java, etc.), assuming that V is the linear indexed data structure and N is the number of elements to be accessed in V, is

for (int i = N - 1; i >= 0; i--)
{       // body of loop accesses or sets V[i]
}

If your data structure V is an STL or Java Vector, or if it is a full apvector (that is, the size of the vector accurately describes the number of meaningful entries in it), then you should use V.size() (STL or Java Vector) or V.length() (apvector) for N. If your data structure is a built-in array, or if the size of an apvector is larger than the actual number of (meaningful) elements in it, then you must keep track of the number of elements as a separate variable.

For example, if hand is an STL Vector of playing cards, then one might use the following loop to display the cards in the hand in reverse order:

for (int i = hand.size() - 1; i >= 0; i--)
{       hand[i].DisplayCard();
}

for (int i = hand.size() - 1; i >= 0; i--)
{       hand.elementAt(i).DisplayCard();
}

This pattern could also be used to modify the value of elements of the collection. For example, to replace existing cards in the hand with new cards obtained from a CardDeck object, the following C++ code might be used:

for (int i = hand.size() - 1; i >= 0; i--)
{       hand[i] = CardDeck.dealCard();
}

for (int i = hand.size() - 1; i >= 0; i--)
{       hand.setElementAt(CardDeck.dealCard(), i);
}

Note the condition in the FOR loop: i >= N - 1. This is the common idiom in C-based languages to ensure that the index i is a Valid Index. Another, logically equivalent, condition would be i > -1, but the former idiom is more common because it is expressed in terms of the lowest Valid Index rather than a non-valid index.

WARNING: It is important to note that your loop will have an off-by-one boundary error if you mix the logical expression of one condition with the stopping point of the other. If, for example, you write

for (int i = hand.size() - 1; i >= -1; i--)              INCORRECT!
{       hand[i].DisplayCard();
}

you will attempt to display one card too many, going beyond the range of a Valid Index. If, on the other hand, you write

for (int i = hand.size() - 1; i > 0; i--)                INCORRECT!
{       hand[i].DisplayCard();
}

you will not display the first card. To avoid these kinds of errors, consistently use the common idiom for Reverse Linear Indexed Traversal:
(i = N - 1; i >= 0; i--)

See Linear Indexed Traversal if you need to access all the entries of an indexed data structure from first to last.