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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
structure Dynarray: DYNARRAY = struct
type 'a t = (int * 'a option Array.array) ref
fun create n =
ref (0, Array.array (n, NONE))
fun create0 () = create 10
fun length dynarr =
let
val (len, _) = !dynarr
in
len
end
fun push dynarr v =
let
val (len, arr) = !dynarr
in
case Int.compare (len, Array.length arr) of
EQUAL =>
let
val arr2 = Array.array (len * 2 + 1, NONE)
in
Array.copy { src = arr, dst = arr2, di = 0 };
dynarr := (len, arr2);
push dynarr v
end
| LESS => (
Array.update (arr, len, SOME v);
dynarr := (len + 1, arr)
)
| GREATER => raise Unreachable
end
fun pushAndGetId dynarr v =
let
val (len, _ ) = !dynarr
val () = push dynarr v
in
len
end
fun get dynarr n =
let
val (len, arr) = !dynarr
in
if n >= len then
raise Subscript
else
valOf $ Array.sub (arr, n)
end
fun set dynarr n v =
let
val (len, arr) = !dynarr
in
if n >= len then
raise Subscript
else
Array.update (arr, n, SOME v)
end
fun reset dynarr =
let
val (_, arr) = !dynarr
in
dynarr := (0, arr)
end
fun toVec dynarr =
let
val (len, arr) = !dynarr
fun arr2list idx acc =
if idx = len then
rev acc
else
arr2list (idx + 1) (valOf (Array.sub (arr, idx)) :: acc)
val l = arr2list 0 []
in
Vector.fromList l
end
fun appi f dynarr =
let
val (len, arr) = !dynarr
fun loop idx =
if idx = len then
()
else (
f (idx, valOf $ Array.sub (arr, idx));
loop (idx + 1)
)
in
loop 0
end
fun last dynarr =
let
val len = length dynarr
in
get dynarr (len - 1)
end
fun pop dynarr =
let
val v = last dynarr
val (len, arr) = !dynarr
in
dynarr := (len - 1, arr);
v
end
fun update dynarr f id =
let
val v = get dynarr id
val v = f v
in
set dynarr id v
end
fun copy (dynarr: 'a t) (f: 'a -> 'b): 'b t =
let
val dynarr2 = create (length dynarr)
fun loop idx =
if idx = length dynarr then
()
else
(push dynarr2 (f $ get dynarr idx); loop (idx + 1))
in
loop 0;
dynarr2
end
end
|
