Map
is a functional data structure (balanced binary tree) implementing finite maps
over a totally-ordered domain, called a "key".
module Or_duplicate = Base__.Map_intf.Or_duplicate
type ('k, 'cmp) comparator
= (module Comparator.S with type comparator_witness = 'cmp and type t = 'k)
val comparator_s : ('a, _, 'cmp) t ‑> ('a, 'cmp) comparator
Returns a first-class module that can be used to build other map/set/etc. with the same notion of comparison.
val comparator : ('a, _, 'cmp) t ‑> ('a, 'cmp) Comparator.t
val singleton : ('a, 'cmp) comparator ‑> 'a ‑> 'b ‑> ('a, 'b, 'cmp) t
A map with one (key, data) pair.
val of_alist : ('a, 'cmp) comparator ‑> ('a * 'b) list ‑> [ `Ok of ('a, 'b, 'cmp) t | `Duplicate_key of 'a ]
Creates a map from an association list with unique keys.
val of_alist_or_error : ('a, 'cmp) comparator ‑> ('a * 'b) list ‑> ('a, 'b, 'cmp) t Or_error.t
Creates a map from an association list with unique keys, returning an error if
duplicate 'a
keys are found.
val of_alist_exn : ('a, 'cmp) comparator ‑> ('a * 'b) list ‑> ('a, 'b, 'cmp) t
Creates a map from an association list with unique keys, raising an exception if
duplicate 'a
keys are found.
val of_alist_multi : ('a, 'cmp) comparator ‑> ('a * 'b) list ‑> ('a, 'b list, 'cmp) t
Creates a map from an association list with possibly repeated keys. The values in the map for a given key appear in the same order as they did in the association list.
val of_alist_fold : ('a, 'cmp) comparator ‑> ('a * 'b) list ‑> init:'c ‑> f:('c ‑> 'b ‑> 'c) ‑> ('a, 'c, 'cmp) t
Combines an association list into a map, folding together bound values with common keys.
val of_alist_reduce : ('a, 'cmp) comparator ‑> ('a * 'b) list ‑> f:('b ‑> 'b ‑> 'b) ‑> ('a, 'b, 'cmp) t
Combines an association list into a map, reducing together bound values with common keys.
val of_iteri : ('a, 'cmp) comparator ‑> iteri:(f:(key:'a ‑> data:'b ‑> unit) ‑> unit) ‑> [ `Ok of ('a, 'b, 'cmp) t | `Duplicate_key of 'a ]
of_iteri ~iteri
behaves like of_alist
, except that instead of taking a concrete
datastruture, it takes an iteration function. For instance, to convert a string table
into a map: of_iteri (module String) ~f:(Hashtbl.iteri table)
. It is faster than
adding the elements one by one.
val of_sorted_array : ('a, 'cmp) comparator ‑> ('a * 'b) array ‑> ('a, 'b, 'cmp) t Or_error.t
Creates a map from a sorted array of key-data pairs. The input array must be sorted (either in ascending or descending order), as given by the relevant comparator, and must not contain duplicate keys. If either of these conditions does not hold, an error is returned.
val of_sorted_array_unchecked : ('a, 'cmp) comparator ‑> ('a * 'b) array ‑> ('a, 'b, 'cmp) t
Like of_sorted_array
except that it returns a map with broken invariants when an
Error
would have been returned.
val of_increasing_iterator_unchecked : ('a, 'cmp) comparator ‑> len:int ‑> f:(int ‑> 'a * 'b) ‑> ('a, 'b, 'cmp) t
of_increasing_iterator_unchecked c ~len ~f
behaves like of_sorted_array_unchecked c
(Array.init len ~f)
, with the additional restriction that a decreasing order is not
supported. The advantage is not requiring you to allocate an intermediate array. f
will be called with 0, 1, ... len - 1
, in order.
val of_increasing_sequence : ('k, 'cmp) comparator ‑> ('k * 'v) Sequence.t ‑> ('k, 'v, 'cmp) t Or_error.t
of_increasing_sequence c seq
behaves like of_sorted_array c (Sequence.to_array
seq)
, but does not allocate the intermediate array.
The sequence will be folded over once, and the additional time complexity is O(n).
val length : (_, _, _) t ‑> int
length map
returns the number of elements in map
. O(1), but Tree.length
is
O(n).
Returns a new map with the specified new binding; if the key was already bound, its previous binding disappears.
val add : ('k, 'v, 'cmp) t ‑> key:'k ‑> data:'v ‑> ('k, 'v, 'cmp) t Or_duplicate.t
add t ~key ~data
adds a new entry to t
mapping key
to data
and returns `Ok
with the new map, or if key
is already present in t
, returns `Duplicate
.
If key
is not present then add a singleton list, otherwise, cons data onto the
head of the existing list.
val find_multi : ('k, 'v list, 'cmp) t ‑> 'k ‑> 'v list
Returns the value bound to the given key, or the empty list if there is none.
change t key ~f
returns a new map m
that is the same as t
on all keys except
for key
, and whose value for key
is defined by f
, i.e., find m key = f (find
t key)
.
val find : ('k, 'v, 'cmp) t ‑> 'k ‑> 'v option
Returns the value bound to the given key, raising Caml.Not_found
of Not_found_s
if none exists.
val find_exn : ('k, 'v, 'cmp) t ‑> 'k ‑> 'v
val iter_keys : ('k, _, _) t ‑> f:('k ‑> unit) ‑> unit
val iter : (_, 'v, _) t ‑> f:('v ‑> unit) ‑> unit
val iteri : ('k, 'v, _) t ‑> f:(key:'k ‑> data:'v ‑> unit) ‑> unit
val iter2 : ('k, 'v1, 'cmp) t ‑> ('k, 'v2, 'cmp) t ‑> f:(key:'k ‑> data:[ `Left of 'v1 | `Right of 'v2 | `Both of 'v1 * 'v2 ] ‑> unit) ‑> unit
Iterates two maps side by side. The complexity of this function is O(M + N). If two
inputs are [(0, a); (1, a)]
and [(1, b); (2, b)]
, f
will be called with [(0,
`Left a); (1, `Both (a, b)); (2, `Right b)]
.
val fold : ('k, 'v, _) t ‑> init:'a ‑> f:(key:'k ‑> data:'v ‑> 'a ‑> 'a) ‑> 'a
Folds over keys and data in the map in increasing order of key
.
val fold_right : ('k, 'v, _) t ‑> init:'a ‑> f:(key:'k ‑> data:'v ‑> 'a ‑> 'a) ‑> 'a
Folds over keys and data in the map in decreasing order of key
.
val fold2 : ('k, 'v1, 'cmp) t ‑> ('k, 'v2, 'cmp) t ‑> init:'a ‑> f:(key:'k ‑> data:[ `Left of 'v1 | `Right of 'v2 | `Both of 'v1 * 'v2 ] ‑> 'a ‑> 'a) ‑> 'a
Folds over two maps side by side, like iter2
.
filter
, filteri
, filter_keys
, filter_map
, and filter_mapi
run in O(n * lg
n) time; they simply accumulate each key & data pair retained by f
into a new map
using add
.
val partition_mapi : ('k, 'v1, 'cmp) t ‑> f:(key:'k ‑> data:'v1 ‑> [ `Fst of 'v2 | `Snd of 'v3 ]) ‑> ('k, 'v2, 'cmp) t * ('k, 'v3, 'cmp) t
partition_mapi t ~f
returns two new t
s, with each key in t
appearing in
exactly one of the resulting maps depending on its mapping in f
.
val partition_map : ('k, 'v1, 'cmp) t ‑> f:('v1 ‑> [ `Fst of 'v2 | `Snd of 'v3 ]) ‑> ('k, 'v2, 'cmp) t * ('k, 'v3, 'cmp) t
partition_map t ~f = partition_mapi t ~f:(fun ~key:_ ~data -> f data)
val partitioni_tf : ('k, 'v, 'cmp) t ‑> f:(key:'k ‑> data:'v ‑> bool) ‑> ('k, 'v, 'cmp) t * ('k, 'v, 'cmp) t
partitioni_tf t ~f
=
partition_mapi t ~f:(fun ~key ~data ->
if f ~key ~data
then `Fst data
else `Snd data)
Returns a total ordering between maps. The first argument is a total ordering used to compare data associated with equal keys in the two maps.
val hash_fold_direct : 'k Hash.folder ‑> 'v Hash.folder ‑> ('k, 'v, 'cmp) t Hash.folder
Hash function: a building block to use when hashing data structures containing maps in
them. hash_fold_direct hash_fold_key
is compatible with compare_direct
iff
hash_fold_key
is compatible with (comparator m).compare
of the map m
being
hashed.
equal cmp m1 m2
tests whether the maps m1
and m2
are equal, that is, contain
the same keys and associate each key with the same value. cmp
is the equality
predicate used to compare the values associated with the keys.
val to_alist : ?key_order:[ `Increasing | `Decreasing ] ‑> ('k, 'v, _) t ‑> ('k * 'v) list
Creates an association list from the given map.
val validate : name:('k ‑> string) ‑> 'v Validate.check ‑> ('k, 'v, _) t Validate.check
val merge : ('k, 'v1, 'cmp) t ‑> ('k, 'v2, 'cmp) t ‑> f:(key:'k ‑> [ `Left of 'v1 | `Right of 'v2 | `Both of 'v1 * 'v2 ] ‑> 'v3 option) ‑> ('k, 'v3, 'cmp) t
Merges two maps. The runtime is O(length(t1) + length(t2)). You shouldn't use this
function to merge a list of maps; consider using merge_skewed
instead.
val merge_skewed : ('k, 'v, 'cmp) t ‑> ('k, 'v, 'cmp) t ‑> combine:(key:'k ‑> 'v ‑> 'v ‑> 'v) ‑> ('k, 'v, 'cmp) t
A special case of merge
, merge_skewed t1 t2
is a map containing all the
bindings of t1
and t2
. Bindings that appear in both t1
and t2
are
combined into a single value using the combine
function. In a call
combine ~key v1 v2
, the value v1
comes from t1
and v2
from t2
.
The runtime of merge_skewed
is O(l1 * log(l2))
, where l1
is the length
of the smaller map and l2
the length of the larger map. This is likely to
be faster than merge
when one of the maps is a lot smaller, or when you
merge a list of maps.
module Symmetric_diff_element : sig ... end
val symmetric_diff : ('k, 'v, 'cmp) t ‑> ('k, 'v, 'cmp) t ‑> data_equal:('v ‑> 'v ‑> bool) ‑> ('k, 'v) Symmetric_diff_element.t Sequence.t
symmetric_diff t1 t2 ~data_equal
returns a list of changes between t1
and t2
.
It is intended to be efficient in the case where t1
and t2
share a large amount of
structure. The keys in the output sequence will be in sorted order.
val min_elt : ('k, 'v, _) t ‑> ('k * 'v) option
min_elt map
returns Some (key, data)
pair corresponding to the minimum key in
map
, or None
if empty.
val min_elt_exn : ('k, 'v, _) t ‑> 'k * 'v
val max_elt : ('k, 'v, _) t ‑> ('k * 'v) option
max_elt map
returns Some (key, data)
pair corresponding to the maximum key in
map
, or None
if map
is empty.
val max_elt_exn : ('k, 'v, _) t ‑> 'k * 'v
These functions have the same semantics as similar functions in List
.
val for_all : ('k, 'v, _) t ‑> f:('v ‑> bool) ‑> bool
val for_alli : ('k, 'v, _) t ‑> f:(key:'k ‑> data:'v ‑> bool) ‑> bool
val exists : ('k, 'v, _) t ‑> f:('v ‑> bool) ‑> bool
val existsi : ('k, 'v, _) t ‑> f:(key:'k ‑> data:'v ‑> bool) ‑> bool
val count : ('k, 'v, _) t ‑> f:('v ‑> bool) ‑> int
val counti : ('k, 'v, _) t ‑> f:(key:'k ‑> data:'v ‑> bool) ‑> int
split t key
returns a map of keys strictly less than key
, the mapping of key
if
any, and a map of keys strictly greater than key
.
Runtime is O(m + log n), where n is the size of the input map and m is the size of the smaller of the two output maps. The O(m) term is due to the need to calculate the length of the output maps.
val append : lower_part:('k, 'v, 'cmp) t ‑> upper_part:('k, 'v, 'cmp) t ‑> [ `Ok of ('k, 'v, 'cmp) t | `Overlapping_key_ranges ]
append ~lower_part ~upper_part
returns `Ok map
where map
contains all the
(key, value)
pairs from the two input maps if all the keys from lower_part
are
less than all the keys from upper_part
. Otherwise it returns
`Overlapping_key_ranges
.
Runtime is O(log n) where n is the size of the larger input map. This can be
significantly faster than Map.merge
or repeated Map.add
.
assert (match Map.append ~lower_part ~upper_part with
| `Ok whole_map ->
whole_map
= Map.(of_alist_exn (List.append (to_alist lower_part) (to_alist upper_part)))
| `Overlapping_key_ranges -> true);
val subrange : ('k, 'v, 'cmp) t ‑> lower_bound:'k Maybe_bound.t ‑> upper_bound:'k Maybe_bound.t ‑> ('k, 'v, 'cmp) t
subrange t ~lower_bound ~upper_bound
returns a map containing all the entries from
t
whose keys lie inside the interval indicated by ~lower_bound
and
~upper_bound
. If this interval is empty, an empty map is returned.
Runtime is O(m + log n), where n is the size of the input map and m is the size of the output map. The O(m) term is due to the need to calculate the length of the output map.
val fold_range_inclusive : ('k, 'v, 'cmp) t ‑> min:'k ‑> max:'k ‑> init:'a ‑> f:(key:'k ‑> data:'v ‑> 'a ‑> 'a) ‑> 'a
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).
val range_to_alist : ('k, 'v, 'cmp) t ‑> min:'k ‑> max:'k ‑> ('k * 'v) list
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
list.
val closest_key : ('k, 'v, 'cmp) t ‑> [ `Greater_or_equal_to | `Greater_than | `Less_or_equal_to | `Less_than ] ‑> 'k ‑> ('k * 'v) option
closest_key t dir k
returns the (key, value)
pair in t
with key
closest to
k
that satisfies the given inequality bound.
For example, closest_key t `Less_than k
would be the pair with the closest key to
k
where 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.
val nth : ('k, 'v, _) t ‑> int ‑> ('k * 'v) option
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.
val nth_exn : ('k, 'v, _) t ‑> int ‑> 'k * 'v
val rank : ('k, 'v, 'cmp) t ‑> 'k ‑> int option
rank t k
If k
is in t
, returns the number of keys strictly less than k
in
t
, and None
otherwise.
val to_sequence : ?order:[ `Increasing_key | `Decreasing_key ] ‑> ?keys_greater_or_equal_to:'k ‑> ?keys_less_or_equal_to:'k ‑> ('k, 'v, 'cmp) t ‑> ('k * 'v) Sequence.t
to_sequence ?order ?keys_greater_or_equal_to ?keys_less_or_equal_to t
gives a
sequence of key-value pairs between keys_less_or_equal_to
and
keys_greater_or_equal_to
inclusive, presented in order
. If
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.
module type Sexp_of_m : sig ... end
module type M_of_sexp : sig ... end
module type Compare_m : sig ... end
module type Hash_fold_m = Hasher.S
val hash_fold_m__t : (module Hash_fold_m with type t = 'k) ‑> (Hash.state ‑> 'v ‑> Hash.state) ‑> Hash.state ‑> ('k, 'v, _) t ‑> Hash.state
module Poly : Base__.Map_intf.S_poly with type ('key, +'value) t = ('key, 'value, Comparator.Poly.comparator_witness) t
A polymorphic Map.
module Using_comparator : sig ... end
Using_comparator
is a similar interface as the toplevel of Map
, except the
functions take a ~comparator:('k, 'cmp) Comparator.t
, whereas the functions at the
toplevel of Map
take a ('k, 'cmp) comparator
.
Map
For use in extensions of Base, like Core_kernel
.
module With_comparator = Base__.Map_intf.With_comparator
module With_first_class_module = Base__.Map_intf.With_first_class_module
module Without_comparator = Base__.Map_intf.Without_comparator
module type S_poly = Base__.Map_intf.S_poly
module type Accessors1 = Base__.Map_intf.Accessors1
module type Accessors2 = Base__.Map_intf.Accessors2
module type Accessors3 = Base__.Map_intf.Accessors3
module type Accessors_generic = Base__.Map_intf.Accessors_generic
module type Creators1 = Base__.Map_intf.Creators1
module type Creators2 = Base__.Map_intf.Creators2
module type Creators_generic = Base__.Map_intf.Creators_generic