## map.api
#
# Abstract api for applicative-style finite maps
# (dictionaries) over ordered typelocked keys.
# Compiled by:
# src/lib/std/standard.lib# Compare to:
# src/lib/src/set.api# src/lib/src/numbered-list.api# src/lib/src/tagged-numbered-list.api# src/lib/src/map-with-implicit-keys.api# This api is implemented in:
# src/lib/src/binary-map-g.pkg# src/lib/src/int-binary-map.pkg# src/lib/src/int-list-map.pkg# src/lib/src/int-red-black-map.pkg# src/lib/src/list-map-g.pkg# src/lib/src/red-black-map-g.pkg# src/lib/src/unt-red-black-map.pkgapi Map {
#
package key: Key; # Key is from src/lib/src/key.api Map(X);
empty: Map(X); # The empty map
is_empty: Map(X) -> Bool; # Return TRUE if and only if the map is empty
singleton: (key::Key, X) -> Map(X); # Return the specified singleton map
from_list: List((key::Key, X)) -> Map(X); # Construct a map containing given key-val pairs.
set: (Map(X), key::Key, X) -> Map(X);
set' : ((key::Key, X), Map(X)) -> Map(X);
($): (Map(X), (key::Key, X)) -> Map(X);
# Insert an item.
get: (Map(X), key::Key) # Look for an item, return NULL if the item doesn't exist
->
Null_Or(X);
get_or_raise_exception_not_found: # Fetch an item, raise Raise lib_base::NOT_FOUND if key is not found.
(Map(X), key::Key) # This is intended to be used in cases where it is algorithmically
-> # certain that the key must be present in the map.
X;
contains_key # Return TRUE, iff the key is in the domain of the map
:
(Map(X), key::Key)
->
Bool;
preceding_key: (Map(X), key::Key) -> Null_Or(key::Key);
following_key: (Map(X), key::Key) -> Null_Or(key::Key);
get_and_drop
:
(Map(X), key::Key) # Remove an item, returning new map and THE value removed (or NULL if key was not found).
->
(Map(X), Null_Or(X));
drop: (Map(X), key::Key) # Remove an item, returning new map. This is a no-op if key is not found.
->
Map(X);
first_val_else_null: Map(X) -> Null_Or(X);
first_keyval_else_null: Map(X) -> Null_Or( (key::Key, X) );
#
# Return the first item in the map (or NULL if it is empty).
last_val_else_null: Map(X) -> Null_Or(X);
last_keyval_else_null: Map(X) -> Null_Or( (key::Key, X) );
#
# Return the last item in the map (or NULL if it is empty).
vals_count: Map(X) -> Int;
#
# Return the number of items in the map.
vals_list: Map(X) -> List(X);
keyvals_list: Map(X) -> List( (key::Key, X) );
#
# Return an ordered list of the items (and their keys) in the map.
keys_list: Map(X) -> List(key::Key);
#
# Return an ordered list of the keys in the map.
compare_sequences # Given an ordering on the map's elements,
: # return an ordering on the map.
((X, X) -> Order)
->
(Map(X), Map(X))
->
Order;
difference_with: (Map(X), Map(X)) -> Map(X);
#
# Return a map whose domain contains all keys in first map except
# those present in second map.
union_with: ( (X, X) -> X) -> (Map(X), Map(X)) -> Map(X);
keyed_union_with: ((key::Key, X, X) -> X) -> (Map(X), Map(X)) -> Map(X);
#
# Return a map whose domain is the union of the domains of the two input
# maps, using the supplied function to define the map on elements that
# are in both domains.
intersect_with: ( (X, Y) -> Z) -> (Map(X), Map(Y)) -> Map(Z);
keyed_intersect_with: ((key::Key, X, Y) -> Z) -> (Map(X), Map(Y)) -> Map(Z);
#
# Return a map whose domain is the intersection of the domains of the
# two input maps, using the supplied function to define the range.
merge_with: ( (Null_Or(X), Null_Or(Y)) -> Null_Or(Z)) -> (Map(X), Map(Y)) -> Map(Z);
keyed_merge_with: ((key::Key, Null_Or(X), Null_Or(Y)) -> Null_Or(Z)) -> (Map(X), Map(Y)) -> Map(Z);
#
# Merge two maps using the given function to control the merge.
# For each key k in the union of the two maps domains, the function
# is applied to the image of the key under the map. If the function
# returns THE y, then (k, y) is added to the resulting map.
apply: (X -> Void) -> Map(X) -> Void;
keyed_apply: ((key::Key, X) -> Void) -> Map(X) -> Void;
#
# Apply a function to the entries of the map in map order.
map: (X -> Y) -> Map(X) -> Map(Y);
keyed_map: ((key::Key, X) -> Y) -> Map(X) -> Map(Y);
#
# Create a new map by applying a map function to the
# name/value pairs in the map.
fold_forward: ( (X, Y) -> Y) -> Y -> Map(X) -> Y;
keyed_fold_forward: ((key::Key, X, Y) -> Y) -> Y -> Map(X) -> Y;
#
# Apply a folding function to the entries of the map
# in increasing map order.
fold_backward: ( (X, Y) -> Y) -> Y -> Map(X) -> Y;
keyed_fold_backward: ((key::Key, X, Y) -> Y) -> Y -> Map(X) -> Y;
#
# Apply a folding function to the entries of the map
# in decreasing map order.
filter: ( X -> Bool) -> Map(X) -> Map(X);
keyed_filter: ((key::Key, X) -> Bool) -> Map(X) -> Map(X);
#
# Filter out those elements of the map that do not satisfy the
# predicate. The filtering is done in increasing map order.
map': ( X -> Null_Or(Y)) -> Map(X) -> Map(Y);
keyed_map': ((key::Key, X) -> Null_Or(Y)) -> Map(X) -> Map(Y);
#
# Map a partial function over the elements of a map
# in increasing map order.
all_invariants_hold: Map(X) -> Bool;
debug_print
:
( Map(X), # Print tree structure of this map.
key::Key -> Void, # Here's how to print out the keys.
X -> Void # Here's how to print out the vals.
)
->
Int;
}; # api Map
## COPYRIGHT (c) 1996 by AT&T Research. See SMLNJ-COPYRIGHT file for details.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.