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



@title{Lecture: Methods for self-referential lists}
  @para[#:style "boxed"]{
  Design methods for unions of classes with self-reference that represent lists.@linebreak{}
  Basic loops.@linebreak{}
  Accumulators.@linebreak{}
  Sorting.@linebreak{}@linebreak{}
     @hspace[4] @link["BookLists.java"]{BookLists.java}
  @hspace[2]}

@section*{Lecture outline}

@itemlist[@item{Representing lists}
          @item{Basic loops}
          @item{Accumulators}
          @item{Sorting}]               
           
@section{Representing lists}

The following class diagram defines class hierarchy that represents a list
of books in a bookstore:

@verbatim{
                +-----------------------+                   
                | ILoB                  |<-------------+
                +-----------------------+              |
                +-----------------------+              |
                | int count()           |              |
                | int totalPrice()      |              |
                | ILoB allBefore(int x) |              |
                +-----------------------+              |
                           |                           |
                          / \                          |
                          ---                          |
                           |                           |
             -----------------------------             |
             |                           |             |
 +-----------------------+   +-----------------------+ |
 | MtLoB                 |   | ConsLoB               | |
 +-----------------------+   +-----------------------+ |
 +-----------------------+ +-| Book first            | |
 | int count()           | | | ILoB rest             |-+
 | int totalPrice()      | | +-----------------------+ 
 | ILoB allBefore(int x) | | | int count()           |
 +-----------------------+ | | int totalPrice()      |
                           | | ILoB allBefore(int x) | 
                           | +-----------------------+ 
                           v
                 +---------------+
                 | Book          |
                 +---------------+
                 | String title  |
                 | String author |
                 | int year      |
                 | int price     |
                 +---------------+
}


@bold{Let's make some examples}

@verbatim{
  //Books 
  Book htdp = new Book("HtDP", "MF", 2001, 60);
  Book lpp = new Book("LPP", "STX", 1942, 25);
  Book ll = new Book("LL", "FF", 1986, 10);

  // lits of Books
  LoB mtlist = new MtLoB();
  LoB lista = new ConsLoB(this.lpp, this.mtlist);
  LoB listb =   new ConsLoB(this.htdp, this.mtlist);
  LoB listc = new ConsLoB(this.lpp, 
                new ConsLoB(this.ll, this.listb));
  LoB listd = new ConsLoB(this.htdp, 
                new ConsLoB(this.ll, 
                  new ConsLoB(this.lpp, this.mtlist)));
}


@section{Basic loops}

Given this preceding class diagram, we would like to design methods to answer 
the following questions 

@itemlist[
          @item{Count how many books we have in a list of books}
          @item{Compute the total price of all books in a list of books}
          @item{Given a date (year) and a list of books, 
                produce a list of all books in the list that were pblished before
                the given year}
          @item{Produce a list of the same books but sorted by their title}]
     
 
Each of the four questions concerns a list of books, and so we start by designing the 
appropriate method headers and purpose statements in the @tt{interface ILoB}:

@verbatim{
 In LoB
 -------
  // count the books in this list
  public int count();

  // produce a list of all books published before the given date 
  // from this list of books
  public ILoB allBefore(int year);

  // calculate the total price of all books in this list
  public int totalPrice(); 
  
  // produce a list of all books in this list, sorted by their title
  public ILoB sort();
}

We now have to define these methods in both the class @tt{MtLoB} and
in the class @tt{ConsLoB}. You may find ti helpful to recall similar 
functions in DrRacket.

The @emph{design recipe} asks us to make examples. For clarity, we write them
in an abbreviated manner - just showing the actual computation and the expected 
outcome:

@verbatim{
  Examples for the class MtLoB
  ----------------------------
  mtlist.count() => 0 
  mtlist.totalPrice() => 0 
  mtlist.allBefore() => mtlist
}

and our methods become:

@verbatim{
 In MtLoB: 
 ---------

  // count the books in this list
  public int count(){ return 0; }

  // produce a list of all books published before the given date 
  // from this empty list of books
  public ILoB allBefore(int year) { return this; }

  // calculate the total price of all books in this list
  public int totalPrice() { return 0; } 
  
  // produce a list of all books in this list, sorted by their title
  public ILoB sort() { return this; } 
}

Notice that the values produced by these methods are the base case
values we have ween in DrRacket for the empty lists. The count for
an empty list is zero, starting with an empty list there is nothing to 
filter out, and nothing to sort, and the total price of buying no books
is zero as well.

There will be more work to do in the @tt{ConsLoB} class. First, examples!

@emph{Note:} We will work on the @tt{sort} method separately, later.

@verbatim{
  Examples
  --------
 lista.count() => 1
 listc.count() => 3
 
 lista.totalPrice() => 25
 listd.totalPrice() => 95
 
 lista.allBefore(2000) => lista
 listb.allBefore(2000) => mtlist
 listc.allBefore(2000) => new ConsLoB(lpp, new ConsLoB(ll,mtlist))
}
 
 The @emph{design recipe} asks us now to derive the template. 
 A template serves as a starting point for @bold{any} method inside ConsLoB:  

@verbatim{
  TEMPLATE:
  ---------
  Fields:
  ... this.first ...                             -- Book
  ... this.rest ...                              -- ILoB
  Methods:
  ... this.count() ...                           -- int
  ... this.totalPrice() ...                      -- int
  ... this.allBefore(int year) ...               -- ILoB  
  Methods for Fields:
  ... this.rest.count() ...                      -- int
  ... this.rest.totalPrice() ...                 -- int
  ... this.rest.allBefore(int year) ...          -- ILoB
}

We can now design the methods. In the template @tt{this.rest.count()}
produces @emph{the count of all books in the rests of this list} - and so the
method body in the class @tt{ConsLoB} becomes:

@verbatim{
  // count the books in this list
  int count(){ return 1 + this.rest.count(); }
}

In the template @tt{this.rest.totalPrice()}
produces @emph{the total price of all books in the rests of this list} - and so the
method body in the class @tt{ConsLoB} just adds to this value the price if the first
book in the list:

@verbatim{
  // calculate the total price of all books in this list
  int totalPrice() { 
    return this.first.price + this.rest.totalPrice();
  } 
}


In the template @tt{this.rest.allBefore(year)}
produces @emph{a list of all books in the rests of this list published before 
the given date} - and so the method body in the class @tt{ConsLoB} just adds 
to this value the first book in the list, provided that the first book has been 
published before the given year. Well, how can we tell? - we need to defer to the
class that represents the books to answer this question. The method body in the 
class @tt{ConsLoB} becomes:

@verbatim{
  // produce a list of all books published before the given date 
  // from this empty list of books
  ILoB allBefore(int year) { 
    if (this.first.producedBefore(year))
      return new ConsLoB(this.first, this.rest.allBefore(year));
    else
      return this.rest.allBefore(year);
  }
}

but we have asked the class @tt{Book} to add the method 

@verbatim{
  // was this book produced before the given year?
  boolean producedBefore(int year) {
    return this.year < year;
  }
}

(We omit the discussion of the design of this method.)

Of course, for all of these methods, we end the design process by making 
sure all tests run. The actual test methods will be:

@verbatim{
// tests for the method count
boolean testCount(Tester t) {
  return
  t.checkExpect(this.mtlist.count(), 0) &&
  t.checkExpect(this.lista.count(), 1) &&
  t.checkExpect(this.listd.count(), 3);
}

// tests for the method totalPrice
boolean testTotalPrice(Tester t) {
  return
  t.checkExpect(this.mtlist.totalPrice(), 0) &&
  t.checkExpect(this.lista.totalPrice(), 10) &&
  t.checkExpect(this.listc.totalPrice(), 95) &&
  t.checkExpect(this.listd.totalPrice(), 95);
}
  
// tests for the method allBefore
boolean testBefore(Tester t) {
  return
  t.checkExpect(this.mtlist.allBefore(2001), this.mtlist) &&
  t.checkExpect(this.lista.allBefore(2001), this.lista) &&
  t.checkExpect(this.listb.allBefore(2001), this.mtlist) &&
  t.checkExpect(this.listc.allBefore(2001), 
     new ConsLoB(this.lpp, new ConsLoB(this.ll, this.mtlist))) &&
  t.checkExpect(this.listd.allBefore(2001),
     new ConsLoB(this.ll, new ConsLoB(this.lpp, this.mtlist)));
}
}
  

@section{Accumulators}

We can define our methods in accumulator style. As we did in DrRacket, we will 
design a helper method that takes one more argument, the accumulator. The 
accumulator at any given point in the computation will hold the "answer" to 
our question thus far. 

In the interface @tt{ILoB} the method with the accumulator is the same as before,
with the @emph{suffix} @tt{Acc} in its name, and an added parameter, the accumulator,
that matches the @emph{return type} of the method. We added a new line to the 
purpose statement explaining the role of the accumulator. 

@emph{Remember:} The accumulator at all times holds the final result of the
method for all list elements already seen.

Here are the purpose statements and headers:

@verbatim{ 
// in ILoB

// produce the count of all books in this list
// add to acc the count of books in this list
int countAcc(int acc); 

// produce the total price of the book in this list
// add to acc the price of the books in this list. 
int totalPriceAcc(int acc); 
   
// produce the list of all books in this list published before the given year
// cons to acc the books in this list that are before year. 
LoB allBeforeAcc(int year, ILoB acc);  
}


In the case of the empty list of books, we always just return the accumulator:

@verbatim{
// in MtLoB:

// add to acc the count of books in this list
int countAcc(int acc) { return acc; } 

// add to acc the price of the books in this list. 
int totalPriceAcc(int acc) { return acc; } 
   
// cons to acc the books in this list that are before year. 
ILoB allBeforeAcc(int year, ILoB acc){ return acc; } 
}

The only hard case is the @tt{ConsLoB}. Let's review out template for ConsLoB.

@verbatim{
  TEMPLATE:
  Fields:
    ... this.first ...                                  -- Book
    ... this.rest ...                                   -- ILoB
    
    Methods:
    ... this.count() ...                                 -- int
    ... this.countAcc(int acc) ...                       -- int
    ... this.countAccUp(int acc) ...                     -- int
    ... this.updateCount(Book b, int acc) ...            -- int
    ... this.allBefore(int year) ...                     -- ILoB
    ... this.allBeforeAcc(int year, ILoB acc) ...        -- ILoB
    ... this.allBeforeAccUp(int year, ILoB acc) ...      -- ILoB
    ... this.updateAllBefore(int year, Book b, ILoB acc) -- ILoB
    
    Methods for fields:
    ... this.rest.count() ...                                 -- int
    ... this.rest.countAcc(int acc) ...                       -- int
    ... this.rest.countAccUp(int acc) ...                     -- int
    ... this.rest.allBefore(int year) ...                     -- ILoB
    ... this.rest.allBeforeAcc(int year, ILoB acc) ...        -- ILoB
    ... this.rest.allBeforeAccUp(int year, ILoB acc) ...      -- ILoB
    ... this.rest.updateAllBefore(int year, Book b, ILoB acc) -- ILoB
  */
}

We need tests, but we should be able to just run the same tests as before,
supplying the initial values of the accumulators equal to the base values
that were produced by the methods in the @tt{MtLoB} class. We discuss the 
tests below, once we can run them and observe the results.

The first two methods are easy. To count the books, we invoke the @tt{countAcc}
with a new accumulator: adding one to the current accumulated value. Similarly,
we add the price of the first book to the accumulated price and invoke the method
on the rest of the list with the new value of the accumulator.

For the third method, if the first book should not be added to the resulting list,
we just invoke the method on the rest of the list with the same accumulator 
value - otherwise, we @emph{cons} the first book in this list to the accumulated list:

@verbatim{
// in ConsLoB: 

// add to acc the count of books in this list
int countAcc(int acc) { return this.rest.countAcc(acc + 1); } 

// add to acc the price of the books in this list. 
int totalPriceAcc(int acc) { 
  return this.rest.totalPriceAcc(this.first.price + acc);
} 
   
// cons to acc the books in this list that are before year. 
ILoB allBeforeAcc(int year, ILoB acc){ 
  if (this.first.producedBefore(year))
    return this.rest.allBeforeAcc(year, 
                                  new ConsLoB(this.first, acc));
  else
    return this.rest.allBeforeAcc(year, acc);
}
}


Using the same tests as before, our accumulator methods should give us 
the same results. @bold{But I run my tests and I get an error!} Why? 

Here is one of the tests that failed: 

@verbatim{
t.checkExpect(this.listc.allBeforeAcc(2001, this.mtlist), 
     new ConsLoB(this.lpp, 
         new ConsLoB(this.ll, this.mtlist))
}  
  
 
Our original example was 

@tt{listc.allBefore(2000) => new ConsLoB(lpp, new ConsLoB(ll,mtlist))}

and since the accumulator version of @tt{allBefore} should give the same result
we expected: 

@verbatim{
listc.allBeforeAcc(2000,mtlist) 
       => new ConsLoB(lpp, new ConsLoB(ll,mtlist))}

But this test fails. Let's trace our code. We will write each call on a 
new line.

@verbatim{
   (new ConsLob(lpp, new ConsLoB(ll,mtlist))).allBeforeAcc(2000,mtlist)    [method-call]
=> (new ConsLob(lpp, new ConsLoB(ll,mtlist))).first.producedBefore(2000)       [if-test]
=> lpp.producedBefore(2000)                                                 [this.first]
=> return lpp.year < 2000                                                  [method-call]
=> return 1942 < 2000                                                         [lpp.year]
=> true                                                                            [ < ]
=> return 
   (new ConsLob(lpp,
        new ConsLoB(ll, 
                    mtlist))).rest.allBeforeAcc(2000,
                                                new ConsLoB(lpp,
                                                            mtlist));   [if-branch-true]
=> return 
   (new ConsLoB(ll, mtlist)).allBeforeAcc(2000, new ConsLoB(lpp, mtlist));   [this.rest]

=> (new ConsLoB(ll, mtlist)).first.producedBefore(2000);                       [if-test]
=> ll.producedBefore(2000);                                                 [this.first]
=> return ll.year < 2000                                                   [method-call]
=> return ll.1986 < 2000                                                       [ll.year]
=> return true                                                                     [ < ]
=> (new ConsLoB(ll,
        mtlist)).rest.allBeforeAcc(2000,
                                   new ConsLoB(ll,
                                               new ConsLoB(lpp,
                                                           mtlist)))    [if-branch-true]
=> mtlist.allBeforeAcc(2000, new ConsLoB(ll,
                                         new ConsLoB(lpp,
                                                     mtlist)))               [this.rest]

=> return  new ConsLoB(ll, new ConsLoB(lpp, mtlist)                        [method-call]
=> new ConsLoB(ll, new ConsLoB(lpp, mtlist)                                     [return]
}     

OOPS! The result is not what I expected. The elements in the list are reversed!
This is why our test fails. The answer given by the program is correct. The purpose
statement did not require that the order of the items in the resulting list matches 
the order in the original list, so the result is correct, and we need to adjust our tests.

@section{Sorting}

The last method to design was defined in the interface @tt{ILoB} as:

@verbatim{

// produce a list of all books in this list, sorted by their title
public ILoB sort();
}

An empty list is sorted already, so in the class @tt{MtLoB} the method beciomes:


@verbatim{

// produce a list of all books in this list, sorted by their title
public ILoB sort() {
  return this;
}                    
}

We do not need to create a @tt{new} empty list, @tt{this} one works perfectly well.

We need examples for the more complex cases. We recall our sample data:

@verbatim{
  // sample books
  Book htdp = new Book("HtDP", "MF", 2001, 60);
  Book lpp = new Book("LPP", "STX", 1942, 10);
  Book ll = new Book("LL", "FF", 1986, 25);
  
  // sample lists of books
  ILoB mtlist = new MtLoB();
  ILoB lista = new ConsLoB(this.lpp, this.mtlist);
  ILoB listb =   new ConsLoB(this.htdp, this.mtlist);
  ILoB listc = new ConsLoB(this.lpp, 
                new ConsLoB(this.ll, this.listb));
  ILoB listd = new ConsLoB(this.htdp, 
                new ConsLoB(this.ll, 
                  new ConsLoB(this.lpp, this.mtlist)));
  ILoB listdUnsorted = new ConsLoB(this.lpp, 
      new ConsLoB(this.htdp, 
        new ConsLoB(this.ll, this.mtlist)));
}

and our tests will be:

@verbatim{ 
  // test the method sort for the lists of books
  boolean testSort(Tester t) {
    return
    t.checkExpect(this.listc.sort(), this.listd) &&
    t.checkExpect(this.listdUnsorted.sort(), this.listd);
  }
}

Next we look at the template that is relevant for this question:


@verbatim{
  TEMPLATE:
  ---------
  Fields:
  ... this.first ...                            -- Book
  ... this.rest ...                             -- ILoB
  Methods:
  ... this.sort() ...                           -- ILoB  
  Methods for Fields:
  ... this.rest.sort() ...                      -- ILoB
}

Well, @tt{this.rest.sort()} does almost all the work for us --- it
produces a sorted rest of the list, so the only remaining task is to 
@emph{insert} the first element of the list into the sorted rest.

But this asks for a helper method for the lists of books. In the @tt{ILoB}
it will be:

@verbatim{
// in ILoB
// insert the given book into this list of books 
// already sorted by title
public ILoB insert(Book b);
}

In the class @tt{MtLoB} the answer is simple, just build a list with only the 
given book in it:


@verbatim{
// in MtLoB
// insert the given book into this list of books 
// already sorted by title
public ILoB insert(Book b) {
  return new ConsLoB(b, this);
}
}

and there is a bit of work to do for the !@tt{ConsLoB} class, including
asking the @tt{Book} class for another helper method. We let you work out the rest. 
The final two method bodies will be:


@verbatim{
// in ConsLoB
// insert the given book into this list of books 
// already sorted by title
public ILoB insert(Book b) {
  if (this.first.titleBefore(b)) {
    return new ConsLoB(this.first, this.rest.insert(b));
  }
  else {
    return new ConsLoB(b, this);
  }
}
}


@verbatim{
// in Book
// is the title of this book before the title of the given book?
// lexicographically 
boolean titleBefore(Book that) {
  return this.title.compareTo(that.title) <= 0;
}
}

The class @tt{String} defines a method @tt{int compareTo(String that)} that 
produces a negative number if @tt{this} @tt{String} comes before @tt{that} @tt{String}, 
a zero, if they are equal, and a positive number otherwise.