Module type V1.S

type 'a t

trie can store arbitrary data

include Core_kernel.Bin_prot.Binable.S1 with type 'a t := 'a t
val bin_shape_t : Bin_prot.Shape.t -> Bin_prot.Shape.t
val bin_size_t : ( 'a, 'a t ) Bin_prot.Size.sizer1
val bin_write_t : ( 'a, 'a t ) Bin_prot.Write.writer1
val bin_read_t : ( 'a, 'a t ) Bin_prot.Read.reader1
val __bin_read_t__ : ( 'a, int -> 'a t ) Bin_prot.Read.reader1
val bin_writer_t : ( 'a, 'a t ) Bin_prot.Type_class.S1.writer
val bin_reader_t : ( 'a, 'a t ) Bin_prot.Type_class.S1.reader
val bin_t : ( 'a, 'a t ) Bin_prot.Type_class.S1.t
include Ppx_sexp_conv_lib.Sexpable.S1 with type 'a t := 'a t
val t_of_sexp : ( Sexplib0__.Sexp.t -> 'a ) -> Sexplib0__.Sexp.t -> 'a t
val sexp_of_t : ( 'a -> Sexplib0__.Sexp.t ) -> 'a t -> Sexplib0__.Sexp.t
type key

a key type that is used to lookup data

val create : unit -> 'a t

create () creates new empty trie

val add : 'a t -> key:key -> data:'a -> unit

add trie ~key ~data associates data with key. If trie already has some value associated with key, then the value will be overwritten (rebound)

val change : 'a t -> key -> ( 'a option -> 'a option ) -> unit

change trie key f if trie has data associated with key then f will be called with Some data, otherwise it will be called with None. If f returns None then there will be no data associated with key, if f returns Some thing, then thing will be associated with key

val find : 'a t -> key -> 'a option

find trie key finds data associated with key

val walk : 'a t -> key -> init:'b -> f:( 'b -> 'a option -> 'b ) -> 'b

walk trie key ~init ~f walks down the tree starting from the root and ending with the last token of the key. Function f is fold over values associated with all substrings of the key, starting from a zero substring.

val remove : 'a t -> key -> unit

remove trie key removes value bound with key if any.

val longest_match : 'a t -> key -> (int * 'a) option

longest_match trie key find a value associated with a longest substring of key. Returns a pair - a length of matched key and the value, associated with that key.

val length : 'a t -> int

length trie returns the number of values in trie

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

pp pp_val creates a printer for a given value printer pp_val. Example:

let int_trie = String.Trie.pp pp_int

will create a printer for a String.Trie that is populated by integers.