OMCompiler/Compiler/Util/PriorityQueue.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 PriorityQueue | ||
| 37 | " file: PriorityQueue.mo | ||
| 38 | package: PriorityQueue | ||
| 39 | description: ADT PriorityQueue | ||
| 40 | |||
| 41 | |||
| 42 | This data-structure is based on Brodal and Okasaki (1996) | ||
| 43 | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 | ||
| 44 | |||
| 45 | It uses a binomial heap with reasonable efficiency. It could | ||
| 46 | be made faster like in the paper by adding some additional information | ||
| 47 | to the data-type. | ||
| 48 | |||
| 49 | Note that we can make this a very general module if we have a bootstrapped | ||
| 50 | compiler. RML takes all the joy out of writing code. | ||
| 51 | |||
| 52 | TODO: Improve the efficiency as in the paper: | ||
| 53 | TODO: Implement getMin() in O(1) time | ||
| 54 | TODO: Implement insert() in O(1) time | ||
| 55 | TODO: Implement meld() in O(1) time | ||
| 56 | " | ||
| 57 | |||
| 58 | public import SimCode; | ||
| 59 | |||
| 60 | public | ||
| 61 | /* protected */ | ||
| 62 | /* TODO: Hide when RML is killed */ | ||
| 63 | |||
| 64 | /* This specific version... */ | ||
| 65 | replaceable type Priority = Integer; | ||
| 66 | replaceable type Data = list<SimCode.SimEqSystem>; | ||
| 67 | |||
| 68 | /* Replaceable types */ | ||
| 69 | |||
| 70 | replaceable function compareElement | ||
| 71 | input Element el1; | ||
| 72 | input Element el2; | ||
| 73 | output Boolean b; | ||
| 74 | protected | ||
| 75 | Priority p1,p2; | ||
| 76 | algorithm | ||
| 77 | ✗ | (p1,_) := el1; | |
| 78 | ✗ | (p2,_) := el2; | |
| 79 | ✗ | b := p1 <= p2; | |
| 80 | end compareElement; | ||
| 81 | |||
| 82 | public | ||
| 83 | |||
| 84 | replaceable type Element = tuple<Priority,Data>; | ||
| 85 | type T = list<Tree>; | ||
| 86 | |||
| 87 | constant T empty = {}; | ||
| 88 | |||
| 89 | /* | ||
| 90 | function isEmpty = listEmpty; | ||
| 91 | */ | ||
| 92 | function isEmpty | ||
| 93 | input T ts; | ||
| 94 | output Boolean isEmpty; | ||
| 95 | algorithm | ||
| 96 | ✗ | isEmpty := listEmpty(ts); | |
| 97 | end isEmpty; | ||
| 98 | |||
| 99 | function insert | ||
| 100 | input Element elt; | ||
| 101 | input T ts; | ||
| 102 | output T ots; | ||
| 103 | algorithm | ||
| 104 | ✗ | ots := ins(NODE(elt,0,{}),ts); | |
| 105 | end insert; | ||
| 106 | |||
| 107 | function meld | ||
| 108 | input T its1; | ||
| 109 | input T its2; | ||
| 110 | output T ts; | ||
| 111 | algorithm | ||
| 112 | ts := match (its1,its2) | ||
| 113 | local | ||
| 114 | Tree t1,t2; | ||
| 115 | T ts1,ts2; | ||
| 116 | case (ts1,{}) then ts1; | ||
| 117 | case ({},ts2) then ts2; | ||
| 118 | ✗ | case (t1::ts1,t2::ts2) then meld2(rank(t1) < rank(t2),rank(t2) < rank(t1),t1,ts1,t2,ts2); | |
| 119 | end match; | ||
| 120 | end meld; | ||
| 121 | |||
| 122 | function meld2 | ||
| 123 | input Boolean b1; | ||
| 124 | input Boolean b2; | ||
| 125 | input Tree t1; | ||
| 126 | input T inTs1; | ||
| 127 | input Tree t2; | ||
| 128 | input T inTs2; | ||
| 129 | output T ts; | ||
| 130 | algorithm | ||
| 131 | ts := match (b1, b2, inTs1, inTs2) | ||
| 132 | local | ||
| 133 | T ts1,ts2; | ||
| 134 | |||
| 135 | case (true, _, ts1, ts2) | ||
| 136 | algorithm | ||
| 137 | ✗ | ts := meld(ts1,t2::ts2); | |
| 138 | then t1::ts; | ||
| 139 | case (_, true, ts1, ts2) | ||
| 140 | algorithm | ||
| 141 | ✗ | ts := meld(t1::ts1,ts2); | |
| 142 | then t2::ts; | ||
| 143 | ✗ | else ins(link(t1,t2), meld(inTs1,inTs2)); | |
| 144 | end match; | ||
| 145 | end meld2; | ||
| 146 | |||
| 147 | function findMin | ||
| 148 | input T inTs; | ||
| 149 | output Element elt; | ||
| 150 | algorithm | ||
| 151 | elt := match inTs | ||
| 152 | local | ||
| 153 | Tree t; | ||
| 154 | Element x,y; | ||
| 155 | T ts; | ||
| 156 | |||
| 157 | case {t} then root(t); | ||
| 158 | case t::ts | ||
| 159 | algorithm | ||
| 160 | x := root(t); | ||
| 161 | ✗ | y := findMin(ts); | |
| 162 | ✗ | then if compareElement(x,y) then x else y; | |
| 163 | end match; | ||
| 164 | end findMin; | ||
| 165 | |||
| 166 | function deleteMin | ||
| 167 | input T ts; | ||
| 168 | output T ots; | ||
| 169 | protected | ||
| 170 | T ts1,ts2; | ||
| 171 | algorithm | ||
| 172 | ✗ | (NODE(trees=ts1),ts2) := getMin(ts); | |
| 173 | ✗ | ots := meld(listReverse(ts1),ts2); | |
| 174 | end deleteMin; | ||
| 175 | |||
| 176 | function deleteAndReturnMin | ||
| 177 | input T ts; | ||
| 178 | output T ots; | ||
| 179 | output Element elt; | ||
| 180 | protected | ||
| 181 | T ts1,ts2; | ||
| 182 | algorithm | ||
| 183 | ✗ | (NODE(elt=elt,trees=ts1),ts2) := getMin(ts); | |
| 184 | ✗ | ots := meld(listReverse(ts1),ts2); | |
| 185 | end deleteAndReturnMin; | ||
| 186 | |||
| 187 | function elements | ||
| 188 | input T ts; | ||
| 189 | output list<Element> elts; | ||
| 190 | algorithm | ||
| 191 | ✗ | elts := elements2(ts,{}); | |
| 192 | end elements; | ||
| 193 | |||
| 194 | function elements2 | ||
| 195 | input T its; | ||
| 196 | input list<Element> acc; | ||
| 197 | output list<Element> elts; | ||
| 198 | algorithm | ||
| 199 | elts := match its | ||
| 200 | local | ||
| 201 | Element elt; | ||
| 202 | T ts; | ||
| 203 | ✗ | case {} then listReverse(acc); | |
| 204 | case ts | ||
| 205 | algorithm | ||
| 206 | ✗ | (ts,elt) := deleteAndReturnMin(ts); | |
| 207 | ✗ | then elements2(ts,elt::acc); | |
| 208 | end match; | ||
| 209 | end elements2; | ||
| 210 | |||
| 211 | /* TODO: Hide from user when we remove RML... */ | ||
| 212 | |||
| 213 | type Rank = Integer; | ||
| 214 | |||
| 215 | uniontype Tree | ||
| 216 | record NODE | ||
| 217 | Element elt; | ||
| 218 | Rank rank; | ||
| 219 | T trees; | ||
| 220 | end NODE; | ||
| 221 | end Tree; | ||
| 222 | |||
| 223 | protected | ||
| 224 | |||
| 225 | function root | ||
| 226 | input Tree tree; | ||
| 227 | output Element elt; | ||
| 228 | algorithm | ||
| 229 | ✗ | NODE(elt=elt) := tree; | |
| 230 | end root; | ||
| 231 | |||
| 232 | function rank | ||
| 233 | input Tree tree; | ||
| 234 | output Rank rank; | ||
| 235 | algorithm | ||
| 236 | ✗ | NODE(rank=rank) := tree; | |
| 237 | end rank; | ||
| 238 | |||
| 239 | function link | ||
| 240 | input Tree t1; | ||
| 241 | input Tree t2; | ||
| 242 | output Tree t; | ||
| 243 | algorithm | ||
| 244 | t := match (t1,t2) | ||
| 245 | local | ||
| 246 | Element e1,e2; | ||
| 247 | Rank r1,r2; | ||
| 248 | T ts1,ts2; | ||
| 249 | case (NODE(e1,r1,ts1),NODE(e2,r2,ts2)) | ||
| 250 | algorithm | ||
| 251 | ✗ | r1 := r1+1; | |
| 252 | ✗ | r2 := r2+1; | |
| 253 | ts1 := t2::ts1; | ||
| 254 | ts2 := t1::ts2; | ||
| 255 | ✗ | then if compareElement(root(t1),root(t2)) then NODE(e1,r1,ts1) else NODE(e2,r2,ts2); | |
| 256 | end match; | ||
| 257 | end link; | ||
| 258 | |||
| 259 | function ins | ||
| 260 | input Tree t; | ||
| 261 | input T its; | ||
| 262 | output T ots; | ||
| 263 | algorithm | ||
| 264 | ots := match (t,its) | ||
| 265 | local | ||
| 266 | Tree t1,t2; | ||
| 267 | T ts; | ||
| 268 | case (_,{}) then {t}; | ||
| 269 | ✗ | case (t1,t2::ts) then if rank(t1) < rank(t2) then t1::t2::ts else ins(link(t1,t2),ts); | |
| 270 | end match; | ||
| 271 | end ins; | ||
| 272 | |||
| 273 | function getMin | ||
| 274 | input T ts; | ||
| 275 | output Tree min; | ||
| 276 | output T ots; | ||
| 277 | algorithm | ||
| 278 | (min,ots) := match ts | ||
| 279 | local | ||
| 280 | Tree t,t1,t2; | ||
| 281 | T ts1,ts2; | ||
| 282 | Boolean b; | ||
| 283 | case {t} then (t,{}); | ||
| 284 | case t1::ts1 | ||
| 285 | algorithm | ||
| 286 | ✗ | (t2,ts2) := getMin(ts1); | |
| 287 | ✗ | b := compareElement(root(t1),root(t2)); | |
| 288 | ✗ | then (if b then t1 else t2, if b then ts1 else t1::ts2); | |
| 289 | end match; | ||
| 290 | end getMin; | ||
| 291 | |||
| 292 | annotation(__OpenModelica_Interface="backend"); | ||
| 293 | end PriorityQueue; | ||
| 294 |