(*tsearch*)

(* Tree search data structures and traversal and insertion fns *)

(*
   An 'a tree has 
    (1) a left branch (which is an 'a Node of a tree or is a leaf)
    (2) an 'a value
    (3) a right branch (which is an 'a Node of a tree or is a leaf)
*)

datatype 'a tree = Nil
                  |Node of ('a tree * 'a * 'a tree)
                  |Nnode of ('a tree * 'a tree * 'a tree);

fun leafp (Node(Nil,_,Nil)) = "Node"
   |leafp (Nnode(Nil,_,Nil)) = "Nnode"
   |leafp anything_else = "Something else entirely";
(* Given a node within a tree, is it a leaf node? *)

exception XXX;

fun get Nil k = raise XXX
   |get (Node(l,a,r)) k =
    if k=1
    then a
    else if k mod 2 = 0
         then get l (k div 2)
         else get r (k div 2);


fun put Nil k data = raise XXX
     (* if k = 1
        then leaf data
        else raise XXX*)
   |put (Node(l,a,r)) k data =
        if k=1
        then Node(l,data,r)
        else if k mod 2 = 0
             then Node((put l (k div 2) data),a,r)
             else Node(l,a,(put r (k div 2) data));

fun add_element_to Nil k (Node(l,d,r)) =
    if k = 1
    then Nnode(Nil,(Node(l,d,r)),Nil)
    else raise XXX
   |add_element_to Nil k data =
    if k=1
    then Node(Nil,data,Nil)
    else raise XXX
   |add_element_to (Node(l,a,r)) k data =
    if k mod 2 = 0
    then Node((add_element_to l (k div 2) data),a,r)
    else Node(l,a,(add_element_to r (k div 2) data));
    

fun make_vector n init_value = 
    if n = 0 
    then raise XXX
    else if n=1 
         then Node(Nil,init_value,Nil)
         else add_element_to (make_vector (n-1) init_value) n init_value;

(*
fun make_2 [] v = raise XXX
   |make_2 (n::x) v =
    if null x
    then raise XXX
    else let val (m::y) = x
         in if null y
            then make_vector n (make_vector m v)
            else make_vector n (make_2 x v)
         end;
*)

fun inorder Nil = []
   |inorder (Node(l,x,r)) = (inorder l)@[x]@(inorder r);