(*
 * This file implements a binary search tree and
 * includes a small test suite in main().
 *
 * available BST member functions:
 * 
 *   init()		returns a Tree object ( for new )
 *   insert(x : Int)	inserts a node having value x
 *   delete(x : Int)	deletes the node having value x
 *   find(x : Int)	finds the node having value x
 *   size()		returns number of nodes in tree
 *   empty()		returns true if empry, false if not
 *   findmin()		returns largest value in tree
 *   findmax()    	returns smallets value in tree
 *   print()		prints all values in tree
*)


-- tree node
class Node {
    
    -- private members
    value : Int;
    left : Node;
    right : Node;
    
    -- member functions
    value() : Int { value };
    
    left() : Node { left };
    right() : Node { right };

    set_left(x : Node) : Node {
	left <- x
    };

    set_right(x : Node) : Node {
	right <- x
    };

    set_value(x : Int) : Int {
	value <- x
    };

    init(x : Int) : Node {
	{
	    value <- x;
	    self;
	}
    };
};

-- tree class
class Tree inherits IO {	
    
    -- private members
    tree : Node;
    size : Int;	
    
    -- return number of elements in tree
    size() : Int { size };
    
    -- is the tree empty?
    empty() : Bool {
	if size = 0 then true
	else false
        fi
    };

    -- insert an element in the tree
    insert(x : Int) : Int {
	{
	    tree <- ninsert(x, tree);
	    size <- size + 1;
	    0;
	}
    };
	
    -- internal insert function
    ninsert(x : Int, t : Node) : Node {
	{
	    -- recursively find new node location and insert
	    if isvoid t then 
	      t <- (new Node.init(x)) else 
	    if x < t.value() then
	      t.set_left(ninsert(x, t.left())) else
	    if t.value() < x then
	      t.set_right(ninsert(x, t.right())) else
	    abort()
	    fi fi fi;
	    t;
	}
    };

    -- not yet working because of inability to self <- void
    -- would need to keep track of parent node and left/right relationships
    delete(x : Int) : Node {
	ndelete(x, tree)
    };

    -- see delete above
    ndelete(x: Int, tr : Node) : Node {
	(let t : Node <- self.find(x) in
	 if isvoid t then t else
	 {
	     if not isvoid t.left() then {
		 if not isvoid t.right() then
		     {
			 out_string("here\n");
			 t.set_value(nfindmin(t.right()).value());
			 t.right().set_right(ndelete(x, t.right()));
		     }
		 else { 
		     out_string("here3\n");
		     t <- t.left(); -- does not work
		 } fi;
	     }
	     else {
		 out_string("here2\n");
		 t <- t.right(); -- does not work
	     } fi;
	 } fi
	)
    };	
    
    -- finds a specific node by value
    find(x : Int) : Node {
	nfind(x, tree)
    };

    -- internal find function
    nfind(x : Int, t : Node) : Node {
	-- recursively search for node in BST
	(let ret : Node in
	 if isvoid t then ret else
	 if x < t.value() then nfind(x, t.left()) else
	 if t.value() < x then nfind(x, t.right()) else
	 t fi fi fi
	)
    };  

    -- returns the largest value in BST
    findmax() : Int {
	(let t : Node <- tree, max : Int <- t.value() in
	 {
	     if not isvoid t then {
		 while (not isvoid t.right()) loop
		     {
			 max <- t.right().value();
			 t <- t.right();
		     }
		 pool;
	     }
	     else abort() fi;
	     max;
	 }
	)
    };

    -- returns the smallest value in BST
    findmin() : Int {
        (let t : Node <- tree, min : Int <- t.value() in
         {
             if not isvoid t then {
                 while (not isvoid t.left()) loop
                     {
                         min <- t.left().value();
                         t <- t.left();
                     }
                 pool;
             }
             else abort() fi;
             min;
         }
        )
    };

    -- internal findmin function to return smallest value node
    nfindmin(t : Node) : Node {
	(let min : Int <- t.value() in
	 {
	     if not isvoid t then {
		 while (not isvoid t.left()) loop
		     {
			 min <- t.left().value();
			 t <- t.left();
		     }
		 pool;
	     }
	     else abort() fi;
	     t;
	 }
	)
    };
    
    -- prints the tree
    print() : Int {
	nprint(tree)
    };

    -- internal print function, recursively print left/right subtrees
    nprint(t : Node) : Int {
	if not isvoid t then {
	    out_int(t.value());
	    out_string(" ");
	    nprint(t.left());
	    nprint(t.right());
	}
	else 0 fi
    };

    init() : SELF_TYPE {
	{
	    size <- 0;
	    self;
	}
    };       
};

-- main class
class Main inherits IO {
    
    -- create a new BST
    myTree : Tree <- (new Tree.init());
    
    main() : Object {
	{
	    -- read numbers from stdin, stops on 0
	    (let input : Int in
	     {
		 while (not 0 = (input <- in_int())) loop
		     myTree.insert(input)
		 pool;
	     }
	    );
	    
	    -- some info...
	    out_string("Number of nodes in tree: ");
	    out_int(myTree.size());
	    out_string("\n");
	    myTree.print();
	    out_string("\nMax: ");
	    out_int(myTree.findmax());
	    out_string("\nMin: ");
	    out_int(myTree.findmin());
	    out_string("\n");
	    
	    -- look for some specific nodes
	    out_string("Searching for nodes 11 and 111\n");

	    (let test1 : Node <- myTree.find(111),
	         test2 : Node <- myTree.find(11) in
	     {
		 if isvoid test1 then out_string("11 not found\n") else
		 {
		     out_int(test1.value());
		     out_string(" found\n");
		 } fi;
		 if isvoid test2 then out_string("11 not found\n") else
		 {
		     out_int(test2.value());
		     out_string(" found\n");
		 } fi;
	     }
	    );
	    
	    -- testing delete
	    -- myTree.delete(111);
	    -- myTree.print();
	    -- out_string("\n");

	}
    };
};