type coureur = {dossard:int;temps:float;equipe:string};;

let course = [{dossard=4000;temps=32.45;equipe="V"};
              {dossard=4001;temps=33.5;equipe="J"};
              {dossard=4005;temps=35.6;equipe="R"};
              {dossard=4003;temps=37.75;equipe="V"};
              {dossard=4002;temps=37.95;equipe="R"};
              {dossard=4008;temps=38.45;equipe="V"};
              {dossard=4007;temps=39.5;equipe="J"};
              {dossard=4004;temps=41.45;equipe="R"};
              {dossard=4006;temps=42.45;equipe="J"}];;

let rec liste_equipes course = match course with
  |[]-> [],[],[]
  |c::q-> let lv,lj,lr = liste_equipes q in
          match c.equipe with
          |"V" -> c::lv,lj,lr
          |"J" -> lv,c::lj,lr
          |_ -> lv,lj,c::lr;;

let compter_points course = 
    let rec aux classement k = match classement with
       |[]-> 0,0,0
       |c::q -> let pv,pj,pr = aux q (k+1) in
          match c.equipe with
          |"V" -> pv+k,pj,pr
          |"J" -> pv,pj+k,pr
          |_ -> pv,pj,pr+k
    in
    aux course 1;;

let classement_equipe course =
  let scores = compter_points course in
  match scores with
  |(pv,pj,pr) when pv<=pj && pj<=pr -> [("V",pv);("J",pj);("R",pr)]
  |(pv,pj,pr) when pv<=pr && pr<=pj -> [("V",pv);("R",pr);("J",pj)]
  |(pv,pj,pr) when pj<=pv && pv<=pr -> [("J",pj);("V",pv);("R",pr)]
  |(pv,pj,pr) when pj<=pr && pr<=pv -> [("J",pj);("R",pr);("V",pv)]
  |(pv,pj,pr) when pr<=pj && pj<=pv -> [("R",pr);("J",pj);("V",pv)]
  |(pv,pj,pr) -> [("R",pr);("V",pv);("J",pj)];;

type coureurmut = {dossard:int; mutable temps: float;equipe:string};;

let course = [{dossard=4000;temps=32.45;equipe="V"};
              {dossard=4001;temps=33.5;equipe="J"};
              {dossard=4005;temps=35.6;equipe="R"};
              {dossard=4003;temps=37.75;equipe="V"};
              {dossard=4002;temps=37.95;equipe="R"};
              {dossard=4008;temps=38.45;equipe="V"};
              {dossard=4007;temps=39.5;equipe="J"};
              {dossard=4004;temps=41.45;equipe="R"};
              {dossard=4006;temps=42.45;equipe="J"}];;

let rec maj course nouvtemps =
  let rec majcoureur c ltps = match ltps with
    |(a,tps)::q when a=c.dossard -> c.temps <- tps
    |_::q -> majcoureur c q
    |[] -> () in
  match course with
  |c::q -> majcoureur c nouvtemps;maj q nouvtemps
  |[] -> ()
;;

let nt = [(4000,32.4);(4001,35.8);(4002,38.2);(4003,42.5);(4004,37.3);(4005,39.7);(4006,46.4);(4007,35.4);(4008,37.6)];;

let extraire_min course = 
  let rec aux course cmin = match course with
    |[]-> cmin,[]
    |c::q when c.temps >= cmin.temps -> let c2min,q2 = aux q cmin in
                                        c2min,c::q2
    |c::q -> let c2min,q2 = aux q c in
             c2min,cmin::q2
  in
  aux (List.tl course) (List.hd course);;

let rec trie course =
  if course = [] then []
  else let cmin,reste_course = extraire_min course in
       cmin::(trie reste_course);;

let rec compter_temps classement = match classement with
  |[]-> 0.,0.,0.
  |c::q -> let pv,pj,pr = compter_temps q in
          match c.equipe with
          |"V" -> pv+.c.temps,pj,pr
          |"J" -> pv,pj+.c.temps,pr
          |_ -> pv,pj,pr+.c.temps;;

let classement_equipe course =
  let cv,cj,cr = compter_points course in
  let dv,dj,dr = compter_temps course in
  let score = (cv,dv),(cj,dj),(cr,dr) in
  match score with
  |(pv,pj,pr) when pv<=pj && pj<=pr -> [("V",pv);("J",pj);("R",pr)]
  |(pv,pj,pr) when pv<=pr && pr<=pj -> [("V",pv);("R",pr);("J",pj)]
  |(pv,pj,pr) when pj<=pv && pv<=pr -> [("J",pj);("V",pv);("R",pr)]
  |(pv,pj,pr) when pj<=pr && pr<=pv -> [("J",pj);("R",pr);("V",pv)]
  |(pv,pj,pr) when pr<=pj && pj<=pv -> [("R",pr);("J",pj);("V",pv)]
  |(pv,pj,pr) -> [("R",pr);("V",pv);("J",pj)];;

classement_equipe (trie course);;


(*k-moyennes*)

type point = {x:float;y:float};;
type centroid = {mutable xm:float;mutable ym:float};;

let dist (p:point) (c:centroid) =
  sqrt ((p.x-.c.xm)**2.+.(p.y-.c.ym)**2.);;

let centroids_init e k =
  let c = Array.make k {xm=0.;ym=0.} in
  for i = 0 to k-1 do
    c.(i) <- {xm=e.(i).x;ym= e.(i).y}
  done;
  c;;

let maj_centroids e centroids clus k =
  let card = Array.make k 0. in
  let n = Array.length e in
  for j = 0 to k-1 do
    centroids.(j).xm <- 0.;
    centroids.(j).ym <- 0.;
  done;
  for i = 0 to n-1 do
    card.(clus.(i)) <-  card.(clus.(i))+. 1.;
    centroids.(clus.(i)).xm <- centroids.(clus.(i)).xm +. e.(i).x;
    centroids.(clus.(i)).ym <- centroids.(clus.(i)).ym +. e.(i).y;
  done;
  for j = 0 to k-1 do
    centroids.(j).xm <- centroids.(j).xm /. card.(clus.(j));
    centroids.(j).ym <- centroids.(j).ym /. card.(clus.(j))
  done;;
    
let maj_clus e centroids clus k =
  let n = Array.length e in
  let maj_point p =
    let m = ref (dist e.(p) centroids.(0)) in
    let d = ref 0. in
    for i = 1 to k-1 do
      d := dist e.(p) centroids.(i);
      if !m > !d then
        (m := !d;
         clus.(p) <- i)
    done
  in
  for j = 0 to n-1 do
    maj_point j
  done;;

let kmoyennes e k nb_it =
  let n = Array.length e in
  let centroids = centroids_init e k in
  let clus = Array.make n 0 in
  maj_clus e centroids clus k;
  for i = 1 to nb_it do
    maj_centroids e centroids clus k;
    maj_clus e centroids clus k
  done;
  clus,centroids;;

let centroids_init_rand e k =
  let n = Array.length e in
  let c = Array.make k {xm=0. ; ym=0.} in
  let i = ref 0 in
  let j = ref 0 in
  let d = ref 0 in
  while !i < k do
    d := Random.int(n- !j-k+ !i +1);
    j := !j+ !d;
    c.(!i) <- {xm= e.(!j).x;ym=e.(!j).y};
    i := !i + 1;
    j := !j + 1
  done;
  c;;

let e2 = [|{x=3.;y=3.};{x=3.;y= -3.};{x= -3.;y=3.};{x= -3.;y= -3.};{x=3.;y=4.};{x=3.;y= -4.};{x= -3.;y=4.};{x= -3.;y= -4.};{x=4.;y=3.};{x=4.;y= -3.};{x= -4.;y=3.};{x= -4.;y= -3.}|];;

kmoyennes e2 4 20;;


(* Listes doublement chainées *)

let cree_file () = {premier = Vide; dernier = Vide};;

let est_vide f = (f.premier = Vide);;

let enfile x f =
  let avantdernier = f.dernier in
  let m = Interne {precedent = avantdernier; etiquette = x; suivant = Vide} in
    begin
      match avantdernier with
        | Vide -> f.premier <- m
        | Interne i -> i.suivant <- m
    end;
    f.dernier <- m;
    ()
;;

let affiche f =
  let rec parcours = function
    | Vide -> print_endline "Fin";
    | Interne mi ->
        print_int mi.etiquette;
        print_string " - ";
        parcours mi.suivant
  in parcours f.premier;;

let defile f = match f.premier with
  | Vide -> failwith "File vide"
  | Interne m -> let s = m.suivant in
      f.premier <- s;
      begin
        match s with
            Vide -> f.dernier <- Vide
          | Interne i -> i.precedent <- Vide
      end;
      m.etiquette;;

let mafile = cree_file ();;

enfile 5 mafile;;
enfile 3 mafile;;
enfile 8 mafile;;

affiche mafile;;
est_vide mafile;;

defile mafile;;
defile mafile;;
defile mafile;;

est_vide mafile;;
affiche mafile;;