LinearizedArray.ml 1.74 KB
Newer Older
1 2 3 4 5
(* The [entry] array contains offsets into the [data] array. It has [n+1]
   elements if the original (unencoded) array has [n] elements. The value
   of [entry.(n)] is the length of the [data] array. This convention is
   natural and allows avoiding a special case. *)

POTTIER Francois's avatar
POTTIER Francois committed
6 7 8 9 10 11 12 13
type 'a t =
  (* data: *)   'a array *
  (* entry: *) int array

let make (a : 'a array array) : 'a t =
  let n = Array.length a in
  (* Build the entry array. *)
  let size = ref 0 in
14
  let entry = Array.init (n + 1) (fun i ->
POTTIER Francois's avatar
POTTIER Francois committed
15
    let s = !size in
16 17
    if i < n then
      size := s + Array.length a.(i);
POTTIER Francois's avatar
POTTIER Francois committed
18 19
    s
  ) in
20
  assert (entry.(n) = !size);
POTTIER Francois's avatar
POTTIER Francois committed
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
  (* Build the data array. *)
  let i = ref 0
  and j = ref 0 in
  let data = Array.init !size (fun _ ->
    while !j = Array.length a.(!i) do
      i := !i + 1;
      j := 0;
    done;
    let x = a.(!i).(!j) in
    j := !j + 1;
    x
  ) in
  data, entry

let length ((_, entry) : 'a t) : int =
  Array.length entry

38 39
let row_length ((_, entry) : 'a t) i : int =
  entry.(i + 1) - entry.(i)
POTTIER Francois's avatar
POTTIER Francois committed
40

41 42 43
let row_length_via get_entry i =
  get_entry (i + 1) - get_entry i

POTTIER Francois's avatar
POTTIER Francois committed
44 45 46 47
let read ((data, entry) as la : 'a t) i j : 'a =
  assert (0 <= j && j < row_length la i);
  data.(entry.(i) + j)

48 49 50 51
let read_via get_data get_entry i j =
  assert (0 <= j && j < row_length_via get_entry i);
  get_data (get_entry i + j)

POTTIER Francois's avatar
POTTIER Francois committed
52 53 54 55
let write ((data, entry) as la : 'a t) i j (v : 'a) : unit =
  assert (0 <= j && j < row_length la i);
  data.(entry.(i) + j) <- v

56
let rec read_interval_via get_data i j =
POTTIER Francois's avatar
POTTIER Francois committed
57 58 59
  if i = j then
    []
  else
60 61 62 63
    get_data i :: read_interval_via get_data (i + 1) j

let read_row_via get_data get_entry i =
  read_interval_via get_data (get_entry i) (get_entry (i + 1))
POTTIER Francois's avatar
POTTIER Francois committed
64

65
let read_row ((data, entry) : 'a t) i : 'a list =
66
  read_row_via (Array.get data) (Array.get entry) i
POTTIER Francois's avatar
POTTIER Francois committed
67