yuujinchou 2.0.0 · OCaml Package

The Trie module implements mappings from paths to values that support efficient subtree operations.

Types

type path = string list

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

type +'a t

The abstract type of a trie.

Basic Operations

val empty : 'a t

The empty trie.

val is_empty : 'a t -> bool

Check whether the trie is empty.

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

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

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

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

val 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

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

equal eq t1 t2 checks whether two tries are equal.

Finding Values

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

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

find_singleton p t returns the value at p.

val 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

val 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 ([]).

val 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 ([]).

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

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

val 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 ([]).

Updating

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

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

val 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

val 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 ([]).

val 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 ([]).

val 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

val 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 (in that order). If detach p t returns t1, t2, then union_subtreem t2 (p, t1) should be equivalent to t.

val 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

val 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 ([]).

val 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 ([]).

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

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

parameter rev_prefix
The prefix prepended to any path sent to merger, but in reverse. The default is the empty unit path ([]). Note that rev_prefix does not directly affect the output trie, only the argument to merger.

Operations with `result`

module Result : sig ... end

package yuujinchou