package incr_map

All Incr_map functions take an optional instrumentation parameter that has type Instrumentation.t. A value of this type is a record containing a function which is polymorphic over a universally-quantified type 'a. This function is passed a unit -> 'a function, which must be immediately executed, and the result of which must be returned.

unordered_fold i ~init ~add ~remove constructs a more incremental version of:

let%map m = i in
Map.fold m ~init ~f:add

assuming that remove is the inverse of add, and that the operations for different keys can be performed in any order. Note that data_equal defaults to phys_equal, but a more precise equality can be provided instead.

When the data for a key updates, by default remove is called on the old data and then add is called on the new data. update provides an alternative single function to call each time a key's data updates, and can be used to improve efficiency.

For the initial computation, by default add is called on all the elements in the map. As this can be inefficient, specialized_initial can be provided to perform the computation in a more effective way.

If revert_to_init_when_empty is true, then if the input map transitions from being full to empty, then instead of calling remove on every kv-pair, it will instead just set the output to whatever you've passed as init. The default value of revert_to_init_when_empty is false, so this optimization does not apply automatically.

finalize defaults to Fn.id is called immediately before the accumulator value is stored and returned during stabilization. You can use it to e.g. process the fold operations in a different order.

unordered_fold_with_extra is similar to unordered_fold, but it also depends on another arbitrary incremental value which can be factored into the folding computation.

cutoff applies a cutoff to values in the map as they pass through the function. It has the same behavior as calling Incr_map.map' with an Incr.set_cutoff inside, but with considerably better performance and memory usage.

Given an input map and a function mapping a kv-pair to a new value, mapi_count will compute a multi-set keyed on that new value.

Any value that would otherwise have a count of "0" is instead removed from the map.

It is assumed that f is quite fast as the function will be called more often than strictly necessary, but it does this in order to avoid allocating an extra map. If f is very slow and you don't mind the extra allocations, use Incr_map.index_byi composed with Incr_map.map ~f:Map.length

The same as mapi_count but the f function only gets to see the data instead of both the key and the data.

Computes the smallest r where r is computed for each kv-pair in the input map.

Computes the largest r where r is computed for each kv-pair in the input map.

Computes the smallest r where r is computed for each kv-pair in the input map.

Computes the largest r where r is computed for each kv-pair in the input map.

Computes the smallest data value from the input map.

Computes the largest data value from the input map.

Computes min * max where the value is computed for each kv-pair in the input map

Computes min * max where the value is computed for each kv-pair in the input map

Computes the smallest and largest data value from the input map.

Like merge in Base.Map.merge. Note that f is called at most once per key in any given stabilization.

merge_both_same is like merge, but optimized for the case where you only care about the case where both maps contain a particular key.

Like merge, but operating using incremental nodes. This is a good use case for ppx_pattern_bind.

unzip_mapi is similar to List.unzip, but for incremental maps. Note that f may be called multiple times on a single element.

unzip_mapi' is like unzip_mapi, but allows you to define the mapping from the input map's elements to the output maps' elements incrementally.

The naive implementation (see below) produces worse Incremental graphs.

let temp =
  Incr_map.mapi' input ~f:(fun ~key ~data ->
    f ~key ~data |> Tuple2.uncurry Incr.both)
in
let left = Incr_map.map temp ~f:Tuple2.get1 in
let right = Incr_map.map temp ~f:Tuple2.get2 in
left, right

This is the "easy" version of join

The non-incremental semantics of this function is the identity function. Its purpose is to collapse the extra level of incrementality at the level of the data of the map.

Computes the rank of a key (given incrementally) inside of a map (also incremental). The traditional Map.rank function is O(n), and this incremental rank function has the following performance characteristics:

definitions: n : the size of the map r : the time to compute Map.symmetric_diff between the two maps k : the change in rank of the key between two stabilizations

note that r and k are _much_ smaller than n for most practical purposes

• O(log n) when the key is not in the map. This takes precedence over other every other scenario.
• O(n) on the initial stabilization
• O(n) when the key transitions from not being in the map to being in the map
• O(log n + r) when the map changes
• O(log n + k) when the key changes
• O(log n + r + k) when both key and map change

subrange map (min, max) constructs an incremental submap that includes all of the keys and data from map between min and max, and none of the keys outside the range.

subrange map None is the empty map. range being None means no elements are chosen.

Note that incremental changes have a runtime of O((k + m) log n) where k is the size of the changes to the underlying map and m is the size of the changes to the elements contained by the range. The complexity of the initial computation is the same as the incremental computation, with some simplification. k = 0 because we have not made any changes to the underlying map yet, and m equals the size of the range, because the initial range is empty.

subrange_by_rank map (s, e) constructs an incremental submap that includes (e-s+1) keys between s-th and e-th, inclusive.

If s is greater or equal to map length, the result is empty. If e is greater or equal to map length, the result contains keys from s-th to the last one.

Raises for invalid indices - s < 0 or e < s.

Runtime of the initial computation is O(min(e, n-s) + log(n)), i.e. linear, but optimized for ranges close to beginning or end.

Runtime of the incremental computation is O(log(n) + k + (m+m') * log(n)) where:

• k is the size of the diff
• m is the total impact of map changes on the range, bounded by k (e.g. if we add 1001 keys and remove 1000 below s, then m = 1)
• m' = O( |new s - old s| + |new e - old e| ).

rekey transforms a map by modifying the type of the key. The user is responsible for ensuring that f doesn't return the same output key for multiple input keys.

This function assumes f is cheap to compute and accordingly may call it multiple times.

index_byi map ~comparator ~index constructs an incremental map-of-maps where each key-data pair of the input map is present in one (or none) of the inner maps. index specifies the outer map key under which each original key-data pair is found.

All of the resulting inner maps are guaranteed to be non-empty; if the inner map would otherwise be empty, then the key for that map is instead removed from the outer map.

An all-at-once version of index_by would look like:

let index_byi map ~comparator ~index =
  Map.to_alist map
  |> List.filter_map ~f:(fun (key, data) ->
    match index ~key ~data with
    | None -> None
    | Some index -> Some (index, (key, data)))
  |> Map.of_alist_multi comparator
  |> Map.map ~f:(Map.of_alist_exn (Map.comparator_s map))
;;

index_by map ~comparator ~index is like index_byi map ~comparator ~index, but the index function does not take the inner map's key.

transpose flips the order of a doubly nested incremental map.

All inner map instances will have at least one element.

collapse_by is similar to collapse, but it allows the user to choose how to combine the two keys from the outer and inner maps. This does mean that it's the responsibility of the implementor of the merge_keys function to uphold this invariant:

> a merged-key being equal to another merged-key implies that the > outer-keys and inner-keys which were used to build the merged keys also > compare to be equal to one another

The ~comparator argument the first-class module of the output key, it usually looks like this: ~comparator:(module Combined_key) but make sure that the module implements the Comparator.S signature.

Convert a map with tuples for keys into a nested map. This operation is roughly the inverse of collapse, though if there are outer keys in the uncollapsed map that correspond to empty inner maps, the outer keys will be dropped from the expanded map.

Incrementally compute the sum of all of the values in the map.

Beware of float's negative infinities. They aren't commutative and will misbehave here.

('k, 'v) Lookup.t provides a way to lookup keys in a map which uses symmetric diffs to trigger updates of the lookups.