Module Core.MapSource

Test if invariants of internal weight-balanced search tree hold.

The empty map.

Map with one (key, data) pair.

Creates map from an association list with unique keys.

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

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

of_hashtbl_exn creates a map from bindings present in a hash table. of_hashtbl_exn raises if there are distinct keys a1 and a2 in the table with comparator.compare a1 a2 = 0, which is only possible if the hash-table comparison function is different than comparator.compare. In the common case, the comparison is the same, in which case of_hashtbl_exn does not raise, regardless of the keys present in the table.

Creates map from an association list with possibly repeated keys.

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

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

of_iteri ~iteri behaves like of_alist, except that instead of taking a concrete datastructure, it takes an iteration function. For instance, to convert a string table into a map: of_iteri (module String) ~iteri:(Hashtbl.iteri table). It is faster than adding the elements one by one.

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

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.

Creates map from a 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 does not hold, an error is returned.

Like of_sorted_array except it returns a map with broken invariants when an Error would have been returned.

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.

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

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 for better performance.

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.

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.

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_multi c (Sequence.to_list seq) but does not allocate the intermediate list.

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.

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.

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

Like of_list_with_key; returns Error on duplicate key.

Like of_list_with_key; raises on duplicate key.

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

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

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

Tests whether a map is empty or not.

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

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.

add_exn t ~key ~data adds a new entry to t mapping key to data and returns the new map, or if key is already present in t, raises.

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

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

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

find_multi t key returns t's values for key if key is present in the table, and returns the empty list otherwise.

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

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

update_and_return t key ~f is like update t key ~f, but also returns the new value.

Returns the value bound to the given key if it exists, and None otherwise.

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

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

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

iter_keys t ~f calls f on every key in the map, going in order from the smallest to the largest keys.

iter t ~f calls f on every element in the map, going in order from the smallest to the largest keys.

iteri t ~f calls f on every key and element in the map, going in order from the smallest to the largest keys.

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

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

Returns new map with bound values replaced by the result of f applied to them.

Like map, but f takes both key and data as arguments.

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

Like map_keys, but raises on duplicate key.

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

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.

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

Folds over two maps side by side, like iter2.

Returns new map with bound values filtered by the result of f applied to them.

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

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.

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

partition_result t = partition_map t ~f:Result.to_either

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

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

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

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

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 equal keys and associate them with equal data. cmp is the equality predicate used to compare the data associated with the keys.

Returns list of keys in map in increasing order.

Returns list of data in map in increasing order of key.

Creates association list from map.

• parameter key_order

  default is `Increasing

Merges two maps. The runtime is O(length(t1) + length(t2)).

The merge_* functions immediately below perform better in cases where they are applicable. For merging a list of maps especially, use merge_disjoin_exn or merge_skewed instead. If you don't require the full generality of ~f's behavior, use merge_by_case.

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

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

An alternative to merge that is more efficient when unmatched keys are unconditionally dropped or kept unchanged in the result.

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. In the case where t2 (resp. t1) is obtained by applying k additions and/or removals to t1 (resp. t2), this runs in min(O(k log n), O(n)), where n is length t1 + length t2. The keys in the output sequence will be in sorted order.

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.

min_elt map returns Some (key, data) pair corresponding to the minimum key in map, None if map is empty.

max_elt map returns Some (key, data) pair corresponding to the maximum key in map, and None if map is empty.

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.

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.

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.

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.

count_lt t key returns the number of keys in t that are strictly less than key.

Runtime is O(log n) where n is the size of the input map.

count_le t key returns the number of keys in t that are less than or equal to key.

Runtime is O(log n) where n is the size of the input map.

count_gt t key returns the number of keys in t that are strictly greater than key.

Runtime is O(log n) where n is the size of the input map.

count_ge t key returns the number of keys in t that are greater than or equal to key.

Runtime is O(log n) where n is the size of the input map.

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)

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(log n) where n is the size of the input map.

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

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.

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.

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.

rank t k if k is in t, returns the number of keys strictly less than k in t, otherwise None.

split_n t n = l, r such that append ~lower_part:l ~upper_part:r = `Ok t and length l = n, or as close as possible if n < 0 or n > length 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.

• parameter order

  `Increasing_key is the default

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.

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.

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 key-value pairs in range.

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

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

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.

Convert a set to a map. Runs in O(length t) time plus a call to f for each key to compute the associated data.

Converts a map to a set of its keys. Runs in O(length t) time.

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.

The following functors may be used to define stable modules