TSRJ Workshop 2008 - Advanced Track

Tuesday afternoon lecture
--------------------------

Goals:

Learn how to define methods following the design recipe. 
Learn about the hidden argument to each function: 'this'
See how the Scheme template with the cond cases for each datatype in a union translates 
to Java dynamic dispatch and eliminates the need for the predicate.

Select an example that allows you to define methods with the following properties:

Single class:

-- method that consumes no additional data and produces a primitive type result

-- method that consumes data of primitive types or String and produces a primitive type result

-- method that consumes an object in this class and produces a primitive type result

-- method that produces a new object of this class

Introduce conditionals as needed. Explain 'this'.
You may bring in helper methods, but may wait till object containment.
Always use 'this' and 'given' in the purpose statements.

Object containment:

-- method that delegates a question about the contained object to its class

Union:

Implement the methods that were defined for a simple class in all new classes in the union.
Add each method to the interface as it is defined.

The example used here - a simple maze - is actually self-referential, but does not look like
either a list or a tree - and so the focus is on the distribution of methods to the appropriate
classes and leveraging the dispatch.

Lists:

Insertion sort in all tis glory.


Note:

It will not be possible to go through one method for each type of header. However, the following points need to be illustrated 
-- delegation to object containment classes
-- argument that not a primitive type
-- result that is not a primitive type.


 
The lecture is structured as follows:

--------------------------------------------------------------------------------------------------------
Part 1: Methods for a Simple class                   -- class GradeRecord          
        based on http://www.ccs.neu.edu/home/vkp/213-sp06/Lectures/Week2/lecture5.java

Part 2: Methods for Object containment                -- class GradeRecord with class Course
        based on http://www.ccs.neu.edu/home/vkp/213-sp06/Lectures/Week3/lecture6.java

Part 3: Methods for Unions and Self-Referential Data  -- Maze with Pit, Gold, and Room
        based on http://www.ccs.neu.edu/home/vkp/213-sp06/Lectures/Week3/lecture7.java

Part 4: Sorting (optional)                            -- list of Course-s 
        based on http://www.ccs.neu.edu/home/vkp/213-sp06/Lectures/Week4/lecture9.java
--------------------------------------------------------------------------------------------------------



--------------------------------------------------------------------------------------------------------
Part 1: Methods for a Simple class 
--------------------------------------------------------------------------------------------------------

Goals:

 - learn to define and use methods in simple classes
 - design recipe for methods

Introduction:

So far we have considered only data. We have not computed anything,
did not ask questions about the objects we defined, in short, we have 
not written any programs.

Part of the reason is that the functions in languages like Java need 
to know what kind of data are they consume and what kind of data they 
produce. In Scheme, this was only specified in a comment, in other 
languages, like Java, the programmer must explicitly write down what 
is the type of each function argument.

The functions in Java are always associated with some class of data --- 
and are called either member functions, or more often 'methods'. Methods 
in a class are designed to answer questions about instances of this class, 
or produce new objects in the class from existing objects. So we may have 
a method in the class Book which determines whether this book has a given 
title, or the class that represents geometric shapes may have a method 
which produces a new shape of the same size and color as the original one, 
but at a new location.

However, the design of methods follows the same design recipe we have 
learned in HtDP.

Example:

Suppose we want to look at the data in a student's transcript. Each
record in the transcript reflect the information about one course
student has completed. The information provided there includes the
course number and title, the grade earned, and the number of credits 
the course carries. (Certainly, this may not be all that is in the
record, but for our purposes this is sufficient.)

We can represent the course number and the credits as an integer, the
course name as a String, and the grade as a 'double'. 


                           +--------------+
                           | GradeRecord  |
                           +--------------+
                           | int number   |
                           | String title |
                           | int credits  |
                           | double grade |
                           +--------------+


// to represent a grade record on a transcript
class GradeRecord {
  int number;
  String title;
  int credits;
  double grade;

  GradeRecord(int number, String title, int credits, double grade) {
    this.number = number;
    this.title = title;
    this.credits = credits;
    this.grade = grade;
  }

// add the methods here
 ...

}

Of course, in scheme, the data definition and the structure definition 
would be:

;; A GradeRecord is (make-gr Number String Number Number)
(define-struct gr (number title credits grade))

Before we design any methods, we make a couple of examples of
grade records:

GradeRecord fund = new GradeRecord(211, "Fundamentals", 4, 3.66);
GradeRecord ovw = new GradeRecord(220, "Overview", 1, 4.0);
GradeRecord algo = new GradeRecord(690, "Algorithms", 4, 3.0);

And, again, in Scheme these would be:

(define fund (make-gr 211 "Fundamentals" 4 3.66)
(define ovw (make-gr 220 "Overview" 1 4.0)
(define algo (make-gr 690 "Algorithms" 4 3.0)

The first method we design computes the quality points for this
grade record. (To compute the grade point average (or at NU it 
used to be called QPA for quality point average) each grade is
multiplied by the number of credits the course carries (this gives
you the quality points for the grade record) and then the sum of 
quality points is divided by the total number of credits on the
transcript.

1. Problem analysis and data definitions:

The only piece of information the method needs is the instance of the 
class GradeRecord for which we are computing the quality points. It 
will produce a double value that represents the quality points.

2. Purpose and contract (we will call it 'header' or 'signature'):

In Scheme this would be:

;; compute the quality points for a grade record 
;; q-point: GradeRecord -> Number
(define (qPoint a-gr) ... )

In Java this becomes:

// compute the quality points for this grade record
double qPoint(){...}

The method header includes not only the names for the method arguments,
but for each of them it also specifies what type of data it represents.
However, we have no arguments here. The only piece of data this method 
can use is the instance of the GradeRecord class that invoked (called) 
the method. The only way Java knows which method to call is by looking
at the type of data that invoked the method and finding the method 
definition within the class definition of that class. (Later we will see
that there is more going on here.)

The double at the beginning specifies what type of data the method produces.
The parentheses after the name of the method hold the list of parameters
for this method - but there are none specified. That is, because the 
grade record for which we are computing the price is already known -- 
as 'this', the object that invoked the method -- as we will see in the 
examples.

3. Examples:

we expect the quality point averages of our three examples to be 14.64,
4.0, and 12.0 respectively.
That means, 

fund.qPoints() should be --> 14.64
ovw.qPoints() should be --> 4.0
algo.qPoints() should be --> 12.0

We see, that in each case the grade record object for which we are computing
the quality point average appears before the method, followed by a '.'
'this' grade record in our purpose statement refer to this implicit parameter.

4. Template:

The template lists all parts of data available for the computation inside of
the body of the method. Even though we have no parameters, the Grade Record object 
which invoked the method contains several parts, and so the template will be:

    ... this.number ...            -- int
    ... this.title ...             -- String
    ... this.credits ...           -- int
    ... this.grade ...             -- double

where 'this' refers to the instance which invoked the method.
Only 'this.credits' and 'this.grade' values are relevant for our method, and 
the body becomes:

  return this.grade * this.credits;

Notice that Java uses the infix notation for the arithmetic (and other)
operations.

The complete method is shown below:

  // compute the quality points for this grade record
  double qPoints(){
    return this.grade * this.credits;
  }

We copy the examples of data and of the method invocation into the 
ExamplesBooks class. It is not easy to compare two double-s for equality.
We know this from HtDP. However, just as in HtDP the test harness does the 
correct comparison for us - as shown below:


class ExamplesGradeRecord{
  ExamplesGradeRecord() {}

  GradeRecord fund = new GradeRecord(211, "Fundamentals", 4, 3.66);
  GradeRecord ovw = new GradeRecord(220, "Overview", 1, 4.0);
  GradeRecord algo = new GradeRecord(690, "Algorithms", 4, 3.0);

  boolean test1 = check this.fund.qPoints() expect 14.64 within 0.01;
  boolean test2 = check this.ovw.qPoints() expect 4.0 within 0.01;
  boolean test3 = check this.algo.qPoints() expect 12.0 within 0.01;
}

------------------------------------------------------------------------
Next, we want to figure out whether a student earned at least some given
number of quality points in this course.

1. Problem analysis and data analysis:
   The method consumes the threshold value and produces a boolean value.

2. Purpose and header:
   // does this grade record earn quality points above the given level?
   boolean okCourse(double level) {...}

3. Examples:
   fun.okCourse(14.0) == false
   algo.okCourse(14.0) == true

4. Template:
   --- we can now add the method we already defined ---
    ... this.number ...            -- int
    ... this.title ...             -- String
    ... this.credits ...           -- int
    ... this.grade ...             -- double
    ... this.qPoints() ...         -- double

5. Body:
   return this.qPoints() >= level;

   so that the whole method becomes:
   // does this course record earn quality points above the given level?
   boolean okCourse(double level) {
     return this.qPoints() >= level;
   }

6. Tests: -- to be inserted in the ExamplesGradeRecord class:
   boolean test4 = check this.fund.okCourse(14.0) expect true;
   boolean test5 = check this.algo.okCourse(14.0) expect false;
*/

/*
Finally, we want to figure out whether one grade record has a higher
grade than another one.

1. Problem analysis and data analysis:
   The method consumes one additional grade record and produces 
   a boolean value.

2. Purpose and header:
   // is the grade in this grade record higher that in the given record
   boolean higherGrade(GradeRecord that) {...}

3. Examples:
   fund.higherThan(ovw) == false
   fund.higherThan(algo) == true

4. Template:
   --- we can now add the methods we already defined ---
    ... this.number ...                  -- int
    ... this.title ...                   -- String
    ... this.credits ...                 -- int
    ... this.grade ...                   -- double
    ... this.qPoints() ...               -- double
    ... this.okCourse(double level) ...  -- boolean

   --- and also all these fields and methods for 'that' grade record ---
    ... that.number ...                  -- int
    ... that.title ...                   -- String
    ... that.credits ...                 -- int
    ... that.grade ...                   -- double
    ... that.qPoints() ...               -- double
    ... that.okCourse(double level) ...  -- boolean

   The first part of the template should be retained in the class 
   definition as a comment right after the constructor. It grows 
   as more methods are added to the class. It can be just copied 
   and pasted into the method body as it is being developed, and 
   erased once not needed. The second part is specific to this method, 
   and so should be written there.

5. Body:
   return this.grade > that.grade;

   so that the whole method becomes:
   // is the grade in this grade record higher that in the given record
   boolean higherGrade(GradeRecord that) {
     return this.grade > that.grade;
   }

6. Tests: -- to be inserted in the ExamplesGradeRecord class:
   boolean test6 = check this.fund.higherGrade(this.ovw) expect false;
   boolean test7 = check this.fund.higherGrade(this.algo) expect true;

*/

/*Here is our code all together:

                           +--------------+
                           | GradeRecord  |
                           +--------------+
                           | int number   |
                           | String title |
                           | int credits  |
                           | double grade |
                           +--------------+

*/

// to represent a grade record on a transcript
class GradeRecord {
  int number;
  String title;
  int credits;
  double grade;

  GradeRecord(int number, String title, int credits, double grade) {
    this.number = number;
    this.title = title;
    this.credits = credits;
    this.grade = grade;
  }

/*  TEMPLATE:
    ... this.number ...                        -- int
    ... this.title ...                         -- String
    ... this.credits ...                       -- int
    ... this.grade ...                         -- double
    ... this.qPoints() ...                     -- double
    ... this.okCourse(double level) ...        -- boolean
    ... this.higherGrade(GradeRecord that) ... -- boolean
*/

  // compute the sale price of this book
  double qPoints(){
    return this.grade * this.credits;
  }

   // does this grade record earn quality points above the given level?
   boolean okCourse(double level) {
     return this.qPoints() >= level;
   }

   // is the grade in this grade record higher that in the given record
   boolean higherGrade(GradeRecord that) {
     return this.grade > that.grade;
   }

}

class ExamplesGradeRecord{
  ExamplesGradeRecord() {}

  GradeRecord fund = new GradeRecord(211, "Fundamentals", 4, 3.66);
  GradeRecord ovw = new GradeRecord(220, "Overview", 1, 4.0);
  GradeRecord algo = new GradeRecord(690, "Algorithms", 4, 3.0);

  // test the method qPoints:
  boolean test1 = check this.fund.qPoints() expect 14.64 within 0.01;
  boolean test2 = check this.ovw.qPoints() expect 4.0 within 0.01;
  boolean test3 = check this.algo.qPoints() expect 12.0 within 0.01;

  // test the method okCourse:
   boolean test4 = check this.fund.okCourse(14.0) expect true;
   boolean test5 = check this.algo.okCourse(14.p) expect false;

  // test the method higherThan:
   boolean test6 = check this.fund.higherGrade(this.ovw) expect false;
   boolean test7 = check this.fund.higherGrade(this.algo) expect true;
}

--------------------------------------------------------------------------------------------------------
Part 2: Methods for Object containment       -- class GradeRecord with class Course
--------------------------------------------------------------------------------------------------------

Let us return to defining methods for the class of data that 
represents grade records. However, we use the class definition
that used a separate class to represent the course, so that 
several students can get a grade in the same course.

Here are the classes that represents grade records and courses:

                           +---------------+
                           | GradeRecord   |
                           +---------------+
         +-----------------| Course course |
         |                 | String term   |
         |                 | double grade  |
         |                 +---------------+
         v
+---------------+
| Course        |
+---------------+
| int num       |
| String title  |
| int credits   |  
+---------------+ 

We changed the data a bit: the Course class knows the course number
and the course title as well as the number of credits the course
carries. The student's grade record records the course, the grade 
earned, and the term in which the student took the course (for now, 
a String, such as "SP06" or "FL05" --- later, we may replace that
with a class that represents the term information.) 

We need new examples of grade records (and courses as well):

  Course fund = new Course(211, "Fundamentals", 4);
  Course ovw  = new Course(220, "Overview", 1);
  Course algo = new Course(690, "Algorithms", 4);

  GradeRecord fundFL05 = new GradeRecord(this.fund, "FL05", 3.66);
  GradeRecord ovwFL05 = new GradeRecord(this.ovw, "FL05", 4.0);
  GradeRecord algoSP05 = new GradeRecord(this.algo, "SP05", 3.0);

Again, we want to compute the quality points the students earned in
a course on the in the grade record. The method remains in the 
class GradeRecord and its purpose and header are unchanged:

  // compute the quality points for this grade record
  double qPoints(){ ... }

We need new examples.

  boolean test1 = check this.fundFL05.qPoints() expect 14.64 within 0.01;
  boolean test2 = check this.ovwFL05.qPoints() expect 4.0 within 0.01;
  boolean test3 = check this.algoSP05.qPoints() expect 12.0 within 0.01;

Well, the method will change, but the examples are the same!!! This 
is a good way to design programs - we refine the class definitions,
and the method implementations, but the program behavior is the same.

The next step is the template for the methods in this class:

  ... this.course ... -- Course
  ... this.term ...   -- String
  ... this.grade ...  -- double

Well, with that information we cannot compute the quality points.
We know the grade, but only the instance of the Course that we refer
to knows about the credits. That means, we delegate this task to the
class Course. Of course, we have to pass on the information about
the earned grade that we already know. The method header and the 
purpose statement for method qPoints in the class Course will be:

  // compute the quality points for the given grade earned in this course
  double qPoints(double grade){ ... }

Once we have the header and the purpose statement for this method, 
we can finish designing the original qPoints method in the class 
GradeRecord. We first add to the template the fact that this.course 
can invoke the method qPoints:

  ... this.course.qPoints(double g) ... -- double

and the body of the method in the class GradeRecord becomes:

  // compute the quality points for this grade record
  double qPoints(){ 
    return this.course.qPoints(this.grade);
  }

We now complete the design of the method qPoints for the class Course.
Of course, we first need more examples:

  boolean test4 = check this.fund.qPoints(3.66) expect 14.64 within 0.01;
  boolean test5 = check this.ovw.qPoints(4.0) expect 4.0 within 0.01;
  boolean test6 = check this.algo.qPoints(3.0) expect 12.0 within 0.01;

The template for the methods in the class Course is:

  ... this.num ...      -- int
  ... this.title ...    -- String
  ... this.credits ...  -- int

The method body is now easy:

  // compute the quality points for the given grade earned in this course
  double qPoints(double grade){
    return this.credits * grade;
  }

We can now run the tests for both methods.

--------------------------------------------------------------------------------------------------------
Part 3: Methods for Unions and Self-Referential Data
--------------------------------------------------------------------------------------------------------

Goals:

 - learn to define and use methods in classes with union and self-reference

Introduction:

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
Pits. 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.

                   +------+                       
                   | Room |<---------------------+
                   +------+                      |
                      / \                        |
                       |                         |
     - - - - - - - - - - - - - - - - -           |
     |             |                 |           |
  +-----+    +------------+    +------------+    |
  | Pit |    | Gold       |    | Token      |    |
  +-----+    +------------+    +------------+    |
  +-----+    | int factor |    | int num    |    |
             +------------+    | Room left  |----+ 
                               | Room right |----+ 
                               +------------+ 

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 it's 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 TokenA 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 tow gold nuggets.

We now design the 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 Room { }

// to represent a pit in a maze game
class Pit implements Room {

  Pit() { }
}

// to represent a gold room in a maze game
class Gold implements Room {
  int factor;

  Gold(int factor) {
    this.factor = factor;
  }
}

// to represent a token room in a maze game
class Token implements Room {
  int num;
  Room left;
  Room right;

  Token(int num, Room left, Room right) {
    this.num = num;
    this.left = left;
    this.right = right;
  }
}

class Examples {
  Examples () {}

  Room pit = new Pit();
  Room gold = new Gold(2);
  Room token3 = new Token(3, this.pit, this.gold);
  Room start = new Token(5, this.pit, this.token3);
}

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

We now want to count the number of pits in the whole game. That 
means, we need to add a 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.

// to represent a room in a maze game
interface Room { 
  // count the number of pits in the maze starting at this room
  int countPits();

}

// to represent a pit in a maze game
class Pit implements Room {

  // count the number of pits in the maze starting at this pit room
  int countPits() {...}
}

// to represent a gold room in a maze game
class Gold implements Room {
  int factor;

  // count the number of pits in the maze starting at this gold room
  int countPits() {...}
}

// to represent a token room in a maze game
class Token implements Room {
  int num;
  Room left;
  Room right;

  // count the number of pits in the maze starting at this token room
  int countPits() {...}
}

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

  Room pit = new Pit();
  Room gold = new Gold(2);
  Room token3 = new Token(3, this.pit, this.gold);
  Room start = new Token(5, this.pit, this.token3);

  boolean testCountPits1 = this.pit.countPits() == 1;
  boolean testCountPits2 = this.gold.countPits() == 0;
  boolean testCountPits3 = this.token3.countPits() == 1;
  boolean testCountPits4 = 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:

    ... this.num ...               -- int
    ... this.left ...              -- Room
    ... this.right ...             -- Room

    ... 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) room
  ... 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
  int countPits() { return 1; }

// in the class Gold:
  // count the number of pits in the maze starting at this gold room
  int countPits() { return 0; }

// in the class Token:
  // count the number of pits in the maze starting at this token room
  int countPits() {
    return this.left.countPits() + this.right.countPits();
  }

Of course, we now have to run our examples.

-------------------
  Optional Part
___________________

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
int mostTokens(){...}

Here are examples:

  boolean testMostTokens1 = this.pit.mostTokens() == 0;
  boolean testMostTokens2 = this.gold.mostTokens() == 0;
  boolean testMostTokens3 = this.token3.mostTokens() == 3;
  boolean testMostTokens4 = 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:

    ... this.num ...            -- int
    ... this.left.mmm() ...     -- Room
    ... this.right.mmm() ...    -- Room

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

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

Before we proceed, we think carefully about the meaning of the data in the 
template. We read aloud the purpose statement for the two self-referential 
method invocations:

find the most number of tokens a player can collect starting in this left room
                                                                ---------
    ... this.left.mostTokens()   -- int


and 
find the most number of tokens a player can collect starting in this right room
                                                                ----------
    ... this.right.mostTokens()  -- int


It is now 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 integers. 
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. Finally, the body of the method 'mostTokens' becomes:

  // find the most number of tokens a player can collect starting in this room
  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 guarantee 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.

--------------------------------------------------------------------------------------------------------
Part 4: Sorting a List of Data
--------------------------------------------------------------------------------------------------------

Goals:

 - Designing methods that sort a list of courses.
 - Practice using the design recipe in the context of a class hierarchy

Introduction:

We would like to order a list of courses by the course number. Of course,
once we understand how to do this, we should be use the same design process
to design methods that will sort a list of other kinds of objects using
another criteria for ordering the list.

Let us follow the design recipe!!

1. Problem analysis.

The method 'sort' will be defined in the classes that represent a list
of courses. There is nothing else the method needs besides the list
of courses that invoked the method.

2. Purpose and Header.

We now know what the header will be - and we add the purpose statement:

// produce a list sorted by course number from this list of courses
ALoCourse sort();

This method needs to be defined in every subclass of the ALoCourse class.

3. Examples.

  Course lab1 = new Course("CS Lab 1", 212);
  Course eng1 = new Course("English 1", 128);
  Course opsys = new Course("Operating Systems", 313);
  Course biol = new Course("Biology 1", 210);

  ALoCourse mtcourses = new MTLoCourse();
  ALoCourse list1 = new ConsLoCourse(this.lab1, this.mtcourses);
  ALoCourse list2 = new ConsLoCourse(this.eng1,this.list1);
  ALoCourse list4 = new ConsLoCourse(this.opsys, 
                      new ConsLoCourse(this.biol, this.list2));

mtcourses.sort() --> new MTLoCourse()
list1.sort() --> list1
list4.sort() --> new ConsLoCourse(eng1, 
                   new ConsLoCourse(biol, 
                   new ConsLoCourse(lab1, 
                   new ConsLoCourse(opsys, 
                   mtcourses))))

4. Template.

Again, there is no data in MTLoCourse, so we only need a template 
for the class ConsLoCourse:

  ... this.first ...                -- Course
  ... this.rest ...                 -- ALoCourse
  ... this.rest.sort() ...          -- ALoCourse (sorted)

5. Body.

As usual we try to do the simple case first.

class MTLoCourse:
-------------

An empty list is sorted, so this is a trivial case:

  ALoCourse sort(){
    return this;
  }

class ConsLoCourse:
---------------

  ... this.first ...                -- Course
  ... this.rest ...                 -- ALoCourse
  ... this.rest.sort() ...          -- ALoCourse (sorted)

Reading aloud the purpose statement for 'this.rest.sort()' we get:

'produce a list sorted by course number from the rest of this list of courses'

So all that remains is to insert the first item into a sorted 
rest of the list. We use a helper method:

// insert the given Course into this sorted list
ALoCourse insert(Course course)

and with the help of this method, the body for the 'sort' becomes:

  return this.rest.sort().insert(this.first);

----------------------------------------------------------------------------
We now work on the helper method 'insert'. We already have the purpose
and the header.

Examples.

mtcourses.insert(tool) --> new ConsLoCourse(tool, mtcourses)
list1.insert(eng1) --> new ConsLoCourse(eng1, list1)
list1.insert(opsys) --> new ConsLoCourse(help, 
                          new ConsLoCourse(opsys, mtcourses))
new ConsLoCourse(eng1, new ConsLoCourse(biol, 
                         new ConsLoCourse(opsys, mtcourses))).insert(lab1)
  --> new ConsLoCourse(eng1, 
        new ConsLoCourse(biol, 
          new ConsLoCourse(lab1, 
            new ConsLoCourse(opsys, mtcourses))))


Template and Body.

class MTLoCourse:
-------------

The result is always a list with one item:

  return new ConsLoCourse(course, this);

class ConsLoCourse:
---------------

We use the earlier template for the class ConsLoCourse 

  ... this.first ...                -- Course
  ... this.rest ...                 -- ALoCourse
  ... this.rest.sort() ...          -- ALoCourse (sorted)

However, we cannot add ... this.rest.insert(Course ...) to the template,
because it requires that the instance that invokes the method be
already sorted. But we can use this.rest.sort() instead, to invoke
the 'insert' method:

  ... this.rest.sort().insert(Course ...) ...  -- ALoCourse (sorted)

Reading aloud the combined purpose statement for 
'this.rest.insert(Course ...)' we get:

'insert the given Course into the sorted rest of this sorted list'

If the given Course has a smaller course number than the first item 
in the list, the resulting list is just

  new ConsLoCourse(course, this)

otherwise, the first item of the sorted list is the first item of the
list we are inserting into, and the rest consists of the given Course
inserted into the rest of the list:

  new ConsLoCourse(this.first, this.rest.insert(course))

and the body of the method is:

  if (course.number < this.first.number)
    return new ConsLoCourse(course, this);
  else
    return new ConsLoCourse(this.first, this.rest.insert(course));