base_trie v0.17.0 (latest)

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_string : S with module Keychain = Keychainable.Of_string

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)

package base_trie