package yuujinchou

  1. Overview
  2. Docs

Module Yuujinchou.TrieSource

The Trie module implements a data structure that maps paths to values and supports efficient subtree operations.

Types

Sourcetype path = string list

The type of hierarchical names. The name x.y.z is represented by the OCaml list ["x"; "y"; "z"].

Sourcetype +'a t

The abstract type of a trie.

Basic Operations

Sourceval empty : 'a t

The empty trie.

Sourceval is_empty : 'a t -> bool

Check whether the trie is empty.

Sourceval root : 'a -> 'a t

root d makes a trie with the only binding: the root and its associated value d. It is equivalent to root_opt(Some d).

Sourceval root_opt : 'a option -> 'a t

root_opt d is equivalent to match d with None ->empty| Some d ->rootd. In other words, root_opt None will make an empty trie and root_opt (Some v) will make a trie with only one binding: the root associated with the value v. If the input is always Some v, use root.

Sourceval prefix : path -> 'a t -> 'a t

prefix p t makes a minimum trie with t rooted at p.

Sourceval singleton : (path * 'a) -> 'a t

singleton (p, d) makes a trie with the only binding: p and its associated value d. It is equivalent to prefixp @@rootd

Sourceval equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool

equal eq t1 t2 checks whether two tries are equal. If the internal representations of tries are physically equal, equal eq t1 t2 will immediately return true without calling eq.

Finding Values

Sourceval find_subtree : path -> 'a t -> 'a t

find_subtree p t returns the subtree rooted at p.

  • returns

    The subtrie with all the bindings under p, including the binding at p itself (which will be the root). If there are no such bindings with the prefix p, an empty trie is returned.

Sourceval find_singleton : path -> 'a t -> 'a option

find_singleton p t returns the value at p.

Sourceval find_root : 'a t -> 'a option

find_root t returns the value at the root. This is equivalent to find_singleton[] t.

Mapping and Filtering

Sourceval iteri : ?rev_prefix:path -> (rev_path:path -> 'a -> unit) -> 'a t -> unit

iteri ~rev_prefix f t applies the function f to each value v in the trie.

  • parameter rev_prefix

    The prefix prepended to any path sent to f, but in reverse. The default is the empty unit path ([]).

Sourceval mapi : ?rev_prefix:path -> (rev_path:path -> 'a -> 'b) -> 'a t -> 'b t

mapi ~rev_prefix f t applies the function f to each value v in the trie.

  • parameter rev_prefix

    The prefix prepended to any path sent to f, but in reverse. The default is the empty unit path ([]).

Sourceval mapi_endo : ?rev_prefix:path -> (rev_path:path -> 'a -> 'a) -> 'a t -> 'a t

mapi_endo ~rev_prefix f t is similar to mapif t except that the domain and the codomain of the function must be the same. The additional benefit of mapi_endo over mapi is that, if f v returns v for every value v in t, then t is returned unchanged. (That is, the new trie will be physically equal to the old one.) See filter_map_endo.

  • parameter rev_prefix

    The prefix prepended to any path sent to f, but in reverse. The default is the empty unit path ([]).

Sourceval filteri : ?rev_prefix:path -> (rev_path:path -> 'a -> bool) -> 'a t -> 'a t

filteri ~rev_prefix f t removes all values v at path p such that f ~rev_prefix:p v returns false. If f v returns true for every value v in t, then t is returned unchanged. (That is, the new trie will be physically equal to the old one.)

  • parameter rev_prefix

    The prefix prepended to any path sent to f. The default is the empty unit path ([]).

Sourceval filter_mapi : ?rev_prefix:path -> (rev_path:path -> 'a -> 'b option) -> 'a t -> 'b t

filter_mapi ~rev_prefix f t applies the function f to each value v at p in the trie. If f ~rev_prefix:p v returns None, then the binding will be removed from the trie. Otherwise, if f v returns Some v', then the value will be replaced by v'.

  • parameter rev_prefix

    The prefix prepended to any path sent to f, but in reverse. The default is the empty unit path ([]).

Sourceval filter_mapi_endo : ?rev_prefix:path -> (rev_path:path -> 'a -> 'a option) -> 'a t -> 'a t

filter_mapi_endo ~rev_prefix f t is similar to filter_mapi~rev_prefix f t except that f must be of type rev_path:path -> 'a -> 'a option; that is, its domain and codomain agree up to the option type. The additional benefit of filter_mapi_endo over filter_mapi is that if f ~rev_prefix:p v returns Some v for every value v at p in t, then t is returned unchanged. (That is, the new trie will be physically equal to the old one.) See map_endo

  • parameter rev_prefix

    The prefix prepended to any path sent to f. The default is the empty unit path ([]).

Updating

Sourceval update_subtree : path -> ('a t -> 'a t) -> 'a t -> 'a t

update_subtree p f t replaces the subtree t' rooted at p in t with f t'. It will try to preserve physical equality when f returns the trie unchanged.

Sourceval update_singleton : path -> ('a option -> 'a option) -> 'a t -> 'a t

update_singleton p f t replaces the value v at p in t with the result of f. If there was no binding at p, f None is evaluated. Otherwise, f (Some v) is used. If the result is None, the old binding at p (if any) is removed. Otherwise, if the result is Some v', the value at p is replaced by v'. It will try to preserve physical equality when f maintains the current status of binding, either returning None for None or Some v for Some v.

Sourceval update_root : ('a option -> 'a option) -> 'a t -> 'a t

update_root f t updates the value at root with f. It is equivalent to update_singleton[] f t.

Union

Sourceval union : ?rev_prefix:path -> (rev_path:path -> 'a -> 'a -> 'a) -> 'a t -> 'a t -> 'a t

union ~rev_prefix merger t1 t2 merges two tries t1 and t2. If both tries have a binding at the same path p, it will call merger ~rev_path:p x y to reconcile the values x from t1 and y from t2 that are both bound at the (reversed) path rev_path. The path rev_path is reversed for efficient traversal.

  • parameter rev_prefix

    The prefix prepended to any path sent to merger. The default is the empty unit path ([]).

Sourceval union_subtree : ?rev_prefix:path -> (rev_path:path -> 'a -> 'a -> 'a) -> 'a t -> (path * 'a t) -> 'a t

union_subtree ~rev_prefix merger t1 (path, t2) is equivalent to union~rev_prefix merger t1 (prefix path t2), but potentially more efficient.

  • parameter rev_prefix

    The prefix prepended to any path sent to merger. The default is the empty unit path ([]).

Sourceval union_singleton : ?rev_prefix:path -> (rev_path:path -> 'a -> 'a -> 'a) -> 'a t -> (path * 'a) -> 'a t

union_singleton merger t binding is equivalent to unionmerger t1 (singleton binding), but potentially more efficient.

  • parameter rev_prefix

    The prefix prepended to any path sent to merger. The default is the empty unit path ([]).

Separation

Sourceval detach_subtree : path -> 'a t -> 'a t * 'a t

detach_subtree p t detaches the subtree at p from the main trie and returns both the subtree and the remaining trie. If detach p t returns t1, t2, then union_subtreem t2 (p, t1) should be equivalent to t.

Sourceval detach_singleton : path -> 'a t -> 'a option * 'a t

detach_singleton p t detaches the binding at p from the main trie and returns both the binding and the remaining trie. If detach p t returns b, t', then union_subtreem t' (p,root_optb) should be equivalent to t.

Iterators

Sourceval to_seq : ?rev_prefix:path -> 'a t -> (path * 'a) Seq.t

to_seq ~rev_prefix t traverses through the trie t in the lexicographical order.

  • parameter rev_prefix

    The prefix prepended to any path in the output, but in reverse. The default is the empty unit path ([]).

Sourceval to_seq_with_reversed_paths : ?rev_prefix:path -> 'a t -> (path * 'a) Seq.t

to_seq_with_reversed_paths is like to_seq but with paths reversed. This is potentially more efficient than to_seq.

  • parameter rev_prefix

    The prefix prepended to any path in the output, but in reverse. The default is the empty unit path ([]).

Sourceval to_seq_values : 'a t -> 'a Seq.t

to_seq_values t traverses through the trie t in the lexicographical order but only returns the associated values. This is potentially more efficient than to_seq because path reversal is skipped.

Sourceval of_seq : ?rev_prefix:path -> (rev_path:path -> 'a -> 'a -> 'a) -> (path * 'a) Seq.t -> 'a t

of_seq ~rev_prefix merger s inserts bindings (p, d) into an empty trie, one by one, using union_subtree.

  • parameter rev_prefix

    The prefix prepended to any path sent to merger, but in reverse. The default is the empty unit path ([]).