(* type des matrices *)
type matr =  (int * (int * float) list) list


(* question 1 *)
(* une fonction auxiliaire *)
let indice_max l = List.fold_left (fun acc l -> max acc (fst l)) (-1) l

let hauteur (m:matr) = 1 + indice_max m

let largeur (m:matr) = 1 + List.fold_left (fun acc l -> max acc (indice_max (snd l))) (-1) m


(* question 2 *)
let case l c (m:matr) =
  try List.assoc c (List.assoc l m)
  with Not_found -> 0.0

(* question 3 *)
(* une fonction auxiliaire : applatit une matrice *)
let applatit (m:matr) =
  List.fold_left
    (fun acc l ->
      let nb_ligne = fst l in
      let ligne = snd l in
      List.rev_append (List.rev_map (fun (c,v) -> (nb_ligne,c,v)) ligne) acc)
    []
    m

let transpose_aux m = List.rev_map (fun (l,c,v) -> (c,l,v)) m


(* premiere version de "reconstruit" *)
let rec cherche_ligne l m acc = match m with
    [] -> [],acc
  | (l',ligne)::m  when l'=l -> ( ligne  ,  List.rev_append acc m)
  | (l',ligne)::m -> cherche_ligne l m ((l',ligne)::acc)

let ajoute m (l,c,v) =  (* ajoute la valeur v dans la ligne l, colone c pour la matrice m *)
  let ligne,m = cherche_ligne l m [] in
	(l,(c,v)::ligne)::m
 
let reconstruit1 m = List.fold_left ajoute [] m

let transpose1 m = reconstruit1 (transpose_aux (applatit m))



(* 2eme versione de "reconstruit" *)
let reconstruit2 m : matr =
  let m = List.sort (fun (l1,c1,_) (l2,c2,_) -> compare (l1,c1) (l2,c2)) m  in
  let rec aux m j acc_l acc_m = match m with
      [] -> (j,acc_l)::acc_m
    | (l,c,v)::m when l=j -> aux m j ((c,v)::acc_l) acc_m
    | (l,c,v)::m -> aux m l [(c,v)] ((j,acc_l)::acc_m)
  in
  aux m 0 [] []

let transpose2 m = reconstruit2 (transpose_aux (applatit m))



(* quelques matrices pour les tests... *)
let m1:matr = [ (0 , [ (0,1.0) ; (1,2.0) ]) ;
		(1 , [ (0,3.0) ; (1,4.0) ]) ]
let m2:matr = [] 
let m3:matr = [ (0,[]) ]
let m4:matr = [ (0 , [ (0,1.0) ] ) ]
let m5:matr = [ (2 , [ (3,1.0) ; (1,2.0) ]) ;
	        (0 , [ (0,0.0) ; (2,4.0) ]) ]