Map (reference.base.base.Base.Map)

Sourcetype (!'key, !+'value, !'cmp) t

Sourcemodule Or_duplicate : sig ... end

Sourcemodule Continue_or_stop : sig ... end

Sourcemodule Finished_or_unfinished : sig ... end

Sourcemodule Merge_element : sig ... end

Sourceval invariants : (_, _, _) t -> bool

Test if the invariants of the internal AVL search tree hold.

Sourceval comparator_s : ('a, _, 'cmp) t -> ('a, 'cmp) Comparator.Module.t

Returns a first-class module that can be used to build other map/set/etc. with the same notion of comparison.

Sourceval comparator : ('a, _, 'cmp) t -> ('a, 'cmp) Comparator.t

Sourceval empty : ('a, 'cmp) Comparator.Module.t -> ('a, 'b, 'cmp) t

The empty map.

Sourceval singleton : ('a, 'cmp) Comparator.Module.t -> 'a -> 'b -> ('a, 'b, 'cmp) t

A map with one (key, data) pair.

Source

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

Creates a map from an association list with unique keys.

Source

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

Source

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

Source

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

Source

val of_alist_fold : 
  ('a, 'cmp) Comparator.Module.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. The accumulator is per-key.

Example:

  # (let map =
       String.Map.of_alist_fold
         [ "a", 1; "a", 10; "b", 2; "b", 20; "b", 200 ]
         ~init:Int.Set.empty
         ~f:Set.add
     in
     print_s [%sexp (map : Int.Set.t String.Map.t)]);;
  ((a (1 10)) (b (2 20 200)))
  - : unit = ()

Source

val of_alist_reduce : 
  ('a, 'cmp) Comparator.Module.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.

Source

val of_iteri : 
  ('a, 'cmp) Comparator.Module.t ->
  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 data structure, 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.

Source

val of_iteri_exn : 
  ('a, 'cmp) Comparator.Module.t ->
  iteri:(f:(key:'a -> data:'b -> unit) -> unit) ->
  ('a, 'b, 'cmp) t

Like of_iteri except that it raises an exception if duplicate 'a keys are found.

Source

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

Source

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

Source

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

Source

val of_increasing_sequence : 
  ('k, 'cmp) Comparator.Module.t ->
  ('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).

Source

val of_sequence : 
  ('k, 'cmp) Comparator.Module.t ->
  ('k * 'v) Sequence.t ->
  [ `Ok of ('k, 'v, 'cmp) t | `Duplicate_key of 'k ]

Creates a map from an association sequence with unique keys.

of_sequence c seq behaves like of_alist c (Sequence.to_list seq) but does not allocate the intermediate list.

If your sequence is increasing, use of_increasing_sequence.

Source

val of_sequence_or_error : 
  ('a, 'cmp) Comparator.Module.t ->
  ('a * 'b) Sequence.t ->
  ('a, 'b, 'cmp) t Or_error.t

Creates a map from an association sequence with unique keys, returning an error if duplicate 'a keys are found.

of_sequence_or_error c seq behaves like of_alist_or_error c (Sequence.to_list seq) but does not allocate the intermediate list.

Source

val of_sequence_exn : 
  ('a, 'cmp) Comparator.Module.t ->
  ('a * 'b) Sequence.t ->
  ('a, 'b, 'cmp) t

Creates a map from an association sequence with unique keys, raising an exception if duplicate 'a keys are found.

of_sequence_exn c seq behaves like of_alist_exn c (Sequence.to_list seq) but does not allocate the intermediate list.

Source

val of_sequence_multi : 
  ('a, 'cmp) Comparator.Module.t ->
  ('a * 'b) Sequence.t ->
  ('a, 'b list, 'cmp) t

Creates a map from an association sequence 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.

of_sequence_multi c seq behaves like of_alist_exn c (Sequence.to_list seq) but does not allocate the intermediate list.

Source

val of_sequence_fold : 
  ('a, 'cmp) Comparator.Module.t ->
  ('a * 'b) Sequence.t ->
  init:'c ->
  f:('c -> 'b -> 'c) ->
  ('a, 'c, 'cmp) t

Combines an association sequence into a map, folding together bound values with common keys.

of_sequence_fold c seq ~init ~f behaves like of_alist_fold c (Sequence.to_list seq) ~init ~f but does not allocate the intermediate list.

Source

val of_sequence_reduce : 
  ('a, 'cmp) Comparator.Module.t ->
  ('a * 'b) Sequence.t ->
  f:('b -> 'b -> 'b) ->
  ('a, 'b, 'cmp) t

Combines an association sequence into a map, reducing together bound values with common keys.

of_sequence_reduce c seq ~f behaves like of_alist_reduce c (Sequence.to_list seq) ~f but does not allocate the intermediate list.

Source

val of_list_with_key : 
  ('k, 'cmp) Comparator.Module.t ->
  'v list ->
  get_key:('v -> 'k) ->
  [ `Ok of ('k, 'v, 'cmp) t | `Duplicate_key of 'k ]

Constructs a map from a list of values, where get_key extracts a key from a value.

Source

val of_list_with_key_or_error : 
  ('k, 'cmp) Comparator.Module.t ->
  'v list ->
  get_key:('v -> 'k) ->
  ('k, 'v, 'cmp) t Or_error.t

Like of_list_with_key; returns Error on duplicate key.

Source

val of_list_with_key_exn : 
  ('k, 'cmp) Comparator.Module.t ->
  'v list ->
  get_key:('v -> 'k) ->
  ('k, 'v, 'cmp) t

Like of_list_with_key; raises on duplicate key.

Source

val of_list_with_key_multi : 
  ('k, 'cmp) Comparator.Module.t ->
  'v list ->
  get_key:('v -> 'k) ->
  ('k, 'v list, 'cmp) t

Like of_list_with_key; produces lists of all values associated with each key.

Source

val of_list_with_key_fold : 
  ('k, 'cmp) Comparator.Module.t ->
  'v list ->
  get_key:('v -> 'k) ->
  init:'acc ->
  f:('acc -> 'v -> 'acc) ->
  ('k, 'acc, 'cmp) t

Like of_list_with_key; resolves duplicate keys the same way of_alist_fold does.

Source

val of_list_with_key_reduce : 
  ('k, 'cmp) Comparator.Module.t ->
  'v list ->
  get_key:('v -> 'k) ->
  f:('v -> 'v -> 'v) ->
  ('k, 'v, 'cmp) t

Like of_list_with_key; resolves duplicate keys the same way of_alist_reduce does.

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

Tests whether a map is empty.

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

length map returns the number of elements in map. O(1), but Tree.length is O(n).

Sourceval set : ('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.

Source

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.

Sourceval add_exn : ('k, 'v, 'cmp) t -> key:'k -> data:'v -> ('k, 'v, 'cmp) t

Source

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 onto the head of the existing list.

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

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

Sourceval 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.

Source

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).

Sourceval 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)).

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

Returns Some value bound to the given key, or None if none exists.

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

Returns the value bound to the given key, raising Stdlib.Not_found or Not_found_s if none exists.

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

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

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

mem map key tests whether map contains a binding for key.

Sourceval iter_keys : ('k, _, _) t -> f:('k -> unit) -> unit

Sourceval iter : (_, 'v, _) t -> f:('v -> unit) -> unit

Sourceval iteri : ('k, 'v, _) t -> f:(key:'k -> data:'v -> unit) -> unit

Source

val iteri_until : 
  ('k, 'v, _) t ->
  f:(key:'k -> data:'v -> Continue_or_stop.t) ->
  Finished_or_unfinished.t

Iterates until the first time f returns Stop. If f returns Stop, the final result is Unfinished. Otherwise, the final result is Finished.

Source

val iter2 : 
  ('k, 'v1, 'cmp) t ->
  ('k, 'v2, 'cmp) t ->
  f:(key:'k -> data:('v1, 'v2) Merge_element.t -> 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)].

Sourceval map : ('k, 'v1, 'cmp) t -> f:('v1 -> 'v2) -> ('k, 'v2, 'cmp) t

Returns a new map with bound values replaced by f applied to the bound values.

Source

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

Like map, but the passed function takes both key and data as arguments.

Source

val map_keys : 
  ('k2, 'cmp2) Comparator.Module.t ->
  ('k1, 'v, 'cmp1) t ->
  f:('k1 -> 'k2) ->
  [ `Ok of ('k2, 'v, 'cmp2) t | `Duplicate_key of 'k2 ]

Convert map with keys of type 'k2 to a map with keys of type 'k2 using f.

Source

val map_keys_exn : 
  ('k2, 'cmp2) Comparator.Module.t ->
  ('k1, 'v, 'cmp1) t ->
  f:('k1 -> 'k2) ->
  ('k2, 'v, 'cmp2) t

Like map_keys, but raises on duplicate key.

Source

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

Folds over keys and data in the map in increasing order of key.

Source

val fold_until : 
  ('k, 'v, _) t ->
  init:'acc ->
  f:(key:'k -> data:'v -> 'acc -> ('acc, 'final) Container.Continue_or_stop.t) ->
  finish:('acc -> 'final) ->
  'final

Folds over keys and data in the map in increasing order of key, until the first time that f returns Stop _. If f returns Stop final, this function returns immediately with the value final. If f never returns Stop _, and the final call to f returns Continue last, this function returns finish last.

Source

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

Folds over keys and data in the map in decreasing order of key.

Source

val fold2 : 
  ('k, 'v1, 'cmp) t ->
  ('k, 'v2, 'cmp) t ->
  init:'acc ->
  f:(key:'k -> data:('v1, 'v2) Merge_element.t -> 'acc -> 'acc) ->
  'acc

Folds over two maps side by side, like iter2.

Sourceval filter_keys : ('k, 'v, 'cmp) t -> f:('k -> bool) -> ('k, 'v, 'cmp) t

filter, filteri, filter_keys, filter_map, and filter_mapi run in O(n) time.

filter, filteri, filter_keys, partition_tf and partitioni_tf keep a lot of sharing between their result and the original map. Dropping or keeping a run of k consecutive elements costs O(log(k)) extra memory. Keeping the entire map costs no extra memory at all: filter ~f:(fun _ -> true) returns the original map.

Sourceval filter : ('k, 'v, 'cmp) t -> f:('v -> bool) -> ('k, 'v, 'cmp) t

Source

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

Source

val filter_map : 
  ('k, 'v1, 'cmp) t ->
  f:('v1 -> 'v2 option) ->
  ('k, 'v2, 'cmp) t

Returns a new map with bound values filtered by f applied to the bound values.

Source

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

Like filter_map, but the passed function takes both key and data as arguments.

Source

val partition_mapi : 
  ('k, 'v1, 'cmp) t ->
  f:(key:'k -> data:'v1 -> ('v2, 'v3) Either.t) ->
  ('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 resulting maps depending on its mapping in f.

Source

val partition_map : 
  ('k, 'v1, 'cmp) t ->
  f:('v1 -> ('v2, 'v3) Either.t) ->
  ('k, 'v2, 'cmp) t * ('k, 'v3, 'cmp) t

partition_map t ~f = partition_mapi t ~f:(fun ~key:_ ~data -> f data)

Source

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 First data
    else Second data)

Source

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)

Sourceval combine_errors : ('k, 'v Or_error.t, 'cmp) t -> ('k, 'v, 'cmp) t Or_error.t

Produces Ok of a map including all keys if all data is Ok, or an Error including all errors otherwise.

Sourceval unzip : ('k, 'v1 * 'v2, 'cmp) t -> ('k, 'v1, 'cmp) t * ('k, 'v2, 'cmp) t

Given a map of tuples, produces a tuple of maps. Equivalent to: map t ~f:fst, map t ~f:snd

Source

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

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.

Source

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.

Sourceval 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 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.

Sourceval keys : ('k, _, _) t -> 'k list

Returns a list of the keys in the given map.

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

Returns a list of the data in the given map.

Source

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

Creates an association list from the given map.

Additional operations on maps

Source

val merge : 
  ('k, 'v1, 'cmp) t ->
  ('k, 'v2, 'cmp) t ->
  f:(key:'k -> ('v1, 'v2) Merge_element.t -> '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_disjoin_exn or merge_skewed instead.

Source

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

Merges two dictionaries with the same type of data and disjoint sets of keys. Raises if any keys overlap.

Source

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(min(l1, l2) * log(max(l1, l2))), where l1 is the length of t1 and l2 the length of t2. 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.

Sourcemodule Symmetric_diff_element : sig ... end

Source

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.

It is assumed that data_equal is at least as equating as physical equality: that phys_equal x y implies data_equal x y. Otherwise, symmetric_diff may behave in unexpected ways. For example, with ~data_equal:(fun _ _ -> false) it is NOT necessarily the case the resulting change sequence will contain an element (k, `Unequal _) for every key k shared by both maps.

Warning: Float equality violates this property! phys_equal Float.nan Float.nan is true, but Float.(=) Float.nan Float.nan is false.

Source

val fold_symmetric_diff : 
  ('k, 'v, 'cmp) t ->
  ('k, 'v, 'cmp) t ->
  data_equal:('v -> 'v -> bool) ->
  init:'acc ->
  f:('acc -> ('k, 'v) Symmetric_diff_element.t -> 'acc) ->
  'acc

fold_symmetric_diff t1 t2 ~data_equal folds across an implicit sequence of changes between t1 and t2, in sorted order by keys. Equivalent to Sequence.fold (symmetric_diff t1 t2 ~data_equal), and more efficient.

Sourceval 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.

Sourceval min_elt_exn : ('k, 'v, _) t -> 'k * 'v

Sourceval 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.

Sourceval max_elt_exn : ('k, 'v, _) t -> 'k * 'v

Source

val transpose_keys : 
  ('k2, 'cmp2) Comparator.Module.t ->
  ('k1, ('k2, 'v, 'cmp2) t, 'cmp1) t ->
  ('k2, ('k1, 'v, 'cmp1) t, 'cmp2) t

Swap the inner and outer keys of nested maps. If transpose_keys m a = b, then find_exn (find_exn a i) j = find_exn (find_exn b j) i.

These functions have the same semantics as similar functions in List.

Sourceval for_all : ('k, 'v, _) t -> f:('v -> bool) -> bool

Sourceval for_alli : ('k, 'v, _) t -> f:(key:'k -> data:'v -> bool) -> bool

Sourceval exists : ('k, 'v, _) t -> f:('v -> bool) -> bool

Sourceval existsi : ('k, 'v, _) t -> f:(key:'k -> data:'v -> bool) -> bool

Sourceval count : ('k, 'v, _) t -> f:('v -> bool) -> int

Sourceval counti : ('k, 'v, _) t -> f:(key:'k -> data:'v -> bool) -> int

Source

val sum : 
  (module Container.Summable with type t = 'a) ->
  ('k, 'v, _) t ->
  f:('v -> 'a) ->
  'a

Source

val sumi : 
  (module Container.Summable with type t = 'a) ->
  ('k, 'v, _) t ->
  f:(key:'k -> data:'v -> 'a) ->
  'a

Source

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.

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.

Sourceval split_le_gt : ('k, 'v, 'cmp) t -> 'k -> ('k, 'v, 'cmp) t * ('k, 'v, 'cmp) t

split_le_gt t key returns a map of keys that are less or equal to key 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.

Sourceval split_lt_ge : ('k, 'v, 'cmp) t -> 'k -> ('k, 'v, 'cmp) t * ('k, 'v, 'cmp) t

split_lt_ge t key returns a map of keys strictly less than key and a map of keys that are greater or equal to 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.

Source

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 ->
      Map.to_alist whole_map
      = List.append (to_alist lower_part) (to_alist upper_part)
    | `Overlapping_key_ranges -> true);

Source

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.

Source

val fold_range_inclusive : 
  ('k, 'v, 'cmp) t ->
  min:'k ->
  max:'k ->
  init:'acc ->
  f:(key:'k -> data:'v -> 'acc -> 'acc) ->
  'acc

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).

Sourceval 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.

Source

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.

Sourceval 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.

Sourceval nth_exn : ('k, 'v, _) t -> int -> 'k * 'v

Sourceval 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.

Source

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.

When neither keys_greater_or_equal_to nor keys_less_or_equal_to are provided, the cost is O(log n) up front and amortized O(1) to produce each element. If either is provided (and is used by the order parameter provided), then the the cost is O(n) up front, and amortized O(1) to produce each element.

Source

val binary_search : 
  ('k, 'v, 'cmp) t ->
  compare:(key:'k -> data:'v -> 'key -> int) ->
  [ `Last_strictly_less_than
  | `Last_less_than_or_equal_to
  | `Last_equal_to
  | `First_equal_to
  | `First_greater_than_or_equal_to
  | `First_strictly_greater_than ] ->
  'key ->
  ('k * 'v) option

binary_search t ~compare which elt returns the (key, value) pair in t specified by compare and which, if one exists.

t must be sorted in increasing order according to compare, where compare and elt divide t into three (possibly empty) segments:

  |  < elt  |  = elt  |  > elt  |

binary_search returns an element on the boundary of segments as specified by which. See the diagram below next to the which variants.

binary_search does not check that compare orders t, and behavior is unspecified if compare doesn't order t. Behavior is also unspecified if compare mutates t.

Source

val binary_search_segmented : 
  ('k, 'v, 'cmp) t ->
  segment_of:(key:'k -> data:'v -> [ `Left | `Right ]) ->
  [ `Last_on_left | `First_on_right ] ->
  ('k * 'v) option

binary_search_segmented t ~segment_of which takes a segment_of function that divides t into two (possibly empty) segments:

  | segment_of elt = `Left | segment_of elt = `Right |

binary_search_segmented returns the (key, value) pair on the boundary of the segments as specified by which: `Last_on_left yields the last element of the left segment, while `First_on_right yields the first element of the right segment. It returns None if the segment is empty.

binary_search_segmented does not check that segment_of segments t as in the diagram, and behavior is unspecified if segment_of doesn't segment t. Behavior is also unspecified if segment_of mutates t.

Source

val binary_search_subrange : 
  ('k, 'v, 'cmp) t ->
  compare:(key:'k -> data:'v -> 'bound -> int) ->
  lower_bound:'bound Maybe_bound.t ->
  upper_bound:'bound Maybe_bound.t ->
  ('k, 'v, 'cmp) t

binary_search_subrange takes a compare function that divides t into three (possibly empty) segments with respect to lower_bound and upper_bound:

  | Below_lower_bound | In_range | Above_upper_bound |

and returns a map of the In_range segment.

Runtime is O(log m + n) where m is the length of the input map and n is the length of the output. The linear term in n is to compute the length of the output.

Behavior is undefined if compare does not segment t as shown above, or if compare mutates its inputs.

Source

module Make_applicative_traversals
  (A : Applicative.Lazy_applicative) : 
  sig ... end

Creates traversals to reconstruct a map within an applicative. Uses Lazy_applicative so that the map can be traversed within the applicative, rather than needing to be traversed all at once, outside the applicative.

Sourcemodule M (K : sig ... end) : sig ... end

M is meant to be used in combination with OCaml applicative functor types:

Sourcemodule type Sexp_of_m = sig ... end

Sourcemodule type M_of_sexp = sig ... end

Sourcemodule type M_sexp_grammar = sig ... end

Sourcemodule type Compare_m = sig ... end

Sourcemodule type Equal_m = sig ... end

Sourcemodule type Hash_fold_m = Hasher.S

Source

val sexp_of_m__t : 
  (module Sexp_of_m with type t = 'k) ->
  ('v -> Sexp.t) ->
  ('k, 'v, 'cmp) t ->
  Sexp.t

Source

val m__t_of_sexp : 
  (module M_of_sexp with type comparator_witness = 'cmp and type t = 'k) ->
  (Sexp.t -> 'v) ->
  Sexp.t ->
  ('k, 'v, 'cmp) t

Source

val m__t_sexp_grammar : 
  (module M_sexp_grammar with type t = 'k) ->
  'v Sexplib0.Sexp_grammar.t ->
  ('k, 'v, 'cmp) t Sexplib0.Sexp_grammar.t

Source

val compare_m__t : 
  (module Compare_m) ->
  ('v -> 'v -> int) ->
  ('k, 'v, 'cmp) t ->
  ('k, 'v, 'cmp) t ->
  int

Source

val equal_m__t : 
  (module Equal_m) ->
  ('v -> 'v -> bool) ->
  ('k, 'v, 'cmp) t ->
  ('k, 'v, 'cmp) t ->
  bool

Source

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

Sourcemodule 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.

Sourcemodule Poly : sig ... end

A polymorphic Map.

Source

val of_tree : 
  ('k, 'cmp) Comparator.Module.t ->
  ('k, 'v, 'cmp) Using_comparator.Tree.t ->
  ('k, 'v, 'cmp) t

Create a map from a tree using the given comparator.

Sourceval to_tree : ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) Using_comparator.Tree.t

Extract a tree from a map.

Modules and module types for extending `Map`

For use in extensions of Base, like Core.

Sourcemodule With_comparator : sig ... end

Sourcemodule With_first_class_module : sig ... end

Sourcemodule Without_comparator : sig ... end

Sourcemodule type For_deriving = sig ... end

Sourcemodule type S_poly = sig ... end

Sourcemodule type Accessors_generic = sig ... end

Sourcemodule type Creators_and_accessors_generic = sig ... end

Sourcemodule type Creators_generic = sig ... end

Additional operations on maps

Modules and module types for extending Map

Modules and module types for extending `Map`