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 / 160
Functions: -% 0 / 1 / 1
Branches: 0.0% 0 / 0 / 76
OMCompiler/Compiler/Util/AvlTree.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 AvlTree
37 " file: AvlTree.mo
38 package: AvlTree
39 description: A MetaModelica AvlTree implementation
40
41 RCS: $Id: Tree.mo 9152 2011-05-28 08:08:28Z adrpo $
42
43 @author: adrpo
44
45 A generic AvlTree with type variables for Key and Val."
46
47 public
48
49 final type Key = polymorphic<Any>;
50 final type Val = polymorphic<Any>;
51
52 partial function FuncTypeKeyToStr<Key>
53 input Key key;
54 output String outString;
55 end FuncTypeKeyToStr;
56
57 partial function FuncTypeValToStr<Val>
58 input Val val;
59 output String outString;
60 end FuncTypeValToStr;
61
62 partial function FuncTypeItemUpdateCheck<Key,Val> "function to print an error on duplicate items"
63 input Item<Key,Val> inItemNew "the new item";
64 input Item<Key,Val> inItemOld "the old item in the tree";
65 output Boolean updateAllowed "returns true, the update is performed, false no update, fail, the update will fail";
66 end FuncTypeItemUpdateCheck;
67
68 partial function FuncTypeKeyCompare<Key> "function to compare keys"
69 input Key inKey1 "the new key";
70 input Key inKey2 "the old key from the tree";
71 output Integer order "return -1,0,1 for less than, equal and greater than keys";
72 end FuncTypeKeyCompare;
73
74 uniontype Tree<Key,Val> "a tree is a node and two optional printing functions"
75 record TREE "a tree is a node and two optional printing functions"
76 Node<Key,Val> root;
77 FuncTypeKeyCompare keyCompareFunc "function to compare keys, should return -1, 0, 1 ONLY!";
78 Option<FuncTypeKeyToStr> keyStrFuncOpt "optional function for printing Key";
79 Option<FuncTypeValToStr> valStrFuncOpt "optional function for printing Val";
80 Option<FuncTypeItemUpdateCheck> updateCheckFuncOpt
81 "optional function for reporting error on an update of the same item
82 if this function is NONE() then updates of items with the same key is allowed!
83 this function gets the new item and the old item for easy reporting,
84 and should return:
85 - true if update is allowed
86 - false if update should not be done
87 - should print an error message and fail if it wants to fail the update";
88 String name "a name for this tree so you know which one it is if you have more";
89 end TREE;
90 end Tree;
91
92 uniontype Node<Key,Val>
93 "The binary tree data structure"
94 record NODE
95 Item<Key,Val> item "Val";
96 Integer height "height of tree, used for balancing";
97 Node<Key,Val> left "left subtree";
98 Node<Key,Val> right "right subtree";
99 end NODE;
100
101 record NO_NODE "no node, empty tree"
102 end NO_NODE;
103 end Node;
104
105 public uniontype Item<Key,Val>
106 "Each node in the binary tree can have an item associated with it."
107 record ITEM
108 Key key "Key";
109 Val val "Val";
110 end ITEM;
111
112 record NO_ITEM "no item"
113 end NO_ITEM;
114 end Item;
115
116 protected import Error;
117
118 public function name
119 "return the name of the tree"
120 input Tree<Key,Val> tree;
121 output String name;
122 algorithm
123 ✗ TREE(name = name) := tree;
124 end name;
125
126 public function create
127 "Return an empty tree with the given printing functions attached"
128 input String name "a name for this tree so you know which one it is if you have more";
129 input FuncTypeKeyCompare inKeyCompareFunc;
130 input Option<FuncTypeKeyToStr> inKeyStrFuncOpt;
131 input Option<FuncTypeValToStr> inValStrFuncOpt;
132 input Option<FuncTypeItemUpdateCheck> inUpdateCheckFuncOpt;
133 output Tree<Key,Val> tree;
134 algorithm
135 ✗ tree := TREE(NODE(NO_ITEM(), 0, NO_NODE(), NO_NODE()), inKeyCompareFunc, inKeyStrFuncOpt, inValStrFuncOpt, inUpdateCheckFuncOpt, name);
136 end create;
137
138 public function hasPrintingFunctions
139 "returns true if you have set printing functions"
140 input Tree<Key,Val> tree;
141 output Boolean hasPrinting;
142 protected
143 Option<FuncTypeKeyToStr> kf;
144 Option<FuncTypeValToStr> vf;
145 algorithm
146 ✗ TREE(keyStrFuncOpt = kf, valStrFuncOpt = vf) := tree;
147 ✗ hasPrinting := boolNot(boolOr(valueEq(NONE(), kf), valueEq(NONE(), vf)));
148 end hasPrintingFunctions;
149
150 public function hasUpdateCheckFunction
151 "returns true if you have set printing functions"
152 input Tree<Key,Val> tree;
153 output Boolean hasUpdateCheck;
154 protected
155 Option<FuncTypeItemUpdateCheck> uf;
156 algorithm
157 ✗ TREE(updateCheckFuncOpt = uf) := tree;
158 ✗ hasUpdateCheck := boolNot(valueEq(NONE(), uf));
159 end hasUpdateCheckFunction;
160
161 public function getUpdateCheckFunc
162 "return the printing function pointer for the key, fails if you haven't set any"
163 input Tree<Key,Val> tree;
164 output FuncTypeItemUpdateCheck outUpdateCheckFunc;
165 algorithm
166 ✗ TREE(updateCheckFuncOpt = SOME(outUpdateCheckFunc)) := tree;
167 end getUpdateCheckFunc;
168
169 public function getKeyCompareFunc
170 "return the printing function pointer for the key, fails if you haven't set any"
171 input Tree<Key,Val> tree;
172 output FuncTypeKeyCompare outKeyCompareFunc;
173 algorithm
174 ✗ TREE(keyCompareFunc = outKeyCompareFunc) := tree;
175 end getKeyCompareFunc;
176
177 public function getKeyToStrFunc
178 "return the printing function pointer for the key, fails if you haven't set any"
179 input Tree<Key,Val> tree;
180 output FuncTypeKeyToStr outKey2StrFunc;
181 algorithm
182 ✗ TREE(keyStrFuncOpt = SOME(outKey2StrFunc)) := tree;
183 end getKeyToStrFunc;
184
185 public function getValToStrFunc
186 "return the printing function pointer for the val, fails if you haven't set any"
187 input Tree<Key,Val> tree;
188 output FuncTypeValToStr outVal2StrFunc;
189 algorithm
190 ✗ TREE(valStrFuncOpt = SOME(outVal2StrFunc)) := tree;
191 end getValToStrFunc;
192
193 protected function newLeafNode
194 input Item<Key,Val> inItem;
195 input Integer height;
196 output Node<Key,Val> outNode;
197 algorithm
198 ✗ outNode := NODE(inItem, 1, NO_NODE(), NO_NODE());
199 end newLeafNode;
200
201 public function add
202 "inserts a new item into the tree."
203 input Tree<Key,Val> inTree;
204 input Key inKey;
205 input Val inVal;
206 output Tree<Key,Val> outTree;
207 algorithm
208 outTree := matchcontinue(inTree, inKey, inVal)
209 local
210 Key key;
211 Val val;
212 Node<Key,Val> node;
213 FuncTypeKeyCompare cf;
214 Option<FuncTypeKeyToStr> kf;
215 Option<FuncTypeValToStr> vf;
216 Option<FuncTypeItemUpdateCheck> uf;
217 String str, n;
218
219 // call addNode on the root
220 case (TREE(node, cf, kf, vf, uf, n), key, val)
221 algorithm
222 ✗ node := addNode(inTree, node, key, val); // send the tree down to the nodes for compare function and update check
223 ✗ then
224 TREE(node, cf, kf, vf, uf, n);
225
226 else
227 algorithm
228 ✗ str := "AvlTree.add name: " + name(inTree) + " failed!";
229 ✗ Error.addMessage(Error.INTERNAL_ERROR, {str});
230 ✗ then
231 fail();
232
233 end matchcontinue;
234 end add;
235
236 protected function addNode
237 "Inserts a new item into the tree root node"
238 input Tree<Key,Val> inTree "sent down so we can use the update check function";
239 input Node<Key,Val> inNode "the node to add item to";
240 input Key inKey;
241 input Val inVal;
242 output Node<Key,Val> outNode;
243 algorithm
244 outNode := match(inTree, inNode, inKey, inVal)
245 local
246 Key key, rkey;
247 Val val;
248 Item<Key,Val> item;
249 FuncTypeKeyCompare keyCompareFunc;
250 Node<Key,Val> n;
251 Integer order;
252 String str;
253
254 // empty node
255 case (_, NO_NODE(), _, _)
256 algorithm
257 ✗ n := newLeafNode(ITEM(inKey, inVal), 1);
258 then
259 n;
260
261 // empty node item
262 case (_, NODE(item = NO_ITEM(), left = NO_NODE(), right = NO_NODE()), key, val)
263 algorithm
264 ✗ n := newLeafNode(ITEM(key, val), 1);
265 then
266 n;
267
268 case (TREE(keyCompareFunc = keyCompareFunc), NODE(item = ITEM(key = rkey)), key, val)
269 algorithm
270 ✗ order := keyCompareFunc(key, rkey);
271 ✗ n := balance(addNode_dispatch(inTree,inNode,order,key, val));
272 then
273 n;
274
275 else
276 algorithm
277 ✗ str := "AvlTree.addNode name: " + name(inTree) + " failed!";
278 ✗ Error.addMessage(Error.INTERNAL_ERROR, {str});
279 ✗ then fail();
280
281 end match;
282 end addNode;
283
284 protected function addNode_dispatch
285 "Helper function to addNode."
286 input Tree<Key,Val> inTree "sent down so we can use the update check function";
287 input Node<Key,Val> inNode;
288 input Integer inKeyComp;
289 input Key inKey;
290 input Val inVal;
291 output Node<Key,Val> outNode;
292 algorithm
293 outNode := matchcontinue(inNode, inKeyComp, inKey, inVal)
294 local
295 Key key;
296 Val val;
297 Node<Key,Val> l, r, n;
298 Integer h;
299 Item<Key,Val> i;
300 FuncTypeItemUpdateCheck updateCheckFunc;
301
302 // replacements of nodes is allowed! no update check function
303 case (NODE(_, h, l, r), 0, key, val)
304 algorithm
305 ✗ false := hasUpdateCheckFunction(inTree);
306 ✗ then
307 NODE(ITEM(key,val), h, l, r);
308
309 // replacements of nodes maybe allowed!
310 // we have an update check function
311 case (NODE(i, h, l, r), 0, key, val)
312 algorithm
313 ✗ true := hasUpdateCheckFunction(inTree);
314 ✗ updateCheckFunc := getUpdateCheckFunc(inTree);
315 // update is allowed
316 ✗ true := updateCheckFunc(i, ITEM(key, val));
317 ✗ then
318 NODE(ITEM(key,val), h, l, r);
319
320 // replacements of nodes maybe allowed!
321 // we have an update check function
322 case (NODE(i, _, _, _), 0, key, val)
323 algorithm
324 ✗ true := hasUpdateCheckFunction(inTree);
325 ✗ updateCheckFunc := getUpdateCheckFunc(inTree);
326 // update is NOT allowed
327 ✗ false := updateCheckFunc(i, ITEM(key, val));
328 then
329 inNode; // return the same node, no update!
330
331 // insert into right subtree.
332 case (NODE(item = i, height = h, left = l, right = r), 1, key, val)
333 algorithm
334 ✗ n := emptyNodeIfNoNode(r);
335 ✗ n := addNode(inTree, n, key, val);
336 ✗ then
337 NODE(i, h, l, n);
338
339 // Insert into left subtree.
340 case (NODE(item = i, height = h, left = l, right = r), -1, key, val)
341 algorithm
342 ✗ n := emptyNodeIfNoNode(l);
343 ✗ n := addNode(inTree, n, key, val);
344 ✗ then
345 NODE(i, h, n, r);
346 end matchcontinue;
347 end addNode_dispatch;
348
349 public function get
350 "Get a Val from the binary tree given a key."
351 input Tree<Key,Val> inTree;
352 input Key inKey;
353 output Val outVal;
354 protected
355 Node<Key,Val> node;
356 algorithm
357 ✗ TREE(root = node) := inTree;
358 ✗ outVal := getNode(inTree, node, inKey); // send the tree down for the compare func!
359 end get;
360
361 protected function getNode
362 "Get a Val from the binary tree node given a key."
363 input Tree<Key,Val> inTree;
364 input Node<Key,Val> inNode;
365 input Key inKey;
366 output Val outVal;
367 protected
368 Key rkey;
369 FuncTypeKeyCompare keyCompareFunc;
370 Integer order;
371 algorithm
372 ✗ NODE(item = ITEM(key = rkey)) := inNode;
373 ✗ keyCompareFunc := getKeyCompareFunc(inTree);
374 ✗ order := keyCompareFunc(inKey, rkey);
375 ✗ outVal := getNode_dispatch(inTree, inNode, order, inKey);
376 end getNode;
377
378 protected function getNode_dispatch
379 "Helper function to getNode."
380 input Tree<Key,Val> inTree;
381 input Node<Key,Val> inNode;
382 input Integer inKeyComp;
383 input Key inKey;
384 output Val outVal;
385 algorithm
386 outVal := match(inNode, inKeyComp, inKey)
387 local
388 Key key;
389 Val val;
390 Node<Key,Val> l, r;
391
392 // found match.
393 case (NODE(item = ITEM(val = val)), 0, _)
394 then val;
395
396 // search to the right.
397 case (NODE(right = r), 1, key)
398 ✗ then getNode(inTree, r, key);
399
400 // search to the left.
401 case (NODE(left = l), -1, key)
402 ✗ then getNode(inTree, l, key);
403
404 end match;
405 end getNode_dispatch;
406
407 public function replace
408 "Replaces the item of an already existing node in the tree with a new item.
409 Note that the update check function is not used if replace is called!"
410 input Tree<Key,Val> inTree;
411 input Key inKey;
412 input Val inVal;
413 output Tree<Key,Val> outTree;
414 algorithm
415 outTree := match(inTree, inKey, inVal)
416 local
417 Key key;
418 Val val;
419 FuncTypeKeyCompare keyCompareFunc;
420 Option<FuncTypeKeyToStr> kf;
421 Option<FuncTypeValToStr> vf;
422 Option<FuncTypeItemUpdateCheck> uf;
423 Node<Key,Val> node;
424 String n, str;
425
426 case (TREE(node, keyCompareFunc, kf, vf, uf, n), key, val)
427 algorithm
428 ✗ node := replaceNode(inTree, node, key, val);
429 ✗ then
430 TREE(node, keyCompareFunc, kf, vf, uf, n);
431
432 else
433 algorithm
434 ✗ str := "AvlTree.replace name: " + name(inTree) + " failed!";
435 ✗ Error.addMessage(Error.INTERNAL_ERROR, {str});
436 ✗ then fail();
437
438 end match;
439 end replace;
440
441 public function replaceNode
442 "Replaces the item of an already existing node in the tree with a new value."
443 input Tree<Key,Val> inTree "send down for comparison function";
444 input Node<Key,Val> inNode;
445 input Key inKey;
446 input Val inVal;
447 output Node<Key,Val> outNode;
448 algorithm
449 outNode := match(inTree, inNode, inKey, inVal)
450 local
451 Key key, rkey;
452 Val val;
453 FuncTypeKeyCompare keyCompareFunc;
454 Node<Key, Val> n;
455 Integer order;
456
457 case (TREE(keyCompareFunc = keyCompareFunc),
458 NODE(item = ITEM(key = rkey)),
459 key, val)
460 algorithm
461 ✗ order := keyCompareFunc(key, rkey);
462 ✗ n := replaceNode_dispatch(inTree, inNode, order, key, val);
463 then
464 n;
465
466 end match;
467 end replaceNode;
468
469 protected function replaceNode_dispatch
470 "Helper function to replaceNode."
471 input Tree<Key,Val> inTree "send down for comparison function";
472 input Node<Key,Val> inNode;
473 input Integer inKeyComp;
474 input Key inKey;
475 input Val inVal;
476 output Node<Key,Val> outNode;
477 algorithm
478 outNode := match(inNode, inKeyComp, inKey, inVal)
479 local
480 Key key;
481 Val val;
482 Node<Key,Val> l, r, n;
483 Integer h;
484 Item<Key,Val> i;
485
486 // replace this node.
487 case (NODE(item = ITEM(), height = h, left = l, right = r), 0, key, val)
488 ✗ then
489 NODE(ITEM(key, val), h, l, r);
490
491 // insert into right subtree.
492 case (NODE(item = i, height = h, left = l, right = r), 1, key, val)
493 algorithm
494 ✗ n := emptyNodeIfNoNode(r);
495 ✗ n := replaceNode(inTree, n, key, val);
496 ✗ then
497 NODE(i, h, l, n);
498
499 // insert into left subtree.
500 case (NODE(item = i, height = h, left = l, right = r), -1, key, val)
501 algorithm
502 ✗ n := emptyNodeIfNoNode(l);
503 ✗ n := replaceNode(inTree, n, key, val);
504 ✗ then
505 NODE(i, h, n, r);
506 end match;
507 end replaceNode_dispatch;
508
509 protected function emptyNodeIfNoNode
510 "creates an empty node if the node is NO_NODE"
511 input Node<Key,Val> inNode;
512 output Node<Key,Val> outNode;
513 algorithm
514 outNode := match inNode
515 case NO_NODE() then NODE(NO_ITEM(), 0, NO_NODE(), NO_NODE());
516 case NODE() then inNode;
517 end match;
518 end emptyNodeIfNoNode;
519
520 protected function balance
521 "Balances an Node<Key,Val>"
522 input Node<Key,Val> inNode;
523 output Node<Key,Val> outNode;
524 protected
525 Integer d;
526 algorithm
527 ✗ d := differenceInHeight(inNode);
528 ✗ outNode := doBalance(d, inNode);
529 end balance;
530
531 protected function doBalance
532 "Performs balance if difference is > 1 or < -1"
533 input Integer difference;
534 input Node<Key,Val> inNode;
535 output Node<Key,Val> outNode;
536 algorithm
537 outNode := match difference
538 ✗ case -1 then computeHeight(inNode);
539 ✗ case 0 then computeHeight(inNode);
540 ✗ case 1 then computeHeight(inNode);
541 // d < -1 or d > 1
542 ✗ else doBalance2(difference < 0, inNode);
543 end match;
544 end doBalance;
545
546 protected function doBalance2
547 "Help function to doBalance"
548 input Boolean inDiffIsNegative;
549 input Node<Key,Val> inNode;
550 output Node<Key,Val> outNode;
551 algorithm
552 outNode := match(inDiffIsNegative, inNode)
553 local
554 Node<Key,Val> n;
555
556 case(true, n)
557 algorithm
558 ✗ n := doBalance3(n);
559 ✗ n := rotateLeft(n);
560 then n;
561
562 case(false,n)
563 algorithm
564 ✗ n := doBalance4(n);
565 ✗ n := rotateRight(n);
566 then n;
567 end match;
568 end doBalance2;
569
570 protected function doBalance3
571 "help function to doBalance2"
572 input Node<Key,Val> inNode;
573 output Node<Key,Val> outNode;
574 algorithm
575 outNode := matchcontinue inNode
576 local
577 Node<Key,Val> n, rr, rN;
578
579 case n
580 algorithm
581 ✗ rN := rightNode(n);
582 ✗ true := differenceInHeight(rN) > 0;
583 ✗ rr := rotateRight(rN);
584 ✗ n := setRight(n, rr);
585 then n;
586
587 else inNode;
588 end matchcontinue;
589 end doBalance3;
590
591 protected function doBalance4
592 "Help function to doBalance2"
593 input Node<Key,Val> inNode;
594 output Node<Key,Val> outNode;
595 algorithm
596 outNode := matchcontinue inNode
597 local
598 Node<Key,Val> rl, n, lN;
599
600 case n
601 algorithm
602 ✗ lN := leftNode(n);
603 ✗ true := differenceInHeight(lN) < 0;
604 ✗ rl := rotateLeft(lN);
605 ✗ n := setLeft(n, rl);
606 then n;
607
608 else inNode;
609 end matchcontinue;
610 end doBalance4;
611
612 protected function setRight
613 "set right treenode"
614 input Node<Key,Val> node;
615 input Node<Key,Val> right;
616 output Node<Key,Val> outNode;
617 protected
618 Item<Key,Val> item;
619 Node<Key,Val> l;
620 Integer height;
621 algorithm
622 ✗ NODE(item, height, l, _) := node;
623 ✗ outNode := NODE(item, height, l, right);
624 end setRight;
625
626 protected function setLeft
627 "set left node"
628 input Node<Key,Val> node;
629 input Node<Key,Val> left;
630 output Node<Key,Val> outNode;
631 protected
632 Item<Key,Val> item;
633 Node<Key,Val> r;
634 Integer height;
635 algorithm
636 ✗ NODE(item, height, _, r) := node;
637 ✗ outNode := NODE(item, height, left, r);
638 end setLeft;
639
640 protected function leftNode
641 "Retrieve the left subnode"
642 input Node<Key,Val> node;
643 output Node<Key,Val> subNode;
644 algorithm
645 ✗ NODE(left = subNode) := node;
646 end leftNode;
647
648 protected function rightNode
649 "Retrieve the right subnode"
650 input Node<Key,Val> node;
651 output Node<Key,Val> subNode;
652 algorithm
653 ✗ NODE(right = subNode) := node;
654 end rightNode;
655
656 protected function exchangeLeft
657 "help function to balance"
658 input Node<Key,Val> inNode;
659 input Node<Key,Val> inParent;
660 output Node<Key,Val> outParent "updated parent";
661 protected
662 Node<Key,Val> parent, node;
663 algorithm
664 ✗ parent := setRight(inParent, leftNode(inNode));
665 ✗ parent := balance(parent);
666 ✗ node := setLeft(inNode, parent);
667 ✗ outParent := balance(node);
668 end exchangeLeft;
669
670 protected function exchangeRight
671 "help function to balance"
672 input Node<Key,Val> inNode;
673 input Node<Key,Val> inParent;
674 output Node<Key,Val> outParent "updated parent";
675 protected
676 Node<Key,Val> parent, node;
677 algorithm
678 ✗ parent := setLeft(inParent, rightNode(inNode));
679 ✗ parent := balance(parent);
680 ✗ node := setRight(inNode, parent);
681 ✗ outParent := balance(node);
682 end exchangeRight;
683
684 protected function rotateLeft
685 "help function to balance"
686 input Node<Key,Val> node;
687 output Node<Key,Val> outNode "updated node";
688 algorithm
689 ✗ outNode := exchangeLeft(rightNode(node), node);
690 end rotateLeft;
691
692 protected function rotateRight
693 "help function to balance"
694 input Node<Key,Val> node;
695 output Node<Key,Val> outNode "updated node";
696 algorithm
697 ✗ outNode := exchangeRight(leftNode(node), node);
698 end rotateRight;
699
700 protected function differenceInHeight
701 "help function to balance, calculates the difference in height between left
702 and right child"
703 input Node<Key,Val> node;
704 output Integer diff;
705 protected
706 Node<Key,Val> l, r;
707 algorithm
708 ✗ NODE(left = l, right = r) := node;
709 ✗ diff := getHeight(l) - getHeight(r);
710 end differenceInHeight;
711
712 protected function computeHeight
713 "compute the heigth of the Tree and store in the node info"
714 input Node<Key,Val> inNode;
715 output Node<Key,Val> outNode;
716 protected
717 Node<Key,Val> l,r;
718 Item<Key,Val> i;
719 Integer hl,hr,height;
720 algorithm
721 ✗ NODE(item = i as ITEM(), left = l, right = r) := inNode;
722 ✗ hl := getHeight(l);
723 ✗ hr := getHeight(r);
724 ✗ height := intMax(hl, hr) + 1;
725 ✗ outNode := NODE(i, height, l, r);
726 end computeHeight;
727
728 protected function getHeight
729 "Retrieve the height of a node"
730 input Node<Key,Val> bt;
731 output Integer height;
732 algorithm
733 height := match bt
734 case NO_NODE() then 0;
735 case NODE(height = height) then height;
736 end match;
737 end getHeight;
738
739 public function prettyPrintTreeStr
740 input Tree<Key,Val> inTree;
741 output String outString;
742 algorithm
743 ✗ outString := prettyPrintTreeStr_dispatch(inTree, "");
744 end prettyPrintTreeStr;
745
746 protected function prettyPrintTreeStr_dispatch
747 input Tree<Key,Val> inTree;
748 input String inIndent;
749 output String outString;
750 protected
751 Node<Key,Val> node;
752 algorithm
753 ✗ if not hasPrintingFunctions(inTree) then
754 ✗ outString := "TreePrintError<NO_PRINTING_FUNCTIONS_ATTACHED> name[" + name(inTree) + "]";
755 ✗ return;
756 end if;
757 ✗ TREE(root = node) := inTree;
758 ✗ outString := prettyPrintNodeStr(inTree, node, inIndent);
759 end prettyPrintTreeStr_dispatch;
760
761 protected function prettyPrintNodeStr
762 input Tree<Key,Val> inTree;
763 input Node<Key,Val> inNode;
764 input String inIndent;
765 output String outString;
766 algorithm
767 outString := match inNode
768 local
769 Item<Key,Val> item;
770 Node<Key,Val> l, r;
771 String indent, s1, s2, res;
772
773 case NO_NODE() then "";
774
775 case NODE(item = NO_ITEM(), left = l, right = r)
776 algorithm
777 ✗ indent := inIndent + " ";
778 ✗ s1 := prettyPrintNodeStr(inTree, l, indent);
779 ✗ s2 := prettyPrintNodeStr(inTree, r, indent);
780 ✗ res := "\n" + s1 + s2;
781 then
782 res;
783
784 case NODE(item = item as ITEM(), left = l, right = r)
785 algorithm
786 ✗ indent := inIndent + " ";
787 ✗ s1 := prettyPrintNodeStr(inTree, l, indent);
788 ✗ s2 := prettyPrintNodeStr(inTree, r, indent);
789 ✗ res := "\n" + inIndent + printItemStr(inTree, item) + s1 + s2;
790 then
791 res;
792
793 end match;
794 end prettyPrintNodeStr;
795
796 public function printTreeStr
797 input Tree<Key,Val> inTree;
798 output String outString;
799 protected
800 Node<Key,Val> node;
801 algorithm
802 ✗ if not hasPrintingFunctions(inTree) then
803 ✗ outString := "TreePrintError<NO_PRINTING_FUNCTIONS_ATTACHED> name[" + name(inTree) + "]";
804 ✗ return;
805 end if;
806 ✗ TREE(root = node) := inTree;
807 ✗ outString := printNodeStr(inTree, node);
808 end printTreeStr;
809
810 protected function printNodeStr
811 input Tree<Key,Val> inTree;
812 input Node<Key,Val> inNode;
813 output String outString;
814 algorithm
815 outString := match inNode
816 local
817 Node<Key,Val> left, right;
818 Item<Key,Val> item;
819 String left_str, right_str, item_str, str;
820
821 case NO_NODE() then "";
822 case NODE(item = NO_ITEM()) then "";
823 case NODE(item = item as ITEM(), left = left, right = right)
824 algorithm
825 ✗ left_str := printNodeStr(inTree, left);
826 ✗ right_str := printNodeStr(inTree, right);
827 ✗ item_str := printItemStr(inTree, item);
828 ✗ str := stringAppendList({"i: ",item_str, ", l: ", left_str, ", r: ", right_str});
829 then
830 str;
831
832 end match;
833 end printNodeStr;
834
835 public function printItemStr
836 input Tree<Key,Val> inTree;
837 input Item<Key,Val> inItem;
838 output String outString;
839 algorithm
840 outString := match inItem
841 local
842 String str, keyStr, valStr;
843 FuncTypeKeyToStr key2Str;
844 FuncTypeValToStr val2Str;
845 Key key;
846 Val val;
847
848 case NO_ITEM() then "[]";
849 case ITEM(key = key, val = val)
850 algorithm
851 ✗ key2Str := getKeyToStrFunc(inTree);
852 ✗ val2Str := getValToStrFunc(inTree);
853 ✗ keyStr := key2Str(key);
854 ✗ valStr := val2Str(val);
855 ✗ str := "[" + keyStr + ", " + valStr + "]";
856 then
857 str;
858 end match;
859 end printItemStr;
860
861 public function getKeyOfVal
862 "search for a key that has val as value, fails if it cannot find it;
863 if there are multiple keys pointing to the same value only the first
864 one encountered is returned"
865 input Tree<Key,Val> inTree;
866 input Val inVal;
867 output Key outKey;
868 protected
869 Node<Key,Val> node;
870 algorithm
871 ✗ TREE(root = node) := inTree;
872 ✗ outKey := getKeyOfValNode(inTree, node, inVal);
873 end getKeyOfVal;
874
875 protected function getKeyOfValNode
876 input Tree<Key,Val> inTree;
877 input Node<Key,Val> inNode;
878 input Val inVal;
879 output Key outKey;
880 algorithm
881 outKey := matchcontinue inNode
882 local
883 Node<Key,Val> left, right;
884 Item<Key,Val> item;
885 Val v;
886 Key k;
887
888 case NODE(item=ITEM(k,v))
889 algorithm
890 ✗ true := valueEq(v, inVal);
891 then
892 k;
893
894 // search left
895 case NODE(item=ITEM(_,v), left = left)
896 algorithm
897 ✗ false := valueEq(v, inVal);
898 ✗ k := getKeyOfValNode(inTree, left, inVal);
899 then
900 k;
901
902 // search right
903 case NODE(item=ITEM(_,v), right = right)
904 algorithm
905 ✗ false := valueEq(v, inVal);
906 ✗ k := getKeyOfValNode(inTree, right, inVal);
907 then
908 k;
909
910 end matchcontinue;
911 end getKeyOfValNode;
912
913 public function addUnique
914 "inserts a new item into the tree if is not there
915 and returns the new item.
916 if the key is there then it returns the already
917 exiting item and doe not update the tree."
918 input Tree<Key,Val> inTree;
919 input Key inKey;
920 input Val inVal;
921 output Tree<Key,Val> outTree;
922 output Item<Key,Val> outItem;
923 algorithm
924 (outTree, outItem) := matchcontinue(inTree, inKey, inVal)
925 local
926 Key key;
927 Val val;
928 Node<Key,Val> node;
929 FuncTypeKeyCompare cf;
930 Option<FuncTypeKeyToStr> kf;
931 Option<FuncTypeValToStr> vf;
932 Option<FuncTypeItemUpdateCheck> uf;
933 String str, n;
934 Item<Key,Val> item;
935
936 // call addNode on the root
937 case (TREE(node, cf, kf, vf, uf, n), key, val)
938 algorithm
939 ✗ (node, item) := addNodeUnique(inTree, node, key, val); // send the tree down to the nodes for compare function and update check
940 ✗ then
941 (TREE(node, cf, kf, vf, uf, n), item);
942
943 else
944 algorithm
945 ✗ str := "AvlTree.addUnique name: " + name(inTree) + " failed!";
946 ✗ Error.addMessage(Error.INTERNAL_ERROR, {str});
947 ✗ then
948 fail();
949
950 end matchcontinue;
951 end addUnique;
952
953 protected function addNodeUnique
954 "Inserts a new item into the tree root node if is not there and returns the new item.
955 if is there it returns the existing item."
956 input Tree<Key,Val> inTree "sent down so we can use the update check function";
957 input Node<Key,Val> inNode "the node to add item to";
958 input Key inKey;
959 input Val inVal;
960 output Node<Key,Val> outNode;
961 output Item<Key,Val> outItem;
962 algorithm
963 (outNode, outItem) := match(inTree, inNode, inKey, inVal)
964 local
965 Key key, rkey;
966 Val val;
967 Item<Key,Val> item;
968 FuncTypeKeyCompare keyCompareFunc;
969 Node<Key,Val> n;
970 Integer order;
971 String str;
972
973 // empty node
974 case (_, NO_NODE(), _, _)
975 algorithm
976 ✗ item := ITEM(inKey, inVal);
977 ✗ n := newLeafNode(item, 1);
978 ✗ then
979 (n, item);
980
981 // empty node item
982 case (_, NODE(item = NO_ITEM(), left = NO_NODE(), right = NO_NODE()), key, val)
983 algorithm
984 ✗ item := ITEM(key, val);
985 ✗ n := newLeafNode(item, 1);
986 ✗ then
987 (n, item);
988
989 case (TREE(keyCompareFunc = keyCompareFunc), NODE(item = ITEM(key = rkey)), key, val)
990 algorithm
991 ✗ order := keyCompareFunc(key, rkey);
992 ✗ (n, item) := addNodeUnique_dispatch(inTree,inNode,order,key,val);
993 ✗ n := balance(n);
994 ✗ then
995 (n, item);
996
997 else
998 algorithm
999 ✗ str := "AvlTree.addNodeUnique name: " + name(inTree) + " failed!";
1000 ✗ Error.addMessage(Error.INTERNAL_ERROR, {str});
1001 ✗ then
1002 fail();
1003 end match;
1004 end addNodeUnique;
1005
1006 protected function addNodeUnique_dispatch
1007 "Helper function to addNode."
1008 input Tree<Key,Val> inTree "sent down so we can use the update check function";
1009 input Node<Key,Val> inNode;
1010 input Integer inKeyComp;
1011 input Key inKey;
1012 input Val inVal;
1013 output Node<Key,Val> outNode;
1014 output Item<Key,Val> outItem;
1015 algorithm
1016 (outNode, outItem) := match(inNode, inKeyComp, inKey, inVal)
1017 local
1018 Key key;
1019 Val val;
1020 Node<Key,Val> l, r, n;
1021 Integer h;
1022 Item<Key,Val> i, it;
1023
1024 // replacements of nodes are not allowed in addUnique
1025 // we don't care about update check functions here
1026 case (NODE(i, _, _, _), 0, _, _)
1027 then
1028 (inNode, i); // return the same node, no update for addUnique!
1029
1030 // insert into right subtree.
1031 case (NODE(item = i, height = h, left = l, right = r), 1, key, val)
1032 algorithm
1033 ✗ n := emptyNodeIfNoNode(r);
1034 ✗ (n, it) := addNodeUnique(inTree, n, key, val);
1035 ✗ then
1036 (NODE(i, h, l, n), it);
1037
1038 // Insert into left subtree.
1039 case (NODE(item = i, height = h, left = l, right = r), -1, key, val)
1040 algorithm
1041 ✗ n := emptyNodeIfNoNode(l);
1042 ✗ (n, it) := addNodeUnique(inTree, n, key, val);
1043 ✗ then
1044 (NODE(i, h, n, r), it);
1045 end match;
1046 end addNodeUnique_dispatch;
1047
1048 annotation(__OpenModelica_Interface="backend_tools");
1049 end AvlTree;
1050
1051