## map-with-implicit-keys.api
#
# Maps where the keys are a function of the values.
# This is essentially a Set with a Map-style interface.
# Compiled by:
# src/lib/std/standard.lib# Compare to:
# src/lib/src/set.api# src/lib/src/map.api# This api is implemented in:
# src/lib/src/red-black-map-with-implicit-keys-g.pkgapi Map_With_Implicit_Keys {
#
package key: Key; # Key is from src/lib/src/key.api Map(X);
empty: (X -> key::Key) -> Map(X); # Construct an empty map. *** DIFFERENT FROM map.api ***
is_empty: Map(X) -> Bool; # Return TRUE if and only if the map is empty
singleton: (X, X -> key::Key) -> Map(X); # Construct a singleton map. *** DIFFERENT FROM map.api ***
set: (Map(X), X) -> Map(X);
set' : (X, Map(X)) -> Map(X);
($): (Map(X), 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;
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;
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) -> X) -> (Map(X), Map(Y)) -> Map(X);
keyed_intersect_with: ((key::Key, X, Y) -> X) -> (Map(X), Map(Y)) -> Map(X);
#
# 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(X)) -> (Map(X), Map(Y)) -> Map(X);
keyed_merge_with: ((key::Key, Null_Or(X), Null_Or(Y)) -> Null_Or(X)) -> (Map(X), Map(Y)) -> Map(X);
#
# 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); # map ops make no sense when the key is a function of the value.
# keyed_map: ((key::Key, X) -> Y) -> Map(X) -> Map(Y); # map ops make no sense when the key is a function of the value.
#
# 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); # map ops make no sense when the key is a function of the value.
# keyed_map': ((key::Key, X) -> Null_Or(Y)) -> Map(X) -> Map(Y); # map ops make no sense when the key is a function of the value.
#
# 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.