let realloc l old_size new_size dummy =
  let l' = Array.create new_size dummy in
  for i = 0 to (min old_size new_size) - 1 do
    l'.(i) <- l.(i);
  done;
  l'

module Lvl1 =
struct
  type 'a t = { mutable line : 'a array;
		dummy : 'a;
		mutable offset : int;
	      }
  let create n a = {
    line = Array.create 0 a;
    dummy = a;
    offset = ~-1;

  }

  let print fmt a =
    Format.fprintf fmt "{ offset=%i;\n dummy=_;line=%a \n}\n%!"
      a.offset
      (Pretty.print_array ~sep:", " (fun fmt x ->
	if x==a.dummy then
	  Format.fprintf fmt "%s" "D"
	else
	  Format.fprintf fmt "%s" "E")) a.line

  let add a i v =
    if a.offset == ~-1 then a.offset <- i;
    let offset = a.offset in
    let len = Array.length a.line in
    if i >= offset && i < offset + len then
      a.line.(i - offset) <- v
    else
      if i < offset then begin (* bottom resize *)
	let pad = offset - i in
	let nlen = len + pad in
	let narray = Array.create nlen a.dummy in
	for j = 0 to len - 1 do
	  narray.(j+pad) <- a.line.(j)
	done;
	a.offset <- i;
	a.line <- narray;
	narray.(0) <- v;
      end else begin (* top resize *)
	(* preventively allocate the space for the following elements *)
	let nlen = ((i - offset + 1) lsl 1) + 1 in
	let narray = Array.create nlen a.dummy in
	for j = 0 to len - 1 do
	  narray.(j) <- a.line.(j);
	done;
	narray.(i - offset) <- v;
	a.line <- narray
      end

  let find a i =
    let offset = a.offset in
    let len = Array.length a.line in
    if i >= offset && i < offset + len then a.line.(i - offset)
    else a.dummy

  let dummy a = a.dummy

  let iteri f a =
    let line = a.line in
    if a.offset == ~-1 then () else
      for i = 0 to Array.length line - 1 do
	let v = line.(i) in
	  f (i+a.offset) v (v==a.dummy)
      done


end



module Lvl2 =
struct
  type 'a t = 'a Lvl1.t Lvl1.t
  let create n a =
    let dummy1 = Lvl1.create 512 a in
    { Lvl1.line = Array.create n dummy1;
      Lvl1.offset = ~-1;
      Lvl1.dummy = dummy1;
    }


  let add a i j v =
    let line = Lvl1.find a i in
    if line == a.Lvl1.dummy then
      let nline = Lvl1.create 0 line.Lvl1.dummy in
      Lvl1.add a i nline;
      Lvl1.add nline j v
    else
      Lvl1.add line j v


  let find a i j =
    let v = Lvl1.find a i in
    if v == a.Lvl1.dummy then a.Lvl1.dummy.Lvl1.dummy
    else Lvl1.find v j


  let dummy c = c.Lvl1.dummy.Lvl1.dummy

  let iteri f a =
    let line = a.Lvl1.line in
    if a.Lvl1.offset == ~-1 then () else
      for i = 0 to Array.length line - 1 do
	Lvl1.iteri (f i) line.(i)
      done


end

module Lvl3 =
struct
  type 'a t = 'a Lvl2.t Lvl1.t

  let create n a =
  let dummy1 = Lvl2.create 512 a in
    { Lvl1.line = Array.create n dummy1;
      Lvl1.offset = ~-1;
      Lvl1.dummy = dummy1;
    }

  let add a i j k v =
    let line = Lvl1.find a i in
    if line == a.Lvl1.dummy then
      let nline =  Lvl1.create 0 line.Lvl1.dummy in
      Lvl1.add a i nline;
      Lvl2.add nline j k v
    else
      Lvl2.add line j k v

  let find a i j k =
    let v = Lvl1.find a i in
    if v == a.Lvl1.dummy then Lvl2.dummy a.Lvl1.dummy
    else Lvl2.find v j k


  let dummy a = Lvl2.dummy a.Lvl1.dummy
  let iteri f a =
    let line = a.Lvl1.line in
    if a.Lvl1.offset == ~-1 then () else
      for i = 0 to Array.length line - 1 do
	Lvl2.iteri (f i) line.(i)
      done

end