(* TP imperatif *)

let next_fact =
  let (r,v) = (ref 0, ref 1) in
  function () ->
    incr r;
    v := !r * !v;
    !v

let build_next_seq u0 f =
  let (r,v) = (ref 0, ref u0) in
  function () ->
    incr r;
    v := f !r !v;
    !v

let (next,reset,get) =
  let c = ref 0 in
  (
    (fun () -> incr c; !c),
    (fun () -> c := 0),
    (fun () -> !c)
  )

(* Vectors *)

(* Traditionnal vectors *)

exception Vector_full
exception Vector_out_of_range of int * int

type 'a t = {
  mutable size : int;
  tab  : 'a array;
}

let make max base =
  {
    size = 0;
    tab = Array.make max base;
  }

let add x v =
  if v.size = Array.length v.tab then
    raise Vector_full
  else
    begin
      v.tab.(v.size) <- x;
      v.size <- v.size + 1;
    end

let get i v =
  if i < 0 || i >= v.size then
    raise (Vector_out_of_range (i,v.size))
  else v.tab.(i)

let insert_at i x v =
  begin
    ignore ( i < Array.length v.tab || raise Vector_full);
    ignore ((i < 0 || i > v.size ) || raise (Vector_out_of_range (i,v.size)));
    for j = v.size downto i+1 do
      v.tab.(j) <- v.tab.(j-1)
    done;
    v.tab.(i) <- x;
    v.size <- v.size + 1;
  end

let iteri f v =
  for i = 0 to v.size do
    f i v.tab.(i)
  done

let iter f v = iteri (fun _ -> f) v

let mapi f v = {
  v with
    tab = Array.init (Array.length v.tab) (fun i -> f i v.tab.(i))
}

let map f v = mapi (fun _ -> f) v

let fold f a v =
  let rec aux a = function
    | 0 -> a
    | n -> aux (f a v.tab.(n-1)) (n-1)
  in aux a v.size

(* Mutable List *)

type 'a _t = {
  mutable content : 'a;
  mutable next : 'a _t option;
}

type 'a t = {
  mutable size : int;
  mutable inner : 'a _t option;
}

let create () = { size = 0; inner = None; }

let add x l =
  l.inner <- Some {content = x; next = l.inner; };
  l.size <- l.size + 1

let length l = l.size

let map f l = {
  l with inner =
    let rec aux = function
      | None -> None
      | Some c -> Some { content = f c.content; next = aux c.next }
    in aux l.inner
}

let iter f l =
  let rec aux = function
    | None -> ()
    | Some c -> f c.content; aux c.next
  in aux l.inner

let fold_left f a l =
  let rec aux a = function
    | None -> a
    | Some c -> aux (f a c.content) c.next
  in aux a l.inner

let fold_right f l a =
  let rec aux a = function
    | None -> a
    | Some c -> f c.content (aux a c.next)
  in aux a l.inner

let access f l =
  let rec aux = function
    | None -> raise Not_found
    | Some c when f c -> c
    | Some c -> aux c.next
  in aux l.inner

let nth i l =
  if i < 0 || i >= l.size then
    invalid_arg "Bad index"
  else
    let r = ref (i+1) in
    (access (fun _ -> decr r; !r = 0 ) l).content

let replace_at i x l =
  if i < 0 || i >= l.size then
    invalid_arg "Bad index"
  else
    let r = ref (i+1) in
    (access (fun _ -> decr r; !r = 0 ) l).content <- x

let replace_if f x l =
  try (access (fun c -> f c.content) l).content <- x; true with
    | Not_found -> false

(***************************************************************************)
(*                              Tests                                      *)
(***************************************************************************)

let static_list = {
  size = 3;
  inner = Some {
    content = 0;
    next = Some {
      content = 1;
      next = Some {
        content = 2;
        next = None;
      };
    };
  };
}

let display l =
  begin
    Format.printf "@[<b 2>[@;";
    iter (Format.printf "%d;@;") l;
    Format.printf "]@]@,";
  end

let dyn_list n =
  let l = create () in
  for i = 0 to n-1 do
    add i l;
  done; l

let main _ =
  begin
    (* Need working create and add *)
    let l = dyn_list 10 in
    Format.printf "@[<v>";

    Format.printf "testing add and iter:@;";
    display l;

    Format.printf "@,testing map:@;";
    display (map (fun x -> x*x) l);

    Format.printf "@,testing fold_left: %d@," (fold_left (+) 0 l);

    Format.printf "@,testing fold_right: %d@," (fold_right (+) l 0);

    Format.printf "@,testing fold_right (more):@,@[<b>[";
    List.iter (Format.printf "@;%d;") (fold_right (fun h t -> h::t) l []);
    Format.printf "@;]@]@,";

    Format.printf "@,@[<v 2>testing nth:";
    for i = 0 to (length l) - 1 do
      Format.printf "@,@[<h>nth %d l = %d@]" i (nth i l);
    done;
    Format.printf "@]@,";

    Format.printf "@,testing replace_at:@,";
    for i = 0 to (length l) - 1 do
      replace_at i i l;
      assert (nth i l = i);
    done;
    display l;

    Format.printf "@,@[<b 2>testing replace_if:";
    for i = 0 to (length l) - 1 do
      if replace_if (fun x -> x = i) (i*10) l then
        Format.printf "@;OK"
      else
        Format.printf "@;KO"
    done;
    Format.printf "@]@,";
    display l;

    Format.printf "@]@.";
    exit 0
  end
let _ = main ()