Returns true iff the map is empty. O(1).
Returns an empty map of the same type and organization, and with the same default, as m.
Returns the number of key-value pairs in the map. O(1).
Returns an arbitrary pair of the map. Specifically, on a nonempty map, returns
three values: an arbitrary key, its associated value, and true; on an empty map, returns nil,
nil, and false. O(1).
If v is not supplied, returns true iff the domain of m contains k. If v is supplied, returns true iff m maps k to v. O(log n).
Returns true iff the domain of m contains k. (This is now redundant with two-argument
contains?, and is mildly deprecated. For most of FSet’s history, contains? on a map
required three arguments; so it was all but useless, and you had to use domain-contains?
instead. Fortunately, I finally came to my senses and fixed contains? to accept two
arguments.) O(log n).
Returns true iff the range of m contains v, that is, if any key is mapped to v. O(n) (requires a linear search).
If m contains a key equal to k, according to its key comparison function, returns three
values: the corresponding value, true, and the key found; otherwise, the map’s default, false, and nil. If the key is not found and the map has no default,
signals an error of type map-domain-error. O(log n).
setf Expander: setf lookup (map) m k v ¶Invoked as (setf (lookup m k) v). Updates the place m (which must
be setf-able) to have a new mapping from k to v. Equivalent to (setf
m (with m k v)), except that subexpressions within m are evaluated
only once.
You can also write (setf (@ m k) v). See The @ Macro.
Returns a map, of the same class and organization as m, that contains all pairs of m
whose key is not equal to k, and also maps k to v. If m already contained a
key equal to k, and the corresponding value is equal to v according to its value
comparison function, returns m itself. (This is so you can find out whether the pair was
added or updated simply by calling eq on m and the result.)
A modify macro that expands to with. If place m
(which must be setf-able) holds a map, updates it so the map now maps k to v.
Returns a map, of the same class and organization as m, that contains all pairs of m
whose key is not equal to k. If m did not contain a key equal to k, according to
its comparison function, returns m itself. (This is so you can find out whether the pair was
removed simply by calling eq on and the result.)
A modify macro that expands to less. If place m
(which must be setf-able) holds a map, updates it so the map does not contain a key k.
If the map has a default, returns it and a true second value; otherwise, returns nil and
false. O(1).
Returns a new map that has all the pairs of m, but whose default is new-default. O(1).
setf Expander: default m new-default ¶(setf (default m) new-default) is equivalent to (setf m (with-default
m new-default)), except that subexpressions within m are evaluated only once.
Returns a new map that has all the pairs of m, but has no default. O(1).
(clear-default m) is equivalent to (setf m (without-default m)),
except that subexpressions within m are evaluated only once.
If m contains key k, returns the index of k within the ordering of m; otherwise
nil. O(log n).
Returns the pair at index idx within the ordering of m. (On a wb-map, this is
the same as at-rank.) rank must be in [0 .. size(s)); otherwise, signals an error of
type simple-type-error. O(log n).
Returns the domain (set of keys) of m, as a set of the same implementation (WB or CHAMP), and using m’s key ordering as its ordering. O(n), but with a relatively small constant factor.
Returns the range of m (the set of values to which any key is mapped), as a set of the same implementation (WB or CHAMP), and using m’s value ordering as its ordering. O(n log n).
Returns a map containing all the keys of m1 and m2, where the value for each key contained in only one map is the value from that map, and the value for each key contained in both maps is the result of calling val-fn on the value from m1 and the value from m2. val-fn defaults to simply returning its second argument, so the entries in m2 simply shadow those in m1. The default for the new map is: if both maps have defaults, the result of calling val-fn on those defaults; if only one map has a default, that default; otherwise none.
map-union assumes that val-fn is idempotent, i.e., if the two values passed to
val-fn are equal, val-fn must return the same value; it often elides calls to
val-fn on that basis.
If val-fn returns the symbol :no-value as a second value, the result will contain no
pair with the corresponding key.
Implements left preference: for any pair of equal keys in the two maps, the result contains the instance that was in m1; the associated value, if the two values are equal, is also that in m1.
Returns a map containing all the keys that are in the domains of both m1 and m2, where the value for each key is the result of calling val-fn on the value from m1 and the value from m2. val-fn defaults to simply returning its second argument, so the entries in m2 simply shadow those in m1. The default for the new map is the result of calling val-fn on the defaults for the two maps, if they both have defaults; else none.
map-intersection assumes that val-fn is idempotent, i.e., if the two values passed
to val-fn are equal, val-fn must return the same value; it often elides calls to
val-fn on that basis.
If val-fn returns :no-value as a second value, the result will contain no pair with the
corresponding key.
Implements left preference: for any pair of equal keys in the two maps, the result contains the instance that was in m1; the associated value, if the two values are equal, is also that in m1.
Returns a map containing all the pairs that are in m1 but not m2.
The default for the returned map is that of m1, if it has a default, except if the defaults are equal, in which case the returned map has no default.
Returns, as two values: a map containing all the pairs that are in m1 but not m2, and one containing all the pairs that are in m2 but not m1.
The default for each returned map is that of its corresponding argument, if it has a default, except if the defaults are equal, in which case neither returned map has a default.
Returns a map containing only those pairs of m whose keys are also in s.
Returns a map containing only those pairs of m whose keys are not also in s.
For each key/value pair of map, binds x to the key and y to the value and executes
body. When done, returns value if supplied, otherwise nil.
Returns a stateful iterator over the map m. The :get
operation returns three values: if there is another key/value pair remaining, returns it as two
values and a true third value, else two nil values and false. Creating an iterator takes
O(log n) time; the :get operation is amortized O(1).
Returns a functional iterator over the map m. The :first
operation returns three values: if the iterator is not empty, returns the first key/value pair as
two values and a true third value, else two nil values and false. Creating an iterator takes
O(log n) time; the :first operation is O(1), and :rest is amortized O(1).
Returns a new map, of the same type and organization as m, containing only those pairs that satisfy pred. pred may be specified as a function or an fbound symbol. O(n ⋅ tc(pred)) + O(r log r), where tc(pred) is the time complexity of pred and r is the size of the result.
Returns a map containing the result of applying fn to each pair of m. That is, fn
is called with both the domain and range values as arguments; it is expected to return two values,
which become the new domain and range values. fn may be specified as a function or an fbound
symbol. key-compare-fn-name and val-compare-fn-name, if supplied, control the
organization of the result; the default for each is the corresponding property of m. The
default of the returned map is nil unless a different default is specified by default,
or no-default? is true.
See also compose, below.
A modify macro that expands to map-image. If place m
(which must be setf-able) holds a map, updates it so the place now contains the image of the
map under fn.
Calls fn repeatedly with three arguments, a state variable and the next key/value pair of
m, storing the result of each call back into the state variable, and finally returning that
result. If initial-value is supplied, it is used as the initial value of the state variable.
Otherwise: if m is nonempty, the initial value is the first element; if m is empty, the
result of reduce is obtained by calling fn with no arguments. In all cases, if
key is provided, it is called on each key/value pair and the resulting two values used in
place of the pair. (Time complexity depends on the behavior of fn.)
Composes a map with another map, a function (possibly specified as an fbound symbol), or a seq (considered as a map from indices to elements). That is, for each pair in m1, the result maps its key to the result of invoking m2, f2, or s2 to its value. If m1 has a default, the value of invoking the second argument on that default becomes the default of the returned map.
In the (map map) and (map seq) cases, takes O(m log n) time, where m is the size of m1 and n is the size of m2 or s2. In the function cases, it obviously depends on the behavior of the function; it will be called m times.
Scans linearly through the keys of m to find an element that matches item according to
key and test. For each element of s, key, a function that defaults to the
identity function, is called on it, and then test is called on item and the result; if
it returns true, find returns two values, the element and its associated value. If no match
is found, find returns two nil values. test defaults to equal?, not
eql.
Normally O(n), but as a special case, if test is equal?, key is not supplied,
and the map’s key comparison function is compare, this does an O(log n) lookup.
Scans linearly through the keys of m to find one for which the result of calling key on it
satisfies pred. key and pred must be functions or fbound symbols. key
defaults to the identity function. Returns two values, the key found and its associated value, or
two nil values if none.
Scans linearly through the keys of m to find one for which the result of calling key on
it does not satisfy pred. key and pred must be functions or fbound symbols.
key defaults to the identity function. Returns two values, the key found and its associated
value, or two nil values if none.
Scans linearly through the keys of m, counting the number that match item according to
key and test. For each key of m, key is called on it, and then test
is called on item and the result; if it returns true, the key is counted. Returns the count.
key and test must be functions or fbound symbols. key defaults to the identity
function; test defaults to equal?, not eql.
Normally O(n), but as a special case, if test is equal?, key is not supplied,
and the map’s key comparison function is compare, this does an O(log n) lookup to return
1 or 0.
Scans linearly through the keys of m to count those for which the result of calling key on them satisfies pred. Returns the count. pred and key must be functions or fbound symbols. key defaults to the identity function.
Scans linearly through the keys of m to count those for which the result of calling key on them does not satisfy pred. Returns the count. pred and key must be functions or fbound symbols. key defaults to the identity function.