/*
 * Bookstore BST: original implementation
 */

import tester.*;

/*
                  +---------------+-+
                  |               | |
                  v               | |                                      
           +-------------+        | |                
           |  IBSTBook   |        | |
           +-------------+        | |
           +-------------+        | |
                  |               | |
                  |               | |
                 /_\              | |
                  |               | |
        +--------------+          | |
        v              v          | |
 +----------+  +----------------+ | |    
 | LeafBook |  | NodeBook       | | |  
 +----------+  +----------------+ | |  
               | Book data      | | |
             +-| IBSTBook left  |-+ |
             | | IBSTBook right |---+
            | +-----------------+
            v
   +---------------+
   | Book          |
   +---------------+
   | String title  |
   | String author |
   | int year      |
   +---------------+  
*/
                          
// to represent a book in a bookstore
class Book{
  String title;
  String author;
  int year;
  
  Book(String title, String author, int year){
    this.title = title;
    this.author = author;
    this.year = year;
  }

/* TEMPLATE:
   FIELDS:
    ... this.title ...              -- String
    ... this.author ...             -- String
    ... this.year ...               -- int

    METHODS FOR FIELDS:
    ... this.name.equals(String) ...   -- boolean 
    ... this.author.equals(String) ... -- boolean   
  
    METHODS FOR THIS CLASS:
    ... this.compareTo(Book) ...       -- int
*/

  // was this book written later that the given book?
  int compareTo(Book that){
    return this.year - that.year;
  }

}                     

// to represent a binary search tree of books
interface IBSTBook{
  
  // compute the total size of this binary search tree
  int size();
  
  // add the given book to this binary search tree
  IBSTBook add(Book b);
}                                

// to represent a leaf in a binary search tree
class LeafBook implements IBSTBook{
  LeafBook(){}
  
  // compute the total size of this binary search tree
  public int size(){
    return 0;
  }
  
  // add the given book to this binary search tree
  public IBSTBook add(Book b){
  	return new NodeBook(b, this, this);
  }
}                                              

// to represent a node in a binary search tree
class NodeBook implements IBSTBook{
  Book data;
  IBSTBook left;
  IBSTBook right;
  
  NodeBook(Book data, IBSTBook left, IBSTBook right){
    this.data = data;
    this.left = left;
    this.right = right;
  }
  

/* TEMPLATE:
   FIELDS:
    ... this.data ...               -- Book
    ... this.left ...               -- IBSTBook
    ... this.right ...              -- IBSTBook

    METHODS FOR FIELDS:
    ... this.data.compareTo(Book) ... -- int
  
    ... this.left.size() ...          -- int
    ... this.left.add(Book) ...       -- IBSTBook
    
    ... this.right.size() ...         -- int
    ... this.right.add(Book) ...      -- IBSTBook

*/
  
  // compute the total size of this binary search tree
  public int size(){
    return 1 + this.left.size() + this.right.size();
  }
  
  // add the given book to this binary search tree
  public IBSTBook add(Book b){
  	if (this.data.compareTo(b) < 0){
  		return new NodeBook(this.data,
  				                this.left,
  				                this.right.add(b));
  	} else {
  		return new NodeBook(this.data,
  												this.left.add(b),
                          this.right);
  	}
  }
}                                                    

// Examples and tests for books and BSTs of books
class Examples{
  Examples(){}

  Book oms = new Book("Old Man and the Sea", "Hemingway", 1952);
  Book eos = new Book("Elements of Style", "EBW", 1927);
  Book htdp = new Book("HtDP", "MF", 2001);
  Book ll = new Book("Little Lisper", "MF", 1995);
  
  IBSTBook leaf = new LeafBook();
  IBSTBook node = new NodeBook(this.oms, this.leaf, this.leaf);
  IBSTBook nodes2 = new NodeBook(this.oms, 
  		                           new NodeBook(this.eos, this.leaf, this.leaf), 
  		                           this.leaf);
  IBSTBook tree = new NodeBook(this.oms, 
  		                         new NodeBook(this.eos, this.leaf, this.leaf),
  		                         new NodeBook(this.htdp, this.leaf, this.leaf));
   
  // test the method compare in the Book class
  boolean testCompare(Tester t){
    return
    t.checkExpect(
    		this.oms.compareTo(new Book("Old Man and the Sea", "Hemingway", 1952)),  
    		0) &&
    t.checkExpect(this.eos.compareTo(this.htdp) < 0, true) &&
    t.checkExpect(this.htdp.compareTo(this.ll) > 0,  true) ;}

  // test the method size in the classes that implement IBSTBook
  boolean testSize(Tester t){
    return
    t.checkExpect(this.leaf.size(),  0) &&
    t.checkExpect(this.node.size(),  1) &&
    t.checkExpect(this.tree.size(),  3);}
    
  // test the method add in the classes that implement IBSTBook
  boolean testContains(Tester t){
    return
    t.checkExpect(this.leaf.add(this.oms),  node) &&
    t.checkExpect(this.node.add(this.eos),  this.nodes2) &&
    t.checkExpect(this.node.add(this.htdp).add(this.eos),  this.tree);}

}