3 let realloc l old_size new_size dummy =
4 let l' = Array.create new_size dummy in
5 for i = 0 to (min old_size new_size) - 1 do
12 type 'a t = { mutable line : 'a array;
17 line = Array.create 0 a;
24 Format.fprintf fmt "{ offset=%i;\n dummy=_;line=%a \n}\n%!"
26 (Pretty.print_array ~sep:", " (fun fmt x ->
28 Format.fprintf fmt "%s" "D"
30 Format.fprintf fmt "%s" "E")) a.line
33 TRACE("twopass", 2, __ "Before add (%i): %a\n%!" i print a);
34 if a.offset == ~-1 then a.offset <- i;
35 let offset = a.offset in
36 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;
62 TRACE("twopass", 2, __ "After add (%i): %a\n%!" i print a)
65 let offset = a.offset in
66 let len = Array.length a.line in
67 if i >= offset && i < offset + len then a.line.(i - offset)
74 if a.offset == ~-1 then () else
75 for i = 0 to Array.length line - 1 do
77 f (i+a.offset) v (v==a.dummy)
87 type 'a t = 'a Lvl1.t Lvl1.t
89 let dummy1 = Lvl1.create 0 a in
90 { Lvl1.line = Array.create n dummy1;
97 TRACE("twopass", 2, __ "Adding %i %i\n%!" i j);
98 let line = Lvl1.find a i in
99 if line == a.Lvl1.dummy then
100 let nline = Lvl1.create 0 line.Lvl1.dummy in
101 TRACE("twopass", 2, __ "Reallocating\n%!");
108 let v = Lvl1.find a i in
109 if v == a.Lvl1.dummy then a.Lvl1.dummy.Lvl1.dummy
113 let dummy c = c.Lvl1.dummy.Lvl1.dummy
116 let line = a.Lvl1.line in
117 if a.Lvl1.offset == ~-1 then () else
118 for i = 0 to Array.length line - 1 do
119 Lvl1.iteri (f i) line.(i)
127 type 'a t = 'a Lvl2.t Lvl1.t
130 let dummy1 = Lvl2.create 512 a in
131 { Lvl1.line = Array.create n dummy1;
137 let line = Lvl1.find a i in
138 if line == a.Lvl1.dummy then
139 let nline = { line with Lvl1.offset = ~-1 } in
140 Lvl2.add nline j k v;
146 let v = Lvl1.find a i in
147 if v == a.Lvl1.dummy then Lvl2.dummy a.Lvl1.dummy
151 let dummy a = Lvl2.dummy a.Lvl1.dummy
153 let line = a.Lvl1.line in
154 if a.Lvl1.offset == ~-1 then () else
155 for i = 0 to Array.length line - 1 do
156 Lvl2.iteri (f i) line.(i)