1 (***********************************************************************)
5 (* Kim Nguyen, LRI UMR8623 *)
6 (* Université Paris-Sud & CNRS *)
8 (* Copyright 2010-2013 Université Paris-Sud and Centre National de la *)
9 (* Recherche Scientifique. All rights reserved. This file is *)
10 (* distributed under the terms of the GNU Lesser General Public *)
11 (* License, with the special exception on linking described in file *)
14 (***********************************************************************)
19 mutable line : 'a array;
24 type 'a index = int -> 'a
26 let create_with_level level a = {
27 line = Array.create 0 a;
32 let create a = create_with_level 1 a
35 if a.offset == ~-1 then a.offset <- i;
36 let offset = a.offset in
37 let len = Array.length a.line in
38 if i >= offset && i < offset + len then
39 a.line.(i - offset) <- v
41 if i < offset then begin (* bottom resize *)
42 let pad = offset - i in
43 let nlen = len + pad in
44 let narray = Array.create nlen a.dummy in
45 for j = 0 to len - 1 do
46 narray.(j+pad) <- a.line.(j)
51 end else begin (* top resize *)
52 (* preventively allocate the space for the following elements *)
53 let nlen = ((i - offset + 1) lsl 1) + 1 in
54 let narray = Array.create nlen a.dummy in
55 for j = 0 to len - 1 do
56 narray.(j) <- a.line.(j);
58 narray.(i - offset) <- v;
63 let idx = i - a.offset in
64 let len = Array.length a.line in
65 if idx >= 0 && idx < len then
66 Array.unsafe_get a.line idx
73 if a.offset == ~-1 then () else
74 for i = 0 to Array.length line - 1 do
76 f (i+a.offset) v (v==a.dummy)
81 let len = Array.length a.line in
82 let used = Array.fold_left (fun acc i ->
83 if i != d then acc+1 else acc) 0 a.line
90 type 'a t = 'a N1.t N1.t
91 let create_with_level level a =
92 let dummy1 = N1.create_with_level (level+1) a in
93 N1.create_with_level level dummy1
95 let create a = create_with_level 1 a
98 let line = N1.find a i in
99 if line == N1.dummy a then
100 let nline = N1.create_with_level (a.N1.level+1) (N1.dummy line) in
108 let v = N1.find a i in
109 if v == a.N1.dummy then v.N1.dummy
113 let dummy c = c.N1.dummy.N1.dummy
116 let line = a.N1.line in
117 if a.N1.offset == ~-1 then () else
118 for i = 0 to Array.length line - 1 do
119 N1.iteri (f i) line.(i)
123 let d = a.N1.dummy in
125 Array.fold_left (fun ((alen,aused) as acc) i ->
127 let l, u = N1.stats i in
130 acc) (0, 0) a.N1.line
138 type 'a t = 'a N2.t N1.t
140 let create_with_level level a =
141 let dummy2 = N2.create_with_level (level+1) a in
142 N1.create_with_level (level) dummy2
144 let create a = create_with_level 1 a
148 let line = N1.find a i in
149 if line == a.N1.dummy then
150 let nline = N2.create_with_level (a.N1.level+1) (N2.dummy line) in
157 let v = N1.find a i in
158 if v == a.N1.dummy then N2.dummy v
162 let dummy a = N2.dummy a.N1.dummy
164 let line = a.N1.line in
165 if a.N1.offset == ~-1 then () else
166 for i = 0 to Array.length line - 1 do
167 N2.iteri (f i) line.(i)
171 let d = a.N1.dummy in
173 Array.fold_left (fun ((alen,aused) as acc) i ->
175 let l, u = N2.stats i in
178 acc) (0, 0) a.N1.line
186 type 'a t = 'a N3.t N1.t
188 let create_with_level level a =
189 let dummy3 = N3.create_with_level (level+1) a in
190 N1.create_with_level (level) dummy3
192 let create a = create_with_level 1 a
195 let add a i j k l v =
196 let line = N1.find a i in
197 if line == N1.dummy a then
198 let nline = N3.create_with_level (a.N1.level+1) (N3.dummy line) in
205 let v = N1.find a i in
206 if v == (N1.dummy a) then N3.dummy v
210 let dummy a = N3.dummy (N1.dummy a)
212 N1.iteri (fun i v _ ->
213 N3.iteri (fun j k l v2 b -> f i j k l v2 b) v ) a
216 let d = a.N1.dummy in
218 Array.fold_left (fun ((alen,aused) as acc) i ->
220 let l, u = N3.stats i in
223 acc) (0, 0) a.N1.line
231 type 'a t = 'a N4.t N1.t
234 let create_with_level level a =
235 let dummy4 = N4.create_with_level (level+1) a in
236 N1.create_with_level level dummy4
238 let create a = create_with_level 1 a
240 let add a i j k l m v =
241 let line = N1.find a i in
242 if line == (N1.dummy a) then
243 let nline = N4.create_with_level (a.N1.level+1) (N4.dummy line) in
245 N4.add nline j k l m v
247 N4.add line j k l m v
249 let find a i j k l m =
250 let v = N1.find a i in
251 if v == (N1.dummy a) then N4.dummy v
252 else N4.find v j k l m
255 let dummy a = N4.dummy (N1.dummy a)
257 N1.iteri (fun i v _ ->
258 N4.iteri (fun j k l m v2 b -> f i j k l m v2 b) v
263 let d = a.N1.dummy in
265 Array.fold_left (fun ((alen,aused) as acc) i ->
267 let l, u = N4.stats i in
270 acc) (0, 0) a.N1.line
278 type 'a t = 'a N5.t N1.t
280 let create_with_level level a =
281 let dummy5 = N5.create_with_level (level+1) a in
282 N1.create_with_level (level) dummy5
284 let create a = create_with_level 1 a
286 let add a i j k l m n v =
287 let line = N1.find a i in
288 if line == N1.dummy a then
289 let nline = N5.create_with_level (a.N1.level+1) (N5.dummy line) in
291 N5.add nline j k l m n v
293 N5.add line j k l m n v
295 let find a i j k l m n =
296 let v = N1.find a i in
297 if v == N1.dummy a then N5.dummy v
298 else N5.find v j k l m n
301 let dummy a = N5.dummy (N1.dummy a)
303 N1.iteri (fun i v _ ->
304 N5.iteri (fun j k l m n v2 b -> f i j k l m n v2 b) v
308 let d = a.N1.dummy in
310 Array.fold_left (fun ((alen,aused) as acc) i ->
312 let l, u = N5.stats i in
315 acc) (0, 0) a.N1.line