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-14 14:50:18 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
23 Array.unsafe_set l' i (Array.unsafe_get l i);
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 idx = i - a.offset in
79 let len = Array.length a.line in
80 if idx >= 0 && idx < len then
81 Array.unsafe_get a.line idx
88 if a.offset == ~-1 then () else
89 for i = 0 to Array.length line - 1 do
91 f (i+a.offset) v (v==a.dummy)
99 type 'a t = 'a N1.t N1.t
101 let dummy1 = N1.create a in
105 let line = N1.find a i in
106 if line == a.N1.dummy then
107 let nline = N1.create line.N1.dummy in
115 let v = N1.find a i in
116 if v == a.N1.dummy then v.N1.dummy
120 let dummy c = c.N1.dummy.N1.dummy
123 let line = a.N1.line in
124 if a.N1.offset == ~-1 then () else
125 for i = 0 to Array.length line - 1 do
126 N1.iteri (f i) line.(i)
134 type 'a t = 'a N2.t N1.t
137 let dummy2 = N2.create a in
141 let line = N1.find a i in
142 if line == a.N1.dummy then
143 let nline = N1.create line.N1.dummy in
150 let v = N1.find a i in
151 if v == a.N1.dummy then N2.dummy v
155 let dummy a = N2.dummy a.N1.dummy
157 let line = a.N1.line in
158 if a.N1.offset == ~-1 then () else
159 for i = 0 to Array.length line - 1 do
160 N2.iteri (f i) line.(i)
167 type 'a t = 'a N3.t N1.t
170 let dummy3 = N3.create a in
173 let add a i j k l v =
174 let line = N1.find a i in
175 if line == N1.dummy a then
176 let nline = N3.create (N3.dummy line) in
183 let v = N1.find a i in
184 if v == (N1.dummy a) then N3.dummy v
188 let dummy a = N3.dummy (N1.dummy a)
190 N1.iteri (fun i v _ ->
191 N3.iteri (fun j k l v2 b -> f i j k l v2 b) v ) a
197 type 'a t = 'a N4.t N1.t
200 let dummy4 = N4.create a in
203 let add a i j k l m v =
204 let line = N1.find a i in
205 if line == (N1.dummy a) then
206 let nline = N4.create (N4.dummy line) in
208 N4.add nline j k l m v
210 N4.add line j k l m v
212 let find a i j k l m =
213 let v = N1.find a i in
214 if v == (N1.dummy a) then N4.dummy v
215 else N4.find v j k l m
218 let dummy a = N4.dummy (N1.dummy a)
220 N1.iteri (fun i v _ ->
221 N4.iteri (fun j k l m v2 b -> f i j k l m v2 b) v
227 type 'a t = 'a N5.t N1.t
230 let dummy5 = N5.create a in
233 let add a i j k l m n v =
234 let line = N1.find a i in
235 if line == N1.dummy a then
236 let nline = N5.create (N5.dummy line) in
238 N5.add nline j k l m n v
240 N5.add line j k l m n v
242 let find a i j k l m n =
243 let v = N1.find a i in
244 if v == N1.dummy a then N5.dummy v
245 else N5.find v j k l m n
248 let dummy a = N5.dummy (N1.dummy a)
250 N1.iteri (fun i v _ ->
251 N5.iteri (fun j k l m n v2 b -> f i j k l m n v2 b) v