(* Beispiele *)
let ex_v = [ (3,0.1); (5,0.5);  (6,0.2) ]

let ex_a = [(2,[(3,23.);(5,25.)]);(5,[(2,52.)]);(6,[(2,62.)])]

(* Vektormultiplikation *)
let rec v_mult p x y =
  match (x,y) with
    ((px,vx)::x',(py,vy)::y') -> 
      if px = py then
		v_mult (p +. vx *. vy) x' y'
	  else if px < py then
	    v_mult p x' y
	  else
	    v_mult p x y'
  | _ -> p

let v_mult x y = v_mult 0. x y

(* Matrix * Vektor *)
let m_v_mult a v =
  let l = List.map (fun (j,aj) -> (j, v_mult aj v)) a in  
    (* Multipliziert Zeilenvektor aj mit dem Vektor v*)
	List.filter (fun (j,aj) -> (aj <> 0.)) l (* Nullen entfernen *)

(* Mergesort wird fuer die Zusatzaufgabe benoetigt, 
		Loesung von Aufgabe 6.4 *)

let init l = List.map (fun x -> [x]) l

let rec merge l1 l2 =
  match (l1,l2) with 
    ([],l) | (l,[]) -> l
  | (x::xs,y::ys) -> 
      if x <= y then 
        x::(merge xs l2)
      else
        y::(merge l1 ys)

let rec merge_list = function
    [] -> []
  | [l] -> [l]
  | l1::l2::ls -> (merge l1 l2)::(merge_list ls)

let rec mergesort l =
  match l with
    [] -> []
  | [x] -> x
  | _ -> mergesort (merge_list l)

let mergesort l = mergesort (init l)


(* Transponieren oder 
	 Zeilenrepraesentation zu Spaltenrepraesentation *)

let rec v_to_list i = function
  (j,x)::v -> (i,j,x)::v_to_list i v
| _ -> [] 

let rec m_to_list = function
  (i,v)::a -> v_to_list i v @ m_to_list a
| _ -> []

let m_from_list l = 
  let l = mergesort l in
  List.fold_right 
    (
	fun (i,j,x) -> 
	  function ((i',v)::vs) -> 
	    if i = i' then 
		  ((i,(j,x)::v)::vs) 
		else 
		  (i,[(j,x)])::((i',v)::vs) 
	  | _ -> [(i,[(j,x)])]
	) 
	l 
	[] 

let transpose a =
  let l = m_to_list a in
  let l = List.map (fun (i,j,x) -> (j,i,x)) l in
  m_from_list l

(* Matrixmultiplikation *)
let m_m_mult a b =
  let b = transpose b in
  let handle_row_a (i,ai) = (i, m_v_mult b ai) in 
  let r = List.map handle_row_a a in
  List.filter (fun (_,ai) -> ai <> []) r 

let p = 
  [ 
    (1, [(3,0.2);(4,0.3)]);
    (2, [(1,0.4);(3,0.8)]);
	(3, [(1,0.6);(4,0.7)]);
	(4, [(2,1.)])
  ]

let x = [(1,1.)]
let y = [(2,1.)]

let rec iter p x i =
  if i = 0 then
    x
  else
	iter p (m_v_mult p x) (i-1)

let rec iterm p i =
  if i = 0 then
    p
  else
	iterm (m_m_mult p p) (i-1)