►Lecture:   Methods for self-referential data
Lecture outline
1 Designing Methods for Unions of Classes
2 The importance of a good purpose statement
3 Using the template to identify helpers.
5.3.5

Lecture: Methods for self-referential data

Design methods for unions of classes with self-reference.
The importance of a good purpose statement.
Using the template to identify helpers.

     Maze.java   

Lecture outline

1 Designing Methods for Unions of Classes

The following class diagram represents the data for a simple maze game that consists of three different kinds of rooms: Token rooms, Gold rooms, and Pit-s. The player starts the game in one room. In each token room the player add to her fortune the number of tokens found in the token room and chooses to go to the next room through either the left or the right door. When the player reaches the Pit, the game ends with player loosing everything. Each gold room contains a key in the shape of a number. When the player reaches the gold room each token changes into as many gold nuggets as the number on the key, and the game ends. The maze is design in such way that the player cannot visit the same room twice.

Our data designers came up with the following class diagram for the data needed to represent this game:

                    +--------------------------+

                    | +----------------------+ |

                    | |                      | |

                    v v                      | |

                 +-------+                   | |

                 | IRoom |                   | |

                 +-------+                   | |

                    / \                      | |

                     |                       | |

   - - - - - - - - - - - - - - - - -         | |

   |             |                 |         | |

+-----+    +------------+    +-------------+ | |

| Pit |    | Gold       |    | Token       | | |

+-----+    +------------+    +-------------+ | |

+-----+    | int factor |    | int num     | | |

           +------------+    | IRoom left  |-+ |

                             | IRoom right |---+

                             +-------------+

Of course, we also need examples of such a game situation, so here is an example of such maze:

      +---------+

      | start   |

      | TOKEN 5 |

      +---------+

     /           \

    /             \

+-----+      +---------+

| PIT |      | token3  |

+-----+      | TOKEN 3 |

             +---------+

            /           \

           /             \

       +-----+       +--------+

       | PIT |       | gold  |

       +-----+       | GOLD 2 |

                     +--------+

The player starts in the start room and adds 5 tokens to his token collection. If he chooses to go left, he ends up in a Pit and the game ends with no winnings. If the chooses to go right, he goes to the token3 room and adds 3 tokens to the token collection. After that, going to the left again leads to a Pit, but going to the right ends the game with 16 gold nuggets - as each of the eight tokens in the player’s possession turns into two gold nuggets.

We now design the Java classes that represent this game and make examples of data, specifically to represent the game shown above.

// to represent a room in a maze game

interface IRoom { }

 

// to represent a pit in a maze game

class Pit implements IRoom {

 

  Pit() { }

}

 

// to represent a gold room in a maze game

class Gold implements IRoom {

  int factor;

 

  Gold(int factor) {

    this.factor = factor;

  }

}

 

// to represent a token room in a maze game

class Token implements IRoom {

  int num;

  IRoom left;

  IRoom right;

 

  Token(int num, IRoom left, IRoom right) {

    this.num = num;

    this.left = left;

    this.right = right;

  }

}

And here are the examples:

class Examples {

  Examples () {}

 

  IRoom pit = new Pit();

  IRoom gold = new Gold(2);

  IRoom token3 = new Token(3, this.pit, this.gold);

  IRoom start = new Token(5, this.pit, this.token3);

}

We only need one instance of a Pit, — there is no way to differentiate between the instances, because the class Pit has no fields.

2 The importance of a good purpose statement

We now want to count the number of pits in the whole game. That means, we need to add the method countPits to the classes that represent different rooms in the maze. The method consumes no arguments - knowing where in the maze we are at the current time (the value represented by this, the object that invoked the method) is sufficient to answer the question.

We add the method header to each class - and to their common interface. We omit the constructors from the text below - to save the space and to highlight the connections between the classes.

Java requires that a method declaed in the interface must have the public visibilty and so we need to preceed the method header with the word public.

// to represent a room in a maze game

interface IRoom {

  // count the number of pits in the maze starting at this room

  public int countPits();

 

}

 

// to represent a pit in a maze game

class Pit implements IRoom {

 

  // count the number of pits in the maze starting at this pit room

  public int countPits() {...}

}

 

// to represent a gold room in a maze game

class Gold implements IRoom {

  int factor;

 

  // count the number of pits in the maze starting at this gold room

  public int countPits() {...}

}

 

// to represent a token room in a maze game

class Token implements IRoom {

  int num;

  IRoom left;

  IRoom right;

 

  // count the number of pits in the maze starting at this token room

  public int countPits() {...}

}

The next step in the design recipe call for examples. We use the examples of data from above.

  IRoom pit = new Pit();

  IRoom gold = new Gold(2);

  IRoom token3 = new Token(3, this.pit, this.gold);

  IRoom start = new Token(5, this.pit, this.token3);

 

  // test the method countPits for the classes that represent a maze

  boolean testCountPits(Tester t) {

    return

    t.checkExpect(this.pit.countPits(), 1) &&

    t.checkExpect(this.gold.countPits(), 0) &&

    t.checkExpect(this.token3.countPits(), 1) &&

    t.checkExpect(this.start.countPits(), 2);

}

Remember, we must have examples for each of the three variants of the union — because we are designing three different methods, one for each variant of the union. The first two methods (for the classes Pit and Gold) are trivial - they always return one and zero respectively. The method for the class Token is harder. We start with the template:

/* TEMPLATE:

   Fields:

  ... this.num ...               -- int

  ... this.left ...              -- IRoom

  ... this.right ...             -- IRoom

  Methods for Fields:

  ... this.left.countPits() ...  -- int

  ... this.right.countPits() ... -- int

*/

We added for each self-reference an invocation of the method countPits that we are designing. Let us read aloud the purpose statements for these two method invocations:

 // count the number of pits in the maze starting at this (left) room

... this.left.countPits() ...

 

 // count the number of pits in the maze starting at this (right) oom

 ... this.right.countPits() ...

It is easy to see that the total count of pit rooms in the maze that starts in a token room is the sum of these two quantities. The three methods then become:

// in the class Pit:

  // count the number of pits in the maze starting at this pit room

  public int countPits() { return 1; }

 

// in the class Gold:

  // count the number of pits in the maze starting at this gold room

  public int countPits() { return 0; }

 

// in the class Token:

  // count the number of pits in the maze starting at this token room

  public int countPits() {

    return this.left.countPits() + this.right.countPits();

  }

Of course, we now have to run our examples.

3 Using the template to identify helpers.

Next we want to figure out what is the maximum number of tokens a player can collect (before falling into a pit, or before the tokens get converted into gold nuggets). Again, knowing the room where the game starts is sufficient, and so the method mostTokens needs no additional arguments. The purpose and the method header is:

// find the most number of tokens a player can collect starting in this room

public int mostTokens(){...}

Here are the examples (already written as tests that can be run):

boolean testMostTokens(Tester t) {

  return

  t.checkExpect(this.pit.mostTokens(), 0) &&

  t.checkExpect(this.gold.mostTokens(), 0) &&

  t.checkExpect(this.token3.mostTokens(), 3) &&

  t.checkExpect(this.start.mostTokens(), 8);

}

It is clear that the methods for the Pit class and for the Gold class are again trivial (always produce zero). For the class Token, the template is extended by the two self-referential method invocations:

/* TEMPLATE:

   Fields:

  ... this.num ...               -- int

  ... this.left ...              -- IRoom

  ... this.right ...             -- IRoom

 

  Methods for Fields:

  ... this.left.countPits() ...  -- int

  ... this.right.countPits() ... -- int

 

  ... this.left.mostTokens()   -- int

  ... this.right.mostTokens()  -- int

*/

It is clear that the number we want is the sum of the number of tokens in this room (this.num) and the larger of the two values (this.left.mostTokens() and this.right.mostTokens(). We design a helper method maxValue that produces the larger of the two given intergers. The method is defined in the class Token, but it makes no use of the Token object that invokes it. We leave it to the reader to go through the design steps. Here is the mathod definition in the class Token:

// find the maximum of the two given numbers

int maxValue(int a, int b){

  if (a > b)

    return a;

  else

    return b;

}

Notice that the purpose statement does not contains our magic word this. (In real Java we would make it a static method, but we ignore such details for now. Alternately, we could also use the method Math.max.

Finally, the body of the method mostTokens becomes:

// find the most number of tokens a player can collect starting in this room

public int mostTokens(){

  return this.num +

         this.maxValue(this.left.mostTokens(), this.right.mostTokens());

}

Running the tests confirms that we are on the right track. Remember, test can only verify that the test cases work properly — it is usually impossible to guaranteee through tests that the program works correctly for all possible inputs.

Complete working code is shown below. Notice, how we extended the class diagram with the list of method headers for all methods defined in these classes, or required for the given interfaces. This description of the classes allows the client of the class see clearly how the instances of the class can be defined and used.

Here is a complete class diagram - that includes the method headers for all methods defined in each class or interface:

                      +--------------------------------------------+

                      | +----------------------------------------+ |

                      | |                                        | |

                      v v                                        | |

            +------------------+                                 | |

            | IRoom            |                                 | |

            +------------------+                                 | |

            | int countPits()  |                                 | |

            | int mostTokens() |                                 | |

            +------------------+                                 | |

                      / \                                        | |

                       |                                         | |

     - - - - - - - - - - - - - - - - - - - - - - - - -           | |

     |                         |                     |           | |

+-----------------+ +-----------------+ +----------------------+ | |

| Pit             | | Gold            | | Token                | | |

+-----------------+ +-----------------+ +----------------------+ | |

| int countPits() | | int factor      | | int num              | | |

| int mostTokens()| +-----------------+ | IRoom left           |-+ |

+-----------------+ | int countPits() | | IRoom right          |---+

                    | int mostTokens()| +----------------------+

                    +-----------------+ | int countPits()      |

                                        | int mostTokens()     |

                                        | int maxValue(int,int)|

                                        +----------------------+

as well as the compete code for this program:

// to represent a room in a maze game

interface IRoom {

 

  // count the number of pits in the maze starting at this room

  public int countPits();

 

  // find the most number of tokens a player can collect starting in this room

  public int mostTokens();

}

// to represent a pit room in a maze game

class Pit implements IRoom {

 

  Pit() { }

 

/*TEMPLATE

  Methods:

  ... this.countPits() ...   -- int

  ... this.mostTokens() ...  -- int

*/

 

  // count the number of pits in the maze starting at this pit room

  public int countPits(){

    return 1;

  }

 

  // find the most number of tokens a player can collect starting in this room

  public int mostTokens(){ return 0; }

}

// to represent a gold room in a maze game

class Gold implements IRoom {

  int factor;

 

  Gold(int factor) {

    this.factor = factor;

  }

 

/*TEMPLATE

  Fields:

  ... this.factor ...       -- int

  Methods:

  ... this.countPits() ...   -- int

  ... this.mostTokens() ...  -- int

*/

 

  // count the number of pits in the maze starting at this gold room

  public int countPits(){

    return 0;

  }

 

  // find the most number of tokens a player can collect starting in this room

  public int mostTokens(){ return 0; }

}

// to represent a token room in a maze game

class Token implements IRoom {

  int num;

  IRoom left;

  IRoom right;

 

  Token(int num, IRoom left, IRoom right) {

    this.num = num;

    this.left = left;

    this.right = right;

  }

 

/*TEMPLATE

  Fields:

  ... this.num ...            -- int

  ... this.left.mmm() ...     -- IRoom

  ... this.right.mmm() ...    -- IRoom

 

  Methods:

  ... this.countPits() ...   -- int

  ... this.mostTokens() ...  -- int

 

  Methods for Fields:

  ... this.left.countPits()   -- int

  ... this.right.countPits()  -- int

 

  ... this.left.mostTokens()   -- int

  ... this.right.mostTokens()  -- int

 

*/

 

  // count the number of pits in the maze starting at this token room

  public int countPits(){

    return this.left.countPits() + this.right.countPits();

  }

 

  // find the most number of tokens a player can collect starting in this room

  public int mostTokens(){

    return this.num +

           this.maxValue(this.left.mostTokens(), this.right.mostTokens());

  }

 

  // find the maximum of the two given numbers

  int maxValue(int a, int b){

    if (a > b)

      return a;

    else

      return b;

  }

}

Finally, here is the complete ExamplesMaze class:

// to represent examples and tests for a maze game

class ExamplesMaze {

  ExamplesMaze () {}

 

  // sample maze rooms:

  IRoom pit = new Pit();

  IRoom gold = new Gold(2);

  IRoom token3 = new Token(3, this.pit, this.gold);

  IRoom start = new Token(5, this.pit, this.token3);

 

  // test the method countPits for the classes that represent a maze

  boolean testCountPits(Tester t) {

    return

    t.checkExpect(this.pit.countPits(), 1) &&

    t.checkExpect(this.gold.countPits(), 0) &&

    t.checkExpect(this.token3.countPits(), 1) &&

    t.checkExpect(this.start.countPits(), 2);

  }

 

  boolean testMostTokens(Tester t) {

    return

    t.checkExpect(this.pit.mostTokens(), 0) &&

    t.checkExpect(this.gold.mostTokens(), 0) &&

    t.checkExpect(this.token3.mostTokens(), 3) &&

    t.checkExpect(this.start.mostTokens(), 8);

  }

}