(* 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 t = data ref and data = | Array of int array | Diff of int * int * 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 rerootk t k = match !t with | Array _ -> k () | Diff (i, v, t') -> rerootk t' (fun () -> 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; k()) let reroot t = rerootk t (fun () -> ()) 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 -> let old = a.(i) in a.(i) <- v; let res = ref n in t := Diff (i, old, res); res | Diff _ -> assert false