Linux GNU 11.4.0 Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 80.1% 137 / 0 / 171
Functions: -% 0 / 1 / 1
Branches: 69.3% 176 / 0 / 254
OMCompiler/Compiler/Util/UnorderedSet.mo
Line Branch Exec Source
1 /*
2 * This file is part of OpenModelica.
3 *
4 * Copyright (c) 1998-2026, Open Source Modelica Consortium (OSMC),
5 * c/o Linköpings universitet, Department of Computer and Information Science,
6 * SE-58183 Linköping, Sweden.
7 *
8 * All rights reserved.
9 *
10 * THIS PROGRAM IS PROVIDED UNDER THE TERMS OF AGPL VERSION 3 LICENSE OR
11 * THIS OSMC PUBLIC LICENSE (OSMC-PL) VERSION 1.8.
12 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS PROGRAM CONSTITUTES
13 * RECIPIENT'S ACCEPTANCE OF THE OSMC PUBLIC LICENSE OR THE GNU AGPL
14 * VERSION 3, ACCORDING TO RECIPIENTS CHOICE.
15 *
16 * The OpenModelica software and the OSMC (Open Source Modelica Consortium)
17 * Public License (OSMC-PL) are obtained from OSMC, either from the above
18 * address, from the URLs:
19 * http://www.openmodelica.org or
20 * https://github.com/OpenModelica/ or
21 * http://www.ida.liu.se/projects/OpenModelica,
22 * and in the OpenModelica distribution.
23 *
24 * GNU AGPL version 3 is obtained from:
25 * https://www.gnu.org/licenses/licenses.html#GPL
26 *
27 * This program is distributed WITHOUT ANY WARRANTY; without
28 * even the implied warranty of MERCHANTABILITY or FITNESS
29 * FOR A PARTICULAR PURPOSE, EXCEPT AS EXPRESSLY SET FORTH
30 * IN THE BY RECIPIENT SELECTED SUBSIDIARY LICENSE CONDITIONS OF OSMC-PL.
31 *
32 * See the full OSMC Public License conditions for more details.
33 *
34 */
35
36 encapsulated uniontype UnorderedSet<T>
37 "An implementation of a generic unordered set, a.k.a. hash set.
38
39 This implementation uses separate chaining and automatically rehashes the set
40 when the load factor becomes too large to keep the performance up."
41
42 import Mutable;
43
44 protected
45 import Array;
46 import List;
47 import MetaModelica.Dangerous.*;
48 import Util;
49
50 public
51 partial function Hash
52 input T key;
53 output Integer hash;
54 end Hash;
55
56 partial function KeyEq
57 input T key1;
58 input T key2;
59 output Boolean equal;
60 end KeyEq;
61
62 record UNORDERED_SET
63 Mutable<array<list<T>>> buckets;
64 Mutable<Integer> size;
65 Hash hashFn;
66 KeyEq eqFn;
67 end UNORDERED_SET;
68
69 function new<T>
70 "Creates a new set given a hash function, equality function, and optional
71 desired bucket count. An approriate bucket count is
72 Util.nextPrime(number of elements that will be added), but starting with a
73 low bucket count is also fine if the number of elements is unknown since the
74 set rehashes as needed."
75 input Hash hash;
76 input KeyEq keyEq;
77 input Integer bucketCount = 13;
78 output UnorderedSet<T> set;
79 protected
80 Mutable<array<list<T>>> buckets;
81 algorithm
82 448986 buckets := Mutable.create(arrayCreate(bucketCount, {}));
83 448986 set := UNORDERED_SET(buckets, Mutable.create(0), hash, keyEq);
84 end new;
85
86 function fromList
87 input list<T> elements;
88 input Hash hash;
89 input KeyEq keyEq;
90 output UnorderedSet<T> set;
91 algorithm
92 192462 set := new<T>(hash, keyEq, Util.nextPrime(listLength(elements)));
93
94
2/2
✓ Branch 0 taken 712902 times.
✓ Branch 1 taken 192462 times.
 905364 for e in elements loop
95 712902 add(e, set);
96 end for;
97 end fromList;
98
99 function copy
100 "Returns a copy of the given set."
101 input UnorderedSet<T> set;
102 output UnorderedSet<T> outSet;
103 algorithm
104 13494 outSet := UNORDERED_SET(
105 Mutable.create(arrayCopy(Mutable.access(set.buckets))),
106 Mutable.create(Mutable.access(set.size)),
107 set.hashFn,
108 set.eqFn
109 );
110 end copy;
111
112 function add
113 "Adds a key to the set unless the key already exists in the set, in which
114 case nothing is done. Might trigger a rehash."
115 input T key;
116 input UnorderedSet<T> set;
117 output Boolean added;
118 protected
119 Integer hash;
120 Option<T> okey;
121 algorithm
122 1299083 (okey, hash) := find(key, set);
123
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1299083 times.
 1299083 added := isNone(okey);
124
2/2
✓ Branch 0 taken 294617 times.
✓ Branch 1 taken 1004466 times.
 1299083 if added then
125 1004466 addKey(key, hash, set);
126 end if;
127 end add;
128
129 function addNew
130 "Adds a key to the set without checking if it already exists. Faster than
131 add since it doesn't need to check if the key exists, but will lead to
132 duplicate keys if it actually does exist in the set already. Might trigger
133 a rehash."
134 input T key;
135 input UnorderedSet<T> set;
136 protected
137 Hash hashfn = set.hashFn;
138 Integer hash;
139 algorithm
140
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 46 times.
 92 hash := intMod(hashfn(key), arrayLength(Mutable.access(set.buckets)));
141 46 addKey(key, hash, set);
142 end addNew;
143
144 function addUnique
145 "Adds a key to the set, but fails if the key already exists.
146 Might trigger a rehash."
147 input T key;
148 input UnorderedSet<T> set;
149 protected
150 Integer hash;
151 algorithm
152
2/4
✗ Branch 1 not taken.
✓ Branch 2 taken 2560 times.
✓ Branch 3 taken 2560 times.
✗ Branch 4 not taken.
 2560 (NONE(), hash) := find(key, set);
153 2560 addKey(key, hash, set);
154 end addUnique;
155
156 function remove
157 "Removes a key from the set. Returns true if the key existed in the set and
158 was removed, or false if the key did not exist in the set.
159
160 Will not trigger a rehash, so rehash must be called manually if shrinking
161 the set is desirable (probably not a good idea unless the load factor is
162 very low, i.e. less than 0.25 or so)."
163 input T key;
164 input UnorderedSet<T> set;
165 output Boolean removed;
166 protected
167 array<list<T>> buckets = Mutable.access(set.buckets);
168 Hash hashfn = set.hashFn;
169 KeyEq eqfn = set.eqFn;
170 Integer hash;
171 list<T> bucket;
172 Option<T> okey;
173 algorithm
174
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 34341 times.
 34341 hash := intMod(hashfn(key), arrayLength(buckets));
175 34341 bucket := arrayGet(buckets, hash + 1);
176
177 34341 (bucket, okey) := List.deleteMemberOnTrue(key, bucket, eqfn);
178
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 34341 times.
✓ Branch 2 taken 262 times.
✓ Branch 3 taken 34079 times.
 34341 removed := isSome(okey);
179
180 if removed then
181 arrayUpdateNoBoundsChecking(buckets, hash + 1, bucket);
182 262 Mutable.update(set.size, Mutable.access(set.size) - 1);
183 end if;
184 end remove;
185
186 function get
187 "Returns SOME(key) if the key exists in the set, otherwise NONE()."
188 input T key;
189 input UnorderedSet<T> set;
190 output Option<T> outKey;
191 algorithm
192 30 outKey := find(key, set);
193 end get;
194
195 function getOrFail
196 "Returns a key if it exists in the set, otherwise fails."
197 input T key;
198 input UnorderedSet<T> set;
199 output T outKey;
200 protected
201 Option<T> okey;
202 algorithm
203 ✗ okey := find(key, set);
204 ✗ SOME(outKey) := okey;
205 end getOrFail;
206
207 function contains
208 "Returns whether the given key exists in the set or not."
209 input T key;
210 input UnorderedSet<T> set;
211 output Boolean res;
212 algorithm
213
3/4
✗ Branch 1 not taken.
✓ Branch 2 taken 5726227 times.
✓ Branch 5 taken 664476 times.
✓ Branch 6 taken 5061751 times.
 5726227 res := isSome(find(key, set));
214 end contains;
215
216 function first
217 "Returns the first element in the set, or fails if the set is empty.
218 Since the set is unordered there isn't really any 'first' element though,
219 it will just return the first element in the first non-empty bucket."
220 input UnorderedSet<T> set;
221 output T val;
222 algorithm
223
1/2
✓ Branch 2 taken 11861 times.
✗ Branch 3 not taken.
 13701 for b in Mutable.access(set.buckets) loop
224
2/2
✓ Branch 0 taken 1840 times.
✓ Branch 1 taken 10021 times.
 11861 if not listEmpty(b) then
225 1840 val := listHead(b);
226 1840 return;
227 end if;
228 end for;
229
230 ✗ fail();
231 end first;
232
233 function isEqual
234 "Returns true if the sets have the same size and contain the same elements,
235 otherwise false."
236 input UnorderedSet<T> set1;
237 input UnorderedSet<T> set2;
238 output Boolean equal = true;
239 algorithm
240
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 240 times.
 240 if Mutable.access(set1.size) <> Mutable.access(set2.size) then
241 equal := false;
242 ✗ return;
243 end if;
244
245
2/2
✓ Branch 2 taken 736 times.
✓ Branch 3 taken 240 times.
 1216 for b in Mutable.access(set1.buckets) loop
246
2/2
✓ Branch 0 taken 640 times.
✓ Branch 1 taken 736 times.
 1376 for k in b loop
247
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 640 times.
 640 if not contains(k, set2) then
248 equal := false;
249 ✗ return;
250 end if;
251 end for;
252 end for;
253 end isEqual;
254
255 function toList
256 "Returns the elements in the set as a list in no particular order."
257 input UnorderedSet<T> set;
258 output list<T> outList = {};
259 algorithm
260
2/2
✓ Branch 2 taken 1086616 times.
✓ Branch 3 taken 210287 times.
 1507190 for b in Mutable.access(set.buckets) loop
261
2/2
✓ Branch 1 taken 534782 times.
✓ Branch 2 taken 1086616 times.
 1621398 for k in b loop
262 outList := k :: outList;
263 end for;
264 end for;
265 end toList;
266
267 function toArray
268 "Returns the elements in the set as an array in no particular order."
269 input UnorderedSet<T> set;
270 output array<T> outArray;
271 protected
272 T dummy = dummy; // Fool the compiler into thinking dummy is initialized.
273 Integer i = 1;
274 algorithm
275 16467 outArray := arrayCreateNoInit(Mutable.access(set.size), dummy);
276
277
2/2
✓ Branch 2 taken 197142 times.
✓ Branch 3 taken 16467 times.
 230076 for b in Mutable.access(set.buckets) loop
278
2/2
✓ Branch 0 taken 26465 times.
✓ Branch 1 taken 197142 times.
 223607 for k in b loop
279 arrayUpdateNoBoundsChecking(outArray, i, k);
280 26465 i := i + 1;
281 end for;
282 end for;
283 end toArray;
284
285 function fold<FT>
286 "Folds over the keys in the set."
287 input UnorderedSet<T> set;
288 input FoldFn fn;
289 input FT startValue;
290 output FT result = startValue;
291
292 partial function FoldFn
293 input T key;
294 input output FT arg;
295 end FoldFn;
296 algorithm
297
2/2
✓ Branch 2 taken 225992 times.
✓ Branch 3 taken 17384 times.
 260760 for b in Mutable.access(set.buckets) loop
298
2/2
✓ Branch 0 taken 8518 times.
✓ Branch 1 taken 225992 times.
 234510 for k in b loop
299
2/2
✓ Branch 0 taken 4721 times.
✓ Branch 1 taken 3797 times.
 8518 result := fn(k, result);
300 end for;
301 end for;
302 end fold;
303
304 /*
305 function map<OT>
306 "Applies a function to all keys in the given set and returns a new set
307 with the new keys."
308 input UnorderedSet<T> set;
309 input MapFn fn;
310 input OutHash hashFn;
311 input OutKeyEq eqFn;
312 output UnorderedSet<OT> outSet;
313
314 partial function MapFn
315 input T key;
316 output OT outKey;
317 end MapFn;
318 partial function OutHash
319 input OT key;
320 input Integer mod;
321 output Integer hash;
322 end OutHash;
323 partial function OutKeyEq
324 input OT key1;
325 input OT key2;
326 output Boolean equal;
327 end OutKeyEq;
328 algorithm
329 outSet := new<OT>(hashFn, eqFn, Util.nextPrime(Mutable.access(set.size)));
330 for b in Mutable.access(set.buckets) loop
331 for k in b loop
332 add(fn(k), outSet);
333 end for;
334 end for;
335 end map;
336 */
337
338 function selfMap
339 "Applies a self-mapping function to all keys in the given set and returns a new set
340 with the new keys of same type as input set."
341 input UnorderedSet<T> set;
342 input MapFn fn;
343 output UnorderedSet<T> outSet = new<T>(set.hashFn, set.eqFn);
344
345 partial function MapFn
346 input output T key;
347 end MapFn;
348 algorithm
349
2/2
✓ Branch 2 taken 1807 times.
✓ Branch 3 taken 139 times.
 2085 for b in Mutable.access(set.buckets) loop
350
2/2
✓ Branch 0 taken 138 times.
✓ Branch 1 taken 1807 times.
 1945 for k in b loop
351
1/2
✓ Branch 0 taken 138 times.
✗ Branch 1 not taken.
 138 add(fn(k), outSet);
352 end for;
353 end for;
354 end selfMap;
355
356 function apply
357 "Applies function fn to all elements in set.
358 fn is expected to have side effects."
359 input UnorderedSet<T> set;
360 input ApplyFn fn;
361
362 partial function ApplyFn
363 input T key;
364 end ApplyFn;
365 algorithm
366 ✗ for b in Mutable.access(set.buckets) loop
367 ✗ for k in b loop
368 ✗ fn(k);
369 end for;
370 end for;
371 end apply;
372
373 function all
374 "Returns true if the given function returns true for all elements in the set,
375 otherwise false."
376 input UnorderedSet<T> set;
377 input PredFn fn;
378 output Boolean res;
379
380 partial function PredFn
381 input T key;
382 output Boolean res;
383 end PredFn;
384 algorithm
385
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3359 times.
 3359 if isEmpty(set) then
386 res := true;
387 ✗ return;
388 end if;
389
390
2/2
✓ Branch 2 taken 28523 times.
✓ Branch 3 taken 3283 times.
 35165 for b in Mutable.access(set.buckets) loop
391
2/2
✓ Branch 0 taken 5745 times.
✓ Branch 1 taken 28447 times.
 34192 for k in b loop
392
3/4
✓ Branch 0 taken 5745 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 76 times.
✓ Branch 5 taken 5669 times.
 5745 if not fn(k) then
393 res := false;
394 76 return;
395 end if;
396 end for;
397 end for;
398
399 res := true;
400 end all;
401
402 function any
403 "Returns true if the given function returns true for any elements in the set,
404 otherwise false."
405 input UnorderedSet<T> set;
406 input PredFn fn;
407 output Boolean res;
408
409 partial function PredFn
410 input T key;
411 output Boolean res;
412 end PredFn;
413 algorithm
414
2/2
✓ Branch 1 taken 127 times.
✓ Branch 2 taken 187 times.
 314 if isEmpty(set) then
415 res := false;
416 127 return;
417 end if;
418
419
2/2
✓ Branch 2 taken 1697 times.
✓ Branch 3 taken 7 times.
 1891 for b in Mutable.access(set.buckets) loop
420
2/2
✓ Branch 0 taken 187 times.
✓ Branch 1 taken 1517 times.
 1704 for k in b loop
421
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 187 times.
✓ Branch 4 taken 180 times.
✓ Branch 5 taken 7 times.
 187 if fn(k) then
422 res := true;
423 180 return;
424 end if;
425 end for;
426 end for;
427
428 res := false;
429 end any;
430
431 function none
432 "Returns true if the given function returns true for none of the elements in
433 the set, otherwise false."
434 input UnorderedSet<T> set;
435 input PredFn fn;
436 output Boolean res;
437
438 partial function PredFn
439 input T key;
440 output Boolean res;
441 end PredFn;
442 algorithm
443 ✗ if isEmpty(set) then
444 res := true;
445 ✗ return;
446 end if;
447
448 ✗ for b in Mutable.access(set.buckets) loop
449 ✗ for k in b loop
450 ✗ if fn(k) then
451 res := false;
452 ✗ return;
453 end if;
454 end for;
455 end for;
456
457 res := true;
458 end none;
459
460 function filterOnFalse
461 "Returns new set containing elements for which fn returns false"
462 input UnorderedSet<T> set;
463 input PredFn fn;
464 output UnorderedSet<T> falseSet = new<T>(set.hashFn, set.eqFn);
465
466 partial function PredFn
467 input T key;
468 output Boolean res;
469 end PredFn;
470 algorithm
471
2/2
✓ Branch 2 taken 46202 times.
✓ Branch 3 taken 3554 times.
 53310 for b in Mutable.access(set.buckets) loop
472
2/2
✓ Branch 0 taken 575 times.
✓ Branch 1 taken 46202 times.
 46777 for k in b loop
473
2/4
✓ Branch 0 taken 575 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 575 times.
✗ Branch 5 not taken.
 575 if not fn(k) then
474 575 add(k, falseSet);
475 end if;
476 end for;
477 end for;
478 end filterOnFalse;
479
480 function splitOnTrue
481 "Splits a set into two subsets depending on predicate function."
482 input UnorderedSet<T> set;
483 input PredFn fn;
484 output UnorderedSet<T> trueSet = new<T>(set.hashFn, set.eqFn);
485 output UnorderedSet<T> falseSet = new<T>(set.hashFn, set.eqFn);
486
487 partial function PredFn
488 input T key;
489 output Boolean res;
490 end PredFn;
491 algorithm
492
2/2
✓ Branch 2 taken 46202 times.
✓ Branch 3 taken 3554 times.
 53310 for b in Mutable.access(set.buckets) loop
493
2/2
✓ Branch 0 taken 575 times.
✓ Branch 1 taken 46202 times.
 46777 for k in b loop
494
3/4
✓ Branch 0 taken 575 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 501 times.
✓ Branch 5 taken 74 times.
 1076 add(k, if fn(k) then trueSet else falseSet);
495 end for;
496 end for;
497 end splitOnTrue;
498
499 function size
500 "Returns the number of elements the set contains."
501 input UnorderedSet<T> set;
502 output Integer s = Mutable.access(set.size);
503 end size;
504
505 function isEmpty
506 "Returns whether the set is empty or not."
507 input UnorderedSet<T> set;
508 output Boolean empty = Mutable.access(set.size) == 0;
509 end isEmpty;
510
511 function bucketCount
512 "Returns the number of buckets used by the set."
513 input UnorderedSet<T> set;
514 output Integer count = arrayLength(Mutable.access(set.buckets));
515 end bucketCount;
516
517 function loadFactor
518 "Returns the load factor, defined as the number of entries divided by the
519 number of buckets."
520 input UnorderedSet<T> set;
521 output Real load = intReal(Mutable.access(set.size)) / bucketCount(set);
522 end loadFactor;
523
524 function rehash
525 "Changes the number of buckets to an appropriate number based on the number
526 of elements in the set and rehashes all the keys."
527 input UnorderedSet<T> set;
528 protected
529 array<list<T>> old_buckets = Mutable.access(set.buckets);
530 array<list<T>> new_buckets;
531 Integer bucket_count, hash;
532 Hash hashfn = set.hashFn;
533 algorithm
534 // Make a new bucket array.
535 3336 bucket_count := Util.nextPrime(Mutable.access(set.size) * 2);
536 3336 new_buckets := arrayCreate(bucket_count, {});
537
538 // Rehash all the keys in the old buckets and add them to the new.
539
2/2
✓ Branch 1 taken 110981 times.
✓ Branch 2 taken 3336 times.
 114317 for b in old_buckets loop
540
2/2
✓ Branch 0 taken 114317 times.
✓ Branch 1 taken 110981 times.
 225298 for k in b loop
541
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 114317 times.
 114317 hash := intMod(hashfn(k), bucket_count);
542 228634 arrayUpdate(new_buckets, hash + 1, k :: arrayGet(new_buckets, hash + 1));
543 end for;
544 end for;
545
546 // Replace the old bucket array with the new one.
547 3336 Mutable.update(set.buckets, new_buckets);
548 end rehash;
549
550 function toString
551 input UnorderedSet<T> set;
552 input StringFn stringFn;
553 input String delimiter = "\n";
554 output String str;
555
556 partial function StringFn
557 input T key;
558 output String str;
559 end StringFn;
560 algorithm
561
5/6
✓ Branch 1 taken 7248 times.
✓ Branch 2 taken 748 times.
✓ Branch 4 taken 7248 times.
✓ Branch 5 taken 748 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 7248 times.
 15992 str := stringDelimitList(list(stringFn(k) for k in toArray(set)), delimiter);
562 end toString;
563
564 function dump
565 "Prints the set to standard output using the given string function."
566 input UnorderedSet<T> set;
567 input StringFn stringFn;
568
569 partial function StringFn
570 input T key;
571 output String str;
572 end StringFn;
573 algorithm
574 ✗ print(toString(set, stringFn));
575 ✗ print("\n");
576 end dump;
577
578 function unique_list<T>
579 "Takes a list of elements and returns a list with duplicates removed, so that
580 each element in the new list is unique."
581 input list<T> inList;
582 input Hash hashFunc;
583 input KeyEq keyEqFunc;
584 output list<T> outList = if List.hasSeveralElements(inList) then toList(fromList(inList, hashFunc, keyEqFunc)) else inList;
585 end unique_list;
586
587 function union
588 "set1 U set2"
589 input UnorderedSet<T> set1;
590 input UnorderedSet<T> set2;
591 output UnorderedSet<T> set;
592 protected
593 Integer sz1, sz2, small_sz;
594 UnorderedSet<T> small_set;
595 algorithm
596 32757 sz1 := Mutable.access(set1.size);
597 32757 sz2 := Mutable.access(set2.size);
598
599
2/2
✓ Branch 0 taken 19038 times.
✓ Branch 1 taken 13719 times.
 32757 if sz1 > sz2 then
600 set := set1;
601 small_set := set2;
602 small_sz := sz2;
603 else
604 set := set2;
605 small_set := set1;
606 small_sz := sz1;
607 end if;
608
609
2/2
✓ Branch 0 taken 17545 times.
✓ Branch 1 taken 15212 times.
 32757 if small_sz > 0 then
610
2/2
✓ Branch 2 taken 30533 times.
✓ Branch 3 taken 15212 times.
 60957 for b in Mutable.access(small_set.buckets) loop
611
2/2
✓ Branch 0 taken 16241 times.
✓ Branch 1 taken 30533 times.
 46774 for k in b loop
612 16241 add(k, set);
613 end for;
614 end for;
615 end if;
616 end union;
617
618 function union_list
619 "set1 U set2 U set3 ... U setn
620 pass the hash and equality function if the list is empty"
621 input list<UnorderedSet<T>> set_lst;
622 input Hash hashFunc;
623 input KeyEq keyEqFunc;
624 output UnorderedSet<T> set;
625 protected
626 list<UnorderedSet<T>> rest;
627 algorithm
628
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 14646 times.
 14667 if listEmpty(set_lst) then
629 21 set := new<T>(hashFunc, keyEqFunc);
630 else
631 // determine the biggest set to make sure we always add to it
632 14646 (set, rest) := extractFromLst(set_lst, intGt);
633
2/2
✓ Branch 0 taken 15833 times.
✓ Branch 1 taken 14646 times.
 30479 for tmp in rest loop
634 15833 set := union(set, tmp);
635 end for;
636 end if;
637 end union_list;
638
639 function merge
640 "set1 U set2
641 like union, but always merges the second into the first set"
642 input output UnorderedSet<T> set1;
643 input UnorderedSet<T> set2;
644 algorithm
645
2/2
✓ Branch 1 taken 27 times.
✓ Branch 2 taken 59 times.
 86 if isEmpty(set2) then
646 27 return;
647 end if;
648
649
2/2
✓ Branch 2 taken 767 times.
✓ Branch 3 taken 59 times.
 885 for b in Mutable.access(set2.buckets) loop
650
2/2
✓ Branch 0 taken 59 times.
✓ Branch 1 taken 767 times.
 826 for k in b loop
651 59 add(k, set1);
652 end for;
653 end for;
654 end merge;
655
656 function intersection
657 "set1 n set2"
658 input UnorderedSet<T> set1;
659 input UnorderedSet<T> set2;
660 output UnorderedSet<T> set;
661 protected
662 UnorderedSet<T> set_small, set_big;
663 list<T> acc = {};
664 algorithm
665 ✗ if Mutable.access(set1.size) > Mutable.access(set2.size) then
666 set_small := set2;
667 set_big := set1;
668 else
669 set_small := set1;
670 set_big := set2;
671 end if;
672
673 ✗ if not isEmpty(set_small) then
674 ✗ for b in Mutable.access(set_small.buckets) loop
675 ✗ for k in b loop
676 ✗ if contains(k, set_big) then
677 acc := k :: acc;
678 end if;
679 end for;
680 end for;
681 end if;
682
683 ✗ set := fromList(acc, set1.hashFn, set1.eqFn);
684 end intersection;
685
686 function intersection_list
687 "set1 n set2 n set3 ... n setn
688 pass the hash and equality function to create an empty list"
689 input list<UnorderedSet<T>> set_lst;
690 input Hash hashFunc;
691 input KeyEq keyEqFunc;
692 output UnorderedSet<T> set;
693 protected
694 UnorderedSet<T> set_small;
695 list<UnorderedSet<T>> rest;
696 list<T> acc = {};
697 algorithm
698 ✗ if not listEmpty(set_lst) then
699 // determine the smallest set to make sure we traverse the fewest elements
700 ✗ (set_small, rest) := extractFromLst(set_lst, intLt);
701 ✗ for b in Mutable.access(set_small.buckets) loop
702 ✗ for k in b loop
703 ✗ if List.all(rest, function contains(key = k)) then
704 acc := k :: acc;
705 end if;
706 end for;
707 end for;
708 end if;
709 ✗ set := fromList(acc, hashFunc, keyEqFunc);
710 end intersection_list;
711
712 function difference_list
713 "lst1 / lst2, assuming unique lists"
714 input list<T> inList1;
715 input list<T> inList2;
716 input Hash hashFunc;
717 input KeyEq keyEqFunc;
718 output list<T> acc = {};
719 protected
720 UnorderedSet<T> set2;
721 list<T> lst1 = inList1, lst2 = inList2;
722 algorithm
723 // remove common start, since this seems to be very common
724
6/10
✓ Branch 0 taken 9899 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6969 times.
✓ Branch 3 taken 2930 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 6969 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 14 taken 1332 times.
✓ Branch 15 taken 5637 times.
 9899 while not (listEmpty(lst1) or listEmpty(lst2)) and keyEqFunc(listHead(lst1), listHead(lst2)) loop
725 1332 lst1 := listRest(lst1);
726 1332 lst2 := listRest(lst2);
727 end while;
728
729 // {} - B = {}
730 // A - {} = A
731
3/4
✓ Branch 0 taken 8567 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2930 times.
✓ Branch 3 taken 5637 times.
 8567 if listEmpty(lst1) or listEmpty(lst2) then
732 acc := lst1;
733 2930 return;
734 end if;
735
736 5637 set2 := fromList(lst2, hashFunc, keyEqFunc);
737
2/2
✓ Branch 0 taken 36100 times.
✓ Branch 1 taken 5637 times.
 41737 for k in lst1 loop
738
2/2
✓ Branch 1 taken 26389 times.
✓ Branch 2 taken 9711 times.
 36100 if not contains(k, set2) then
739 acc := k :: acc;
740 end if;
741 end for;
742 end difference_list;
743
744 function difference_list_set
745 "difference_list(inList1, inList2) with set2 = fromList(inList2) built by
746 the caller, for reducing several lists by the same inList2."
747 input list<T> inList1;
748 input list<T> inList2;
749 input UnorderedSet<T> set2;
750 output list<T> acc = {};
751 protected
752 list<T> lst1 = inList1, lst2 = inList2;
753 KeyEq eqFn = set2.eqFn;
754 algorithm
755
7/10
✓ Branch 0 taken 742 times.
✓ Branch 1 taken 149 times.
✓ Branch 2 taken 682 times.
✓ Branch 3 taken 60 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 682 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 14 taken 613 times.
✓ Branch 15 taken 69 times.
 891 while not (listEmpty(lst1) or listEmpty(lst2)) and eqFn(listHead(lst1), listHead(lst2)) loop
756 613 lst1 := listRest(lst1);
757 613 lst2 := listRest(lst2);
758 end while;
759
760
4/4
✓ Branch 0 taken 129 times.
✓ Branch 1 taken 149 times.
✓ Branch 2 taken 69 times.
✓ Branch 3 taken 60 times.
 278 if listEmpty(lst1) or listEmpty(lst2) then
761 acc := lst1;
762 209 return;
763 end if;
764
765
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 69 times.
 269 for k in lst1 loop
766
2/2
✓ Branch 1 taken 109 times.
✓ Branch 2 taken 91 times.
 200 if not contains(k, set2) then
767 acc := k :: acc;
768 end if;
769 end for;
770 end difference_list_set;
771
772 function equal_list
773 "Takes two lists and returns true if they contain the same elements.
774 Ignores duplicates."
775 input list<T> inList1;
776 input list<T> inList2;
777 input Hash hashFunc;
778 input KeyEq keyEqFunc;
779 output Boolean b = false;
780 protected
781 UnorderedSet<T> set1 = fromList(inList1, hashFunc, keyEqFunc);
782 UnorderedSet<T> set2 = fromList(inList2, hashFunc, keyEqFunc);
783 algorithm
784
1/2
✓ Branch 2 taken 70 times.
✗ Branch 3 not taken.
 70 if Mutable.access(set1.size) <> Mutable.access(set2.size) then
785 ✗ return;
786 end if;
787
788
2/2
✓ Branch 0 taken 1161 times.
✓ Branch 1 taken 56 times.
 1217 for k in inList1 loop
789
2/2
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 1147 times.
 1161 if not contains(k, set2) then
790 14 return;
791 end if;
792 end for;
793 b := true;
794 end equal_list;
795
796 function difference
797 "set1 / set2"
798 input UnorderedSet<T> set1;
799 input UnorderedSet<T> set2;
800 output UnorderedSet<T> set;
801 protected
802 list<T> acc = {};
803 algorithm
804
2/2
✓ Branch 1 taken 17 times.
✓ Branch 2 taken 109 times.
 126 if not isEmpty(set1) then
805
2/2
✓ Branch 2 taken 34 times.
✓ Branch 3 taken 17 times.
 68 for b in Mutable.access(set1.buckets) loop
806
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 34 times.
 61 for k in b loop
807
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 if not contains(k, set2) then
808 acc := k :: acc;
809 end if;
810 end for;
811 end for;
812 end if;
813
814 126 set := fromList(acc, set1.hashFn, set1.eqFn);
815 end difference;
816
817 function sym_difference
818 "set1 / set2 U set2 / set1"
819 input UnorderedSet<T> set1;
820 input UnorderedSet<T> set2;
821 output UnorderedSet<T> set;
822 protected
823 list<T> acc = {};
824 algorithm
825
2/2
✓ Branch 1 taken 140 times.
✓ Branch 2 taken 147 times.
 287 if not isEmpty(set1) then
826
2/2
✓ Branch 2 taken 280 times.
✓ Branch 3 taken 140 times.
 560 for b in Mutable.access(set1.buckets) loop
827
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 280 times.
 424 for k in b loop
828
2/2
✓ Branch 1 taken 94 times.
✓ Branch 2 taken 50 times.
 144 if not contains(k, set2) then
829 acc := k :: acc;
830 end if;
831 end for;
832 end for;
833 end if;
834
835
2/2
✓ Branch 1 taken 187 times.
✓ Branch 2 taken 100 times.
 287 if not isEmpty(set2) then
836
2/2
✓ Branch 2 taken 374 times.
✓ Branch 3 taken 187 times.
 748 for b in Mutable.access(set2.buckets) loop
837
2/2
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 374 times.
 590 for k in b loop
838
2/2
✓ Branch 1 taken 166 times.
✓ Branch 2 taken 50 times.
 216 if not contains(k, set1) then
839 acc := k :: acc;
840 end if;
841 end for;
842 end for;
843 end if;
844
845 287 set := fromList(acc, set1.hashFn, set1.eqFn);
846 end sym_difference;
847
848 function isDisjoint
849 input UnorderedSet<T> set1;
850 input UnorderedSet<T> set2;
851 output Boolean b = true;
852 protected
853 UnorderedSet<T> set_small, set_big;
854 algorithm
855
1/2
✓ Branch 2 taken 19 times.
✗ Branch 3 not taken.
 19 if Mutable.access(set1.size) > Mutable.access(set2.size) then
856 set_small := set2;
857 set_big := set1;
858 else
859 set_small := set1;
860 set_big := set2;
861 end if;
862
863
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 if not isEmpty(set_small) then
864 ✗ for buckets in Mutable.access(set_small.buckets) loop
865 ✗ for k in buckets loop
866 ✗ if contains(k, set_big) then
867 b := false;
868 ✗ return;
869 end if;
870 end for;
871 end for;
872 end if;
873 end isDisjoint;
874
875 protected
876 function find
877 "Tries to find a key in the set, returning the key as an option, and the
878 key's hash."
879 input T key;
880 input UnorderedSet<T> set;
881 output Option<T> outKey = NONE();
882 output Integer hash;
883 protected
884 Hash hashfn = set.hashFn;
885 KeyEq eqfn = set.eqFn;
886 array<list<T>> buckets = Mutable.access(set.buckets);
887 list<T> bucket;
888 algorithm
889
2/2
✓ Branch 0 taken 4644 times.
✓ Branch 1 taken 12749483 times.
 12754127 hash := intMod(hashfn(key), arrayLength(buckets));
890 12754127 bucket := arrayGet(buckets, hash + 1);
891
892
2/2
✓ Branch 0 taken 3435302 times.
✓ Branch 1 taken 11130553 times.
 14565855 for k in bucket loop
893
4/4
✓ Branch 0 taken 4178 times.
✓ Branch 1 taken 3431124 times.
✓ Branch 4 taken 1623574 times.
✓ Branch 5 taken 1811728 times.
 3435302 if eqfn(k, key) then
894 outKey := SOME(k);
895 1623574 break;
896 end if;
897 end for;
898 end find;
899
900 function addKey
901 "Adds a key to the set given its hash."
902 input T key;
903 input Integer hash;
904 input UnorderedSet<T> set;
905 protected
906 array<list<T>> buckets;
907 Integer h;
908 Hash hashfn;
909 algorithm
910
2/2
✓ Branch 1 taken 3336 times.
✓ Branch 2 taken 1003736 times.
 1007072 if loadFactor(set) > 1 then
911 // Rehash if the load factor is too high to keep performance up.
912 3336 rehash(set);
913 3336 hashfn := set.hashFn;
914 3336 buckets := Mutable.access(set.buckets);
915 // The bucket count has changed so we need to rehash the key we're going
916 // to add too.
917
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3336 times.
 3336 h := intMod(hashfn(key), arrayLength(buckets));
918 else
919 1003736 buckets := Mutable.access(set.buckets);
920 h := hash;
921 end if;
922
923 // Add the key to the bucket indicated by the hash.
924 2014144 arrayUpdate(buckets, h + 1, key :: arrayGet(buckets, h + 1));
925 // Update the size of the set.
926 1007072 Mutable.update(set.size, Mutable.access(set.size) + 1);
927 end addKey;
928
929 function extractFromLst
930 "extracts a set from a list with smallest or biggest size
931 (use with intGt or intLt)
932 Note: input lst cannot be empty or else this fails!"
933 input list<UnorderedSet<T>> lst;
934 input size_compare func;
935 output UnorderedSet<T> single;
936 output list<UnorderedSet<T>> rest = {};
937 protected
938 partial function size_compare
939 input Integer i1;
940 input Integer i2;
941 output Boolean b;
942 end size_compare;
943 Integer size;
944 list<UnorderedSet<T>> tmp_lst;
945 algorithm
946
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14646 times.
 14646 single :: tmp_lst := lst;
947 14646 size := Mutable.access(single.size);
948
2/2
✓ Branch 0 taken 15833 times.
✓ Branch 1 taken 14646 times.
 30479 for tmp in tmp_lst loop
949
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 15833 times.
✓ Branch 6 taken 2095 times.
✓ Branch 7 taken 13738 times.
 15833 if func(Mutable.access(tmp.size), size) then
950 2095 size := Mutable.access(tmp.size);
951 rest := single :: rest;
952 single := tmp;
953 else
954 rest := tmp :: rest;
955 end if;
956 end for;
957 end extractFromLst;
958
959 annotation(__OpenModelica_Interface="util");
960 end UnorderedSet;
961