1%---------------------------------------------------------------------------% 2% Copyright (C) 1994-1997, 1999-2000 The University of Melbourne. 3% Copyright (C) 2000 Imperial College London. 4% This file may only be copied under the terms of the GNU Library General 5% Public License - see the file COPYING.LIB. 6%---------------------------------------------------------------------------% 7 8% m_tree234 - implements a map (dictionary) using 2-3-4 trees. 9% main author: conway@cs.mu.OZ.AU. 10% stability: medium. 11 12% Modified for ECLiPSe by Warwick Harvey <wh@icparc.ic.ac.uk>, April 2000, 13% based on revision 1.28 of file mercury/library/tree234.m from the 14% Mercury CVS repository. See http://www.cs.mu.oz.au/mercury for 15% information about obtaining Mercury. 16 17% The conversion included stripping out the functional versions of 18% predicates and the higher-order predicates. It also included providing 19% user-level documentation. 20 21% Note that the elimination of choicepoints in the ECLiPSe version was done 22% semi-automatically; hence the names of the introduced predicates are not 23% particularly imaginitive. 24 25% This module assumes that keys are ground (so they can't be modified after 26% insertion into the tree), but allows the values stored to be variables. 27 28%---------------------------------------------------------------------------% 29 30:- module(m_tree234). 31 32:- export 33 init/1, 34 is_empty/1, 35 member/3, 36 search/3, 37 lookup/3, 38 lower_bound_search/4, 39 lower_bound_lookup/4, 40 upper_bound_search/4, 41 upper_bound_lookup/4, 42 insert/4, 43 set/4, 44 delete/3, 45 remove/4, 46 remove_smallest/4, 47 keys/2, 48 values/2, 49 update/4, 50 count/2, 51 assoc_list_to_tree234/2, 52 tree234_to_assoc_list/2. 53 54:- comment(categories, ["Data Structures"]). 55:- comment(summary, "A map (dictionary) implemented using 2-3-4 trees"). 56:- comment(author, "Thomas Conway (Mercury) and Warwick Harvey (ECLiPSe)"). 57:- comment(desc, html("\ 58 <P> 59 This module implements 2-3-4 trees. They can be used to manage and 60 index a collection of key/value pairs. You probably want to use the 61 interface provided by `map.pl' instead of using this module 62 directly. 63 </P> 64 <P> 65 Note that keys must be ground, but values are allowed to be 66 variables. 67 </P> 68 ")). 69 70% :- pred init(tree234(K, V)). 71% :- mode init(uo) is det. 72:- comment(init/1, [ 73 amode: init(-), 74 args: ["Tree":"The new tree"], 75 summary: "Initialise a new (empty) 2-3-4 tree.", 76 fail_if: "Never fails.", 77 resat: no, 78 see_also: [is_empty/1] 79]). 80 81% :- pred is_empty(tree234(K, V)). 82% :- mode is_empty(in) is semidet. 83:- comment(is_empty/1, [ 84 amode: is_empty(+), 85 args: ["Tree":"A 2-3-4 tree"], 86 summary: "Check whether a tree is empty.", 87 fail_if: "Fails if Tree is not an empty tree.", 88 resat: no, 89 see_also: [init/1] 90]). 91 92% :- pred member(tree234(K, V), K, V). 93% :- mode member(in, out, out) is nondet. 94:- comment(member/3, [ 95 amode: member(+, ?, ?), 96 args: ["Tree":"A 2-3-4 tree", 97 "Key":"A key from Tree", 98 "Value":"The value in Tree corresponding to Key"], 99 summary: "Succeeds if Key and Value unify with a key/value pair from Tree.", 100 fail_if: "Fails if Key and Value do not unify with a key/value pair from Tree.", 101 resat: yes, 102 see_also: [search/3, lookup/3], 103 desc: html("\ 104 <P> 105 Tries to unify Key and Value with key/value pairs from the tree Tree. 106 </P> 107 <P> 108 If Key and Value are variables and Tree is a 2-3-4 tree, then all 109 members of the tree Tree are found on backtracking. 110 </P> 111 <P> 112 This predicate should only be called with trees created by other 113 predicates from the tree234 module. 114 </P> 115 ") 116]). 117 118% :- pred search(tree234(K, V), K, V). 119% :- mode search(in, in, out) is semidet. 120:- comment(search/3, [ 121 amode: search(+, ++, ?), 122 args: ["Tree":"A 2-3-4 tree", 123 "Key":"A key to search for", 124 "Value":"The value corresponding to Key"], 125 summary: "Search a tree for a key.", 126 fail_if: "Fails if Key does not appear in Tree or if Value does not unify with the corresponding value found.", 127 resat: no, 128 see_also: [member/3, lookup/3], 129 desc: html("\ 130 <P> 131 This predicate searches the tree Tree for an entry with key Key. 132 If the key is found, then it attempts to unify the corresponding 133 value with Value. 134 </P> 135 <P> 136 This predicate should only be called with trees created by other 137 predicates from the tree234 module. 138 </P> 139 ") 140]). 141 142% :- pred lookup(tree234(K, V), K, V). 143% :- mode lookup(in, in, out) is det. 144:- comment(lookup/3, [ 145 amode: lookup(+, ++, ?), 146 args: ["Tree":"A 2-3-4 tree", 147 "Key":"A key to search for", 148 "Value":"The value corresponding to Key"], 149 summary: "Search a tree for a key.", 150 fail_if: "Fails if Value does not unify with the value corresponding to Key.", 151 resat: no, 152 see_also: [member/3, search/3], 153 desc: html("\ 154 <P> 155 This predicate searches the tree Tree for an entry with key Key. 156 If the key is found, then it attempts to unify the corresponding 157 value with Value. If the key is not found, then it aborts with 158 a runtime error. 159 </P> 160 <P> 161 This predicate should only be called with trees created by other 162 predicates from the tree234 module. 163 </P> 164 ") 165]). 166 167% :- pred lower_bound_search(tree234(K, V), K, K, V). 168% :- mode lower_bound_search(in, in, out, out) is semidet. 169:- comment(lower_bound_search/4, [ 170 amode: lower_bound_search(+, ++, ?, ?), 171 args: ["Tree":"A 2-3-4 tree", 172 "SearchKey":"A key to search for", 173 "Key":"The key found", 174 "Value":"The value corresponding to Key"], 175 summary: "Search a tree for the smallest key no smaller than SearchKey.", 176 fail_if: "Fails if there are no keys at least as large as SearchKey in Tree or if Key and Value do not unify with the key and value found.", 177 resat: no, 178 see_also: [lower_bound_lookup/4, 179 upper_bound_search/4, 180 upper_bound_lookup/4], 181 desc: html("\ 182 <P> 183 This predicate searches the tree Tree for the entry with the 184 smallest key which is no smaller than SearchKey. If such a key is 185 found, then it attempts to unify it with Key and the corresponding 186 value with Value. 187 </P> 188 <P> 189 This predicate should only be called with trees created by other 190 predicates from the tree234 module. 191 </P> 192 ") 193]). 194 195% :- pred lower_bound_lookup(tree234(K, V), K, K, V). 196% :- mode lower_bound_lookup(in, in, out, out) is det. 197:- comment(lower_bound_lookup/4, [ 198 amode: lower_bound_lookup(+, ++, ?, ?), 199 args: ["Tree":"A 2-3-4 tree", 200 "SearchKey":"A key to search for", 201 "Key":"The key found", 202 "Value":"The value corresponding to Key"], 203 summary: "Search a tree for the smallest key no smaller than SearchKey.", 204 fail_if: "Fails if Key and Value do not unify with the key and value found.", 205 resat: no, 206 see_also: [lower_bound_search/4, 207 upper_bound_search/4, 208 upper_bound_lookup/4], 209 desc: html("\ 210 <P> 211 This predicate searches the tree Tree for the entry with the 212 smallest key which is no smaller than SearchKey. If such a key is 213 found, then it attempts to unify it with Key and the corresponding 214 value with Value. If such a key is not found, then it aborts with 215 a runtime error. 216 </P> 217 <P> 218 This predicate should only be called with trees created by other 219 predicates from the tree234 module. 220 </P> 221 ") 222]). 223 224% :- pred upper_bound_search(tree234(K, V), K, K, V). 225% :- mode upper_bound_search(in, in, out, out) is semidet. 226:- comment(upper_bound_search/4, [ 227 amode: upper_bound_search(+, ++, ?, ?), 228 args: ["Tree":"A 2-3-4 tree", 229 "SearchKey":"A key to search for", 230 "Key":"The key found", 231 "Value":"The value corresponding to Key"], 232 summary: "Search a tree for the largest key no larger than SearchKey.", 233 fail_if: "Fails if there are no keys at least as large as SearchKey in Tree or if Key and Value do not unify with the key and value found.", 234 resat: no, 235 see_also: [lower_bound_search/4, 236 lower_bound_lookup/4, 237 upper_bound_lookup/4], 238 desc: html("\ 239 <P> 240 This predicate searches the tree Tree for the entry with the 241 largest key which is no larger than SearchKey. If such a key is 242 found, then it attempts to unify it with Key and the corresponding 243 value with Value. 244 </P> 245 <P> 246 This predicate should only be called with trees created by other 247 predicates from the tree234 module. 248 </P> 249 ") 250]). 251 252% :- pred upper_bound_lookup(tree234(K, V), K, K, V). 253% :- mode upper_bound_lookup(in, in, out, out) is det. 254:- comment(upper_bound_lookup/4, [ 255 amode: upper_bound_lookup(+, ++, ?, ?), 256 args: ["Tree":"A 2-3-4 tree", 257 "SearchKey":"A key to search for", 258 "Key":"The key found", 259 "Value":"The value corresponding to Key"], 260 summary: "Search a tree for the largest key no larger than SearchKey.", 261 fail_if: "Fails if Key and Value do not unify with the key and value found.", 262 resat: no, 263 see_also: [lower_bound_search/4, 264 lower_bound_lookup/4, 265 upper_bound_search/4], 266 desc: html("\ 267 <P> 268 This predicate searches the tree Tree for the entry with the 269 largest key which is no larger than SearchKey. If such a key is 270 found, then it attempts to unify it with Key and the corresponding 271 value with Value. If such a key is not found, then it aborts with 272 a runtime error. 273 </P> 274 <P> 275 This predicate should only be called with trees created by other 276 predicates from the tree234 module. 277 </P> 278 ") 279]). 280 281% :- pred insert(tree234(K, V), K, V, tree234(K, V)). 282% :- mode insert(in, in, in, out) is semidet. 283% % :- mode insert(di_tree234, in, in, uo_tree234) is semidet. 284% % :- mode insert(in, in, in, out) is semidet. 285:- comment(insert/4, [ 286 amode: insert(+, ++, ?, -), 287 args: ["Tree0":"A 2-3-4 tree", 288 "Key":"A key to insert", 289 "Value":"The value corresponding to Key", 290 "Tree":"The tree after insertion"], 291 summary: "Insert a key/value pair into a tree, failing if the key already exists.", 292 fail_if: "Fails if Key already appears in Tree0.", 293 resat: no, 294 see_also: [update/4, set/4], 295 desc: html("\ 296 <P> 297 This predicate inserts the key Key with corresponding value Value 298 into the tree Tree0, resulting in the tree Tree. If the key Key is 299 already in the tree, then the predicate fails. 300 </P> 301 <P> 302 This predicate should only be called with trees created by other 303 predicates from the tree234 module. 304 </P> 305 ") 306]). 307 308% :- pred set(tree234(K, V), K, V, tree234(K, V)). 309% :- mode set(di, di, di, uo) is det. 310% % :- mode set(di_tree234, in, in, uo_tree234) is det. 311% :- mode set(in, in, in, out) is det. 312:- comment(set/4, [ 313 amode: set(+, ++, ?, -), 314 args: ["Tree0":"A 2-3-4 tree", 315 "Key":"A key to set", 316 "Value":"The value corresponding to Key", 317 "Tree":"The tree after setting"], 318 summary: "Update the value corresponding to a key in a tree, inserting the key if it doesn't exist already.", 319 fail_if: "Never fails.", 320 resat: no, 321 see_also: [insert/4, update/4], 322 desc: html("\ 323 <P> 324 If the key Key already exists in the tree Tree0, then this predicate 325 updates the corresponding value to be Value. Otherwise it inserts 326 the key Key into the tree with value Value. The resulting tree is 327 Tree. 328 </P> 329 <P> 330 This predicate should only be called with trees created by other 331 predicates from the tree234 module. 332 </P> 333 ") 334]). 335 336% :- pred delete(tree234(K, V), K, tree234(K, V)). 337% :- mode delete(di, in, uo) is det. 338% % :- mode delete(di_tree234, in, uo_tree234) is det. 339% :- mode delete(in, in, out) is det. 340:- comment(delete/3, [ 341 amode: delete(+, ++, -), 342 args: ["Tree0":"A 2-3-4 tree", 343 "Key":"The key to delete", 344 "Tree":"The tree after deletion"], 345 summary: "Delete a key/value pair from a tree.", 346 fail_if: "Never fails.", 347 resat: no, 348 see_also: [remove/4], 349 desc: html("\ 350 <P> 351 If the key Key appears in the tree Tree0, then remove it and its 352 corresponding value, resulting in the tree Tree. If the key Key 353 does not appear, Tree is simply bound to Tree0. 354 </P> 355 <P> 356 This predicate should only be called with trees created by other 357 predicates from the tree234 module. 358 </P> 359 ") 360]). 361 362% :- pred remove(tree234(K, V), K, V, tree234(K, V)). 363% :- mode remove(di, in, uo, uo) is semidet. 364% % :- mode remove(di_tree234, in, out, uo_tree234) is semidet. 365% :- mode remove(in, in, out, out) is semidet. 366:- comment(remove/4, [ 367 amode: remove(+, ++, ?, -), 368 args: ["Tree0":"A 2-3-4 tree", 369 "Key":"The key to remove", 370 "Value":"The value corresponding to Key", 371 "Tree":"The tree after removal"], 372 summary: "Remove a key/value pair from a tree, failing if the key is not present.", 373 fail_if: "Fails is Key does not appear in Tree0 or if Value does not unify with the corresponding value.", 374 resat: no, 375 see_also: [delete/3, remove_smallest/4], 376 desc: html("\ 377 <P> 378 If the key Key appears in the tree Tree0, then remove it and attempt 379 to unify its corresponding value with Value. Tree is Tree0 with the 380 key removed. 381 </P> 382 <P> 383 This predicate should only be called with trees created by other 384 predicates from the tree234 module. 385 </P> 386 ") 387]). 388 389% :- pred remove_smallest(tree234(K, V), K, V, tree234(K, V)). 390% :- mode remove_smallest(di, uo, uo, uo) is semidet. 391% % :- mode remove_smallest(di_tree234, out, out, uo_tree234) 392% % is semidet. 393% :- mode remove_smallest(in, out, out, out) is semidet. 394:- comment(remove_smallest/4, [ 395 amode: remove_smallest(+, ?, ?, -), 396 args: ["Tree0":"A 2-3-4 tree", 397 "Key":"The key removed", 398 "Value":"The value corresponding to Key", 399 "Tree":"The tree after removal"], 400 summary: "Remove the smallest key and its corresponding value from a tree.", 401 fail_if: "Fails if Tree0 is empty or if Key and Value do not unify with the key and value removed.", 402 resat: no, 403 see_also: [remove/4], 404 desc: html("\ 405 <P> 406 Removes the smallest key in the tree Tree0 (resulting in the 407 tree Tree), and attempts to unify the removed key with Key and 408 its corresponding value with Value. 409 </P> 410 <P> 411 This predicate should only be called with trees created by other 412 predicates from the tree234 module. 413 </P> 414 ") 415]). 416 417% :- pred keys(tree234(K, V), list(K)). 418% :- mode keys(in, out) is det. 419:- comment(keys/2, [ 420 amode: keys(+, -), 421 args: ["Tree":"A 2-3-4 tree", 422 "KeyList":"A list of all the keys from Tree"], 423 summary: "Return all the keys from a tree.", 424 fail_if: "Never fails.", 425 resat: no, 426 see_also: [values/2], 427 desc: html("\ 428 <P> 429 KeyList is a list of all the keys appearing in the tree Tree. 430 </P> 431 <P> 432 This predicate should only be called with trees created by other 433 predicates from the tree234 module. 434 </P> 435 ") 436]). 437 438% :- pred values(tree234(K, V), list(V)). 439% :- mode values(in, out) is det. 440:- comment(values/2, [ 441 amode: values(+, -), 442 args: ["Tree":"A 2-3-4 tree", 443 "ValueList":"A list of all the values from Tree"], 444 summary: "Return all the values from a tree.", 445 fail_if: "Never fails.", 446 resat: no, 447 see_also: [values/2], 448 desc: html("\ 449 <P> 450 ValueList is a list of all the values appearing in the tree Tree. 451 </P> 452 <P> 453 This predicate should only be called with trees created by other 454 predicates from the tree234 module. 455 </P> 456 ") 457]). 458 459% :- pred update(tree234(K, V), K, V, tree234(K, V)). 460% :- mode update(in, in, in, out) is semidet. 461% % :- mode update(di_tree234, in, in, uo_tree234) is det. 462% % :- mode update(di, di, di, uo) is semidet. 463:- comment(update/4, [ 464 amode: update(+, ++, ?, -), 465 args: ["Tree0":"A 2-3-4 tree", 466 "Key":"A key to update", 467 "Value":"The value corresponding to Key", 468 "Tree":"The tree after updating"], 469 summary: "Update the value corresponding to a key in a tree.", 470 fail_if: "Fails if Key does not appear in Tree0.", 471 resat: no, 472 see_also: [insert/4, set/4], 473 desc: html("\ 474 <P> 475 If the key Key already exists in the tree Tree0, then this predicate 476 updates the corresponding value to be Value. The resulting tree is 477 Tree. 478 </P> 479 <P> 480 This predicate should only be called with trees created by other 481 predicates from the tree234 module. 482 </P> 483 ") 484]). 485 486% % count the number of elements in a tree 487% :- pred count(tree234(K, V), int). 488% :- mode count(in, out) is det. 489:- comment(count/2, [ 490 amode: count(+, ?), 491 args: ["Tree":"A 2-3-4 tree", 492 "Count":"The number of elements in Tree"], 493 summary: "Count the number of elements in a tree.", 494 fail_if: "Fails if Count does not unify with the number of elements in Tree.", 495 resat: no, 496 desc: html("\ 497 <P> 498 Counts the number of elements in the tree Tree, and attempts to 499 unify the result with Count. 500 </P> 501 <P> 502 This predicate should only be called with trees created by other 503 predicates from the tree234 module. 504 </P> 505 ") 506]). 507 508% :- pred assoc_list_to_tree234(assoc_list(K, V), tree234(K, V)). 509% :- mode assoc_list_to_tree234(in, out) is det. 510:- comment(assoc_list_to_tree234/2, [ 511 amode: assoc_list_to_tree234(+, -), 512 args: ["AssocList":"A list of key-value pairs", 513 "Tree":"A 2-3-4 tree"], 514 summary: "Converts an association list into a tree.", 515 fail_if: "Never fails.", 516 resat: no, 517 see_also: [tree234_to_assoc_list/2], 518 desc: html("\ 519 <P> 520 AssocList is a list of key/value pairs of the form Key-Value, 521 and Tree is a tree containing these key/value pairs. If a key 522 appears more than once in AssocList, then its corresponding value 523 in the tree Tree will be the last one appearing in AssocList. 524 </P> 525 ") 526]). 527 528% :- pred tree234_to_assoc_list(tree234(K, V), assoc_list(K, V)). 529% :- mode tree234_to_assoc_list(in, out) is det. 530:- comment(tree234_to_assoc_list/2, [ 531 amode: tree234_to_assoc_list(+, -), 532 args: ["Tree":"A 2-3-4 tree", 533 "AssocList":"A list of the key-value pairs from Tree"], 534 summary: "Converts a tree into an association list.", 535 fail_if: "Never fails.", 536 resat: no, 537 see_also: [assoc_list_to_tree234/2], 538 desc: html("\ 539 <P> 540 AssocList is a list containing the key/value pairs from the tree 541 Tree, in the form Key-Value. 542 </P> 543 <P> 544 This predicate should only be called with trees created by other 545 predicates from the tree234 module. 546 </P> 547 ") 548]). 549 550 551%------------------------------------------------------------------------------% 552%------------------------------------------------------------------------------% 553 554% :- import_module int, require, bool, std_util. 555 556% :- type tree234(K, V) ---> 557% empty 558% ; two(K, V, tree234(K, V), tree234(K, V)) 559% ; three(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V)) 560% ; four(K, V, K, V, K, V, tree234(K, V), tree234(K, V), 561% tree234(K, V), tree234(K, V)). 562 563 564:- lib(mercury). 565 566%------------------------------------------------------------------------------% 567 568init(empty). 569 570is_empty(Tree) :- 571 Tree = empty. 572 573%------------------------------------------------------------------------------% 574 575member(empty, _K, _V) :- fail. 576member(two(K0, V0, T0, T1), K, V) :- 577 ( 578 K = K0, 579 V = V0 580 ; 581 member(T0, K, V) 582 ; 583 member(T1, K, V) 584 ). 585member(three(K0, V0, K1, V1, T0, T1, T2), K, V) :- 586 ( 587 K = K0, 588 V = V0 589 ; 590 K = K1, 591 V = V1 592 ; 593 member(T0, K, V) 594 ; 595 member(T1, K, V) 596 ; 597 member(T2, K, V) 598 ). 599member(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), K, V) :- 600 ( 601 K = K0, 602 V = V0 603 ; 604 K = K1, 605 V = V1 606 ; 607 K = K2, 608 V = V2 609 ; 610 member(T0, K, V) 611 ; 612 member(T1, K, V) 613 ; 614 member(T2, K, V) 615 ; 616 member(T3, K, V) 617 ). 618 619%------------------------------------------------------------------------------% 620 621search(T, _K, _V) :- 622 T = empty, 623 fail. 624search(T, K, V) :- 625 T = two(K0, _, _, _), 626 compare(Result, K, K0), 627 search_aux4(Result, V, K, T). 628search(T, K, V) :- 629 T = three(K0, _, _, _, _, _, _), 630 compare(Result0, K, K0), 631 search_aux5(Result0, V, K, T). 632search(T, K, V) :- 633 T = four(_, _, K1, _, _, _, _, _, _, _), 634 compare(Result1, K, K1), 635 search_aux7(Result1, V, K, T). 636 637search_aux4(Result, V, K, T) :- 638 Result = (<), 639 T = two(_, _, T0, _), 640 search(T0, K, V). 641search_aux4(Result, V, _K, T) :- 642 Result = (=), 643 T = two(_, V0, _, _), 644 V = V0. 645search_aux4(Result, V, K, T) :- 646 Result = (>), 647 T = two(_, _, _, T1), 648 search(T1, K, V). 649 650search_aux5(Result0, V, K, T) :- 651 Result0 = (<), 652 T = three(_, _, _, _, T0, _, _), 653 search(T0, K, V). 654search_aux5(Result0, V, _K, T) :- 655 Result0 = (=), 656 T = three(_, V0, _, _, _, _, _), 657 V = V0. 658search_aux5(Result0, V, K, T) :- 659 Result0 = (>), 660 T = three(_, _, K1, _, _, _, _), 661 compare(Result1, K, K1), 662 search_aux5_aux6(Result1, T, K, V). 663 664search_aux5_aux6(Result1, T, K, V) :- 665 Result1 = (<), 666 T = three(_, _, _, _, _, T1, _), 667 search(T1, K, V). 668search_aux5_aux6(Result1, T, _K, V) :- 669 Result1 = (=), 670 T = three(_, _, _, V1, _, _, _), 671 V = V1. 672search_aux5_aux6(Result1, T, K, V) :- 673 Result1 = (>), 674 T = three(_, _, _, _, _, _, T2), 675 search(T2, K, V). 676 677search_aux7(Result1, V, K, T) :- 678 Result1 = (<), 679 T = four(K0, _, _, _, _, _, _, _, _, _), 680 compare(Result0, K, K0), 681 search_aux7_aux8(Result0, T, K, V). 682search_aux7(Result1, V, _K, T) :- 683 Result1 = (=), 684 T = four(_, _, _, V1, _, _, _, _, _, _), 685 V = V1. 686search_aux7(Result1, V, K, T) :- 687 Result1 = (>), 688 T = four(_, _, _, _, K2, _, _, _, _, _), 689 compare(Result2, K, K2), 690 search_aux7_aux9(Result2, T, K, V). 691 692search_aux7_aux8(Result0, T, K, V) :- 693 Result0 = (<), 694 T = four(_, _, _, _, _, _, T0, _, _, _), 695 search(T0, K, V). 696search_aux7_aux8(Result0, T, _K, V) :- 697 Result0 = (=), 698 T = four(_, V0, _, _, _, _, _, _, _, _), 699 V = V0. 700search_aux7_aux8(Result0, T, K, V) :- 701 Result0 = (>), 702 T = four(_, _, _, _, _, _, _, T1, _, _), 703 search(T1, K, V). 704 705search_aux7_aux9(Result2, T, K, V) :- 706 Result2 = (<), 707 T = four(_, _, _, _, _, _, _, _, T2, _), 708 search(T2, K, V). 709search_aux7_aux9(Result2, T, _K, V) :- 710 Result2 = (=), 711 T = four(_, _, _, _, _, V2, _, _, _, _), 712 V = V2. 713search_aux7_aux9(Result2, T, K, V) :- 714 Result2 = (>), 715 T = four(_, _, _, _, _, _, _, _, _, T3), 716 search(T3, K, V). 717 718lookup(T, K, V) :- 719 ( search(T, K, V0) -> 720 V = V0 721 ; 722 report_lookup_error("lookup: key not found.", K, V) 723 ). 724 725%------------------------------------------------------------------------------% 726 727lower_bound_search(T, _SearchK, _K, _V) :- 728 T = empty, 729 fail. 730lower_bound_search(T, SearchK, K, V) :- 731 T = two(K0, _, _, _), 732 compare(Result, SearchK, K0), 733 lower_bound_search_aux10(Result, K0, V, K, SearchK, T). 734lower_bound_search(T, SearchK, K, V) :- 735 T = three(K0, _, _, _, _, _, _), 736 compare(Result0, SearchK, K0), 737 lower_bound_search_aux11(Result0, K0, V, K, SearchK, T). 738lower_bound_search(T, SearchK, K, V) :- 739 T = four(_, _, K1, _, _, _, _, _, _, _), 740 compare(Result1, SearchK, K1), 741 lower_bound_search_aux13(Result1, K1, V, K, SearchK, T). 742 743lower_bound_search_aux10(Result, _K0, V, K, SearchK, T) :- 744 Result = (<), 745 T = two(_, _, T0, _), 746 lower_bound_search(T0, SearchK, K, V). 747lower_bound_search_aux10(Result, _K0, V, K, SearchK, T) :- 748 Result = (=), 749 T = two(_, V0, _, _), 750 K = SearchK, 751 V = V0. 752lower_bound_search_aux10(Result, K0, V, K, SearchK, T) :- 753 Result = (>), 754 T = two(_, _, _, T1), 755 ( 756 lower_bound_search(T1, SearchK, Kp, Vp) 757 -> 758 K = Kp, 759 V = Vp 760 ; 761 T = two(_, V0, _, _), 762 K = K0, 763 V = V0 764 ). 765 766lower_bound_search_aux11(Result0, _K0, V, K, SearchK, T) :- 767 Result0 = (=), 768 T = three(_, V0, _, _, _, _, _), 769 K = SearchK, 770 V = V0. 771lower_bound_search_aux11(Result0, K0, V, K, SearchK, T) :- 772 Result0 = (>), 773 T = three(_, _, K1, _, _, _, _), 774 compare(Result1, SearchK, K1), 775 lower_bound_search_aux11_aux12(Result1, K1, T, SearchK, K, V, K0). 776 777lower_bound_search_aux11_aux12(Result1, _K1, T, SearchK, K, V, K0) :- 778 Result1 = (<), 779 T = three(_, _, _, _, _, T1, _), 780 ( 781 lower_bound_search(T1, SearchK, Kp, Vp) 782 -> 783 K = Kp, 784 V = Vp 785 ; 786 T = three(_, V0, _, _, _, _, _), 787 K = K0, 788 V = V0 789 ). 790lower_bound_search_aux11_aux12(Result1, _K1, T, SearchK, K, V, _K0) :- 791 Result1 = (=), 792 T = three(_, _, _, V1, _, _, _), 793 K = SearchK, 794 V = V1. 795lower_bound_search_aux11_aux12(Result1, K1, T, SearchK, K, V, _K0) :- 796 Result1 = (>), 797 T = three(_, _, _, _, _, _, T2), 798 ( 799 lower_bound_search(T2, SearchK, Kp, Vp) 800 -> 801 K = Kp, 802 V = Vp 803 ; 804 T = three(_, _, _, V1, _, _, _), 805 K = K1, 806 V = V1 807 ). 808 809lower_bound_search_aux13(Result1, _K1, V, K, SearchK, T) :- 810 Result1 = (<), 811 T = four(K0, _, _, _, _, _, _, _, _, _), 812 compare(Result0, SearchK, K0), 813 lower_bound_search_aux13_aux14(Result0, K0, T, SearchK, K, V). 814lower_bound_search_aux13(Result1, _K1, V, K, SearchK, T) :- 815 Result1 = (=), 816 T = four(_, _, _, V1, _, _, _, _, _, _), 817 K = SearchK, 818 V = V1. 819lower_bound_search_aux13(Result1, K1, V, K, SearchK, T) :- 820 Result1 = (>), 821 T = four(_, _, _, _, K2, _, _, _, _, _), 822 compare(Result2, SearchK, K2), 823 lower_bound_search_aux13_aux15(Result2, K2, T, SearchK, K, V, K1). 824 825lower_bound_search_aux13_aux14(Result0, _K0, T, SearchK, K, V) :- 826 Result0 = (<), 827 T = four(_, _, _, _, _, _, T0, _, _, _), 828 lower_bound_search(T0, SearchK, K, V). 829lower_bound_search_aux13_aux14(Result0, _K0, T, SearchK, K, V) :- 830 Result0 = (=), 831 T = four(_, V0, _, _, _, _, _, _, _, _), 832 K = SearchK, 833 V = V0. 834lower_bound_search_aux13_aux14(Result0, K0, T, SearchK, K, V) :- 835 Result0 = (>), 836 T = four(_, _, _, _, _, _, _, T1, _, _), 837 ( 838 lower_bound_search(T1, SearchK, Kp, Vp) 839 -> 840 K = Kp, 841 V = Vp 842 ; 843 T = four(_, V0, _, _, _, _, _, _, _, _), 844 K = K0, 845 V = V0 846 ). 847 848lower_bound_search_aux13_aux15(Result2, _K2, T, SearchK, K, V, K1) :- 849 Result2 = (<), 850 T = four(_, _, _, _, _, _, _, _, T2, _), 851 ( 852 lower_bound_search(T2, SearchK, Kp, Vp) 853 -> 854 K = Kp, 855 V = Vp 856 ; 857 T = four(_, _, _, V1, _, _, _, _, _, _), 858 K = K1, 859 V = V1 860 ). 861lower_bound_search_aux13_aux15(Result2, _K2, T, SearchK, K, V, _K1) :- 862 Result2 = (=), 863 T = four(_, _, _, _, _, V2, _, _, _, _), 864 K = SearchK, 865 V = V2. 866lower_bound_search_aux13_aux15(Result2, K2, T, SearchK, K, V, _K1) :- 867 Result2 = (>), 868 T = four(_, _, _, _, _, _, _, _, _, T3), 869 ( 870 lower_bound_search(T3, SearchK, Kp, Vp) 871 -> 872 K = Kp, 873 V = Vp 874 ; 875 T = four(_, _, _, _, _, V2, _, _, _, _), 876 K = K2, 877 V = V2 878 ). 879 880 881lower_bound_lookup(T, SearchK, K, V) :- 882 ( lower_bound_search(T, SearchK, K0, V0) -> 883 K = K0, 884 V = V0 885 ; 886 report_lookup_error("lower_bound_lookup: key not found.", 887 SearchK, V) 888 ). 889 890%------------------------------------------------------------------------------% 891 892upper_bound_search(T, _SearchK, _K, _V) :- 893 T = empty, 894 fail. 895upper_bound_search(T, SearchK, K, V) :- 896 T = two(K0, _, _, _), 897 compare(Result, SearchK, K0), 898 upper_bound_search_aux16(Result, K0, V, K, SearchK, T). 899upper_bound_search(T, SearchK, K, V) :- 900 T = three(K0, _, _, _, _, _, _), 901 compare(Result0, SearchK, K0), 902 upper_bound_search_aux17(Result0, K0, V, K, SearchK, T). 903upper_bound_search(T, SearchK, K, V) :- 904 T = four(_, _, K1, _, _, _, _, _, _, _), 905 compare(Result1, SearchK, K1), 906 upper_bound_search_aux19(Result1, K1, V, K, SearchK, T). 907 908upper_bound_search_aux16(Result, K0, V, K, SearchK, T) :- 909 Result = (<), 910 T = two(_, _, T0, _), 911 ( 912 upper_bound_search(T0, SearchK, Kp, Vp) 913 -> 914 K = Kp, 915 V = Vp 916 ; 917 T = two(_, V0, _, _), 918 K = K0, 919 V = V0 920 ). 921upper_bound_search_aux16(Result, _K0, V, K, SearchK, T) :- 922 Result = (=), 923 T = two(_, V0, _, _), 924 K = SearchK, 925 V = V0. 926upper_bound_search_aux16(Result, _K0, V, K, SearchK, T) :- 927 Result = (>), 928 T = two(_, _, _, T1), 929 upper_bound_search(T1, SearchK, K, V). 930 931upper_bound_search_aux17(Result0, K0, V, K, SearchK, T) :- 932 Result0 = (<), 933 T = three(_, _, _, _, T0, _, _), 934 ( 935 upper_bound_search(T0, SearchK, Kp, Vp) 936 -> 937 K = Kp, 938 V = Vp 939 ; 940 T = three(_, V0, _, _, _, _, _), 941 K = K0, 942 V = V0 943 ). 944upper_bound_search_aux17(Result0, _K0, V, K, SearchK, T) :- 945 Result0 = (=), 946 T = three(_, V0, _, _, _, _, _), 947 K = SearchK, 948 V = V0. 949upper_bound_search_aux17(Result0, _K0, V, K, SearchK, T) :- 950 Result0 = (>), 951 T = three(_, _, K1, _, _, _, _), 952 compare(Result1, SearchK, K1), 953 upper_bound_search_aux17_aux18(Result1, K1, T, SearchK, K, V). 954 955upper_bound_search_aux17_aux18(Result1, K1, T, SearchK, K, V) :- 956 Result1 = (<), 957 T = three(_, _, _, _, _, T1, _), 958 ( 959 upper_bound_search(T1, SearchK, Kp, Vp) 960 -> 961 K = Kp, 962 V = Vp 963 ; 964 T = three(_, _, _, V1, _, _, _), 965 K = K1, 966 V = V1 967 ). 968upper_bound_search_aux17_aux18(Result1, _K1, T, SearchK, K, V) :- 969 Result1 = (=), 970 T = three(_, _, _, V1, _, _, _), 971 K = SearchK, 972 V = V1. 973upper_bound_search_aux17_aux18(Result1, _K1, T, SearchK, K, V) :- 974 Result1 = (>), 975 T = three(_, _, _, _, _, _, T2), 976 upper_bound_search(T2, SearchK, K, V). 977 978upper_bound_search_aux19(Result1, K1, V, K, SearchK, T) :- 979 Result1 = (<), 980 T = four(K0, _, _, _, _, _, _, _, _, _), 981 compare(Result0, SearchK, K0), 982 upper_bound_search_aux19_aux20(Result0, K0, T, SearchK, K, V, K1). 983upper_bound_search_aux19(Result1, _K1, V, K, SearchK, T) :- 984 Result1 = (=), 985 T = four(_, _, _, V1, _, _, _, _, _, _), 986 K = SearchK, 987 V = V1. 988upper_bound_search_aux19(Result1, _K1, V, K, SearchK, T) :- 989 Result1 = (>), 990 T = four(_, _, _, _, K2, _, _, _, _, _), 991 compare(Result2, SearchK, K2), 992 upper_bound_search_aux19_aux21(Result2, K2, T, SearchK, K, V). 993 994upper_bound_search_aux19_aux21(Result2, K2, T, SearchK, K, V) :- 995 Result2 = (<), 996 T = four(_, _, _, _, _, _, _, _, T2, _), 997 ( 998 upper_bound_search(T2, SearchK, Kp, Vp) 999 -> 1000 K = Kp, 1001 V = Vp 1002 ; 1003 T = four(_, _, _, _, _, V2, _, _, _, _), 1004 K = K2, 1005 V = V2 1006 ). 1007upper_bound_search_aux19_aux21(Result2, _K2, T, SearchK, K, V) :- 1008 Result2 = (=), 1009 T = four(_, _, _, _, _, V2, _, _, _, _), 1010 K = SearchK, 1011 V = V2. 1012upper_bound_search_aux19_aux21(Result2, _K2, T, SearchK, K, V) :- 1013 Result2 = (>), 1014 T = four(_, _, _, _, _, _, _, _, _, T3), 1015 upper_bound_search(T3, SearchK, K, V). 1016 1017upper_bound_search_aux19_aux20(Result0, K0, T, SearchK, K, V, _K1) :- 1018 Result0 = (<), 1019 T = four(_, _, _, _, _, _, T0, _, _, _), 1020 ( 1021 upper_bound_search(T0, SearchK, Kp, Vp) 1022 -> 1023 K = Kp, 1024 V = Vp 1025 ; 1026 T = four(_, V0, _, _, _, _, _, _, _, _), 1027 K = K0, 1028 V = V0 1029 ). 1030upper_bound_search_aux19_aux20(Result0, _K0, T, SearchK, K, V, _K1) :- 1031 Result0 = (=), 1032 T = four(_, V0, _, _, _, _, _, _, _, _), 1033 K = SearchK, 1034 V = V0. 1035upper_bound_search_aux19_aux20(Result0, _K0, T, SearchK, K, V, K1) :- 1036 Result0 = (>), 1037 T = four(_, _, _, _, _, _, _, T1, _, _), 1038 ( 1039 upper_bound_search(T1, SearchK, Kp, Vp) 1040 -> 1041 K = Kp, 1042 V = Vp 1043 ; 1044 T = four(_, _, _, V1, _, _, _, _, _, _), 1045 K = K1, 1046 V = V1 1047 ). 1048 1049upper_bound_lookup(T, SearchK, K, V) :- 1050 ( upper_bound_search(T, SearchK, K0, V0) -> 1051 K = K0, 1052 V = V0 1053 ; 1054 report_lookup_error("upper_bound_lookup: key not found.", 1055 SearchK, V) 1056 ). 1057 1058%------------------------------------------------------------------------------% 1059 1060update(Tin, _K, _V, _Tout) :- 1061 Tin = empty, 1062 fail. 1063update(Tin, K, V, Tout) :- 1064 Tin = two(K0, _, _, _), 1065 compare(Result, K, K0), 1066 update_aux22(Result, K0, Tout, V, K, Tin). 1067update(Tin, K, V, Tout) :- 1068 Tin = three(K0, _, _, _, _, _, _), 1069 compare(Result0, K, K0), 1070 update_aux23(Result0, K0, Tout, V, K, Tin). 1071update(Tin, K, V, Tout) :- 1072 Tin = four(_, _, K1, _, _, _, _, _, _, _), 1073 compare(Result1, K, K1), 1074 update_aux25(Result1, K1, Tout, V, K, Tin). 1075 1076update_aux22(Result, K0, Tout, V, K, Tin) :- 1077 Result = (<), 1078 Tin = two(_, _, T0, _), 1079 update(T0, K, V, NewT0), 1080 Tin = two(_, V0, _, T1), 1081 Tout = two(K0, V0, NewT0, T1). 1082update_aux22(Result, K0, Tout, V, _K, Tin) :- 1083 Result = (=), 1084 Tin = two(_, _, T0, T1), 1085 Tout = two(K0, V, T0, T1). 1086update_aux22(Result, K0, Tout, V, K, Tin) :- 1087 Result = (>), 1088 Tin = two(_, _, _, T1), 1089 update(T1, K, V, NewT1), 1090 Tin = two(_, V0, T0, _), 1091 Tout = two(K0, V0, T0, NewT1). 1092 1093update_aux23(Result0, K0, Tout, V, K, Tin) :- 1094 Result0 = (<), 1095 Tin = three(_, _, _, _, T0, _, _), 1096 update(T0, K, V, NewT0), 1097 Tin = three(_, V0, K1, V1, _, T1, T2), 1098 Tout = three(K0, V0, K1, V1, NewT0, T1, T2). 1099update_aux23(Result0, K0, Tout, V, _K, Tin) :- 1100 Result0 = (=), 1101 Tin = three(_, _, K1, V1, T0, T1, T2), 1102 Tout = three(K0, V, K1, V1, T0, T1, T2). 1103update_aux23(Result0, K0, Tout, V, K, Tin) :- 1104 Result0 = (>), 1105 Tin = three(_, _, K1, _, _, _, _), 1106 compare(Result1, K, K1), 1107 update_aux23_aux24(Result1, K1, Tin, K, V, Tout, K0). 1108 1109update_aux23_aux24(Result1, K1, Tin, K, V, Tout, K0) :- 1110 Result1 = (<), 1111 Tin = three(_, _, _, _, _, T1, _), 1112 update(T1, K, V, NewT1), 1113 Tin = three(_, V0, _, V1, T0, _, T2), 1114 Tout = three(K0, V0, K1, V1, T0, NewT1, T2). 1115update_aux23_aux24(Result1, K1, Tin, _K, V, Tout, K0) :- 1116 Result1 = (=), 1117 Tin = three(_, V0, _, _, T0, T1, T2), 1118 Tout = three(K0, V0, K1, V, T0, T1, T2). 1119update_aux23_aux24(Result1, K1, Tin, K, V, Tout, K0) :- 1120 Result1 = (>), 1121 Tin = three(_, _, _, _, _, _, T2), 1122 update(T2, K, V, NewT2), 1123 Tin = three(_, V0, _, V1, T0, T1, _), 1124 Tout = three(K0, V0, K1, V1, T0, T1, NewT2). 1125 1126update_aux25(Result1, K1, Tout, V, K, Tin) :- 1127 Result1 = (<), 1128 Tin = four(K0, _, _, _, _, _, _, _, _, _), 1129 compare(Result0, K, K0), 1130 update_aux25_aux26(Result0, K0, Tin, K, V, Tout, K1). 1131update_aux25(Result1, K1, Tout, V, _K, Tin) :- 1132 Result1 = (=), 1133 Tin = four(K0, V0, _, _, K2, V2, T0, T1, T2, T3), 1134 Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3). 1135update_aux25(Result1, K1, Tout, V, K, Tin) :- 1136 Result1 = (>), 1137 Tin = four(_, _, _, _, K2, _, _, _, _, _), 1138 compare(Result2, K, K2), 1139 update_aux25_aux27(Result2, K2, Tin, K, V, Tout, K1). 1140 1141update_aux25_aux26(Result0, K0, Tin, K, V, Tout, K1) :- 1142 Result0 = (<), 1143 Tin = four(_, _, _, _, _, _, T0, _, _, _), 1144 update(T0, K, V, NewT0), 1145 Tin = four(_, V0, _, V1, K2, V2, _, T1, T2, T3), 1146 Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3). 1147update_aux25_aux26(Result0, K0, Tin, _K, V, Tout, K1) :- 1148 Result0 = (=), 1149 Tin = four(_, _, _, V1, K2, V2, T0, T1, T2, T3), 1150 Tout = four(K0, V, K1, V1, K2, V2, T0, T1, T2, T3). 1151update_aux25_aux26(Result0, K0, Tin, K, V, Tout, K1) :- 1152 Result0 = (>), 1153 Tin = four(_, _, _, _, _, _, _, T1, _, _), 1154 update(T1, K, V, NewT1), 1155 Tin = four(_, V0, _, V1, K2, V2, T0, _, T2, T3), 1156 Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3). 1157 1158update_aux25_aux27(Result2, K2, Tin, K, V, Tout, K1) :- 1159 Result2 = (<), 1160 Tin = four(_, _, _, _, _, _, _, _, T2, _), 1161 update(T2, K, V, NewT2), 1162 Tin = four(K0, V0, _, V1, _, V2, T0, T1, _, T3), 1163 Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3). 1164update_aux25_aux27(Result2, K2, Tin, _K, V, Tout, K1) :- 1165 Result2 = (=), 1166 Tin = four(K0, V0, _, V1, _, _, T0, T1, T2, T3), 1167 Tout = four(K0, V0, K1, V1, K2, V, T0, T1, T2, T3). 1168update_aux25_aux27(Result2, K2, Tin, K, V, Tout, K1) :- 1169 Result2 = (>), 1170 Tin = four(_, _, _, _, _, _, _, _, _, T3), 1171 update(T3, K, V, NewT3), 1172 Tin = four(K0, V0, _, V1, _, V2, T0, T1, T2, _), 1173 Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3). 1174 1175%------------------------------------------------------------------------------% 1176%------------------------------------------------------------------------------% 1177 1178% :- inst two(K, V, T) = 1179% bound( 1180% two(K, V, T, T) 1181% ). 1182% 1183% :- inst uniq_two(K, V, T) = 1184% unique( 1185% two(K, V, T, T) 1186% ). 1187% 1188% :- inst three(K, V, T) = 1189% bound( 1190% three(K, V, K, V, T, T, T) 1191% ). 1192% 1193% :- inst uniq_three(K, V, T) = 1194% unique( 1195% three(K, V, K, V, T, T, T) 1196% ). 1197% 1198% :- inst four(K, V, T) = 1199% bound( 1200% four(K, V, K, V, K, V, T, T, T, T) 1201% ). 1202% 1203% :- inst uniq_four(K, V, T) = 1204% unique( 1205% four(K, V, K, V, K, V, T, T, T, T) 1206% ). 1207% 1208% :- mode uo_two :: out(uniq_two(unique, unique, unique)). 1209% :- mode suo_two :: out(uniq_two(ground, ground, uniq_tree234_gg)). 1210% :- mode out_two :: out(two(ground, ground, ground)). 1211% 1212% :- mode di_two :: di(uniq_two(unique, unique, unique)). 1213% :- mode sdi_two :: di(uniq_two(ground, ground, uniq_tree234_gg)). 1214% :- mode in_two :: in(two(ground, ground, ground)). 1215% 1216% :- mode di_three :: di(uniq_three(unique, unique, unique)). 1217% :- mode sdi_three :: di(uniq_three(ground, ground, uniq_tree234_gg)). 1218% :- mode in_three :: in(three(ground, ground, ground)). 1219% 1220% :- mode di_four :: di(uniq_four(unique, unique, unique)). 1221% :- mode sdi_four :: di(uniq_four(ground, ground, uniq_tree234_gg)). 1222% :- mode in_four :: in(four(ground, ground, ground)). 1223 1224%------------------------------------------------------------------------------% 1225 1226% :- pred split_four(tree234(K, V), K, V, tree234(K, V), tree234(K, V)). 1227% :- mode split_four(di_four, uo, uo, uo_two, uo_two) is det. 1228% % :- mode split_four(sdi_four, out, out, suo_two, suo_two) is det. 1229% :- mode split_four(in_four, out, out, out_two, out_two) is det. 1230 1231split_four(Tin, MidK, MidV, Sub0, Sub1) :- 1232 Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 1233 Sub0 = two(K0, V0, T0, T1), 1234 MidK = K1, 1235 MidV = V1, 1236 Sub1 = two(K2, V2, T2, T3). 1237 1238%------------------------------------------------------------------------------% 1239 1240% insert is implemented using the simple top-down 1241% approach described in eg Sedgwick which splits 4 nodes into 1242% two 2 nodes on the downward traversal of the tree as we 1243% search for the right place to insert the new key-value pair. 1244% We know we have the right place if the subtrees of the node 1245% are empty (in which case we expand the node - which will always 1246% work because we already split 4 nodes into 2 nodes), or if the 1247% tree itself is empty. 1248% This algorithm is O(lgN). 1249 1250insert(Tin, K, V, Tout) :- 1251 Tin = empty, 1252 Tout = two(K, V, empty, empty). 1253insert(Tin, K, V, Tout) :- 1254 Tin = two(_, _, _, _), 1255 insert2(Tin, K, V, Tout). 1256insert(Tin, K, V, Tout) :- 1257 Tin = three(_, _, _, _, _, _, _), 1258 insert3(Tin, K, V, Tout). 1259insert(Tin, K, V, Tout) :- 1260 Tin = four(_, _, _, _, _, _, _, _, _, _), 1261 split_four(Tin, MidK, MidV, Sub0, Sub1), 1262 compare(Result1, K, MidK), 1263 insert_aux1(Result1, K, V, MidK, MidV, Sub0, Sub1, Tout). 1264 1265insert_aux1(Result1, K, V, MidK, MidV, Sub0, Sub1, Tout) :- 1266 Result1 = (<), 1267 insert2(Sub0, K, V, NewSub0), 1268 Tout = two(MidK, MidV, NewSub0, Sub1). 1269insert_aux1(Result1, _K, _V, _MidK, _MidV, _Sub0, _Sub1, _Tout) :- 1270 Result1 = (=), 1271 fail. 1272insert_aux1(Result1, K, V, MidK, MidV, Sub0, Sub1, Tout) :- 1273 Result1 = (>), 1274 insert2(Sub1, K, V, NewSub1), 1275 Tout = two(MidK, MidV, Sub0, NewSub1). 1276 1277% :- pred insert2(tree234(K, V), K, V, tree234(K, V)). 1278% :- mode insert2(di_two, di, di, uo) is semidet. 1279% % :- mode insert2(sdi_two, in, in, uo_tree234) is semidet. 1280% :- mode insert2(in_two, in, in, out) is semidet. 1281 1282insert2(two(K0, V0, T0, T1), K, V, Tout) :- 1283 ( 1284 T0 = empty, 1285 T1 = empty 1286 -> 1287 compare(Result, K, K0), 1288 insert2_aux1(Result, K, V, K0, V0, Tout) 1289 ; 1290 compare(Result, K, K0), 1291 insert2_aux28(Result, Tout, V, K, T1, T0, V0, K0) 1292 ). 1293 1294insert2_aux1(Result, K, V, K0, V0, Tout) :- 1295 Result = (<), 1296 Tout = three(K, V, K0, V0, empty, empty, empty). 1297insert2_aux1(Result, _K, _V, _K0, _V0, _Tout) :- 1298 Result = (=), 1299 fail. 1300insert2_aux1(Result, K, V, K0, V0, Tout) :- 1301 Result = (>), 1302 Tout = three(K0, V0, K, V, empty, empty, empty). 1303 1304insert2_aux28_aux29(K0, V0, T0, T1, K, V, Tout) :- 1305 T0 = empty, 1306 NewT0 = two(K, V, empty, empty), 1307 Tout = two(K0, V0, NewT0, T1). 1308insert2_aux28_aux29(K0, V0, T0, T1, K, V, Tout) :- 1309 T0 = two(_, _, _, _), 1310 insert2(T0, K, V, NewT0), 1311 Tout = two(K0, V0, NewT0, T1). 1312insert2_aux28_aux29(K0, V0, T0, T1, K, V, Tout) :- 1313 T0 = three(_, _, _, _, _, _, _), 1314 insert3(T0, K, V, NewT0), 1315 Tout = two(K0, V0, NewT0, T1). 1316insert2_aux28_aux29(K0, V0, T0, T1, K, V, Tout) :- 1317 T0 = four(_, _, _, _, _, _, _, _, _, _), 1318 split_four(T0, MT0K, MT0V, T00, T01), 1319 compare(Result1, K, MT0K), 1320 insert2_aux28_aux29_aux30(Result1, T01, T00, MT0V, MT0K, Tout, V, K, T1, V0, K0). 1321 1322insert2_aux28_aux31(K0, V0, T0, T1, K, V, Tout) :- 1323 T1 = empty, 1324 NewT1 = two(K, V, empty, empty), 1325 Tout = two(K0, V0, T0, NewT1). 1326insert2_aux28_aux31(K0, V0, T0, T1, K, V, Tout) :- 1327 T1 = two(_, _, _, _), 1328 insert2(T1, K, V, NewT1), 1329 Tout = two(K0, V0, T0, NewT1). 1330insert2_aux28_aux31(K0, V0, T0, T1, K, V, Tout) :- 1331 T1 = three(_, _, _, _, _, _, _), 1332 insert3(T1, K, V, NewT1), 1333 Tout = two(K0, V0, T0, NewT1). 1334insert2_aux28_aux31(K0, V0, T0, T1, K, V, Tout) :- 1335 T1 = four(_, _, _, _, _, _, _, _, _, _), 1336 split_four(T1, MT1K, MT1V, T10, T11), 1337 compare(Result1, K, MT1K), 1338 insert2_aux28_aux31_aux32(Result1, T11, T10, MT1V, MT1K, Tout, V, K, T0, V0, K0). 1339 1340insert2_aux28(Result, Tout, V, K, T1, T0, V0, K0) :- 1341 Result = (<), 1342 insert2_aux28_aux29(K0, V0, T0, T1, K, V, Tout). 1343insert2_aux28(Result, _Tout, _V, _K, _T1, _T0, _V0, _K0) :- 1344 Result = (=), 1345 fail. 1346insert2_aux28(Result, Tout, V, K, T1, T0, V0, K0) :- 1347 Result = (>), 1348 insert2_aux28_aux31(K0, V0, T0, T1, K, V, Tout). 1349 1350insert2_aux28_aux29_aux30(Result1, T01, T00, MT0V, MT0K, Tout, V, K, T1, V0, K0) :- 1351 Result1 = (<), 1352 insert2(T00, K, V, NewT00), 1353 Tout = three(MT0K, MT0V, K0, V0, NewT00, T01, T1). 1354insert2_aux28_aux29_aux30(Result1, _T01, _T00, _MT0V, _MT0K, _Tout, _V, _K, _T1, _V0, _K0) :- 1355 Result1 = (=), 1356 fail. 1357insert2_aux28_aux29_aux30(Result1, T01, T00, MT0V, MT0K, Tout, V, K, T1, V0, K0) :- 1358 Result1 = (>), 1359 insert2(T01, K, V, NewT01), 1360 Tout = three(MT0K, MT0V, K0, V0, T00, NewT01, T1). 1361 1362insert2_aux28_aux31_aux32(Result1, T11, T10, MT1V, MT1K, Tout, V, K, T0, V0, K0) :- 1363 Result1 = (<), 1364 insert2(T10, K, V, NewT10), 1365 Tout = three(K0, V0, MT1K, MT1V, T0, NewT10, T11). 1366insert2_aux28_aux31_aux32(Result1, _T11, _T10, _MT1V, _MT1K, _Tout, _V, _K, _T0, _V0, _K0) :- 1367 Result1 = (=), 1368 fail. 1369insert2_aux28_aux31_aux32(Result1, T11, T10, MT1V, MT1K, Tout, V, K, T0, V0, K0) :- 1370 Result1 = (>), 1371 insert2(T11, K, V, NewT11), 1372 Tout = three(K0, V0, MT1K, MT1V, T0, T10, NewT11). 1373 1374% :- pred insert3(tree234(K, V), K, V, tree234(K, V)). 1375% :- mode insert3(di_three, di, di, uo) is semidet. 1376% % :- mode insert3(sdi_three, in, in, uo_tree234) is semidet. 1377% :- mode insert3(in_three, in, in, out) is semidet. 1378 1379insert3(three(K0, V0, K1, V1, T0, T1, T2), K, V, Tout) :- 1380 ( 1381 T0 = empty, 1382 T1 = empty, 1383 T2 = empty 1384 -> 1385 compare(Result0, K, K0), 1386 insert3_aux34(Result0, Tout, V, K, V1, K1, V0, K0) 1387 ; 1388 compare(Result0, K, K0), 1389 insert3_aux33(Result0, Tout, V, K, T2, T1, T0, V1, K1, V0, K0) 1390 ). 1391 1392insert3_aux34(Result0, Tout, V, K, V1, K1, V0, K0) :- 1393 Result0 = (<), 1394 Tout = four(K, V, K0, V0, K1, V1, empty, empty, empty, empty). 1395insert3_aux34(Result0, _Tout, _V, _K, _V1, _K1, _V0, _K0) :- 1396 Result0 = (=), 1397 fail. 1398insert3_aux34(Result0, Tout, V, K, V1, K1, V0, K0) :- 1399 Result0 = (>), 1400 compare(Result1, K, K1), 1401 insert3_aux34_aux42(Result1, K0, V0, K1, V1, K, V, Tout). 1402 1403insert3_aux34_aux42(Result1, K0, V0, K1, V1, K, V, Tout) :- 1404 Result1 = (<), 1405 Tout = four(K0, V0, K, V, K1, V1, empty, empty, empty, empty). 1406insert3_aux34_aux42(Result1, _K0, _V0, _K1, _V1, _K, _V, _Tout) :- 1407 Result1 = (=), 1408 fail. 1409insert3_aux34_aux42(Result1, K0, V0, K1, V1, K, V, Tout) :- 1410 Result1 = (>), 1411 Tout = four(K0, V0, K1, V1, K, V, empty, empty, empty, empty). 1412 1413insert3_aux33_aux35(K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1414 T0 = empty, 1415 NewT0 = two(K, V, empty, empty), 1416 Tout = three(K0, V0, K1, V1, NewT0, T1, T2). 1417insert3_aux33_aux35(K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1418 T0 = two(_, _, _, _), 1419 insert2(T0, K, V, NewT0), 1420 Tout = three(K0, V0, K1, V1, NewT0, T1, T2). 1421insert3_aux33_aux35(K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1422 T0 = three(_, _, _, _, _, _, _), 1423 insert3(T0, K, V, NewT0), 1424 Tout = three(K0, V0, K1, V1, NewT0, T1, T2). 1425insert3_aux33_aux35(K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1426 T0 = four(_, _, _, _, _, _, _, _, _, _), 1427 split_four(T0, MT0K, MT0V, T00, T01), 1428 compare(ResultM, K, MT0K), 1429 insert3_aux33_aux35_aux36(ResultM, T01, T00, MT0V, MT0K, Tout, V, K, T2, T1, V1, K1, V0, K0). 1430 1431insert3_aux33_aux37_aux38(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1432 T1 = empty, 1433 NewT1 = two(K, V, empty, empty), 1434 Tout = three(K0, V0, K1, V1, T0, NewT1, T2). 1435insert3_aux33_aux37_aux38(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1436 T1 = two(_, _, _, _), 1437 insert2(T1, K, V, NewT1), 1438 Tout = three(K0, V0, K1, V1, T0, NewT1, T2). 1439insert3_aux33_aux37_aux38(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1440 T1 = three(_, _, _, _, _, _, _), 1441 insert3(T1, K, V, NewT1), 1442 Tout = three(K0, V0, K1, V1, T0, NewT1, T2). 1443insert3_aux33_aux37_aux38(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1444 T1 = four(_, _, _, _, _, _, _, _, _, _), 1445 split_four(T1, MT1K, MT1V, T10, T11), 1446 compare(ResultM, K, MT1K), 1447 insert3_aux33_aux37_aux38_aux39(ResultM, T11, T10, MT1V, MT1K, K0, V0, K1, V1, T0, T2, K, V, Tout). 1448 1449insert3_aux33_aux37_aux40(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1450 T2 = empty, 1451 NewT2 = two(K, V, empty, empty), 1452 Tout = three(K0, V0, K1, V1, T0, T1, NewT2). 1453insert3_aux33_aux37_aux40(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1454 T2 = two(_, _, _, _), 1455 insert2(T2, K, V, NewT2), 1456 Tout = three(K0, V0, K1, V1, T0, T1, NewT2). 1457insert3_aux33_aux37_aux40(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1458 T2 = three(_, _, _, _, _, _, _), 1459 insert3(T2, K, V, NewT2), 1460 Tout = three(K0, V0, K1, V1, T0, T1, NewT2). 1461insert3_aux33_aux37_aux40(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1462 T2 = four(_, _, _, _, _, _, _, _, _, _), 1463 split_four(T2, MT2K, MT2V, T20, T21), 1464 compare(ResultM, K, MT2K), 1465 insert3_aux33_aux37_aux40_aux41(ResultM, T21, T20, MT2V, MT2K, K0, V0, K1, V1, T0, T1, K, V, Tout). 1466 1467insert3_aux33(Result0, Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1468 Result0 = (<), 1469 insert3_aux33_aux35(K0, V0, K1, V1, T0, T1, T2, K, V, Tout). 1470insert3_aux33(Result0, _Tout, _V, _K, _T2, _T1, _T0, _V1, _K1, _V0, _K0) :- 1471 Result0 = (=), 1472 fail. 1473insert3_aux33(Result0, Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1474 Result0 = (>), 1475 compare(Result1, K, K1), 1476 insert3_aux33_aux37(Result1, K0, V0, K1, V1, T0, T1, T2, K, V, Tout). 1477 1478insert3_aux33_aux37(Result1, K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1479 Result1 = (<), 1480 insert3_aux33_aux37_aux38(Tout, V, K, T2, T1, T0, V1, K1, V0, K0). 1481insert3_aux33_aux37(Result1, _K0, _V0, _K1, _V1, _T0, _T1, _T2, _K, _V, _Tout) :- 1482 Result1 = (=), 1483 fail. 1484insert3_aux33_aux37(Result1, K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1485 Result1 = (>), 1486 insert3_aux33_aux37_aux40(Tout, V, K, T2, T1, T0, V1, K1, V0, K0). 1487 1488insert3_aux33_aux35_aux36(ResultM, T01, T00, MT0V, MT0K, Tout, V, K, T2, T1, V1, K1, V0, K0) :- 1489 ResultM = (<), 1490 insert2(T00, K, V, NewT00), 1491 Tout = four(MT0K, MT0V, K0, V0, K1, V1, NewT00, T01, T1, T2). 1492insert3_aux33_aux35_aux36(ResultM, _T01, _T00, _MT0V, _MT0K, _Tout, _V, _K, _T2, _T1, _V1, _K1, _V0, _K0) :- 1493 ResultM = (=), 1494 fail. 1495insert3_aux33_aux35_aux36(ResultM, T01, T00, MT0V, MT0K, Tout, V, K, T2, T1, V1, K1, V0, K0) :- 1496 ResultM = (>), 1497 insert2(T01, K, V, NewT01), 1498 Tout = four(MT0K, MT0V, K0, V0, K1, V1, T00, NewT01, T1, T2). 1499 1500insert3_aux33_aux37_aux38_aux39(ResultM, T11, T10, MT1V, MT1K, K0, V0, K1, V1, T0, T2, K, V, Tout) :- 1501 ResultM = (<), 1502 insert2(T10, K, V, NewT10), 1503 Tout = four(K0, V0, MT1K, MT1V, K1, V1, T0, NewT10, T11, T2). 1504insert3_aux33_aux37_aux38_aux39(ResultM, _T11, _T10, _MT1V, _MT1K, _K0, _V0, _K1, _V1, _T0, _T2, _K, _V, _Tout) :- 1505 ResultM = (=), 1506 fail. 1507insert3_aux33_aux37_aux38_aux39(ResultM, T11, T10, MT1V, MT1K, K0, V0, K1, V1, T0, T2, K, V, Tout) :- 1508 ResultM = (>), 1509 insert2(T11, K, V, NewT11), 1510 Tout = four(K0, V0, MT1K, MT1V, K1, V1, T0, T10, NewT11, T2). 1511 1512insert3_aux33_aux37_aux40_aux41(ResultM, T21, T20, MT2V, MT2K, K0, V0, K1, V1, T0, T1, K, V, Tout) :- 1513 ResultM = (<), 1514 insert2(T20, K, V, NewT20), 1515 Tout = four(K0, V0, K1, V1, MT2K, MT2V, T0, T1, NewT20, T21). 1516insert3_aux33_aux37_aux40_aux41(ResultM, _T21, _T20, _MT2V, _MT2K, _K0, _V0, _K1, _V1, _T0, _T1, _K, _V, _Tout) :- 1517 ResultM = (=), 1518 fail. 1519insert3_aux33_aux37_aux40_aux41(ResultM, T21, T20, MT2V, MT2K, K0, V0, K1, V1, T0, T1, K, V, Tout) :- 1520 ResultM = (>), 1521 insert2(T21, K, V, NewT21), 1522 Tout = four(K0, V0, K1, V1, MT2K, MT2V, T0, T1, T20, NewT21). 1523 1524%------------------------------------------------------------------------------% 1525 1526% set uses the same algorithm as used for insert, 1527% except that instead of failing for equal keys, we replace the value. 1528 1529set(Tin, K, V, Tout) :- 1530 Tin = empty, 1531 Tout = two(K, V, empty, empty). 1532set(Tin, K, V, Tout) :- 1533 Tin = two(_, _, _, _), 1534 set2(Tin, K, V, Tout). 1535set(Tin, K, V, Tout) :- 1536 Tin = three(_, _, _, _, _, _, _), 1537 set3(Tin, K, V, Tout). 1538set(Tin, K, V, Tout) :- 1539 Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 1540 compare(Result1, K, K1), 1541 set_aux43(Result1, T3, T2, T1, T0, V2, K2, V1, K1, V0, K0, Tout, V, K). 1542 1543set_aux43(Result1, T3, T2, T1, T0, V2, K2, V1, K1, V0, K0, Tout, V, K) :- 1544 Result1 = (<), 1545 Sub0 = two(K0, V0, T0, T1), 1546 Sub1 = two(K2, V2, T2, T3), 1547 set2(Sub0, K, V, NewSub0), 1548 Tout = two(K1, V1, NewSub0, Sub1). 1549set_aux43(Result1, T3, T2, T1, T0, V2, K2, _V1, K1, V0, K0, Tout, V, _K) :- 1550 Result1 = (=), 1551 Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3). 1552set_aux43(Result1, T3, T2, T1, T0, V2, K2, V1, K1, V0, K0, Tout, V, K) :- 1553 Result1 = (>), 1554 Sub0 = two(K0, V0, T0, T1), 1555 Sub1 = two(K2, V2, T2, T3), 1556 set2(Sub1, K, V, NewSub1), 1557 Tout = two(K1, V1, Sub0, NewSub1). 1558 1559% :- pred set2(tree234(K, V), K, V, tree234(K, V)). 1560% :- mode set2(di_two, di, di, uo) is det. 1561% % :- mode set2(sdi_two, in, in, uo_tree234) is det. 1562% :- mode set2(in_two, in, in, out) is det. 1563 1564set2(two(K0, V0, T0, T1), K, V, Tout) :- 1565 ( 1566 T0 = empty, 1567 T1 = empty 1568 -> 1569 compare(Result, K, K0), 1570 set2_aux45(Result, Tout, V, K, T1, T0, V0, K0) 1571 ; 1572 compare(Result, K, K0), 1573 set2_aux44(Result, Tout, V, K, T1, T0, V0, K0) 1574 ). 1575 1576set2_aux44_aux46(K0, V0, T0, T1, K, V, Tout) :- 1577 T0 = empty, 1578 NewT0 = two(K, V, empty, empty), 1579 Tout = two(K0, V0, NewT0, T1). 1580set2_aux44_aux46(K0, V0, T0, T1, K, V, Tout) :- 1581 T0 = two(_, _, _, _), 1582 set2(T0, K, V, NewT0), 1583 Tout = two(K0, V0, NewT0, T1). 1584set2_aux44_aux46(K0, V0, T0, T1, K, V, Tout) :- 1585 T0 = three(_, _, _, _, _, _, _), 1586 set3(T0, K, V, NewT0), 1587 Tout = two(K0, V0, NewT0, T1). 1588set2_aux44_aux46(K0, V0, T0, T1, K, V, Tout) :- 1589 T0 = four(_, _, _, _, _, _, _, _, _, _), 1590 split_four(T0, MT0K, MT0V, T00, T01), 1591 compare(Result1, K, MT0K), 1592 set2_aux44_aux46_aux47(Result1, T01, T00, MT0V, MT0K, Tout, V, K, T1, V0, K0). 1593 1594set2_aux44_aux48(K0, V0, T0, T1, K, V, Tout) :- 1595 T1 = empty, 1596 NewT1 = two(K, V, empty, empty), 1597 Tout = two(K0, V0, T0, NewT1). 1598set2_aux44_aux48(K0, V0, T0, T1, K, V, Tout) :- 1599 T1 = two(_, _, _, _), 1600 set2(T1, K, V, NewT1), 1601 Tout = two(K0, V0, T0, NewT1). 1602set2_aux44_aux48(K0, V0, T0, T1, K, V, Tout) :- 1603 T1 = three(_, _, _, _, _, _, _), 1604 set3(T1, K, V, NewT1), 1605 Tout = two(K0, V0, T0, NewT1). 1606set2_aux44_aux48(K0, V0, T0, T1, K, V, Tout) :- 1607 T1 = four(_, _, _, _, _, _, _, _, _, _), 1608 split_four(T1, MT1K, MT1V, T10, T11), 1609 compare(Result1, K, MT1K), 1610 set2_aux44_aux48_aux49(Result1, T11, T10, MT1V, MT1K, Tout, V, K, T0, V0, K0). 1611 1612set2_aux44(Result, Tout, V, K, T1, T0, V0, K0) :- 1613 Result = (<), 1614 set2_aux44_aux46(K0, V0, T0, T1, K, V, Tout). 1615set2_aux44(Result, Tout, V, K, T1, T0, _V0, _K0) :- 1616 Result = (=), 1617 Tout = two(K, V, T0, T1). 1618set2_aux44(Result, Tout, V, K, T1, T0, V0, K0) :- 1619 Result = (>), 1620 set2_aux44_aux48(K0, V0, T0, T1, K, V, Tout). 1621 1622set2_aux45(Result, Tout, V, K, _T1, _T0, V0, K0) :- 1623 Result = (<), 1624 Tout = three(K, V, K0, V0, empty, empty, empty). 1625set2_aux45(Result, Tout, V, K, T1, T0, _V0, _K0) :- 1626 Result = (=), 1627 Tout = two(K, V, T0, T1). 1628set2_aux45(Result, Tout, V, K, _T1, _T0, V0, K0) :- 1629 Result = (>), 1630 Tout = three(K0, V0, K, V, empty, empty, empty). 1631 1632set2_aux44_aux46_aux47(Result1, T01, T00, MT0V, MT0K, Tout, V, K, T1, V0, K0) :- 1633 Result1 = (<), 1634 set2(T00, K, V, NewT00), 1635 Tout = three(MT0K, MT0V, K0, V0, NewT00, T01, T1). 1636set2_aux44_aux46_aux47(Result1, T01, T00, _MT0V, MT0K, Tout, V, _K, T1, V0, K0) :- 1637 Result1 = (=), 1638 Tout = three(MT0K, V, K0, V0, T00, T01, T1). 1639set2_aux44_aux46_aux47(Result1, T01, T00, MT0V, MT0K, Tout, V, K, T1, V0, K0) :- 1640 Result1 = (>), 1641 set2(T01, K, V, NewT01), 1642 Tout = three(MT0K, MT0V, K0, V0, T00, NewT01, T1). 1643 1644set2_aux44_aux48_aux49(Result1, T11, T10, MT1V, MT1K, Tout, V, K, T0, V0, K0) :- 1645 Result1 = (<), 1646 set2(T10, K, V, NewT10), 1647 Tout = three(K0, V0, MT1K, MT1V, T0, NewT10, T11). 1648set2_aux44_aux48_aux49(Result1, T11, T10, _MT1V, MT1K, Tout, V, _K, T0, V0, K0) :- 1649 Result1 = (=), 1650 Tout = three(K0, V0, MT1K, V, T0, T10, T11). 1651set2_aux44_aux48_aux49(Result1, T11, T10, MT1V, MT1K, Tout, V, K, T0, V0, K0) :- 1652 Result1 = (>), 1653 set2(T11, K, V, NewT11), 1654 Tout = three(K0, V0, MT1K, MT1V, T0, T10, NewT11). 1655 1656% :- pred set3(tree234(K, V), K, V, tree234(K, V)). 1657% :- mode set3(di_three, di, di, uo) is det. 1658% % :- mode set3(sdi_three, in, in, uo_tree234) is det. 1659% :- mode set3(in_three, in, in, out) is det. 1660 1661set3(three(K0, V0, K1, V1, T0, T1, T2), K, V, Tout) :- 1662 ( 1663 T0 = empty, 1664 T1 = empty, 1665 T2 = empty 1666 -> 1667 compare(Result0, K, K0), 1668 set3_aux51(Result0, Tout, V, K, V1, K1, V0, K0) 1669 ; 1670 compare(Result0, K, K0), 1671 set3_aux50(Result0, Tout, V, K, T2, T1, T0, V1, K1, V0, K0) 1672 ). 1673 1674set3_aux51(Result0, Tout, V, K, V1, K1, V0, K0) :- 1675 Result0 = (<), 1676 Tout = four(K, V, K0, V0, K1, V1, empty, empty, empty, empty). 1677set3_aux51(Result0, Tout, V, _K, V1, K1, _V0, K0) :- 1678 Result0 = (=), 1679 Tout = three(K0, V, K1, V1, empty, empty, empty). 1680set3_aux51(Result0, Tout, V, K, V1, K1, V0, K0) :- 1681 Result0 = (>), 1682 compare(Result1, K, K1), 1683 set3_aux51_aux59(Result1, K0, V0, K1, V1, K, V, Tout). 1684 1685set3_aux51_aux59(Result1, K0, V0, K1, V1, K, V, Tout) :- 1686 Result1 = (<), 1687 Tout = four(K0, V0, K, V, K1, V1, empty, empty, empty, empty). 1688set3_aux51_aux59(Result1, K0, V0, K1, _V1, _K, V, Tout) :- 1689 Result1 = (=), 1690 Tout = three(K0, V0, K1, V, empty, empty, empty). 1691set3_aux51_aux59(Result1, K0, V0, K1, V1, K, V, Tout) :- 1692 Result1 = (>), 1693 Tout = four(K0, V0, K1, V1, K, V, empty, empty, empty, empty). 1694 1695set3_aux50_aux52(K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1696 T0 = empty, 1697 NewT0 = two(K, V, empty, empty), 1698 Tout = three(K0, V0, K1, V1, NewT0, T1, T2). 1699set3_aux50_aux52(K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1700 T0 = two(_, _, _, _), 1701 set2(T0, K, V, NewT0), 1702 Tout = three(K0, V0, K1, V1, NewT0, T1, T2). 1703set3_aux50_aux52(K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1704 T0 = three(_, _, _, _, _, _, _), 1705 set3(T0, K, V, NewT0), 1706 Tout = three(K0, V0, K1, V1, NewT0, T1, T2). 1707set3_aux50_aux52(K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1708 T0 = four(_, _, _, _, _, _, _, _, _, _), 1709 split_four(T0, MT0K, MT0V, T00, T01), 1710 compare(ResultM, K, MT0K), 1711 set3_aux50_aux52_aux53(ResultM, T01, T00, MT0V, MT0K, Tout, V, K, T2, T1, V1, K1, V0, K0). 1712 1713set3_aux50_aux54_aux55(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1714 T1 = empty, 1715 NewT1 = two(K, V, empty, empty), 1716 Tout = three(K0, V0, K1, V1, T0, NewT1, T2). 1717set3_aux50_aux54_aux55(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1718 T1 = two(_, _, _, _), 1719 set2(T1, K, V, NewT1), 1720 Tout = three(K0, V0, K1, V1, T0, NewT1, T2). 1721set3_aux50_aux54_aux55(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1722 T1 = three(_, _, _, _, _, _, _), 1723 set3(T1, K, V, NewT1), 1724 Tout = three(K0, V0, K1, V1, T0, NewT1, T2). 1725set3_aux50_aux54_aux55(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1726 T1 = four(_, _, _, _, _, _, _, _, _, _), 1727 split_four(T1, MT1K, MT1V, T10, T11), 1728 compare(ResultM, K, MT1K), 1729 set3_aux50_aux54_aux55_aux56(ResultM, T11, T10, MT1V, MT1K, K0, V0, K1, V1, T0, T2, K, V, Tout). 1730 1731set3_aux50_aux54_aux57(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1732 T2 = empty, 1733 NewT2 = two(K, V, empty, empty), 1734 Tout = three(K0, V0, K1, V1, T0, T1, NewT2). 1735set3_aux50_aux54_aux57(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1736 T2 = two(_, _, _, _), 1737 set2(T2, K, V, NewT2), 1738 Tout = three(K0, V0, K1, V1, T0, T1, NewT2). 1739set3_aux50_aux54_aux57(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1740 T2 = three(_, _, _, _, _, _, _), 1741 set3(T2, K, V, NewT2), 1742 Tout = three(K0, V0, K1, V1, T0, T1, NewT2). 1743set3_aux50_aux54_aux57(Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1744 T2 = four(_, _, _, _, _, _, _, _, _, _), 1745 split_four(T2, MT2K, MT2V, T20, T21), 1746 compare(ResultM, K, MT2K), 1747 set3_aux50_aux54_aux57_aux58(ResultM, T21, T20, MT2V, MT2K, K0, V0, K1, V1, T0, T1, K, V, Tout). 1748 1749set3_aux50(Result0, Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1750 Result0 = (<), 1751 set3_aux50_aux52(K0, V0, K1, V1, T0, T1, T2, K, V, Tout). 1752set3_aux50(Result0, Tout, V, _K, T2, T1, T0, V1, K1, _V0, K0) :- 1753 Result0 = (=), 1754 Tout = three(K0, V, K1, V1, T0, T1, T2). 1755set3_aux50(Result0, Tout, V, K, T2, T1, T0, V1, K1, V0, K0) :- 1756 Result0 = (>), 1757 compare(Result1, K, K1), 1758 set3_aux50_aux54(Result1, K0, V0, K1, V1, T0, T1, T2, K, V, Tout). 1759 1760set3_aux50_aux54(Result1, K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1761 Result1 = (<), 1762 set3_aux50_aux54_aux55(Tout, V, K, T2, T1, T0, V1, K1, V0, K0). 1763set3_aux50_aux54(Result1, K0, V0, _K1, _V1, T0, T1, T2, K, V, Tout) :- 1764 Result1 = (=), 1765 Tout = three(K0, V0, K, V, T0, T1, T2). 1766set3_aux50_aux54(Result1, K0, V0, K1, V1, T0, T1, T2, K, V, Tout) :- 1767 Result1 = (>), 1768 set3_aux50_aux54_aux57(Tout, V, K, T2, T1, T0, V1, K1, V0, K0). 1769 1770set3_aux50_aux52_aux53(ResultM, T01, T00, MT0V, MT0K, Tout, V, K, T2, T1, V1, K1, V0, K0) :- 1771 ResultM = (<), 1772 set2(T00, K, V, NewT00), 1773 Tout = four(MT0K, MT0V, K0, V0, K1, V1, NewT00, T01, T1, T2). 1774set3_aux50_aux52_aux53(ResultM, T01, T00, _MT0V, MT0K, Tout, V, _K, T2, T1, V1, K1, V0, K0) :- 1775 ResultM = (=), 1776 Tout = four(MT0K, V, K0, V0, K1, V1, T00, T01, T1, T2). 1777set3_aux50_aux52_aux53(ResultM, T01, T00, MT0V, MT0K, Tout, V, K, T2, T1, V1, K1, V0, K0) :- 1778 ResultM = (>), 1779 set2(T01, K, V, NewT01), 1780 Tout = four(MT0K, MT0V, K0, V0, K1, V1, T00, NewT01, T1, T2). 1781 1782set3_aux50_aux54_aux55_aux56(ResultM, T11, T10, MT1V, MT1K, K0, V0, K1, V1, T0, T2, K, V, Tout) :- 1783 ResultM = (<), 1784 set2(T10, K, V, NewT10), 1785 Tout = four(K0, V0, MT1K, MT1V, K1, V1, T0, NewT10, T11, T2). 1786set3_aux50_aux54_aux55_aux56(ResultM, T11, T10, _MT1V, MT1K, K0, V0, K1, V1, T0, T2, _K, V, Tout) :- 1787 ResultM = (=), 1788 Tout = four(K0, V0, MT1K, V, K1, V1, T0, T10, T11, T2). 1789set3_aux50_aux54_aux55_aux56(ResultM, T11, T10, MT1V, MT1K, K0, V0, K1, V1, T0, T2, K, V, Tout) :- 1790 ResultM = (>), 1791 set2(T11, K, V, NewT11), 1792 Tout = four(K0, V0, MT1K, MT1V, K1, V1, T0, T10, NewT11, T2). 1793 1794set3_aux50_aux54_aux57_aux58(ResultM, T21, T20, MT2V, MT2K, K0, V0, K1, V1, T0, T1, K, V, Tout) :- 1795 ResultM = (<), 1796 set2(T20, K, V, NewT20), 1797 Tout = four(K0, V0, K1, V1, MT2K, MT2V, T0, T1, NewT20, T21). 1798set3_aux50_aux54_aux57_aux58(ResultM, T21, T20, _MT2V, MT2K, K0, V0, K1, V1, T0, T1, _K, V, Tout) :- 1799 ResultM = (=), 1800 Tout = four(K0, V0, K1, V1, MT2K, V, T0, T1, T20, T21). 1801set3_aux50_aux54_aux57_aux58(ResultM, T21, T20, MT2V, MT2K, K0, V0, K1, V1, T0, T1, K, V, Tout) :- 1802 ResultM = (>), 1803 set2(T21, K, V, NewT21), 1804 Tout = four(K0, V0, K1, V1, MT2K, MT2V, T0, T1, T20, NewT21). 1805 1806%------------------------------------------------------------------------------% 1807%------------------------------------------------------------------------------% 1808 1809delete(Tin, K, Tout) :- 1810 delete_2(Tin, K, Tout, _). 1811 1812 % When deleting an item from a tree, the height of the tree may be 1813 % reduced by one. The last argument says whether this has occurred. 1814 1815% :- pred delete_2(tree234(K, V), K, tree234(K, V), bool). 1816% :- mode delete_2(di, in, uo, out) is det. 1817% :- mode delete_2(in, in, out, out) is det. 1818 1819delete_2(Tin, _K, Tout, RH) :- 1820 Tin = empty, 1821 Tout = empty, 1822 RH = no. 1823delete_2(Tin, K, Tout, RH) :- 1824 Tin = two(K0, V0, T0, T1), 1825 compare(Result0, K, K0), 1826 delete_2_aux60(Result0, T1, T0, V0, K0, RH, Tout, K). 1827delete_2(Tin, K, Tout, RH) :- 1828 Tin = three(K0, V0, K1, V1, T0, T1, T2), 1829 compare(Result0, K, K0), 1830 delete_2_aux61(Result0, T2, T1, T0, V1, K1, V0, K0, RH, Tout, K). 1831delete_2(Tin, K, Tout, RH) :- 1832 Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 1833 compare(Result1, K, K1), 1834 delete_2_aux63(Result1, T3, T2, T1, T0, V2, K2, V1, K1, V0, K0, RH, Tout, K). 1835 1836delete_2_aux60(Result0, T1, T0, V0, K0, RH, Tout, K) :- 1837 Result0 = (<), 1838 delete_2(T0, K, NewT0, RHT0), 1839 ( 1840 RHT0 = yes 1841 -> 1842 fix_2node_t0(K0, V0, NewT0, T1, Tout, RH) 1843 ; 1844 Tout = two(K0, V0, NewT0, T1), 1845 RH = no 1846 ). 1847delete_2_aux60(Result0, T1, T0, _V0, _K0, RH, Tout, _K) :- 1848 Result0 = (=), 1849 ( 1850 remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) 1851 -> 1852 ( 1853 RHT1 = yes 1854 -> 1855 fix_2node_t1(ST1K, ST1V, T0, NewT1, Tout, RH) 1856 ; 1857 Tout = two(ST1K, ST1V, T0, NewT1), 1858 RH = no 1859 ) 1860 ; 1861 Tout = T0, 1862 RH = yes 1863 ). 1864delete_2_aux60(Result0, T1, T0, V0, K0, RH, Tout, K) :- 1865 Result0 = (>), 1866 delete_2(T1, K, NewT1, RHT1), 1867 ( 1868 RHT1 = yes 1869 -> 1870 fix_2node_t1(K0, V0, T0, NewT1, Tout, RH) 1871 ; 1872 Tout = two(K0, V0, T0, NewT1), 1873 RH = no 1874 ). 1875 1876delete_2_aux61(Result0, T2, T1, T0, V1, K1, V0, K0, RH, Tout, K) :- 1877 Result0 = (<), 1878 delete_2(T0, K, NewT0, RHT0), 1879 ( 1880 RHT0 = yes 1881 -> 1882 fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH) 1883 ; 1884 Tout = three(K0, V0, K1, V1, NewT0, T1, T2), 1885 RH = no 1886 ). 1887delete_2_aux61(Result0, T2, T1, T0, V1, K1, _V0, _K0, RH, Tout, _K) :- 1888 Result0 = (=), 1889 ( 1890 remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) 1891 -> 1892 ( 1893 RHT1 = yes 1894 -> 1895 fix_3node_t1(ST1K, ST1V, K1, V1, T0, NewT1, T2, Tout, RH) 1896 ; 1897 Tout = three(ST1K, ST1V, K1, V1, T0, NewT1, T2), 1898 RH = no 1899 ) 1900 ; 1901 Tout = two(K1, V1, T0, T2), 1902 RH = no 1903 ). 1904delete_2_aux61(Result0, T2, T1, T0, V1, K1, V0, K0, RH, Tout, K) :- 1905 Result0 = (>), 1906 compare(Result1, K, K1), 1907 delete_2_aux61_aux62(Result1, K, Tout, RH, K0, V0, K1, V1, T0, T1, T2). 1908 1909delete_2_aux61_aux62(Result1, K, Tout, RH, K0, V0, K1, V1, T0, T1, T2) :- 1910 Result1 = (<), 1911 delete_2(T1, K, NewT1, RHT1), 1912 ( 1913 RHT1 = yes 1914 -> 1915 fix_3node_t1(K0, V0, K1, V1, T0, NewT1, T2, Tout, RH) 1916 ; 1917 Tout = three(K0, V0, K1, V1, T0, NewT1, T2), 1918 RH = no 1919 ). 1920delete_2_aux61_aux62(Result1, _K, Tout, RH, K0, V0, _K1, _V1, T0, T1, T2) :- 1921 Result1 = (=), 1922 ( 1923 remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) 1924 -> 1925 ( 1926 RHT2 = yes 1927 -> 1928 fix_3node_t2(K0, V0, ST2K, ST2V, T0, T1, NewT2, Tout, RH) 1929 ; 1930 Tout = three(K0, V0, ST2K, ST2V, T0, T1, NewT2), 1931 RH = no 1932 ) 1933 ; 1934 Tout = two(K0, V0, T0, T1), 1935 RH = no 1936 ). 1937delete_2_aux61_aux62(Result1, K, Tout, RH, K0, V0, K1, V1, T0, T1, T2) :- 1938 Result1 = (>), 1939 delete_2(T2, K, NewT2, RHT2), 1940 ( 1941 RHT2 = yes 1942 -> 1943 fix_3node_t2(K0, V0, K1, V1, T0, T1, NewT2, Tout, RH) 1944 ; 1945 Tout = three(K0, V0, K1, V1, T0, T1, NewT2), 1946 RH = no 1947 ). 1948 1949delete_2_aux63(Result1, T3, T2, T1, T0, V2, K2, V1, K1, V0, K0, RH, Tout, K) :- 1950 Result1 = (<), 1951 compare(Result0, K, K0), 1952 delete_2_aux63_aux64(Result0, K, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3). 1953delete_2_aux63(Result1, T3, T2, T1, T0, V2, K2, _V1, _K1, V0, K0, RH, Tout, _K) :- 1954 Result1 = (=), 1955 ( 1956 remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) 1957 -> 1958 ( 1959 RHT2 = yes 1960 -> 1961 fix_4node_t2(K0, V0, ST2K, ST2V, K2, V2, T0, T1, NewT2, T3, Tout, RH) 1962 ; 1963 Tout = four(K0, V0, ST2K, ST2V, K2, V2, T0, T1, NewT2, T3), 1964 RH = no 1965 ) 1966 ; 1967 Tout = three(K0, V0, K2, V2, T0, T1, T3), 1968 RH = no 1969 ). 1970delete_2_aux63(Result1, T3, T2, T1, T0, V2, K2, V1, K1, V0, K0, RH, Tout, K) :- 1971 Result1 = (>), 1972 compare(Result2, K, K2), 1973 delete_2_aux63_aux65(Result2, K, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3). 1974 1975delete_2_aux63_aux64(Result0, K, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 1976 Result0 = (<), 1977 delete_2(T0, K, NewT0, RHT0), 1978 ( 1979 RHT0 = yes 1980 -> 1981 fix_4node_t0(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3, Tout, RH) 1982 ; 1983 Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3), 1984 RH = no 1985 ). 1986delete_2_aux63_aux64(Result0, _K, Tout, RH, _K0, _V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 1987 Result0 = (=), 1988 ( 1989 remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) 1990 -> 1991 ( 1992 RHT1 = yes 1993 -> 1994 fix_4node_t1(ST1K, ST1V, K1, V1, K2, V2, T0, NewT1, T2, T3, Tout, RH) 1995 ; 1996 Tout = four(ST1K, ST1V, K1, V1, K2, V2, T0, NewT1, T2, T3), 1997 RH = no 1998 ) 1999 ; 2000 Tout = three(K1, V1, K2, V2, T0, T2, T3), 2001 RH = no 2002 ). 2003delete_2_aux63_aux64(Result0, K, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 2004 Result0 = (>), 2005 delete_2(T1, K, NewT1, RHT1), 2006 ( 2007 RHT1 = yes 2008 -> 2009 fix_4node_t1(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3, Tout, RH) 2010 ; 2011 Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3), 2012 RH = no 2013 ). 2014 2015delete_2_aux63_aux65(Result2, K, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 2016 Result2 = (<), 2017 delete_2(T2, K, NewT2, RHT2), 2018 ( 2019 RHT2 = yes 2020 -> 2021 fix_4node_t2(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3, Tout, RH) 2022 ; 2023 Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3), 2024 RH = no 2025 ). 2026delete_2_aux63_aux65(Result2, _K, Tout, RH, K0, V0, K1, V1, _K2, _V2, T0, T1, T2, T3) :- 2027 Result2 = (=), 2028 ( 2029 remove_smallest_2(T3, ST3K, ST3V, NewT3, RHT3) 2030 -> 2031 ( 2032 RHT3 = yes 2033 -> 2034 fix_4node_t3(K0, V0, K1, V1, ST3K, ST3V, T0, T1, T2, NewT3, Tout, RH) 2035 ; 2036 Tout = four(K0, V0, K1, V1, ST3K, ST3V, T0, T1, T2, NewT3), 2037 RH = no 2038 ) 2039 ; 2040 Tout = three(K0, V0, K1, V1, T0, T1, T2), 2041 RH = no 2042 ). 2043delete_2_aux63_aux65(Result2, K, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 2044 Result2 = (>), 2045 delete_2(T3, K, NewT3, RHT3), 2046 ( 2047 RHT3 = yes 2048 -> 2049 fix_4node_t3(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3, Tout, RH) 2050 ; 2051 Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3), 2052 RH = no 2053 ). 2054 2055%------------------------------------------------------------------------------% 2056 2057 % We use the same algorithm as delete. 2058 2059remove(Tin, K, V, Tout) :- 2060 remove_2(Tin, K, V, Tout, _). 2061 2062% :- pred remove_2(tree234(K, V), K, V, tree234(K, V), bool). 2063% :- mode remove_2(di, in, uo, uo, out) is semidet. 2064% :- mode remove_2(in, in, out, out, out) is semidet. 2065 2066remove_2(Tin, _K, _V, _Tout, _RH) :- 2067 Tin = empty, 2068 fail. 2069remove_2(Tin, K, V, Tout, RH) :- 2070 Tin = two(K0, V0, T0, T1), 2071 compare(Result0, K, K0), 2072 remove_2_aux66(Result0, T1, T0, V0, K0, RH, Tout, V, K). 2073remove_2(Tin, K, V, Tout, RH) :- 2074 Tin = three(K0, V0, K1, V1, T0, T1, T2), 2075 compare(Result0, K, K0), 2076 remove_2_aux67(Result0, T2, T1, T0, V1, K1, V0, K0, RH, Tout, V, K). 2077remove_2(Tin, K, V, Tout, RH) :- 2078 Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 2079 compare(Result1, K, K1), 2080 remove_2_aux69(Result1, T3, T2, T1, T0, V2, K2, V1, K1, V0, K0, RH, Tout, V, K). 2081 2082remove_2_aux66(Result0, T1, T0, V0, K0, RH, Tout, V, K) :- 2083 Result0 = (<), 2084 remove_2(T0, K, V, NewT0, RHT0), 2085 ( 2086 RHT0 = yes 2087 -> 2088 fix_2node_t0(K0, V0, NewT0, T1, Tout, RH) 2089 ; 2090 Tout = two(K0, V0, NewT0, T1), 2091 RH = no 2092 ). 2093remove_2_aux66(Result0, T1, T0, V0, _K0, RH, Tout, V, _K) :- 2094 Result0 = (=), 2095 ( 2096 remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) 2097 -> 2098 ( 2099 RHT1 = yes 2100 -> 2101 fix_2node_t1(ST1K, ST1V, T0, NewT1, Tout, RH) 2102 ; 2103 Tout = two(ST1K, ST1V, T0, NewT1), 2104 RH = no 2105 ) 2106 ; 2107 Tout = T0, 2108 RH = yes 2109 ), 2110 V = V0. 2111remove_2_aux66(Result0, T1, T0, V0, K0, RH, Tout, V, K) :- 2112 Result0 = (>), 2113 remove_2(T1, K, V, NewT1, RHT1), 2114 ( 2115 RHT1 = yes 2116 -> 2117 fix_2node_t1(K0, V0, T0, NewT1, Tout, RH) 2118 ; 2119 Tout = two(K0, V0, T0, NewT1), 2120 RH = no 2121 ). 2122 2123remove_2_aux67(Result0, T2, T1, T0, V1, K1, V0, K0, RH, Tout, V, K) :- 2124 Result0 = (<), 2125 remove_2(T0, K, V, NewT0, RHT0), 2126 ( 2127 RHT0 = yes 2128 -> 2129 fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH) 2130 ; 2131 Tout = three(K0, V0, K1, V1, NewT0, T1, T2), 2132 RH = no 2133 ). 2134remove_2_aux67(Result0, T2, T1, T0, V1, K1, V0, _K0, RH, Tout, V, _K) :- 2135 Result0 = (=), 2136 ( 2137 remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) 2138 -> 2139 ( 2140 RHT1 = yes 2141 -> 2142 fix_3node_t1(ST1K, ST1V, K1, V1, T0, NewT1, T2, Tout, RH) 2143 ; 2144 Tout = three(ST1K, ST1V, K1, V1, T0, NewT1, T2), 2145 RH = no 2146 ) 2147 ; 2148 Tout = two(K1, V1, T0, T2), 2149 RH = no 2150 ), 2151 V = V0. 2152remove_2_aux67(Result0, T2, T1, T0, V1, K1, V0, K0, RH, Tout, V, K) :- 2153 Result0 = (>), 2154 compare(Result1, K, K1), 2155 remove_2_aux67_aux68(Result1, K, V, Tout, RH, K0, V0, K1, V1, T0, T1, T2). 2156 2157remove_2_aux67_aux68(Result1, K, V, Tout, RH, K0, V0, K1, V1, T0, T1, T2) :- 2158 Result1 = (<), 2159 remove_2(T1, K, V, NewT1, RHT1), 2160 ( 2161 RHT1 = yes 2162 -> 2163 fix_3node_t1(K0, V0, K1, V1, T0, NewT1, T2, Tout, RH) 2164 ; 2165 Tout = three(K0, V0, K1, V1, T0, NewT1, T2), 2166 RH = no 2167 ). 2168remove_2_aux67_aux68(Result1, _K, V, Tout, RH, K0, V0, _K1, V1, T0, T1, T2) :- 2169 Result1 = (=), 2170 ( 2171 remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) 2172 -> 2173 ( 2174 RHT2 = yes 2175 -> 2176 fix_3node_t2(K0, V0, ST2K, ST2V, T0, T1, NewT2, Tout, RH) 2177 ; 2178 Tout = three(K0, V0, ST2K, ST2V, T0, T1, NewT2), 2179 RH = no 2180 ) 2181 ; 2182 Tout = two(K0, V0, T0, T1), 2183 RH = no 2184 ), 2185 V = V1. 2186remove_2_aux67_aux68(Result1, K, V, Tout, RH, K0, V0, K1, V1, T0, T1, T2) :- 2187 Result1 = (>), 2188 remove_2(T2, K, V, NewT2, RHT2), 2189 ( 2190 RHT2 = yes 2191 -> 2192 fix_3node_t2(K0, V0, K1, V1, T0, T1, NewT2, Tout, RH) 2193 ; 2194 Tout = three(K0, V0, K1, V1, T0, T1, NewT2), 2195 RH = no 2196 ). 2197 2198remove_2_aux69(Result1, T3, T2, T1, T0, V2, K2, V1, K1, V0, K0, RH, Tout, V, K) :- 2199 Result1 = (<), 2200 compare(Result0, K, K0), 2201 remove_2_aux69_aux70(Result0, K, V, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3). 2202remove_2_aux69(Result1, T3, T2, T1, T0, V2, K2, V1, _K1, V0, K0, RH, Tout, V, _K) :- 2203 Result1 = (=), 2204 ( 2205 remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) 2206 -> 2207 ( 2208 RHT2 = yes 2209 -> 2210 fix_4node_t2(K0, V0, ST2K, ST2V, K2, V2, T0, T1, NewT2, T3, Tout, RH) 2211 ; 2212 Tout = four(K0, V0, ST2K, ST2V, K2, V2, T0, T1, NewT2, T3), 2213 RH = no 2214 ) 2215 ; 2216 Tout = three(K0, V0, K2, V2, T0, T1, T3), 2217 RH = no 2218 ), 2219 V = V1. 2220remove_2_aux69(Result1, T3, T2, T1, T0, V2, K2, V1, K1, V0, K0, RH, Tout, V, K) :- 2221 Result1 = (>), 2222 compare(Result2, K, K2), 2223 remove_2_aux69_aux71(Result2, K, V, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3). 2224 2225remove_2_aux69_aux70(Result0, K, V, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 2226 Result0 = (<), 2227 remove_2(T0, K, V, NewT0, RHT0), 2228 ( 2229 RHT0 = yes 2230 -> 2231 fix_4node_t0(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3, Tout, RH) 2232 ; 2233 Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3), 2234 RH = no 2235 ). 2236remove_2_aux69_aux70(Result0, _K, V, Tout, RH, _K0, V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 2237 Result0 = (=), 2238 ( 2239 remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) 2240 -> 2241 ( 2242 RHT1 = yes 2243 -> 2244 fix_4node_t1(ST1K, ST1V, K1, V1, K2, V2, T0, NewT1, T2, T3, Tout, RH) 2245 ; 2246 Tout = four(ST1K, ST1V, K1, V1, K2, V2, T0, NewT1, T2, T3), 2247 RH = no 2248 ) 2249 ; 2250 Tout = three(K1, V1, K2, V2, T0, T2, T3), 2251 RH = no 2252 ), 2253 V = V0. 2254remove_2_aux69_aux70(Result0, K, V, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 2255 Result0 = (>), 2256 remove_2(T1, K, V, NewT1, RHT1), 2257 ( 2258 RHT1 = yes 2259 -> 2260 fix_4node_t1(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3, Tout, RH) 2261 ; 2262 Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3), 2263 RH = no 2264 ). 2265 2266remove_2_aux69_aux71(Result2, K, V, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 2267 Result2 = (<), 2268 remove_2(T2, K, V, NewT2, RHT2), 2269 ( 2270 RHT2 = yes 2271 -> 2272 fix_4node_t2(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3, Tout, RH) 2273 ; 2274 Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3), 2275 RH = no 2276 ). 2277remove_2_aux69_aux71(Result2, _K, V, Tout, RH, K0, V0, K1, V1, _K2, V2, T0, T1, T2, T3) :- 2278 Result2 = (=), 2279 ( 2280 remove_smallest_2(T3, ST3K, ST3V, NewT3, RHT3) 2281 -> 2282 ( 2283 RHT3 = yes 2284 -> 2285 fix_4node_t3(K0, V0, K1, V1, ST3K, ST3V, T0, T1, T2, NewT3, Tout, RH) 2286 ; 2287 Tout = four(K0, V0, K1, V1, ST3K, ST3V, T0, T1, T2, NewT3), 2288 RH = no 2289 ) 2290 ; 2291 Tout = three(K0, V0, K1, V1, T0, T1, T2), 2292 RH = no 2293 ), 2294 V = V2. 2295remove_2_aux69_aux71(Result2, K, V, Tout, RH, K0, V0, K1, V1, K2, V2, T0, T1, T2, T3) :- 2296 Result2 = (>), 2297 remove_2(T3, K, V, NewT3, RHT3), 2298 ( 2299 RHT3 = yes 2300 -> 2301 fix_4node_t3(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3, Tout, RH) 2302 ; 2303 Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3), 2304 RH = no 2305 ). 2306 2307%------------------------------------------------------------------------------% 2308 2309 % The algorithm we use similar to delete, except that we 2310 % always go down the left subtree. 2311 2312remove_smallest(Tin, K, V, Tout) :- 2313 remove_smallest_2(Tin, K, V, Tout, _). 2314 2315% :- pred remove_smallest_2(tree234(K, V), K, V, tree234(K, V), bool). 2316% :- mode remove_smallest_2(di, uo, uo, uo, out) is semidet. 2317% :- mode remove_smallest_2(in, out, out, out, out) is semidet. 2318 2319remove_smallest_2(Tin, _K, _V, _Tout, _RH) :- 2320 Tin = empty, 2321 fail. 2322remove_smallest_2(Tin, K, V, Tout, RH) :- 2323 Tin = two(K0, V0, T0, T1), 2324 ( 2325 T0 = empty 2326 -> 2327 K = K0, 2328 V = V0, 2329 Tout = T1, 2330 RH = yes 2331 ; 2332 remove_smallest_2(T0, K, V, NewT0, RHT0), 2333 ( RHT0 = yes -> 2334 fix_2node_t0(K0, V0, NewT0, T1, Tout, RH) 2335 ; 2336 Tout = two(K0, V0, NewT0, T1), 2337 RH = no 2338 ) 2339 ). 2340remove_smallest_2(Tin, K, V, Tout, RH) :- 2341 Tin = three(K0, V0, K1, V1, T0, T1, T2), 2342 ( 2343 T0 = empty 2344 -> 2345 K = K0, 2346 V = V0, 2347 Tout = two(K1, V1, T1, T2), 2348 RH = no 2349 ; 2350 remove_smallest_2(T0, K, V, NewT0, RHT0), 2351 ( RHT0 = yes -> 2352 fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, 2353 Tout, RH) 2354 ; 2355 Tout = three(K0, V0, K1, V1, NewT0, T1, T2), 2356 RH = no 2357 ) 2358 ). 2359remove_smallest_2(Tin, K, V, Tout, RH) :- 2360 Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 2361 ( 2362 T0 = empty 2363 -> 2364 K = K0, 2365 V = V0, 2366 Tout = three(K1, V1, K2, V2, T1, T2, T3), 2367 RH = no 2368 ; 2369 remove_smallest_2(T0, K, V, NewT0, RHT0), 2370 ( RHT0 = yes -> 2371 fix_4node_t0(K0, V0, K1, V1, K2, V2, 2372 NewT0, T1, T2, T3, Tout, RH) 2373 ; 2374 Tout = four(K0, V0, K1, V1, K2, V2, 2375 NewT0, T1, T2, T3), 2376 RH = no 2377 ) 2378 ). 2379 2380%------------------------------------------------------------------------------% 2381 2382 % The input to the following group of predicates are the components 2383 % of a two-, three- or four-node in which the height of the indicated 2384 % subtree is one less that it should be. If it is possible to increase 2385 % the height of that subtree by moving into it elements from its 2386 % neighboring subtrees, do so, and return the resulting tree with RH 2387 % set to no. Otherwise, return a balanced tree whose height is reduced 2388 % by one, with RH set to yes to indicate the reduced height. 2389 2390% :- pred fix_2node_t0(K, V, tree234(K, V), tree234(K, V), tree234(K, V), bool). 2391% :- mode fix_2node_t0(di, di, di, di, uo, out) is det. 2392% :- mode fix_2node_t0(in, in, in, in, out, out) is det. 2393 2394fix_2node_t0(K0, V0, T0, T1, Tout, RH) :- 2395 % steal T1's leftmost subtree and combine it with T0 2396 T1 = four(K10, V10, K11, V11, K12, V12, T10, T11, T12, T13), 2397 NewT1 = three(K11, V11, K12, V12, T11, T12, T13), 2398 Node = two(K0, V0, T0, T10), 2399 Tout = two(K10, V10, Node, NewT1), 2400 RH = no. 2401fix_2node_t0(K0, V0, T0, T1, Tout, RH) :- 2402 % steal T1's leftmost subtree and combine it with T0 2403 T1 = three(K10, V10, K11, V11, T10, T11, T12), 2404 NewT1 = two(K11, V11, T11, T12), 2405 Node = two(K0, V0, T0, T10), 2406 Tout = two(K10, V10, Node, NewT1), 2407 RH = no. 2408fix_2node_t0(K0, V0, T0, T1, Tout, RH) :- 2409 % move T0 one level down and combine it with the subtrees of T1 2410 % this reduces the depth of the tree 2411 T1 = two(K10, V10, T10, T11), 2412 Tout = three(K0, V0, K10, V10, T0, T10, T11), 2413 RH = yes. 2414fix_2node_t0(_K0, _V0, _T0, T1, _Tout, _RH) :- 2415 T1 = empty, 2416 error("unbalanced 234 tree"). 2417 % Tout = two(K0, V0, T0, T1), 2418 % RH = yes 2419 2420% :- pred fix_2node_t1(K, V, tree234(K, V), tree234(K, V), tree234(K, V), bool). 2421% :- mode fix_2node_t1(di, di, di, di, uo, out) is det. 2422% :- mode fix_2node_t1(in, in, in, in, out, out) is det. 2423 2424fix_2node_t1(K0, V0, T0, T1, Tout, RH) :- 2425 % steal T0's leftmost subtree and combine it with T1 2426 T0 = four(K00, V00, K01, V01, K02, V02, T00, T01, T02, T03), 2427 NewT0 = three(K00, V00, K01, V01, T00, T01, T02), 2428 Node = two(K0, V0, T03, T1), 2429 Tout = two(K02, V02, NewT0, Node), 2430 RH = no. 2431fix_2node_t1(K0, V0, T0, T1, Tout, RH) :- 2432 % steal T0's leftmost subtree and combine it with T1 2433 T0 = three(K00, V00, K01, V01, T00, T01, T02), 2434 NewT0 = two(K00, V00, T00, T01), 2435 Node = two(K0, V0, T02, T1), 2436 Tout = two(K01, V01, NewT0, Node), 2437 RH = no. 2438fix_2node_t1(K0, V0, T0, T1, Tout, RH) :- 2439 % move T1 one level down and combine it with the subtrees of T0 2440 % this reduces the depth of the tree 2441 T0 = two(K00, V00, T00, T01), 2442 Tout = three(K00, V00, K0, V0, T00, T01, T1), 2443 RH = yes. 2444fix_2node_t1(_K0, _V0, T0, _T1, _Tout, _RH) :- 2445 T0 = empty, 2446 error("unbalanced 234 tree"). 2447 % Tout = two(K0, V0, T0, T1), 2448 % RH = yes 2449 2450% :- pred fix_3node_t0(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V), 2451% tree234(K, V), bool). 2452% :- mode fix_3node_t0(di, di, di, di, di, di, di, uo, out) is det. 2453% :- mode fix_3node_t0(in, in, in, in, in, in, in, out, out) is det. 2454 2455fix_3node_t0(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :- 2456 % steal T1's leftmost subtree and combine it with T0 2457 T1 = four(K10, V10, K11, V11, K12, V12, T10, T11, T12, T13), 2458 NewT1 = three(K11, V11, K12, V12, T11, T12, T13), 2459 Node = two(K0, V0, T0, T10), 2460 Tout = three(K10, V10, K1, V1, Node, NewT1, T2), 2461 RH = no. 2462fix_3node_t0(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :- 2463 % steal T1's leftmost subtree and combine it with T0 2464 T1 = three(K10, V10, K11, V11, T10, T11, T12), 2465 NewT1 = two(K11, V11, T11, T12), 2466 Node = two(K0, V0, T0, T10), 2467 Tout = three(K10, V10, K1, V1, Node, NewT1, T2), 2468 RH = no. 2469fix_3node_t0(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :- 2470 % move T0 one level down to become the leftmost subtree of T1 2471 T1 = two(K10, V10, T10, T11), 2472 NewT1 = three(K0, V0, K10, V10, T0, T10, T11), 2473 Tout = two(K1, V1, NewT1, T2), 2474 RH = no. 2475fix_3node_t0(_K0, _V0, _K1, _V1, _T0, T1, _T2, _Tout, _RH) :- 2476 T1 = empty, 2477 error("unbalanced 234 tree"). 2478 % Tout = three(K0, V0, K1, V1, T0, T1, T2), 2479 % The heights of T1 and T2 are unchanged 2480 % RH = no 2481 2482% :- pred fix_3node_t1(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V), 2483% tree234(K, V), bool). 2484% :- mode fix_3node_t1(di, di, di, di, di, di, di, uo, out) is det. 2485% :- mode fix_3node_t1(in, in, in, in, in, in, in, out, out) is det. 2486 2487fix_3node_t1(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :- 2488 % steal T0's rightmost subtree and combine it with T1 2489 T0 = four(K00, V00, K01, V01, K02, V02, T00, T01, T02, T03), 2490 NewT0 = three(K00, V00, K01, V01, T00, T01, T02), 2491 Node = two(K0, V0, T03, T1), 2492 Tout = three(K02, V02, K1, V1, NewT0, Node, T2), 2493 RH = no. 2494fix_3node_t1(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :- 2495 % steal T0's rightmost subtree and combine it with T1 2496 T0 = three(K00, V00, K01, V01, T00, T01, T02), 2497 NewT0 = two(K00, V00, T00, T01), 2498 Node = two(K0, V0, T02, T1), 2499 Tout = three(K01, V01, K1, V1, NewT0, Node, T2), 2500 RH = no. 2501fix_3node_t1(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :- 2502 % move T1 one level down to become the rightmost subtree of T0 2503 T0 = two(K00, V00, T00, T01), 2504 NewT0 = three(K00, V00, K0, V0, T00, T01, T1), 2505 Tout = two(K1, V1, NewT0, T2), 2506 RH = no. 2507fix_3node_t1(_K0, _V0, _K1, _V1, T0, _T1, _T2, _Tout, _RH) :- 2508 T0 = empty, 2509 error("unbalanced 234 tree"). 2510 % Tout = three(K0, V0, K1, V1, T0, T1, T2), 2511 % The heights of T0 and T2 are unchanged 2512 % RH = no 2513 2514% :- pred fix_3node_t2(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V), 2515% tree234(K, V), bool). 2516% :- mode fix_3node_t2(di, di, di, di, di, di, di, uo, out) is det. 2517% :- mode fix_3node_t2(in, in, in, in, in, in, in, out, out) is det. 2518 2519fix_3node_t2(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :- 2520 % steal T1's rightmost subtree and combine it with T2 2521 T1 = four(K10, V10, K11, V11, K12, V12, T10, T11, T12, T13), 2522 NewT1 = three(K10, V10, K11, V11, T10, T11, T12), 2523 Node = two(K1, V1, T13, T2), 2524 Tout = three(K0, V0, K12, V12, T0, NewT1, Node), 2525 RH = no. 2526fix_3node_t2(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :- 2527 % steal T1's rightmost subtree and combine it with T2 2528 T1 = three(K10, V10, K11, V11, T10, T11, T12), 2529 NewT1 = two(K10, V10, T10, T11), 2530 Node = two(K1, V1, T12, T2), 2531 Tout = three(K0, V0, K11, V11, T0, NewT1, Node), 2532 RH = no. 2533fix_3node_t2(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :- 2534 % move T2 one level down to become the rightmost subtree of T1 2535 T1 = two(K10, V10, T10, T11), 2536 NewT1 = three(K10, V10, K1, V1, T10, T11, T2), 2537 Tout = two(K0, V0, T0, NewT1), 2538 RH = no. 2539fix_3node_t2(_K0, _V0, _K1, _V1, _T0, T1, _T2, _Tout, _RH) :- 2540 T1 = empty, 2541 error("unbalanced 234 tree"). 2542 % Tout = three(K0, V0, K1, V1, T0, T1, T2), 2543 % The heights of T0 and T1 are unchanged 2544 % RH = no 2545 2546% :- pred fix_4node_t0(K, V, K, V, K, V, 2547% tree234(K, V), tree234(K, V), tree234(K, V), tree234(K, V), 2548% tree234(K, V), bool). 2549% :- mode fix_4node_t0(di, di, di, di, di, di, di, di, di, di, uo, out) is det. 2550% :- mode fix_4node_t0(in, in, in, in, in, in, in, in, in, in, out, out) is det. 2551 2552fix_4node_t0(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2553 % steal T1's leftmost subtree and combine it with T0 2554 T1 = four(K10, V10, K11, V11, K12, V12, T10, T11, T12, T13), 2555 NewT1 = three(K11, V11, K12, V12, T11, T12, T13), 2556 Node = two(K0, V0, T0, T10), 2557 Tout = four(K10, V10, K1, V1, K2, V2, Node, NewT1, T2, T3), 2558 RH = no. 2559fix_4node_t0(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2560 % steal T1's leftmost subtree and combine it with T0 2561 T1 = three(K10, V10, K11, V11, T10, T11, T12), 2562 NewT1 = two(K11, V11, T11, T12), 2563 Node = two(K0, V0, T0, T10), 2564 Tout = four(K10, V10, K1, V1, K2, V2, Node, NewT1, T2, T3), 2565 RH = no. 2566fix_4node_t0(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2567 % move T0 one level down to become the leftmost subtree of T1 2568 T1 = two(K10, V10, T10, T11), 2569 NewT1 = three(K0, V0, K10, V10, T0, T10, T11), 2570 Tout = three(K1, V1, K2, V2, NewT1, T2, T3), 2571 RH = no. 2572fix_4node_t0(_K0, _V0, _K1, _V1, _K2, _V2, _T0, T1, _T2, _T3, _Tout, _RH) :- 2573 T1 = empty, 2574 error("unbalanced 234 tree"). 2575 % Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 2576 % The heights of T1, T2 and T3 are unchanged 2577 % RH = no 2578 2579% :- pred fix_4node_t1(K, V, K, V, K, V, 2580% tree234(K, V), tree234(K, V), tree234(K, V), tree234(K, V), 2581% tree234(K, V), bool). 2582% :- mode fix_4node_t1(di, di, di, di, di, di, di, di, di, di, uo, out) is det. 2583% :- mode fix_4node_t1(in, in, in, in, in, in, in, in, in, in, out, out) is det. 2584 2585fix_4node_t1(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2586 % steal T2's leftmost subtree and combine it with T1 2587 T2 = four(K20, V20, K21, V21, K22, V22, T20, T21, T22, T23), 2588 NewT2 = three(K21, V21, K22, V22, T21, T22, T23), 2589 Node = two(K1, V1, T1, T20), 2590 Tout = four(K0, V0, K20, V20, K2, V2, T0, Node, NewT2, T3), 2591 RH = no. 2592fix_4node_t1(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2593 % steal T2's leftmost subtree and combine it with T1 2594 T2 = three(K20, V20, K21, V21, T20, T21, T22), 2595 NewT2 = two(K21, V21, T21, T22), 2596 Node = two(K1, V1, T1, T20), 2597 Tout = four(K0, V0, K20, V20, K2, V2, T0, Node, NewT2, T3), 2598 RH = no. 2599fix_4node_t1(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2600 % move T1 one level down to become the leftmost subtree of T2 2601 T2 = two(K20, V20, T20, T21), 2602 NewT2 = three(K1, V1, K20, V20, T1, T20, T21), 2603 Tout = three(K0, V0, K2, V2, T0, NewT2, T3), 2604 RH = no. 2605fix_4node_t1(_K0, _V0, _K1, _V1, _K2, _V2, _T0, _T1, T2, _T3, _Tout, _RH) :- 2606 T2 = empty, 2607 error("unbalanced 234 tree"). 2608 % Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 2609 % The heights of T0, T2 and T3 are unchanged 2610 % RH = no 2611 2612% :- pred fix_4node_t2(K, V, K, V, K, V, 2613% tree234(K, V), tree234(K, V), tree234(K, V), tree234(K, V), 2614% tree234(K, V), bool). 2615% :- mode fix_4node_t2(di, di, di, di, di, di, di, di, di, di, uo, out) is det. 2616% :- mode fix_4node_t2(in, in, in, in, in, in, in, in, in, in, out, out) is det. 2617 2618fix_4node_t2(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2619 % steal T3's leftmost subtree and combine it with T2 2620 T3 = four(K30, V30, K31, V31, K32, V32, T30, T31, T32, T33), 2621 NewT3 = three(K31, V31, K32, V32, T31, T32, T33), 2622 Node = two(K2, V2, T2, T30), 2623 Tout = four(K0, V0, K1, V1, K30, V30, T0, T1, Node, NewT3), 2624 RH = no. 2625fix_4node_t2(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2626 % steal T3's leftmost subtree and combine it with T2 2627 T3 = three(K30, V30, K31, V31, T30, T31, T32), 2628 NewT3 = two(K31, V31, T31, T32), 2629 Node = two(K2, V2, T2, T30), 2630 Tout = four(K0, V0, K1, V1, K30, V30, T0, T1, Node, NewT3), 2631 RH = no. 2632fix_4node_t2(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2633 % move T2 one level down to become the leftmost subtree of T3 2634 T3 = two(K30, V30, T30, T31), 2635 NewT3 = three(K2, V2, K30, V30, T2, T30, T31), 2636 Tout = three(K0, V0, K1, V1, T0, T1, NewT3), 2637 RH = no. 2638fix_4node_t2(_K0, _V0, _K1, _V1, _K2, _V2, _T0, _T1, _T2, T3, _Tout, _RH) :- 2639 T3 = empty, 2640 error("unbalanced 234 tree"). 2641 % Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 2642 % The heights of T0, T1 and T3 are unchanged 2643 % RH = no 2644 2645% :- pred fix_4node_t3(K, V, K, V, K, V, 2646% tree234(K, V), tree234(K, V), tree234(K, V), tree234(K, V), 2647% tree234(K, V), bool). 2648% :- mode fix_4node_t3(di, di, di, di, di, di, di, di, di, di, uo, out) is det. 2649% :- mode fix_4node_t3(in, in, in, in, in, in, in, in, in, in, out, out) is det. 2650 2651fix_4node_t3(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2652 % steal T2's rightmost subtree and combine it with T3 2653 T2 = four(K20, V20, K21, V21, K22, V22, T20, T21, T22, T23), 2654 NewT2 = three(K20, V20, K21, V21, T20, T21, T22), 2655 Node = two(K2, V2, T23, T3), 2656 Tout = four(K0, V0, K1, V1, K22, V22, T0, T1, NewT2, Node), 2657 RH = no. 2658fix_4node_t3(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2659 % steal T2's rightmost subtree and combine it with T3 2660 T2 = three(K20, V20, K21, V21, T20, T21, T22), 2661 NewT2 = two(K20, V20, T20, T21), 2662 Node = two(K2, V2, T22, T3), 2663 Tout = four(K0, V0, K1, V1, K21, V21, T0, T1, NewT2, Node), 2664 RH = no. 2665fix_4node_t3(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :- 2666 % move T3 one level down to become the rightmost subtree of T2 2667 T2 = two(K20, V20, T20, T21), 2668 NewT2 = three(K20, V20, K2, V2, T20, T21, T3), 2669 Tout = three(K0, V0, K1, V1, T0, T1, NewT2), 2670 RH = no. 2671fix_4node_t3(_K0, _V0, _K1, _V1, _K2, _V2, _T0, _T1, T2, _T3, _Tout, _RH) :- 2672 T2 = empty, 2673 error("unbalanced 234 tree"). 2674 % Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 2675 % The heights of T0, T1 and T2 are unchanged 2676 % RH = no 2677 2678%------------------------------------------------------------------------------% 2679 2680keys(Tree, Keys) :- 2681 keys_2(Tree, [], Keys). 2682 2683% :- pred keys_2(tree234(K, V), list(K), list(K)). 2684% :- mode keys_2(in, in, out) is det. 2685 2686keys_2(empty, List, List). 2687keys_2(two(K0, _V0, T0, T1), L0, L) :- 2688 keys_2(T1, L0, L1), 2689 keys_2(T0, [K0 | L1], L). 2690keys_2(three(K0, _V0, K1, _V1, T0, T1, T2), L0, L) :- 2691 keys_2(T2, L0, L1), 2692 keys_2(T1, [K1 | L1], L2), 2693 keys_2(T0, [K0 | L2], L). 2694keys_2(four(K0, _V0, K1, _V1, K2, _V2, T0, T1, T2, T3), L0, L) :- 2695 keys_2(T3, L0, L1), 2696 keys_2(T2, [K2 | L1], L2), 2697 keys_2(T1, [K1 | L2], L3), 2698 keys_2(T0, [K0 | L3], L). 2699 2700%------------------------------------------------------------------------------% 2701 2702values(Tree, Values) :- 2703 values_2(Tree, [], Values). 2704 2705% :- pred values_2(tree234(K, V), list(V), list(V)). 2706% :- mode values_2(in, in, out) is det. 2707 2708values_2(empty, List, List). 2709values_2(two(_K0, V0, T0, T1), L0, L) :- 2710 values_2(T1, L0, L1), 2711 values_2(T0, [V0 | L1], L). 2712values_2(three(_K0, V0, _K1, V1, T0, T1, T2), L0, L) :- 2713 values_2(T2, L0, L1), 2714 values_2(T1, [V1 | L1], L2), 2715 values_2(T0, [V0 | L2], L). 2716values_2(four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3), L0, L) :- 2717 values_2(T3, L0, L1), 2718 values_2(T2, [V2 | L1], L2), 2719 values_2(T1, [V1 | L2], L3), 2720 values_2(T0, [V0 | L3], L). 2721 2722%------------------------------------------------------------------------------% 2723 2724assoc_list_to_tree234(AssocList, Tree) :- 2725 assoc_list_to_tree234_2(AssocList, empty, Tree). 2726 2727% :- pred assoc_list_to_tree234_2(assoc_list(K, V), tree234(K, V), 2728% tree234(K, V)). 2729% :- mode assoc_list_to_tree234_2(in, in, out) is det. 2730 2731assoc_list_to_tree234_2([], Tree, Tree). 2732assoc_list_to_tree234_2([K - V | Rest], Tree0, Tree) :- 2733 set(Tree0, K, V, Tree1), 2734 assoc_list_to_tree234_2(Rest, Tree1, Tree). 2735 2736%------------------------------------------------------------------------------% 2737 2738tree234_to_assoc_list(Tree, AssocList) :- 2739 tree234_to_assoc_list_2(Tree, [], AssocList). 2740 2741% :- pred tree234_to_assoc_list_2(tree234(K, V), assoc_list(K, V), 2742% assoc_list(K, V)). 2743% :- mode tree234_to_assoc_list_2(in, in, out) is det. 2744 2745tree234_to_assoc_list_2(empty, List, List). 2746tree234_to_assoc_list_2(two(K0, V0, T0, T1), L0, L) :- 2747 tree234_to_assoc_list_2(T1, L0, L1), 2748 tree234_to_assoc_list_2(T0, [K0 - V0 | L1], L). 2749tree234_to_assoc_list_2(three(K0, V0, K1, V1, T0, T1, T2), L0, L) :- 2750 tree234_to_assoc_list_2(T2, L0, L1), 2751 tree234_to_assoc_list_2(T1, [K1 - V1 | L1], L2), 2752 tree234_to_assoc_list_2(T0, [K0 - V0 | L2], L). 2753tree234_to_assoc_list_2(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), 2754 L0, L) :- 2755 tree234_to_assoc_list_2(T3, L0, L1), 2756 tree234_to_assoc_list_2(T2, [K2 - V2 | L1], L2), 2757 tree234_to_assoc_list_2(T1, [K1 - V1 | L2], L3), 2758 tree234_to_assoc_list_2(T0, [K0 - V0 | L3], L). 2759 2760%------------------------------------------------------------------------------% 2761 2762 % count the number of elements in a tree 2763count(empty, 0). 2764count(two(_, _, T0, T1), N) :- 2765 count(T0, N0), 2766 count(T1, N1), 2767 N is 1 + N0 + N1. 2768count(three(_, _, _, _, T0, T1, T2), N) :- 2769 count(T0, N0), 2770 count(T1, N1), 2771 count(T2, N2), 2772 N is 2 + N0 + N1 + N2. 2773count(four(_, _, _, _, _, _, T0, T1, T2, T3), N) :- 2774 count(T0, N0), 2775 count(T1, N1), 2776 count(T2, N2), 2777 count(T3, N3), 2778 N is 3 + N0 + N1 + N2 + N3. 2779 2780