package base_trie

  1. Overview
  2. Docs
module Keychainable : sig ... end
module Iterator : sig ... end
type ('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.

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

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

Constructors via comparator.

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

Accessors at top layer of trie

val 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
val datum : ('chain, 'data, _) t -> 'data Base.option
val tries : ('chain, 'data, (_ * 'key * 'cmp * _ * _) as 'desc) t -> ('key, ('chain, 'data, 'desc) t, 'cmp) Base.Map.t
val find_child : ('chain, 'data, (_ * 'key * _ * _ * _) as 'desc) t -> 'key -> ('chain, 'data, 'desc) t Base.option

Length accessors

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

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

Key metadata accessors

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

Comparisons

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

Serialization

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

Accessors for individual elements.

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

Accessors for trie nodes

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

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

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

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

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

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

Like add_trie; raises on failure.

val 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

val invariant : 'chain Base.Invariant.t -> 'data Base.Invariant.t -> ('chain, 'data, _) t Base.Invariant.t
val keychains : ('chain, _, _) t -> 'chain Base.list
val data : (_, 'data, _) t -> 'data Base.list
val to_alist : ('chain, 'data, _) t -> ('chain * 'data) Base.list
val to_sequence : ('chain, 'data, _) t -> ('chain * 'data) Base.Sequence.t
val iter : (_, 'data, _) t -> f:('data -> Base.unit) -> Base.unit
val iter_keychains : ('chain, _, _) t -> f:('chain -> Base.unit) -> Base.unit
val 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.

val fold : ('chain, 'data, _) t -> init:'acc -> f:('acc -> 'data -> 'acc) -> 'acc
val foldi : ('chain, 'data, 'desc) t -> init:'acc -> f:('acc -> keychain:'chain -> data:'data -> 'acc) -> 'acc
val map : ('chain, 'a, 'desc) t -> f:('a -> 'b) -> ('chain, 'b, 'desc) t
val mapi : ('chain, 'a, 'desc) t -> f:(keychain:'chain -> data:'a -> 'b) -> ('chain, 'b, 'desc) t
val filter : ('chain, 'data, 'desc) t -> f:('data -> Base.bool) -> ('chain, 'data, 'desc) t
val filter_keychains : ('chain, 'data, 'desc) t -> f:('chain -> Base.bool) -> ('chain, 'data, 'desc) t
val filteri : ('chain, 'data, 'desc) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> ('chain, 'data, 'desc) t
val filter_map : ('chain, 'a, 'desc) t -> f:('a -> 'b Base.option) -> ('chain, 'b, 'desc) t
val filter_mapi : ('chain, 'a, 'desc) t -> f:(keychain:'chain -> data:'a -> 'b Base.option) -> ('chain, 'b, 'desc) t
val for_all : (_, 'data, _) t -> f:('data -> Base.bool) -> Base.bool
val for_alli : ('chain, 'data, _) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> Base.bool
val exists : (_, 'data, _) t -> f:('data -> Base.bool) -> Base.bool
val existsi : ('chain, 'data, _) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> Base.bool
val count : (_, 'data, _) t -> f:('data -> Base.bool) -> Base.int
val counti : ('chain, 'data, _) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> Base.int
val partition_tf : ('chain, 'data, 'desc) t -> f:('data -> Base.bool) -> ('chain, 'data, 'desc) t * ('chain, 'data, 'desc) t
val partitioni_tf : ('chain, 'data, 'desc) t -> f:(keychain:'chain -> data:'data -> Base.bool) -> ('chain, 'data, 'desc) t * ('chain, 'data, 'desc) t
val partition_map : ('chain, 'a, 'desc) t -> f:('a -> ('b, 'c) Base.Either.t) -> ('chain, 'b, 'desc) t * ('chain, 'c, 'desc) t
val partition_mapi : ('chain, 'a, 'desc) t -> f:(keychain:'chain -> data:'a -> ('b, 'c) Base.Either.t) -> ('chain, 'b, 'desc) t * ('chain, 'c, 'desc) t
val 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
val 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.

module Make (Keychain : Keychainable.S) : S with module Keychain = Keychain
module Of_list (Key : Base.Comparator.S) : S with module Keychain = Keychainable.Of_list(Key)
module Of_listable (Key : Base.Comparator.S) (Keychain : Keychainable.Listable with type elt = Key.t) : S with module Keychain = Keychainable.Of_listable(Key)(Keychain)
OCaml

Innovation. Community. Security.