1%---------------------------------------------------------------------------% 2% Copyright (C) 1993-1999 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% File: m_map.pl. 9% Main author: fjh@cs.mu.OZ.AU, conway@cs.mu.OZ.AU. 10% Stability: high. 11% 12% This file provides the (Mercury) 'map' ADT. 13% A map (also known as a dictionary or an associative array) is a collection 14% of (Key,Data) pairs which allows you to look up any Data item given the 15% Key. 16% 17% The implementation is using balanced trees, as provided by 18% m_tree234.pl. Virtually all the predicates in this file just 19% forward the work to the corresponding predicate in m_tree234.pl. 20% 21% Modified for ECLiPSe by Warwick Harvey <wh@icparc.ic.ac.uk>, April 2000, 22% based on revision 1.71 of file mercury/library/map.m from the 23% Mercury CVS repository. See http://www.cs.mu.oz.au/mercury for 24% information about obtaining Mercury. 25% 26% The conversion included stripping out the functional versions of 27% predicates and the higher-order predicates. It also included writing 28% more verbose user-level documentation. 29% 30% Also changed was the type of the second argument of select/3. 31% Since ECLiPSe doesn't have a set ADT, a list has been used instead. 32% 33% This module assumes that keys are ground (so they can't be modified after 34% insertion into the map), but allows the values stored to be variables. 35% 36%-----------------------------------------------------------------------------% 37%-----------------------------------------------------------------------------% 38 39:- module(m_map). 40 41%-----------------------------------------------------------------------------% 42 43% :- type map(_K, _V). 44 45%-----------------------------------------------------------------------------% 46 47:- export 48 init/1, 49 is_empty/1, 50 contains/2, 51 member/3, 52 search/3, 53 lookup/3, 54 lower_bound_search/4, 55 lower_bound_lookup/4, 56 upper_bound_search/4, 57 upper_bound_lookup/4, 58 inverse_search/3, 59 insert/4, 60 det_insert/4, 61 det_insert_from_corresponding_lists/4, 62 det_insert_from_assoc_list/3, 63 update/4, 64 det_update/4, 65 set/4, 66 keys/2, 67 sorted_keys/2, 68 values/2, 69 to_assoc_list/2, 70 to_sorted_assoc_list/2, 71 from_assoc_list/2, 72 from_sorted_assoc_list/2, 73 delete/3, 74 delete_list/3, 75 remove/4, 76 det_remove/4, 77 count/2, 78 from_corresponding_lists/3, 79 merge/3, 80 overlay/3, 81 select/3, 82 apply_to_list/3, 83 optimize/2, 84 remove_smallest/4. 85 86:- comment(categories, ["Data Structures"]). 87:- comment(summary, "The `map' abstract data type."). 88:- comment(author, "Fergus Henderson and Thomas Conway (Mercury) and Warwick Harvey (ECLiPSe)"). 89:- comment(desc, html("\ 90 <P> 91 This module provides the `map' abstract data type. A map, also 92 known as a dictionary or an associative array, is a collection of 93 key/value pairs which allows you to look up any data item given its 94 key. 95 </P> 96 <P> 97 Note that keys must be ground, but values are allowed to be 98 variables. 99 </P> 100 ")). 101 102% :- pred init(map(_,_)). 103% :- mode init(uo) is det. 104:- comment(init/1, [ 105 amode: init(-), 106 args: ["Map":"The new map"], 107 summary: "Initialise a new (empty) map.", 108 fail_if: "Never fails.", 109 resat: no, 110 see_also: [is_empty/1] 111]). 112 113% :- pred is_empty(map(_,_)). 114% :- mode is_empty(in) is semidet. 115:- comment(is_empty/1, [ 116 amode: is_empty(+), 117 args: ["Map":"A map"], 118 summary: "Check whether a map is empty.", 119 fail_if: "Fails if Map is not an empty map.", 120 resat: no, 121 see_also: [init/1] 122]). 123 124% :- pred contains(map(K,_V), K). 125% :- mode contains(in, in) is semidet. 126:- comment(contains/2, [ 127 amode: contains(+, ++), 128 args: ["Map":"A map", 129 "Key":"The key to look for"], 130 summary: "Check whether a map contains a key.", 131 fail_if: "Fails if Key does not appear in Map.", 132 resat: no, 133 see_also: [search/3, keys/2, sorted_keys/2], 134 desc: html("\ 135 <P> 136 This predicate checks the map Map to see whether it contains an 137 entry with key Key. 138 </P> 139 <P> 140 This predicate should only be called with maps created by other 141 predicates from the map module. 142 </P> 143 ") 144]). 145 146% :- pred member(map(K,V), K, V). 147% :- mode member(in, out, out) is nondet. 148:- comment(member/3, [ 149 amode: member(+, ?, ?), 150 args: ["Map":"A map", 151 "Key":"A key from Map", 152 "Value":"The value in Map corresponding to Key"], 153 summary: "Succeeds if Key and Value unify with a key/value pair from Map.", 154 fail_if: "Fails if Key and Value do not unify with a key/value pair from Map.", 155 resat: yes, 156 see_also: [search/3, lookup/3], 157 desc: html("\ 158 <P> 159 Tries to unify Key and Value with key/value pairs from the map Map. 160 </P> 161 <P> 162 If Key and Value are variables and Map is a map, then all 163 members of the map Map are found on backtracking. 164 </P> 165 <P> 166 This predicate should only be called with maps created by other 167 predicates from the map module. 168 </P> 169 ") 170]). 171 172% :- pred search(map(K,V), K, V). 173% :- mode search(in, in, in) is semidet. % implied 174% :- mode search(in, in, out) is semidet. 175:- comment(search/3, [ 176 amode: search(+, ++, ?), 177 args: ["Map":"A map", 178 "Key":"A key to search for", 179 "Value":"The value corresponding to Key"], 180 summary: "Search a map for a key.", 181 fail_if: "Fails if Key does not appear in Map or if Value does not unify with the corresponding value found.", 182 resat: no, 183 see_also: [member/3, lookup/3, inverse_search/3], 184 desc: html("\ 185 <P> 186 This predicate searches the map Map for an entry with key Key. 187 If the key is found, then it attempts to unify the corresponding 188 value with Value. 189 </P> 190 <P> 191 This predicate should only be called with maps created by other 192 predicates from the map module. 193 </P> 194 ") 195]). 196 197% :- pred lookup(map(K,V), K, V). 198% :- mode lookup(in, in, out) is det. 199:- comment(lookup/3, [ 200 amode: lookup(+, ++, ?), 201 args: ["Map":"A map", 202 "Key":"A key to search for", 203 "Value":"The value corresponding to Key"], 204 summary: "Search a map for a key.", 205 fail_if: "Fails if Value does not unify with the value corresponding to Key.", 206 resat: no, 207 see_also: [member/3, search/3], 208 desc: html("\ 209 <P> 210 This predicate searches the map Map for an entry with key Key. 211 If the key is found, then it attempts to unify the corresponding 212 value with Value. If the key is not found, then it aborts with 213 a runtime error. 214 </P> 215 <P> 216 This predicate should only be called with maps created by other 217 predicates from the map module. 218 </P> 219 ") 220]). 221 222% :- pred lower_bound_search(map(K,V), K, K, V). 223% :- mode lower_bound_search(in, in, out, out) is semidet. 224:- comment(lower_bound_search/4, [ 225 amode: lower_bound_search(+, ++, ?, ?), 226 args: ["Map":"A map", 227 "SearchKey":"A key to search for", 228 "Key":"The key found", 229 "Value":"The value corresponding to Key"], 230 summary: "Search a map for the smallest key no smaller than SearchKey.", 231 fail_if: "Fails if there are no keys at least as large as SearchKey in Map or if Key and Value do not unify with the key and value found.", 232 resat: no, 233 see_also: [lower_bound_lookup/4, 234 upper_bound_search/4, 235 upper_bound_lookup/4], 236 desc: html("\ 237 <P> 238 This predicate searches the map Map for the entry with the 239 smallest key which is no smaller than SearchKey. If such a key is 240 found, then it attempts to unify it with Key and the corresponding 241 value with Value. 242 </P> 243 <P> 244 This predicate should only be called with maps created by other 245 predicates from the map module. 246 </P> 247 ") 248]). 249 250% :- pred lower_bound_lookup(map(K,V), K, K, V). 251% :- mode lower_bound_lookup(in, in, out, out) is det. 252:- comment(lower_bound_lookup/4, [ 253 amode: lower_bound_lookup(+, ++, ?, ?), 254 args: ["Map":"A map", 255 "SearchKey":"A key to search for", 256 "Key":"The key found", 257 "Value":"The value corresponding to Key"], 258 summary: "Search a map for the smallest key no smaller than SearchKey.", 259 fail_if: "Fails if Key and Value do not unify with the key and value found.", 260 resat: no, 261 see_also: [lower_bound_search/4, 262 upper_bound_search/4, 263 upper_bound_lookup/4], 264 desc: html("\ 265 <P> 266 This predicate searches the map Map for the entry with the 267 smallest key which is no smaller than SearchKey. If such a key is 268 found, then it attempts to unify it with Key and the corresponding 269 value with Value. If such a key is not found, then it aborts with 270 a runtime error. 271 </P> 272 <P> 273 This predicate should only be called with maps created by other 274 predicates from the map module. 275 </P> 276 ") 277]). 278 279% :- pred upper_bound_search(map(K,V), K, K, V). 280% :- mode upper_bound_search(in, in, out, out) is semidet. 281:- comment(upper_bound_search/4, [ 282 amode: upper_bound_search(+, ++, ?, ?), 283 args: ["Map":"A map", 284 "SearchKey":"A key to search for", 285 "Key":"The key found", 286 "Value":"The value corresponding to Key"], 287 summary: "Search a map for the largest key no larger than SearchKey.", 288 fail_if: "Fails if there are no keys at least as large as SearchKey in Map or if Key and Value do not unify with the key and value found.", 289 resat: no, 290 see_also: [lower_bound_search/4, 291 lower_bound_lookup/4, 292 upper_bound_lookup/4], 293 desc: html("\ 294 <P> 295 This predicate searches the map Map for the entry with the 296 largest key which is no larger than SearchKey. If such a key is 297 found, then it attempts to unify it with Key and the corresponding 298 value with Value. 299 </P> 300 <P> 301 This predicate should only be called with maps created by other 302 predicates from the map module. 303 </P> 304 ") 305]). 306 307% :- pred upper_bound_lookup(map(K,V), K, K, V). 308% :- mode upper_bound_lookup(in, in, out, out) is det. 309:- comment(upper_bound_lookup/4, [ 310 amode: upper_bound_lookup(+, ++, ?, ?), 311 args: ["Map":"A map", 312 "SearchKey":"A key to search for", 313 "Key":"The key found", 314 "Value":"The value corresponding to Key"], 315 summary: "Search a map for the largest key no larger than SearchKey.", 316 fail_if: "Fails if Key and Value do not unify with the key and value found.", 317 resat: no, 318 see_also: [lower_bound_search/4, 319 lower_bound_lookup/4, 320 upper_bound_search/4], 321 desc: html("\ 322 <P> 323 This predicate searches the map Map for the entry with the 324 largest key which is no larger than SearchKey. If such a key is 325 found, then it attempts to unify it with Key and the corresponding 326 value with Value. If such a key is not found, then it aborts with 327 a runtime error. 328 </P> 329 <P> 330 This predicate should only be called with maps created by other 331 predicates from the map module. 332 </P> 333 ") 334]). 335 336% :- pred inverse_search(map(K,V), V, K). 337% :- mode inverse_search(in, in, out) is nondet. 338:- comment(inverse_search/3, [ 339 amode: inverse_search(+, ?, ?), 340 args: ["Map":"A map", 341 "Value":"A value to search for", 342 "Key":"A key corresponding to Value"], 343 summary: "Search a map for a value.", 344 fail_if: "Fails if Value does not appear in Map or if Key does not unify with any corresponding keys found.", 345 resat: yes, 346 see_also: [search/3, member/3], 347 desc: html("\ 348 <P> 349 This predicate searches the map Map for value entries which unify 350 with Value. If such a value is found, then it attempts to unify the 351 corresponding key with Key. 352 </P> 353 <P> 354 This predicate should only be called with maps created by other 355 predicates from the map module. 356 </P> 357 ") 358]). 359 360% :- pred insert(map(K,V), K, V, map(K,V)). 361% :- mode insert(in, in, in, out) is semidet. 362:- comment(insert/4, [ 363 amode: insert(+, ++, ?, -), 364 args: ["Map0":"A map", 365 "Key":"A key to insert", 366 "Value":"The value corresponding to Key", 367 "Map":"The map after insertion"], 368 summary: "Insert a key/value pair into a map, failing if the key already exists.", 369 fail_if: "Fails if Key already appears in Map0.", 370 resat: no, 371 see_also: [det_insert/4, update/4, det_update/4, set/4], 372 desc: html("\ 373 <P> 374 This predicate inserts the key Key with corresponding value Value 375 into the map Map0, resulting in the map Map. If the key Key is 376 already in the map, then the predicate fails. 377 </P> 378 <P> 379 This predicate should only be called with maps created by other 380 predicates from the map module. 381 </P> 382 ") 383]). 384 385% :- pred det_insert(map(K,V), K, V, map(K,V)). 386% :- mode det_insert(in, in, in, out) is det. 387:- comment(det_insert/4, [ 388 amode: det_insert(+, ++, ?, -), 389 args: ["Map0":"A map", 390 "Key":"A key to insert", 391 "Value":"The value corresponding to Key", 392 "Map":"The map after insertion"], 393 summary: "Insert a key/value pair into a map, aborting if the key already exists.", 394 fail_if: "Never fails.", 395 resat: no, 396 see_also: [insert/4, update/4, det_update/4, set/4], 397 desc: html("\ 398 <P> 399 This predicate inserts the key Key with corresponding value Value 400 into the map Map0, resulting in the map Map. If the key Key is 401 already in the map, then the predicate aborts with a runtime error. 402 </P> 403 <P> 404 This predicate should only be called with maps created by other 405 predicates from the map module. 406 </P> 407 ") 408]). 409 410% :- pred det_insert_from_corresponding_lists(map(K,V), list(K), 411% list(V), map(K,V)). 412% :- mode det_insert_from_corresponding_lists(in, in, in, out) is det. 413:- comment(det_insert_from_corresponding_lists/4, [ 414 amode: det_insert_from_corresponding_lists(+, ++, ?, -), 415 args: ["Map0":"A map", 416 "KeyList":"A list of keys to insert", 417 "ValueList":"A list of values corresponding to the keys in KeyList", 418 "Map":"The map after insertion"], 419 summary: "Insert key/value pairs into a map, aborting if any of the keys already exist.", 420 fail_if: "Fails if the lists aren't the same length.", 421 resat: no, 422 see_also: [det_insert/4, det_insert_from_assoc_list/3, from_corresponding_lists/3], 423 desc: html("\ 424 <P> 425 This predicate takes a map Map0, and for each key Key in KeyList 426 and corresponding value Value from ValueList, calls 427 det_insert/4 to insert the Key/Value pair into the map. 428 The result after all the insertions is the map Map. 429 </P> 430 <P> 431 This predicate should only be called with maps created by other 432 predicates from the map module. 433 </P> 434 ") 435]). 436 437% :- pred det_insert_from_assoc_list(map(K,V), assoc_list(K, V), 438% map(K,V)). 439% :- mode det_insert_from_assoc_list(in, in, out) is det. 440:- comment(det_insert_from_assoc_list/3, [ 441 amode: det_insert_from_assoc_list(+, +, -), 442 args: ["Map0":"A map", 443 "List":"A list of Key-Value pairs to insert", 444 "Map":"The map after insertion"], 445 summary: "Insert key/value pairs into a map, aborting if any of the keys already exist.", 446 fail_if: "Never fails.", 447 resat: no, 448 see_also: [det_insert/4, det_insert_from_corresponding_lists/4, from_assoc_list/2, from_sorted_assoc_list/2], 449 desc: html("\ 450 <P> 451 This predicate takes a map Map0, and for each entry in List (of 452 the form Key-Value), calls det_insert/4 to insert the 453 Key/Value pair into the map. The result after all the insertions 454 is the map Map. 455 </P> 456 <P> 457 This predicate should only be called with maps created by other 458 predicates from the map module. 459 </P> 460 ") 461]). 462 463% :- pred update(map(K,V), K, V, map(K,V)). 464% :- mode update(in, in, in, out) is semidet. 465:- comment(update/4, [ 466 amode: update(+, ++, ?, -), 467 args: ["Map0":"A map", 468 "Key":"A key to update", 469 "Value":"The value corresponding to Key", 470 "Map":"The map after updating"], 471 summary: "Update the value corresponding to a key in a map.", 472 fail_if: "Fails if Key does not appear in Map0.", 473 resat: no, 474 see_also: [det_update/4, insert/4, det_insert/4, set/4], 475 desc: html("\ 476 <P> 477 If the key Key already exists in the map Map0, then this predicate 478 updates the corresponding value to be Value. The resulting map is 479 Map. 480 </P> 481 <P> 482 This predicate should only be called with maps created by other 483 predicates from the map module. 484 </P> 485 ") 486]). 487 488% :- pred det_update(map(K,V), K, V, map(K,V)). 489% :- mode det_update(in, in, in, out) is det. 490:- comment(det_update/4, [ 491 amode: det_update(+, ++, ?, -), 492 args: ["Map0":"A map", 493 "Key":"A key to update", 494 "Value":"The value corresponding to Key", 495 "Map":"The map after updating"], 496 summary: "Update the value corresponding to a key in a map, aborting if it doesn't exist.", 497 fail_if: "Never fails.", 498 resat: no, 499 see_also: [update/4, insert/4, det_insert/4, set/4], 500 desc: html("\ 501 <P> 502 If the key Key already exists in the map Map0, then this 503 predicate updates the corresponding value to be Value, resulting 504 in the map Map. If the key Key is not already in the map, 505 then the predicate aborts with a runtime error. 506 </P> 507 <P> 508 This predicate should only be called with maps created by other 509 predicates from the map module. 510 </P> 511 ") 512]). 513 514% :- pred set(map(K,V), K, V, map(K,V)). 515% :- mode set(di, di, di, uo) is det. 516% :- mode set(in, in, in, out) is det. 517:- comment(set/4, [ 518 amode: set(+, ++, ?, -), 519 args: ["Map0":"A map", 520 "Key":"A key to set", 521 "Value":"The value corresponding to Key", 522 "Map":"The map after setting"], 523 summary: "Update the value corresponding to a key in a map, inserting the key if it doesn't exist already.", 524 fail_if: "Never fails.", 525 resat: no, 526 see_also: [insert/4, det_insert/4, update/4, det_update/4], 527 desc: html("\ 528 <P> 529 If the key Key already exists in the map Map0, then this predicate 530 updates the corresponding value to be Value. Otherwise it inserts 531 the key Key into the map with value Value. The resulting map is 532 Map. 533 </P> 534 <P> 535 This predicate should only be called with maps created by other 536 predicates from the map module. 537 </P> 538 ") 539]). 540 541% :- pred keys(map(K, _V), list(K)). 542% :- mode keys(in, out) is det. 543:- comment(keys/2, [ 544 amode: keys(+, -), 545 args: ["Map":"A map", 546 "KeyList":"A list of all the keys from Map"], 547 summary: "Return all the keys from a map.", 548 fail_if: "Never fails.", 549 resat: no, 550 see_also: [sorted_keys/2, values/2], 551 desc: html("\ 552 <P> 553 KeyList is a list of all the keys appearing in the map Map. 554 </P> 555 <P> 556 This predicate should only be called with maps created by other 557 predicates from the map module. 558 </P> 559 ") 560]). 561 562% :- pred sorted_keys(map(K, _V), list(K)). 563% :- mode sorted_keys(in, out) is det. 564:- comment(sorted_keys/2, [ 565 amode: sorted_keys(+, -), 566 args: ["Map":"A map", 567 "KeyList":"A list of all the keys from Map"], 568 summary: "Return all the keys from a map, in sorted order.", 569 fail_if: "Never fails.", 570 resat: no, 571 see_also: [keys/2, values/2], 572 desc: html("\ 573 <P> 574 KeyList is a list of all the keys appearing in the map Map, in 575 sorted order. 576 </P> 577 <P> 578 This predicate should only be called with maps created by other 579 predicates from the map module. 580 </P> 581 ") 582]). 583 584% :- pred values(map(_K, V), list(V)). 585% :- mode values(in, out) is det. 586:- comment(values/2, [ 587 amode: values(+, -), 588 args: ["Map":"A map", 589 "ValueList":"A list of all the values from Map"], 590 summary: "Return all the values from a map.", 591 fail_if: "Never fails.", 592 resat: no, 593 see_also: [values/2], 594 desc: html("\ 595 <P> 596 ValueList is a list of all the values appearing in the map Map. 597 </P> 598 <P> 599 This predicate should only be called with maps created by other 600 predicates from the map module. 601 </P> 602 ") 603]). 604 605% :- pred to_assoc_list(map(K,V), assoc_list(K,V)). 606% :- mode to_assoc_list(in, out) is det. 607:- comment(to_assoc_list/2, [ 608 amode: to_assoc_list(+, -), 609 args: ["Map":"A map", 610 "AssocList":"A list of the key-value pairs from Map"], 611 summary: "Converts a map into an association list.", 612 fail_if: "Never fails.", 613 resat: no, 614 see_also: [to_sorted_assoc_list/2, from_assoc_list/2], 615 desc: html("\ 616 <P> 617 AssocList is a list containing the key/value pairs from the map 618 Map, in the form Key-Value. 619 </P> 620 <P> 621 This predicate should only be called with maps created by other 622 predicates from the map module. 623 </P> 624 ") 625]). 626 627% :- pred to_sorted_assoc_list(map(K,V), assoc_list(K,V)). 628% :- mode to_sorted_assoc_list(in, out) is det. 629:- comment(to_sorted_assoc_list/2, [ 630 amode: to_sorted_assoc_list(+, -), 631 args: ["Map":"A map", 632 "AssocList":"A sorted list of the key-value pairs from Map"], 633 summary: "Converts a map into a (sorted) association list.", 634 fail_if: "Never fails.", 635 resat: no, 636 see_also: [to_assoc_list/2, from_sorted_assoc_list/2], 637 desc: html("\ 638 <P> 639 AssocList is a sorted list containing the key/value pairs from the 640 map Map, in the form Key-Value. 641 </P> 642 <P> 643 This predicate should only be called with maps created by other 644 predicates from the map module. 645 </P> 646 ") 647]). 648 649% :- pred from_assoc_list(assoc_list(K,V), map(K,V)). 650% :- mode from_assoc_list(in, out) is det. 651:- comment(from_assoc_list/2, [ 652 amode: from_assoc_list(+, -), 653 args: ["AssocList":"A list of key-value pairs", 654 "Map":"A map"], 655 summary: "Converts an association list into a map.", 656 fail_if: "Never fails.", 657 resat: no, 658 see_also: [to_assoc_list/2, from_sorted_assoc_list/2], 659 desc: html("\ 660 <P> 661 AssocList is a list of key/value pairs of the form Key-Value, 662 and Map is a map containing these key/value pairs. If a key 663 appears more than once in AssocList, then its corresponding value 664 in the map Map will be the last one appearing in AssocList. 665 </P> 666 ") 667]). 668 669% :- pred from_sorted_assoc_list(assoc_list(K,V), map(K,V)). 670% :- mode from_sorted_assoc_list(in, out) is det. 671:- comment(from_sorted_assoc_list/2, [ 672 amode: from_sorted_assoc_list(+, -), 673 args: ["AssocList":"A sorted list of key-value pairs", 674 "Map":"A map"], 675 summary: "Converts a sorted association list into a map.", 676 fail_if: "Never fails.", 677 resat: no, 678 see_also: [to_sorted_assoc_list/2, from_assoc_list/2], 679 desc: html("\ 680 <P> 681 AssocList is a sorted list of key/value pairs of the form Key-Value, 682 and Map is a map containing these key/value pairs. If a key 683 appears more than once in AssocList, then its corresponding value 684 in the map Map will be the last one appearing in AssocList. 685 </P> 686 ") 687]). 688 689% :- pred delete(map(K,V), K, map(K,V)). 690% :- mode delete(di, in, uo) is det. 691% :- mode delete(in, in, out) is det. 692:- comment(delete/3, [ 693 amode: delete(+, ++, -), 694 args: ["Map0":"A map", 695 "Key":"The key to delete", 696 "Map":"The map after deletion"], 697 summary: "Delete a key/value pair from a map.", 698 fail_if: "Never fails.", 699 resat: no, 700 see_also: [delete_list/3, remove/4], 701 desc: html("\ 702 <P> 703 If the key Key appears in the map Map0, then remove it and its 704 corresponding value, resulting in the map Map. If the key Key 705 does not appear, Map is simply bound to Map0. 706 </P> 707 <P> 708 This predicate should only be called with maps created by other 709 predicates from the map module. 710 </P> 711 ") 712]). 713 714% :- pred delete_list(map(K,V), list(K), map(K,V)). 715% :- mode delete_list(di, in, uo) is det. 716% :- mode delete_list(in, in, out) is det. 717:- comment(delete_list/3, [ 718 amode: delete_list(+, ++, -), 719 args: ["Map0":"A map", 720 "KeyList":"A list of keys to delete", 721 "Map":"The map after deletions"], 722 summary: "Delete a list of key/value pairs from a map.", 723 fail_if: "Never fails.", 724 resat: no, 725 see_also: [delete/3, remove/4], 726 desc: html("\ 727 <P> 728 This predicate takes a map Map0, and for each key in KeyList, 729 calls delete/3 to delete the key and its corresponding 730 value. The result after all the deletions is the map Map. 731 </P> 732 <P> 733 This predicate should only be called with maps created by other 734 predicates from the map module. 735 </P> 736 ") 737]). 738 739% :- pred remove(map(K,V), K, V, map(K,V)). 740% :- mode remove(in, in, out, out) is semidet. 741:- comment(remove/4, [ 742 amode: remove(+, ++, ?, -), 743 args: ["Map0":"A map", 744 "Key":"The key to remove", 745 "Value":"The value corresponding to Key", 746 "Map":"The map after removal"], 747 summary: "Remove a key/value pair from a map, failing if the key is not present.", 748 fail_if: "Fails is Key does not appear in Map0 or if Value does not unify with the corresponding value.", 749 resat: no, 750 see_also: [delete/3, det_remove/4, remove_smallest/4], 751 desc: html("\ 752 <P> 753 If the key Key appears in the map Map0, then remove it and attempt 754 to unify its corresponding value with Value. Map is Map0 with the 755 key removed. 756 </P> 757 <P> 758 This predicate should only be called with maps created by other 759 predicates from the map module. 760 </P> 761 ") 762]). 763 764% :- pred det_remove(map(K,V), K, V, map(K,V)). 765% :- mode det_remove(in, in, out, out) is det. 766:- comment(det_remove/4, [ 767 amode: det_remove(+, ++, ?, -), 768 args: ["Map0":"A map", 769 "Key":"The key to remove", 770 "Value":"The value corresponding to Key", 771 "Map":"The map after removal"], 772 summary: "Remove a key/value pair from a map, aborting if the key is not present.", 773 fail_if: "Fails if Value does not unify with the value corresponding to Key.", 774 resat: no, 775 see_also: [delete/3, remove/4], 776 desc: html("\ 777 <P> 778 This predicate removes the key Key and its corresponding value from 779 the map Map0, resulting in the map Map. It then attempts to 780 unify the removed value with Value. If the key Key was not in the 781 map Map0, then the predicate aborts with a runtime error. 782 </P> 783 <P> 784 This predicate should only be called with maps created by other 785 predicates from the map module. 786 </P> 787 ") 788]). 789 790% :- pred count(map(K, V), int). 791% :- mode count(in, out) is det. 792:- comment(count/2, [ 793 amode: count(+, ?), 794 args: ["Map":"A map", 795 "Count":"The number of elements in Map"], 796 summary: "Count the number of elements in a map.", 797 fail_if: "Fails if Count does not unify with the number of elements in Map.", 798 resat: no, 799 desc: html("\ 800 <P> 801 Counts the number of elements in the map Map, and attempts to 802 unify the result with Count. 803 </P> 804 <P> 805 This predicate should only be called with maps created by other 806 predicates from the map module. 807 </P> 808 ") 809]). 810 811% :- pred from_corresponding_lists(list(K), list(V), map(K, V)). 812% :- mode from_corresponding_lists(in, in, out) is det. 813:- comment(from_corresponding_lists/3, [ 814 amode: from_corresponding_lists(++, ?, -), 815 args: ["KeyList":"A list of keys", 816 "ValueList":"A list of values corresponding to the keys in KeyList", 817 "Map":"The created map"], 818 summary: "Converts a corresponding pair of lists into a map.", 819 fail_if: "Fails if the lists aren't the same length.", 820 resat: no, 821 see_also: [from_assoc_list/2, det_insert_from_corresponding_lists/4], 822 desc: html("\ 823 <P> 824 Converts a list of keys KeyList and a corresponding list of values 825 ValueList into a map Map. If a key appears more than once in 826 KeyList, then its corresponding value in the map Map will be 827 the last one appearing in AssocList. 828 </P> 829 ") 830]). 831 832% :- pred merge(map(K, V), map(K, V), map(K, V)). 833% :- mode merge(in, in, out) is det. 834:- comment(merge/3, [ 835 amode: merge(+, +, -), 836 args: ["MapA":"A map to merge", 837 "MapB":"The other map to merge", 838 "Map":"The merged map"], 839 summary: "Merges two maps into one.", 840 fail_if: "Never fails.", 841 resat: no, 842 see_also: [overlay/3], 843 desc: html("\ 844 <P> 845 The map Map is the result of merging the map MapA and the map MapB; 846 i.e. Map contains all the key/value pairs from both MapA and MapB. 847 If MapA and MapB have a key in common, then it is not defined 848 which corresponding value will end up associated with that key 849 in Map. 850 </P> 851 <P> 852 This predicate should only be called with maps created by other 853 predicates from the map module. 854 </P> 855 ") 856]). 857 858% :- pred overlay(map(K,V), map(K,V), map(K,V)). 859% :- mode overlay(in, in, out) is det. 860:- comment(overlay/3, [ 861 amode: overlay(+, +, -), 862 args: ["MapA":"A map", 863 "MapB":"The map to overlay", 864 "Map":"The resulting map"], 865 summary: "Overlays one map over another.", 866 fail_if: "Never fails.", 867 resat: no, 868 see_also: [merge/3], 869 desc: html("\ 870 <P> 871 The map Map contains a key/value pair for every key that appears in 872 either the map MapA or the map MapB. If a key Key appears in MapB, 873 then its corresponding value in Map is that appearing in MapB; 874 otherwise it is that appearing in MapA. 875 </P> 876 <P> 877 This predicate should only be called with maps created by other 878 predicates from the map module. 879 </P> 880 ") 881]). 882 883% Mercury version: 884% :- pred select(map(K,V), set(K), map(K,V)). 885% ECLiPSe version: 886% :- pred select(map(K,V), list(K), map(K,V)). 887% :- mode select(in, in, out) is det. 888:- comment(select/3, [ 889 amode: select(+, ++, -), 890 args: ["Map0":"A map", 891 "KeyList":"A list of keys to select", 892 "Map":"The resulting map"], 893 summary: "Creates a new map containing just those entries corresponding to a given list of keys.", 894 fail_if: "Never fails.", 895 resat: no, 896 desc: html("\ 897 <P> 898 The map Map contains the key/value pairs from the map Map0 where 899 the key appears in the list KeyList. Keys in KeyList which do not 900 appear in Map0 are ignored. 901 </P> 902 <P> 903 This predicate should only be called with maps created by other 904 predicates from the map module. 905 </P> 906 ") 907]). 908 909% :- pred apply_to_list(list(K), map(K, V), list(V)). 910% :- mode apply_to_list(in, in, out) is det. 911:- comment(apply_to_list/3, [ 912 amode: apply_to_list(++, +, ?), 913 args: ["KeyList":"A list of keys to map", 914 "Map":"The map to apply", 915 "ValueList":"The list of corresponding values"], 916 summary: "Map a list of keys to their corresponding values.", 917 fail_if: "Fails if ValueList does not unify with the list of values corresponding to KeyList.", 918 resat: no, 919 see_also: [lookup/3], 920 desc: html("\ 921 <P> 922 This predicate applies the map Map to a list of keys KeyList to 923 produce the list of values ValueList; i.e. it maps a list of keys 924 to their corresponding values. If one of the keys in KeyList is 925 not found in Map, then the predicate aborts witha runtime error. 926 </P> 927 <P> 928 This predicate should only be called with maps created by other 929 predicates from the map module. 930 </P> 931 ") 932]). 933 934% :- pred optimize(map(K, V), map(K, V)). 935% :- mode optimize(in, out) is det. 936:- comment(optimize/2, [ 937 amode: optimize(+, -), 938 args: ["Map0":"A map to optimize", 939 "Map":"The optimized map"], 940 summary: "Optimize a map for many lookups but few/no modification.", 941 fail_if: "Never fails.", 942 resat: no, 943 desc: html("\ 944 <P> 945 Declaratively, this predicate does nothing (i.e. the map Map is 946 equivalent to the map Map0). However, operationally it suggests to 947 the implementation that the representation of the map be optimised 948 for lookups, with few or no modifications to be expected. 949 </P> 950 <P> 951 This predicate should only be called with maps created by other 952 predicates from the map module. 953 </P> 954 ") 955]). 956 957% :- pred remove_smallest(map(K, V), K, V, map(K, V)). 958% :- mode remove_smallest(in, out, out, out) is semidet. 959:- comment(remove_smallest/4, [ 960 amode: remove_smallest(+, ?, ?, -), 961 args: ["Map0":"A map", 962 "Key":"The key removed", 963 "Value":"The value corresponding to Key", 964 "Map":"The map after removal"], 965 summary: "Remove the smallest key and its corresponding value from a map.", 966 fail_if: "Fails if Map0 is empty or if Key and Value do not unify with the key and value removed.", 967 resat: no, 968 see_also: [remove/4], 969 desc: html("\ 970 <P> 971 Removes the smallest key in the map Map0 (resulting in the 972 map Map), and attempts to unify the removed key with Key and 973 its corresponding value with Value. 974 </P> 975 <P> 976 This predicate should only be called with maps created by other 977 predicates from the map module. 978 </P> 979 ") 980]). 981 982%-----------------------------------------------------------------------------% 983 984:- lib(m_tree234). 985:- lib(mercury). 986 987% :- type map(K,V) == tree234(K,V). 988 989%-----------------------------------------------------------------------------% 990%-----------------------------------------------------------------------------% 991 992init(M) :- 993 m_tree234:init(M). 994 995is_empty(M) :- 996 m_tree234:is_empty(M). 997 998contains(Map, K) :- 999 search(Map, K, _). 1000 1001member(Map, K, V) :- 1002 m_tree234:member(Map, K, V). 1003 1004search(Map, K, V) :- 1005 m_tree234:search(Map, K, V). 1006 1007lookup(Map, K, V) :- 1008 ( m_tree234:search(Map, K, V1) -> 1009 V = V1 1010 ; 1011 report_lookup_error("lookup: key not found", K, V) 1012 ). 1013 1014lower_bound_search(Map, SearchK, K, V) :- 1015 m_tree234:lower_bound_search(Map, SearchK, K, V). 1016 1017lower_bound_lookup(Map, SearchK, K, V) :- 1018 ( m_tree234:lower_bound_search(Map, SearchK, K1, V1) -> 1019 K = K1, 1020 V = V1 1021 ; 1022 report_lookup_error("lower_bound_lookup: key not found", 1023 SearchK, V) 1024 ). 1025 1026upper_bound_search(Map, SearchK, K, V) :- 1027 m_tree234:upper_bound_search(Map, SearchK, K, V). 1028 1029upper_bound_lookup(Map, SearchK, K, V) :- 1030 ( m_tree234:upper_bound_search(Map, SearchK, K1, V1) -> 1031 K = K1, 1032 V = V1 1033 ; 1034 report_lookup_error("upper_bound_lookup: key not found", 1035 SearchK, V) 1036 ). 1037 1038insert(Map0, K, V, Map) :- 1039 m_tree234:insert(Map0, K, V, Map). 1040 1041det_insert(Map0, K, V, Map) :- 1042 ( m_tree234:insert(Map0, K, V, Map1) -> 1043 Map = Map1 1044 ; 1045 report_lookup_error("det_insert: key already present", 1046 K, V) 1047 ). 1048 1049det_insert_from_corresponding_lists(Map0, Ks, Vs, Map) :- 1050 ( 1051 foreach(K, Ks), foreach(V, Vs), 1052 fromto(Map0, Map_In, Map_Out, Map) 1053 do 1054 det_insert(Map_In, K, V, Map_Out) 1055 ). 1056 1057det_insert_from_assoc_list(Map, [], Map). 1058det_insert_from_assoc_list(Map0, [K - V | KVs], Map) :- 1059 det_insert(Map0, K, V, Map1), 1060 det_insert_from_assoc_list(Map1, KVs, Map). 1061 1062update(Map0, K, V, Map) :- 1063 m_tree234:update(Map0, K, V, Map). 1064 1065det_update(Map0, K, V, Map) :- 1066 ( m_tree234:update(Map0, K, V, Map1) -> 1067 Map = Map1 1068 ; 1069 report_lookup_error("det_update: key not found", K, V) 1070 ). 1071 1072set(Map0, K, V, Map) :- 1073 m_tree234:set(Map0, K, V, Map). 1074 1075keys(Map, KeyList) :- 1076 m_tree234:keys(Map, KeyList). 1077 1078sorted_keys(Map, KeyList) :- 1079 % Guaranteed to yield sorted lists. 1080 m_tree234:keys(Map, KeyList). 1081 1082values(Map, KeyList) :- 1083 m_tree234:values(Map, KeyList). 1084 1085to_assoc_list(M, L) :- 1086 m_tree234:tree234_to_assoc_list(M, L). 1087 1088to_sorted_assoc_list(M, L) :- 1089 % Guaranteed to yield sorted lists. 1090 m_tree234:tree234_to_assoc_list(M, L). 1091 1092from_assoc_list(L, M) :- 1093 m_tree234:assoc_list_to_tree234(L, M). 1094 1095from_sorted_assoc_list(L, M) :- 1096 m_tree234:assoc_list_to_tree234(L, M). 1097 1098delete(Map0, Key, Map) :- 1099 m_tree234:delete(Map0, Key, Map). 1100 1101delete_list(Map, [], Map). 1102delete_list(Map0, [Key | Keys], Map) :- 1103 delete(Map0, Key, Map1), 1104 delete_list(Map1, Keys, Map). 1105 1106remove(Map0, Key, Value, Map) :- 1107 m_tree234:remove(Map0, Key, Value, Map). 1108 1109det_remove(Map0, Key, Value, Map) :- 1110 ( m_tree234:remove(Map0, Key, Value1, Map1) -> 1111 Value = Value1, 1112 Map = Map1 1113 ; 1114 report_lookup_error("det_remove: key not found", 1115 Key, Value) 1116 ). 1117 1118count(Map, Count) :- 1119 m_tree234:count(Map, Count). 1120 1121%-----------------------------------------------------------------------------% 1122 1123 % XXX inefficient 1124 1125inverse_search(Map, V, K) :- 1126 m_tree234:tree234_to_assoc_list(Map, AssocList), 1127 assoc_list_member(K, V, AssocList). 1128 1129%-----------------------------------------------------------------------------% 1130 1131 % The code here is deliberately written using very simple 1132 % modes. 1133 % The reason we don't just use member/2 is that we want to 1134 % bootstrap this thing ASAP. 1135 1136% :- pred assoc_list_member(K, V, list(pair(K,V))). 1137% :- mode assoc_list_member(in, out, in) is nondet. 1138% :- mode assoc_list_member(out, in, in) is nondet. 1139% :- mode assoc_list_member(in, in, in) is semidet. 1140assoc_list_member(K, V, [K - V | _]). 1141assoc_list_member(K, V, [_ | Xs]) :- 1142 assoc_list_member(K, V, Xs). 1143 1144%-----------------------------------------------------------------------------% 1145 1146from_corresponding_lists(Keys, Values, Map) :- 1147 %assoc_list__from_corresponding_lists(Keys, Values, AssocList), 1148 ( 1149 foreach(K, Keys), foreach(V, Values), foreach(KV, AssocList) 1150 do 1151 KV = K - V 1152 ), 1153 m_tree234:assoc_list_to_tree234(AssocList, Map). 1154 1155%-----------------------------------------------------------------------------% 1156 1157merge(M0, M1, M) :- 1158 to_assoc_list(M0, ML0), 1159 to_assoc_list(M1, ML1), 1160 %list__merge(ML0, ML1, ML), 1161 eclipse_language:merge(ML0, ML1, ML), 1162 from_sorted_assoc_list(ML, M). 1163 1164%-----------------------------------------------------------------------------% 1165 1166optimize(Map, Map). 1167 1168%-----------------------------------------------------------------------------% 1169 1170overlay(Map0, Map1, Map) :- 1171 to_assoc_list(Map1, AssocList), 1172 overlay_2(AssocList, Map0, Map). 1173 1174% :- pred overlay_2(assoc_list(K,V), map(K,V), map(K,V)). 1175% :- mode overlay_2(in, in, out) is det. 1176 1177overlay_2([], Map, Map). 1178overlay_2([K - V | AssocList], Map0, Map) :- 1179 set(Map0, K, V, Map1), 1180 overlay_2(AssocList, Map1, Map). 1181 1182%-----------------------------------------------------------------------------% 1183 1184select(Original, KeyList, NewMap) :- 1185 init(NewMap0), 1186 select_2(KeyList, Original, NewMap0, NewMap). 1187 1188% :- pred select_2(list(K), map(K,V), map(K,V), map(K,V)). 1189% :- mode select_2(in, in, in, out) is det. 1190 1191select_2([], _Original, New, New). 1192select_2([K|Ks], Original, New0, New) :- 1193 ( 1194 search(Original, K, V) 1195 -> 1196 set(New0, K, V, New1) 1197 ; 1198 New1 = New0 1199 ), 1200 select_2(Ks, Original, New1, New). 1201 1202%-----------------------------------------------------------------------------% 1203 1204apply_to_list([], _, []). 1205apply_to_list([K | Ks], Map, [V | Vs]) :- 1206 lookup(Map, K, V), 1207 apply_to_list(Ks, Map, Vs). 1208 1209%-----------------------------------------------------------------------------% 1210 1211remove_smallest(Map0, K, V, Map) :- 1212 m_tree234:remove_smallest(Map0, K, V, Map). 1213 1214