Test-arbre.ml

Ce programme utilise les implantations des AVL (avl.ml) et des ARN (arn.ml) afin de comparer les transformations effectuées lors des insertions (notamment lors des insertions massives.)

Utilisation:

./test-arbre [type] [graine] [taille]
./test-arbre [type] [graine] [taille] off

• Le premier type d'appel, engendre un arbre de type [type] (avl ou arn) de taille [taille], la graine n'est pas utilisée. Le programme sort sur la sortie standard le code à insérer dans un fichier LaTeX (arbre et informations sur les transformations.)
• Le second type d'appel, engendre un arbre de type [type] (avl ou arn) de taille [taille] où les clefs insérées sont générées aléatoirement (en utilisant la graine.) Seules les informations sur les transformations sont affichées.

Le premier type d'appel, sert surtout à visualiser le résultat avec un arbre de taille raisonable, tandis que le second type permet plutôt d'observer ce qui se passe avec un très grand nombre d'insertions (où l'affichage de l'arbre n'est plus pertinent.)

Code

(* Test d'arbre ... *)

(* La signature des modules de representation des arbres *)
module type Arbre =
sig
  type t
  val empty :  t
  val is_empty :  t -> bool
  val add : (string -> 'a) -> int -> t -> t
  val print : t -> unit
  val print_tex : t -> unit
  val mem : int -> t -> bool
end

(* Le foncteur pour tester les arbres *)
module Testeur (T:Arbre) =
struct
  type t = T.t

  (* La fonction "enregistrant" les transformations *)
  let update =
    (* Donnees statique *)
    let data = Hashtbl.create 7 in
    let get s =
      try
	Hashtbl.find data s
      with Not_found -> 0
    in
      fun b s ->
	if b then
	  begin
	    Hashtbl.replace data s (1 + get s);
	    data
	  end
	else
	  data

  (* Ajout en mass dans un arbre depuis une liste *)
  let mass_add l =
    List.fold_left
      (fun t k ->
	 T.add (update true) k t)
      T.empty l

  (* Execution des tests *)
  let perform_test flag l =
    begin
      let t = (mass_add l) in
	Hashtbl.iter (Format.printf "%s: %i\\\\@.") (update false "");
	Format.printf "@.";
	List.iter (fun k -> ignore (T.mem k t)) l;
	if (not flag) then
	  T.print_tex t;
	Format.printf "@.";
    end

end

let rec gen_list_lin acu = function
    0 -> acu
  | n when n>0 -> gen_list_lin (n::acu) (n-1)
  | _ -> assert false

let rec gen_list_rand acu = function
    0 -> acu
  | n when n>0 -> gen_list_rand (Random.int 65536::acu) (n-1)
  | _ -> assert false

let choose_gen_list b =
  if b then
    gen_list_rand
  else
    gen_list_lin

let main () =
  begin
    if (Array.length Sys.argv)>3 then
      begin
	let flag = (Array.length Sys.argv)>4 in
	let gen_list = choose_gen_list flag in
	  Random.init (int_of_string (Sys.argv.(2)));
	  let l = gen_list [] (int_of_string Sys.argv.(3)) in
	    (match Sys.argv.(1) with
		 "avl" ->
		   let module MyTreeTest = Testeur (Avl) in
		     MyTreeTest.perform_test flag l
	       | "arn" ->
		   let module MyTreeTest = Testeur (Arn) in
		     MyTreeTest.perform_test flag l
	       | _ -> (Printf.fprintf stderr "Wrong tree type ... \n"; exit 2));
	    exit 0
      end
    else
      begin
	Printf.fprintf stderr "Miss some args ...\n";
	exit 1
      end
  end

let _ = main ()

Fichiers suplémetaires

Makefile

Voici mon Makefile pour ce programme.

# Au besoin on peut changer les compilateurs par défaut
OCAMLC=ocamlc.opt
OCAMLOPT=ocamlopt.opt

all: test-arbre

test-arbre: avl.cmx arn.cmx test-arbre.cmx
	${OCAMLOPT} -o $@ $>

test-arbre.cmx: avl.cmi arn.cmi

arn.tex: test-arbre
	rm -f arn.tex
	./test-arbre arn 0 25 > arn.tex

avl.tex: test-arbre
	rm -f avl.tex
	./test-arbre avl 0 25 > avl.tex

tree.pdf: tree.tex arn.tex avl.tex
	pdflatex tree.tex
	pdflatex tree.tex

# Le reste n'a pas de raison de changer

.SUFFIXES: .ml .mli .cmo .cmi .cmx .opt

# Generation d'un exécutable à partir d'un .ml (bytecode)
.ml:
	${OCAMLC} -o $@ $<

# Generation d'un exécutable à partir d'un .ml (natif)
.ml.opt:
	${OCAMLOPT} -o $@ $<

.mli.cmi:
	${OCAMLC} -c $<

.ml.cmo:
	${OCAMLC} -c $<

.ml.cmx:
	${OCAMLOPT} -c $<

# some cleaning ...
clean::
	rm -f *~                 # do we use emacs ;)
	rm -f *.cm[iox] *.o      # remove comp prod
	rm -f test-arbre
	rm -f tree.aux tree.log

# THE END (do not delete)

tree.tex

Et le fichier tree.tex:

\documentclass[a4paper,pdftex,french,landscape]{article}

\usepackage{fullpage}
\usepackage[utf8]{inputenc}
\usepackage{txfonts}
\usepackage{tikz}
\usetikzlibrary{trees}

\begin{document}

\noindent\input{arn}
\pagebreak
\noindent\input{avl}

\end{document}