#lang scribble/manual
@(require "vkp-scrbl/unnumbered.rkt" "vkp-scrbl/utils.rkt")



@title{Lecture: Methods for self-referential data}
  @para[#:style "boxed"]{
  Design methods for unions of classes with self-reference.@linebreak{}
  The importance of a good purpose statement.@linebreak{}
  Using the template to identify helpers.@linebreak{}@linebreak{}
     @hspace[4] @link["Maze.java"]{Maze.java}
  @hspace[2]}

@section*{Lecture outline}

@itemlist[@item{Finding the class where the method should be defined}
          @item{The importance of a good purpose statement}
          @item{Using the template to identify helpers}]               
           
@section{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: @tt{Token} rooms, @tt{Gold} rooms, and
@tt{Pit}-s. The player starts the game in one room. In each @emph{token room} the player
add to her fortune the number of tokens found in the @emph{token room} and 
chooses to go to the next room through either the left or the right door.
When the player reaches the @tt{Pit}, the game ends with player loosing everything. 
Each @emph{gold room} contains a key in the shape of a number. When the player
reaches the @emph{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:

@verbatim{
                      +--------------------------+
                      | +----------------------+ |
                      | |                      | |
                      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:

@verbatim{
               +---------+  
               | start   |
               | TOKEN 5 |
               +---------+  
              /           \
             /             \
         +-----+      +---------+  
         | PIT |      | token3  |
         +-----+      | TOKEN 3 |
                      +---------+
                     /           \
                    /             \
                +-----+       +--------+
                | PIT |       | gold  |
                +-----+       | GOLD 2 |
                              +--------+
}

The player starts in the @emph{start} room and adds 5 tokens to his token collection.
If he chooses to go left, he ends up in a @tt{Pit} and the game ends with no winnings. 
If the chooses to go right, he goes to the @emph{token3} room and adds 3 tokens to the
token collection. After that, going to the left again leads to a @tt{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.

@verbatim{
// 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:

@verbatim{
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 @tt{Pit}, --- there is no way to 
differentiate between the instances, because the class @tt{Pit} has 
no fields.

@section{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 @tt{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 @tt{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 @tt{interface} must have
the @tt{public} visibilty and so we need to preceed the method header
with the word @tt{public}.

@verbatim{
// 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.

@verbatim{
  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
@tt{Pit} and @tt{Gold}) are trivial - they always return one and zero respectively.
The method for the class Token is harder. We start with the template:

@verbatim{
  /* 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 @tt{countPits}
that we are designing. Let us read aloud the purpose statements for these 
two method invocations:

@verbatim{
  // 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:

@verbatim{
// 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.

@section{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 @tt{mostTokens} needs no
additional arguments. The purpose and the method header is:

@verbatim{
// 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):

@verbatim{
  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 @tt{Pit} class and for the @tt{Gold} 
class are again trivial (always produce zero). For the class @tt{Token}, 
the template  is extended by the two self-referential method invocations:


@verbatim{
  /* 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 (@tt{this.num}) and the larger of the two values
(@tt{this.left.mostTokens()} and @tt{this.right.mostTokens()}. We design a @emph{helper} 
method @tt{maxValue} that produces the larger of the two given intergers. 
The method is defined in the class @tt{Token}, but it makes no use of the
@tt{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 @tt{Token}:


@verbatim{
  // 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 @tt{this}. 
(In @emph{real Java} we would make it a @tt{static} method, but we ignore 
such details for now. Alternately, we could also use the method @tt{Math.max}.

Finally, the body of the method @tt{mostTokens} becomes:

@verbatim{
  // 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:

@verbatim{
                      +--------------------------------------------+
                      | +----------------------------------------+ |
                      | |                                        | |
                      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:

@verbatim{
// 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();
}
}

@verbatim{
// 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; }
}
}

@verbatim{
// 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; }  
}
}

@verbatim{
// 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 @tt{ExamplesMaze} class:

@verbatim{
// 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);
  }
}
}