Previous  Up  Next

Module Std_internal.Map

module Map: Core_map
module Tree: sig .. end
type ('key, +'value, 'cmp) t 
val invariants : ('a, 'b, 'c) t -> bool
Test if invariants of internal AVL search tree hold.
val comparator : ('a, 'b, '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 -> [ `Duplicate_key of 'a | `Ok of ('a, 'b, 'cmp) t ]
creates map from association list with unique keys
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 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
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 : ('a, 'b, 'c) t -> bool
Test whether a map is empty or not.
val length : ('a, 'b, 'c) t -> int
length map
Returns number of elements in map.
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 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
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, '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
iterator for map
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
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, 'b) 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, 'b) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a
folds over keys and data in map in decreasing order of key.
val filter : ('k, 'v, 'cmp) t ->
       f:(key:'k -> data:'v -> 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 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, 'a, 'b) t -> 'k list
returns list of keys in map
val data : ('a, 'v, 'b) t -> 'v list
returns list of data in map
val to_alist : ('k, 'v, 'a) t -> ('k * 'v) list
creates association list from map. No guarantee about order.
val validate : name:('k -> string) ->
       'v Validate.check -> ('k, 'v, 'a) t Validate.check

Additional operations on maps

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
merges two maps
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 ]) list
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
Returns Some (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
Returns Some (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
same semantics as similar functions in List
val exists : ('k, 'v, 'a) t -> f:('v -> bool) -> bool
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 prev_key : ('k, 'v, 'cmp) t -> 'k -> ('k * 'v) option
prev_key t k returns the largest (key, value) pair in t with key less than k
val next_key : ('k, 'v, 'cmp) t -> 'k -> ('k * 'v) option
next_key t k returns the smallest (key, value) pair in t with key greater than k
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
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: 
functor (Key : Key) -> S  with type Key.t = Key.t
module Make_using_comparator: 
functor (Key : Comparator.S) -> S 
    with type Key.t          = Key.t 
    with type Key.comparator = Key.comparator
module Make_binable: 
functor (Key : Key_binable) -> S_binable  with type Key.t = Key.t
module Make_binable_using_comparator: 
functor (Key : Comparator.S_binable) -> S_binable 
    with type Key.t          = Key.t 
    with type Key.comparator = Key.comparator