+++ /dev/null
-(***********************************************************************)
-(* *)
-(* TAToo *)
-(* *)
-(* Kim Nguyen, LRI UMR8623 *)
-(* Université Paris-Sud & CNRS *)
-(* *)
-(* Copyright 2010-2013 Université Paris-Sud and Centre National de la *)
-(* Recherche Scientifique. All rights reserved. This file is *)
-(* distributed under the terms of the GNU Lesser General Public *)
-(* License, with the special exception on linking described in file *)
-(* ../LICENSE. *)
-(* *)
-(***********************************************************************)
-
-(*
- Time-stamp: <Last modified on 2013-03-18 22:41:45 CET by Kim Nguyen>
-*)
-
-module N1 =
-struct
- 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 create a = create_with_level 1 a
-
- 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 idx = i - a.offset in
- let len = Array.length a.line in
- if idx >= 0 && idx < len then
- Array.unsafe_get a.line idx
- 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
-
- 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_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 == 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
- N1.add line j v
-
-
- let find a i j =
- let v = N1.find a i in
- if v == a.N1.dummy then v.N1.dummy
- else N1.find v j
-
-
- let dummy c = c.N1.dummy.N1.dummy
-
- 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
- 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
-
-module N3 =
-struct
- type 'a t = 'a N2.t N1.t
-
- 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 = N2.create_with_level (a.N1.level+1) (N2.dummy line) in
- N1.add a i nline;
- N2.add nline j k v
- else
- N2.add line j k v
-
- let find a i j k =
- let v = N1.find a i in
- if v == a.N1.dummy then N2.dummy v
- else N2.find v j k
-
-
- let dummy a = N2.dummy a.N1.dummy
- 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
- 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_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 == 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
- N3.add line j k l v
-
- let find a i j k l =
- let v = N1.find a i in
- if v == (N1.dummy a) then N3.dummy v
- else N3.find v j k l
-
-
- let dummy a = N3.dummy (N1.dummy a)
- let iteri f a =
- 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
-
-module N5 =
-struct
- type 'a t = 'a N4.t N1.t
-
-
- 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 == (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
- N4.add line j k l m v
-
- let find a i j k l m =
- let v = N1.find a i in
- if v == (N1.dummy a) then N4.dummy v
- else N4.find v j k l m
-
-
- let dummy a = N4.dummy (N1.dummy a)
- let iteri f a =
- 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 N5.t N1.t
-
- 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 = 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
- N5.add line j k l m n v
-
- let find a i j k 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 = 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