#use "tp2.mli";;


module Tp2 : TP2 = struct

    exception Non_Implante of string

    (* Principaux types du Tp ------------------------------------------------ *)
    (* ----------------------------------------------------------------------- *)
    type programme = transition list * etat
    and  transition = etat * action * etat
    and  action = Epsilon | Api of string
    and  etat = int;;

    open List

    (*let pgm1 =
      ([(1, Api "a", 2); (2, Epsilon, 6); (2, Epsilon, 6); (6, Api "e", 7);
        (7, Epsilon, 7); (7, Api "exit", 10)],1);;

    let pgm2 =
      ([(1, Api "a", 2); (2, Epsilon, 5); (5, Epsilon, 6); (6, Api "c", 7);
        (7, Epsilon, 7); (1, Epsilon, 3); (3, Api "a", 4); (4, Epsilon, 4);
        (4, Api "b", 8)],1);;

    let pgm3 =
      ([(1, Epsilon, 2); (2, Api "a", 6); (6, Epsilon, 7); (7, Api "b", 10);
          (10, Epsilon, 10); (6, Api "c", 8); (1, Epsilon, 4);
          (4, Epsilon, 1)], 1);;

    let pgm4 =
      ([(0, Api "a", 6); (0, Epsilon, 3); (6, Api "b", 10); (6, Api "c", 8);
        (8, Epsilon, 8)],0);;*)


    (* Fonctions du Tp à implanter ------------------------------------------- *)
    let isActionAPI (action : action) = match action with
    | Epsilon -> false
    | Api(_) -> true;;

    let rec getTransition listeTransition etatRecherche listeAPI listeEpsi  =
      match listeTransition with
      | [] -> (listeAPI,listeEpsi)
      | hd::tl -> match hd with
      | (etat1,action,etat2) when etat1 = etatRecherche && isActionAPI(action) = true-> getTransition tl etatRecherche (hd::listeAPI) listeEpsi
      | (etat1,action,etat2) when etat1 = etatRecherche && isActionAPI(action) = false -> getTransition tl etatRecherche listeAPI (hd::listeEpsi)
      | (_,_,_) -> getTransition tl etatRecherche listeAPI listeEpsi;;


    (* ----------------------------------------------------------------------- *)

    (* 5 points *)

    let transitionsImmediates pgm etat =
      match pgm with
      | (listeTransition,_)->  getTransition listeTransition etat [] [];;

    (* 30 points *)

    (* x appartient à l? *)
     let ( <+ ) x l = exists (fun y -> x = y) l;;

    (* ajout x à l si x n'existe pas déjà dans l *)
    let ( +: ) x l = if x <+ l then l else x::l;;

        let actionEpsiImmediats transitions etat =
          fold_left (fun l (e1,action,e2) -> if e1 = etat && isActionAPI(action) = false  then e2 +: l else l)
                    [] transitions ;;

        let getEpsiSucc listeTransition etat =
          let rec parcours etat acc =
            let immediats = actionEpsiImmediats listeTransition etat in
            let etats = filter (fun x -> not (x <+ acc)) immediats in
            fold_left (fun l e -> parcours e l) (acc @ immediats) immediats
          in
          parcours etat [];;

    let rec getEpsilons listeTransition acc =
       match listeTransition with
       | [] -> acc
       | hd::tl -> match hd with
       | (etat1,action,etat2) when isActionAPI(action) = true -> getEpsilons tl ((etat1,[])::acc)
       | (etat1,action,etat2) when isActionAPI(action) = false -> getEpsilons tl ((etat1,(getEpsiSucc listeTransition etat1))::acc) ;;

    let epsilonAtteignable pgm =
      match pgm with
      | (listeTransition,_)->  getEpsilons listeTransition  [];;

    (* 30 points *)
    let supprimeEpsilon pgm =
        raise (Non_Implante "supprimeEpsilon a completer");;

    (* 20 points *)
    let similaire pgm1 pgm2 =
        raise (Non_Implante "similaire a completer");;

    (* 5 points *)
    let bisimilaire pgm1 pgm2 =
        raise (Non_Implante "bisimilaire a completer");;

    (* 10 points *)
    let estSousPgm pgm1 pgm2 =
        raise (Non_Implante "estSousPgm a completer");;

end