- dummy : 'a }
-
- let create n a = { line = Array.create n a;
- dummy = a }
-
- let find c i =
- let line = c.line in
- let len = Array.length line in
- if i >= len then c.dummy else line.(i)
-
- let add c i v =
- let line = c.line in
- let len = Array.length line in
- if i >= len then c.line <- realloc line len (i*2+1) c.dummy;
- c.line.(i) <- v
+ dummy : 'a;
+ mutable offset : int;
+ }
+ let create n a = {
+ line = Array.create 0 a;
+ dummy = a;
+ offset = ~-1;
+
+ }
+
+
+ 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 + 1) <- v;
+ a.line <- narray
+ end
+
+ let find a i =
+ let offset = a.offset in
+ let len = Array.length a.line in
+ if i >= offset && i < offset + len then a.line.(i - offset)
+ else a.dummy