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 Expandable Linear Indexed Data Structure)
• Let's Go Fishing    (Patterns: Appended Item)
• Viewing 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 basic for loops, simple selection statements, prompting for input, and the Random class.

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

Becoming a Collector

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 a Linear Indexed Data Structure. Examples include the Java ArrayList class, Java String, or a built-in array. Patterns for building and using these structures include Expandable Linear Indexed Data Structure, Appended Item, and Linear Indexed Traversal.

---

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

You are in a situation that calls for a Linear Indexed Data Structure and you don't know up front how many objects it will need to hold.

Therefore, declare and construct an empty collection, using the Declare-Construct-Initialize pattern. Add Appended Items to the collections as necessary, using a method that resizes the collection automatically.

For example, the syntax for creating a Java ArrayList is:

ArrayList<Type> v = new ArrayList();

The <Type> portion indicates what type of object the ArrayList will hold. These patterns are described more fully in the complete Linear Indexed Data Structure Pattern.

Let's Go Fishing

Introduction

Pattern: Appended Item (Linear Indexed Data Structure) -- Abridged

You want to add an element to an Expandable Linear Indexed Data Structure. Either you don't care where in the list the item is put, or you want to add it as the last item.

Therefore, use a method that will append an object to the end of the collection.

For example, if deck is a Java ArrayList of playing cards, then the following statement adds a new Card to the end of the deck:

deck.add(new Card());

Notice that it is not necessary to create a new variable for each element in the collection. We refer to the individual object by specifying its location using Indexed Random Access rather than by using a unique variable name.

Of course, it is also possible to append an already existing object to a collection.

Card card1 = new Card();
deck.add(card1);

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

Viewing the Catch

Introduction

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 ArrayList 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.get(0)).display();

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

(deck.get(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.get(0);   // temp is 1st card
deck.set(0, deck.get(51));       // 1st card is now same as 52nd card
deck.set(temp, 51);              // 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 A is a Java ArrayList, then you can use

A.size()

to obtain the number of elements.

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

Loopy Fish

Introduction

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.

This is the situation for the FOR EACH statement. For example, if you want to access all the elements in the ArrayList, then one might use the following loop structure:

for (Card card : hand)
{       
	card.displayCard();
}

This is read as "For each card of type Card in ArrayList hand, display the card". FOR EACH statements can only be used when all the elements in the list are to be accessed and the position in the ArrayList doesn't matter. If you want to add things to an ArrayList or remember where in the ArrayList the object is located, then you cannot use the FOR EACH statment.

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 to ensure a Valid Index in a Java ArrayList, A, is

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

This pattern could be used to modify elements in the collection. For example, to replace existing 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.size(); i++)
{       hand.set(i, deck.dealCard());
}

Note the condition in the FOR loop: i < N (or, in this case, i < hand.size()). 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!
{       ((Card)hand.get(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!
{       ((Card)hand.get(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?

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?