(*** TP : Algorithme de Berry-Sethi ***)

(* type pour les regexp et les regexp linéarisées *)

type regexp = Vide | Epsilon | C of char * int 
| Concat of regexp * regexp | Union of regexp * regexp | Etoile of regexp

(* C of char*int permettra de linéariser la rexgep*)


(* type pour représenter l'automate final. *)
(* NB : les transitions sont représentées par une liste de triplets *)

type autoND = { initial:int; final:int list; transitions:(int * char * int) list }


(* fonctions d'affichage *)

let rec afficheRegexp r = match r with
  | Vide -> print_string("vide")
  | Epsilon -> print_string("eps")
  | Concat (r1,r2) -> afficheRegexp r1; afficheRegexp r2
  | Etoile (r) -> print_string("("); afficheRegexp r; print_string(")*")
  | Union (r1,r2) -> print_string("("); afficheRegexp r1; 
    print_string("|"); afficheRegexp r2; print_string(")")
  | C (c,i) -> Printf.printf "%c%d" c i

let afficheAutomate aut =
  Printf.printf "initial:%d\n" aut.initial;
  print_string "final:["; List.iter (fun q -> Printf.printf "%d," q) aut.final; print_string "]\n";
  print_string "transitions:["; List.iter (fun (q1,c,q2) -> Printf.printf "%d-%c-%d," q1 c q2) aut.transitions; print_string "]\n";;


(* exemples *)

let r0 =
  Concat (
    Concat (C('a', 0),
            Etoile (Concat (C('b',0), C('a',0)))),
    Etoile (C('c', 0)));;

let r1 = 
  Concat (
    Etoile (Concat (C('a',0), C('b',0))),
    Concat (Concat (C('c',0), C('a',0)),
            Etoile (Union (C('c', 0), Concat (C('b',0), C('a', 0))))));;

(*linéarise une regexp *)
let linearise r = 
  let indice = ref 0 in 
  let rec auxlin r =
    (* décore l'arborescence en numétorant les caractères *)
    failwith "A faire"
  in auxlin r;; 


afficheRegexp r0;; print_newline ();;
afficheRegexp (linearise r0);; print_newline ();;


(* on représente les ensembles comme des listes sans doublons *)
(* quelques fonctions utilitaires *)

let rec ajouteSansDoublons l e =
  failwith "A faire"

let rec unionSansDoublons l1 l2 =
  failwith "A faire"

let rec produitListes l1 l2 = (* construit la liste des couples *)
  failwith "A faire"

let rec contientVide r = (* vérifie si une regexp contient le mot vide *)
  failwith "A faire"

(* renvoie P(L) -> (char * int) list *)
let rec p r = match r with  
  | _ -> failwith "A faire"

(* renvoie S(L) -> (char * int) list *)
let rec s r = match r with  
  | _ -> failwith "A faire"

(* renvoie F(L) -> ((char * int) * (char * int)) list *)
let rec f r = match r with  
  | _ -> failwith "A faire"

let affichePSF p s f =
  print_string "P:["; List.iter (fun (c,i) -> Printf.printf "%c%d," c i) p; print_string "]\n";
  print_string "S:["; List.iter (fun (c,i) -> Printf.printf "%c%d," c i) s; print_string "]\n";
  print_string "F:["; List.iter (fun ((c1,i1),(c2,i2)) -> Printf.printf "%c%d%c%d," c1 i1 c2 i2) f; print_string "]\n";