Up

Module Map = Core_map

Signature

module Tree : sig .. end
type ('key, +'value, 'cmp) t
val invariants : (_, _, _) t -> bool

Test if invariants of internal AVL search tree hold.

val comparator : ('a, _, 'cmp) t -> ('a, 'cmp) Comparator.t
val empty : comparator:('a, 'cmp) Comparator.t -> ('a, 'b, 'cmp) t

the empty map

val singleton : comparator:('a, 'cmp) Comparator.t -> 'a -> 'b -> ('a, 'b, 'cmp) t

map with one key, data pair

val of_alist : comparator:('a, 'cmp) Comparator.t -> ('a * 'b) list -> [
| `Ok of ('a, 'b, 'cmp) t
| `Duplicate_key of 'a
]

creates map from association list with unique keys

val of_alist_or_error : comparator:('a, 'cmp) Comparator.t -> ('a * 'b) list -> ('a, 'b, 'cmp) t Or_error.t

creates map from association list with unique keys. Returns an error if duplicate 'a keys are found.

val of_alist_exn : comparator:('a, 'cmp) Comparator.t -> ('a * 'b) list -> ('a, 'b, 'cmp) t

creates map from association list with unique keys. Raises an exception if duplicate 'a keys are found.

val of_alist_multi : comparator:('a, 'cmp) Comparator.t -> ('a * 'b) list -> ('a, 'b list, 'cmp) t

creates map from association list with possibly repeated keys.

val of_alist_fold : comparator:('a, 'cmp) Comparator.t -> ('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 : comparator:('a, 'cmp) Comparator.t -> ('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 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

Creates a 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

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.

val of_sorted_array_unchecked : comparator:('a, 'cmp) Comparator.t -> ('a * 'b) array -> ('a, 'b, 'cmp) t

Like of_sorted_array except behavior is undefined when an Error would have been returned.

val is_empty : (_, _, _) t -> bool

Test whether a map is empty or not.

val length : (_, _, _) t -> int

length map

Returns number of elements in map. O(1), but Tree.length is O(n).
val add : ('k, 'v, 'cmp) t -> key:'k -> data:'v -> ('k, 'v, 'cmp) t

returns a new map with the specified new binding; if the key was already bound, its previous binding disappears.

val add_multi : ('k, 'v list, 'cmp) t -> key:'k -> data:'v -> ('k, 'v list, 'cmp) t

if key is not present then add a singleton list, otherwise, cons data on the head of the existing list.

val remove_multi : ('k, 'v list, 'cmp) t -> 'k -> ('k, 'v list, 'cmp) t

if key is present then remove its head element; if result is empty, remove the key.

val change : ('k, 'v, 'cmp) t -> 'k -> f:('v option -> 'v option) -> ('k, 'v, 'cmp) t

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 update : ('k, 'v, 'cmp) t -> 'k -> f:('v option -> 'v) -> ('k, 'v, 'cmp) t

update t key ~f is change t key ~f:(fun o -> Some (f o)).

val find : ('k, 'v, 'cmp) t -> 'k -> 'v option

returns the value bound to the given key, raising Not_found if none such exists

val find_exn : ('k, 'v, 'cmp) t -> 'k -> 'v
val remove : ('k, 'v, 'cmp) t -> 'k -> ('k, 'v, 'cmp) t

returns a new map with any binding for the key in question removed

val mem : ('k, _, 'cmp) t -> 'k -> bool

mem map key tests whether map contains a binding for key

val iter : ('k, 'v, _) t -> f:(key:'k -> data:'v -> unit) -> unit
val iteri : ('k, 'v, _) t -> f:(key:'k -> data:'v -> unit) -> unit
val iter_keys : ('k, _, _) t -> f:('k -> 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

Iterate two maps side by side. 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 map : ('k, 'v1, 'cmp) t -> f:('v1 -> 'v2) -> ('k, 'v2, 'cmp) t

returns new map with bound values replaced by f applied to the bound values

val mapi : ('k, 'v1, 'cmp) t -> f:(key:'k -> data:'v1 -> 'v2) -> ('k, 'v2, 'cmp) t

like map, but function takes both key and data as arguments

val fold : ('k, 'v, _) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a

folds over keys and data in 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 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.

val filter : ('k, 'v, 'cmp) t -> f:(key:'k -> data:'v -> bool) -> ('k, 'v, 'cmp) t
val filteri : ('k, 'v, 'cmp) t -> f:(key:'k -> data:'v -> bool) -> ('k, 'v, 'cmp) t

filteri, 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_keys : ('k, 'v, 'cmp) t -> f:('k -> bool) -> ('k, 'v, 'cmp) t
val filter_map : ('k, 'v1, 'cmp) t -> f:('v1 -> 'v2 option) -> ('k, 'v2, 'cmp) t

returns new map with bound values filtered by f applied to the bound values

val filter_mapi : ('k, 'v1, 'cmp) t -> f:(key:'k -> data:'v1 -> 'v2 option) -> ('k, 'v2, 'cmp) t

like filter_map, but function takes both key and data as arguments

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 ts, with each key in t appearing in exactly one of the result 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)
val partition_tf : ('k, 'v, 'cmp) t -> f:('v -> bool) -> ('k, 'v, 'cmp) t * ('k, 'v, 'cmp) t

partition_tf t ~f = partitioni_tf t ~f:(fun ~key:_ ~data -> f data)

val compare_direct : ('v -> 'v -> int) -> ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> int

Total ordering between maps. The first argument is a total ordering used to compare data associated with equal keys in the two maps.

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, _, _) t -> 'k list

returns list of keys in map

val data : (_, 'v, _) t -> 'v list

returns list of data in map

val to_alist : ?key_order:[
| `Increasing
| `Decreasing
] -> ('k, 'v, _) t -> ('k * 'v) list

creates association list from map.

val validate : name:('k -> string) -> 'v Validate.check -> ('k, 'v, _) t Validate.check
Additional operations on maps
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

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.

val min_elt : ('k, 'v, _) t -> ('k * 'v) option

min_elt map

Returns Some (key, data) pair corresponding to the minimum key in map, 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, and None if map is empty.
val max_elt_exn : ('k, 'v, _) t -> 'k * 'v
val for_all : ('k, 'v, _) t -> f:('v -> bool) -> bool

same semantics as similar functions in List

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
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, _) 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, otherwise None

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.

val gen : comparator:('k, 'cmp) Comparator.t -> 'k Quickcheck.Generator.t -> 'v Quickcheck.Generator.t -> ('k, 'v, 'cmp) t Quickcheck.Generator.t
val shrinker : 'k Quickcheck.Shrinker.t -> 'v Quickcheck.Shrinker.t -> ('k, 'v, 'cmp) t Quickcheck.Shrinker.t

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.

module Poly : sig .. end
module type Key = Core_map_intf.Key
module type S = Core_map_intf.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 = Core_map_intf.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 (Key : Key) : S with type Key.t = Key.t
module Make_using_comparator (Key : sig .. end) : S with type Key.t = Key.t with type Key.comparator_witness = Key.comparator_witness
module Make_binable (Key : Key_binable) : S_binable with type Key.t = Key.t