with Ada.Text_IO; use Ada.Text_IO;
with ada.integer_text_io; use ada.integer_text_io;
with ada.characters.handling;

package body binarysearchtree is
	
	count:integer:=0;	

	function toLower (c : character) return character renames Ada.characters.handling.to_lower;

		--  tolower - translates all alphabetic, uppercase characters
		--  in str to lowercase
	function toLower (Str : String) return String is
		convert : String (str'Range);
	begin
		for x in  convert'Range loop
			convert (x) := toLower (str (x));
		end loop;
		return convert;
	end toLower;

	procedure InsertBinarySearchTree(Root:  in out BinarySearchTreePoint; custName: in String10; custPhone: String10 ) is
		p:binarySearchTreePoint:=root;
		q:binarySearchTreePoint:=root;
		t:binarySearchTreePoint;
		
	begin
		count:=count+1;
		t:=new node;
		t.info.name:=custName;
		t.info.phoneNumber:=custPhone;
		t.rLink:=t;
		t.rLink:=t;
		
		if root = null then
			root:=t;
		else
			loop
				if q/=null then
					if toLower(custName) < toLower(q.info.name) then
						if q.lLink=p then
							p:=q;
							exit;
						end if;
						p:=q;
						q:=q.lLink;
						elsif q.rTag = true then
							p:=q;
							q:=q.rLink;
						else
							p:=q;
							exit;
						end if;
					else
						exit;
				end if;
			end loop;
		
		
			if toLower(p.info.name) > toLower(custName) then
				t.lLink:=p.lLink;
				p.lTag := true;
				t.rLink:=p;
				t.rTag:=false;
				if t.lTag=true then
					t.lLink.rLink:=t; --check for child and rethread tree
				end if;
			elsif toLower(p.info.name) <= toLower(custName) then
				p.rLink:=t;
				p.rTag:=true;
				t.lLink:=p;
				t.lTag:=false;
				if t.rTag=true then
					t.rLink.lLink:=t; --check for child and rethread tree
				end if;
			end if;
		end if;
	end InsertBinarySearchTree;
		 

	-- This procedure locates a customer using a binary search.  A pointer is returned to the
-- customer record if they exist, otherwise a Null pointer is returned (in CustomerPoint).
	-- The search must be implemented iteratively.
	procedure FindCustomerIterative(Root: in BinarySearchTreePoint; CustomerName:  in String10; CustomerPoint:  out BinarySearchTreePoint) is
		p:binarySearchTreePoint:=root;
		temp:integer:=count;
	begin
		loop
			if temp = 0 then
				p:=null;
				exit;
			elsif toLower(p.info.name) = toLower(customerName) then
				customerPoint:=p;
				exit;
			elsif toLower(p.info.name) > toLower(customerName) then
				p:=p.lLink;
			elsif toLower(p.info.name) <= toLower(customerName) then
				p:=p.rLink;
			end if;
			
			temp:=temp-1;
			
		end loop;
		customerPoint:=p;
	end FindCustomerIterative;
	
	-- This procedure locates a customer using a binary search.  A pointer is returned to the
-- customer record if they exist, otherwise a Null pointer is returned (in CustomerPoint).
	-- The search must be implemented recursively.
	procedure FindCustomerRecursive(Root: in BinarySearchTreePoint; CustomerName:  in String10) is
		p:binarysearchtreepoint;
	begin
			p:=root;
		if p = null then
			return;
		elsif toLower(p.info.name) > toLower(customerName) then
			findCustomerRecursive(p.lLink, customerName);
		elsif toLower(p.info.name) < toLower(customerName) then 
			findCustomerRecursive(p.rLink, customerName);
		elsif toLower(p.info.name) = toLower(customerName) then
			put_line(p.info.phoneNumber);
			return;
		end if;
						
	end FindCustomerRecursive;

	-- This function returns the address of the next node in inorder taking advantage of threads.
-- The user may enter the  tree at any random location.  This is sometimes called an iteration 
-- function or iterater (no recursion).
	function InOrderSuccessor(TreePoint: in BinarySearchTreePoint) return BinarySearchTreePoint is
		p:binarySearchTreePoint;
		q:binarySearchTreePoint;
	begin
		p:=treePoint;
		q := p.rLink; 
		if p.rTag = false then
			p:=q;
		else
			while q.lTag = true loop
				q := q.lLink; 
			end loop;
			p:=q;
		end if;
		
		return p;
	end InOrderSuccessor;
	-- Access functions to return customer names and phone numbers.
	function CustomerName(TreePoint: in BinarySearchTreePoint) return String10 is
	begin
		return treePoint.info.name;
	end customerName;
	
	function CustomerPhone(TreePoint: in BinarySearchTreePoint) return String10 is
	begin
		return treePoint.info.phoneNumber;
	end customerPhone;

	procedure init is
		root:binarySearchTreePoint;
		t:binarySearchTreePoint;	
	
		selection:integer:=0;
		s:string10:=(others=>' ');
		p:string10:=(others=>' ');
		temp:integer:=0;	
		begin
			loop
			put_line("::Binary Search Tree Program::");
			put_line("1)insert into binary search tree");
			put_line("2)find customer iteratively");
			put_line("3)find customer recursively");
			put_line("4)inoder successor");
			put_line("5)traverse inorder");
			put_line("6)exit");
			put("enter selection::");
			get(selection);
	
			if selection = 1 then
				put("Please enter name::");
				get(s);
				put_line(s);
				put("Please enter phone number::");
				get(p);
				put_line(p);
				insertBinarySearchTree(root,s,p);
				s:=(others=>' ');
				p:=(others=>' ');
			elsif selection = 2 then
				put("Please enter name::");
				get(s);
				put_line(" ");
				findCustomerIterative(root,s,t);
				if t/=null then	
					put_line("Customer Phone::" & customerPhone(t));	
				else	put_line("Customer not found in Tree");
				end if;
			elsif selection = 3 then
				put("Please enter name::");
				get(s);
				put_line(" ");
				findCustomerRecursive(root,s);
			elsif selection = 4 then
				put("Please enter name::");
				get(s);
				put_line(" ");
				findCustomerIterative(root,s,t);
				root:=inOrderSuccessor(t);
				put_line("In order successor::");
				put(root.info.name);
				put_line(" ");
			elsif selection = 5 then
				put_line("Please enter starting point::");
				put_line("1)start at root");
				put_line("2)give node to start at");
				get(selection);
				if selection = 1 then
					s:=customerName(root);
					loop
					t:=inOrderSuccessor(root);
					root:=t;
					if toLower(s) = toLower(root.info.name) then
						exit;
					else
						put_line(root.info.name);
					end if;
					end loop;
				elsif selection = 2 then
					temp:=count;
					put("Enter customer name::");
					get(s);
					findCustomerIterative(root,s,t);
					put_line(customerName(t));
					put_line(customerPhone(t));
					root:=inOrderSuccessor(t);
					loop
						t:=inorderSuccessor(t);
						put_line(customerName(t));
						put_line(customerPhone(t));
						temp:=temp-1;
						exit when temp = 1;
					
					end loop;
				end if;
	
			elsif selection = 6 then
				exit;
			end if;	
		end loop;
	end init;	
end binarysearchtree;