Lecture: Methods for self-referential lists

5.3.5

Lecture: Methods for self-referential lists

Design methods for unions of classes with self-reference 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) | |

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

| |

/ \ |

--- |

| |

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

| | |

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

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

+-----------------------+ +-| Book first | |

| int totalPrice() | | +-----------------------+

+-----------------------+ | | int totalPrice() |

| | ILoB allBefore(int x) |

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

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

| 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) [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.

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 — it produces a sorted rest of the list, so the only remaining task is to 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 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.