module Map: Core_map
module Tree:sig
..end
type ('key, +'value, 'cmp)
t
val invariants : ('a, 'b, 'c) t -> bool
val comparator : ('a, 'b, 'cmp) t -> ('a, 'cmp) Comparator.t
val empty : comparator:('a, 'cmp) Comparator.t -> ('a, 'b, 'cmp) t
val singleton : comparator:('a, 'cmp) Comparator.t -> 'a -> 'b -> ('a, 'b, 'cmp) t
val of_alist : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> [ `Duplicate_key of 'a | `Ok of ('a, 'b, 'cmp) t ]
val of_alist_or_error : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> ('a, 'b, 'cmp) t Or_error.t
val of_alist_exn : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> ('a, 'b, 'cmp) t
val of_alist_multi : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> ('a, 'b list, 'cmp) t
val of_alist_fold : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> init:'c -> f:('c -> 'b -> 'c) -> ('a, 'c, 'cmp) t
val of_alist_reduce : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) list -> f:('b -> 'b -> 'b) -> ('a, 'b, 'cmp) t
val to_tree : ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) Tree.t
val of_tree : comparator:('k, 'cmp) Comparator.t ->
('k, 'v, 'cmp) Tree.t -> ('k, 'v, 'cmp) t
t
from a Tree.t
and a Comparator.t
. This is an O(n) operation as it
must discover the length of the Tree.t
.val of_sorted_array : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) array -> ('a, 'b, 'cmp) t Or_error.t
val of_sorted_array_unchecked : comparator:('a, 'cmp) Comparator.t ->
('a * 'b) array -> ('a, 'b, 'cmp) t
of_sorted_array
except behavior is undefined when an Error
would have been
returned.val is_empty : ('a, 'b, 'c) t -> bool
val length : ('a, 'b, 'c) t -> int
length map
map
. O(1), but Tree.length
is O(n).val add : ('k, 'v, 'cmp) t -> key:'k -> data:'v -> ('k, 'v, 'cmp) t
val add_multi : ('k, 'v list, 'cmp) t ->
key:'k -> data:'v -> ('k, 'v list, 'cmp) t
val change : ('k, 'v, 'cmp) t ->
'k -> ('v option -> 'v option) -> ('k, 'v, 'cmp) t
change map key f
updates the given map by changing the value stored under key
according to f
. Thus, for example, one might write:
change m k (function None -> Some 0 | Some x -> Some (x + 1))
to produce a new map where the integer stored under key k
is incremented by one
(treating an unknown key as zero).
val find : ('k, 'v, 'cmp) t -> 'k -> 'v option
Not_found
if none such existsval find_exn : ('k, 'v, 'cmp) t -> 'k -> 'v
val remove : ('k, 'v, 'cmp) t -> 'k -> ('k, 'v, 'cmp) t
val mem : ('k, 'a, 'cmp) t -> 'k -> bool
mem map key
tests whether map
contains a binding for key
val iter : ('k, 'v, 'a) t -> f:(key:'k -> data:'v -> unit) -> unit
val iter2 : ('k, 'v1, 'cmp) t ->
('k, 'v2, 'cmp) t ->
f:(key:'k ->
data:[ `Both of 'v1 * 'v2 | `Left of 'v1 | `Right of 'v2 ] -> unit) ->
unit
(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 map : ('k, 'v1, 'cmp) t -> f:('v1 -> 'v2) -> ('k, 'v2, 'cmp) t
val mapi : ('k, 'v1, 'cmp) t ->
f:(key:'k -> data:'v1 -> 'v2) -> ('k, 'v2, 'cmp) t
map
, but function takes both key and data as argumentsval fold : ('k, 'v, 'b) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a
val fold_right : ('k, 'v, 'b) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a
val filter : ('k, 'v, 'cmp) t ->
f:(key:'k -> data:'v -> bool) -> ('k, 'v, 'cmp) t
filter
, filter_map
, and filter_mapi
run in O(n * lg n) time; they simply
accumulate each key & data retained by f
into a new map using add
.val filter_map : ('k, 'v1, 'cmp) t ->
f:('v1 -> 'v2 option) -> ('k, 'v2, 'cmp) t
val filter_mapi : ('k, 'v1, 'cmp) t ->
f:(key:'k -> data:'v1 -> 'v2 option) -> ('k, 'v2, 'cmp) t
filter_map
, but function takes both key and data as argumentsval compare_direct : ('v -> 'v -> int) ->
('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> int
val equal : ('v -> 'v -> bool) ->
('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> bool
equal cmp m1 m2
tests whether the maps m1
and m2
are equal, that is, contain
equal keys and associate them with equal data. cmp
is the equality predicate used
to compare the data associated with the keys.val keys : ('k, 'a, 'b) t -> 'k list
val data : ('a, 'v, 'b) t -> 'v list
val to_alist : ('k, 'v, 'a) t -> ('k * 'v) list
val validate : name:('k -> string) ->
'v Validate.check -> ('k, 'v, 'a) t Validate.check
val merge : ('k, 'v1, 'cmp) t ->
('k, 'v2, 'cmp) t ->
f:(key:'k ->
[ `Both of 'v1 * 'v2 | `Left of 'v1 | `Right of 'v2 ] -> 'v3 option) ->
('k, 'v3, 'cmp) t
val symmetric_diff : ('k, 'v, 'cmp) t ->
('k, 'v, 'cmp) t ->
data_equal:('v -> 'v -> bool) ->
('k * [ `Left of 'v | `Right of 'v | `Unequal of 'v * 'v ]) 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.val min_elt : ('k, 'v, 'a) t -> ('k * 'v) option
min_elt map
(key, data)
pair corresponding to the minimum key in
map
, None if empty.val min_elt_exn : ('k, 'v, 'a) t -> 'k * 'v
val max_elt : ('k, 'v, 'a) t -> ('k * 'v) option
max_elt map
(key, data)
pair corresponding to the maximum key in
map
, and None if map
is empty.val max_elt_exn : ('k, 'v, 'a) t -> 'k * 'v
val for_all : ('k, 'v, 'a) t -> f:('v -> bool) -> bool
val exists : ('k, 'v, 'a) t -> f:('v -> bool) -> bool
val split : ('k, 'v, 'cmp) t ->
'k ->
('k, 'v, 'cmp) t * ('k * 'v) option * ('k, 'v, 'cmp) t
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
. *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
, which 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, 'a) 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 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,
otherwise Noneval to_sequence : ?order:[ `Decreasing_key | `Increasing_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 Poly:sig
..end
with type ('a, 'b, 'c) map = ('a, 'b, 'c) t
module type Key = Core_map_intf.Key
module type Key_binable = Core_map_intf.Key_binable
module type S =S
with type ('a, 'b, 'c) map := ('a, 'b, 'c) t
with type ('a, 'b, 'c) tree := ('a, 'b, 'c) Tree.t
module type S_binable =S_binable
with type ('a, 'b, 'c) map := ('a, 'b, 'c) t
with type ('a, 'b, 'c) tree := ('a, 'b, 'c) Tree.t
module Make:
module Make_using_comparator:functor (
Key
:
sig
type
t
include Comparator.S
val t_of_sexp :Sexplib.Sexp.t -> t
val sexp_of_t :t -> Sexplib.Sexp.t
end
) ->
S
with type Key.t = Key.t
with type Key.comparator_witness = Key.comparator_witness
module Make_binable:
module Make_binable_using_comparator:functor (
Key
:
sig
type
t
include Comparator.S
val t_of_sexp :Sexplib.Sexp.t -> t
val sexp_of_t :t -> Sexplib.Sexp.t
val bin_t :t Bin_prot.Type_class.t
val bin_read_t :t Bin_prot.Read.reader
val __bin_read_t__ :(int -> t) Bin_prot.Read.reader
val bin_reader_t :t Bin_prot.Type_class.reader
val bin_size_t :t Bin_prot.Size.sizer
val bin_write_t :t Bin_prot.Write.writer
val bin_writer_t :t Bin_prot.Type_class.writer
end
) ->
S_binable
with type Key.t = Key.t
with type Key.comparator_witness = Key.comparator_witness