(* 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