Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
module Incr : sig ... end
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:
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