Test if invariants of internal AVL search tree hold.
creates map from sorted array of key-data pairs. The input array must be sorted, as given by the relevant comparator (either in ascending or descending order), and must not contain any duplicate keys. If either of these conditions do not hold, an error is returned.
Test whether a map is empty or not.
map. O(1), but
returns the value bound to the given key, raising
Not_found if none such exists
mem map key tests whether
map contains a binding for
Iterate two maps side by side. Complexity of this function is O(M+N). If two inputs
(0, a); (1, a) and
(1, b); (2, b),
f will be called with
(0, `Left a); (1,
`Both (a, b)); (2, `Right b)
folds over keys and data in map in increasing order of key.
folds over keys and data in map in decreasing order of key.
returns list of keys in map
returns list of data in map
creates association list from map.
symmetric_diff t1 t2 ~data_equal returns a list of changes between
It is intended to be efficient in the case where
t2 share a large amount of
(key, data)pair corresponding to the minimum key in
map, None if empty.
(key, data)pair corresponding to the maximum key in
map, and None if
same semantics as similar functions in List
fold_range_inclusive t ~min ~max ~init ~f
folds f (with initial value ~init) over all keys (and their associated values)
that are in the range
min, max (inclusive).
range_to_alist t ~min ~max returns an associative list of the elements whose
keys lie in
min, max (inclusive), with the smallest key being at the head of the
closest_key t dir k returns the
(key, value) pair in
key closest to
k, which satisfies the given inequality bound.
closest_key t `Less_than k would be the pair with the closest key to
key < k.
to_sequence can be used to get the same results as
closest_key. It is less
efficient for individual lookups but more efficient for finding many elements starting
at some value.
nth t n finds the (key, value) pair of rank n (i.e. such that there are exactly n
keys strictly less than the found key), if one exists. O(log(length t) + n) time.
rank t k if k is in t, returns the number of keys strictly less than k in t,
to_sequence ?order ?keys_greater_or_equal_to ?keys_less_or_equal_to t gives a
sequence of key-value pairs between
keys_greater_or_equal_to inclusive, presented in
keys_greater_or_equal_to > keys_less_or_equal_to, the sequence is empty. Cost is
O(log n) up front and amortized O(1) to produce each element.
This shrinker and the other shrinkers for maps and trees produce a shrunk value by dropping a key-value pair, shrinking a key or shrinking a value. A shrunk key will override an existing key's value.