testtp1

open Facturesetcheques
open Tris

let cpt = ref 0

let cmp x y =
  incr cpt;
  if x < y then
    -1
  else if x = y then
    0
  else
    1

let cmp_cheques c1 c2 =
  cmp (numero_facture_cheque c1) (numero_facture_cheque c2)

let cmp_factures f1 f2 =
  cmp (numero_facture f1) (numero_facture f2)

(**
    algorithme 1, on s'interdit tout pretraitement sur les factures et
    les cheques
*)
let liste_des_factures_impayees_1 f c =
    let liste = ref []
    and estpaye = ref false in
    for i=0 to (Array.length f)-1 do (
        estpaye := false;
        for j=0 to (Array.length c)-1 do (
            if (cmp (numero_facture (f.(i))) (numero_facture_cheque (c.(j))) = 0) then (
                estpaye := true;
            );

        )
        done;
        if not(!estpaye) then
            liste := (f.(i)):: !liste;
    )
    done;
    !cpt


(**
    algorithme 2, on s'autorise de pretraiter soit les factures, soit
    les cheques mais pas les deux
*)
let liste_des_factures_impayees_2 f ch =
    (*Tableau des chèques trié*)
    let c = (trier ch cmp_cheques)
    (*Liste des factures impayées*)
    and liste = ref []
    (*La facture est impayée*)
    and payee = ref false
    (*Indices*)
    and debut = ref 0
    and fin = ref ((Array.length ch)-1)
    in
    let milieu = ref ((!debut + !fin)/2)
    in
    for i=0 to ((Array.length f)-1) do (
        incr cpt;
        payee := false;
        debut := 0;
        fin := ((Array.length c)-1);
        milieu := (!debut + !fin)/2;
        while (not(!payee) && (!milieu <> !debut) && (!milieu <> !fin) && (!debut <= !fin)) do (
            if (
                ((cmp (numero_facture f.(i)) (numero_facture_cheque c.(!milieu)))) = 0 ||
                ((numero_facture f.(i)) = (numero_facture_cheque c.(!debut))) ||
                ((numero_facture f.(i)) = (numero_facture_cheque c.(!fin))))
            then (
                payee := true;
            )
            else (
                if ((numero_facture f.(i)) > (numero_facture_cheque c.(!milieu))) then (
                    debut := !milieu
                )
                else (
                    fin := !milieu
                );
                if (((!debut + !fin) mod 2)=0) then (
                    milieu := ((!debut + !fin)/2)
                )
                else (
                    milieu := (((!debut + !fin)/2)+1)
                );
            );
        )done;
        if (not(!payee)) then (
            liste := (f.(i)):: !liste;
        );
    )done;
    !cpt


(**
    algorithme 3, on s'autorise de pretraiter à la fois les factures et
    les cheques
*)
let liste_des_factures_impayees_3 fact ch =
    (*Tableau des chèques trié*)
    let c = (trier ch cmp_cheques)
    (*Tableau des factures trié*)
    and f = (trier fact cmp_factures)
    (*Liste des factures impayées*)
    and liste = ref []
    (*La facture est impayée*)
    and payee = ref false
    (*Indices*)
    and compt = ref 0
    in
    for i=0 to (Array.length(f)-1) do (
        payee := false;
        if !compt > (Array.length c)-1 then
            payee := false
        else (
            if ((cmp (numero_facture f.(i)) (numero_facture_cheque c.(!compt))) = 0) then (
                payee := true;
                incr compt;

            );
        );
        if (not(!payee)) then (
            liste := (f.(i)):: !liste;
        );
    )
    done;
    !cpt


(**
   [imprimer_liste_factures l] imprime les numeros de facture de la liste l
*)
let rec imprimer_liste_factures l =
  match l with
    | [] ->
      Printf.printf "\n"
    | f::r ->
      Printf.printf "%d " (numero_facture f);
      imprimer_liste_factures r

let _ =
  let n = int_of_string Sys.argv.(1)
  in
  let ftab = factures n
  in
  for i=1 to n do (
    let ctab = cheques i ftab in
    Printf.printf "%d %d " n i;
    (* test methode 1 *)
    cpt := 0;
    Printf.printf "%d " (liste_des_factures_impayees_1 ftab ctab);
    (* test methode 2 *)
    cpt := 0;
    Printf.printf "%d " (liste_des_factures_impayees_2 ftab ctab);
    (* test methode 3 *)
    cpt :=0;
    Printf.printf "%d \n" (liste_des_factures_impayees_3 ftab ctab);
  )
  done;