Mini-Lab: More Fish!

This set of Mini-Lab Exercises is the fourth in a series in which students build a small program with several fish moving around in an aquarium. The set includes the following exercises:

• We Want More!     (Patterns: Linear Indexed Data Structure and Fixed-Size Linear Data Structure)
• Fish Out of Water     (Patterns: Indexed Random Access and Valid Index)
• Home, Sweet Home     (Pattern: Linear Indexed Traversal)
• A School in Motion     (Nested Loops)
• Houdini Fish     (Complex Expressions)

Each section contains an Introduction to a problem or task, (usually) abridged versions of one or more Patterns that will be useful in solving the problem or completing the task, and an Exercise.

In the exercises that precede this one, students will have created three fish of various colors that move randomly back and forth in an aquarium, being careful not to hit the sides. Students should be familiar with basic for loops, simple selection statements, prompting for input, and the RandGen class.

We Want More!

Introduction

A better alternative would be to ask the user how many fish to place in the aquarium and then store them in a collection object. We can use a Linear Indexed Data Structure to store the collection of fish.

Pattern: Linear Indexed Data Structure (Container) -- Abridged

You are in a situation in which you need a collection of objects of a given type, such that at least one of the following conditions is true.

• You will want to be able to access arbitrary elements in the collection quickly. (For example, you might want to directly and quickly access the 5th element in the collection without stepping through the first 4 elements.)
• The order of the elements in the collection is unimportant.
• The order of the elements in the collection is important and elements will be added to the collection in order.
  See the complete Linear Indexed Data Structure pattern to see other conditions in which this pattern is appropriate.

Therefore, use an STL or Java Vector or String class, an apvector or apstring, or a built-in array. Patterns for building and using these structures include Fixed-Size Linear Data Structure, Expandable Linear Data Structure, Appended Item, and Linear Indexed Traversal.

---

Pattern: Fixed-Size Linear Data Structure (Linear Indexed Data Structure) -- Abridged

You are in a situation that calls for a Linear Indexed Data Structure and you know up front how many such objects there will be.

Therefore, specify the number of items that will be in the collection as you construct it. For example, the syntax for creating an apvector of known size whose elements are of type T is:

 apvector<T> V(nbrItems);

The syntax for creating an STL Vector of known capacity whose elements are of type T is essentially the same:

 Vector<T> V(nbrItems);

Note that whether the items in the collection are actually constructed and initialized when the data structure is constructed depends on the particular data structure and the type of the objects in it. In the case of C++ built-in arrays and apvectors, the data structure is filled to capacity with "default items" of the underlying data element type. If that type is a primitive type, the individual items are uninitialized. If the individual items are objects, they are constructed and initialized using the default constructor for their class. Whether these data elements are meaningful depends on the type of the objects, the behavior of the default constructor, and what the program wishes to do with the data items.

This pattern is described more fully in the complete Linear Indexed Data Structure Pattern.

  /*
        d.Show (fish1);
        .
        .    more code to display and move fish
        .
        d.Show (fish3);
   */

Fish Out of Water

Introduction

To solve this problem, we will replace the default AquaFish in the apvector with properly constructed AquaFish. Then we will partially test our modified code by displaying some fish. Rather than trying to replace and display all the fish in the aquarium right away, though, we will start by concentrating on the first and last fish in the collection. We can no longer refer to each fish by name, but we can use an Indexed Random Access to refer to any particular fish in our Linear Indexed Data Structure.

Pattern: Indexed Random Access (Linear Indexed Data Structure) -- Abridged

You want to access (retrieve or set) a specified entry in a Linear Indexed Data Structure.

Therefore, access it directly, specifying the index of the desired entry. The index should be a Valid Index for the specific Linear Indexed Data Structure.

For example, if deck is an STL Vector of playing cards, then one might use the following statement to display the 1st card in the deck (provided that there is at least 1 card in the deck):

 deck[0].display();

One could display the 6th card just as easily (provided that there are at least 6 cards in the deck):

 deck[5].display();

(Note that indexing of Linear Indexed Data Structures in C, C++, and Java, along with some other languages, begins at 0. See Valid Index for more details.)

This pattern can also be used to modify an element in the data structure. For example, to swap the 1st and 52nd cards in the deck, the following code might be used:

Card temp = deck[0];          // temp is 1st card
deck[0] = deck[51];           // 1st card is now same as 52nd card
deck[51] = temp;              // 52nd card is now old 1st card

---

Pattern: Valid Index (Linear Indexed Data Structure) -- Abridged

You want to access a valid element in a Linear Indexed Data Structure.

Therefore, use an index in the range determined by the programming language and the size of the data structure. In many languages, such as C, C++, and Java, valid indices for a structure with N elements ranges from 0 to N-1, where 0 is the index of the 1st element in the Linear Indexed Data Structure and N-1 is the index of the last element. In other languages, such as Pascal, valid indices for a Linear Indexed Data Structure with N elements ranges from 1 to N.

How to determine the size of a data structure (the number of elements in it) also depends on the language and the particular data structure. For example, if your data structure V is an STL or Java Vector, then you can use

 V.size()

to obtain the number of elements.

Technically, the "number of elements" in a built-in array or apvector depends on its capacity (which depends only on the amount of memory that has been allocated to it). In fact, when a built-in array or apvector is constructed, it is filled with objects created using the default constructor for that type. Whether these are meaningful data elements or not depends on the type of the objects and what the program wishes to do with them. For an apvector V, you can use

 V.length()

to refer to its capacity. If the capacity of the data structure is larger than the number of meaningful elements put into it, then the program must keep track of the number of meaningful elements separately.

This pattern is described more fully in the complete Linear Indexed Data Structure Pattern.

       fishList[0] = AquaFish (aqua, "Red");

Home, Sweet Home

Introduction

Linear Indexed Traversal (Repetition) -- Abridged

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 the number of elements in the Linear Indexed Data Structure.

Therefore, use a FOR statement in which the loop control variable is the 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 does not go beyond the last element in the data structure.

The common idiom for Linear Indexed Traversal in the C-based languages (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 V[i]
}

If your data structure V is an STL or Java String or Vector, an apstring, or 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) 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();
}

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 = 0; i < hand.size(); i++)
{       hand[i] = CardDeck.dealCard();
}

The code to add new cards to an empty built-in array or apvector of sufficient capacity would be similar, except that hand.size() would be replaced with the number of cards to add. See the Expandable Linear Data Structure pattern for details on ensuring sufficient capacity for an array or apvector, covered in the complete Linear Indexed Data Structure pattern.

Note the condition in the FOR loop: i < N. This is the common idiom used to ensure that the index i never refers to an element beyond the last one 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!
{       hand[i].DisplayCard();
}

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!
{       hand[i].DisplayCard();
}

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. This alternative, and other types of Repetition, are described in the complete Repetition Pattern.

A School in Motion

Introduction

It seems clear that we will want to loop through the steps in the simulation, as we are already doing. It also seems clear that we will want to loop through all the fish. The question is:

• Should we do one after the other? If so, which should we do first?
• Or, should we do one as part of (inside) the other? If so, which goes inside which?

Processing all the fish and all the steps in the simulation are not independent of one another. That is, we can't process all the fish and then process all the simulation steps, or vice versa. Either processing all the fish is part of what we do in one step of the simulation, or running all the steps of the simulation is part of what we do for each fish. Thus, we will need to nest one of the loops inside the other.

To decide which loop gets nested inside of which, consider the following algorithmic structures in which we assume that we have 25 fish in the aquarium and we want to run the simulation 100 times.

We do not want the first fish to move 100 times, followed by the second fish moving 100 times, followed by the third fish moving 100 times. Instead, we want all 25 fish to move once, then all 25 fish to move again. This corresponds to the second solution above.

Another question we have to consider is where the display of the aquarium should be relative to the fish movement. Do we want to display the fish and aquarium in the outer loop (as part of each simulation step), or in the inner loop (as part of processing each fish)? The following table illustrates these two options.

Which behavior do you wish to implement?

Houdini Fish

Introduction

Our aquarium program has a subtle logic error that may have gone unnoticed when we had fewer fish. Fish in this program are always constructed facing right, so any fish constructed at the left wall of the aquarium will not be facing the wall. Thus, it will not automatically change direction before moving forward. Like any other fish that is not facing a wall, though, it may randomly choose to change direction before moving forward, in which case it will turn around and swim right through the left aquarium wall. We need to fix the logic in our program to prevent such "Houdini fish" from escaping.