+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'
+ Array.blit l 0 l' 0 (min old_size new_size);
+ l'
module Lvl1 =
- struct
+struct
- type 'a t = { mutable line : 'a array;
- dummy : 'a }
- let create n a = { line = Array.create n a;
- dummy = a }
+ type 'a t = { mutable line : 'a array;
+ 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 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 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 dummy c = c.dummy
- let to_array c = c.line
- end
+ 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 (*Array.create c.l1_size c.dummy*) 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
+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 i j k = t.line.(i).(j).(k)
-(*
- let find t i j k =
- let line = t.line in
- let line1 = line.(i) in
- if line1 == dummy_line1 then t.dummy else
- let line2 = line1.(j) in
- if line2 == dummy_line2 then t.dummy else line2.(k)
-*)
-
- let add t i j k 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
+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