xb5_trees (xb5 v1.0.1)

View Source

An ordered key-value store backed by a B-tree of order 5, and a drop-in alternative to gb_trees.

Keys are kept in ascending Erlang term order. Comparisons use == rather than =:= — so key 1 and key 1.0 are considered the same key.

Conversion to a list of {Key, Value} pairs via to_list/1 always yields entries in ascending key order.

Beyond gb_trees

In addition to the gb_trees API, xb5_trees provides:

See also

Examples

> T = xb5_trees:from_list([{b, 2}, {a, 1}]).
> xb5_trees:get(a, T).
1
> xb5_trees:largest(T).
{b, 2}

Summary

Types

iter()

Shorthand for iter(_, _).

iter(Key, Value)

An iterator over entries of type {Key, Value}. See iterator/1 and next/1.

tree()

Shorthand for tree(_, _).

tree(Key, Value)

An ordered key-value tree containing entries of type {Key, Value}.

unwrapped_tree(Key, Value)

A plain-map representation of a tree, suitable for cross-language serialization (for example, converting to or from an Elixir struct that uses the same underlying node structures).

Functions

balance(Tree1)

Returns Tree unchanged.

delete(Key, Tree1)

Removes key Key from Tree1, returning a new tree Tree2.

delete_any(Key, Tree1)

Removes key Key from Tree1 if present, returning a new tree Tree2. If Key is not present, Tree1 is returned unchanged.

empty()

Equivalent to new/0.

enter(Key, Value, Tree1)

Inserts Key with value Value into Tree1 if the key is not present, otherwise updates Key to value Value in Tree1.

foldl(Function, Acc0, Tree)

Folds Function over all entries of Tree in ascending key order, calling Function(Key, Value, AccIn) for each entry. Returns the final accumulator value.

foldr(Function, Acc0, Tree)

Folds Function over all entries of Tree in descending key order, calling Function(Key, Value, AccIn) for each entry. Returns the final accumulator value.

from_list(List)

Returns a tree of the key-value pairs in List. Duplicate keys are resolved by keeping the last occurrence.

from_orddict(Orddict)

Returns a tree built from the ordered dictionary Orddict.

get(Key, Tree)

Retrieves the value stored with Key in Tree.

insert(Key, Value, Tree1)

Inserts Key with value Value into Tree1, returning a new tree Tree2.

insert_with(Key, Fun, Tree1)

Like insert/3, but takes a zero-arity fun that is only evaluated when the key is not yet present. Returns a new tree Tree2 with the key inserted.

intersect(Tree1, Tree2)

Returns the intersection of Tree1 and Tree2, i.e., a tree containing only the keys present in both trees. For keys present in both, the value from Tree2 is kept.

intersect_with(Fun, Tree1, Tree2)

Returns the intersection of Tree1 and Tree2, using Fun to compute the value for each key present in both trees. Fun is called as Fun(Key, Value1, Value2) where Value1 is from Tree1 and Value2 is from Tree2.

is_defined(Key, Tree)

Returns true if Key is present in Tree, otherwise false.

is_empty(Tree)

Returns true if Tree is empty, otherwise false.

is_equal(Tree1, Tree2)

Returns true if Tree1 and Tree2 contain the same keys and values, otherwise false.

iterator(Tree)

Returns an iterator that can be used for traversing the entries of Tree; see next/1. Equivalent to iterator(Tree, ordered).

iterator(Tree, Order)

Returns an iterator that can be used for traversing the entries of Tree in the given Order; see next/1.

iterator_from(Key, Tree)

Returns an iterator that can be used for traversing the entries of Tree starting from the first key greater than or equal to Key; see next/1. Equivalent to iterator_from(Key, Tree, ordered).

iterator_from(Key, Tree, Order)

Returns an iterator that can be used for traversing the entries of Tree starting from the key nearest to Key in the given Order; see next/1.

keys(Tree)

Returns the keys in Tree as an ordered list.

larger(Key1, Tree)

Returns {Key2, Value} where Key2 is the least key strictly greater than Key1 in Tree, or none if no such key exists.

largest(Tree)

Returns {Key, Value} where Key is the largest key in Tree.

lookup(Key, Tree)

Looks up Key in Tree. Returns {value, Value} if Key is present, or none if Key is not present.

map(Function, Tree1)

Maps Function over all values in Tree1, returning a new tree Tree2 with the same keys. For each entry, Function(Key, Value1) must return the new value Value2.

merge(Tree1, Tree2)

Merges Tree1 and Tree2 into a single tree. For keys present in both trees, the value from Tree2 is kept.

merge_with(Fun, Tree1, Tree2)

Merges Tree1 and Tree2 into a single tree, using Fun to compute the value for each key present in both trees. Fun is called as Fun(Key, Value1, Value2) where Value1 is from Tree1 and Value2 is from Tree2.

new()

Returns a new empty tree.

next(Iter1)

Returns {Key, Value, Iter2} where Key and Value are the next entry referred to by iterator Iter1 and Iter2 is the updated iterator, or none if no more entries remain.

size(Tree)

Returns the number of entries in Tree.

smaller(Key1, Tree)

Returns {Key2, Value} where Key2 is the greatest key strictly less than Key1 in Tree, or none if no such key exists.

smallest(Tree)

Returns {Key, Value} where Key is the smallest key in Tree.

structural_stats(Tree)

Returns structural statistics about the B-tree backing Tree.

take(Key, Tree1)

Returns {Value, Tree2} where Value is the value associated with Key and Tree2 is Tree1 with Key removed.

take_any(Key, Tree1)

Like take/2, but returns error if the key is not present instead of raising an exception.

take_largest(Tree1)

Returns {Key, Value, Tree2} where Key is the largest key in Tree1, Value is its associated value, and Tree2 is Tree1 with that entry removed.

take_smallest(Tree1)

Returns {Key, Value, Tree2} where Key is the smallest key in Tree1, Value is its associated value, and Tree2 is Tree1 with that entry removed.

to_list(Tree)

Converts Tree into an ordered list of {Key, Value} tuples.

unwrap(Term)

Unwraps an opaque tree into a plain map representation suitable for cross-language interop (for example, converting to an Elixir struct that uses the same underlying node module). Returns {ok, Unwrapped} on success or {error, Reason} if Term is not a valid tree.

update(Key, Value, Tree1)

Updates Key to value Value in Tree1, returning a new tree Tree2.

update_with(Key, Fun, Tree1)

Applies Fun to the current value of Key in Tree1, storing the result as the new value and returning the updated tree Tree2.

update_with(Key, Fun, Init, Tree1)

Like update_with/3, but inserts Init as the value if Key is not present in Tree1.

values(Tree)

Returns the values in Tree as a list, ordered by their corresponding keys.

wrap/1

Wraps a plain map representation back into an opaque tree.

Types

iter()

-type iter() :: iter(_, _).

Shorthand for iter(_, _).

iter(Key, Value)

-opaque iter(Key, Value)

An iterator over entries of type {Key, Value}. See iterator/1 and next/1.

tree()

-type tree() :: tree(_, _).

Shorthand for tree(_, _).

tree(Key, Value)

-opaque tree(Key, Value)

An ordered key-value tree containing entries of type {Key, Value}.

unwrapped_tree(Key, Value)

-type unwrapped_tree(Key, Value) :: #{size := non_neg_integer(), root := xb5_trees_node:t(Key, Value)}.

A plain-map representation of a tree, suitable for cross-language serialization (for example, converting to or from an Elixir struct that uses the same underlying node structures).

See unwrap/1 and wrap/1.

Functions

balance(Tree1)

-spec balance(Tree1) -> Tree2 when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).

Returns Tree unchanged.

This function exists only to ease migration from gb_trees. Since xb5 B-trees are always balanced, calling this function is never necessary.

Examples

> T = xb5_trees:from_list([{3, c}, {1, a}, {2, b}]).
> xb5_trees:to_list(xb5_trees:balance(T)).
[{1, a}, {2, b}, {3, c}]

delete(Key, Tree1)

-spec delete(Key, Tree1) -> Tree2 when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).

Removes key Key from Tree1, returning a new tree Tree2.

Raises a {badkey, Key} error if the key is not present.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> xb5_trees:to_list(xb5_trees:delete(2, T)).
[{1, a}, {3, c}]

delete_any(Key, Tree1)

-spec delete_any(Key, Tree1) -> Tree2 when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).

Removes key Key from Tree1 if present, returning a new tree Tree2. If Key is not present, Tree1 is returned unchanged.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> xb5_trees:to_list(xb5_trees:delete_any(2, T)).
[{1, a}, {3, c}]
> xb5_trees:to_list(xb5_trees:delete_any(42, T)).
[{1, a}, {2, b}, {3, c}]

empty()

-spec empty() -> tree().

Equivalent to new/0.

enter(Key, Value, Tree1)

-spec enter(Key, Value, Tree1) -> Tree2 when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).

Inserts Key with value Value into Tree1 if the key is not present, otherwise updates Key to value Value in Tree1.

Examples

> T0 = xb5_trees:new().
> T1 = xb5_trees:enter(1, a, T0).
> xb5_trees:to_list(T1).
[{1, a}]
> T2 = xb5_trees:enter(1, z, T1).
> xb5_trees:to_list(T2).
[{1, z}]
> T3 = xb5_trees:enter(2, b, T2).
> xb5_trees:to_list(T3).
[{1, z}, {2, b}]

foldl(Function, Acc0, Tree)

-spec foldl(Function, Acc0, Tree) -> Acc1
               when
                   Function :: fun((Key, Value, AccIn) -> AccOut),
                   Acc0 :: Acc,
                   Acc1 :: Acc,
                   AccIn :: Acc,
                   AccOut :: Acc,
                   Tree :: tree(Key, Value).

Folds Function over all entries of Tree in ascending key order, calling Function(Key, Value, AccIn) for each entry. Returns the final accumulator value.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> xb5_trees:foldl(fun(K, V, Acc) -> [{K, V} | Acc] end, [], T).
[{3, c}, {2, b}, {1, a}]

foldr(Function, Acc0, Tree)

-spec foldr(Function, Acc0, Tree) -> Acc1
               when
                   Function :: fun((Key, Value, AccIn) -> AccOut),
                   Acc0 :: Acc,
                   Acc1 :: Acc,
                   AccIn :: Acc,
                   AccOut :: Acc,
                   Tree :: tree(Key, Value).

Folds Function over all entries of Tree in descending key order, calling Function(Key, Value, AccIn) for each entry. Returns the final accumulator value.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> xb5_trees:foldr(fun(K, V, Acc) -> [{K, V} | Acc] end, [], T).
[{1, a}, {2, b}, {3, c}]

from_list(List)

-spec from_list(List) -> Tree when List :: [{Key, Value}], Tree :: tree(Key, Value).

Returns a tree of the key-value pairs in List. Duplicate keys are resolved by keeping the last occurrence.

It sorts the List by key and then delegates to from_orddict/1 - see that function for performance characteristics.

Examples

> xb5_trees:to_list(xb5_trees:from_list([{3, c}, {1, a}, {2, b}])).
[{1, a}, {2, b}, {3, c}]
> xb5_trees:to_list(xb5_trees:from_list([{1, a}, {1, z}])).
[{1, z}]
> xb5_trees:to_list(xb5_trees:from_list([])).
[]

from_orddict(Orddict)

-spec from_orddict(Orddict) -> Tree
                      when Orddict :: orddict:orddict(Key, Value), Tree :: tree(Key, Value).

Returns a tree built from the ordered dictionary Orddict.

The tree is built by recursively splitting the list top-down rather than by sequential insertion, yielding an optimally balanced result without intermediate allocations or element comparisons. This is analogous to gb_trees:from_orddict/1.

Examples

> xb5_trees:to_list(xb5_trees:from_orddict([{1, a}, {2, b}])).
[{1, a}, {2, b}]

get(Key, Tree)

-spec get(Key, Tree) -> Value when Tree :: tree(Key, Value).

Retrieves the value stored with Key in Tree.

Raises a {badkey, Key} error if the key is not present.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> xb5_trees:get(2, T).
b

insert(Key, Value, Tree1)

-spec insert(Key, Value, Tree1) -> Tree2 when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).

Inserts Key with value Value into Tree1, returning a new tree Tree2.

Raises a {key_exists, Key} error if the key is already present.

Examples

> T0 = xb5_trees:new().
> T1 = xb5_trees:insert(1, a, T0).
> xb5_trees:to_list(T1).
[{1, a}]
> T2 = xb5_trees:insert(2, b, T1).
> xb5_trees:to_list(T2).
[{1, a}, {2, b}]

insert_with(Key, Fun, Tree1)

-spec insert_with(Key, Fun, Tree1) -> Tree2
                     when Fun :: fun(() -> Value), Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).

Like insert/3, but takes a zero-arity fun that is only evaluated when the key is not yet present. Returns a new tree Tree2 with the key inserted.

Raises a {key_exists, Key} error if the key already exists.

Examples

> T0 = xb5_trees:new().
> T1 = xb5_trees:insert_with(1, fun() -> a end, T0).
> xb5_trees:to_list(T1).
[{1, a}]

intersect(Tree1, Tree2)

-spec intersect(Tree1, Tree2) -> Tree3
                   when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value), Tree3 :: tree(Key, Value).

Returns the intersection of Tree1 and Tree2, i.e., a tree containing only the keys present in both trees. For keys present in both, the value from Tree2 is kept.

Examples

> T1 = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> T2 = xb5_trees:from_list([{2, x}, {3, y}, {4, z}]).
> xb5_trees:to_list(xb5_trees:intersect(T1, T2)).
[{2, x}, {3, y}]

intersect_with(Fun, Tree1, Tree2)

-spec intersect_with(Fun, Tree1, Tree2) -> Tree3
                        when
                            Fun :: fun((Key1 | Key2, Value1, Value2) -> Value3),
                            Tree1 :: tree(Key1, Value1),
                            Tree2 :: tree(Key2, Value2),
                            Tree3 :: tree(Key1 | Key2, Value3).

Returns the intersection of Tree1 and Tree2, using Fun to compute the value for each key present in both trees. Fun is called as Fun(Key, Value1, Value2) where Value1 is from Tree1 and Value2 is from Tree2.

Examples

> T1 = xb5_trees:from_list([{1, 10}, {2, 20}, {3, 30}]).
> T2 = xb5_trees:from_list([{2, 2}, {3, 3}, {4, 4}]).
> F = fun(_K, V1, V2) -> V1 * V2 end.
> xb5_trees:to_list(xb5_trees:intersect_with(F, T1, T2)).
[{2, 40}, {3, 90}]

is_defined(Key, Tree)

-spec is_defined(Key, Tree) -> boolean() when Tree :: tree(Key, Value :: term()).

Returns true if Key is present in Tree, otherwise false.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> xb5_trees:is_defined(2, T).
true
> xb5_trees:is_defined(42, T).
false

is_empty(Tree)

-spec is_empty(Tree) -> boolean() when Tree :: tree().

Returns true if Tree is empty, otherwise false.

Examples

> xb5_trees:is_empty(xb5_trees:new()).
true
> xb5_trees:is_empty(xb5_trees:from_list([{1, a}])).
false

is_equal(Tree1, Tree2)

-spec is_equal(Tree1, Tree2) -> boolean() when Tree1 :: tree(), Tree2 :: tree().

Returns true if Tree1 and Tree2 contain the same keys and values, otherwise false.

Keys are compared with ==, values with =:=.

Examples

> S1 = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> S2 = xb5_trees:from_list([{3, c}, {1.0, a}, {2, b}]).
> xb5_trees:is_equal(S1, S2).
true
> S3 = xb5_trees:from_list([{1, x}, {2, y}]).
> xb5_trees:is_equal(S1, S3).
false

iterator(Tree)

-spec iterator(Tree) -> Iter when Tree :: tree(Key, Value), Iter :: iter(Key, Value).

Returns an iterator that can be used for traversing the entries of Tree; see next/1. Equivalent to iterator(Tree, ordered).

Examples

> T = xb5_trees:from_list([{3, c}, {1, a}, {2, b}]).
> I = xb5_trees:iterator(T).
> {1, a, I2} = xb5_trees:next(I).
> {2, b, I3} = xb5_trees:next(I2).
> {3, c, I4} = xb5_trees:next(I3).
> xb5_trees:next(I4).
none

iterator(Tree, Order)

-spec iterator(Tree, Order) -> Iter
                  when Tree :: tree(Key, Value), Iter :: iter(Key, Value), Order :: ordered | reversed.

Returns an iterator that can be used for traversing the entries of Tree in the given Order; see next/1.

Order must be ordered (ascending) or reversed (descending).

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> I = xb5_trees:iterator(T, reversed).
> {3, c, I2} = xb5_trees:next(I).
> {2, b, I3} = xb5_trees:next(I2).
> {1, a, I4} = xb5_trees:next(I3).
> xb5_trees:next(I4).
none

iterator_from(Key, Tree)

-spec iterator_from(Key, Tree) -> Iter when Tree :: tree(Key, Value), Iter :: iter(Key, Value).

Returns an iterator that can be used for traversing the entries of Tree starting from the first key greater than or equal to Key; see next/1. Equivalent to iterator_from(Key, Tree, ordered).

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}, {4, d}, {5, e}]).
> I = xb5_trees:iterator_from(3, T).
> {3, c, I2} = xb5_trees:next(I).
> {4, d, I3} = xb5_trees:next(I2).
> {5, e, I4} = xb5_trees:next(I3).
> xb5_trees:next(I4).
none

iterator_from(Key, Tree, Order)

-spec iterator_from(Key, Tree, Order) -> Iter
                       when
                           Tree :: tree(Key, Value),
                           Iter :: iter(Key, Value),
                           Order :: ordered | reversed.

Returns an iterator that can be used for traversing the entries of Tree starting from the key nearest to Key in the given Order; see next/1.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}, {4, d}, {5, e}]).
> I = xb5_trees:iterator_from(3, T, reversed).
> {3, c, I2} = xb5_trees:next(I).
> {2, b, I3} = xb5_trees:next(I2).
> {1, a, I4} = xb5_trees:next(I3).
> xb5_trees:next(I4).
none

keys(Tree)

-spec keys(Tree) -> [Key] when Tree :: tree(Key, _).

Returns the keys in Tree as an ordered list.

Examples

> T = xb5_trees:from_list([{3, c}, {1, a}, {2, b}]).
> xb5_trees:keys(T).
[1, 2, 3]

larger(Key1, Tree)

-spec larger(Key1, Tree) -> none | {Key2, Value} when Key1 :: Key, Key2 :: Key, Tree :: tree(Key, Value).

Returns {Key2, Value} where Key2 is the least key strictly greater than Key1 in Tree, or none if no such key exists.

Examples

> T = xb5_trees:from_list([{1, a}, {3, c}, {5, e}]).
> xb5_trees:larger(2, T).
{3, c}
> xb5_trees:larger(5, T).
none

largest(Tree)

-spec largest(Tree) -> {Key, Value} when Tree :: tree(Key, Value).

Returns {Key, Value} where Key is the largest key in Tree.

Raises an empty_tree error if the tree is empty.

Examples

> xb5_trees:largest(xb5_trees:from_list([{1, a}, {2, b}, {3, c}])).
{3, c}

lookup(Key, Tree)

-spec lookup(Key, Tree) -> none | {value, Value} when Tree :: tree(Key, Value).

Looks up Key in Tree. Returns {value, Value} if Key is present, or none if Key is not present.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> xb5_trees:lookup(2, T).
{value, b}
> xb5_trees:lookup(42, T).
none

map(Function, Tree1)

-spec map(Function, Tree1) -> Tree2
             when
                 Function :: fun((K :: Key, V1 :: Value1) -> V2 :: Value2),
                 Tree1 :: tree(Key, Value1),
                 Tree2 :: tree(Key, Value2).

Maps Function over all values in Tree1, returning a new tree Tree2 with the same keys. For each entry, Function(Key, Value1) must return the new value Value2.

Examples

> T = xb5_trees:from_list([{1, 10}, {2, 20}, {3, 30}]).
> xb5_trees:to_list(xb5_trees:map(fun(_K, V) -> V * 2 end, T)).
[{1, 20}, {2, 40}, {3, 60}]

merge(Tree1, Tree2)

-spec merge(Tree1, Tree2) -> Tree3
               when
                   Tree1 :: tree(KeyA, ValueA),
                   Tree2 :: tree(KeyB, ValueB),
                   Tree3 :: tree(KeyA | KeyB, ValueA | ValueB).

Merges Tree1 and Tree2 into a single tree. For keys present in both trees, the value from Tree2 is kept.

Examples

> T1 = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> T2 = xb5_trees:from_list([{2, x}, {4, y}]).
> xb5_trees:to_list(xb5_trees:merge(T1, T2)).
[{1, a}, {2, x}, {3, c}, {4, y}]

merge_with(Fun, Tree1, Tree2)

-spec merge_with(Fun, Tree1, Tree2) -> Tree3
                    when
                        Fun :: fun((KeyA | KeyB, ValueA, ValueB) -> MergeValue),
                        Tree1 :: tree(KeyA, ValueA),
                        Tree2 :: tree(KeyB, ValueB),
                        Tree3 :: tree(KeyA | KeyB, ValueA | ValueB | MergeValue).

Merges Tree1 and Tree2 into a single tree, using Fun to compute the value for each key present in both trees. Fun is called as Fun(Key, Value1, Value2) where Value1 is from Tree1 and Value2 is from Tree2.

Examples

> T1 = xb5_trees:from_list([{1, 10}, {2, 20}, {3, 30}]).
> T2 = xb5_trees:from_list([{2, 2}, {4, 40}]).
> F = fun(_K, V1, V2) -> V1 + V2 end.
> xb5_trees:to_list(xb5_trees:merge_with(F, T1, T2)).
[{1, 10}, {2, 22}, {3, 30}, {4, 40}]

new()

-spec new() -> tree().

Returns a new empty tree.

Examples

> xb5_trees:is_empty(xb5_trees:new()).
true
> xb5_trees:size(xb5_trees:new()).
0

next(Iter1)

-spec next(Iter1) -> none | {Key, Value, Iter2}
              when Iter1 :: iter(Key, Value), Iter2 :: iter(Key, Value).

Returns {Key, Value, Iter2} where Key and Value are the next entry referred to by iterator Iter1 and Iter2 is the updated iterator, or none if no more entries remain.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}]).
> I = xb5_trees:iterator(T).
> {1, a, I2} = xb5_trees:next(I).
> {2, b, I3} = xb5_trees:next(I2).
> xb5_trees:next(I3).
none

size(Tree)

-spec size(Tree) -> non_neg_integer() when Tree :: tree().

Returns the number of entries in Tree.

Examples

> xb5_trees:size(xb5_trees:new()).
0
> xb5_trees:size(xb5_trees:from_list([{1, a}, {2, b}, {3, c}])).
3

smaller(Key1, Tree)

-spec smaller(Key1, Tree) -> none | {Key2, Value}
                 when Key1 :: Key, Key2 :: Key, Tree :: tree(Key, Value).

Returns {Key2, Value} where Key2 is the greatest key strictly less than Key1 in Tree, or none if no such key exists.

Examples

> T = xb5_trees:from_list([{1, a}, {3, c}, {5, e}]).
> xb5_trees:smaller(4, T).
{3, c}
> xb5_trees:smaller(1, T).
none

smallest(Tree)

-spec smallest(Tree) -> {Key, Value} when Tree :: tree(Key, Value).

Returns {Key, Value} where Key is the smallest key in Tree.

Raises an empty_tree error if the tree is empty.

Examples

> xb5_trees:smallest(xb5_trees:from_list([{3, c}, {1, a}, {2, b}])).
{1, a}

structural_stats(Tree)

-spec structural_stats(Tree) -> Stats when Tree :: tree(), Stats :: xb5_structural_stats:t().

Returns structural statistics about the B-tree backing Tree.

This is primarily intended for debugging and testing. The result is a proplist with keys such as height, total_keys, node_counts, node_percentages, and others.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> Stats = xb5_trees:structural_stats(T).
> {height, 1} = lists:keyfind(height, 1, Stats).
> {total_keys, 3} = lists:keyfind(total_keys, 1, Stats).

take(Key, Tree1)

-spec take(Key, Tree1) -> {Value, Tree2}
              when Tree1 :: tree(Key, _), Tree2 :: tree(Key, _), Key :: term(), Value :: term().

Returns {Value, Tree2} where Value is the value associated with Key and Tree2 is Tree1 with Key removed.

Raises a {badkey, Key} error if the key is not present.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> {b, T2} = xb5_trees:take(2, T).
> xb5_trees:to_list(T2).
[{1, a}, {3, c}]

take_any(Key, Tree1)

-spec take_any(Key, Tree1) -> {Value, Tree2} | error
                  when Tree1 :: tree(Key, _), Tree2 :: tree(Key, _), Key :: term(), Value :: term().

Like take/2, but returns error if the key is not present instead of raising an exception.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> {b, T2} = xb5_trees:take_any(2, T).
> xb5_trees:to_list(T2).
[{1, a}, {3, c}]
> xb5_trees:take_any(42, T).
error

take_largest(Tree1)

-spec take_largest(Tree1) -> {Key, Value, Tree2}
                      when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).

Returns {Key, Value, Tree2} where Key is the largest key in Tree1, Value is its associated value, and Tree2 is Tree1 with that entry removed.

Raises an empty_tree error if the tree is empty.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> {3, c, T2} = xb5_trees:take_largest(T).
> xb5_trees:to_list(T2).
[{1, a}, {2, b}]

take_smallest(Tree1)

-spec take_smallest(Tree1) -> {Key, Value, Tree2}
                       when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).

Returns {Key, Value, Tree2} where Key is the smallest key in Tree1, Value is its associated value, and Tree2 is Tree1 with that entry removed.

Raises an empty_tree error if the tree is empty.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> {1, a, T2} = xb5_trees:take_smallest(T).
> xb5_trees:to_list(T2).
[{2, b}, {3, c}]

to_list(Tree)

-spec to_list(Tree) -> [{Key, Value}] when Tree :: tree(Key, Value).

Converts Tree into an ordered list of {Key, Value} tuples.

Examples

> xb5_trees:to_list(xb5_trees:from_list([{3, c}, {1, a}, {2, b}])).
[{1, a}, {2, b}, {3, c}]
> xb5_trees:to_list(xb5_trees:new()).
[]

unwrap(Term)

-spec unwrap(Term :: _) -> {ok, unwrapped_tree(_, _)} | {error, Reason :: _}.

Unwraps an opaque tree into a plain map representation suitable for cross-language interop (for example, converting to an Elixir struct that uses the same underlying node module). Returns {ok, Unwrapped} on success or {error, Reason} if Term is not a valid tree.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> {ok, Unwrapped} = xb5_trees:unwrap(T).
> maps:get(size, Unwrapped).
3
> {error, _} = xb5_trees:unwrap(not_a_tree).

update(Key, Value, Tree1)

-spec update(Key, Value, Tree1) -> Tree2 when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).

Updates Key to value Value in Tree1, returning a new tree Tree2.

Raises a {badkey, Key} error if the key is not present.

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> xb5_trees:to_list(xb5_trees:update(2, z, T)).
[{1, a}, {2, z}, {3, c}]

update_with(Key, Fun, Tree1)

-spec update_with(Key, Fun, Tree1) -> Tree2
                     when
                         Fun :: fun((Value1) -> Value2),
                         Tree1 :: tree(Key, Value | Value1),
                         Tree2 :: tree(Key, Value | Value2).

Applies Fun to the current value of Key in Tree1, storing the result as the new value and returning the updated tree Tree2.

Raises a {badkey, Key} error if the key is not present.

Examples

> T = xb5_trees:from_list([{1, 10}, {2, 20}, {3, 30}]).
> xb5_trees:to_list(xb5_trees:update_with(2, fun(V) -> V + 1 end, T)).
[{1, 10}, {2, 21}, {3, 30}]

update_with(Key, Fun, Init, Tree1)

-spec update_with(Key, Fun, Init, Tree1) -> Tree2
                     when
                         Fun :: fun((Value1) -> Value2),
                         Tree1 :: tree(Key, Value | Value1),
                         Tree2 :: tree(Key, Value | Value2 | Init).

Like update_with/3, but inserts Init as the value if Key is not present in Tree1.

Examples

> T = xb5_trees:from_list([{1, 10}, {2, 20}]).
> T2 = xb5_trees:update_with(2, fun(V) -> V + 1 end, 0, T).
> xb5_trees:to_list(T2).
[{1, 10}, {2, 21}]
> T3 = xb5_trees:update_with(3, fun(V) -> V + 1 end, 0, T).
> xb5_trees:to_list(T3).
[{1, 10}, {2, 20}, {3, 0}]

values(Tree)

-spec values(Tree) -> [Value] when Tree :: tree(_, Value).

Returns the values in Tree as a list, ordered by their corresponding keys.

Examples

> T = xb5_trees:from_list([{3, c}, {1, a}, {2, b}]).
> xb5_trees:values(T).
[a, b, c]

wrap/1

-spec wrap(unwrapped_tree(Key, Value)) -> tree(Key, Value).

Wraps a plain map representation back into an opaque tree.

This is the inverse of unwrap/1 and is intended for cross-language interop (for example, converting from an Elixir struct that shares the same underlying node module).

Examples

> T = xb5_trees:from_list([{1, a}, {2, b}, {3, c}]).
> {ok, U} = xb5_trees:unwrap(T).
> T2 = xb5_trees:wrap(U).
> xb5_trees:to_list(T2).
[{1, a}, {2, b}, {3, c}]