(*This program is implemented to enable some basic operations on
a Binary Search Tree.Binary Search Tree is a tree in which considering 
a parent node,values of all the nodes in left subtree is smaller than
or equal to the value of the parent node and values of all the nodes
in right subtree is greater than the value of the parent node.
The file consists of three classes; Node,BSTree and Main.
First class Node carries the properties of a Node of a tree. The second class 
BSTree uses instances of Node classes in order to serve as a search and sorting tool.
Implemented methods are tested in the Main class.*)

(*This class is implemented to have properties and 
operations allowed on a Node of any Binary Search Tree.
Properties of a Node are consting of a pointer to its 
left child, a pointer to its right child, and the value of
the node. Note that there is no pointers to the parent node
because I did not implement delete operation on BSTree. The 
operations will be explained at where they are implemented *)

class Node{
	left_child : Node;
	right_child : Node;	
	value : Int ;

		(*This is the constructer of the class Node.
		Once a new instance is created the value of 
		the node could be assigned using init method*)
	init(a:Int) : SELF_TYPE {
		{
		value <- a;
		self;
		}
	};
	
	--To set the left child
	set_left_ch(n : Node) : SELF_TYPE{
		{
		left_child <- n;
		self;	
		}
	};
	
	--To set the right child
	set_right_ch(n : Node ) : SELF_TYPE {
		{
		right_child <- n;
		self;
		}
	};
	
	--To set the value of the Node
	set_value (a : Int) : SELF_TYPE {
		{
		value <- a;
		self;
		}
	};
	
	--Returns a reference to the left child of the Node if it has,returns void otherwise
	get_left_ch () : Node  { left_child	};

	--Returns a reference to the right child of the Node if it has,returns void otherwise
	get_right_ch () : Node { right_child	};

	--Returns the value of the Node
	get_value () : Int    { value		};
};


(*This class is a basic implementation of a Binary Search Tree.
Since all nodes have references to their children we only need to
store the root of the tree,and can reach to every nodes by
traversing the tree.*)

class BSTree inherits IO{
	
	root : Node;

	(*This is the constructer of the class. While an instance of 
	BSTree is being created a root with given value could be
	added to this tree using this init method*)
	init ( a:Int ) : SELF_TYPE {
		{
		root <- ( new Node ).init(a);
		self;
		}
	}; 
	
	--Returns the root of the tree
	get_root () : Node { root };
	
	--This method is to insert a new Node to the tree with the given value
	--Method gives control of execution to the recursive method find_parent
	add_value (a : Int) : SELF_TYPE {
		{
		find_parent(a,root); --Start with root to try to find appropriate parent of the node
		self;
		}
	};
	
	--This function traverses the tree recursively in order to find the
	--node which is supposed to be newly to be created Node. And returns that Node. 
	find_parent (a : Int, n : Node) : Node {
		
	 	if n.get_value() <= a then
			if isvoid n.get_right_ch() then n.set_right_ch((new Node).init(a))
			else find_parent (a , n.get_right_ch())
			fi
		else 	if isvoid n.get_left_ch() then n.set_left_ch((new Node).init(a)) 
			else find_parent (a, n.get_left_ch())
			fi	
	 	fi
		
	};
	
	--This method searches for a specific value in the subtree with 
	--the root conveyed by the variable n. It is supposed to be called
	--with root node in order to search whole tree
	--Method returns true if the value is found and false otherwise
	search_value (a:Int , n:Node) : Bool {
		
		if n.get_value() = a then true
		else if n.get_value() < a then
			if isvoid n.get_right_ch() then false
			else search_value(a,n.get_right_ch())
			fi
		else	if isvoid n.get_left_ch() then false
			else search_value(a,n.get_left_ch())
			fi
		fi fi
	
	};
		
	--Prints out the values of the all nodes from smallest to greatest
	print_inorder(n : Node) : Int {
		
		if isvoid n then 1 else
		{
		print_inorder (n.get_left_ch());
		out_int(n.get_value());
		out_string("\n");
		print_inorder (n.get_right_ch());
		}
		fi
	};
	
	--Prints out the values of the all nodes in preorder format.
	--(Which is a node's value is printed before its children's values.)
	print_preorder(n : Node) : Int {
		
		if isvoid n then 1 else
		{
		out_int(n.get_value());
		out_string("\n");
		print_preorder (n.get_left_ch());
		print_preorder (n.get_right_ch());
		}
		fi
	};

	--Prints out the values of the all nodes in postorder format.
	--(Which is a node's value is printed after its children's values.)
	print_postorder(n : Node) : Int {
		
		if isvoid n then 1 else
		{
		print_postorder (n.get_left_ch());
		print_postorder (n.get_right_ch());
		out_int(n.get_value());
		out_string("\n");
		1;
		}
		fi
	};

	--Prints out the values of all Nodes from smallest to greatest.
	print_decorder(n : Node) : Int {
		if isvoid n then 1 else
		{
			print_decorder(n.get_right_ch());
			out_int(n.get_value());
			out_string("\n");
			print_decorder(n.get_left_ch());
		}
		fi
	};	
};


class Main inherits IO {
	--Create an instance of BSTree with the value 24 attached to its root.
	a : BSTree <- (new BSTree).init(24); 
	
	main() : Int {
		{
		--Add some nodes to the tree ,some other values could be added
		a.add_value(4);
		a.add_value(3);
		a.add_value(45);
		a.add_value(25);
		a.add_value(2);
		a.add_value(34);
		a.add_value(4);

		out_string("Values of nodes in decreasing order!\n");
		a.print_decorder(a.get_root());

		out_string("\nValues of nodes in pre-order!\n");	
		a.print_preorder(a.get_root());

		out_string("\nValues of nodes in post-order!\n");
		a.print_postorder(a.get_root());

		out_string("\nValues of nodes in-order(increasing)!\n");
		a.print_inorder(a.get_root());
		
		out_string("\nSearch result for the number 7\n");		
		if a.search_value(7,a.get_root()) then out_string("Number found in tree!\n") else out_string("Number not found!\n")
		fi;
		
		out_string("\nSearch result for the number 34\n");		
		if a.search_value(34,a.get_root()) then out_string("Number found in tree!\n\n") else out_string("Number not found!\n\n")
		fi;	

		1;	
		}
	};
};