package lazy-trie

  1. Overview
  2. Docs
Implementation of lazy prefix trees

Install 

dune-project
 Dependency

github.com Readme Edit opam file Versions (1)

Authors

  1. L
    Louis Gesbert
  2. T
    Thomas Gazagnaire

Maintainers

  1. T
    thomas@gazagnaire.org

Sources

lazy-trie-v1.2.0.tbz
sha256=c1dd53dffc0b9df94061493635e1943f9b32e26505ca331b0d0405efe5555c37
md5=480a4a13701392bd93bbd649afd7b9bb

doc/lazy-trie/Lazy_trie/index.html

Module Lazy_trieSource

Lazy tries based on lists

Sourcetype ('a, 'b) t

Type of tries mapping from 'a list to 'b

include Sexplib0.Sexpable.S2 with type ('a, 'b) t := ('a, 'b) t
Sourceval t_of_sexp : (Sexplib0.Sexp.t -> 'a) -> (Sexplib0.Sexp.t -> 'b) -> Sexplib0.Sexp.t -> ('a, 'b) t
Sourceval sexp_of_t : ('a -> Sexplib0.Sexp.t) -> ('b -> Sexplib0.Sexp.t) -> ('a, 'b) t -> Sexplib0.Sexp.t
Sourceval empty : ('a, 'b) t
Sourceval create : ?children:('a * ('a, 'b) t) list Lazy.t -> ?value:'b -> unit -> ('a, 'b) t

Create a new trie with the given components

Sourceval mem : ('a, 'b) t -> 'a list -> bool

Returns true if there is a value associated with the given path

Sourceval find : ('a, 'b) t -> 'a list -> 'b

Returns the value associated with the given path.

  • raises [Not_found]
Sourceval set : ('a, 'b) t -> 'a list -> 'b -> ('a, 'b) t

Associates a value with the given path, or replaces if there was already one

Sourceval set_lazy : ('a, 'b) t -> 'a list -> 'b Lazy.t -> ('a, 'b) t

The same but taking a lazy value

Sourceval unset : ('a, 'b) t -> 'a list -> ('a, 'b) t

Removes an association from the trie. Warning: doesn't cleanup branches that don't point to anything anymore

Sourceval map_subtree : ('a, 'b) t -> 'a list -> (('a, 'b) t -> ('a, 'b) t) -> ('a, 'b) t

map_subtree tree path f applies f on value and children of the node found at path in tree, and bind the returned node back at that position in the tree

Sourceval iter : ('a list -> 'b -> unit) -> ('a, 'b) t -> unit

iters over all the bindings in the trie, top-down

Sourceval fold : ('acc -> 'a list -> 'b -> 'acc) -> ('a, 'b) t -> 'acc -> 'acc

folds over all bindings of the trie, bottom-up

Sourceval map_filter_values : ('b -> 'c option) -> ('a, 'b) t -> ('a, 'c) t

Maps and filters over all values in the trie, removing the value if None is returned

Sourceval sub : ('a, 'b) t -> 'a list -> ('a, 'b) t

sub t p returns the sub-trie associated with the path p in the trie t. If p is not a valid path of t, it returns an empty trie.

Sourceval filter_keys : ('a -> bool) -> ('a, 'b) t -> ('a, 'b) t

filter f t returns t with all subtrees for which f key = false pruned

Sourceval graft : ('a, 'b) t -> 'a list -> ('a, 'b) t -> ('a, 'b) t

graft tree path node grafts node in tree at path

Sourceval graft_lazy : ('a, 'b) t -> 'a list -> ('a, 'b) t Lazy.t -> ('a, 'b) t

Same as graft, but using lazy parameters.