OMCompiler/Compiler/BackEnd/BinaryTreeInt.mo - 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 / 37
Functions:	-%	0 / 1 / 1
Branches:	0.0%	0 / 0 / 10

    OMCompiler/Compiler/BackEnd/BinaryTreeInt.mo
    
        Line
        Branch
        Exec
        Source
      
        /*
      
         * This file is part of OpenModelica.
      
         *
      
         * Copyright (c) 1998-2026, 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 AGPL VERSION 3 LICENSE OR
      
         * THIS OSMC PUBLIC LICENSE (OSMC-PL) VERSION 1.8.
      
         * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS PROGRAM CONSTITUTES
      
         * RECIPIENT'S ACCEPTANCE OF THE OSMC PUBLIC LICENSE OR THE GNU AGPL
      
         * VERSION 3, ACCORDING TO RECIPIENTS CHOICE.
      
         *
      
         * The OpenModelica software and the OSMC (Open Source Modelica Consortium)
      
         * Public License (OSMC-PL) are obtained from OSMC, either from the above
      
         * address, from the URLs:
      
         * http://www.openmodelica.org or
      
         * https://github.com/OpenModelica/ or
      
         * http://www.ida.liu.se/projects/OpenModelica,
      
         * and in the OpenModelica distribution.
      
         *
      
         * GNU AGPL version 3 is obtained from:
      
         * https://www.gnu.org/licenses/licenses.html#GPL
      
         *
      
         * 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 package BinaryTreeInt
      
        " file:        BinaryTreeInt.mo
      
          package:     BinaryTreeInt
      
          description: BinaryTreeInt comprises functions for BinaryTrees.
      
          BinaryTree."
      
        /**************************
      
          imports
      
         **************************/
      
        protected import Error;
      
        protected import Util;
      
        /**************************
      
          types
      
         **************************/
      
        public
      
        uniontype BinTree "Generic Binary tree implementation
      
          - Binary Tree"
      
          record TREENODE
      
            Option<TreeValue> value "Value";
      
            Option<BinTree> leftSubTree "left subtree";
      
            Option<BinTree> rightSubTree "right subtree";
      
          end TREENODE;
      
        end BinTree;
      
        public
      
        uniontype TreeValue "Each node in the binary tree can have a value associated with it.
      
          - Tree Value"
      
          record TREEVALUE
      
            Key key "Key";
      
            Value value "Value";
      
          end TREEVALUE;
      
        end TreeValue;
      
        public
      
        type Key = Integer "A key is a Integer";
      
        public
      
        type Value = Integer "- Value";
      
        public constant BinTree emptyBinTree=TREENODE(NONE(),NONE(),NONE()) " Empty binary tree ";
      
        /**************************
      
          implementation
      
         **************************/
      
        protected function keyCmp
      
          input Key keya;
      
          input Key keyb;
      
          output Integer cmp;
      
        algorithm
      
        ✗
          cmp := Util.intSign(keya-keyb);
      
        end keyCmp;
      
        public function treeGet "author: Frenkel TUD 2012-09-18
      
          Copied from generic implementation. Changed that no hashfunction is passed
      
          since a string can not be uniquely mapped to an int. Therefore we need to compare two strings
      
          to get a unique ordering.
      
        "
      
          input BinTree bt;
      
          input Key key;
      
          output Value v;
      
        protected
      
        algorithm
      
        ✗
          v := treeGet3(bt, key, treeGet2(bt, key));
      
        end treeGet;
      
        protected function treeGet2
      
          "Helper function to treeGet"
      
          input BinTree inBinTree;
      
          input Key ikey;
      
          output Integer compResult;
      
        algorithm
      
          compResult := match inBinTree
      
            local
      
              Key key;
      
            // found it
      
            case TREENODE(value = SOME(TREEVALUE(key=key)))
      
        ✗
              then keyCmp(key, ikey);
      
          end match;
      
        end treeGet2;
      
        protected function treeGet3
      
          "Helper function to treeGet"
      
          input BinTree inBinTree;
      
          input Key ikey;
      
          input Integer inCompResult;
      
          output Value outValue;
      
        algorithm
      
          outValue := match (inBinTree, inCompResult)
      
            local
      
              Value rval;
      
              BinTree right, left;
      
              Integer compResult;
      
            // found it
      
            case (TREENODE(value = SOME(TREEVALUE(value=rval))), 0) then rval;
      
            // search right
      
            case (TREENODE(rightSubTree = SOME(right)), 1)
      
              algorithm
      
        ✗
                compResult := treeGet2(right, ikey);
      
        ✗
              then treeGet3(right, ikey, compResult);
      
            // search left
      
            case (TREENODE(leftSubTree = SOME(left)), -1)
      
              algorithm
      
        ✗
                compResult := treeGet2(left, ikey);
      
        ✗
              then treeGet3(left, ikey, compResult);
      
          end match;
      
        end treeGet3;
      
        public function treeAddList "author: Frenkel TUD"
      
          input BinTree inBinTree;
      
          input list<Key> inKeyLst;
      
          output BinTree outBinTree;
      
        algorithm
      
          outBinTree := match (inBinTree,inKeyLst)
      
            local
      
              Key key;
      
              list<Key> res;
      
              BinTree bt,bt_1,bt_2;
      
            case (bt,{}) then bt;
      
            case (bt,key::res)
      
              algorithm
      
        ✗
                bt_1 := treeAdd(bt,key,0);
      
        ✗
                bt_2 := treeAddList(bt_1,res);
      
              then
      
                bt_2;
      
          end match;
      
        end treeAddList;
      
        public function treeAdd "author: PA
      
          Copied from generic implementation. Changed that no hashfunction is passed
      
          since a string (ComponentRef) can not be uniquely mapped to an int. Therefore we need to compare two strings
      
          to get a unique ordering.
      
          Actually, hashing is still important in order to speed up comparison of strings... So it was re-added in a
      
          good way, see function keyCompareNinjaSecretHashTricks"
      
          input BinTree inBinTree;
      
          input Key inKey;
      
          input Value inValue;
      
          output BinTree outBinTree;
      
        algorithm
      
          outBinTree := matchcontinue inBinTree
      
            local
      
              Key rkey;
      
              Option<BinTree> left,right;
      
              BinTree t_1,t,right_1,left_1;
      
              Option<TreeValue> optVal;
      
            case TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE())
      
        ✗
              then
      
                TREENODE(SOME(TREEVALUE(inKey,inValue)),NONE(),NONE());
      
            case TREENODE(value = SOME(TREEVALUE(rkey,_)),leftSubTree = left,rightSubTree = right)
      
              algorithm
      
        ✗
                0 := keyCmp(rkey,inKey);
      
        ✗
              then
      
                TREENODE(SOME(TREEVALUE(rkey,inValue)),left,right);
      
            case TREENODE(value = optVal as SOME(TREEVALUE(rkey,_)),leftSubTree = left,rightSubTree = (SOME(t)))
      
              algorithm
      
        ✗
                1 := keyCmp(rkey,inKey);
      
        ✗
                t_1 := treeAdd(t, inKey, inValue);
      
        ✗
              then
      
                TREENODE(optVal,left,SOME(t_1));
      
            case TREENODE(value = optVal as SOME(TREEVALUE(rkey,_)),leftSubTree = left,rightSubTree = (NONE()))
      
              algorithm
      
        ✗
                1 := keyCmp(rkey,inKey);
      
        ✗
                right_1 := treeAdd(TREENODE(NONE(),NONE(),NONE()), inKey, inValue);
      
        ✗
              then
      
                TREENODE(optVal,left,SOME(right_1));
      
            case TREENODE(value = optVal as SOME(TREEVALUE(rkey,_)),leftSubTree = (SOME(t)),rightSubTree = right)
      
              algorithm
      
        ✗
                -1 := keyCmp(rkey,inKey);
      
        ✗
                t_1 := treeAdd(t, inKey, inValue);
      
        ✗
              then
      
                TREENODE(optVal,SOME(t_1),right);
      
            case TREENODE(value = optVal as SOME(TREEVALUE(rkey,_)),leftSubTree = (NONE()),rightSubTree = right)
      
              algorithm
      
        ✗
                -1 := keyCmp(rkey,inKey);
      
        ✗
                left_1 := treeAdd(TREENODE(NONE(),NONE(),NONE()), inKey, inValue);
      
        ✗
              then
      
                TREENODE(optVal,SOME(left_1),right);
      
            else
      
              algorithm
      
        ✗
                Error.addMessage(Error.INTERNAL_ERROR,{"- BinaryTreeInt.treeAdd failed\n"});
      
        ✗
              then
      
                fail();
      
          end matchcontinue;
      
        end treeAdd;
      
        // protected function treeDelete2 "author: PA
      
        //   This function deletes an entry from the BinTree."
      
        //   input BinTree inBinTree;
      
        //   input Integer inKey;
      
        //   output BinTree outBinTree;
      
        // algorithm
      
        //   outBinTree := matchcontinue (inBinTree,inKey)
      
        //     local
      
        //       BinTree bt,right,left,t;
      
        //       Key key,rkey;
      
        //       TreeValue rightmost;
      
        //       Option<BinTree> optRight,optLeft,optTree;
      
        //       Value rval;
      
        //       Option<TreeValue> optVal;
      
        //       Integer rhash;
      
        //
      
        //     case ((bt as TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE())),_)
      
        //       then bt;
      
        //
      
        //     case (TREENODE(value = SOME(TREEVALUE(rkey,rval)),leftSubTree = optLeft,rightSubTree = SOME(right)),_)
      
        //       equation
      
        //         0 = keyCmp(rkey, inKey);
      
        //         (rightmost,right) = treeDeleteRightmostValue(right);
      
        //         optRight = treePruneEmptyNodes(right);
      
        //       then
      
        //         TREENODE(SOME(rightmost),optLeft,optRight);
      
        //
      
        //     case (TREENODE(value = SOME(TREEVALUE(rkey,rval)),leftSubTree = SOME(left as TREENODE(value=_)),rightSubTree = NONE()),_)
      
        //       equation
      
        //         0 = keyCmp(rkey, inKey);
      
        //       then
      
        //         left;
      
        //
      
        //     case (TREENODE(value = SOME(TREEVALUE(rkey,rval)),leftSubTree = NONE(),rightSubTree = NONE()),_)
      
        //       equation
      
        //         0 = keyCmp(rkey, inKey);
      
        //       then
      
        //         TREENODE(NONE(),NONE(),NONE());
      
        //
      
        //     case (TREENODE(value = optVal as SOME(TREEVALUE(rkey,rval)),leftSubTree = optLeft,rightSubTree = SOME(t)),_)
      
        //       equation
      
        //         1 = keyCmp(rkey, inKey);
      
        //         t = treeDelete2(t, inKey);
      
        //         optTree = treePruneEmptyNodes(t);
      
        //       then
      
        //         TREENODE(optVal,optLeft,optTree);
      
        //
      
        //     case (TREENODE(value = optVal as SOME(TREEVALUE(rkey,rval)),leftSubTree =  SOME(t),rightSubTree = optRight),_)
      
        //       equation
      
        //         -1 = keyCmp(rkey, inKey);
      
        //         t = treeDelete2(t, inKey);
      
        //         optTree = treePruneEmptyNodes(t);
      
        //       then
      
        //         TREENODE(optVal,optTree,optRight);
      
        //
      
        //     else
      
        //       equation
      
        //         Error.addMessage(Error.INTERNAL_ERROR,{"-BinaryTree.treeDelete failed\n"});
      
        //       then
      
        //         fail();
      
        //   end matchcontinue;
      
        // end treeDelete2;
      
        // protected function treeDeleteRightmostValue "author: PA
      
        //   This function takes a BinTree and deletes the rightmost value of the tree.
      
        //   Tt returns this value and the updated BinTree. This function is used in
      
        //   the binary tree deletion function \'tree_delete\'.
      
        //   inputs:  (BinTree)
      
        //   outputs: (TreeValue, /* deleted value */
      
        //               BinTree    /* updated bintree */)
      
        // "
      
        //   input BinTree inBinTree;
      
        //   output TreeValue outTreeValue;
      
        //   output BinTree outBinTree;
      
        // algorithm
      
        //   (outTreeValue,outBinTree) := matchcontinue (inBinTree)
      
        //     local
      
        //       TreeValue treeVal,value;
      
        //       BinTree left,right,bt;
      
        //       Option<BinTree> optRight, optLeft;
      
        //       Option<TreeValue> optTreeVal;
      
        //
      
        //     case (TREENODE(value = SOME(treeVal),leftSubTree = NONE(),rightSubTree = NONE()))
      
        //       then (treeVal,TREENODE(NONE(),NONE(),NONE()));
      
        //
      
        //     case (TREENODE(value = SOME(treeVal),leftSubTree = SOME(left),rightSubTree = NONE()))
      
        //       then (treeVal,left);
      
        //
      
        //     case (TREENODE(value = optTreeVal,leftSubTree = optLeft,rightSubTree = SOME(right)))
      
        //       equation
      
        //         (value,right) = treeDeleteRightmostValue(right);
      
        //         optRight = treePruneEmptyNodes(right);
      
        //       then
      
        //         (value,TREENODE(optTreeVal,optLeft,optRight));
      
        //
      
        //     case (TREENODE(value = SOME(treeVal),leftSubTree = NONE(),rightSubTree = SOME(right)))
      
        //       equation
      
        //         failure((_,_) = treeDeleteRightmostValue(right));
      
        //         print("- BinaryTree.treeDeleteRightmostValue: right value was empty, left NONE\n");
      
        //       then
      
        //         (treeVal,TREENODE(NONE(),NONE(),NONE()));
      
        //
      
        //     else
      
        //       equation
      
        //         Error.addMessage(Error.INTERNAL_ERROR,{"- BinaryTree.treeDeleteRightmostValue failed\n"});
      
        //       then
      
        //         fail();
      
        //   end matchcontinue;
      
        // end treeDeleteRightmostValue;
      
        // protected function treePruneEmptyNodes "author: PA
      
        //   This function is a helper function to tree_delete
      
        //   It is used to delete empty nodes of the BinTree
      
        //   representation, that might be introduced when deleting nodes."
      
        //   input BinTree inBinTree;
      
        //   output Option<BinTree> outBinTreeOption;
      
        // algorithm
      
        //   outBinTreeOption := matchcontinue (inBinTree)
      
        //     local BinTree bt;
      
        //     case TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE()) then NONE();
      
        //     case bt then SOME(bt);
      
        //   end matchcontinue;
      
        // end treePruneEmptyNodes;
      
        // protected function bintreeDepth "author: PA
      
        //   This function calculates the depth of the Binary Tree given
      
        //   as input. It can be used for debugging purposes to investigate
      
        //   how balanced binary trees are."
      
        //   input BinTree inBinTree;
      
        //   output Integer outInteger;
      
        // algorithm
      
        //   outInteger := matchcontinue (inBinTree)
      
        //     local
      
        //       Value ld,rd,res;
      
        //       BinTree left,right;
      
        //
      
        //     case (TREENODE(leftSubTree = NONE(),rightSubTree = NONE())) then 1;
      
        //
      
        //     case (TREENODE(leftSubTree = SOME(left),rightSubTree = SOME(right)))
      
        //       equation
      
        //         ld = bintreeDepth(left);
      
        //         rd = bintreeDepth(right);
      
        //         res = intMax(ld, rd);
      
        //       then
      
        //         res + 1;
      
        //
      
        //     case (TREENODE(leftSubTree = SOME(left),rightSubTree = NONE()))
      
        //       equation
      
        //         ld = bintreeDepth(left);
      
        //       then
      
        //         ld;
      
        //
      
        //     case (TREENODE(leftSubTree = NONE(),rightSubTree = SOME(right)))
      
        //       equation
      
        //         rd = bintreeDepth(right);
      
        //       then
      
        //         rd;
      
        //   end matchcontinue;
      
        // end bintreeDepth;
      
        public function bintreeToList "author: PA
      
          This function takes a BinTree and transform it into a list
      
          representation, i.e. two lists of keys and values
      
        "
      
          input BinTree inBinTree;
      
          output list<Key> outKeyLst;
      
          output list<Value> outValueLst;
      
        algorithm
      
          (outKeyLst,outValueLst):=
      
          matchcontinue inBinTree
      
            local
      
              list<Key> klst;
      
              list<Value> vlst;
      
              BinTree bt;
      
            case bt
      
              algorithm
      
        ✗
                (klst,vlst) := bintreeToList2(bt, {}, {});
      
              then
      
                (klst,vlst);
      
            case _
      
              algorithm
      
        ✗
                print("- BackendDAEUtil.bintreeToList failed\n");
      
        ✗
              then
      
                fail();
      
          end matchcontinue;
      
        end bintreeToList;
      
        protected function bintreeToList2 "author: PA
      
          helper function to bintreeToList"
      
          input BinTree inBinTree;
      
          input list<Key> inKeyLst;
      
          input list<Value> inValueLst;
      
          output list<Key> outKeyLst;
      
          output list<Value> outValueLst;
      
        algorithm
      
          (outKeyLst,outValueLst) := matchcontinue (inBinTree,inKeyLst,inValueLst)
      
            local
      
              list<Key> klst;
      
              list<Value> vlst;
      
              Key key;
      
              Value value;
      
              Option<BinTree> left,right;
      
            case (TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE()),klst,vlst)
      
        ✗
              then (klst,vlst);
      
            case (TREENODE(value = SOME(TREEVALUE(key=key,value=value)),leftSubTree = left,rightSubTree = right),klst,vlst)
      
              algorithm
      
        ✗
                (klst,vlst) := bintreeToListOpt(left, klst, vlst);
      
        ✗
                (klst,vlst) := bintreeToListOpt(right, klst, vlst);
      
        ✗
              then
      
                ((key :: klst),(value :: vlst));
      
            case (TREENODE(value = NONE(),leftSubTree = left),klst,vlst)
      
              algorithm
      
        ✗
                (klst,vlst) := bintreeToListOpt(left, klst, vlst);
      
        ✗
                (klst,vlst) := bintreeToListOpt(left, klst, vlst);
      
              then
      
                (klst,vlst);
      
          end matchcontinue;
      
        end bintreeToList2;
      
        protected function bintreeToListOpt "author: PA
      
          helper function to bintreeToList"
      
          input Option<BinTree> inBinTreeOption;
      
          input list<Key> inKeyLst;
      
          input list<Value> inValueLst;
      
          output list<Key> outKeyLst;
      
          output list<Value> outValueLst;
      
        algorithm
      
          (outKeyLst,outValueLst) := match (inBinTreeOption,inKeyLst,inValueLst)
      
            local
      
              list<Key> klst;
      
              list<Value> vlst;
      
              BinTree bt;
      
        ✗
            case (NONE(),klst,vlst) then (klst,vlst);
      
            case (SOME(bt),klst,vlst)
      
              algorithm
      
        ✗
                (klst,vlst) := bintreeToList2(bt, klst, vlst);
      
              then
      
                (klst,vlst);
      
          end match;
      
        end bintreeToListOpt;
      
        annotation(__OpenModelica_Interface="backend_tools");
      
        end BinaryTreeInt;

Line	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 BinaryTreeInt
37		" file: BinaryTreeInt.mo
38		package: BinaryTreeInt
39		description: BinaryTreeInt comprises functions for BinaryTrees.
40
41
42		BinaryTree."
43
44		/**************************
45		imports
46		**************************/
47
48		protected import Error;
49		protected import Util;
50
51
52		/**************************
53		types
54		**************************/
55
56		public
57		uniontype BinTree "Generic Binary tree implementation
58		- Binary Tree"
59		record TREENODE
60		Option<TreeValue> value "Value";
61		Option<BinTree> leftSubTree "left subtree";
62		Option<BinTree> rightSubTree "right subtree";
63		end TREENODE;
64
65		end BinTree;
66
67		public
68		uniontype TreeValue "Each node in the binary tree can have a value associated with it.
69		- Tree Value"
70		record TREEVALUE
71		Key key "Key";
72		Value value "Value";
73		end TREEVALUE;
74
75		end TreeValue;
76
77		public
78		type Key = Integer "A key is a Integer";
79
80		public
81		type Value = Integer "- Value";
82
83		public constant BinTree emptyBinTree=TREENODE(NONE(),NONE(),NONE()) " Empty binary tree ";
84
85		/**************************
86		implementation
87		**************************/
88
89		protected function keyCmp
90		input Key keya;
91		input Key keyb;
92		output Integer cmp;
93		algorithm
94	✗	cmp := Util.intSign(keya-keyb);
95		end keyCmp;
96
97		public function treeGet "author: Frenkel TUD 2012-09-18
98
99		Copied from generic implementation. Changed that no hashfunction is passed
100		since a string can not be uniquely mapped to an int. Therefore we need to compare two strings
101		to get a unique ordering.
102		"
103		input BinTree bt;
104		input Key key;
105		output Value v;
106		protected
107		algorithm
108	✗	v := treeGet3(bt, key, treeGet2(bt, key));
109		end treeGet;
110
111		protected function treeGet2
112		"Helper function to treeGet"
113		input BinTree inBinTree;
114		input Key ikey;
115		output Integer compResult;
116		algorithm
117		compResult := match inBinTree
118		local
119		Key key;
120
121		// found it
122		case TREENODE(value = SOME(TREEVALUE(key=key)))
123	✗	then keyCmp(key, ikey);
124		end match;
125		end treeGet2;
126
127		protected function treeGet3
128		"Helper function to treeGet"
129		input BinTree inBinTree;
130		input Key ikey;
131		input Integer inCompResult;
132		output Value outValue;
133		algorithm
134		outValue := match (inBinTree, inCompResult)
135		local
136		Value rval;
137		BinTree right, left;
138		Integer compResult;
139
140		// found it
141		case (TREENODE(value = SOME(TREEVALUE(value=rval))), 0) then rval;
142		// search right
143		case (TREENODE(rightSubTree = SOME(right)), 1)
144		algorithm
145	✗	compResult := treeGet2(right, ikey);
146	✗	then treeGet3(right, ikey, compResult);
147		// search left
148		case (TREENODE(leftSubTree = SOME(left)), -1)
149		algorithm
150	✗	compResult := treeGet2(left, ikey);
151	✗	then treeGet3(left, ikey, compResult);
152		end match;
153		end treeGet3;
154
155		public function treeAddList "author: Frenkel TUD"
156		input BinTree inBinTree;
157		input list<Key> inKeyLst;
158		output BinTree outBinTree;
159		algorithm
160		outBinTree := match (inBinTree,inKeyLst)
161		local
162		Key key;
163		list<Key> res;
164		BinTree bt,bt_1,bt_2;
165
166		case (bt,{}) then bt;
167
168		case (bt,key::res)
169		algorithm
170	✗	bt_1 := treeAdd(bt,key,0);
171	✗	bt_2 := treeAddList(bt_1,res);
172		then
173		bt_2;
174		end match;
175		end treeAddList;
176
177		public function treeAdd "author: PA
178		Copied from generic implementation. Changed that no hashfunction is passed
179		since a string (ComponentRef) can not be uniquely mapped to an int. Therefore we need to compare two strings
180		to get a unique ordering.
181
182		Actually, hashing is still important in order to speed up comparison of strings... So it was re-added in a
183		good way, see function keyCompareNinjaSecretHashTricks"
184		input BinTree inBinTree;
185		input Key inKey;
186		input Value inValue;
187		output BinTree outBinTree;
188		algorithm
189		outBinTree := matchcontinue inBinTree
190		local
191		Key rkey;
192		Option<BinTree> left,right;
193		BinTree t_1,t,right_1,left_1;
194		Option<TreeValue> optVal;
195
196		case TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE())
197	✗	then
198		TREENODE(SOME(TREEVALUE(inKey,inValue)),NONE(),NONE());
199
200		case TREENODE(value = SOME(TREEVALUE(rkey,_)),leftSubTree = left,rightSubTree = right)
201		algorithm
202	✗	0 := keyCmp(rkey,inKey);
203	✗	then
204		TREENODE(SOME(TREEVALUE(rkey,inValue)),left,right);
205
206		case TREENODE(value = optVal as SOME(TREEVALUE(rkey,_)),leftSubTree = left,rightSubTree = (SOME(t)))
207		algorithm
208	✗	1 := keyCmp(rkey,inKey);
209	✗	t_1 := treeAdd(t, inKey, inValue);
210	✗	then
211		TREENODE(optVal,left,SOME(t_1));
212
213		case TREENODE(value = optVal as SOME(TREEVALUE(rkey,_)),leftSubTree = left,rightSubTree = (NONE()))
214		algorithm
215	✗	1 := keyCmp(rkey,inKey);
216	✗	right_1 := treeAdd(TREENODE(NONE(),NONE(),NONE()), inKey, inValue);
217	✗	then
218		TREENODE(optVal,left,SOME(right_1));
219
220		case TREENODE(value = optVal as SOME(TREEVALUE(rkey,_)),leftSubTree = (SOME(t)),rightSubTree = right)
221		algorithm
222	✗	-1 := keyCmp(rkey,inKey);
223	✗	t_1 := treeAdd(t, inKey, inValue);
224	✗	then
225		TREENODE(optVal,SOME(t_1),right);
226
227		case TREENODE(value = optVal as SOME(TREEVALUE(rkey,_)),leftSubTree = (NONE()),rightSubTree = right)
228		algorithm
229	✗	-1 := keyCmp(rkey,inKey);
230	✗	left_1 := treeAdd(TREENODE(NONE(),NONE(),NONE()), inKey, inValue);
231	✗	then
232		TREENODE(optVal,SOME(left_1),right);
233
234		else
235		algorithm
236	✗	Error.addMessage(Error.INTERNAL_ERROR,{"- BinaryTreeInt.treeAdd failed\n"});
237	✗	then
238		fail();
239		end matchcontinue;
240		end treeAdd;
241
242		// protected function treeDelete2 "author: PA
243		// This function deletes an entry from the BinTree."
244		// input BinTree inBinTree;
245		// input Integer inKey;
246		// output BinTree outBinTree;
247		// algorithm
248		// outBinTree := matchcontinue (inBinTree,inKey)
249		// local
250		// BinTree bt,right,left,t;
251		// Key key,rkey;
252		// TreeValue rightmost;
253		// Option<BinTree> optRight,optLeft,optTree;
254		// Value rval;
255		// Option<TreeValue> optVal;
256		// Integer rhash;
257		//
258		// case ((bt as TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE())),_)
259		// then bt;
260		//
261		// case (TREENODE(value = SOME(TREEVALUE(rkey,rval)),leftSubTree = optLeft,rightSubTree = SOME(right)),_)
262		// equation
263		// 0 = keyCmp(rkey, inKey);
264		// (rightmost,right) = treeDeleteRightmostValue(right);
265		// optRight = treePruneEmptyNodes(right);
266		// then
267		// TREENODE(SOME(rightmost),optLeft,optRight);
268		//
269		// case (TREENODE(value = SOME(TREEVALUE(rkey,rval)),leftSubTree = SOME(left as TREENODE(value=_)),rightSubTree = NONE()),_)
270		// equation
271		// 0 = keyCmp(rkey, inKey);
272		// then
273		// left;
274		//
275		// case (TREENODE(value = SOME(TREEVALUE(rkey,rval)),leftSubTree = NONE(),rightSubTree = NONE()),_)
276		// equation
277		// 0 = keyCmp(rkey, inKey);
278		// then
279		// TREENODE(NONE(),NONE(),NONE());
280		//
281		// case (TREENODE(value = optVal as SOME(TREEVALUE(rkey,rval)),leftSubTree = optLeft,rightSubTree = SOME(t)),_)
282		// equation
283		// 1 = keyCmp(rkey, inKey);
284		// t = treeDelete2(t, inKey);
285		// optTree = treePruneEmptyNodes(t);
286		// then
287		// TREENODE(optVal,optLeft,optTree);
288		//
289		// case (TREENODE(value = optVal as SOME(TREEVALUE(rkey,rval)),leftSubTree = SOME(t),rightSubTree = optRight),_)
290		// equation
291		// -1 = keyCmp(rkey, inKey);
292		// t = treeDelete2(t, inKey);
293		// optTree = treePruneEmptyNodes(t);
294		// then
295		// TREENODE(optVal,optTree,optRight);
296		//
297		// else
298		// equation
299		// Error.addMessage(Error.INTERNAL_ERROR,{"-BinaryTree.treeDelete failed\n"});
300		// then
301		// fail();
302		// end matchcontinue;
303		// end treeDelete2;
304
305		// protected function treeDeleteRightmostValue "author: PA
306		// This function takes a BinTree and deletes the rightmost value of the tree.
307		// Tt returns this value and the updated BinTree. This function is used in
308		// the binary tree deletion function \'tree_delete\'.
309		// inputs: (BinTree)
310		// outputs: (TreeValue, /* deleted value */
311		// BinTree /* updated bintree */)
312		// "
313		// input BinTree inBinTree;
314		// output TreeValue outTreeValue;
315		// output BinTree outBinTree;
316		// algorithm
317		// (outTreeValue,outBinTree) := matchcontinue (inBinTree)
318		// local
319		// TreeValue treeVal,value;
320		// BinTree left,right,bt;
321		// Option<BinTree> optRight, optLeft;
322		// Option<TreeValue> optTreeVal;
323		//
324		// case (TREENODE(value = SOME(treeVal),leftSubTree = NONE(),rightSubTree = NONE()))
325		// then (treeVal,TREENODE(NONE(),NONE(),NONE()));
326		//
327		// case (TREENODE(value = SOME(treeVal),leftSubTree = SOME(left),rightSubTree = NONE()))
328		// then (treeVal,left);
329		//
330		// case (TREENODE(value = optTreeVal,leftSubTree = optLeft,rightSubTree = SOME(right)))
331		// equation
332		// (value,right) = treeDeleteRightmostValue(right);
333		// optRight = treePruneEmptyNodes(right);
334		// then
335		// (value,TREENODE(optTreeVal,optLeft,optRight));
336		//
337		// case (TREENODE(value = SOME(treeVal),leftSubTree = NONE(),rightSubTree = SOME(right)))
338		// equation
339		// failure((_,_) = treeDeleteRightmostValue(right));
340		// print("- BinaryTree.treeDeleteRightmostValue: right value was empty, left NONE\n");
341		// then
342		// (treeVal,TREENODE(NONE(),NONE(),NONE()));
343		//
344		// else
345		// equation
346		// Error.addMessage(Error.INTERNAL_ERROR,{"- BinaryTree.treeDeleteRightmostValue failed\n"});
347		// then
348		// fail();
349		// end matchcontinue;
350		// end treeDeleteRightmostValue;
351
352		// protected function treePruneEmptyNodes "author: PA
353		// This function is a helper function to tree_delete
354		// It is used to delete empty nodes of the BinTree
355		// representation, that might be introduced when deleting nodes."
356		// input BinTree inBinTree;
357		// output Option<BinTree> outBinTreeOption;
358		// algorithm
359		// outBinTreeOption := matchcontinue (inBinTree)
360		// local BinTree bt;
361		// case TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE()) then NONE();
362		// case bt then SOME(bt);
363		// end matchcontinue;
364		// end treePruneEmptyNodes;
365
366		// protected function bintreeDepth "author: PA
367		// This function calculates the depth of the Binary Tree given
368		// as input. It can be used for debugging purposes to investigate
369		// how balanced binary trees are."
370		// input BinTree inBinTree;
371		// output Integer outInteger;
372		// algorithm
373		// outInteger := matchcontinue (inBinTree)
374		// local
375		// Value ld,rd,res;
376		// BinTree left,right;
377		//
378		// case (TREENODE(leftSubTree = NONE(),rightSubTree = NONE())) then 1;
379		//
380		// case (TREENODE(leftSubTree = SOME(left),rightSubTree = SOME(right)))
381		// equation
382		// ld = bintreeDepth(left);
383		// rd = bintreeDepth(right);
384		// res = intMax(ld, rd);
385		// then
386		// res + 1;
387		//
388		// case (TREENODE(leftSubTree = SOME(left),rightSubTree = NONE()))
389		// equation
390		// ld = bintreeDepth(left);
391		// then
392		// ld;
393		//
394		// case (TREENODE(leftSubTree = NONE(),rightSubTree = SOME(right)))
395		// equation
396		// rd = bintreeDepth(right);
397		// then
398		// rd;
399		// end matchcontinue;
400		// end bintreeDepth;
401
402
403		public function bintreeToList "author: PA
404
405		This function takes a BinTree and transform it into a list
406		representation, i.e. two lists of keys and values
407		"
408		input BinTree inBinTree;
409		output list<Key> outKeyLst;
410		output list<Value> outValueLst;
411		algorithm
412		(outKeyLst,outValueLst):=
413		matchcontinue inBinTree
414		local
415		list<Key> klst;
416		list<Value> vlst;
417		BinTree bt;
418		case bt
419		algorithm
420	✗	(klst,vlst) := bintreeToList2(bt, {}, {});
421		then
422		(klst,vlst);
423		case _
424		algorithm
425	✗	print("- BackendDAEUtil.bintreeToList failed\n");
426	✗	then
427		fail();
428		end matchcontinue;
429		end bintreeToList;
430
431		protected function bintreeToList2 "author: PA
432		helper function to bintreeToList"
433		input BinTree inBinTree;
434		input list<Key> inKeyLst;
435		input list<Value> inValueLst;
436		output list<Key> outKeyLst;
437		output list<Value> outValueLst;
438		algorithm
439		(outKeyLst,outValueLst) := matchcontinue (inBinTree,inKeyLst,inValueLst)
440		local
441		list<Key> klst;
442		list<Value> vlst;
443		Key key;
444		Value value;
445		Option<BinTree> left,right;
446
447		case (TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE()),klst,vlst)
448	✗	then (klst,vlst);
449
450		case (TREENODE(value = SOME(TREEVALUE(key=key,value=value)),leftSubTree = left,rightSubTree = right),klst,vlst)
451		algorithm
452	✗	(klst,vlst) := bintreeToListOpt(left, klst, vlst);
453	✗	(klst,vlst) := bintreeToListOpt(right, klst, vlst);
454	✗	then
455		((key :: klst),(value :: vlst));
456
457		case (TREENODE(value = NONE(),leftSubTree = left),klst,vlst)
458		algorithm
459	✗	(klst,vlst) := bintreeToListOpt(left, klst, vlst);
460	✗	(klst,vlst) := bintreeToListOpt(left, klst, vlst);
461		then
462		(klst,vlst);
463		end matchcontinue;
464		end bintreeToList2;
465
466		protected function bintreeToListOpt "author: PA
467		helper function to bintreeToList"
468		input Option<BinTree> inBinTreeOption;
469		input list<Key> inKeyLst;
470		input list<Value> inValueLst;
471		output list<Key> outKeyLst;
472		output list<Value> outValueLst;
473		algorithm
474		(outKeyLst,outValueLst) := match (inBinTreeOption,inKeyLst,inValueLst)
475		local
476		list<Key> klst;
477		list<Value> vlst;
478		BinTree bt;
479
480	✗	case (NONE(),klst,vlst) then (klst,vlst);
481
482		case (SOME(bt),klst,vlst)
483		algorithm
484	✗	(klst,vlst) := bintreeToList2(bt, klst, vlst);
485		then
486		(klst,vlst);
487		end match;
488		end bintreeToListOpt;
489
490		annotation(__OpenModelica_Interface="backend_tools");
491		end BinaryTreeInt;
492