open Stop_and_copy
open Format

(* teste com a ordenação por inserção : cria uma lista aleatória de comprimento n e ordena  por inserção *)

let sort n =
  reset ();
  let head x = memory.(x + 1) in
  let tail x = memory.(x + 2) in
  let cons x = let p = alloc 2 in memory.(p+1) <- x; p in
  let cons0 x = let p = cons x in memory.(p+2) <- roots.(0); roots.(0) <- p in
  (* construção de uma lista aleatória de tamanho i na raíz 0 *)
  let rec make i =
    if i = 0 then
      roots.(0) <- -1
    else begin
      make (i - 1);
      cons0 (-(1 + Random.int 1000))
    end
  in
  let rec print l =
    if l = -1 then printf "@\n"
    else begin printf "%d," memory.(l+1); print memory.(l+2) end
  in
  (* inserção de x na lista que é a raíz 0 ; o resultado está também na raíz 0 *)
  let rec insert x =
    if roots.(0) = -1 then
      cons0 x
    else
      let y = head roots.(0) in
      if x < y then
	cons0 x
      else begin
	roots.(0) <- tail roots.(0);
	insert x;
	cons0 y
      end
  in
  (* ordenação por inserção da lista que é a raíz 0 *)
  let rec insort () =
    if roots.(0) <> -1 then begin
      let y = head roots.(0) in
      roots.(0) <- tail roots.(0);
      insort ();
      insert y
    end
  in
  (* criamos uma lista de tamanho n, mostramo-la , ordenamos, e voltamos a mostrá-la *)
  make n;
  print roots.(0);
  insort ();
  print roots.(0)

let test n =
  printf "@[<hov 2>sort %d@\n" n;
  sort n;
  printf "@]@."

let () = test 3
let () = test 10
let () = test 17