longarray.ml

(* The Longarray module is designed to work around the maximum array size
 * imposed by OCaml's built-in Array module.  Longarray provides the
 * same interface as Array (well, a portion of it) and is implemented as
 * a list of arrays.  For arrays shorter than the maximum length, the
 * only cost is an additional level of indirection. *)

(* open Pretty *)

module E = Errormsg

type 'a t = 'a array list

let split_len (len: int) : int * int =
  if len <= Sys.max_array_length then
    len, 0
  else
    Sys.max_array_length, len - Sys.max_array_length

let split_idx (idx: int) : int option =
  if idx < Sys.max_array_length then
    None
  else
    Some (idx - Sys.max_array_length)

let rec create (len: int) (init: 'a) : 'a t =
  let len1, len2 = split_len len in
  (Array.create len1 init) :: (if len2 > 0 then create len2 init else [])

let rec init (len: int) (fn: int -> 'a) : 'a t =
  let len1, len2 = split_len len in
  let fn2 i = fn (i + len1) in
  (Array.init len1 fn) :: (if len2 > 0 then init len2 fn2 else [])

let rec blit (src: 'a t) (srcidx: int)
             (dst: 'a t) (dstidx: int) (len: int) : unit =
  if srcidx != 0 || dstidx != 0 then
    E.s ("Longarray.blit with nonzero src/dst indices");
  try
    let len1, len2 = split_len len in
    Array.blit (List.hd src) 0 (List.hd dst) 0 len1;
    if len2 > 0 then
      blit (List.tl src) 0 (List.tl dst) 0 len2
  with Failure ("hd" | "tl") ->
    raise (Invalid_argument "Longarray.blit")

let rec length (a: 'a t) : int =
  match a with
  | hd :: tl -> Array.length hd + length tl
  | [] -> 0

let rec get (a: 'a t) (i: int) : 'a =
  try
    match split_idx i with
    | None -> Array.get (List.hd a) i
    | Some i' -> get (List.tl a) i'
  with Failure ("hd" | "tl") ->
    raise (Invalid_argument "(get) index out of bounds")

let rec set (a: 'a t) (i: int) (elt: 'a) : unit =
  try
    match split_idx i with
    | None -> Array.set (List.hd a) i elt
    | Some i' -> set (List.tl a) i' elt
  with Failure ("hd" | "tl") ->
    raise (Invalid_argument "(set) index out of bounds")