Gary Jaye's Guide to the Marine Biology Case Study (2)

Back to Contents     To next section    MCX1 home     MCX2 home

4. The Fish::EmptyNeighbors function and Brady's object diagram

Studying the Fish::EmptyNeighbors function carefully should extend and reinforce your knowledge of the essential infrastructure of the Marine Biology Case Study program. In the process, it should also provide an introduction to the Fish class. To prepare for this section, you should have hard copies of fish.h and fish.cpp in front of you.

1. The interface/implementation division: How would you determine what the EmptyNeighbors member function does? Notice that fish.h contains no documentation concerning the function. Do you think that this is a careless omission? Examining Alyce Brady's Fish::EmptyNeighbors object diagram should provide the necessary clue to make a reasonable conjecture.

       

Notice that EmptyNeighbors is a private member function. With a little reflection we should conclude that documenting a private member works against the information hiding principle by which the program's authors have been guided. The interface/implementation dichotomy characterizing all well-designed C++ classes is a standard technique for realizing the principle of information hiding: The interface is defined and described in a header file, and the programming specifics are hammered out in an implementation file. Given that EmptyNeighbors should be  documented but that program design considerations rule out the header file, the implementation file was the logical place to situate it.

2. Implementing EmptyNeighbors: Before examining the documentation and implementation of EmptyNeighbors in fish.cpp, try to determine what information the object diagram imparts. The fact that objects of four different classes  interact to accomplish the function's task is clearly illustrated.  It can also be seen that the action performed on the Neighborhood object is taken through the other private function, Fish::AddIfEmpty. This is the documentation of the two private member functions of the Fish class (in fish.cpp):

Neighborhood Fish::EmptyNeighbors(const Environment & env, const Position & pos) const {
//  precondition:  pos is in the grid being modeled
//  postcondition: returns a Neighborhood of pos of empty positions
 

void Fish::AddIfEmpty(const Environment & env, Neighborhood & nbrs, const Position & pos) const {
// postcondition: pos is added to nbrs if pos in env and empty

By reviewing the object diagram, the function headers (and accompanying documentation) above, you should be able to implement the Fish::EmptyNeighbors function. Here's a checklist of the questions you need (and should) be able to answer in order to complete EmptyNeighbors:

1. What does a Neighborhood object represent?  (See The program infrastructure above.)
2. How is a Neighborhood implemented to achieve its representational purpose? (See The program infrastructure above.)
3. What does Environment::IsEmpty do?  (See The Environment::IsEmpty function above.)
4. The number of calls to AddIfEmpty a successful implementation EmptyNeighbors necessarily makes.

Question 4.1: Complete Fish::EmptyNeighbors started below.

Neighborhood Fish::EmptyNeighbors(const Environment & env, const Position & pos) const {

}

3. Top-down design: The relative simplicity with which EmptyNeighbors (see Answer 4.1 below, if necessary) can be implemented owes a lot to the AddIfEmpty function. Even at this detail-oriented, concrete level of the Marine Biology case study program, the benefit of accomplishing a task by creating one or more helper functions to handle its implementation specifics should be apparent. Moving from the abstract to the concrete, is another basic principle of program organization: top-down design. What's striking here is that a helper function has been endowed with its own helper function.

Question 4.2: Complete Fish::AddIfEmpty started below.

void Fish::AddIfEmpty(const Environment & env, Neighborhood & nbrs, const Position & pos) const {

}

4a. Introduction to the Fish class

The best form of introduction to the Fish class is the interface documentation in its header file. This is the class description and instructions on how to interact with its objects given in fish.h:

The Fish class represents a fish/swimmer. A fish has an integer id and maintains its position in a grid. Both these pieces of information are set by the constructor, and the id is never changed. A Fish moves via the member function Move. A fish whose "amIDefined" field is false represents an "empty" "undefined" fish. The IsUndefined() member function distinguishes defined fish from undefined fish. The default Fish() constructor creates an empty/undefined fish.

This is the Fish class definition in fish.h:

class Fish {
  public:
    // constructors
    Fish();  // postcond: IsUndefined() == true
    Fish(int id, const Position & pos);  // postcond: Location() returns pos,
                                        // Id() returns id, isUndefined() == false
    // accessing functions
    int Id() const;  // precond:!IsUndefined(), postcond: returns id number of fish
    Position Location() const; // postcondition: returns current fish position
    bool IsUndefined() const; // postcond: returns true if constructed via default
                               // constructor, false otherwise
    apstring ToString() const; // postcond: returns a stringized form of Fish
    char ShowMe() const;       // postcond: returns a character that can make me visible
    // modifying functions
    void Move(Environment & env); // precond:  Fish stored in env at Location()
                                  // postcond: Fish has moved to a new location in env (if possible)
  private:
    // helper functions
    Neighborhood EmptyNeighbors(const Environment & env, const Position & pos) const;
    void AddIfEmpty(const Environment & env, Neighborhood & nbrs, const Position & pos) const;
    // data members
    int myId;
    Position myPos;
    bool amIDefined;
};

Question 4.3: Using the internal documentation accompanying its declaration above, complete the explicit-value Fish constructor started below. A constructor initializer list should be part of your solution!! Check your answer against the fish.cpp   implementation or Answer 4.3 before proceeding to Question 4.4.  

Fish::Fish(int id, const Position & pos) {

}

Question 4.4: Using the internal documentation accompanying its declaration above, complete the default constructor started below. A constructor initializer list should be part of your solution!!  

void Fish::Fish() {

}

Question 4.5: The authors' implementation of the default constructor contained no reference to the private data member myPos, yet their implementation is valid. Briefly explain why.

Question 4.6: Briefly explain why the const qualifier used in the access functions (Id and Location, for example) is not similarly deployed in the declarations of the Fish constructors.

Question 4.7: Using the internal documentation accompanying its declaration above, complete the implementation of isUndefined started below. Hint: The required code is short but surprisingly clumsy! Check your answer against the fish.cpp  implementation or Answer 4.7.  

bool Fish::IsUndefined() const {

}

4b. Programming: modifying Fish::ShowMe

In this section, we will briefly review the Fish::ShowMe function, and discuss the properties of the ASCII collating sequence on which the function relies.  Using these properties, you will be asked to modify the function by continuing the  programming exercise you began in section 3b. This is the current implementation of ShowMe found in fish.cpp: 

char Fish::ShowMe() const {
// postcondition: returns a character that can make me visible
  if (1 <= Id() && Id() <= 26) {
    return 'A' + (Id() - 1);
  }
  return '*';
}

Examining the code, it's apparent that the value returned by Id determines the value that ShowMe returns. Turning to the implementation of Id in fish.cpp, we find that the function simply returns the value stored to data member myId. Therefore, if value stored to myId  is in [1,26], ShowMe returns 'A'+(Id()-1, otherwise it returns '*'. The value that the expression 'A' + (Id() - 1) represents is based on the concept of a collating sequence.

A collating sequence is an ordering scheme in which a set of consecutive integer codes is mapped to and from a set of characters or symbols. In this manner, a lexicographic order (an extension of alphabetic order to non-alphabetic characters or symbols) can be imposed on a set of chacacters. Consider the ASCII collating sequence, the ordering scheme used on most personal computers.  If this collating sequence maps the character 'A' to the integer code 65 while mapping the integer code 65 to 'A', we can conclude all of the following on any ASCII-based computer:

1. char('A' + 1) == 'B'  && int('B') == 65 + 1 or 66             
2. char('A' + 25) == 'Z' && int('Z') == 65 + 25 or 90
3. Therefore, ('A' < 'B')  && ('B' < 'C') && ('C' < 'D') &&...&& ('Y' < 'Z') which gives us the ability to collate.

And since the ASCII collating sequence maps 'a' to the integer code 97 and maps the integer code 97 to 'a', we can also conclude all of the following on any operating system that uses the ASCII codes:

4. char('a' + 1) == 'b'   && int('b') == 97 + 1 or 98           
5. char('a' + 25) == 'z' && int('z') == 97 + 25 or 122
6. Therefore, ('a' < 'b')  && ('b' < 'c') && ('c' < 'd') &&...&&('y' < 'z')

Note that however plausible they might seem,  these two assumptions are false under the ASCII collating sequence:

7. False: 'A' > 'a'   Since int('A') == 65 and int('a') == 97, the ASCII codes ensure that 'A' < 'a' is evaluated as true
8. False: char('Z' + 1) == 'a'    Since int('Z') + 1 == 90 + 1 or 91 and int('a') == 97, then char('Z' +1) != 'a'

Question 4.8: What is the ordered set of characters that the expression 'A' + (Id() - 1) represents in the ShowMe function?

part 6 (of programming exercise started in section 3b):
    1. Change the fish birth process that you installed in part 5 to have a new fish added to the simulation whenever a fish is removed.
    2. Now change ShowMe to enable it to print lower case letters when the myId exceeds 26. Ultimately you want it produce this output:

        codes            return values        
          1..26                 'A'..'Z'
        27..52                 'a'..'z'
        53..78                 'A'..'Z'
        79..94                 'a'..'Z'
        etc... 

In other words, your revised ShowMe function should always return an upper or lower case letter. When testing your solution, make sure that maverik characters like @ and ' don't appear in the output. See the ASCII collating sequence if you have any questions about particular codes. Hint: study the codes/return values chart above carefully before formulating your algorithm..

Question 4.9: The ASCII collating sequence is not the only collating sequence. The EBCDIC collating sequence is used on many IBM mainframe computers and the terminals attached to them. 
    a. Why can't a computer using the EBCDIC collating sequence support the strategy used in the original and revised versions of the ShowMe
         function would?  Hint: examine the EBCDIC codes for the characters 'i' and 'j'.
    b. How do you think the ASCII collating sequence is incorporated into personal computers?

5. The Fish::Move function and Brady's object diagram

If you have been faithfully following this case study narrative from the beginning--answering the questions, and completing the programming exercises--mastering the details of the Fish::Move function should be fairly straightforward. To prepare for this section, you should have hard copies of fish.h and fish.cpp in front of you.

1. An invalid version: Recognizing that a particular approach to a task won't work often makes clear why a more complicated approach has been employed. This seems to be the case with the Fish::Move function. Using Alyce Brady's Fish::Move object diagram and the prototypes of the relevant functions involved in the function's implementation,  see if you can find the errors in invalid version given below:


Position Neighborhood::Select(int index) const; // access a Position
// precondition:  0 <= index < Size()
// postcondition: returns the index-th Position in Neighborhood

int RandGen::RandInt(int max); // returns int in [0..max)
void Environment::Update(const Position & oldLoc, Fish & fish);
// precondition:  fish was located at oldLoc, has been updated
// postcondition: if (fish.Location() != oldLoc) then oldLoc is empty;
//                Fish fish is updated properly in this environment
 Neighborhood Fish::EmptyNeighbors(const Environment & env, const Position & pos) const;
//  precondition:  pos is in the grid being modelled
//  postcondition: returns a Neighborhood of pos of empty positions
   void Fish::Move(Environment & env);
      // precondition:  Fish stored in env at Location()
      // postcondition: Fish has moved to a new location in env (if possible)

AN INVALID VERSION:
void Fish::Move(Environment & env) {
  RandGen randomVals;
  Neighborhood nbrs = EmptyNeighbors(env, myPos);
  if (nbrs.Size() > 0) {
      // there were some empty neighbors, so randomly choose one
      Position oldPos = myPos;
      myPos = nbrs.Select(randomVals.RandInt(0, nbrs.Size() - 1));
      myWorld[oldPos.Row()][oldPos.Col] = fish();
  }
}

On the surface, this version makes an attempt to carry out the tasks involved in simulating a fish move:

1. It obtains a list of candidate positions.
2. If the list of positions contains more than zero candidates
    a. The old position is saved.
    b. A candidate position is pseudo-randomly selected and stored to myPos.
    c. The position being vacated is appropriately modified.

There are two major errors in this naive version, both of which should coerce us into implementing the function more correctly. One causes a syntax error, the other is perfectly grammatical, and each is a logic error at its core. See if you can identify them before reading on.

First, the statement myWorld[oldPos.Row()][oldPos.Col] = fish();  generates a syntax errror because myWorld is not a data member of the Fish class. The agent that modifies the position being vacated must be a member function of the Environment class. This indirectness is the price we pay for information hiding. But it clearly points out the need to involve an Environment member function in the solution. It also explains  the involvement of Environment::Update in the object diagram.

The other error is one of omission. Recall (from  Overview of Part II) the context in which a Fish::Move function is invoked:

void Simulation::Step(Environment & env) {
// postcondition: one step of simulation in env has been made
  apvector<Fish> fishList;
  int k;
  fishList = env.AllFish();
  for (k = 0; k < fishList.length(); k++)
  {
     fishList[k].Move(env);
  } 
}                                      [from simulate.cpp]

Notice that the Fish objects that own the successive the calls to Move are proxies for Fish objects in env.myWorld. Therefore, a statment such as

   myWorld[myPos.Row()][myPos.Col].myPos = myPos; // this too is invalid!!

needs to be executed to reflect the new value of myPos in the appropriate myWorld element. And the only member function of the relevant five in the object diagram in which this statement can be specified is Environment::Update.  This statement, however,  raises the same problem that it was intended to solve: as a private member of the Fish class, myPos cannot be referenced by an Environment member function!

Having examined the major pitfalls, you should be able to devise a credible version of the Fish::Move function. In Question 5.1 you will be asked to do so. If  needed, a informal outline of the task is provided below.

Fish::Move outline
1. Move calls Fish::EmptyNeigbors to obtain a Neighborhood list of the positions to which its owner can move.
2. If any positions are open, the process of position selection begins:
    a. The current position of the fish is saved to oldPos.
    b. RandGen::RandInt pseudo-randomly generates an appropriate number for position selection.
    c. Neighborhood::Select modifies the owner's member myPos.
3. Using the Fish object itself and oldPos, Environment::Update then updates myWorld to properly reflect:
    a. The new position that the fish now occupies.
    b. That the position from which the fish has moved is vacant..

Question 5.1: Complete the implementation of Fish::Move started below. Read the prototype of the Environment::Update function (above) before proceeding. Validate you solution by checking fish.cpp or the distilled version listed in Answer 5.1.

void Fish::Move(Environment & env) {
      // precondition:  Fish stored in env at Location()
     // postcondition: Fish has moved to a new location in env (if possible)

    }

5a. Programming: mini-project

Start this project with a clean slate; this is not a continuation of our first programming endeavor. In each of the three parts, you will need to determine which classes should be modified. Make sure you have hard copies of all  the case study header and implementation files before you begin. Test your solution to each part thoroughly before proceeding to the next part. These are the project specifications:

1. New criteria for fish movement: South and East are  no longer   valid directions for fish movement. A fish can  move in three directions:   North,  West, and Northwest. If a position is candidate destination for a fish move, the probablity of selecting it is 1/n, where n is the total number of candidate   positions.

2. Terminating the simulation: Under the new rules for movement, the fish population should eventaully pile up at the northwestern region of the  environment and become immobile. When no fish is moved in a simulation step, the simulation is to be terminated. Use the exit function as described earlier (see Modifying the Environment class). Recall that the exit function was employed in the Environment::AllFish function before, a tactic that won't work in the current problem. Consider adding  an additional data member and member function to facilate your programming task.

3. Removing fish: Once you've succeeded in implementining the first two parts of the program, enforce this rule: a fish that  fails to move in three successive simulation steps is to be   removed from the simulation. You may modify the Fish class in any way that is appropriate to accomplishing your objective.


Back to Contents     To next section    MCX1 home     MCX2 home