module Int = struct
  type t = int
  let compare = compare
end

module Set1 = Set234.Make(Int)

let create1 size max =
  let rec fn acc remain =
    if remain = 0 then acc
    else
      let x = Random.int max in
      fn (Set1.add x acc) (remain - 1)
  in
  fn Set1.empty size

module Set2 = Set.Make(Int)

let create2 size max =
  let rec fn acc remain =
    if remain = 0 then acc
    else
      let x = Random.int max in
      fn (Set2.add x acc) (remain - 1)
  in
  fn Set2.empty size

let create12 size max =
  let rec fn acc acc' remain =
    if remain = 0 then acc, acc'
    else
      let x = Random.int max in
      fn (Set1.add x acc) (Set2.add x acc') (remain - 1)
  in
  fn Set1.empty Set2.empty size

let search1 t size max =
  let rec fn acc remain =
    if remain = 0 then acc
    else
      let x = Random.int max in
      fn (if Set1.mem x t then acc+1 else acc) (remain - 1)
  in
  fn 0 size

let search2 t size max =
  let rec fn acc remain =
    if remain = 0 then acc
    else
      let x = Random.int max in
      fn (if Set2.mem x t then acc+1 else acc) (remain - 1)
  in
  fn 0 size


let t1,t2 = create12 (int_of_string Sys.argv.(1)) 1000
let h = Set1.test_height t1
let _ = 
  print_int h; print_newline ();
  print_int (Set1.cardinal t1); print_newline ();
  print_int (Set2.cardinal t2); print_newline ();
  if Set2.for_all (fun n -> Set1.mem n t1) t2 then
    print_string "identical trees\n"

let chrono s f x =
  let {Unix.tms_utime = ut;Unix.tms_stime = st} = Unix.times () in
  let r = f x in
  let {Unix.tms_utime = ut';Unix.tms_stime = st'} = Unix.times () in
  Printf.printf "%s: %.2fs\n" s ((ut' -. ut) +. (st' -. st));
  flush stdout;
  ignore r

let _ =
  print_string "construction of random tree with 200000 interger less then 10^6"; print_newline ();
  chrono "234" (create1 200000) 1000000;
  chrono "bal" (create2 200000) 1000000;
  chrono "234" (create1 200000) 1000000;
  chrono "bal" (create2 200000) 1000000;
  chrono "234" (create1 200000) 1000000;
  chrono "bal" (create2 200000) 1000000;
  chrono "234" (create1 200000) 1000000;
  chrono "bal" (create2 200000) 1000000;
  let t1, t2 = create12 100000 1000000 in
  print_string "search 10^6 times in tree of size 100000"; print_newline ();
  chrono "234" (search1 t1 1000000) 1000000;
  chrono "bal" (search2 t2 1000000) 1000000;
  chrono "234" (search1 t1 1000000) 1000000;
  chrono "bal" (search2 t2 1000000) 1000000;
  chrono "234" (search1 t1 1000000) 1000000;
  chrono "bal" (search2 t2 1000000) 1000000;
  chrono "234" (search1 t1 1000000) 1000000;
  chrono "bal" (search2 t2 1000000) 1000000;
  let t1, t2 = create12 500000 1000000 in
  print_string "search 10^6 times in tree of size 500000"; print_newline ();
  chrono "234" (search1 t1 1000000) 1000000;
  chrono "bal" (search2 t2 1000000) 1000000;
  chrono "234" (search1 t1 1000000) 1000000;
  chrono "bal" (search2 t2 1000000) 1000000;
  chrono "234" (search1 t1 1000000) 1000000;
  chrono "bal" (search2 t2 1000000) 1000000;
  chrono "234" (search1 t1 1000000) 1000000;
  chrono "bal" (search2 t2 1000000) 1000000