/*
 * Bank accounts BST: original implementation
 */

import tester.*;

/*
                  +---------------+-+
                  |               | |
                  v               | |                                      
           +-------------+        | |                
           |  IBSTAcct   |        | |
           +-------------+        | |
           +-------------+        | |
                  |               | |
                  |               | |
                 /_\              | |
                  |               | |
        +--------------+          | |
        v              v          | |
 +----------+  +----------------+ | |    
 | LeafAcct |  | NodeAcct       | | |  
 +----------+  +----------------+ | | 
               | Acct data      | | | 
             +-| IBSTAcct left  |-+ |
             | | IBSTAcct right |---+
            | +-----------------+
            v
   +---------------+
   | Acct          |
   +---------------+
   | String owner  |
   | String kind   |
   | int balance   |
   +---------------+  
 */

//to represent an account in a bank
class Acct{
	String owner;
	String kind;
	int balance;

	Acct(String owner, String kind, int balance){
		this.owner = owner;
		this.kind = kind;
		this.balance = balance;
	}

	/* TEMPLATE:
FIELDS:
 ... this.owner ...             -- String
 ... this.kind ...              -- String
 ... this.balance ...           -- int

 METHODS FOR FIELDS:
 ... this.owner.equals(String) ... -- boolean  
 ... this.kind.equals(String) ...  -- boolean  

 METHODS FOR THIS CLASS:
 ... this.compareTo(Acct) ...      -- int
	 */

	// does this account have a lower balance than the given one?
	int compareTo(Acct that){
		return this.balance - that.balance;
	}

}                     

// to represent a list of books
interface IBSTAcct{

	// compute the total size of this binary search tree
	int size();

	// add the given account to this binary search tree
	IBSTAcct add(Acct a);
}                                

// to represent an empty list of accounts
class LeafAcct implements IBSTAcct{
	LeafAcct(){}

	// compute the total size of this binary search tree
	public int size(){
		return 0;
	}

	// add the given account to this binary search tree
	public IBSTAcct add(Acct b){
		return new NodeAcct(b, this, this);
	}
}                                              

// to represent a nonempty list of accounts
class NodeAcct implements IBSTAcct{
	Acct data;
	IBSTAcct left;
	IBSTAcct right;

	NodeAcct(Acct data, IBSTAcct left, IBSTAcct 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 list
	public int size(){
		return 1 + this.left.size() + this.right.size();
	}

	// does this list of books contain the given book?
	public IBSTAcct add(Acct b){
		if (this.data.compareTo(b) < 0){
			return new NodeAcct(this.data,
					this.left,
					this.right.add(b));
		} else {
			return new NodeAcct(this.data,
					this.left.add(b),
					this.right);
		}
	}
}                                                    

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


	Acct chk1 = new Acct("JFK", "checking", 4000);
	Acct chk2 = new Acct("LBJ", "checking", 1000);
	Acct sav = new Acct("DDE", "savings", 2000);
	Acct credit = new Acct("RMN", "credit card", 3000);
	  

	IBSTAcct leaf = new LeafAcct();
	IBSTAcct node = new NodeAcct(this.sav, this.leaf, this.leaf);
	IBSTAcct nodes2 = new NodeAcct(this.sav, 
			                           new NodeAcct(this.chk2, this.leaf, this.leaf), 
			                           this.leaf);
	IBSTAcct tree = new NodeAcct(this.sav, 
			                         new NodeAcct(this.chk2, this.leaf, this.leaf),
			                         new NodeAcct(this.chk1, this.leaf, this.leaf));
	
	// test the method compare in the Acct class
	boolean testCompare(Tester t){
		return
		t.checkExpect(
				this.chk1.compareTo(new Acct("JFK", "checking", 4000)),  
				0) &&
				t.checkExpect(this.chk2.compareTo(this.chk1) < 0, true) &&
				t.checkExpect(this.chk1.compareTo(this.sav) > 0,  true) ;}

	// test the method size in the classes that implement IBSTAcct
	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 contains in the classes that implement IBSTAcct
	boolean testAdd(Tester t){
		return
		t.checkExpect(this.leaf.add(this.sav),  node) &&
		t.checkExpect(this.node.add(this.chk2),  this.nodes2) &&
		t.checkExpect(this.node.add(this.chk1).add(this.chk2),  this.tree);}

}