okasaki2.3.ml

open Printf

module type Ord =
sig
  type t
  val lt : t -> t -> bool
  val lte : t -> t -> bool
  val eq : t -> t -> bool
end

module IntOrd : Ord with type t = int =
struct
  type t = int
  let lt = (<)
  let lte = (<=)
  let eq = (=)
end

module type Set =
sig
  type elem
  type set
  val empty : set
  val insert : elem -> set -> set
  val member : elem -> set -> bool
end

module UnbalSet(Elt : Ord) : Set with type elem = Elt.t =
struct
  type elem = Elt.t
  type 'a tree = 
      Leaf 
    | Node of 'a tree * 'a * 'a tree
  type set = elem tree 

  exception Error of string 
      
  let empty = Leaf
  (* if the x exists in t, we raise an exception and return t *)
  let insert x t = 
    let rec insert_exc x = function
      |  Leaf -> Node (Leaf, x, Leaf)
      | Node (a, y, b) -> 
        if Elt.lt x y then Node (insert_exc x a, y, b)
        else if Elt.lt y x then Node (a, y, insert_exc x b) 
        else raise (Error "already inserted")
    in try insert_exc x t
    with Error s -> print_endline s; t
      
  (* we assume x is strictly < or > to any node value
     when we reach a leaf we check x equality with the last node
     x was superior to, z *)
  let member x s = 
    let rec member_aux x s z =
      match s with
          Leaf -> x = z
        | Node(a, y, b) -> 
            if Elt.lt x y then member_aux x a z
            else member_aux x b y
    in
      match s with
          Leaf -> false
        | Node(_, y, _) -> member_aux x s y
      
        
end

module IntSet = UnbalSet (IntOrd)

let insert_ordered n s =
  for i = 1 to n do
      (* print_int i; *)
      s := (IntSet.insert i !s)
  done

(*
let _ =
  let s = (ref IntSet.empty) in
  insert_ordered 1000 s;
  let res =IntSet.member 1001 !s in
  print_endline (string_of_bool res);
  IntSet.insert 1000 !s
*)


let insert_random n max s =
  (* 1 *) (* 1 *) for i = 1 to n do
      (* print_int i; *)
      s := (IntSet.insert (Random.int max) !s)
  done

(*
ocamlcp -p f chap2_4.ml -o chap2_4
ocamlprof chap2_4.ml > chap2_4_prof.ml
*)
let main () =
  (* 1 *) (* 1 *) let s = (ref IntSet.empty) in
  insert_random 10000 100000 s
  (*
  let res = IntSet.member 1001 !s in
  print_endline (string_of_bool res);
  IntSet.insert 1000 !s
  *)
let _ = main ()