Library
Module
Module type
Parameter
Class
Class type
The Trie
module implements a data structure that maps paths to values and supports efficient subtree operations.
The type of hierarchical names. The name x.y.z
is represented by the OCaml list ["x"; "y"; "z"]
.
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
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
.
val find_root : 'a t -> 'a option
find_root t
returns the value at the root. This is equivalent to find_singleton
[] t
.
iteri ~rev_prefix f t
applies the function f
to each value v
in the trie.
mapi ~rev_prefix f t
applies the function f
to each value v
in the trie.
mapi_endo ~rev_prefix f t
is similar to mapi
f 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
.
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.)
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'
.
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
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.
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
.
update_root f t
updates the value at root with f
. It is equivalent to update_singleton
[] f 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.
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.
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 union
merger t1 (singleton binding)
, but potentially more efficient.
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_subtree
m t2 (p, t1)
should be equivalent to 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_subtree
m t' (p,
root_opt
b)
should be equivalent to t
.
to_seq ~rev_prefix t
traverses through the trie t
in the lexicographical order.
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.