package base_trie

You can search for identifiers within the package.

in-package search v0.2.0

package base_trie

base_trie
- LICENSE
- README
- Library base_trie
  - Trie
    
    Keychainable
    
    Impl
    
    Key
    
    Iterator
    
    Listable
    
    S
    
    Key
    
    Iterator
    
    Make
    
    Key
    
    Iterator
    
    Of_string
    
    Key
    
    Iterator
    
    Of_list
    
    Key
    
    Iterator
    
    Of_listable
    
    Key
    
    Iterator
    
    Iterator
    
    Impl0
    
    Impl1
    
    Listable0
    
    Listable1
    
    S0
    
    S1
    
    Make1
    
    Make0
    
    Monomorphic
    
    Of_string
    
    Of_list
    
    Of_listable0
    
    Of_listable1
    
    S
    
    Keychain
    
    Key
    
    Iterator
    
    Or_duplicate
    
    Make
    
    Keychain
    
    Of_string
    
    Keychain
    
    Of_list
    
    Keychain
    
    Of_listable
    
    Keychain
- Library base_trie.test_trie
  - Test_trie
- Library base_trie.trie_stable
  - Trie_stable
    
    V1
- Library base_trie.trie_stable_test
  - Trie_stable_test
- Sources
  - base_trie
    
    iterator.ml
    
    iterator_intf.ml
    
    keychainable.ml
    
    keychainable_intf.ml
    
    trie.ml
    
    trie__.ml
    
    trie_intf.ml
  - base_trie.test_trie
    
    test_iterator.ml
    
    test_trie.ml
    
    test_trie__.ml
  - base_trie.trie_stable
    
    trie_stable.ml
  - base_trie.trie_stable_test
    
    trie_stable_test.ml

Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module `Trie`Source

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.

Source

val 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

Source

val of_alist : 
  ('chain, 'desc) Keychainable.t ->
  ('chain * 'data) Base.list ->
  (('chain, 'data, 'desc) t, 'chain) Or_duplicate.t

Source

val of_alist_or_error : 
  ('chain, 'desc) Keychainable.t ->
  ('chain * 'data) Base.list ->
  ('chain, 'data, 'desc) t Base.Or_error.t

Source

val of_alist_exn : 
  ('chain, 'desc) Keychainable.t ->
  ('chain * 'data) Base.list ->
  ('chain, 'data, 'desc) t

Source

val of_alist_multi : 
  ('chain, 'desc) Keychainable.t ->
  ('chain * 'data) Base.list ->
  ('chain, 'data Base.list, 'desc) t

Source

val of_sequence : 
  ('chain, 'desc) Keychainable.t ->
  ('chain * 'data) Base.Sequence.t ->
  (('chain, 'data, 'desc) t, 'chain) Or_duplicate.t

Source

val of_sequence_or_error : 
  ('chain, 'desc) Keychainable.t ->
  ('chain * 'data) Base.Sequence.t ->
  ('chain, 'data, 'desc) t Base.Or_error.t

Source

val of_sequence_exn : 
  ('chain, 'desc) Keychainable.t ->
  ('chain * 'data) Base.Sequence.t ->
  ('chain, 'data, 'desc) t

Source

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

Source

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

Sourceval datum : ('chain, 'data, _) t -> 'data Base.option

Source

val tries : 
  ('chain, 'data, (_ * 'key * 'cmp * _ * _) as 'desc) t ->
  ('key, ('chain, 'data, 'desc) t, 'cmp) Base.Map.t

Source

val 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

Source

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

Source

val 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

Source

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

Source

val add : 
  ('chain, 'data, 'desc) t ->
  keychain:'chain ->
  data:'data ->
  (('chain, 'data, 'desc) t, 'chain) Or_duplicate.t

Source

val add_or_error : 
  ('chain, 'data, 'desc) t ->
  keychain:'chain ->
  data:'data ->
  ('chain, 'data, 'desc) t Base.Or_error.t

Source

val 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

Source

val change : 
  ('chain, 'data, 'desc) t ->
  'chain ->
  f:('data Base.option -> 'data Base.option) ->
  ('chain, 'data, 'desc) t

Source

val update : 
  ('chain, 'data, 'desc) t ->
  'chain ->
  f:('data Base.option -> 'data) ->
  ('chain, 'data, 'desc) t

Source

val add_multi : 
  ('chain, 'data Base.list, 'desc) t ->
  keychain:'chain ->
  data:'data ->
  ('chain, 'data Base.list, 'desc) t

Source

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

Source

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.

Source

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.

Source

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.

Source

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.

Source

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

Source

val 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

Source

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.

Source

val fold : 
  ('chain, 'data, _) t ->
  init:'acc ->
  f:('acc -> 'data -> 'acc) ->
  'acc

Source

val foldi : 
  ('chain, 'data, 'desc) t ->
  init:'acc ->
  f:('acc -> keychain:'chain -> data:'data -> 'acc) ->
  'acc

Sourceval map : ('chain, 'a, 'desc) t -> f:('a -> 'b) -> ('chain, 'b, 'desc) t

Source

val mapi : 
  ('chain, 'a, 'desc) t ->
  f:(keychain:'chain -> data:'a -> 'b) ->
  ('chain, 'b, 'desc) t

Source

val filter : 
  ('chain, 'data, 'desc) t ->
  f:('data -> Base.bool) ->
  ('chain, 'data, 'desc) t

Source

val filter_keychains : 
  ('chain, 'data, 'desc) t ->
  f:('chain -> Base.bool) ->
  ('chain, 'data, 'desc) t

Source

val filteri : 
  ('chain, 'data, 'desc) t ->
  f:(keychain:'chain -> data:'data -> Base.bool) ->
  ('chain, 'data, 'desc) t

Source

val filter_map : 
  ('chain, 'a, 'desc) t ->
  f:('a -> 'b Base.option) ->
  ('chain, 'b, 'desc) t

Source

val 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

Source

val for_alli : 
  ('chain, 'data, _) t ->
  f:(keychain:'chain -> data:'data -> Base.bool) ->
  Base.bool

Sourceval exists : (_, 'data, _) t -> f:('data -> Base.bool) -> Base.bool

Source

val existsi : 
  ('chain, 'data, _) t ->
  f:(keychain:'chain -> data:'data -> Base.bool) ->
  Base.bool

Sourceval count : (_, 'data, _) t -> f:('data -> Base.bool) -> Base.int

Source

val counti : 
  ('chain, 'data, _) t ->
  f:(keychain:'chain -> data:'data -> Base.bool) ->
  Base.int

Source

val partition_tf : 
  ('chain, 'data, 'desc) t ->
  f:('data -> Base.bool) ->
  ('chain, 'data, 'desc) t * ('chain, 'data, 'desc) t

Source

val partitioni_tf : 
  ('chain, 'data, 'desc) t ->
  f:(keychain:'chain -> data:'data -> Base.bool) ->
  ('chain, 'data, 'desc) t * ('chain, 'data, 'desc) t

Source

val partition_map : 
  ('chain, 'a, 'desc) t ->
  f:('a -> ('b, 'c) Base.Either.t) ->
  ('chain, 'b, 'desc) t * ('chain, 'c, 'desc) t

Source

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

Source

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

Source

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.

Sourcemodule Make (Keychain : Keychainable.S) : S with module Keychain = Keychain

Sourcemodule Of_string : S with module Keychain = Keychainable.Of_string

Source

module Of_list
  (Key : Base.Comparator.S) : 
  S with module Keychain = Keychainable.Of_list(Key)

Source

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

Module TrieSource

Module `Trie`Source