# Mini-Lab: More Fish!

Using Vectors

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:

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 more realistic simulation of an aquarium would have more than two or three fish. We could modify the simulation so that it supports four fish, five fish, or twelve fish, but if we "hard-code" the number of fish into program in this way, then we must modify and re-compile the program to change the number of fish in the aquarium. We must also repeat statements, such as the code to display and move fish, four, five, or twelve times.

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.

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.

#### Exercise

Prompt the user for the number of fish they want in the aquarium. Replace the three fish you constructed earlier with a Fixed-Size Linear Data Structure of the right size to store the number of fish the user wants. What does this data structure represent? Choose a Role-Indicating Name for it. Don't forget to include the appropriate header file (`apvector.h`).

#### Stop and Think

Where should you construct the data structure representing the collection of fish? Do you need to know the size when you construct it? When do you know the size?

It is always difficult to test modified code part-way through the change. At this point, you have constructed a variable-sized collection of fish rather than three specific fish, but the rest of your program still expects three named fish. In order to test that you have not introduced any syntax errors into your program, "comment out" the code that displays and moves the three fish (who no longer exist) by placing the appropriate code in comments. For example,

``````  /*
d.Show (fish1);
.
.    more code to display and move fish
.
d.Show (fish3);
*/
``````
(Don't be surprised when your program no longer moves or displays fish!)

## Fish Out of Water

### Introduction

Until now, we've been creating our fish in the context of an aquarium (so that they have a valid position). We've done this by passing the aquarium object to the AquaFish constructor. The individual objects in a Fixed-Size Linear Data Structure, however, are constructed with the default constructor, that is, the constructor that doesn't take any parameters. This means that our fish aren't in an aquarium and there are a number of AquaFish methods that we can't use with them. (We see this by looking at the precondition on the AquaFish XCoord, YCoord, MoveForward, and ChangeDir methods; fish must be in an aquarium before these methods are called.)

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.

#### Exercise

The default fish in the new `apvector` of fish are useless to us because they are not in an aquarium. You will want to replace them immediately with fish created with the appropriate constructor. Rather than replacing them all, however, we will focus on just replacing the first and last fish in the collection in order to practice using Indexed Random Access into a Linear Indexed Data Structure.

Modify your program to replace the first and last fish in your collection with a properly constructed and initialized AquaFish with appropriate constructor parameters. You can do this using the following syntax (assuming that you named your collection fishList):

``````       fishList[0] = AquaFish (aqua, "Red");
``````
(Question: What is the index of the last fish in the collection?)

Next, remove the comments around the initial display of the aquarium and fish. Replace the statements displaying the three named fish with statements displaying the first and last fish in the collection. If you are using a graphics display, you may want to change your call to Pause back to WaitNClear. (Or just comment out the call to Pause, since you will probably want to go back to it later.)

NOTE: Keep the comments around the code that moves fish and redisplays them.

## Home, Sweet Home

### Introduction

Now let's replace all the fish. We can use a Linear Indexed Traversal to step through and process each item in our Linear Indexed Data Structure.

### 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.

#### Exercise

Step through the Linear Indexed Data Structure of fish using Linear Indexed Traversal, and set each one to be a newly constructed fish, initialized with both the aquarium and a color. (For now, you may set all the fish to a single color.)

Research the Display interface to discover how to display an indexed collection of fish. Update the initial display of fish in the aquarium to display all the fish in the collection. Test that the initial display works.

## A School in Motion

### Introduction

Now let's think about how to move and display all the fish for as many time steps as the user wants.

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.

 For each fish in the collection:         Move 100 times and display the aquarium. For each step in the simulation:         Move the 25 fish once and display the aquarium.

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.

 For each step in the simulation:         For each fish in the collection:                 Move, possibly changing direction.         Display aquarium & fish. For each step in the simulation:         For each fish in the collection:                 Move, possibly changing direction.                 Display aquarium & fish.

Which behavior do you wish to implement?

#### Exercise

Remove the remaining comments around the code that runs through the steps of the simulation, moving and displaying the fish in the aquarium.

Inside the simulation loop, replace the code that moves the three named fish with a loop that will move all the fish in your collection. (Each will still change direction when it has to or when it randomly chooses to.) Use a Linear Indexed Traversal through your Linear Indexed Data Structure of fish.

Display all the fish in the aquarium with a single statement, as you did at the beginning of the program. Where does this statement (along with the redisplay of the actual aquarium and the call to Pause or WaitNClear) belong? Should it be part of the inner or outer loop?

## Houdini Fish

### Introduction

As you have tested the programs you have written, you have undoubtedly encountered syntax errors. These are errors that the compiler can catch for you, such as misspelled variable names or missing parentheses and semi-colons. It is also possible for a program to have logic errors. A program with logic errors will correctly compile, and will even correctly do what you programmed it to do, but what you programmed it to do is not what you meant for it to do.

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.

#### Exercise

Run your program several times, until you witness the logic error described above. For example, run the simulation for 3 - 5 steps (or even 1 step) with 25 fish. You may see the error immediately, or you may have to run the program 5 - 10 times. (If you always get the same 25 fish in the same locations, then you have initialized your random number generator with a seed. Double-check the RandGen interface, and modify your program to construct your random number generator without a seed.)

Modify your program to correct the logic that controls whether a fish changes direction before moving forward. A fish should change direction if either of the following conditions is true.

• It is facing a wall and, thus, cannot move forward in the current direction.
• It is not against a wall and it randomly chooses to change direction.
The logic for this condition embodies both an OR condition and an AND condition, so you will need to be careful about how you construct the selection statement and the logical expressions in it.