(* Routines diverses *)
exception NotDisjoint;;


let build_vect n f =
  let v=make_vect n (f 0) in
  for i=2 to (n-1) do
   v.(i)<-f i
  done;
  v;;

let do_vect2 f v1 v2 =
  for i=0 to (vect_length v1 - 1) do
   f v1.(i) v2.(i);
  done;;

let exists_vect f v =
  let l=vect_length v in
  let rec aux n = if n>=l then false else if f v.(n) then true else aux (n+1)
  in aux 0;;

let rec strict_assoc cle = function
  [] -> raise Not_found
| (c,v)::q -> if c==cle then v else strict_assoc cle q;;

let pr=print_string;;

let int_of_bool = fun true -> 1 | false -> 0;;

let for_all_int p deb fin =
 let rec test i = if i>fin then true else if p i then test (i+1) else false
 in test deb;;

let rec do_list_sep f sep = function
| []   -> ()
| [a]  -> f a
| a::r -> f a; sep(); do_list_sep f sep r;;

(* Listes associatives triees sans doublons *)
let assoc_env n =
  let rec aux = function
    | []   -> raise Not_found
    | (p,r)::q -> if (p=n) then r else if (p<n) then raise Not_found else aux q
  in aux;;

let rec mem_assoc_env n = function
  | [] -> false
  | (p,r)::q -> if (p=n) then true else if (p<n) then false else mem_assoc_env n q;;

let add_env (n,x) =
  let rec aux = function
    | []   -> [n,x]
    | (p,r)::q as l -> if (p=n) then (n,x)::q else if (p<n) then (n,x)::l else (p,r)::(aux q)
  in aux;;

let rec fus_env e1 e2 = match (e1,e2) with
 | _,[] -> e1
 | [],_ -> e2
 | (c1,x1)::q1,(c2,x2)::q2 ->
        if c1>c2 then (c1,x1)::(fus_env q1 e2) else
        if c1<c2 then (c2,x2)::(fus_env e1 q2) else
        (c1,x1)::(fus_env q1 q2);;


let rec fus_set e1 e2 = match (e1,e2) with
 | _,[] -> e1
 | [],_ -> e2
 | c1::q1,c2::q2 ->
        if c1>c2 then c1::(fus_set q1 e2) else
        if c1<c2 then c2::(fus_set e1 q2) else
        c1::(fus_set q1 q2);;

let rec fus_set_disj e1 e2 = match (e1,e2) with
 | _,[] -> e1
 | [],_ -> e2
 | c1::q1,c2::q2 ->
        if c1>c2 then c1::(fus_set_disj q1 e2) else
        if c1<c2 then c2::(fus_set_disj e1 q2) else
        raise NotDisjoint;;

let rec sub_set x = function
 | [] -> []
 | c::q as e -> if c>x then c::(sub_set x q) else if c=x then q else e;;


(* Englobage des tables *)

type ('a,'b) table = {
  clear: unit->unit;
  find:'a->'b;
  mem:'a->bool;
  add:'a->'b->unit;
  remove:'a->unit;
  change:'a->'b->unit
};;

let make_table () =
  let ta=hashtbl__new 127 in
  {
  clear  =(fun ()-> hashtbl__clear ta);
  find   =hashtbl__find ta;
  mem    =(fun x-> try (hashtbl__find ta x; true) with Not_found -> false);
  add    =hashtbl__add ta;
  remove =hashtbl__remove ta;
  change =fun a b -> hashtbl__remove ta a; hashtbl__add ta a b
  };;