structure Dynarray: DYNARRAY = struct
  type 'a t = (int * 'a option Array.array) ref

  fun create n =
    ref (0, Array.array (n, NONE))

  fun create0 () = create 10

  fun length dynarr =
  let
    val (len, _) = !dynarr
  in
    len
  end

  fun push dynarr v =
  let
    val (len, arr) = !dynarr
  in
    case Int.compare (len, Array.length arr) of
      EQUAL =>
      let
        val arr2 = Array.array (len * 2 + 1, NONE)
      in
        Array.copy { src = arr, dst = arr2, di = 0 };
        dynarr := (len, arr2);
        push dynarr v
      end
    | LESS => (
      Array.update (arr, len, SOME v);
      dynarr := (len + 1, arr)
    )
    | GREATER => raise Unreachable
  end

  fun pushAndGetId dynarr v =
  let
    val (len, _ ) = !dynarr
    val () = push dynarr v
  in
    len
  end

  fun get dynarr n =
  let
    val (len, arr) = !dynarr
  in
    if n >= len then
      raise Subscript
    else
      valOf $ Array.sub (arr, n)
  end

  fun set dynarr n v =
  let
    val (len, arr) = !dynarr
  in
    if n >= len then
      raise Subscript
    else
      Array.update (arr, n, SOME v)
  end

  fun reset dynarr =
  let
    val (_, arr) = !dynarr
  in
    dynarr := (0, arr)
  end

  fun toVec dynarr =
  let
    val (len, arr) = !dynarr

    fun arr2list idx acc =
      if idx = len then
        rev acc
      else
        arr2list (idx + 1) (valOf (Array.sub (arr, idx)) :: acc)
    val l = arr2list 0 []
  in
    Vector.fromList l
  end

  fun appi f dynarr =
  let
    val (len, arr) = !dynarr

    fun loop idx =
      if idx = len then
        ()
      else (
        f (idx, valOf $ Array.sub (arr, idx));
        loop (idx + 1)
      )
  in
    loop 0
  end

  fun last dynarr =
  let
    val len = length dynarr
  in
    get dynarr (len - 1)
  end

  fun pop dynarr =
  let
    val v = last dynarr
    val (len, arr) = !dynarr
  in
    dynarr := (len - 1, arr);
    v
  end

  fun update dynarr f id =
  let
    val v = get dynarr id
    val v = f v
  in
    set dynarr id v
  end

  fun copy (dynarr: 'a t) (f: 'a -> 'b): 'b t =
  let
    val dynarr2 = create (length dynarr)

    fun loop idx =
      if idx = length dynarr then
        ()
      else
        (push dynarr2 (f $ get dynarr idx); loop (idx + 1))
  in
    loop 0;
    dynarr2
  end
end