Lecture: Methods for selfreferential lists
Design methods for unions of classes with selfreference that represent lists.
Basic loops.
Accumulators.
Sorting.
BookLists.java
Lecture outline
Representing lists
Basic loops
Accumulators
Sorting
1 Representing lists
The following class diagram defines class hierarchy that represents a list of books in a bookstore:
++ 
 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  
++ 
Let’s make some examples
//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))); 
2 Basic loops
Given this preceding class diagram, we would like to design methods to answer the following questions
Count how many books we have in a list of books
Compute the total price of all books in a list of books
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
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 interface ILoB:
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 MtLoB and in the class ConsLoB. You may find ti helpful to recall similar functions in DrRacket.
The 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:
Examples for the class MtLoB 
 
mtlist.count() => 0 
mtlist.totalPrice() => 0 
mtlist.allBefore() => mtlist 
and our methods become:
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 ConsLoB class. First, examples!
Note: We will work on the sort method separately, later.
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 design recipe asks us now to derive the template. A template serves as a starting point for any method inside ConsLoB:
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 this.rest.count() produces the count of all books in the rests of this list  and so the method body in the class ConsLoB becomes:
// count the books in this list 
int count(){ return 1 + this.rest.count(); } 
In the template this.rest.totalPrice() produces the total price of all books in the rests of this list  and so the method body in the class ConsLoB just adds to this value the price if the first book in the list:
// calculate the total price of all books in this list 
int totalPrice() { 
return this.first.price + this.rest.totalPrice(); 
} 
In the template this.rest.allBefore(year) produces a list of all books in the rests of this list published before the given date  and so the method body in the class 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 ConsLoB becomes:
// 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 Book to add the method
// 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:
// 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))); 
} 
3 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 ILoB the method with the accumulator is the same as before, with the suffix Acc in its name, and an added parameter, the accumulator, that matches the return type of the method. We added a new line to the purpose statement explaining the role of the accumulator.
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:
// 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:
// 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 ConsLoB. Let’s review out template for ConsLoB.
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 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 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 cons the first book in this list to the accumulated list:
// 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. But I run my tests and I get an error! Why?
Here is one of the tests that failed:
t.checkExpect(this.listc.allBeforeAcc(2001, this.mtlist), 
new ConsLoB(this.lpp, 
new ConsLoB(this.ll, this.mtlist)) 
Our original example was
listc.allBefore(2000) => new ConsLoB(lpp, new ConsLoB(ll,mtlist))
and since the accumulator version of allBefore should give the same result we expected:
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.
(new ConsLob(lpp, new ConsLoB(ll,mtlist))).allBeforeAcc(2000,mtlist) [methodcall] 
=> (new ConsLob(lpp, new ConsLoB(ll,mtlist))).first.producedBefore(2000) [iftest] 
=> lpp.producedBefore(2000) [this.first] 
=> return lpp.year < 2000 [methodcall] 
=> return 1942 < 2000 [lpp.year] 
=> true [ < ] 
=> return 
(new ConsLob(lpp, 
new ConsLoB(ll, 
mtlist))).rest.allBeforeAcc(2000, 
new ConsLoB(lpp, 
mtlist)); [ifbranchtrue] 
=> return 
(new ConsLoB(ll, mtlist)).allBeforeAcc(2000, new ConsLoB(lpp, mtlist)); [this.rest] 

=> (new ConsLoB(ll, mtlist)).first.producedBefore(2000); [iftest] 
=> ll.producedBefore(2000); [this.first] 
=> return ll.year < 2000 [methodcall] 
=> return ll.1986 < 2000 [ll.year] 
=> return true [ < ] 
=> (new ConsLoB(ll, 
mtlist)).rest.allBeforeAcc(2000, 
new ConsLoB(ll, 
new ConsLoB(lpp, 
mtlist))) [ifbranchtrue] 
=> mtlist.allBeforeAcc(2000, new ConsLoB(ll, 
new ConsLoB(lpp, 
mtlist))) [this.rest] 

=> return new ConsLoB(ll, new ConsLoB(lpp, mtlist) [methodcall] 
=> 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.
4 Sorting
The last method to design was defined in the interface ILoB as:

// 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 MtLoB the method beciomes:

// 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 new empty list, this one works perfectly well.
We need examples for the more complex cases. We recall our sample data:
// 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:
// 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:
TEMPLATE: 
 
Fields: 
... this.first ...  Book 
... this.rest ...  ILoB 
Methods: 
... this.sort() ...  ILoB 
Methods for Fields: 
... this.rest.sort() ...  ILoB 
Well, this.rest.sort() does almost all the work for us —
But this asks for a helper method for the lists of books. In the ILoB it will be:
// in ILoB 
// insert the given book into this list of books 
// already sorted by title 
public ILoB insert(Book b); 
In the class MtLoB the answer is simple, just build a list with only the given book in it:
// 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 !ConsLoB class, including asking the Book class for another helper method. We let you work out the rest. The final two method bodies will be:
// 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); 
} 
} 
// 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 String defines a method int compareTo(String that) that produces a negative number if this String comes before that String, a zero, if they are equal, and a positive number otherwise.