package soteria

  1. Overview
  2. Docs
package soteria
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module PatriciaTree.MakeMap

Parameters

module Key : Key

Signature

type key = Key.t
type 'a t
val empty : 'a t
val is_empty : 'a t -> bool
val cardinal : 'a t -> int

Number of bindings. For a weak map, this counts the bindings that have not been collected yet, and is therefore only meaningful right after compact.

val singleton : key -> 'a -> 'a t
val mem : key -> 'a t -> bool
val find : key -> 'a t -> 'a
val find_opt : key -> 'a t -> 'a option
val add : key -> 'a -> 'a t -> 'a t

Adds a binding, replacing any existing one.

val add_assert_new : key -> 'a -> 'a t -> 'a t

add_assert_new k v m is add k v m, but raises Invalid_argument if k is already bound in m.

val remove : key -> 'a t -> 'a t
val update : key -> ('a option -> 'a option) -> 'a t -> 'a t

update k f m rebinds k to f (find_opt k m), removing the binding when f returns None. Must return m itself when the result of f is physically equal to its argument.

val update_from : 'b t -> (key -> 'a option -> 'b -> 'a option) -> 'a t -> 'a t

update_from guide f m updates m at every key bound in guide: each binding (k, y) of guide rebinds k to f k (find_opt k m) y, removing the binding when f returns None. Keys bound in m but not in guide are left untouched.

This descends both tries simultaneously in a single pass, rather than iterating over guide and updating m key by key.

val union : (key -> 'a -> 'a -> 'a) -> 'a t -> 'a t -> 'a t

union f m1 m2 keeps the bindings of both maps, resolving conflicts with f. f must be idempotent (f k v v = v) so that shared subtrees can be returned without being traversed.

val inter : (key -> 'a -> 'a -> 'a) -> 'a t -> 'a t -> 'a t

inter f m1 m2 keeps only the keys bound in both maps, combining values with f. f must be idempotent (f k v v = v), as for union.

val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool

equal eq m1 m2 tests whether the two maps bind the same keys to equivalent values. eq must be reflexive, so that physically equal subtrees can be skipped.

val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'acc -> 'acc) -> 'a t -> 'acc -> 'acc
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val to_seq : 'a t -> (key * 'a) Seq.t
val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
val compact : 'a t -> 'a t

Rebuilds the trie from its live bindings, discarding the internal nodes left behind by collected entries. This is the identity (and should be O(1)) for a strong map; for a weak map it is what makes traversals proportional to the number of live bindings again.

val pp : (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit