Linux GNU 11.4.0 Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 0.0% 0 / 0 / 98
Functions: -% 0 / 1 / 1
Branches: 0.0% 0 / 0 / 20
OMCompiler/Compiler/FFrontEnd/FVisit.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 package FVisit
37 " file: FVisit.mo
38 package: FVisit
39 description: Visitation info for nodes
40
41
42 "
43
44 // public imports
45 public
46 import FCore;
47 import FNode;
48
49 // protected imports
50 protected
51 import List;
52 import Error;
53
54 public
55 type Id = FCore.Id;
56 type Seq = FCore.Seq;
57 type Next = FCore.Next;
58 type Node = FCore.Node;
59 type Ref = FCore.Ref;
60 type Data = FCore.Data;
61 type Visit = FCore.Visit;
62 type VAvlTree = FCore.VAvlTree;
63 type Visited = FCore.Visited;
64 type AvlTree = FCore.VAvlTree;
65 type AvlKey = FCore.VAvlKey;
66 type AvlValue = FCore.VAvlValue;
67 type AvlTreeValue = FCore.VAvlTreeValue;
68
69 constant Visited emptyVisited = FCore.V(FCore.emptyVAvlTree, FCore.firstId);
70
71 public function new
72 "make a new visited tree"
73 output Visited visited;
74 algorithm
75 visited := emptyVisited;
76 end new;
77
78 public function reset
79 "reset visited information"
80 input Visited inVisited;
81 output Visited visited;
82 algorithm
83 ✗ visited := new();
84 end reset;
85
86 public function next
87 input Visited inVisited;
88 output Visited outVisited;
89 output Next next;
90 protected
91 VAvlTree v;
92 Next n;
93 algorithm
94 ✗ FCore.V(v, n) := inVisited;
95 next := n;
96 ✗ n := FCore.next(n);
97 ✗ outVisited := FCore.V(v, n);
98 end next;
99
100 public function visited
101 "@autor: adrpo
102 check if a node was visited"
103 input Visited inVisited;
104 input Ref inRef;
105 output Boolean b;
106 algorithm
107 b := matchcontinue inVisited
108 local
109 AvlTree a;
110 Id id;
111
112 // there
113 case FCore.V(tree = a)
114 algorithm
115 ✗ FNode.id(FNode.fromRef(inRef));
116 ✗ avlTreeGet(a, FNode.id(FNode.fromRef(inRef)));
117 then
118 true;
119
120 // not there
121 else false;
122 end matchcontinue;
123 end visited;
124
125 public function seq
126 input Visit v;
127 output Seq s;
128 algorithm
129 ✗ FCore.VN(seq = s) := v;
130 end seq;
131
132 public function ref
133 input Visit v;
134 output Ref r;
135 algorithm
136 ✗ FCore.VN(ref = r) := v;
137 end ref;
138
139 public function tree
140 input Visited v;
141 output AvlTree a;
142 algorithm
143 ✗ FCore.V(tree = a) := v;
144 end tree;
145
146 public function visit
147 "@autor: adrpo
148 add the node to visited"
149 input Visited inVisited;
150 input Ref inRef;
151 output Visited outVisited;
152 algorithm
153 outVisited := matchcontinue inVisited
154 local
155 Seq s;
156 Next n;
157 AvlTree a;
158 Visit v;
159 Id id;
160
161 // already there, something's fishy!
162 case _
163 algorithm
164 ✗ FNode.id(FNode.fromRef(inRef));
165 ✗ v := avlTreeGet(tree(inVisited), FNode.id(FNode.fromRef(inRef)));
166 ✗ print("Already visited: " + FNode.toStr(FNode.fromRef(inRef)) + " seq: " + intString(seq(v)) + "\n");
167 ✗ then
168 fail();
169
170 case FCore.V(a, _)
171 algorithm
172 ✗ id := FNode.id(FNode.fromRef(inRef));
173 ✗ failure(avlTreeGet(tree(inVisited), id));
174 ✗ (FCore.V(next = n), s) := next(inVisited);
175 ✗ a := avlTreeAdd(a, id, FCore.VN(inRef, s));
176 ✗ outVisited := FCore.V(a, n);
177 then
178 outVisited;
179 end matchcontinue;
180 end visit;
181
182 // ************************ AVL Tree implementation ***************************
183 // ************************ AVL Tree implementation ***************************
184 // ************************ AVL Tree implementation ***************************
185 // ************************ AVL Tree implementation ***************************
186
187 public function keyCompare "compare 2 keys"
188 input AvlKey k1;
189 input AvlKey k2;
190 output Integer i;
191 algorithm
192 ✗ i := if intGt(k1, k2) then 1 else (if intLt(k1, k2) then -1 else 0);
193 end keyCompare;
194
195 public function keyStr "prints a key to a string"
196 input AvlKey k;
197 output String str;
198 algorithm
199 ✗ str := intString(k);
200 end keyStr;
201
202 public function valueStr "prints a Value to a string"
203 input AvlValue v;
204 output String str;
205 algorithm
206 str := match v
207 local
208 Integer seq;
209 ✗ case FCore.VN(seq = seq) then intString(seq);
210 end match;
211 end valueStr;
212
213 /* Generic Code below */
214 public function avlTreeNew "Return an empty tree"
215 output AvlTree tree;
216 annotation(__OpenModelica_EarlyInline = true);
217 algorithm
218 tree := FCore.emptyVAvlTree;
219 end avlTreeNew;
220
221 public function avlTreeAdd
222 "Help function to avlTreeAdd."
223 input AvlTree inAvlTree;
224 input AvlKey inKey;
225 input AvlValue inValue;
226 output AvlTree outAvlTree;
227 algorithm
228 outAvlTree := match (inAvlTree,inKey,inValue)
229 local
230 AvlKey key,rkey;
231 AvlValue value;
232
233 // empty tree
234 case (FCore.VAVLTREENODE(value = NONE(),left = NONE(),right = NONE()),key,value)
235 ✗ then FCore.VAVLTREENODE(SOME(FCore.VAVLTREEVALUE(key,value)),1,NONE(),NONE());
236
237 case (FCore.VAVLTREENODE(value = SOME(FCore.VAVLTREEVALUE(key=rkey))),key,value)
238 ✗ then balance(avlTreeAdd2(inAvlTree,keyCompare(key,rkey),key,value));
239
240 else
241 algorithm
242 ✗ Error.addMessage(Error.INTERNAL_ERROR, {"Env.avlTreeAdd failed"});
243 ✗ then fail();
244 end match;
245 end avlTreeAdd;
246
247 public function avlTreeAdd2
248 "Help function to avlTreeAdd."
249 input AvlTree inAvlTree;
250 input Integer keyComp "0=get value from current node, 1=search right subtree, -1=search left subtree";
251 input AvlKey inKey;
252 input AvlValue inValue;
253 output AvlTree outAvlTree;
254 algorithm
255 outAvlTree := match (inAvlTree,keyComp,inKey,inValue)
256 local
257 AvlKey key,rkey;
258 AvlValue value;
259 Option<AvlTree> left,right;
260 Integer h;
261 AvlTree t_1,t;
262 Option<AvlTreeValue> oval;
263
264 /*/ Don't allow replacing of nodes.
265 case (_, 0, key, _)
266 algorithm
267 info = getItemInfo(inValue);
268 Error.addSourceMessage(Error.DOUBLE_DECLARATION_OF_ELEMENTS,
269 {inKey}, info);
270 then
271 fail();*/
272
273 // replace this node
274 case (FCore.VAVLTREENODE(value = SOME(FCore.VAVLTREEVALUE(key=rkey)),height=h,left = left,right = right),0,_,value)
275 algorithm
276 // inactive for now, but we should check if we don't replace a class with a var or vice-versa!
277 // checkValueReplacementCompatible(rval, value);
278 ✗ then
279 FCore.VAVLTREENODE(SOME(FCore.VAVLTREEVALUE(rkey,value)),h,left,right);
280
281 // insert to right
282 case (FCore.VAVLTREENODE(value = oval,height=h,left = left,right = right),1,key,value)
283 algorithm
284 ✗ t := createEmptyAvlIfNone(right);
285 ✗ t_1 := avlTreeAdd(t, key, value);
286 ✗ then
287 FCore.VAVLTREENODE(oval,h,left,SOME(t_1));
288
289 // insert to left subtree
290 case (FCore.VAVLTREENODE(value = oval,height=h,left = left ,right = right),-1,key,value)
291 algorithm
292 ✗ t := createEmptyAvlIfNone(left);
293 ✗ t_1 := avlTreeAdd(t, key, value);
294 ✗ then
295 FCore.VAVLTREENODE(oval,h,SOME(t_1),right);
296
297 end match;
298 end avlTreeAdd2;
299
300 protected function createEmptyAvlIfNone "Help function to AvlTreeAdd2"
301 input Option<AvlTree> t;
302 output AvlTree outT;
303 algorithm
304 outT := match t
305 case NONE() then FCore.VAVLTREENODE(NONE(),0,NONE(),NONE());
306 case SOME(outT) then outT;
307 end match;
308 end createEmptyAvlIfNone;
309
310 protected function nodeValue "return the node value"
311 input AvlTree bt;
312 output AvlValue v;
313 algorithm
314 v := match bt
315 case FCore.VAVLTREENODE(value=SOME(FCore.VAVLTREEVALUE(_,v))) then v;
316 end match;
317 end nodeValue;
318
319 protected function balance "Balances a AvlTree"
320 input AvlTree inBt;
321 output AvlTree outBt;
322 algorithm
323 outBt := match inBt
324 local Integer d; AvlTree bt;
325 case bt
326 algorithm
327 ✗ d := differenceInHeight(bt);
328 ✗ bt := doBalance(d,bt);
329 then bt;
330 end match;
331 end balance;
332
333 protected function doBalance "perform balance if difference is > 1 or < -1"
334 input Integer difference;
335 input AvlTree inBt;
336 output AvlTree outBt;
337 algorithm
338 outBt := match (difference,inBt)
339 local AvlTree bt;
340 ✗ case(-1,bt) then computeHeight(bt);
341 ✗ case(0,bt) then computeHeight(bt);
342 ✗ case(1,bt) then computeHeight(bt);
343 /* d < -1 or d > 1 */
344 case(_,bt)
345 algorithm
346 ✗ bt := doBalance2(difference < 0,bt);
347 then bt;
348 end match;
349 end doBalance;
350
351 protected function doBalance2 "help function to doBalance"
352 input Boolean differenceIsNegative;
353 input AvlTree inBt;
354 output AvlTree outBt;
355 algorithm
356 outBt := match (differenceIsNegative,inBt)
357 local AvlTree bt;
358 case (true,bt)
359 algorithm
360 ✗ bt := doBalance3(bt);
361 ✗ bt := rotateLeft(bt);
362 then bt;
363 case (false,bt)
364 algorithm
365 ✗ bt := doBalance4(bt);
366 ✗ bt := rotateRight(bt);
367 then bt;
368 end match;
369 end doBalance2;
370
371 protected function doBalance3 "help function to doBalance2"
372 input AvlTree inBt;
373 output AvlTree outBt;
374 algorithm
375 outBt := matchcontinue inBt
376 local
377 AvlTree rr,bt;
378 case bt
379 algorithm
380 ✗ true := differenceInHeight(getOption(rightNode(bt))) > 0;
381 ✗ rr := rotateRight(getOption(rightNode(bt)));
382 ✗ bt := setRight(bt,SOME(rr));
383 then bt;
384 else inBt;
385 end matchcontinue;
386 end doBalance3;
387
388 protected function doBalance4 "help function to doBalance2"
389 input AvlTree inBt;
390 output AvlTree outBt;
391 algorithm
392 outBt := matchcontinue inBt
393 local
394 AvlTree rl,bt;
395 case bt
396 algorithm
397 ✗ true := differenceInHeight(getOption(leftNode(bt))) < 0;
398 ✗ rl := rotateLeft(getOption(leftNode(bt)));
399 ✗ bt := setLeft(bt,SOME(rl));
400 then bt;
401 else inBt;
402 end matchcontinue;
403 end doBalance4;
404
405 protected function setRight "set right treenode"
406 input AvlTree node;
407 input Option<AvlTree> right;
408 output AvlTree outNode;
409 algorithm
410 outNode := match node
411 local Option<AvlTreeValue> value;
412 Option<AvlTree> l;
413 Integer height;
414 ✗ case FCore.VAVLTREENODE(value,height,l,_) then FCore.VAVLTREENODE(value,height,l,right);
415 end match;
416 end setRight;
417
418 protected function setLeft "set left treenode"
419 input AvlTree node;
420 input Option<AvlTree> left;
421 output AvlTree outNode;
422 algorithm
423 outNode := match node
424 local Option<AvlTreeValue> value;
425 Option<AvlTree> r;
426 Integer height;
427 ✗ case FCore.VAVLTREENODE(value,height,_,r) then FCore.VAVLTREENODE(value,height,left,r);
428 end match;
429 end setLeft;
430
431 protected function leftNode "Retrieve the left subnode"
432 input AvlTree node;
433 output Option<AvlTree> subNode;
434 algorithm
435 subNode := match node
436 case FCore.VAVLTREENODE(left = subNode) then subNode;
437 end match;
438 end leftNode;
439
440 protected function rightNode "Retrieve the right subnode"
441 input AvlTree node;
442 output Option<AvlTree> subNode;
443 algorithm
444 subNode := match node
445 case FCore.VAVLTREENODE(right = subNode) then subNode;
446 end match;
447 end rightNode;
448
449 protected function exchangeLeft "help function to balance"
450 input AvlTree inNode;
451 input AvlTree inParent;
452 output AvlTree outParent "updated parent";
453 algorithm
454 outParent := match(inNode,inParent)
455 local
456 AvlTree bt,node,parent;
457
458 case(node,parent) algorithm
459 ✗ parent := setRight(parent,leftNode(node));
460 ✗ parent := balance(parent);
461 ✗ node := setLeft(node,SOME(parent));
462 ✗ bt := balance(node);
463 then bt;
464 end match;
465 end exchangeLeft;
466
467 protected function exchangeRight "help function to balance"
468 input AvlTree inNode;
469 input AvlTree inParent;
470 output AvlTree outParent "updated parent";
471 algorithm
472 outParent := match(inNode,inParent)
473 local AvlTree bt,node,parent;
474 case(node,parent) algorithm
475 ✗ parent := setLeft(parent,rightNode(node));
476 ✗ parent := balance(parent);
477 ✗ node := setRight(node,SOME(parent));
478 ✗ bt := balance(node);
479 then bt;
480 end match;
481 end exchangeRight;
482
483 protected function rotateLeft "help function to balance"
484 input AvlTree node;
485 output AvlTree outNode "updated node";
486 algorithm
487 ✗ outNode := exchangeLeft(getOption(rightNode(node)),node);
488 end rotateLeft;
489
490 protected function getOption "Retrieve the value of an option"
491 replaceable type T subtypeof Any;
492 input Option<T> opt;
493 output T val;
494 algorithm
495 val := match opt
496 case SOME(val) then val;
497 end match;
498 end getOption;
499
500 protected function rotateRight "help function to balance"
501 input AvlTree node;
502 output AvlTree outNode "updated node";
503 algorithm
504 ✗ outNode := exchangeRight(getOption(leftNode(node)),node);
505 end rotateRight;
506
507 protected function differenceInHeight "help function to balance, calculates the difference in height
508 between left and right child"
509 input AvlTree node;
510 output Integer diff;
511 algorithm
512 diff := match node
513 local
514 Integer lh,rh;
515 Option<AvlTree> l,r;
516 case FCore.VAVLTREENODE(left=l,right=r)
517 algorithm
518 ✗ lh := getHeight(l);
519 ✗ rh := getHeight(r);
520 ✗ then lh - rh;
521 end match;
522 end differenceInHeight;
523
524 public function avlTreeGet
525 "Get a value from the binary tree given a key."
526 input AvlTree inAvlTree;
527 input AvlKey inKey;
528 output AvlValue outValue;
529 algorithm
530 outValue := match (inAvlTree,inKey)
531 local
532 AvlKey rkey,key;
533 case (FCore.VAVLTREENODE(value = SOME(FCore.VAVLTREEVALUE(key=rkey))),key)
534 ✗ then avlTreeGet2(inAvlTree,keyCompare(key,rkey),key);
535 end match;
536 end avlTreeGet;
537
538 protected function avlTreeGet2
539 "Get a value from the binary tree given a key."
540 input AvlTree inAvlTree;
541 input Integer keyComp "0=get value from current node, 1=search right subtree, -1=search left subtree";
542 input AvlKey inKey;
543 output AvlValue outValue;
544 algorithm
545 outValue := match (inAvlTree,keyComp,inKey)
546 local
547 AvlKey key;
548 AvlValue rval;
549 AvlTree left,right;
550
551 // hash func Search to the right
552 case (FCore.VAVLTREENODE(value = SOME(FCore.VAVLTREEVALUE(value=rval))),0,_)
553 then rval;
554
555 // search to the right
556 case (FCore.VAVLTREENODE(right = SOME(right)),1,key)
557 ✗ then avlTreeGet(right, key);
558
559 // search to the left
560 case (FCore.VAVLTREENODE(left = SOME(left)),-1,key)
561 ✗ then avlTreeGet(left, key);
562 end match;
563 end avlTreeGet2;
564
565 protected function getOptionStr "Retrieve the string from a string option.
566 If NONE() return empty string."
567 input Option<Type_a> inTypeAOption;
568 input FuncTypeType_aToString inFuncTypeTypeAToString;
569 output String outString;
570 replaceable type Type_a subtypeof Any;
571 partial function FuncTypeType_aToString
572 input Type_a inTypeA;
573 output String outString;
574 end FuncTypeType_aToString;
575 algorithm
576 outString:=
577 match (inTypeAOption,inFuncTypeTypeAToString)
578 local
579 String str;
580 Type_a a;
581 FuncTypeType_aToString r;
582 case (SOME(a),r)
583 algorithm
584 ✗ str := r(a);
585 then
586 str;
587 case (NONE(),_) then "";
588 end match;
589 end getOptionStr;
590
591 protected function printAvlTreeStr "
592 Prints the avl tree to a string"
593 input AvlTree inAvlTree;
594 output String outString;
595 algorithm
596 outString:=
597 match inAvlTree
598 local
599 String s2,s3,res;
600 AvlValue rval;
601 Option<AvlTree> l,r;
602
603 case FCore.VAVLTREENODE(value = SOME(FCore.VAVLTREEVALUE(_,rval)),left = l,right = r)
604 algorithm
605 ✗ s2 := getOptionStr(l, printAvlTreeStr);
606 ✗ s3 := getOptionStr(r, printAvlTreeStr);
607 ✗ res := "\n" + valueStr(rval) + ", " + (if stringEq(s2, "") then "" else (s2 + ", ")) + s3;
608 then
609 res;
610 case FCore.VAVLTREENODE(value = NONE(),left = l,right = r)
611 algorithm
612 ✗ s2 := getOptionStr(l, printAvlTreeStr);
613 ✗ s3 := getOptionStr(r, printAvlTreeStr);
614 ✗ res := (if stringEq(s2, "") then "" else (s2 + ", ")) + s3;
615 then
616 res;
617 end match;
618 end printAvlTreeStr;
619
620 protected function computeHeight "compute the heigth of the AvlTree and store in the node info"
621 input AvlTree bt;
622 output AvlTree outBt;
623 algorithm
624 outBt := match bt
625 local
626 Option<AvlTree> l,r;
627 Option<AvlTreeValue> v;
628 Integer hl,hr,height;
629 case FCore.VAVLTREENODE(value=v as SOME(_),left=l,right=r)
630 algorithm
631 ✗ hl := getHeight(l);
632 ✗ hr := getHeight(r);
633 ✗ height := intMax(hl,hr) + 1;
634 ✗ then FCore.VAVLTREENODE(v,height,l,r);
635 end match;
636 end computeHeight;
637
638 protected function getHeight "Retrieve the height of a node"
639 input Option<AvlTree> bt;
640 output Integer height;
641 algorithm
642 height := match bt
643 case NONE() then 0;
644 case SOME(FCore.VAVLTREENODE(height = height)) then height;
645 end match;
646 end getHeight;
647
648 public function printAvlTreeStrPP
649 input AvlTree inTree;
650 output String outString;
651 algorithm
652 ✗ outString := printAvlTreeStrPP2(SOME(inTree), "");
653 end printAvlTreeStrPP;
654
655 protected function printAvlTreeStrPP2
656 input Option<AvlTree> inTree;
657 input String inIndent;
658 output String outString;
659 algorithm
660 outString := match inTree
661 local
662 AvlKey rkey;
663 Option<AvlTree> l, r;
664 String s1, s2, res, indent;
665
666 case NONE() then "";
667
668 case SOME(FCore.VAVLTREENODE(value = SOME(FCore.VAVLTREEVALUE(key = rkey)), left = l, right = r))
669 algorithm
670 ✗ indent := inIndent + " ";
671 ✗ s1 := printAvlTreeStrPP2(l, indent);
672 ✗ s2 := printAvlTreeStrPP2(r, indent);
673 ✗ res := "\n" + inIndent + keyStr(rkey) + s1 + s2;
674 then
675 res;
676
677 case SOME(FCore.VAVLTREENODE(value = NONE(), left = l, right = r))
678 algorithm
679 ✗ indent := inIndent + " ";
680 ✗ s1 := printAvlTreeStrPP2(l, indent);
681 ✗ s2 := printAvlTreeStrPP2(r, indent);
682 ✗ res := "\n" + s1 + s2;
683 then
684 res;
685 end match;
686 end printAvlTreeStrPP2;
687
688 public function avlTreeReplace
689 "Replaces the value of an already existing node in the tree with a new value."
690 input AvlTree inAvlTree;
691 input AvlKey inKey;
692 input AvlValue inValue;
693 output AvlTree outAvlTree;
694 algorithm
695 outAvlTree := match(inAvlTree, inKey, inValue)
696 local
697 AvlKey key, rkey;
698 AvlValue value;
699
700 case (FCore.VAVLTREENODE(value = SOME(FCore.VAVLTREEVALUE(key = rkey))), key, value)
701 ✗ then avlTreeReplace2(inAvlTree, keyCompare(key, rkey), key, value);
702
703 else
704 algorithm
705 ✗ Error.addMessage(Error.INTERNAL_ERROR, {getInstanceName() + " failed"});
706 ✗ then fail();
707
708 end match;
709 end avlTreeReplace;
710
711 protected function avlTreeReplace2
712 "Helper function to avlTreeReplace."
713 input AvlTree inAvlTree;
714 input Integer inKeyComp;
715 input AvlKey inKey;
716 input AvlValue inValue;
717 output AvlTree outAvlTree;
718 algorithm
719 outAvlTree := match(inAvlTree, inKeyComp, inKey, inValue)
720 local
721 AvlKey key;
722 AvlValue value;
723 Option<AvlTree> left, right;
724 Integer h;
725 AvlTree t;
726 Option<AvlTreeValue> oval;
727
728 // Replace this node.
729 case (FCore.VAVLTREENODE(value = SOME(_), height = h, left = left, right = right),
730 0, key, value)
731 ✗ then FCore.VAVLTREENODE(SOME(FCore.VAVLTREEVALUE(key, value)), h, left, right);
732
733 // Insert into right subtree.
734 case (FCore.VAVLTREENODE(value = oval, height = h, left = left, right = right),
735 1, key, value)
736 algorithm
737 ✗ t := createEmptyAvlIfNone(right);
738 ✗ t := avlTreeReplace(t, key, value);
739 ✗ then
740 FCore.VAVLTREENODE(oval, h, left, SOME(t));
741
742 // Insert into left subtree.
743 case (FCore.VAVLTREENODE(value = oval, height = h, left = left, right = right),
744 -1, key, value)
745 algorithm
746 ✗ t := createEmptyAvlIfNone(left);
747 ✗ t := avlTreeReplace(t, key, value);
748 ✗ then
749 FCore.VAVLTREENODE(oval, h, SOME(t), right);
750 end match;
751 end avlTreeReplace2;
752
753 public function getAvlTreeValues
754 input list<Option<AvlTree>> tree;
755 input list<AvlTreeValue> acc;
756 output list<AvlTreeValue> res;
757 algorithm
758 res := match tree
759 local
760 Option<AvlTreeValue> value;
761 Option<AvlTree> left,right;
762 list<Option<AvlTree>> rest;
763 case {} then acc;
764 case SOME(FCore.VAVLTREENODE(value=value,left=left,right=right))::rest
765 ✗ then getAvlTreeValues(left::right::rest,List.consOption(value,acc));
766 ✗ case NONE()::rest then getAvlTreeValues(rest,acc);
767 end match;
768 end getAvlTreeValues;
769
770 public function getAvlValue
771 input AvlTreeValue inValue;
772 output AvlValue res;
773 algorithm
774 res := match inValue
775 case FCore.VAVLTREEVALUE(value = res) then res;
776 end match;
777 end getAvlValue;
778
779 // ************************ END AVL Tree implementation ***************************
780 // ************************ END AVL Tree implementation ***************************
781 // ************************ END AVL Tree implementation ***************************
782 // ************************ END AVL Tree implementation ***************************
783
784 annotation(__OpenModelica_Interface="frontend");
785 end FVisit;
786