Programming Project:
Implementing an Unbounded Ocean

In this assignment you will create the Unbounded Ocean that the biologists want (see the Problem Statement at the beginning of Part 2 of the Marine Biology Case Study).^* To do this, you will create an unordered list (apvector) of the fish in the ocean rather than keeping a matrix of defined and undefined fish in all possible environment positions. Much of the change is restricted to the Environment class, because you are changing the internal representation of the environment.

Adding Useful Operations to the Position and Environment Classes

• Do Modification Exercise 1 on p. 42 of the Marine Biology Case Study.

• Implement operator< for the Position class also. A position is "less than" another position if it is above it (in a row with a lower index) or if it is in the same row but to the left of it (lower column index). Using ==, !=, and <, implement the remaining comparison operators.

• Do Modification Exercise 1 on p. 48 of the Marine Biology Case Study. Once you have implemented your new FishAt function, you should modify Display Show to call it. For each displayable cell, the body of the nested loops in Show should display a fish if one occupies the corresponding environment position and display blank spaces otherwise. (Graphics versions do not need to explicitly display blank spaces where there are no fish.)
  CORRECTION: You should use Environment FishAt and Fish IsUndefined in Display Show, rather than IsEmpty and FishAt. (Can you figure out why?)

Make Show independent of AllFish.

• Text-based versions only: The Display constructor should take the number of rows and columns to be displayed as parameters. Create new data members to store these values.

  Modify the main function in fishsim.cpp to construct the Display by specifying an appropriate number of rows and columns (for example, 10 x 20).

  Graphics-based versions: Make sure that your particular graphics version allows you to derive the number of rows and columns to be displayed from the size of the window and possibly "scaling factors" which describe the size of each "cell."

• Modify the Show function to take the upper-left display position as a parameter. (This means modifying the header file, the implementation, and the call to Show in fishsim.cpp. For now, you may pass Position(0, 0) to Show in fishsim.cpp.) Use this upper-left display position as the starting point for your nested for loops. Then display the proper number of rows and columns, starting at the upper-left position.

Modify the internal representation of the Environment.

• Modify the Environment header file, changing the internal representation of the environment from a matrix of fish to a vector of fish.

• In the Environment implementation file, modify the Environment constructor to construct the vector with an arbitrary size in the initialization list (10, for example). Decide whether you wish to remove the lines that read in the number of rows and columns in the Environment (in which case you will have to modify your data file(s) as well), or whether you wish to keep those lines there but ignore the values that you read in.

• The functions NumRows, NumCols, and InRange are no longer meaningful. Delete them from the header and implementation files.

• Modify the AllFish function. It should become much simpler, since you are now creating a vector from another vector, rather than from a matrix.

• Since the fish in the apvector are not in any particular order, IsEmpty, Update, and FishAt will now need to search through the list for the fish in the specified position in order to do their jobs. Rather than implement the search separately in three (or more) different functions, create a new helper member function called FishIndex. This function will only be used internally by other Environment member functions, so it should be private. FishIndex takes a Position as a parameter, and returns the index of the fish at that position (if one is found), or -1 if no fish is found at that position. Add the declaration for FishIndex to the private section of the Environment header file and its code to the bottom of the implementation file. Since FishIndex will not change the Environment object, it should be a const member function.

• Modify IsEmpty and FishAt to use FishIndex. IsEmpty becomes a one-line function. If there is no fish at the specified position, FishAt needs to return an undefined fish. One way to do this is to put the following line of code at the top of the function

          Fish undefinedFish;
  

  and then return the local undefinedFish object when necessary.

• Modify Update to use FishIndex. There are now two error conditions: FishIndex might indicate that there is no fish at the specified position (how does it indicate that?), or the fish at that location might have the wrong ID number. If there is no error, the new code will be considerably simpler than the old code -- just put the new fish into the spot indicated by FishIndex.

• In AddFish, after you have checked that the position is currently empty, add the following lines of code:

     if (myFishCount == myWorld.length())
     {
         myWorld.resize(2 * myWorld.length());
         DebugPrint(7, "doubling length of myWorld to "
  	  + IntToString(myWorld.length()));
     }
  

  This increases the size of the vector if necessary. Then update the code to actually add the new fish to the vector rather than to a matrix.

• Scan through the Environment header file and implementation file to double-check that you have changed all references to the apmatrix to use an apvector instead.

Process fish in the right order.

• Run your program with the data sets suggested in the section on black-box testing (pp. 21 - 28). Include a data set that provides the fish in a haphazard order. You should notice an error. The fish are no longer being processed in top-down, left-to-right order. Instead they are being processed in the order in which they were added to the list. You will need to sort the fish in the list to put them in the right order. Fortunately, there is one already provided in utils.cpp. This function depends on the existence of operator<, which you implemented above.

  One recommendation is to call Sort from the Simulation Step function.   (Why is this a good place to put this call?)

• Run your test suite again.

^*This lab was derived from the Advanced Placement Computer Science Marine Biology Simulation Case Study, available from the College Board for face-to-face teaching purposes.