Aquarium Lab Series

Mini-Lab: More Fish!

Using Arrays

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:

Becoming a Collector (Patterns: Linear Indexed Data Structure and Fixed-Size Linear Indexed Data Structure)
Bringing Home the Catch (Patterns: Indexed Random Access and Valid Index)
Loopy Fish (Pattern: Linear Indexed Traversal)
A School in Motion

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 that move randomly back and forth in an aquarium, being careful not to hit the sides. Students should be familiar with constructing objects, invoking methods, simple selection statements, basic for loops, and the Random class.

Students should read over the patterns that appear in this document before the lab.

Becoming a Collector

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 in that many variables, but if we "hard-code" the number of fish into the 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 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 a Linear Indexed Data Structure. Examples include Java arrays, the Java ArrayList class, and the Java String class. Patterns for building and using these structures include Fixed-Size Linear Data Structure, Expandable Linear Indexed Data Structure, Appended Item, and Linear Indexed Traversal.

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

Linear Indexed Data Structure

Therefore, declare and construct a fixed-size collection, initializing it to the appropriate size as you construct it using the Declare-Construct-Initialize pattern.

For example, the syntax for creating a Java array, deck, that will contain 52 references to objects of the Card class is:

Card[] deck = new Card[52];

More generally, the syntax for creating a Java array, anArray, with numItems references to objects of the class T is:

T[] anArray = new T[numItems];

This will actually construct an array that contains numItems null references. In order for it to contain numItems references to objects of type T, you will have to insert valid object references into the array using Indexed Random Access and Valid Index (see below).

The various Linear Indexed Data Structure patterns are described more fully in the complete Linear Indexed Data Structure Pattern.

Exercise

Modify your program to ask the graphical user interface to prompt the user for the number of fish as well as the number of simulation steps. Store the result in a local variable with an Intention Revealing Name.

Stop and Think
Where does it make sense to ask for the number of fish?
Replace the three fish you constructed earlier with a Fixed-Size Linear Indexed Data Structure of the right size to store the number of fish the user wants. What does this data structure represent? Choose an Intention Revealing Name for it.

It is always difficult to test modified code part-way through the change. At this point, you have constructed a collection that can contain fish but doesn't yet. The rest of your program, however, 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). Do this by placing the specified code in comments. For example,
Now compile your program just to make sure that you have created your fixed-size collection correctly. (Don't be surprised when your program no longer moves or displays fish!)

Bringing Home the Catch

Introduction

Of course, we don't see any fish, because we haven't created any. But we do have a container to hold them. When we create fish, we can put them directly into the Linear Indexed Data Structure.

How do we do this? And once we've put them there, how do we display one of them, or ask one for its color? We can no longer refer to each fish by name, but we can use the Indexed Random Access pattern to refer to any individual object in a Linear Indexed Data Structure. Rather than trying to create 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.

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 a Java array 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();

deck[5].display();

Linear Indexed Data Structures

Valid Index

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 range 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 range 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 myArray is a Java array, then you can use the expression myArray.length to obtain the number of elements. Actually, this gives you the capacity, or number of references, in the array. Whether these are null references or references to meaningful data elements depends on whether you have initialized the array. 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.

These patterns are described more fully in the complete Linear Indexed Data Structure Pattern.

Exercise

Modify your program to put two newly constructed fish in the first and last slots in your Fixed-Size Linear Indexed Data Structure. Construct them as you did before, but instead of putting them in named local variables, insert them in your array using the Indexed Random Access pattern.

Stop and Think
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. You may leave the code for moving the fish commented out for now.
Test your program to make sure that your program is correctly constructing and displaying two fish.

Loopy Fish

Introduction

One of the reasons we switched to using a collection object was to avoid having to duplicate code for each fish, but we currently have two lines to display the two fish. This will not scale up well if we want to put 25 fish in the aquarium! We can access all of the fish sequentially using the Linear Indexed Traversal pattern.

Linear Indexed Traversal (Repetition) -- Abridged

You need to access (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 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.

The common idiom for Linear Indexed Traversal through arrays in the C-based languages (C, C++, Objective C, Java, etc.) is

for (i = 0; i < N; i++)
{     // body of loop accesses or sets myArray[i]
}

i

int

myArray

N

If your data structure is a full Java array then you should use myArray.length for N. If the array's capacity is larger than the actual number of (meaningful) elements in it, then you should instead keep track of the number of elements as a separate variable. For example, if hand is a partially full Java array of playing cards with numCards cards in it, then one might use the following loop to display the cards in the hand:

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

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

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

Note the condition in the FOR loop: i < N (or, in this case, i < hand.length). 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:

off-by-one

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

for (int i = 0; i < hand.length - 1; i++)         INCORRECT!
{       hand[i].displayCard();
}

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 your Linear Indexed Data Structure using a Linear Indexed Traversal to put newly constructed fish in each slot. Even though the aquarium can now handle more fish than before, your code should be getting considerably shorter!
In the initial display of the aquarium and fish, replace the statements displaying the first and last fish in the collection with a Linear Indexed Traversal to display all fish. You may leave the code for moving the fish commented out for now.
Test your program to make sure that it correctly constructs and displays the number of fish specified by the user.

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. You may wish to create a temporary variable in the loop to refer to the fish being processed in this iteration rather than repeatedly retrieve the same fish from the Java array.
Display all the fish in the aquarium with a single statement. Research the abbreviated AquaSimGUI specification to discover how to display an indexed collection of fish. Note that this method will also display the aquarium, so you no longer need to do that separately (although you still need to "repaint" the interface and pause for the user to see the fish movement).

Stop and Think
Where does this statement belong? Should it be part of the inner or outer loop?
Update the initial display of fish in the aquarium also to display all the fish at once.
Test your modifications.
Make sure that you have updated the program documentation at the top of the file to reflect your changes.

Aquarium Lab Series

Mini-Lab: More Fish!

Becoming a Collector

Introduction

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

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

Exercise

Stop and Think

Bringing Home the Catch

Introduction

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

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

Exercise

Stop and Think

Loopy Fish

Introduction

Linear Indexed Traversal (Repetition) -- Abridged

Exercise

A School In Motion

Introduction

Exercise

Stop and Think