incr_map v0.13.0 · OCaml Package

Parameters

module Incr : Incremental.S

Signature

val of_set : 
  ('k, 'cmp) Core_kernel.Set.t Incr.t ->
  ('k, unit, 'cmp) Core_kernel.Map.t Incr.t

val filter_mapi : 
  ?data_equal:('v1 -> 'v1 -> bool) ->
  ('k, 'v1, 'cmp) Core_kernel.Map.t Incr.t ->
  f:(key:'k -> data:'v1 -> 'v2 option) ->
  ('k, 'v2, 'cmp) Core_kernel.Map.t Incr.t

val mapi : 
  ?data_equal:('v1 -> 'v1 -> bool) ->
  ('k, 'v1, 'cmp) Core_kernel.Map.t Incr.t ->
  f:(key:'k -> data:'v1 -> 'v2) ->
  ('k, 'v2, 'cmp) Core_kernel.Map.t Incr.t

val filter_mapi' : 
  ?cutoff:'v1 Incr.Cutoff.t ->
  ?data_equal:('v1 -> 'v1 -> bool) ->
  ('k, 'v1, 'cmp) Core_kernel.Map.t Incr.t ->
  f:(key:'k -> data:'v1 Incr.t -> 'v2 option Incr.t) ->
  ('k, 'v2, 'cmp) Core_kernel.Map.t Incr.t

val mapi' : 
  ?cutoff:'v1 Incr.Cutoff.t ->
  ?data_equal:('v1 -> 'v1 -> bool) ->
  ('k, 'v1, 'cmp) Core_kernel.Map.t Incr.t ->
  f:(key:'k -> data:'v1 Incr.t -> 'v2 Incr.t) ->
  ('k, 'v2, 'cmp) Core_kernel.Map.t Incr.t

val unordered_fold : 
  ?data_equal:('v -> 'v -> bool) ->
  ?update:(key:'k -> old_data:'v -> new_data:'v -> 'acc -> 'acc) ->
  ('k, 'v, 'cmp) Core_kernel.Map.t Incr.t ->
  init:'acc ->
  add:(key:'k -> data:'v -> 'acc -> 'acc) ->
  remove:(key:'k -> data:'v -> 'acc -> 'acc) ->
  'acc Incr.t

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.

val merge : 
  ?data_equal_left:('v1 -> 'v1 -> bool) ->
  ?data_equal_right:('v2 -> 'v2 -> bool) ->
  ('k, 'v1, 'cmp) Core_kernel.Map.t Incr.t ->
  ('k, 'v2, 'cmp) Core_kernel.Map.t Incr.t ->
  f:
    (key:'k ->
      [ `Left of 'v1 | `Right of 'v2 | `Both of 'v1 * 'v2 ] ->
      'v3 option) ->
  ('k, 'v3, 'cmp) Core_kernel.Map.t Incr.t

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

val flatten : 
  ('k, 'v Incr.t, 'cmp) Core_kernel.Map.t ->
  ('k, 'v, 'cmp) Core_kernel.Map.t Incr.t

This is the "easy" version of join

val join : 
  ('k, 'v Incr.t, 'cmp) Core_kernel.Map.t Incr.t ->
  ('k, 'v, 'cmp) Core_kernel.Map.t Incr.t

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.

val separate : 
  ('k, 'v, 'cmp) Core_kernel.Map.t Incr.t ->
  data_equal:('v -> 'v -> bool) ->
  ('k, 'v Incr.t, 'cmp) Core_kernel.Map.t Incr.t

val keys : 
  ('k, 'v, 'c) Core_kernel.Map.t Incr.t ->
  ('k, 'c) Core_kernel.Set.t Incr.t

val subrange : 
  ?data_equal:('v -> 'v -> bool) ->
  ('k, 'v, 'cmp) Core_kernel.Map.t Incr.t ->
  ('k Core_kernel.Maybe_bound.As_lower_bound.t
   * 'k Core_kernel.Maybe_bound.As_upper_bound.t)
    option
    Incr.t ->
  ('k, 'v, 'cmp) Core_kernel.Map.t Incr.t

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.

val subrange_by_rank : 
  ?data_equal:('v -> 'v -> bool) ->
  ('k, 'v, 'cmp) Core_kernel.Map.t Incr.t ->
  (int * int) Incr.t ->
  ('k, 'v, 'cmp) Core_kernel.Map.t Incr.t

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

module Lookup : sig ... end

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

module For_testing : sig ... end

package incr_map

Parameters

Signature