(* If you would like, write how many hours you spent on this homework:

  XXX

*)

(** Q1 **)

module Fresh = struct
  let ctr = ref 0
  let fresh () = 
      ctr := !ctr + 1;
      !ctr
end

module type FreshSig = sig
  val fresh : unit -> int
end

module FixedFresh : FreshSig = struct 
  let ctr = ref 0
  let fresh () = 
      ctr := !ctr + 1;
      !ctr
end

(* Return two integers --- both coming from different calls to Fresh.fresh --- that should always be equal. *)
let break_fresh () : int * int = failwith "TODO"

(* TODO: Why does the above code not work for FixedFresh? 
    ---

*)

(** Q2 **)

module type ManualRefSig = sig
  type 'a arena 
  type 'a mref

  (* Create a new arena. The argument (capacity of the arena) must be nonnegative. *)
  val fresh_arena : int -> 'a arena

  (* Find an unused slot in the arena and store the given value there; and return an mref to that location. 
     Return None if no free space is available.
  *)
  val alloc : 'a arena -> 'a -> 'a mref option

  (* Free the mref, which should allow that slot in the arena to be re-used. If the mref points to an already freed location, the operation should do nothing. *)
  val free : 'a arena -> 'a mref -> unit

  (* Read an mref. Should return None if the mref is pointing to a freed location in the arena. *)
  val read : 'a arena -> 'a mref -> 'a option

  (* Write to an mref. Should return None if the mref is pointign to a freed location in the arena. *)
  val write : 'a arena -> 'a mref -> 'a -> unit option

  (* Do the two mrefs point to the same index in the arena? *)
  val phys_eq : 'a mref -> 'a mref -> bool

  (* Return the number of currently free cells in the arena. *)
  val num_free : 'a arena -> int

  (* Return the number of times we have called alloc on the arena. *)
  val num_allocations : 'a arena -> int
end

module ManualRef : ManualRefSig = struct
    type 'a arena = unit (* TODO: Replace with your type *)
    type 'a mref = unit (* TODO: Replace with your type *)

    let fresh_arena (n : int) = failwith "TODO"

    let alloc (a : 'a arena) (x : 'a) = failwith "TODO"

    let free (a : 'a arena) (m : 'a mref) = failwith "TODO"

    let read (a : 'a arena) (m : 'a mref) = failwith "TODO"
    let write (a : 'a arena) (m : 'a mref) (x : 'a) = failwith "TODO"

    let phys_eq (m1 : 'a mref) (m2 : 'a mref) = failwith "TODO"

    let num_free (a : 'a arena) = failwith "TODO"
    let num_allocations (a : 'a arena) = failwith "TODO"

end

(** Q3 **)

module MemorySpecs (R : ManualRefSig) = struct
  open R
  let leakage_free (a : 'a arena) (f : 'a arena -> 'b) : bool = failwith "TODO"
  let num_allocations_in (a : 'a arena) (f : 'a arena -> 'b) : int = failwith "TODO"
end

(** Q4 **)

module Fib (R : ManualRefSig) = struct
  open R
  module IntMap = Map.Make(Int)

  (* Helper functions *)
  let create_map (n : int) (f : int -> 'a) : 'a IntMap.t = 
      IntMap.of_list (List.init n (fun i -> (i, f i)))

  let create_map_option (n : int) (f : int -> 'a option) : ('a IntMap.t) option = 
    let pairs = List.init n (fun i -> (i, f i)) in 
    if List.exists (fun p -> (Option.is_none (snd p))) pairs then 
        None 
    else 
        Some (IntMap.of_list (List.map (fun p -> (fst p, Option.get (snd p))) pairs))
  let iter_map (m : 'a IntMap.t) (f : int -> 'a -> unit) : unit = 
      IntMap.iter f m

  let fib_fast (a : int arena) (n : int) : int option = failwith "TODO"
end