/* Thursday am lecture - Part 1: Circularly Referential Data --- CSU213 Spring 2005 Lecture Notes --------- Copyright 2005 Viera K. Proulx Lecture 20: Books and Authors and Books and Authors and ... */ /* Goals: - learn to program with circlularly referential data - introduce assignment and mutation of objects Introduction: By now we have seen many examples of lists of books and their authors. But here is a new twist! Many books have been co-authored by several authors, and so, a book should not have just one author, but a list of authors. Similarly, one is often interested in knowing what are the other books an author wrote, besides the book we hold in our hands. It would be good for the object that represents the author to include the list of books the author wrote. It is straightforward to define the class hierarchy that accomodates our wishes. The class diagram and the code is shown here, the code is shown later in the code section. +----------------------------------------------+ | +----------------+ | | | | | | v | v | +------+ | +------+ | | ALoB |<----------+ | | ALoA |<------------+ | +------+ | | +------+ | | +------+ | | +------+ | | / \ | | / \ | | --- | | --- | | | | | | | | ---------------- | | ---------------- | | | | | | | | | | +-------+ +------------+ | | +-------+ +--------------+ | | | MTLoB | | ConsLoB | | | | MTLoA | | ConsLoA | | | +-------+ +------------+ | | +-------+ +--------------+ | | +-------+ +-| Book first | | | +-------+ +-| Author first | | | | | ALoB rest |-+ | | | ALoB rest |-+ | | +------------+ | | +--------------+ | | | | | v | v | +--------------+ | +-------------+ | | Book | | | Author | | +--------------+ | +-------------+ | | String title | | | String name | +----| ALoA authors | +-----| ALoB books | | int year | | int year | +--------------+ +-------------+ ------------------------------------------------------------------------ However, we run into a problem when we try to make examples of data. When we define a book object, we already need to have all necessary author objects, but we cannot define an author object without having the book objects for the books the author wrote. Let us think what comes first. There are budding authors for whom we can record their name and year when they were born, but their books have not yet been published. As they write and publish a book, we would like to add the book to the author's list of books. This is actually very important - as over the years, the list of books an author wrote grows. When a book is published, we know for sure who are the authors, and so the list of authors should be available when the book object is first created. We first modify the constructor for the class Author, so that it does not consume an argument that represent the list of books, and instead, initialize this.books to an empty list of books. Author(String name, int year){ this.title = title; this.books = new MTLoB(); this.year = year; } With this restriction we can make examples, but without any credit to the authors for having written the books: // Examples of authors: Author db = new Author("DB", 1957); Author pc = new Author("PC", 1946); Author ap = new Author("AP", 1950); // Examples of lists of authors: ALoA dblist = new ConsLoA(this.db, new MTLoA()); ALoA pclist = new ConsLoA(this.pc, new MTLoA()); ALoA allauthors = new ConsLoA(this.ap,new ConsLoA(this.pc, this.dblist)); // Examples of books: Book dvc = new Book("DVC", this.dblist, 2003); Book mls = new Book("MLS", this.pclist, 2002); Book snx = new Book("SN", this.allauthors, 2001); // Examples of lists of books ALoB booklist1 = new MTLoB(); ALoB booklist2 = new ConsLoB(this.dvc, new ConsLoB(this.mls, this.booklist1)); ALoB booklist3 = new ConsLoB(this.snx, this.booklist2); ------------------------------------------------------------------------ We now need to learn how to add to the Author object the information about the books she wrote. We cannot produce a new Author object, because all the books this author wrote already refer to our original Author object. And, of course, we cannot replace the existing Book objects by new ones, as other authors of that particular book already refer to it in their lists of books. We need to design a method in the class Author that does not produce any new data, just modifies the books field. Here is the purpose and the header: // modify the field books for this author, so it contains the given book void addBook(Book b){ ... } Here are some examples: We start with Author db and add two books to the list of book she wrote: db.add(dvc); db.add(snx); After that, the Author object db should contain the following data: name --> should be "DB" books --> should be new ConsLoB(snx, new ConsLoB(dvc, new MTLoB())) year --> should be 1957 The template for the method is: ... this.name ... ... this.books ... ... this.year ... We make no use of the name and year of birth information. The this.books field should contain all the books that were in the list prior to this method invocation, and the given book b as well. The body of the method is: // modify the field books for this author, so it contains the given book void addBook(Book b){ this.books = new ConsLoB(b, this.books; } The "=" sign here indicates 'assignment' - a change of the meaning of the field reference this.books. If before the method invocation this.books refered to an empty list of books, it now refers to a list that contains one book (Book b). ------------------------------------------------------------------------ We would like to convert our examples into tests. To do so, we design the following test method: // tests for the method addBook in the class Author boolean testAddBook(Author a, Book b){ // make a new copy of the Author object Author aMod = new Author(a.name, a.year); Author aRes = new Author(a.name, a.year); // the constructor srats with an empty list of books // so change it to match the given Author's list of books aMod.books = a.books; aRes.books = new ConsLoB(b, a.books); // add the given book to the book list for our copy aMod.addBook(b); // compare our copy with the given book added to the original booklist return aMod.same(aRes); } It makes two copies of the information in the original Author object, invokes the method that modifies the copied object, and compares the data it contains with the expected values. It leaves the original object unchanged. When designing tests in the presence of mutation, it is important that the side effects of the method being tested do not affect the original data, so it does not interfere with the normal progress of the program, and so that the program behaves identically whether the test suite is enabled or disabled. ------------------------------------------------------------------------ But we run into a new problem. The way we compare two Author objects for equality is by comparing all corresponding fields. Comparing the name and year is easy. However, to compare the lists of books, we need to match tha corresponding Book objects. Two Book objects are considered to be the same, if they have the same title, year of publication, and the same list of authors. Which means, we need to compare the two lists of authors, one by one. Two Author objects are the same if they have the same name, year of birth, and the same list of books. ... Wow!!! we are running around in circles. There are several ways of dealing with this problem. The proper way is to keep track of objects compared already and detect the fact that the same comparison is being repeated. For our purposes, it is easier to relax the criterion for equality of two authors. If the two authors have the same name and year of birth, it is sufficient to compare the titles of the books they wrote. We add a method 'sameTitles' to the classes that represent a list of books, and modify the 'same' method for the class Author as follows: // determine extensional equality of this and given object boolean same(Object obj){ return this.name.equals(((Author)obj).name) && this.books.sameTitles(((Author)obj).books) && this.year == ((Author)obj).year; } We encounter the same problem if we try to design the methods 'toString' that display the data in a meaningful way as String-s. The solution is to add a method that produces a String of titles of the books and use that method inside the toString method for the class Author. ------------------------------------------------------------------------ We are still having difficulties constructing examples of authors with several books to their credit, even though we have several books that know who the authors are. It would make sense to update the author information every time a new book object is constructed. Here is what we mean. Each new book object contains a list of its authors, supplied to the constructor for the Book object. We would like to make sure that as each new Book object is constructed, our combined information about books and authors is ocnsistent. This is typically done by adding to the constructor the code that assures consistency of data or verifies that the provided intial values satisfy the constraint we may have on the possible values of data, such as the value of 'hour' field being in the range from 0 to 24. In our case, we can include in the constructor the code that would add this book to the list of books for every author in the list of authors given to the constructor. We need to add a method to the classes that represent the list of authors that adds the given book to the list of books for every author. So, if a new book ss comes out written by authors sk and rf, then the book ss will be added to the lists of books for sk and for rf. We will leave it to the reader to follow the design recipe and design the method addBook in the classes that represent list of authors. We can now modify the constructor for the class Book as follows: Book(String title, ALoA authors, int year){ this.title = title; this.authors = authors; this.year = year; authors.addBook(this); } and test that it produces the correct data for the objects in the Author class: boolean testBookConstructorEffects1 = this.db.books.same(new ConsLoB(bt.snx, new ConsLoB(bt.dvc, new MTLoB()))); boolean testBookConstructorEffects1 = this.pc.books.same(new ConsLoB(bt.snx, new ConsLoB(bt.mls, new MTLoB()))); We finally have the class hierarchy we need to represent this data and the infrastructure for testing the results of methods we design for this class hierarchy. Several sample methods are included for illustration. The code as shown here runs in full Java with one modification - the visibilty modifier for the interface ISame should be 'public'. (ProfessorJ rejected it - but that is a bug that will be fixed.) ------------------------------------------------------------------------ */ /* ; ; ; ; ; ;;;; ; ; ; ; ; ; ; ; ; ; ;;; ; ;; ;; ;;; ; ; ;; ; ; ;; ;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;; ; ; ; ;;;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;; ;;;;; ; ; ; ;;;; ; ; ; */ interface ISame{ // is this object the same as the given object boolean same(Object obj); } /* ; ; ; ; ;;;;; ; ; ; ; ; ; ; ; ; ; ; ; ;;; ;;; ; ; ; ;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;; ; ; ; ;;; ; ; ;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;;; ;;; ;;; ; ; ; ; ; */ // to represent a book class Book implements ISame{ String title; ALoA authors; int year; Book(String title, ALoA authors, int year){ this.title = title; this.authors = authors; this.year = year; this.authors.addBook(this); } // was this book published before the given year boolean before(int year){ return this.year < year; } // was this book written by the given author boolean sameAuthor(Author a){ return this.authors.contains(a); } // count the authros of this book int countAuthors(){ return this.authors.count(); } // determine extensional equality of this and given object boolean same(Object obj){ return this.title.equals(((Book)obj).title) && this.authors.same(((Book)obj).authors) && this.year == ((Book)obj).year; } // provide the values of this instance represented as a String String toString(){ return ("\n Book: ").concat( "\n title: ").concat(this.title).concat( "\n author: ").concat(this.authors.toString()).concat( "\n year: ").//concat(this.year). concat("\n"); } /* Template * * ... this.title ... * ... this.author ... * ... this.author.sameName(String name) ... * ... this.year ... * ... this.before(int year) ... * ... this.sameAuthor(String name) ... * ... this.toString() ... * */ } /* ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;; ; ;; ;;; ; ; ; ; ; ; ; ; ;; ; ; ; ;; ; ; ; ; ; ; ; ; ; ; ; ; ;;;;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;; ; ; ; ; ; ; ; ; ; ;; ; ;; ; ; ;;; ; ; ; ; */ // to represent an author of a book class Author implements ISame{ String name; int year; ALoB books; Author(String name, int year){ this.name = name; this.year = year; this.books = new MTLoB(); } // add the given book to this author's list of books void addBook(Book b){ this.books = new ConsLoB(b, this.books); } // count the number of books written by this author int countBooks(){ return this.books.count(); } // is this author's name the same as the given one boolean sameName(String name){ return this.name.equals(name); } // determine extensional equality of this and given object boolean same(Object obj){ return this.name.equals(((Author)obj).name) && this.books.sameTitles(((Author)obj).books) && this.year == ((Author)obj).year; } // provide the values of this instance represented as a String String toString(){ return "\n Author: ".concat( "\n name: ") .concat(this.name) .concat( "\n year: ") . //concat(this.year) . concat( "\n" ) .concat( "\n books: ") .concat(this.books.titleString()); } /* Template * * ... this.name ... * ... this.year ... * ... this.sameName(String name) ... * ... this.toString() ... * */ } /* ; ; ; ; ; ; ;;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;; ; ; ; ; ; ; ; ; ;;;; ; ; ; ; ; ; ; ; ; ;;;;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;;;; ;;; ;;;;; ; ; ; */ // to represent a list of books abstract class ALoB{ // does this list contain the given book abstract boolean contains(Book b); // count the authors in this list abstract int count(); // determine extensional equality of this and given object boolean same(Object obj){ return this.sameLoB((ALoB)obj); } // determine extensional equality of this and given list of books abstract boolean sameLoB(ALoB alist); // determine extensional equality of this and given list of books boolean sameMTLoB(MTLoB alist){ return false; } // determine extensional equality of this and given list of books boolean sameConsLoB(ConsLoB alist){ return false; } // are the titles of the books in this list and given list the same abstract boolean sameTitles(ALoB books); // are the titles of the books in this list and given list the same boolean sameTitlesMT(MTLoB books){ return false; } // are the titles of the books in this list and given list the same boolean sameTitlesCons(ConsLoB books){ return false; } // provide the values of this instance represented as a String abstract String toString(); // provide the titles of books in this list as a String abstract String titleString(); } /* ; ; ; ; ; ; ;;;;;;; ; ;;;;; ; ;; ;; ; ; ; ; ; ;; ;; ; ; ; ; ; ; ; ; ; ; ; ;;; ; ; ; ; ; ; ; ; ; ; ; ;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;;;; ;;; ;;;;; ; ; ; */ // to represent an empty list of books class MTLoB extends ALoB{ MTLoB(){} // does this list contain the given book boolean contains(Book b){ return false; } // count the books in this list int count(){ return 0; } // determine extensional equality of this and given list of books boolean sameLoB(ALoB alist){ return alist.sameMTLoB(this); } // is this list the same as the given empty list boolean sameMTLoB(MTLoB alist){ return true; } // are the titles of the books in this list and given list the same boolean sameTitles(ALoB books){ return books.sameTitlesMT(this); } // are the titles of the books in this list and given list the same boolean sameTitlesMT(MTLoB books){ return true; } // provide the values of this instance represented as a String String toString(){ return ("\n MTLoB: ") .concat(" *\n"); } // provide the titles of books in this list as a String String titleString(){ return "\nLast title: *\n"; } } /* ; ; ; ; ;;;; ; ;;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;; ; ;; ;;; ; ;;; ; ; ; ; ; ; ;; ; ; ; ; ; ;;;; ; ; ; ; ; ; ;; ; ; ; ; ; ; ; ; ; ; ; ;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;; ;;; ; ; ;;; ;;;;;; ;;; ;;;;; ; ; ; */ // to represent a nonempty list of books class ConsLoB extends ALoB{ Book first; ALoB rest; ConsLoB(Book first, ALoB rest){ this.first = first; this.rest = rest; } // does this list contain the given book boolean contains(Book b){ return this.first.same(b) || this.rest.contains(b); } // count the books in this list int count(){ return 1 + this.rest.count(); } // determine extensional equality of this and given list of books boolean sameLoB(ALoB alist){ return alist.sameConsLoB(this); } // is this list the same as the given empty list boolean sameConsLoB(ConsLoB alist){ return this.first.same(alist.first) && this.rest.same(alist.rest); } // are the titles of the books in this list and given list the same boolean sameTitles(ALoB books){ return books.sameTitlesCons(this); } // are the titles of the books in this list and given list the same boolean sameTitlesCons(ConsLoB books){ return this.first.title.compareTo(books.first.title) == 0 && this.rest.sameTitles(books.rest); } // provide the values of this instance represented as a String String toString(){ return ("\n ConsLoB: ").concat( "\n first: ").concat(this.first.toString()).concat( "\n rest: ").concat(this.rest.toString()).concat("\n"); } // provide the titles of books in this list as a String String titleString(){ return ("\nTitle: ").concat(this.first.title).concat( this.rest.titleString()); } /* Template * * ... this.first ... * ... this.first.title ... * ... this.first.author ... * ... this.first.year ... * ... this.rest ... * ... this.rest.contains(Book b) ... * ... this.rest.toString() ... * */ } /* ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;;;;; ; ; ; ;;;;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;;;; ;;; ; ; ; ; ; */ //to represent a list of authors abstract class ALoA implements ISame{ // does this list contain the given author abstract boolean contains(Author a); // add the given book to all authors in this list abstract void addBook(Book b); // count the authors in this list abstract int count(); // determine extensional equality of this and given object boolean same(Object obj){ return this.sameLoA((ALoA)obj); } // determine extensional equality of this and given list of authors abstract boolean sameLoA(ALoA alist); // determine extensional equality of this and given list of authors boolean sameMTLoA(MTLoA alist){ return false; } // determine extensional equality of this and given list of authors boolean sameConsLoA(ConsLoA alist){ return false; } // provide the values of this instance represented as a String abstract String toString(); } /* ; ; ; ; ; ; ;;;;;;; ; ; ; ;; ;; ; ; ; ; ;; ;; ; ; ; ; ; ; ; ; ; ; ; ;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;;;; ;;; ; ; ; ; ; */ //to represent an empty list of authors class MTLoA extends ALoA{ MTLoA(){} // does this list contain the given author boolean contains(Author a){ return false; } // add the given book to all authors in this list void addBook(Book b){ } // count the authors in this list int count(){ return 0; } // determine extensional equality of this and given list of authors boolean sameLoA(ALoA alist){ return alist.sameMTLoA(this); } // is this list the same as the given empty list boolean sameMTLoA(MTLoA alist){ return true; } // provide the values of this instance represented as a String String toString(){ return ("\n MTLoB: ").concat(" *\n"); } } /* ; ; ; ; ;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;; ; ;; ;;; ; ;;; ; ; ; ; ; ; ;; ; ; ; ; ; ; ; ; ; ; ; ; ; ;; ; ; ; ; ; ; ; ; ; ; ; ;; ; ; ; ;;;;;;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;;;; ;;; ; ; ;;; ;;;;;; ;;; ; ; ; ; ; */ //to represent a nonempty list of authors class ConsLoA extends ALoA{ Author first; ALoA rest; ConsLoA(Author first, ALoA rest){ this.first = first; this.rest = rest; } // does this list contain the given author boolean contains(Author a){ return this.first.same(a) || this.rest.contains(a); } // count the authors in this list int count(){ return 1 + this.rest.count(); } // add the given book to all authors in this list void addBook(Book b){ this.first.addBook(b); this.rest.addBook(b); } // determine extensional equality of this and given list of authors boolean sameLoA(ALoA alist){ return alist.sameConsLoA(this); } // is this list the same as the given empty list boolean sameConsLoA(ConsLoA alist){ return this.first.same(alist.first) && this.rest.same(alist.rest); } // provide the values of this instance represented as a String String toString(){ return ("\n ConsLoA: ").concat( "\n first: ").concat(this.first.toString()).concat( "\n rest: ").concat(this.rest.toString()).concat("\n"); } /* Template * * ... this.first ... * ... this.first.sameName(Author a) ... * ... this.first.same(Object obj... * ... this.rest ... * ... this.rest.contains(Book b) ... * ... this.rest.toString() ... * */ } /* ; ; ; ; ;;;;;; ; ; ; ; ; ; ; ; ; ; ; ;;; ; ;; ;; ; ;; ; ;;; ;;; ; ;;;;; ; ; ; ; ;; ;; ; ;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;; ; ; ; ;;;; ; ; ; ; ; ; ;;;;;; ;; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;; ; ; ; ; ; ;;;;;;; ; ;;;;; ; ; ; ; ;; ; ;;;; ;;; ; ; ; ; ; ; */ class Examples{ Examples(){} // Examples of authors: Author db = new Author("DB", 1957); Author pc = new Author("PC", 1946); Author ap = new Author("AP", 1950); // Examples of lists of authors: ALoA dblist = new ConsLoA(this.db, new MTLoA()); ALoA pclist = new ConsLoA(this.pc, new MTLoA()); ALoA allauthors = new ConsLoA(this.ap,new ConsLoA(this.pc, this.dblist)); // Examples of books: Book dvc = new Book("DVC", this.dblist, 2003); Book mls = new Book("MLS", this.pclist, 2002); Book snx = new Book("SN", this.allauthors, 2001); // Examples of lists of books ALoB booklist1 = new MTLoB(); ALoB booklist2 = new ConsLoB(this.dvc, new ConsLoB(this.mls, this.booklist1)); ALoB booklist3 = new ConsLoB(this.snx, this.booklist2); // test the effect of the Book constructo on the Author objects boolean testBookConstructorEffects1 = this.db.books.same(new ConsLoB(this.snx, new ConsLoB(this.dvc, new MTLoB()))); boolean testBookConstructorEffects2 = this.pc.books.same(new ConsLoB(this.snx, new ConsLoB(this.mls, new MTLoB()))); // tests for the method addBook in the class Author boolean testAddBook(Author a, Book b){ // make a new copy of the Author object Author aMod = new Author(a.name, a.year); Author aRes = new Author(a.name, a.year); // the constructor srats with an empty list of books // so change it to match the given Author's list of books aMod.books = a.books; aRes.books = new ConsLoB(b, a.books); // add the given book to the book list for our copy aMod.addBook(b); // compare our copy with the given book added to the original booklist return aMod.same(aRes); } // test the addBook method in the class Author boolean testAddBook1 = this.testAddBook(this.db, this.dvc); boolean testAddBook2 = this.testAddBook(this.ap, this.snx); // test for the method before(int year) boolean testBefore1 = this.dvc.before(2004) == true; boolean testBefore2 = this.dvc.before(1990) == false; // test the method sameAuthor(String name) in the class Book boolean testSameAuthor1 = this.dvc.sameAuthor(this.db) == true; boolean testSameAuthor2 = this.dvc.sameAuthor(this.pc) == false; // test the method sameName(String name) in the class Author boolean testSameName1 = this.db.sameName("DB") == true; boolean testSameName2 = this.db.sameName("PC") == false; // test the method countBooks() in the class Author boolean testCountBooks1 = this.db.countBooks() == 2; boolean testCountBooks2 = this.ap.countBooks() == 1; // test the method countAuthors() in the class Book boolean testCountAuthors1 = this.dvc.countAuthors() == 1; boolean testCountAuthors2 = this.snx.countAuthors() == 3; // test the method contains(Book b) in the class ALoB boolean testContains1 = this.booklist1.contains(this.mls) == false; boolean testContains2 = this.booklist2.contains(this.mls) == true; boolean testContains3 = this.booklist2.contains(this.snx) == false; }