package incr_map

You can search for identifiers within the package.

in-package search v0.2.0

Helpers for incremental operations on map like data structures

Install

dune-project

Dependency

github.com Changelog MIT License Edit opam file Versions (6)

Authors

J

Jane Street Group, LLC

Maintainers

J

Jane Street developers

Sources

v0.17.0.tar.gz

sha256=91acc784e4760af8544c4504bee1a9f6d7385eb0620f8e56392cd193a250b7d2

doc/incr_map/Incr_map/Lookup/index.html

Module `Incr_map.Lookup`Source

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

The complexity of an update depends on:

n: the number of keys in the larger of the old/updated input map
k: the number of lookup nodes created using find
m: the number of elements in the symdiff of the maps
symdiff(n): the cost of performing the symdiff on the map (m <= symdiff(n) <= n)

Each update should cost O(symdiff(n) + m * log k), so this will be efficient when there are a lot of lookups (close to n) into a map which can be efficiently symdiffed (and therefore has a small number of changes also). The cost of updating when performing the same lookups by means of Incr.map ~f:(fun m -> Map.find m key) is O(k * log n).

Sourcetype ('k, 'v, 'cmp, 'w) t

Source

val create : 
  ?instrumentation:Instrumentation.t ->
  ?data_equal:('v -> 'v -> bool) ->
  (('k, 'v, 'cmp) Core.Map.t, 'w) Incremental.t ->
  comparator:('k, 'cmp) Core.Comparator.t ->
  ('k, 'v, 'cmp, 'w) t

Create the lookup structure on an incremental map.

Sourceval find : ('k, 'v, _, 'w) t -> 'k -> ('v option, 'w) Incremental.t

Create a node which performs Map.find on the input map.

find (create incr_map) key should be equivalent to Incr.map ~f:(fun m -> Map.find m key) incr_map, but when you call find many times for a single create the nodes should update more efficiently in stabilisation when incr_map changes in a way which can be efficiently diffed.

This will re-use existing nodes when it can, but will not always do so.

Sourcemodule M (K : sig ... end) : sig ... end

A convenient way to refer to the type for a given key.

Sourcemodule For_debug : sig ... end