-
Notifications
You must be signed in to change notification settings - Fork 298
/
ExpandableArray.mo
351 lines (320 loc) · 13.1 KB
/
ExpandableArray.mo
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
/*
* This file is part of OpenModelica.
*
* Copyright (c) 1998-2014, Open Source Modelica Consortium (OSMC),
* c/o Linköpings universitet, Department of Computer and Information Science,
* SE-58183 Linköping, Sweden.
*
* All rights reserved.
*
* THIS PROGRAM IS PROVIDED UNDER THE TERMS OF GPL VERSION 3 LICENSE OR
* THIS OSMC PUBLIC LICENSE (OSMC-PL) VERSION 1.2.
* ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS PROGRAM CONSTITUTES
* RECIPIENT'S ACCEPTANCE OF THE OSMC PUBLIC LICENSE OR THE GPL VERSION 3,
* ACCORDING TO RECIPIENTS CHOICE.
*
* The OpenModelica software and the Open Source Modelica
* Consortium (OSMC) Public License (OSMC-PL) are obtained
* from OSMC, either from the above address,
* from the URLs: http://www.ida.liu.se/projects/OpenModelica or
* http://www.openmodelica.org, and in the OpenModelica distribution.
* GNU version 3 is obtained from: http://www.gnu.org/copyleft/gpl.html.
*
* This program is distributed WITHOUT ANY WARRANTY; without
* even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE, EXCEPT AS EXPRESSLY SET FORTH
* IN THE BY RECIPIENT SELECTED SUBSIDIARY LICENSE CONDITIONS OF OSMC-PL.
*
* See the full OSMC Public License conditions for more details.
*
*/
encapsulated uniontype ExpandableArray<T> "Implementation of an expandable array
This provides a generic implementation of an expandable array. It basically
behaves like an ordinary array, which means all elements can get accessed via
index. When the array runs out of space, it get automatically resized. It is
also possible to delete an element from any position."
record EXPANDABLE_ARRAY
array<Integer> numberOfElements "This is an array of one Integer, to make numberOfElements mutable";
array<Integer> lastUsedIndex "This is an array of one Integer, to make lastUsedIndex mutable";
array<Integer> capacity "This is an array of one Integer, to make capacity mutable";
array<array<Option<T>>> data "This is an array of one array<Option<T>>, to make data mutable";
end EXPANDABLE_ARRAY;
protected
import Array;
import MetaModelica.Dangerous;
import Util;
public
impure function new "O(n)
Creates a new empty ExpandableArray with a certain capacity."
input Integer capacity;
input T dummy "This is needed to determine the type information, the actual value is not used";
output ExpandableArray<T> exarray;
algorithm
exarray := EXPANDABLE_ARRAY(arrayCreate(1, 0), arrayCreate(1, 0), arrayCreate(1, capacity), arrayCreate(1, arrayCreate(capacity, NONE())));
end new;
function clear "O(n)
Deletes all elements."
input output ExpandableArray<T> exarray;
protected
Integer n = Dangerous.arrayGetNoBoundsChecking(exarray.numberOfElements, 1);
Integer lastUsedIndex = Dangerous.arrayGetNoBoundsChecking(exarray.lastUsedIndex, 1);
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
algorithm
Dangerous.arrayUpdateNoBoundsChecking(exarray.numberOfElements, 1, 0);
Dangerous.arrayUpdateNoBoundsChecking(exarray.lastUsedIndex, 1, 0);
for i in 1:lastUsedIndex loop
if isSome(Dangerous.arrayGetNoBoundsChecking(data, i)) then
n := n-1;
Dangerous.arrayUpdateNoBoundsChecking(data, i, NONE());
if n == 0 then
return;
end if;
end if;
end for;
end clear;
function copy
input ExpandableArray<T> inExarray;
input T dummy "This is needed to determine the type information, the actual value is not used";
output ExpandableArray<T> outExarray;
algorithm
outExarray := new(inExarray.capacity[1], dummy);
outExarray.numberOfElements := arrayCopy(inExarray.numberOfElements);
outExarray.lastUsedIndex := arrayCopy(inExarray.lastUsedIndex);
outExarray.capacity := arrayCopy(inExarray.capacity);
outExarray.data := arrayCreate(1, arrayCopy(Dangerous.arrayGetNoBoundsChecking(inExarray.data, 1)));
end copy;
function occupied "O(1)
Returns if the element at the given index is occupied or not."
input Integer index;
input ExpandableArray<T> exarray;
output Boolean b;
protected
Integer lastUsedIndex = Dangerous.arrayGetNoBoundsChecking(exarray.lastUsedIndex, 1);
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
algorithm
b := index >= 1 and index <= lastUsedIndex and isSome(Dangerous.arrayGetNoBoundsChecking(data, index));
end occupied;
function get "O(1)
Returns the value of the element at the given index.
Fails if there is nothing assigned to the given index."
input Integer index;
input ExpandableArray<T> exarray;
output T value;
protected
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
algorithm
if occupied(index, exarray) then
SOME(value) := Dangerous.arrayGetNoBoundsChecking(data, index);
else
fail();
end if;
end get;
function expandToSize "O(n)
Expands an array to the given size, or does nothing if the array is already
large enough."
input Integer minCapacity;
input output ExpandableArray<T> exarray;
protected
Integer capacity = Dangerous.arrayGetNoBoundsChecking(exarray.capacity, 1);
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
algorithm
if minCapacity > capacity then
Dangerous.arrayUpdateNoBoundsChecking(exarray.capacity, 1, minCapacity);
data := Array.expandToSize(minCapacity, data, NONE());
Dangerous.arrayUpdateNoBoundsChecking(exarray.data, 1, data);
end if;
end expandToSize;
function set "if index <= capacity then O(1) otherwise O(n)
Sets the element at the given index to the given value.
Fails if the index is already used."
input Integer index;
input T value;
input output ExpandableArray<T> exarray;
protected
Integer numberOfElements = Dangerous.arrayGetNoBoundsChecking(exarray.numberOfElements, 1);
Integer lastUsedIndex = Dangerous.arrayGetNoBoundsChecking(exarray.lastUsedIndex, 1);
Integer capacity = Dangerous.arrayGetNoBoundsChecking(exarray.capacity, 1);
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
algorithm
if index > 0 and (index > capacity or isNone(Dangerous.arrayGetNoBoundsChecking(data, index))) then
if index > capacity then
capacity := max(capacity, 1);
while index > capacity loop
capacity := capacity * 2;
end while;
expandToSize(capacity, exarray);
data := Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
end if;
arrayUpdate(data, index, SOME(value));
Dangerous.arrayUpdateNoBoundsChecking(exarray.numberOfElements, 1, numberOfElements+1);
if index > lastUsedIndex then
Dangerous.arrayUpdateNoBoundsChecking(exarray.lastUsedIndex, 1, index);
end if;
else
fail();
end if;
end set;
function add "if index <= capacity then O(1) otherwise O(n)
Sets the first unused element to the given value."
input T value;
input output ExpandableArray<T> exarray;
output Integer index;
protected
Integer lastUsedIndex = Dangerous.arrayGetNoBoundsChecking(exarray.lastUsedIndex, 1);
algorithm
index := lastUsedIndex+1;
exarray := set(index, value, exarray);
end add;
function delete "O(1)
Deletes the value of the element at the given index.
Fails if there is no value stored at the given index."
input Integer index;
input output ExpandableArray<T> exarray;
protected
Integer numberOfElements = Dangerous.arrayGetNoBoundsChecking(exarray.numberOfElements, 1);
Integer lastUsedIndex = Dangerous.arrayGetNoBoundsChecking(exarray.lastUsedIndex, 1);
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
algorithm
if index >= 1 and index <= lastUsedIndex and isSome(Dangerous.arrayGetNoBoundsChecking(data, index)) then
arrayUpdate(data, index, NONE());
Dangerous.arrayUpdateNoBoundsChecking(exarray.numberOfElements, 1, numberOfElements-1);
if index == lastUsedIndex then
lastUsedIndex := lastUsedIndex-1;
while lastUsedIndex > 0 and isNone(Dangerous.arrayGetNoBoundsChecking(data, lastUsedIndex)) loop
lastUsedIndex := lastUsedIndex-1;
end while;
Dangerous.arrayUpdateNoBoundsChecking(exarray.lastUsedIndex, 1, lastUsedIndex);
end if;
else
fail();
end if;
end delete;
function update "O(1)
Overrides the value of the element at the given index.
Fails if there is no value stored at the given index."
input Integer index;
input T value;
input output ExpandableArray<T> exarray;
protected
Integer lastUsedIndex = Dangerous.arrayGetNoBoundsChecking(exarray.lastUsedIndex, 1);
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
algorithm
if index >= 1 and index <= lastUsedIndex and isSome(Dangerous.arrayGetNoBoundsChecking(data, index)) then
arrayUpdate(data, index, SOME(value));
else
fail();
end if;
end update;
function toList
input ExpandableArray<T> exarray;
output list<T> listT = {};
protected
Integer numberOfElements = Dangerous.arrayGetNoBoundsChecking(exarray.numberOfElements, 1);
Integer lastUsedIndex = Dangerous.arrayGetNoBoundsChecking(exarray.lastUsedIndex, 1);
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
T dummy;
algorithm
if numberOfElements == 0 then
listT := {};
elseif lastUsedIndex == 1 then
listT := {Util.getOption(data[1])};
else
listT := list(Util.getOption(data[i]) for i guard Util.isSome(data[i]) in 1:lastUsedIndex);
end if;
end toList;
function compress "O(n)
Reorders the elements in order to remove all the gaps.
Be careful: This changes the indices of the elements."
input output ExpandableArray<T> exarray;
protected
Integer numberOfElements = Dangerous.arrayGetNoBoundsChecking(exarray.numberOfElements, 1);
Integer lastUsedIndex = Dangerous.arrayGetNoBoundsChecking(exarray.lastUsedIndex, 1);
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
Integer i = 0;
algorithm
while lastUsedIndex > numberOfElements loop
i := i+1;
if isNone(Dangerous.arrayGetNoBoundsChecking(data, i)) then
Dangerous.arrayUpdateNoBoundsChecking(data, i, Dangerous.arrayGetNoBoundsChecking(data, lastUsedIndex));
Dangerous.arrayUpdateNoBoundsChecking(data, lastUsedIndex, NONE());
lastUsedIndex := lastUsedIndex-1;
while isNone(Dangerous.arrayGetNoBoundsChecking(data, lastUsedIndex)) loop
lastUsedIndex := lastUsedIndex-1;
end while;
end if;
end while;
Dangerous.arrayUpdateNoBoundsChecking(exarray.lastUsedIndex, 1, lastUsedIndex);
end compress;
function shrink "O(n)
Reduces the capacity of the ExpandableArray to the number of elements.
Be careful: This may change the indices of the elements."
input output ExpandableArray<T> exarray;
protected
Integer numberOfElements = Dangerous.arrayGetNoBoundsChecking(exarray.numberOfElements, 1);
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
array<Option<T>> newData;
algorithm
exarray := compress(exarray);
Dangerous.arrayUpdateNoBoundsChecking(exarray.capacity, 1, numberOfElements);
newData := Dangerous.arrayCreateNoInit(numberOfElements, Dangerous.arrayGetNoBoundsChecking(data, 1));
for i in 1:numberOfElements loop
Dangerous.arrayUpdateNoBoundsChecking(newData, i, Dangerous.arrayGetNoBoundsChecking(data, i));
end for;
Dangerous.arrayUpdateNoBoundsChecking(exarray.data, 1, newData);
end shrink;
function toString "O(n)
Dumps all elements with the given print function."
input ExpandableArray<T> exarray;
input String header;
input PrintFunction func;
input Boolean debug = true;
output String str;
partial function PrintFunction
input T t;
output String str;
end PrintFunction;
protected
Integer numberOfElements = Dangerous.arrayGetNoBoundsChecking(exarray.numberOfElements, 1);
Integer capacity = Dangerous.arrayGetNoBoundsChecking(exarray.capacity, 1);
T value;
array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
algorithm
if debug then
str := header + " (" + intString(numberOfElements) + "/" + intString(capacity) + ")\n";
else
str := header + " (" + intString(numberOfElements) + ")\n";
end if;
str := str + "========================================\n";
if numberOfElements == 0 then
str := str + "<empty>\n";
else
for i in 1:capacity loop
if isSome(Dangerous.arrayGetNoBoundsChecking(data, i)) then
SOME(value) := Dangerous.arrayGetNoBoundsChecking(data, i);
numberOfElements := numberOfElements-1;
str := str + intString(i) + ": " + func(value) + "\n";
if numberOfElements == 0 then
return;
end if;
end if;
end for;
end if;
end toString;
function getNumberOfElements
input ExpandableArray<T> exarray;
output Integer numberOfElements = Dangerous.arrayGetNoBoundsChecking(exarray.numberOfElements, 1);
end getNumberOfElements;
function getLastUsedIndex
input ExpandableArray<T> exarray;
output Integer lastUsedIndex = Dangerous.arrayGetNoBoundsChecking(exarray.lastUsedIndex, 1);
end getLastUsedIndex;
function getCapacity
input ExpandableArray<T> exarray;
output Integer capacity = Dangerous.arrayGetNoBoundsChecking(exarray.capacity, 1);
end getCapacity;
function getData
input ExpandableArray<T> exarray;
output array<Option<T>> data = Dangerous.arrayGetNoBoundsChecking(exarray.data, 1);
end getData;
annotation(__OpenModelica_Interface="util");
end ExpandableArray;