OMCompiler/Compiler/BackEnd/BinaryTree.mo - Linux GNU 11.4.0 Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	82.2%	37 / 0 / 45
Functions:	-%	0 / 1 / 1
Branches:	83.3%	10 / 0 / 12

    OMCompiler/Compiler/BackEnd/BinaryTree.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 BinaryTree
      
        " file:        BinaryTree.mo
      
          package:     BinaryTree
      
          description: BinaryTree comprises functions for BinaryTrees.
      
          BinaryTree."
      
        /**************************
      
          imports
      
         **************************/
      
        public import DAE;
      
        protected import BaseHashTable;
      
        protected import ComponentReference;
      
        protected import ComponentReferenceBasics;
      
        protected import Error;
      
        protected import List;
      
        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";
      
            String str;
      
            Integer hash;
      
            Value value "Value";
      
          end TREEVALUE;
      
        end TreeValue;
      
        public
      
        type Key = .DAE.ComponentRef "A key is a Component Reference";
      
        public
      
        type Value = Integer "- Value";
      
        public constant BinTree emptyBinTree=TREENODE(NONE(),NONE(),NONE()) " Empty binary tree ";
      
        /**************************
      
          implementation
      
         **************************/
      
        protected function keyCompareNinjaSecretHashTricks
      
          "Super ninja secret that allows you to implement a binary tree based on the hash of strings.
      
          And only do string comparisons for those rare conflicts (we use 63-bit integers, so conflicts should be
      
          very, very rare)"
      
          input String lstr;
      
          input Integer lhash;
      
          input String rstr;
      
          input Integer rhash;
      
          output Integer cmp;
      
        algorithm
      
        952296
          cmp := Util.intSign(lhash-rhash);
      
          2/2✓ Branch 0 taken 101826 times.
✓ Branch 1 taken 850470 times.

        952296
          cmp := if cmp == 0 then stringCompare(lstr, rstr) else cmp;
      
        end keyCompareNinjaSecretHashTricks;
      
        public function treeGet "author: PA
      
          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
      
          String keystr;
      
          Integer keyhash;
      
        algorithm
      
        147531
          keystr := ComponentReferenceBasics.printComponentRefStr(key);
      
        147531
          keyhash := stringHashDjb2Mod(keystr,BaseHashTable.hugeBucketSize);
      
        147531
          v := treeGet3(bt, keystr, keyhash, treeGet2(bt, keystr, keyhash));
      
        end treeGet;
      
        protected function treeGet2
      
          "Helper function to treeGet"
      
          input BinTree inBinTree;
      
          input String keystr;
      
          input Integer keyhash;
      
          output Integer compResult;
      
        algorithm
      
          compResult := match inBinTree
      
            local
      
              String rkeystr;
      
              Integer rkeyhash;
      
            // found it
      
            case TREENODE(value = SOME(TREEVALUE(str=rkeystr,hash=rkeyhash)))
      
        351623
              then keyCompareNinjaSecretHashTricks(rkeystr, rkeyhash, keystr, keyhash);
      
          end match;
      
        end treeGet2;
      
        protected function treeGet3
      
          "Helper function to treeGet"
      
          input BinTree inBinTree;
      
          input String keystr;
      
          input Integer keyhash;
      
          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
      
        73298
                compResult := treeGet2(right, keystr, keyhash);
      
        73298
              then treeGet3(right, keystr, keyhash, compResult);
      
            // search left
      
            case (TREENODE(leftSubTree = SOME(left)), -1)
      
              algorithm
      
        151122
                compResult := treeGet2(left, keystr, keyhash);
      
        151122
              then treeGet3(left, keystr, keyhash, 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;
      
        protected
      
          String str;
      
        algorithm
      
        123993
          str := ComponentReferenceBasics.printComponentRefStr(inKey);
      
          // We use modulo hashes in order to avoid problems with boxing/unboxing of integers in bootstrapped OMC
      
        123993
          outBinTree := treeAdd2(inBinTree,inKey,stringHashDjb2Mod(str,BaseHashTable.hugeBucketSize),str,inValue);
      
        end treeAdd;
      
        protected function treeAdd2 "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."
      
          input BinTree inBinTree;
      
          input Key inKey;
      
          input Integer keyhash;
      
          input String keystr;
      
          input Value inValue;
      
          output BinTree outBinTree;
      
        algorithm
      
          outBinTree := matchcontinue (inBinTree, inKey, inValue)
      
            local
      
              DAE.ComponentRef key,rkey;
      
              Value value;
      
              String rkeystr;
      
              Option<BinTree> left,right;
      
              BinTree t_1,t,right_1,left_1;
      
              Integer rhash;
      
              Option<TreeValue> optVal;
      
            case (TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE()), key, value)
      
        195700
              then
      
                TREENODE(SOME(TREEVALUE(key,keystr,keyhash,value)),NONE(),NONE());
      
            case (TREENODE(value = SOME(TREEVALUE(rkey,rkeystr,rhash,_)),leftSubTree = left,rightSubTree = right), _, value)
      
              algorithm
      
          2/2✓ Branch 1 taken 223713 times.
✓ Branch 2 taken 26143 times.

        249856
                0 := keyCompareNinjaSecretHashTricks(rkeystr,rhash,keystr,keyhash);
      
        52286
              then
      
                TREENODE(SOME(TREEVALUE(rkey,rkeystr,rhash,value)),left,right);
      
            case (TREENODE(value = optVal as SOME(TREEVALUE(_,rkeystr,rhash,_)),leftSubTree = left,rightSubTree = (SOME(t))), key, value)
      
              algorithm
      
          2/2✓ Branch 1 taken 49358 times.
✓ Branch 2 taken 57992 times.

        107350
                1 := keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
      
        57992
                t_1 := treeAdd2(t, key, keyhash, keystr, value);
      
        57992
              then
      
                TREENODE(optVal,left,SOME(t_1));
      
            case (TREENODE(value = optVal as SOME(TREEVALUE(_,rkeystr,rhash,_)),leftSubTree = left,rightSubTree = (NONE())), key, value)
      
              algorithm
      
          2/2✓ Branch 1 taken 77746 times.
✓ Branch 2 taken 38617 times.

        116363
                1 := keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
      
        38617
                right_1 := treeAdd2(TREENODE(NONE(),NONE(),NONE()), key, keyhash, keystr, value);
      
        38617
              then
      
                TREENODE(optVal,left,SOME(right_1));
      
            case (TREENODE(value = optVal as SOME(TREEVALUE(_,rkeystr,rhash,_)),leftSubTree = (SOME(t)),rightSubTree = right), key, value)
      
              algorithm
      
          1/2✗ Branch 1 not taken.
✓ Branch 2 taken 87793 times.

        87793
                -1 := keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
      
        87793
                t_1 := treeAdd2(t, key, keyhash, keystr, value);
      
        87793
              then
      
                TREENODE(optVal,SOME(t_1),right);
      
            case (TREENODE(value = optVal as SOME(TREEVALUE(_,rkeystr,rhash,_)),leftSubTree = (NONE()),rightSubTree = right), key, value)
      
              algorithm
      
          1/2✗ Branch 1 not taken.
✓ Branch 2 taken 39311 times.

        39311
                -1 := keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
      
        39311
                left_1 := treeAdd2(TREENODE(NONE(),NONE(),NONE()), key, keyhash, keystr, value);
      
        39311
              then
      
                TREENODE(optVal,SOME(left_1),right);
      
            else
      
              algorithm
      
        ✗
                Error.addMessage(Error.INTERNAL_ERROR,{"- BinaryTree.treeAdd2 failed\n"});
      
        ✗
              then
      
                fail();
      
          end matchcontinue;
      
        end treeAdd2;
      
        // protected function treeDelete2 "author: PA
      
        //   This function deletes an entry from the BinTree."
      
        //   input BinTree inBinTree;
      
        //   input String keystr;
      
        //   input Integer keyhash;
      
        //   output BinTree outBinTree;
      
        // algorithm
      
        //   outBinTree := matchcontinue (inBinTree,keystr,keyhash)
      
        //     local
      
        //       BinTree bt,right,left,t;
      
        //       DAE.ComponentRef key,rkey;
      
        //       String rkeystr;
      
        //       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,rkeystr,rhash,rval)),leftSubTree = optLeft,rightSubTree = SOME(right)),_,_)
      
        //       equation
      
        //         0 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
      
        //         (rightmost,right) = treeDeleteRightmostValue(right);
      
        //         optRight = treePruneEmptyNodes(right);
      
        //       then
      
        //         TREENODE(SOME(rightmost),optLeft,optRight);
      
        //
      
        //     case (TREENODE(value = SOME(TREEVALUE(rkey,rkeystr,rhash,rval)),leftSubTree = SOME(left as TREENODE(value=_)),rightSubTree = NONE()),_,_)
      
        //       equation
      
        //         0 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
      
        //       then
      
        //         left;
      
        //
      
        //     case (TREENODE(value = SOME(TREEVALUE(rkey,rkeystr,rhash,rval)),leftSubTree = NONE(),rightSubTree = NONE()),_,_)
      
        //       equation
      
        //         0 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
      
        //       then
      
        //         TREENODE(NONE(),NONE(),NONE());
      
        //
      
        //     case (TREENODE(value = optVal as SOME(TREEVALUE(rkey,rkeystr,rhash,rval)),leftSubTree = optLeft,rightSubTree = SOME(t)),_,_)
      
        //       equation
      
        //         1 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
      
        //         t = treeDelete2(t, keystr, keyhash);
      
        //         optTree = treePruneEmptyNodes(t);
      
        //       then
      
        //         TREENODE(optVal,optLeft,optTree);
      
        //
      
        //     case (TREENODE(value = optVal as SOME(TREEVALUE(rkey,rkeystr,rhash,rval)),leftSubTree =  SOME(t),rightSubTree = optRight),_,_)
      
        //       equation
      
        //         -1 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
      
        //         t = treeDelete2(t, keystr, keyhash);
      
        //         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;
      
            case _
      
              algorithm
      
        11145
                (klst,vlst) := bintreeToList2(inBinTree, {}, {});
      
              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
      
            local
      
              list<Key> klst;
      
              list<Value> vlst;
      
              DAE.ComponentRef key;
      
              Value value;
      
              Option<BinTree> left,right;
      
            case TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE())
      
        2252
              then (inKeyLst,inValueLst);
      
            case TREENODE(value = SOME(TREEVALUE(key=key,value=value)),leftSubTree = left,rightSubTree = right)
      
              algorithm
      
        49884
                (klst,vlst) := bintreeToListOpt(left, key::inKeyLst, value::inValueLst);
      
        49884
                (klst,vlst) := bintreeToListOpt(right, klst, vlst);
      
              then
      
                (klst,vlst);
      
            case TREENODE(value = NONE(),leftSubTree = left)
      
              algorithm
      
        ✗
                (klst,vlst) := bintreeToListOpt(left, inKeyLst, inValueLst);
      
        ✗
                (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
      
            local
      
              list<Key> klst;
      
              list<Value> vlst;
      
              BinTree bt;
      
        58777
            case NONE() then (inKeyLst,inValueLst);
      
            case SOME(bt)
      
              algorithm
      
        40991
                (klst,vlst) := bintreeToList2(bt, inKeyLst,inValueLst);
      
              then
      
                (klst,vlst);
      
          end match;
      
        end bintreeToListOpt;
      
        public function binTreeintersection
      
        "Author: Frenkel TUD 2012-09
      
          at all key member of bt1 and bt2 to iBt"
      
          input BinTree bt1;
      
          input BinTree bt2;
      
          input BinTree iBt;
      
          output BinTree oBt;
      
        protected
      
          list<DAE.ComponentRef> keys;
      
        algorithm
      
        11145
          (keys,_) := bintreeToList(bt1);
      
        11145
          oBt := List.fold1(keys, binTreeintersection1, bt2,iBt);
      
        end binTreeintersection;
      
        protected function binTreeintersection1
      
        "Author: Frenkel TUD 2012-09
      
          Helper for binTreeintersection1"
      
          input DAE.ComponentRef key;
      
          input BinTree bt2;
      
          input BinTree iBt;
      
          output BinTree oBt;
      
        algorithm
      
          oBt := matchcontinue iBt
      
            local
      
             BinTree bt;
      
            case _
      
              algorithm
      
        49884
                treeGet(bt2,key);
      
        30928
                bt := treeAdd(iBt,key,0);
      
              then
      
                bt;
      
            else iBt;
      
          end matchcontinue;
      
        end binTreeintersection1;
      
        annotation(__OpenModelica_Interface="backend");
      
        end BinaryTree;

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 BinaryTree
37			" file: BinaryTree.mo
38			package: BinaryTree
39			description: BinaryTree comprises functions for BinaryTrees.
40
41
42			BinaryTree."
43
44			/**************************
45			imports
46			**************************/
47
48			public import DAE;
49
50			protected import BaseHashTable;
51			protected import ComponentReference;
52			protected import ComponentReferenceBasics;
53			protected import Error;
54			protected import List;
55			protected import Util;
56
57
58			/**************************
59			types
60			**************************/
61
62			public
63			uniontype BinTree "Generic Binary tree implementation
64			- Binary Tree"
65			record TREENODE
66			Option<TreeValue> value "Value";
67			Option<BinTree> leftSubTree "left subtree";
68			Option<BinTree> rightSubTree "right subtree";
69			end TREENODE;
70
71			end BinTree;
72
73			public
74			uniontype TreeValue "Each node in the binary tree can have a value associated with it.
75			- Tree Value"
76			record TREEVALUE
77			Key key "Key";
78			String str;
79			Integer hash;
80			Value value "Value";
81			end TREEVALUE;
82
83			end TreeValue;
84
85			public
86			type Key = .DAE.ComponentRef "A key is a Component Reference";
87
88			public
89			type Value = Integer "- Value";
90
91			public constant BinTree emptyBinTree=TREENODE(NONE(),NONE(),NONE()) " Empty binary tree ";
92
93			/**************************
94			implementation
95			**************************/
96
97			protected function keyCompareNinjaSecretHashTricks
98			"Super ninja secret that allows you to implement a binary tree based on the hash of strings.
99			And only do string comparisons for those rare conflicts (we use 63-bit integers, so conflicts should be
100			very, very rare)"
101			input String lstr;
102			input Integer lhash;
103			input String rstr;
104			input Integer rhash;
105			output Integer cmp;
106			algorithm
107		952296	cmp := Util.intSign(lhash-rhash);
108	2/2 ✓ Branch 0 taken 101826 times. ✓ Branch 1 taken 850470 times.	952296	cmp := if cmp == 0 then stringCompare(lstr, rstr) else cmp;
109			end keyCompareNinjaSecretHashTricks;
110
111			public function treeGet "author: PA
112
113			Copied from generic implementation. Changed that no hashfunction is passed
114			since a string can not be uniquely mapped to an int. Therefore we need to compare two strings
115			to get a unique ordering.
116			"
117			input BinTree bt;
118			input Key key;
119			output Value v;
120			protected
121			String keystr;
122			Integer keyhash;
123			algorithm
124		147531	keystr := ComponentReferenceBasics.printComponentRefStr(key);
125		147531	keyhash := stringHashDjb2Mod(keystr,BaseHashTable.hugeBucketSize);
126		147531	v := treeGet3(bt, keystr, keyhash, treeGet2(bt, keystr, keyhash));
127			end treeGet;
128
129			protected function treeGet2
130			"Helper function to treeGet"
131			input BinTree inBinTree;
132			input String keystr;
133			input Integer keyhash;
134			output Integer compResult;
135			algorithm
136			compResult := match inBinTree
137			local
138			String rkeystr;
139			Integer rkeyhash;
140
141			// found it
142			case TREENODE(value = SOME(TREEVALUE(str=rkeystr,hash=rkeyhash)))
143		351623	then keyCompareNinjaSecretHashTricks(rkeystr, rkeyhash, keystr, keyhash);
144			end match;
145			end treeGet2;
146
147			protected function treeGet3
148			"Helper function to treeGet"
149			input BinTree inBinTree;
150			input String keystr;
151			input Integer keyhash;
152			input Integer inCompResult;
153			output Value outValue;
154			algorithm
155			outValue := match (inBinTree, inCompResult)
156			local
157			Value rval;
158			BinTree right, left;
159			Integer compResult;
160
161			// found it
162			case (TREENODE(value = SOME(TREEVALUE(value=rval))), 0) then rval;
163			// search right
164			case (TREENODE(rightSubTree = SOME(right)), 1)
165			algorithm
166		73298	compResult := treeGet2(right, keystr, keyhash);
167		73298	then treeGet3(right, keystr, keyhash, compResult);
168			// search left
169			case (TREENODE(leftSubTree = SOME(left)), -1)
170			algorithm
171		151122	compResult := treeGet2(left, keystr, keyhash);
172		151122	then treeGet3(left, keystr, keyhash, compResult);
173			end match;
174			end treeGet3;
175
176			public function treeAddList "author: Frenkel TUD"
177			input BinTree inBinTree;
178			input list<Key> inKeyLst;
179			output BinTree outBinTree;
180			algorithm
181			outBinTree := match (inBinTree,inKeyLst)
182			local
183			Key key;
184			list<Key> res;
185			BinTree bt,bt_1,bt_2;
186
187			case (bt,{}) then bt;
188
189			case (bt,key::res)
190			algorithm
191		✗	bt_1 := treeAdd(bt,key,0);
192		✗	bt_2 := treeAddList(bt_1,res);
193			then
194			bt_2;
195			end match;
196			end treeAddList;
197
198			public function treeAdd "author: PA
199			Copied from generic implementation. Changed that no hashfunction is passed
200			since a string (ComponentRef) can not be uniquely mapped to an int. Therefore we need to compare two strings
201			to get a unique ordering.
202
203			Actually, hashing is still important in order to speed up comparison of strings... So it was re-added in a
204			good way, see function keyCompareNinjaSecretHashTricks"
205			input BinTree inBinTree;
206			input Key inKey;
207			input Value inValue;
208			output BinTree outBinTree;
209			protected
210			String str;
211			algorithm
212		123993	str := ComponentReferenceBasics.printComponentRefStr(inKey);
213			// We use modulo hashes in order to avoid problems with boxing/unboxing of integers in bootstrapped OMC
214		123993	outBinTree := treeAdd2(inBinTree,inKey,stringHashDjb2Mod(str,BaseHashTable.hugeBucketSize),str,inValue);
215			end treeAdd;
216
217			protected function treeAdd2 "author: PA
218			Copied from generic implementation. Changed that no hashfunction is passed
219			since a string (ComponentRef) can not be uniquely mapped to an int. Therefore we need to compare two strings
220			to get a unique ordering."
221			input BinTree inBinTree;
222			input Key inKey;
223			input Integer keyhash;
224			input String keystr;
225			input Value inValue;
226			output BinTree outBinTree;
227			algorithm
228			outBinTree := matchcontinue (inBinTree, inKey, inValue)
229			local
230			DAE.ComponentRef key,rkey;
231			Value value;
232			String rkeystr;
233			Option<BinTree> left,right;
234			BinTree t_1,t,right_1,left_1;
235			Integer rhash;
236			Option<TreeValue> optVal;
237
238			case (TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE()), key, value)
239		195700	then
240			TREENODE(SOME(TREEVALUE(key,keystr,keyhash,value)),NONE(),NONE());
241
242			case (TREENODE(value = SOME(TREEVALUE(rkey,rkeystr,rhash,_)),leftSubTree = left,rightSubTree = right), _, value)
243			algorithm
244	2/2 ✓ Branch 1 taken 223713 times. ✓ Branch 2 taken 26143 times.	249856	0 := keyCompareNinjaSecretHashTricks(rkeystr,rhash,keystr,keyhash);
245		52286	then
246			TREENODE(SOME(TREEVALUE(rkey,rkeystr,rhash,value)),left,right);
247
248			case (TREENODE(value = optVal as SOME(TREEVALUE(_,rkeystr,rhash,_)),leftSubTree = left,rightSubTree = (SOME(t))), key, value)
249			algorithm
250	2/2 ✓ Branch 1 taken 49358 times. ✓ Branch 2 taken 57992 times.	107350	1 := keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
251		57992	t_1 := treeAdd2(t, key, keyhash, keystr, value);
252		57992	then
253			TREENODE(optVal,left,SOME(t_1));
254
255			case (TREENODE(value = optVal as SOME(TREEVALUE(_,rkeystr,rhash,_)),leftSubTree = left,rightSubTree = (NONE())), key, value)
256			algorithm
257	2/2 ✓ Branch 1 taken 77746 times. ✓ Branch 2 taken 38617 times.	116363	1 := keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
258		38617	right_1 := treeAdd2(TREENODE(NONE(),NONE(),NONE()), key, keyhash, keystr, value);
259		38617	then
260			TREENODE(optVal,left,SOME(right_1));
261
262			case (TREENODE(value = optVal as SOME(TREEVALUE(_,rkeystr,rhash,_)),leftSubTree = (SOME(t)),rightSubTree = right), key, value)
263			algorithm
264	1/2 ✗ Branch 1 not taken. ✓ Branch 2 taken 87793 times.	87793	-1 := keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
265		87793	t_1 := treeAdd2(t, key, keyhash, keystr, value);
266		87793	then
267			TREENODE(optVal,SOME(t_1),right);
268
269			case (TREENODE(value = optVal as SOME(TREEVALUE(_,rkeystr,rhash,_)),leftSubTree = (NONE()),rightSubTree = right), key, value)
270			algorithm
271	1/2 ✗ Branch 1 not taken. ✓ Branch 2 taken 39311 times.	39311	-1 := keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
272		39311	left_1 := treeAdd2(TREENODE(NONE(),NONE(),NONE()), key, keyhash, keystr, value);
273		39311	then
274			TREENODE(optVal,SOME(left_1),right);
275
276			else
277			algorithm
278		✗	Error.addMessage(Error.INTERNAL_ERROR,{"- BinaryTree.treeAdd2 failed\n"});
279		✗	then
280			fail();
281			end matchcontinue;
282			end treeAdd2;
283
284			// protected function treeDelete2 "author: PA
285			// This function deletes an entry from the BinTree."
286			// input BinTree inBinTree;
287			// input String keystr;
288			// input Integer keyhash;
289			// output BinTree outBinTree;
290			// algorithm
291			// outBinTree := matchcontinue (inBinTree,keystr,keyhash)
292			// local
293			// BinTree bt,right,left,t;
294			// DAE.ComponentRef key,rkey;
295			// String rkeystr;
296			// TreeValue rightmost;
297			// Option<BinTree> optRight,optLeft,optTree;
298			// Value rval;
299			// Option<TreeValue> optVal;
300			// Integer rhash;
301			//
302			// case ((bt as TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE())),_,_)
303			// then bt;
304			//
305			// case (TREENODE(value = SOME(TREEVALUE(rkey,rkeystr,rhash,rval)),leftSubTree = optLeft,rightSubTree = SOME(right)),_,_)
306			// equation
307			// 0 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
308			// (rightmost,right) = treeDeleteRightmostValue(right);
309			// optRight = treePruneEmptyNodes(right);
310			// then
311			// TREENODE(SOME(rightmost),optLeft,optRight);
312			//
313			// case (TREENODE(value = SOME(TREEVALUE(rkey,rkeystr,rhash,rval)),leftSubTree = SOME(left as TREENODE(value=_)),rightSubTree = NONE()),_,_)
314			// equation
315			// 0 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
316			// then
317			// left;
318			//
319			// case (TREENODE(value = SOME(TREEVALUE(rkey,rkeystr,rhash,rval)),leftSubTree = NONE(),rightSubTree = NONE()),_,_)
320			// equation
321			// 0 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
322			// then
323			// TREENODE(NONE(),NONE(),NONE());
324			//
325			// case (TREENODE(value = optVal as SOME(TREEVALUE(rkey,rkeystr,rhash,rval)),leftSubTree = optLeft,rightSubTree = SOME(t)),_,_)
326			// equation
327			// 1 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
328			// t = treeDelete2(t, keystr, keyhash);
329			// optTree = treePruneEmptyNodes(t);
330			// then
331			// TREENODE(optVal,optLeft,optTree);
332			//
333			// case (TREENODE(value = optVal as SOME(TREEVALUE(rkey,rkeystr,rhash,rval)),leftSubTree = SOME(t),rightSubTree = optRight),_,_)
334			// equation
335			// -1 = keyCompareNinjaSecretHashTricks(rkeystr, rhash, keystr, keyhash);
336			// t = treeDelete2(t, keystr, keyhash);
337			// optTree = treePruneEmptyNodes(t);
338			// then
339			// TREENODE(optVal,optTree,optRight);
340			//
341			// else
342			// equation
343			// Error.addMessage(Error.INTERNAL_ERROR,{"-BinaryTree.treeDelete failed\n"});
344			// then
345			// fail();
346			// end matchcontinue;
347			// end treeDelete2;
348
349			// protected function treeDeleteRightmostValue "author: PA
350			// This function takes a BinTree and deletes the rightmost value of the tree.
351			// Tt returns this value and the updated BinTree. This function is used in
352			// the binary tree deletion function \'tree_delete\'.
353			// inputs: (BinTree)
354			// outputs: (TreeValue, /* deleted value */
355			// BinTree /* updated bintree */)
356			// "
357			// input BinTree inBinTree;
358			// output TreeValue outTreeValue;
359			// output BinTree outBinTree;
360			// algorithm
361			// (outTreeValue,outBinTree) := matchcontinue (inBinTree)
362			// local
363			// TreeValue treeVal,value;
364			// BinTree left,right,bt;
365			// Option<BinTree> optRight, optLeft;
366			// Option<TreeValue> optTreeVal;
367			//
368			// case (TREENODE(value = SOME(treeVal),leftSubTree = NONE(),rightSubTree = NONE()))
369			// then (treeVal,TREENODE(NONE(),NONE(),NONE()));
370			//
371			// case (TREENODE(value = SOME(treeVal),leftSubTree = SOME(left),rightSubTree = NONE()))
372			// then (treeVal,left);
373			//
374			// case (TREENODE(value = optTreeVal,leftSubTree = optLeft,rightSubTree = SOME(right)))
375			// equation
376			// (value,right) = treeDeleteRightmostValue(right);
377			// optRight = treePruneEmptyNodes(right);
378			// then
379			// (value,TREENODE(optTreeVal,optLeft,optRight));
380			//
381			// case (TREENODE(value = SOME(treeVal),leftSubTree = NONE(),rightSubTree = SOME(right)))
382			// equation
383			// failure((_,_) = treeDeleteRightmostValue(right));
384			// print("- BinaryTree.treeDeleteRightmostValue: right value was empty, left NONE\n");
385			// then
386			// (treeVal,TREENODE(NONE(),NONE(),NONE()));
387			//
388			// else
389			// equation
390			// Error.addMessage(Error.INTERNAL_ERROR,{"- BinaryTree.treeDeleteRightmostValue failed\n"});
391			// then
392			// fail();
393			// end matchcontinue;
394			// end treeDeleteRightmostValue;
395
396			// protected function treePruneEmptyNodes "author: PA
397			// This function is a helper function to tree_delete
398			// It is used to delete empty nodes of the BinTree
399			// representation, that might be introduced when deleting nodes."
400			// input BinTree inBinTree;
401			// output Option<BinTree> outBinTreeOption;
402			// algorithm
403			// outBinTreeOption := matchcontinue (inBinTree)
404			// local BinTree bt;
405			// case TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE()) then NONE();
406			// case bt then SOME(bt);
407			// end matchcontinue;
408			// end treePruneEmptyNodes;
409
410			// protected function bintreeDepth "author: PA
411			// This function calculates the depth of the Binary Tree given
412			// as input. It can be used for debugging purposes to investigate
413			// how balanced binary trees are."
414			// input BinTree inBinTree;
415			// output Integer outInteger;
416			// algorithm
417			// outInteger := matchcontinue (inBinTree)
418			// local
419			// Value ld,rd,res;
420			// BinTree left,right;
421			//
422			// case (TREENODE(leftSubTree = NONE(),rightSubTree = NONE())) then 1;
423			//
424			// case (TREENODE(leftSubTree = SOME(left),rightSubTree = SOME(right)))
425			// equation
426			// ld = bintreeDepth(left);
427			// rd = bintreeDepth(right);
428			// res = intMax(ld, rd);
429			// then
430			// res + 1;
431			//
432			// case (TREENODE(leftSubTree = SOME(left),rightSubTree = NONE()))
433			// equation
434			// ld = bintreeDepth(left);
435			// then
436			// ld;
437			//
438			// case (TREENODE(leftSubTree = NONE(),rightSubTree = SOME(right)))
439			// equation
440			// rd = bintreeDepth(right);
441			// then
442			// rd;
443			// end matchcontinue;
444			// end bintreeDepth;
445
446
447			public function bintreeToList "author: PA
448
449			This function takes a BinTree and transform it into a list
450			representation, i.e. two lists of keys and values
451			"
452			input BinTree inBinTree;
453			output list<Key> outKeyLst;
454			output list<Value> outValueLst;
455			algorithm
456			(outKeyLst,outValueLst):=
457			matchcontinue inBinTree
458			local
459			list<Key> klst;
460			list<Value> vlst;
461			case _
462			algorithm
463		11145	(klst,vlst) := bintreeToList2(inBinTree, {}, {});
464			then
465			(klst,vlst);
466			case _
467			algorithm
468		✗	print("- BackendDAEUtil.bintreeToList failed\n");
469		✗	then
470			fail();
471			end matchcontinue;
472			end bintreeToList;
473
474			protected function bintreeToList2 "author: PA
475			helper function to bintreeToList"
476			input BinTree inBinTree;
477			input list<Key> inKeyLst;
478			input list<Value> inValueLst;
479			output list<Key> outKeyLst;
480			output list<Value> outValueLst;
481			algorithm
482			(outKeyLst,outValueLst) := matchcontinue inBinTree
483			local
484			list<Key> klst;
485			list<Value> vlst;
486			DAE.ComponentRef key;
487			Value value;
488			Option<BinTree> left,right;
489
490			case TREENODE(value = NONE(),leftSubTree = NONE(),rightSubTree = NONE())
491		2252	then (inKeyLst,inValueLst);
492
493			case TREENODE(value = SOME(TREEVALUE(key=key,value=value)),leftSubTree = left,rightSubTree = right)
494			algorithm
495		49884	(klst,vlst) := bintreeToListOpt(left, key::inKeyLst, value::inValueLst);
496		49884	(klst,vlst) := bintreeToListOpt(right, klst, vlst);
497			then
498			(klst,vlst);
499
500			case TREENODE(value = NONE(),leftSubTree = left)
501			algorithm
502		✗	(klst,vlst) := bintreeToListOpt(left, inKeyLst, inValueLst);
503		✗	(klst,vlst) := bintreeToListOpt(left, klst, vlst);
504			then
505			(klst,vlst);
506			end matchcontinue;
507			end bintreeToList2;
508
509			protected function bintreeToListOpt "author: PA
510			helper function to bintreeToList"
511			input Option<BinTree> inBinTreeOption;
512			input list<Key> inKeyLst;
513			input list<Value> inValueLst;
514			output list<Key> outKeyLst;
515			output list<Value> outValueLst;
516			algorithm
517			(outKeyLst,outValueLst) := match inBinTreeOption
518			local
519			list<Key> klst;
520			list<Value> vlst;
521			BinTree bt;
522
523		58777	case NONE() then (inKeyLst,inValueLst);
524
525			case SOME(bt)
526			algorithm
527		40991	(klst,vlst) := bintreeToList2(bt, inKeyLst,inValueLst);
528			then
529			(klst,vlst);
530			end match;
531			end bintreeToListOpt;
532
533			public function binTreeintersection
534			"Author: Frenkel TUD 2012-09
535			at all key member of bt1 and bt2 to iBt"
536			input BinTree bt1;
537			input BinTree bt2;
538			input BinTree iBt;
539			output BinTree oBt;
540			protected
541			list<DAE.ComponentRef> keys;
542			algorithm
543		11145	(keys,_) := bintreeToList(bt1);
544		11145	oBt := List.fold1(keys, binTreeintersection1, bt2,iBt);
545			end binTreeintersection;
546
547			protected function binTreeintersection1
548			"Author: Frenkel TUD 2012-09
549			Helper for binTreeintersection1"
550			input DAE.ComponentRef key;
551			input BinTree bt2;
552			input BinTree iBt;
553			output BinTree oBt;
554			algorithm
555			oBt := matchcontinue iBt
556			local
557			BinTree bt;
558			case _
559			algorithm
560		49884	treeGet(bt2,key);
561		30928	bt := treeAdd(iBt,key,0);
562			then
563			bt;
564			else iBt;
565			end matchcontinue;
566			end binTreeintersection1;
567
568			annotation(__OpenModelica_Interface="backend");
569			end BinaryTree;
570