(* persistent arrays implemented in a more subtle way:
as soon as we get read in a Diff we exchange the roles of Array and Diff
(rerooting) *)
type 'a t = 'a data ref
and 'a data =
| Array of 'a array
| Diff of int * 'a * 'a t
let create n v = ref (Array (Array.create n v))
let init n f = ref (Array (Array.init n f))
(* reroot t ensures that t becomes an Array node *)
let rec reroot t = match !t with
| Array _ -> ()
| Diff (i, v, t') ->
reroot t';
begin match !t' with
| Array a as n ->
let v' = a.(i) in
a.(i) <- v;
t := n;
t' := Diff (i, v', t)
| Diff _ -> assert false
end
let rec get t i = match !t with
| Array a ->
a.(i)
| Diff _ ->
reroot t;
begin match !t with Array a -> a.(i) | Diff _ -> assert false end
let set t i v =
reroot t;
match !t with
| Array a as n when i < Array.length a ->
let old = a.(i) in
a.(i) <- v;
let res = ref n in
t := Diff (i, old, res);
res
| Array a -> (* needs resizing *)
let size = max (i+1) (2 * Array.length a) in
let a' = Array.create size 0 in
Array.blit a 0 a' 0 (Array.length a);
let old = a'.(i) in
a'.(i) <- v;
let res = ref (Array a') in
t := Diff (i, old, res);
res
| Diff _ ->
assert false