(*
task 2
*)

datatype Expr = Val of int | Plus of Expr * Expr | Times of Expr * Expr | Neg of Expr;

fun eval (Val v) = v
  | eval (Plus (e1, e2)) = (eval e1) + (eval e2)
  | eval (Times (e1, e2)) = (eval e1) * (eval e2)
  | eval (Neg e) = ~(eval e);

(*
Task 5
*)

(*
Binary Trees
*)
datatype 'a Tree = Lf | Br of 'a * 'a Tree * 'a Tree
exception Missing

val natrange = 
    let 
        fun nr l a b i = if b < a then l else nr (b :: l) a (b-i) i
    in 
        nr [] 
    end;

datatype Ord = EQ | LT | GT

fun lookup b x Lf = raise Missing
  | lookup b x (Br ((x',y),t1,t2)) = case b x x' of
                                         EQ => y |
                                         LT => lookup b x t1 |
                                         GT => lookup b x t2;

fun update b ((x, y), Lf) = Br ((x,y), Lf, Lf)
  | update b ((x, y), (Br ((x',y'), t1, t2))) = case b x x' of
                                                    EQ => Br ((x',y), t1, t2) |
                                                    LT => Br ((x',y'), (update b ((x, y), t1)), t2)|
                                                    GT => Br ((x',y'), t1 , (update b ((x, y), t2)));

exception Collision of int;
fun insert (x,y) Lf = Br ((x,y),Lf,Lf)
  | insert (x,y) (Br ((x',y'), t1, t2)) = if x < x'
                                          then Br ((x',y'), insert (x,y) t1, t2)
                                          else if x > x' 
                                          then Br ((x',y'), t1, insert (x,y) t2)
                                          else raise Collision y'



fun deleteLeftmost (Br (kv,Lf,tr)) = (kv, tr)
  | deleteLeftmost (Br (kv,tl,tr)) = let val (kv', t) = deleteLeftmost tl in 
                                         (kv',Br (kv, t, tr))
                                     end;

fun delete b x Lf = Lf
  | delete b x (Br ((x',y'),tl,tr)) = 
    case b x x' of
        EQ => (case tr of 
                   Lf => tl 
                 | Br (_,Lf,_) => tr
                 | Br (_,tl',_) => let val (kv, t) = deleteLeftmost tl' in Br (kv,tl,t) end)
      | LT => Br ((x',y'), delete b x tl, tr)
      | GT => Br ((x',y'), tl, delete b x tr);

(*
test the binary tree
*)

fun list2tree b l = foldr (update b) Lf l;

fun intb x y = if x < y then LT else if x > y then GT else EQ;

fun flatten Lf = []
  | flatten (Br (a,t1,t2)) = (flatten t1) @ [a] @ (flatten t2);

fun increasing b [] = true
  | increasing b [x] = true
  | increasing b (x::y::l) = if b (x, y) then increasing b (y::l) else false;


local val a = 16807.0 and m = 2147489.0
in fun nextrandom seed =
          let val t = a*seed
          in t - m * real(floor(t/m)) end
    and truncto k r = 1 + floor((r / m) * (real k))
end;

fun randlist (n,seed,seeds) =
        if n=0 then (seed,seeds)
        else randlist(n-1, (nextrandom seed), seed::seeds);
val (seed,rs) = randlist(10000, 1.0, []);

val testList = map (fn x => let val y = trunc x in (y,y) end) rs;

val testTree = list2tree intb testList;

fun snd (_,y) = y;
fun fst (x,_) = x;

fun foldr' f b al = foldr (fn (x,y) => f x y) b al;

val testTreeDel = foldr' (delete intb) testTree (map fst (List.take(testList,2000)));
val testTreeDelList = flatten testTreeDel;
val test1 = increasing Int.< (map fst testTreeDelList);