1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
type 'a t = {mutable cnt:int;
mutable arr: 'a array}
let make_empty () = {cnt=0; arr=[||]}
let singleton (e:'a) = {cnt=1; arr=Array.make 1 e}
let make (n:int) (e:'a) = {cnt=n; arr=Array.make n e}
let count (v:'a t): int = v.cnt
let is_empty (v:'s t): bool = (count v = 0)
let elem (v:'a t) (i:int): 'a =
assert (i<v.cnt);
v.arr.(i)
let first (v:'a t): 'a =
assert (0 < count v);
elem v 0
let last (v:'a t): 'a =
assert (0 < count v);
elem v (count v - 1)
let copy (s:'a t): 'a t =
{cnt = s.cnt; arr = Array.copy s.arr}
let put (v:'a t) (i:int) (e:'a): unit =
assert (i<v.cnt);
v.arr.(i) <- e
let push_rear (v:'a t) (elem:'a): unit =
let cnt = v.cnt
in
let _ =
if cnt = Array.length v.arr then
let narr =
Array.make (1+2*cnt) elem
in
Array.blit v.arr 0 narr 0 cnt;
v.arr <- narr
else
v.arr.(cnt) <- elem
in
assert (cnt < Array.length v.arr);
v.cnt <- cnt+1
let remove_n_last (v: 'a t) (n:int): unit =
assert (n <= count v);
v.cnt <- v.cnt - n
let remove_last (v:'a t): 'a =
assert (0 < count v);
let e = last v in
remove_n_last v 1; e
let keep (v: 'a t) (n:int): unit =
assert (n <= count v);
v.cnt <- n
let remove (s:'a t) (i:int): unit =
assert (i < count s);
s.arr <-
Array.init
(Array.length s.arr - 1)
(fun j ->
if j < i then s.arr.(j)
else s.arr.(j+1));
s.cnt <- s.cnt - 1