Module TrieSource

Sourcemodule Keychainable : sig ... end
Sourcemodule Iterator : sig ... end
Sourcetype ('chain, +'data, 'desc) t constraint 'desc = _ * _ * _ * _ * _

The type of a trie. Keychains have type 'chain. The data associated with each keychain has type 'data. The description of the keychain implementation is 'desc; see Keychainable.t for details.

We derive only sexp_of for this type. For stable and round-trippable serializations, see Trie_stable.

Sourceval sexp_of_t : ('chain -> Sexplib0.Sexp.t) -> ('data -> Sexplib0.Sexp.t) -> ('desc -> Sexplib0.Sexp.t) -> ('chain, 'data, 'desc) t -> Sexplib0.Sexp.t
Sourcemodule type S = sig ... end
Sourcemodule Or_duplicate : sig ... end

Unlike Base.Map, we avoid polymorphic variants for add* functions.

Constructors via comparator.

Sourceval empty : ('chain, 'desc) Keychainable.t -> ('chain, _, 'desc) t
Sourceval of_alist : ('chain, 'desc) Keychainable.t -> ('chain * 'data) Base.list -> (('chain, 'data, 'desc) t, 'chain) Or_duplicate.t
Sourceval of_alist_or_error : ('chain, 'desc) Keychainable.t -> ('chain * 'data) Base.list -> ('chain, 'data, 'desc) t Base.Or_error.t
Sourceval of_alist_exn : ('chain, 'desc) Keychainable.t -> ('chain * 'data) Base.list -> ('chain, 'data, 'desc) t
Sourceval of_alist_multi : ('chain, 'desc) Keychainable.t -> ('chain * 'data) Base.list -> ('chain, 'data Base.list, 'desc) t
Sourceval of_sequence : ('chain, 'desc) Keychainable.t -> ('chain * 'data) Base.Sequence.t -> (('chain, 'data, 'desc) t, 'chain) Or_duplicate.t
Sourceval of_sequence_or_error : ('chain, 'desc) Keychainable.t -> ('chain * 'data) Base.Sequence.t -> ('chain, 'data, 'desc) t Base.Or_error.t
Sourceval of_sequence_exn : ('chain, 'desc) Keychainable.t -> ('chain * 'data) Base.Sequence.t -> ('chain, 'data, 'desc) t
Sourceval of_sequence_multi : ('chain, 'desc) Keychainable.t -> ('chain * 'data) Base.Sequence.t -> ('chain, 'data Base.list, 'desc) t

Accessors at top layer of trie

Sourceval create : ('chain, (_ * 'key * 'cmp * _ * _) as 'desc) Keychainable.t -> datum:'data Base.option -> tries:('key, ('chain, 'data, 'desc) t, 'cmp) Base.Map.t -> ('chain, 'data, 'desc) t
Sourceval datum : ('chain, 'data, _) t -> 'data Base.option
Sourceval tries : ('chain, 'data, (_ * 'key * 'cmp * _ * _) as 'desc) t -> ('key, ('chain, 'data, 'desc) t, 'cmp) Base.Map.t
Sourceval find_child : ('chain, 'data, (_ * 'key * _ * _ * _) as 'desc) t -> 'key -> ('chain, 'data, 'desc) t Base.option

Length accessors

Sourceval is_empty : (_, _, _) t -> Base.bool
Sourceval length : (_, _, _) t -> Base.int
Sourceval num_children : (_, _, _) t -> Base.int

Faster version of t |> tries |> Map.length.

Key metadata accessors

Sourceval keychainable : ('chain, _, 'desc) t -> ('chain, 'desc) Keychainable.t
Sourceval sexp_of_keychain : ('chain, _, _) t -> 'chain -> Base.Sexp.t
Sourceval sexp_of_key : ('chain, _, _ * 'key * _ * _ * _) t -> 'key -> Base.Sexp.t

Comparisons

Sourceval compare : ('data -> 'data -> Base.int) -> ('chain, 'data, 'desc) t -> ('chain, 'data, 'desc) t -> Base.int
Sourceval equal : ('data -> 'data -> Base.bool) -> ('chain, 'data, 'desc) t -> ('chain, 'data, 'desc) t -> Base.bool

Serialization

Sourceval to_sexp : ('data -> Base.Sexp.t) -> (_, 'data, _) t -> Base.Sexp.t

Accessors for individual elements.

Sourceval mem : ('chain, _, _) t -> 'chain -> Base.bool
Sourceval find : ('chain, 'data, _) t -> 'chain -> 'data Base.option
Sourceval find_exn : ('chain, 'data, _) t -> 'chain -> 'data
Sourceval set : ('chain, 'data, 'desc) t -> keychain:'chain -> data:'data -> ('chain, 'data, 'desc) t
Sourceval add : ('chain, 'data, 'desc) t -> keychain:'chain -> data:'data -> (('chain, 'data, 'desc) t, 'chain) Or_duplicate.t
Sourceval add_or_error : ('chain, 'data, 'desc) t -> keychain:'chain -> data:'data -> ('chain, 'data, 'desc) t Base.Or_error.t
Sourceval add_exn : ('chain, 'data, 'desc) t -> keychain:'chain -> data:'data -> ('chain, 'data, 'desc) t
Sourceval remove : ('chain, 'data, 'desc) t -> 'chain -> ('chain, 'data, 'desc) t
Sourceval change : ('chain, 'data, 'desc) t -> 'chain -> f:('data Base.option -> 'data Base.option) -> ('chain, 'data, 'desc) t
Sourceval update : ('chain, 'data, 'desc) t -> 'chain -> f:('data Base.option -> 'data) -> ('chain, 'data, 'desc) t
Sourceval add_multi : ('chain, 'data Base.list, 'desc) t -> keychain:'chain -> data:'data -> ('chain, 'data Base.list, 'desc) t
Sourceval remove_multi : ('chain, 'data Base.list, 'desc) t -> 'chain -> ('chain, 'data Base.list, 'desc) t
Sourceval find_multi : ('chain, 'data Base.list, _) t -> 'chain -> 'data Base.list

Accessors for trie nodes

Sourceval mem_trie : ('chain, 'data, 'desc) t -> 'chain -> Base.bool

Reports whether there is a non-empty trie at the position of the given chain. Equivalently, reports whether the given key is a (non-strict) prefix of any element's key.

Sourceval find_trie : ('chain, 'data, 'desc) t -> 'chain -> ('chain, 'data, 'desc) t
Produces the trie at the given position. If [not (mem_trie t keychain)]], returns an
     empty trie.
Sourceval set_trie : ('chain, 'data, 'desc) t -> keychain:'chain -> trie:('chain, 'data, 'desc) t -> ('chain, 'data, 'desc) t

Replaces the trie node at the given position, if any, with the given trie.

Sourceval add_trie : ('chain, 'data, 'desc) t -> keychain:'chain -> trie:('chain, 'data, 'desc) t -> (('chain, 'data, 'desc) t, 'chain) Or_duplicate.t

Adds the given trie node at the given position, or reports a duplicate if there is already a non-empty trie there.

Sourceval add_trie_or_error : ('chain, 'data, 'desc) t -> keychain:'chain -> trie:('chain, 'data, 'desc) t -> ('chain, 'data, 'desc) t Base.Or_error.t

Like add_trie; returns an Or_error.t.

Sourceval add_trie_exn : ('chain, 'data, 'desc) t -> keychain:'chain -> trie:('chain, 'data, 'desc) t -> ('chain, 'data, 'desc) t

Like add_trie; raises on failure.

Sourceval update_trie : ('chain, 'data, 'desc) t -> 'chain -> f:(('chain, 'data, 'desc) t -> ('chain, 'data, 'desc) t) -> ('chain, 'data, 'desc) t

Modifies the trie node at the position of the given chain.

Traversals

Sourceval invariant : 'chain Base.Invariant.t -> 'data Base.Invariant.t -> ('chain, 'data, _) t Base.Invariant.t
Sourceval keychains : ('chain, _, _) t -> 'chain Base.list
Sourceval data : (_, 'data, _) t -> 'data Base.list
Sourceval to_alist : ('chain, 'data, _) t -> ('chain * 'data) Base.list
Sourceval to_sequence : ('chain, 'data, _) t -> ('chain * 'data) Base.Sequence.t
Sourceval iter : (_, 'data, _) t -> f:('data -> Base.unit) -> Base.unit
Sourceval iter_keychains : ('chain, _, _) t -> f:('chain -> Base.unit) -> Base.unit
Sourceval iteri : ('chain, 'data, _) t -> f:(keychain:'chain -> data:'data -> Base.unit) -> Base.unit

Unlike Base.Map, we distinguish fold from foldi. For consistency with Container.fold, we take the accumulator argument first in both cases.

Sourceval fold : ('chain, 'data, _) t -> init:'acc -> f:('acc -> 'data -> 'acc) -> 'acc
Sourceval foldi : ('chain, 'data, 'desc) t -> init:'acc -> f:('acc -> keychain:'chain -> data:'data -> 'acc) -> 'acc
Sourceval foldi_tries : ('chain, 'data, 'desc) t -> init:'acc -> f:('acc -> keychain:'chain -> trie:('chain, 'data, 'desc) t -> 'acc) -> 'acc

Calls f with t, plus recursively on descendent tries of t where not (is_empty trie). Passes keychain where find_trie t keychain = trie.

Sourceval map : ('chain, 'a, 'desc) t -> f:('a -> 'b) -> ('chain, 'b, 'desc) t
Sourceval mapi : ('chain, 'a, 'desc) t -> f:(keychain:'chain -> data:'a -> 'b) -> ('chain, 'b, 'desc) t
Sourceval filter : ('chain, 'data, 'desc) t -> f:('data -> Base.bool) -> ('chain, 'data, 'desc) t
Sourceval filter_keychains : ('chain, 'data, 'desc) t -> f:('chain -> Base.bool) -> ('chain, 'data, 'desc) t
Sourceval filteri : ('chain, 'data, 'desc) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> ('chain, 'data, 'desc) t
Sourceval filter_map : ('chain, 'a, 'desc) t -> f:('a -> 'b Base.option) -> ('chain, 'b, 'desc) t
Sourceval filter_mapi : ('chain, 'a, 'desc) t -> f:(keychain:'chain -> data:'a -> 'b Base.option) -> ('chain, 'b, 'desc) t
Sourceval for_all : (_, 'data, _) t -> f:('data -> Base.bool) -> Base.bool
Sourceval for_alli : ('chain, 'data, _) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> Base.bool
Sourceval exists : (_, 'data, _) t -> f:('data -> Base.bool) -> Base.bool
Sourceval existsi : ('chain, 'data, _) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> Base.bool
Sourceval count : (_, 'data, _) t -> f:('data -> Base.bool) -> Base.int
Sourceval counti : ('chain, 'data, _) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> Base.int
Sourceval partition_tf : ('chain, 'data, 'desc) t -> f:('data -> Base.bool) -> ('chain, 'data, 'desc) t * ('chain, 'data, 'desc) t
Sourceval partitioni_tf : ('chain, 'data, 'desc) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> ('chain, 'data, 'desc) t * ('chain, 'data, 'desc) t
Sourceval partition_map : ('chain, 'a, 'desc) t -> f:('a -> ('b, 'c) Base.Either.t) -> ('chain, 'b, 'desc) t * ('chain, 'c, 'desc) t
Sourceval partition_mapi : ('chain, 'a, 'desc) t -> f:(keychain:'chain -> data:'a -> ('b, 'c) Base.Either.t) -> ('chain, 'b, 'desc) t * ('chain, 'c, 'desc) t
Sourceval merge : ('chain, 'a, 'desc) t -> ('chain, 'b, 'desc) t -> f: (keychain:'chain -> [ `Left of 'a | `Right of 'b | `Both of 'a * 'b ] -> 'c Base.option) -> ('chain, 'c, 'desc) t
Sourceval merge_skewed : ('chain, 'data, 'desc) t -> ('chain, 'data, 'desc) t -> combine:(keychain:'chain -> 'data -> 'data -> 'data) -> ('chain, 'data, 'desc) t

Modules and functors specializing tries to a keychain implementation.