INCLUDE "trace.ml"

let realloc l old_size new_size dummy =
  let l' = Array.create new_size dummy in
  Array.blit l 0 l' 0 (min old_size new_size);
  l'

module Lvl1 =
struct

  type 'a t = { mutable line : 'a array;
		dummy : 'a }

  let create n a = { line = Array.create n a;
		     dummy = a }

  let find c i =
    let line = c.line in
    let len = Array.length line in
    if i >= len then c.dummy else line.(i)

  let add c i v =
    let line = c.line in
    let len = Array.length line in
    if i >= len then c.line <- realloc line len (i*2+1) c.dummy;
    c.line.(i) <- v

  let dummy c = c.dummy

  let to_array c = c.line
end

include Lvl1

module Lvl2 =
struct
  type 'a t = { mutable line : 'a array array;
		dummy : 'a;
		l1_size : int;
		dummy_line1 : 'a array
	      }

  let dummy_line = [| |]

  let create ?(l1_size=512) n a =
    let dummy_line1 = Array.create l1_size a in
    { line = Array.create n dummy_line1;
      dummy = a;
      l1_size = l1_size;
      dummy_line1 = dummy_line1;
    }

  let find c i j = c.line.(i).(j)

  let add c i j v =
    let line = c.line in
    let len = Array.length line in
    if i >= len then
      c.line <- realloc line len (i*2 + 1) c.dummy_line1;
    let line = c.line.(i) in
    let line =
      if line == c.dummy_line1 then
	let nline = Array.copy line in
	c.line.(i) <- nline;
	nline
      else line
    in
    line.(j) <- v

  let dummy c = c.dummy
  let to_array c = c.line
  let dummy_line c = c.dummy_line1
end

module Lvl3 =
struct
  type 'a t =
      { mutable line : 'a array array array;
	dummy : 'a;
	l1_size : int;
	l2_size : int;
	dummy_line1 : 'a array array;
	dummy_line2 : 'a array }

  let dummy_line2 = [| |]
  let dummy_line1 = [| |]

  let create ?(l1_size=512) ?(l2_size=512) n a =
    let dummy_line2 = Array.create l2_size a in
    let dummy_line1 = Array.create l1_size dummy_line2 in
    { line = Array.create n dummy_line1;
      dummy = a;
      l1_size = l1_size;
      l2_size = l2_size;
      dummy_line1 = dummy_line1;
      dummy_line2 = dummy_line2
    }
  let find t k j i = t.line.(i).(j).(k)


  let add t k j i v =
    let line = t.line in
    let line1 =
      let l1 = line.(i) in
      if l1 == t.dummy_line1 then
	let l1' = Array.copy l1 in
	line.(i) <- l1'; l1'
      else l1
    in
    let line2 =
      let l2 = line1.(j) in
      if l2 == t.dummy_line2 then
	let l2' = Array.copy l2 in
	line1.(j) <- l2'; l2'
      else l2
    in
    line2.(k) <- v

  let dummy a = a.dummy
  let to_array a = a.line
end