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 (***********************************************************************)
17 Time-stamp: <Last modified on 2013-03-13 16:02:03 CET by Kim Nguyen>
20 let realloc l old_size new_size dummy =
21 let l' = Array.create new_size dummy in
22 for i = 0 to (min old_size new_size) - 1 do
29 type 'a t = { mutable line : 'a array;
34 line = Array.create 0 a;
41 Format.fprintf fmt "{ offset=%i;\n dummy=_;line=%a \n}\n%!"
43 (Pretty.print_array ~sep:", " (fun fmt x ->
45 Format.fprintf fmt "%s" "D"
47 Format.fprintf fmt "%s" "E")) a.line
50 if a.offset == ~-1 then a.offset <- i;
51 let offset = a.offset in
52 let len = Array.length a.line in
53 if i >= offset && i < offset + len then
54 a.line.(i - offset) <- v
56 if i < offset then begin (* bottom resize *)
57 let pad = offset - i in
58 let nlen = len + pad in
59 let narray = Array.create nlen a.dummy in
60 for j = 0 to len - 1 do
61 narray.(j+pad) <- a.line.(j)
66 end else begin (* top resize *)
67 (* preventively allocate the space for the following elements *)
68 let nlen = ((i - offset + 1) lsl 1) + 1 in
69 let narray = Array.create nlen a.dummy in
70 for j = 0 to len - 1 do
71 narray.(j) <- a.line.(j);
73 narray.(i - offset) <- v;
78 let offset = a.offset in
79 let len = Array.length a.line in
80 if i >= offset && i < offset + len then a.line.(i - offset)
87 if a.offset == ~-1 then () else
88 for i = 0 to Array.length line - 1 do
90 f (i+a.offset) v (v==a.dummy)
100 type 'a t = 'a N1.t N1.t
102 let dummy1 = N1.create 512 a in
103 { N1.line = Array.create n dummy1;
110 let line = N1.find a i in
111 if line == a.N1.dummy then
112 let nline = N1.create 0 line.N1.dummy in
120 let v = N1.find a i in
121 if v == a.N1.dummy then a.N1.dummy.N1.dummy
125 let dummy c = c.N1.dummy.N1.dummy
128 let line = a.N1.line in
129 if a.N1.offset == ~-1 then () else
130 for i = 0 to Array.length line - 1 do
131 N1.iteri (f i) line.(i)
139 type 'a t = 'a N2.t N1.t
142 let dummy1 = N2.create 512 a in
143 { N1.line = Array.create n dummy1;
149 let line = N1.find a i in
150 if line == a.N1.dummy then
151 let nline = N1.create 0 line.N1.dummy in
158 let v = N1.find a i in
159 if v == a.N1.dummy then N2.dummy a.N1.dummy
163 let dummy a = N2.dummy a.N1.dummy
165 let line = a.N1.line in
166 if a.N1.offset == ~-1 then () else
167 for i = 0 to Array.length line - 1 do
168 N2.iteri (f i) line.(i)
175 type 'a t = 'a N3.t N1.t
178 let dummy1 = N3.create 512 a in
179 { N1.line = Array.create n dummy1;
184 let add a i j k l v =
185 let line = N1.find a i in
186 if line == a.N1.dummy then
187 let nline = N1.create 0 line.N1.dummy in
194 let v = N1.find a i in
195 if v == a.N1.dummy then N3.dummy a.N1.dummy
199 let dummy a = N3.dummy a.N1.dummy
201 let line = a.N1.line in
202 if a.N1.offset == ~-1 then () else
203 for i = 0 to Array.length line - 1 do
204 N3.iteri (f i) line.(i)
211 type 'a t = 'a N4.t N1.t
214 let dummy1 = N4.create 512 a in
215 { N1.line = Array.create n dummy1;
220 let add a i j k l m v =
221 let line = N1.find a i in
222 if line == a.N1.dummy then
223 let nline = N1.create 0 line.N1.dummy in
225 N4.add nline j k l m v
227 N4.add line j k l m v
229 let find a i j k l m =
230 let v = N1.find a i in
231 if v == a.N1.dummy then N4.dummy a.N1.dummy
232 else N4.find v j k l m
235 let dummy a = N4.dummy a.N1.dummy
237 let line = a.N1.line in
238 if a.N1.offset == ~-1 then () else
239 for i = 0 to Array.length line - 1 do
240 N4.iteri (f i) line.(i)