#load "netmcore_util.cmo";;
open Netmcore_util.AVL;;
let h = create_header();;
h.nodes <- Array.init 50 (fun _ -> create_node());;
init_header h;;

let add1() =
  add h 1 1;
  add h 2 2;
  add h 10 10;
  add h 5 5

let height k =
  let rec descent k depth =
    if k = (-1) then
      depth
    else (
      let node = h.nodes.(k) in
      let h1 = descent node.left (depth+1) in
      let h2 = descent node.right (depth+1) in
      max h1 h2
    ) in
  descent k 0

let check_bal () =
  let rec descent k =
    if k <> (-1) then (
      let node = h.nodes.(k) in
      let h1 = height node.left in
      let h2 = height node.right in
      assert(node.bal = h2-h1);
      descent node.left;
      descent node.right
    )
  in
  descent h.root

let t1() =
  init_header h;
  for k = 1 to 20 do
    print_endline ("k=" ^ string_of_int k);
    add h k k;
    check_bal()
  done

let t2() =
  init_header h;
  for k = 20 downto 1 do
    print_endline ("k=" ^ string_of_int k);
    add h k k;
    check_bal()
  done

let t3() =
  init_header h;
  for k = 1 to 20 do
    let x = Random.int 100 in
    print_endline ("x=" ^ string_of_int x);
    add h x x;
    check_bal()
  done

let t4() =
  t1();
  for k = 1 to 20 do
    print_endline ("k=" ^ string_of_int k);
    remove h k;
    check_bal()
  done

let t5() =
  t1();
  for k = 20 downto 1 do
    print_endline ("k=" ^ string_of_int k);
    remove h k;
    check_bal()
  done

let t6() =  (* removal in reverse add order *)
  init_header h;
  let keys = ref [] in
  for k = 1 to 20 do
    let x = Random.int 100 in
    print_endline ("x=" ^ string_of_int x);
    add h x x;
    check_bal();
    keys := x :: !keys
  done;
  while !keys <> [] do
    let x = List.hd !keys in
    print_endline ("x=" ^ string_of_int x);
    remove h x;
    print_endline ("  remaining: " ^ as_debug_list h);
    check_bal();
    keys := List.tl !keys
  done

let t7() =  (* removal in add order *)
  init_header h;
  let keys = ref [] in
  for k = 1 to 20 do
    let x = Random.int 100 in
    print_endline ("x=" ^ string_of_int x);
    add h x x;
    check_bal();
    keys := x :: !keys
  done;
  keys := List.rev !keys;
  while !keys <> [] do
    let x = List.hd !keys in
    print_endline ("x=" ^ string_of_int x);
    remove h x;
    print_endline ("  remaining: " ^ as_debug_list h);
    check_bal();
    keys := List.tl !keys
  done


let t8() =  (* removal in random order *)
  init_header h;
  let keys = ref [] in
  for k = 1 to 20 do
    let x = Random.int 100 in
    print_endline ("x=" ^ string_of_int x);
    add h x x;
    check_bal();
    keys := x :: !keys
  done;
  let l = List.map (fun x -> (Random.int 100, x)) !keys in
  let l' = List.sort (fun (a,_) (b,_) -> a-b) l in
  keys := List.map (fun (_,x) -> x) l';
  while !keys <> [] do
    let x = List.hd !keys in
    print_endline ("x=" ^ string_of_int x);
    remove h x;
    print_endline ("  remaining: " ^ as_debug_list h);
    check_bal();
    keys := List.tl !keys
  done