X-Git-Url: http://git.nguyen.vg/gitweb/?p=tatoo.git;a=blobdiff_plain;f=src%2Futils%2Fcache.ml;h=f9b7457d827c1ad77163215ae000df116cae3466;hp=7ba67d57f88177835b91fa5a35280d3bdecb0256;hb=1972639ed4bb0aab7136e3f09d6a46398afec709;hpb=738218592e41da4ceb46f4dba41f292a60ba1f7b

diff --git a/src/utils/cache.ml b/src/utils/cache.ml
index 7ba67d5..f9b7457 100644
--- a/src/utils/cache.ml
+++ b/src/utils/cache.ml
@@ -14,37 +14,26 @@
 (***********************************************************************)
 
 (*
-  Time-stamp: <Last modified on 2013-03-13 18:17:13 CET by Kim Nguyen>
+  Time-stamp: <Last modified on 2013-03-18 22:41:45 CET by Kim Nguyen>
 *)
 
-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 N1 =
 struct
-  type 'a t = { mutable line : 'a array;
-		dummy : 'a;
-		mutable offset : int;
-	      }
-  let create _ a = {
+  type 'a t = {
+    mutable line : 'a array;
+    dummy : 'a;
+    mutable offset : int;
+    level : int;
+  }
+  type 'a index = int -> 'a
+  let level a = a.level
+  let create_with_level level a = {
     line = Array.create 0 a;
     dummy = a;
     offset = ~-1;
-
+    level = level;
   }
-
-  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 create a = create_with_level 1 a
 
   let add a i v =
     if a.offset == ~-1 then a.offset <- i;
@@ -56,7 +45,7 @@ struct
       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
+   	let narray = Array.create nlen a.dummy in
 	for j = 0 to len - 1 do
 	  narray.(j+pad) <- a.line.(j)
 	done;
@@ -75,9 +64,10 @@ struct
       end
 
   let find a i =
-    let offset = a.offset in
+    let idx = i - a.offset in
     let len = Array.length a.line in
-    if i >= offset && i < offset + len then a.line.(i - offset)
+    if idx >= 0 && idx < len then
+      Array.unsafe_get a.line idx
     else a.dummy
 
   let dummy a = a.dummy
@@ -90,26 +80,28 @@ struct
 	  f (i+a.offset) v (v==a.dummy)
       done
 
-
+  let stats a =
+    let d = dummy a in
+    let len = Array.length a.line in
+    let used = Array.fold_left (fun acc i ->
+      if i != d then acc+1 else acc) 0 a.line
+    in
+    len, used
 end
 
-
-
 module N2 =
 struct
   type 'a t = 'a N1.t N1.t
-  let create n a =
-    let dummy1 = N1.create 512 a in
-    { N1.line = Array.create n dummy1;
-      N1.offset = ~-1;
-      N1.dummy = dummy1;
-    }
+  let create_with_level level a =
+    let dummy1 = N1.create_with_level (level+1) a in
+    N1.create_with_level level dummy1
 
+  let create a = create_with_level 1 a
 
   let add a i j v =
     let line = N1.find a i in
-    if line == a.N1.dummy then
-      let nline = N1.create 0 line.N1.dummy in
+    if line == N1.dummy a then
+      let nline = N1.create_with_level (a.N1.level+1) (N1.dummy line) in
       N1.add a i nline;
       N1.add nline j v
     else
@@ -118,7 +110,7 @@ struct
 
   let find a i j =
     let v = N1.find a i in
-    if v == a.N1.dummy then a.N1.dummy.N1.dummy
+    if v == a.N1.dummy then v.N1.dummy
     else N1.find v j
 
 
@@ -131,6 +123,17 @@ struct
 	N1.iteri (f i) line.(i)
       done
 
+  let stats a =
+    let d = a.N1.dummy in
+    let len, used =
+      Array.fold_left (fun ((alen,aused) as acc) i ->
+        if i != d then
+          let l, u = N1.stats i in
+          (alen+l, aused+u)
+        else
+          acc) (0, 0) a.N1.line
+    in
+    len, used
 
 end
 
@@ -138,17 +141,17 @@ module N3 =
 struct
   type 'a t = 'a N2.t N1.t
 
-  let create n a =
-  let dummy1 = N2.create 512 a in
-    { N1.line = Array.create n dummy1;
-      N1.offset = ~-1;
-      N1.dummy = dummy1;
-    }
+  let create_with_level level a =
+    let dummy2 = N2.create_with_level (level+1) a in
+    N1.create_with_level (level) dummy2
+
+  let create a = create_with_level 1 a
+
 
   let add a i j k v =
     let line = N1.find a i in
     if line == a.N1.dummy then
-      let nline =  N1.create 0 line.N1.dummy in
+      let nline = N2.create_with_level (a.N1.level+1) (N2.dummy line) in
       N1.add a i nline;
       N2.add nline j k v
     else
@@ -156,7 +159,7 @@ struct
 
   let find a i j k =
     let v = N1.find a i in
-    if v == a.N1.dummy then N2.dummy a.N1.dummy
+    if v == a.N1.dummy then N2.dummy v
     else N2.find v j k
 
 
@@ -168,23 +171,35 @@ struct
 	N2.iteri (f i) line.(i)
       done
 
+  let stats a =
+    let d = a.N1.dummy in
+    let len, used =
+      Array.fold_left (fun ((alen,aused) as acc) i ->
+        if i != d then
+          let l, u = N2.stats i in
+          (alen+l, aused+u)
+        else
+          acc) (0, 0) a.N1.line
+    in
+    len, used
+
 end
 
 module N4 =
 struct
   type 'a t = 'a N3.t N1.t
 
-  let create n a =
-  let dummy1 = N3.create 512 a in
-    { N1.line = Array.create n dummy1;
-      N1.offset = ~-1;
-      N1.dummy = dummy1;
-    }
+  let create_with_level level a =
+    let dummy3 = N3.create_with_level (level+1) a in
+    N1.create_with_level (level) dummy3
+
+  let create a = create_with_level 1 a
+
 
   let add a i j k l v =
     let line = N1.find a i in
-    if line == a.N1.dummy then
-      let nline =  N1.create 0 line.N1.dummy in
+    if line == N1.dummy a then
+      let nline =  N3.create_with_level (a.N1.level+1) (N3.dummy line) in
       N1.add a i nline;
       N3.add nline j k l v
     else
@@ -192,17 +207,26 @@ struct
 
   let find a i j k l =
     let v = N1.find a i in
-    if v == a.N1.dummy then N3.dummy a.N1.dummy
+    if v == (N1.dummy a) then N3.dummy v
     else N3.find v j k l
 
 
-  let dummy a = N3.dummy a.N1.dummy
+  let dummy a = N3.dummy (N1.dummy a)
   let iteri f a =
-    let line = a.N1.line in
-    if a.N1.offset == ~-1 then () else
-      for i = 0 to Array.length line - 1 do
-	N3.iteri (f i) line.(i)
-      done
+    N1.iteri (fun i v _ ->
+      N3.iteri (fun j k l v2 b -> f i j k l v2 b) v ) a
+
+  let stats a =
+    let d = a.N1.dummy in
+    let len, used =
+      Array.fold_left (fun ((alen,aused) as acc) i ->
+        if i != d then
+          let l, u = N3.stats i in
+          (alen+l, aused+u)
+        else
+          acc) (0, 0) a.N1.line
+    in
+    len, used
 
 end
 
@@ -210,17 +234,17 @@ module N5 =
 struct
   type 'a t = 'a N4.t N1.t
 
-  let create n a =
-  let dummy1 = N4.create 512 a in
-    { N1.line = Array.create n dummy1;
-      N1.offset = ~-1;
-      N1.dummy = dummy1;
-    }
+
+  let create_with_level level a =
+    let dummy4 = N4.create_with_level (level+1) a in
+    N1.create_with_level level dummy4
+
+  let create a = create_with_level 1 a
 
   let add a i j k l m v =
     let line = N1.find a i in
-    if line == a.N1.dummy then
-      let nline =  N1.create 0 line.N1.dummy in
+    if line == (N1.dummy a) then
+      let nline =  N4.create_with_level (a.N1.level+1) (N4.dummy line) in
       N1.add a i nline;
       N4.add nline j k l m v
     else
@@ -228,43 +252,72 @@ struct
 
   let find a i j k l m =
     let v = N1.find a i in
-    if v == a.N1.dummy then N4.dummy a.N1.dummy
+    if v == (N1.dummy a) then N4.dummy v
     else N4.find v j k l m
 
 
-  let dummy a = N4.dummy a.N1.dummy
+  let dummy a = N4.dummy (N1.dummy a)
   let iteri f a =
-    let line = a.N1.line in
-    if a.N1.offset == ~-1 then () else
-      for i = 0 to Array.length line - 1 do
-	N4.iteri (f i) line.(i)
-      done
+    N1.iteri (fun i v _ ->
+      N4.iteri (fun j k l m v2 b -> f i j k l m v2 b) v
+    ) a
+
+
+  let stats a =
+    let d = a.N1.dummy in
+    let len, used =
+      Array.fold_left (fun ((alen,aused) as acc) i ->
+        if i != d then
+          let l, u = N4.stats i in
+          (alen+l, aused+u)
+        else
+          acc) (0, 0) a.N1.line
+    in
+    len, used
 
 end
 
 module N6 =
 struct
-  type 'a t = 'a N3.t N3.t
+  type 'a t = 'a N5.t N1.t
 
-  let create _n a =
-         let dummy1 = N3.create 512 a in
-         N3.create 512 dummy1
+  let create_with_level level a =
+    let dummy5 = N5.create_with_level (level+1) a in
+    N1.create_with_level (level) dummy5
+
+  let create a = create_with_level 1 a
 
   let add a i j k l m n v =
-    let line = N3.find a i j k in
-    if line == N3.dummy a then
-      let nline =  N3.create 0 (N3.dummy line) in
-      N3.add a i j k nline;
-      N3.add nline l m n v
+    let line = N1.find a i in
+    if line == N1.dummy a then
+      let nline = N5.create_with_level (a.N1.level+1) (N5.dummy line) in
+      N1.add a i nline;
+      N5.add nline j k l m n v
     else
-      N3.add line l m n v
+      N5.add line j k l m n v
 
   let find a i j k l m n =
-    let v = N3.find a i j k in
-    if v == N3.dummy a then N3.dummy (N3.dummy a)
-    else N3.find v l m n
+    let v = N1.find a i in
+    if v == N1.dummy a then N5.dummy v
+    else N5.find v j k l m n
 
 
-  let dummy a = N3.dummy (N3.dummy a)
-  let iteri _f _a = assert false
+  let dummy a = N5.dummy (N1.dummy a)
+  let iteri f a =
+    N1.iteri (fun i v _  ->
+      N5.iteri (fun j k l m n v2 b -> f i j k l m n v2 b) v
+    ) a
+
+  let stats a =
+    let d = a.N1.dummy in
+    let len, used =
+      Array.fold_left (fun ((alen,aused) as acc) i ->
+        if i != d then
+          let l, u = N5.stats i in
+          (alen+l, aused+u)
+        else
+          acc) (0, 0) a.N1.line
+    in
+    len, used
+
 end