An ordered key-value store backed by a B-tree of order 5.
Keys are kept in ascending Erlang term order. Comparisons use == rather than === —
so key 1 and key 1.0 are treated as the same key, unlike Map.
Erlang interop
Xb5.Tree is compatible with the Erlang :xb5_trees module. Build one from an
:xb5_trees term via new/1. To go the other way, call unwrap!/1 to extract the
size and root node, then pass the result to :xb5_trees.wrap/1.
See also
Xb5.Bag— ordered multiset with order-statistic operations (percentile, rank)Xb5.Set— ordered set, for unique elements and set-algebraic operations.
Examples
iex> tree = Xb5.Tree.new([b: 2, a: 1])
Xb5.Tree.new([a: 1, b: 2])
iex> Xb5.Tree.get(tree, :a)
1
iex> Xb5.Tree.last!(tree)
{:b, 2}Summary
Functions
Deletes the entry in tree for a specific key.
Drops the given keys from tree.
Checks if two trees are equal.
Fetches the value for a specific key in the given tree.
Fetches the value for a specific key in the given tree, erroring out if tree
doesn't contain key.
Returns a new tree containing only entries from tree for which fun returns a truthy value.
Returns the first (smallest-key) entry in tree as {key, value}, or default if empty.
Returns the first (smallest-key) entry in tree as {key, value}.
Builds a tree from the given keys and the fixed value.
Gets the value for a specific key in tree.
Gets the value from key and updates it, all in one pass.
Gets the value from key and updates it, all in one pass. Raises if there is no key.
Gets the value for a specific key in tree.
Returns whether the given key exists in the given tree.
Returns the entry with the smallest key strictly greater (larger) than key,
or :error if none exists.
Intersects two trees, returning a tree with the common keys.
Intersects two trees, returning a tree with the common keys and resolving conflicts through a function.
Returns all keys from tree in ascending order.
Returns the last (largest-key) entry in tree as {key, value}, or default if empty.
Returns the last (largest-key) entry in tree as {key, value}.
Returns the entry with the largest key strictly less (smaller) than key, or
:error if none exists.
Returns a new tree with all values replaced according to fun.
Merges two trees into one.
Merges two trees into one, resolving conflicts through the given fun.
Returns a new empty tree.
Creates a tree from an Erlang :xb5_trees term or an enumerable of {key, value} pairs.
Creates a tree from an Erlang :xb5_trees term or an enumerable via the transformation
function.
Removes the value associated with key in tree and returns the value and the updated tree.
Removes and returns the value associated with key in tree alongside the updated tree,
or raises if key is not present.
Removes and returns {key, value, updated_tree} for the entry with the first (smallest) key.
Removes and returns {key, value, updated_tree} for the entry with the last (largest) key.
Lazily returns and removes the value associated with key in tree.
Puts the given value under key in tree.
Puts the given value under key unless the entry key already exists in tree.
Evaluates fun and puts the result under key in tree unless key is already present.
Returns a new tree excluding the entries from tree for which fun returns a truthy value.
Puts a value under key only if key already exists in tree.
Puts a value under key only if key already exists in tree.
Replaces the value under key using the given function only if key already exists
in tree.
Returns the number of entries in tree.
Takes all entries corresponding to the given keys in tree and extracts them into a
separate tree.
Splits tree into two trees according to the given function fun.
Returns a lazy stream over all entries of tree as {key, value} pairs.
Returns a lazy stream over entries of tree starting from key, yielding
{key, value} pairs.
Returns structural statistics about the underlying B-tree.
Returns a new tree with all the key-value pairs in tree where the key is in keys.
Converts tree to a list.
Returns the size and root node of tree as %{size: n, root: node}.
Updates the key in tree with the given function.
Updates key with the given function.
Returns all values from tree in ascending key order.
Types
@type key() :: term()
@type order() :: :asc | :desc
@type t(key, value) :: %Xb5.Tree{ root: :xb5_trees_node.t(key, value), size: non_neg_integer() }
@type value() :: term()
Functions
Deletes the entry in tree for a specific key.
If key does not exist, returns tree unchanged.
Examples
iex> Xb5.Tree.delete(Xb5.Tree.new([a: 1, b: 2]), :a)
Xb5.Tree.new([b: 2])
iex> Xb5.Tree.delete(Xb5.Tree.new([b: 2]), :a)
Xb5.Tree.new([b: 2])Drops the given keys from tree.
If keys contains keys that are not in tree, they're simply ignored.
Examples
iex> Xb5.Tree.drop(Xb5.Tree.new([a: 1, b: 2, c: 3]), [:b, :d])
Xb5.Tree.new([a: 1, c: 3])Checks if two trees are equal.
Two trees are considered equal if they contain the same keys and those keys contain
the same values. Keys are compared using ==, so key 1 and key 1.0 are treated
as identical. Values are compared using ===, so a value of 1 does not equal 1.0.
Examples
iex> Xb5.Tree.equal?(Xb5.Tree.new([a: 1, b: 2]), Xb5.Tree.new([b: 2, a: 1]))
true
iex> Xb5.Tree.equal?(Xb5.Tree.new([a: 1, b: 2]), Xb5.Tree.new([b: 1, a: 2]))
false
iex> Xb5.Tree.equal?(Xb5.Tree.new([{1, :x}]), Xb5.Tree.new([{1.0, :x}]))
true
iex> Xb5.Tree.equal?(Xb5.Tree.new([a: 1.0]), Xb5.Tree.new([a: 1]))
falseFetches the value for a specific key in the given tree.
If tree contains the given key then its value is returned in the shape of {:ok, value}.
If tree doesn't contain key, :error is returned.
Examples
iex> Xb5.Tree.fetch(Xb5.Tree.new([a: 1]), :a)
{:ok, 1}
iex> Xb5.Tree.fetch(Xb5.Tree.new([a: 1]), :b)
:errorFetches the value for a specific key in the given tree, erroring out if tree
doesn't contain key.
If tree contains key, the corresponding value is returned. If tree doesn't
contain key, a KeyError exception is raised.
Examples
iex> Xb5.Tree.fetch!(Xb5.Tree.new([a: 1]), :a)
1
iex> assert_raise KeyError, fn -> Xb5.Tree.fetch!(Xb5.Tree.new([a: 1]), :b) endReturns a new tree containing only entries from tree for which fun returns a truthy value.
fun receives each {key, value} pair as its only argument.
See also reject/2 which discards all entries where the function returns a truthy value.
Examples
iex> Xb5.Tree.filter(Xb5.Tree.new([one: 1, two: 2, three: 3]), fn {_key, val} -> rem(val, 2) == 1 end)
Xb5.Tree.new([one: 1, three: 3])Returns the first (smallest-key) entry in tree as {key, value}, or default if empty.
Examples
iex> Xb5.Tree.first(Xb5.Tree.new([a: 1, b: 2, c: 3]))
{:a, 1}
iex> Xb5.Tree.first(Xb5.Tree.new())
nil
iex> Xb5.Tree.first(Xb5.Tree.new(), :empty)
:emptyReturns the first (smallest-key) entry in tree as {key, value}.
Raises Xb5.EmptyError if tree is empty.
Examples
iex> Xb5.Tree.first!(Xb5.Tree.new([a: 1, b: 2, c: 3]))
{:a, 1}
iex> Xb5.Tree.first!(Xb5.Tree.new())
** (Xb5.EmptyError) empty errorBuilds a tree from the given keys and the fixed value.
Examples
iex> Xb5.Tree.from_keys([:a, :b, :c], 0)
Xb5.Tree.new([a: 0, b: 0, c: 0])Gets the value for a specific key in tree.
If key is present in tree then its value is returned. Otherwise, default is returned.
If default is not provided, nil is used.
Examples
iex> Xb5.Tree.get(Xb5.Tree.new(), :a)
nil
iex> Xb5.Tree.get(Xb5.Tree.new([a: 1]), :a)
1
iex> Xb5.Tree.get(Xb5.Tree.new([a: 1]), :b)
nil
iex> Xb5.Tree.get(Xb5.Tree.new([a: 1]), :b, 3)
3
iex> Xb5.Tree.get(Xb5.Tree.new([a: nil]), :a, 1)
nil@spec get_and_update( t(), key(), (value() | nil -> {current_value, new_value :: value()} | :pop) ) :: {current_value, new_tree :: t()} when current_value: value()
Gets the value from key and updates it, all in one pass.
fun is called with the current value under key in tree (or nil if key is not
present in tree) and must return a two-element tuple: the current value (the retrieved
value, which can be operated on before being returned) and the new value to be stored
under key in the resulting new tree. fun may also return :pop, which means the
current value shall be removed from tree and returned.
The returned value is a two-element tuple with the current value returned by fun and a
new tree with the updated value under key.
Examples
iex> Xb5.Tree.get_and_update(Xb5.Tree.new([a: 1]), :a, fn current_value ->
...> {current_value, "new value!"}
...> end)
{1, Xb5.Tree.new([a: "new value!"])}
iex> Xb5.Tree.get_and_update(Xb5.Tree.new([a: 1]), :b, fn current_value ->
...> {current_value, "new value!"}
...> end)
{nil, Xb5.Tree.new([a: 1, b: "new value!"])}
iex> Xb5.Tree.get_and_update(Xb5.Tree.new([a: 1]), :a, fn _ -> :pop end)
{1, Xb5.Tree.new([])}
iex> Xb5.Tree.get_and_update(Xb5.Tree.new([a: 1]), :b, fn _ -> :pop end)
{nil, Xb5.Tree.new([a: 1])}@spec get_and_update!( t(), key(), (value() -> {current_value, new_value :: value()} | :pop) ) :: {current_value, t()} when current_value: value()
Gets the value from key and updates it, all in one pass. Raises if there is no key.
Behaves exactly like get_and_update/3, but raises a KeyError exception if key is
not present in tree.
Examples
iex> Xb5.Tree.get_and_update!(Xb5.Tree.new([a: 1]), :a, fn current_value ->
...> {current_value, "new value!"}
...> end)
{1, Xb5.Tree.new([a: "new value!"])}
iex> assert_raise KeyError, fn -> Xb5.Tree.get_and_update!(Xb5.Tree.new([a: 1]), :b, fn current_value ->
...> {current_value, "new value!"}
...> end) end
iex> Xb5.Tree.get_and_update!(Xb5.Tree.new([a: 1]), :a, fn _ ->
...> :pop
...> end)
{1, Xb5.Tree.new([])}Gets the value for a specific key in tree.
If key is present in tree then its value is returned. Otherwise, fun is evaluated
and its result is returned.
This is useful if the default value is very expensive to calculate or generally difficult to setup and teardown again.
Examples
iex> tree = Xb5.Tree.new([a: 1])
iex> fun = fn ->
...> # some expensive operation here
...> 13
...> end
iex> Xb5.Tree.get_lazy(tree, :a, fun)
1
iex> Xb5.Tree.get_lazy(tree, :b, fun)
13Returns whether the given key exists in the given tree.
Examples
iex> Xb5.Tree.has_key?(Xb5.Tree.new([a: 1]), :a)
true
iex> Xb5.Tree.has_key?(Xb5.Tree.new([a: 1]), :b)
falseReturns the entry with the smallest key strictly greater (larger) than key,
or :error if none exists.
key does not need to exist in tree.
Examples
iex> Xb5.Tree.higher(Xb5.Tree.new([a: 1, b: 2, c: 3]), :b)
{:c, 3}
iex> Xb5.Tree.higher(Xb5.Tree.new([a: 1, c: 2]), :b)
{:c, 2}
iex> Xb5.Tree.higher(Xb5.Tree.new([a: 1, b: 2, c: 3]), :c)
:errorIntersects two trees, returning a tree with the common keys.
The values in the returned tree are the values of the intersected keys in tree2.
Examples
iex> Xb5.Tree.intersect(Xb5.Tree.new([a: 1, b: 2]), Xb5.Tree.new([b: "b", c: "c"]))
Xb5.Tree.new([b: "b"])Intersects two trees, returning a tree with the common keys and resolving conflicts through a function.
The given function will be invoked when there are duplicate keys; its arguments are key
(the duplicate key), value1 (the value of key in tree1), and value2 (the value of
key in tree2). The value returned by fun is used as the value under key in the
resulting tree.
Examples
iex> Xb5.Tree.intersect(Xb5.Tree.new([a: 1, b: 2]), Xb5.Tree.new([b: 2, c: 3]), fn _k, v1, v2 ->
...> v1 + v2
...> end)
Xb5.Tree.new([b: 4])Returns all keys from tree in ascending order.
Examples
iex> Xb5.Tree.keys(Xb5.Tree.new([a: 1, b: 2]))
[:a, :b]Returns the last (largest-key) entry in tree as {key, value}, or default if empty.
Examples
iex> Xb5.Tree.last(Xb5.Tree.new([a: 1, b: 2, c: 3]))
{:c, 3}
iex> Xb5.Tree.last(Xb5.Tree.new())
nil
iex> Xb5.Tree.last(Xb5.Tree.new(), :empty)
:emptyReturns the last (largest-key) entry in tree as {key, value}.
Raises Xb5.EmptyError if tree is empty.
Examples
iex> Xb5.Tree.last!(Xb5.Tree.new([a: 1, b: 2, c: 3]))
{:c, 3}
iex> Xb5.Tree.last!(Xb5.Tree.new())
** (Xb5.EmptyError) empty errorReturns the entry with the largest key strictly less (smaller) than key, or
:error if none exists.
key does not need to exist in tree.
Examples
iex> Xb5.Tree.lower(Xb5.Tree.new([a: 1, b: 2, c: 3]), :b)
{:a, 1}
iex> Xb5.Tree.lower(Xb5.Tree.new([a: 1, c: 2]), :b)
{:a, 1}
iex> Xb5.Tree.lower(Xb5.Tree.new([a: 1, b: 2, c: 3]), :a)
:error@spec map(t(key(), value()), (key(), value() -> new_value)) :: t(key(), new_value) when new_value: value()
Returns a new tree with all values replaced according to fun.
fun receives the key and value of each entry and must return the new value.
Examples
iex> Xb5.Tree.map(Xb5.Tree.new([a: 1, b: 2]), fn _k, v -> v * 2 end)
Xb5.Tree.new([a: 2, b: 4])Merges two trees into one.
All keys in tree2 will be added to tree1, overriding any existing value
(i.e. the keys in tree2 have precedence over the ones in tree1).
Examples
iex> Xb5.Tree.merge(Xb5.Tree.new([a: 1, b: 2]), Xb5.Tree.new([a: 3, d: 4]))
Xb5.Tree.new([a: 3, b: 2, d: 4])Merges two trees into one, resolving conflicts through the given fun.
All keys in tree2 will be added to tree1. The given function will be invoked when
there are duplicate keys; its arguments are key (the duplicate key), value1 (the
value of key in tree1), and value2 (the value of key in tree2). The value
returned by fun is used as the value under key in the resulting tree.
Examples
iex> Xb5.Tree.merge(Xb5.Tree.new([a: 1, b: 2]), Xb5.Tree.new([a: 3, d: 4]), fn _k, v1, v2 ->
...> v1 + v2
...> end)
Xb5.Tree.new([a: 4, b: 2, d: 4])@spec new() :: t()
Returns a new empty tree.
Examples
iex> Xb5.Tree.new()
Xb5.Tree.new([])@spec new(:xb5_trees.tree(key(), value()) | Enumerable.t()) :: t(key(), value())
Creates a tree from an Erlang :xb5_trees term or an enumerable of {key, value} pairs.
Duplicated keys are removed; the latest one prevails. When given an Erlang :xb5_trees
term, the underlying structure is reused directly.
Examples
iex> Xb5.Tree.new([{:b, 1}, {:a, 2}])
Xb5.Tree.new([a: 2, b: 1])
iex> Xb5.Tree.new(a: 1, a: 2, a: 3)
Xb5.Tree.new([a: 3])@spec new(:xb5_trees.tree() | Enumerable.t(), (term() -> value())) :: t(key(), value())
Creates a tree from an Erlang :xb5_trees term or an enumerable via the transformation
function.
transform receives each element and must return a {key, value} pair. Duplicated keys
are removed; the latest one prevails.
Examples
iex> Xb5.Tree.new([:a, :b], fn x -> {x, x} end)
Xb5.Tree.new([a: :a, b: :b])@spec pop(t(), key(), default) :: {value(), updated_map :: t()} | {default, t()} when default: value()
Removes the value associated with key in tree and returns the value and the updated tree.
If key is present in tree, it returns {value, updated_tree} where value is the value
of the key and updated_tree is the result of removing key from tree. If key is not
present in tree, {default, tree} is returned.
Examples
iex> Xb5.Tree.pop(Xb5.Tree.new([a: 1]), :a)
{1, Xb5.Tree.new([])}
iex> Xb5.Tree.pop(Xb5.Tree.new([a: 1]), :b)
{nil, Xb5.Tree.new([a: 1])}
iex> Xb5.Tree.pop(Xb5.Tree.new([a: 1]), :b, 3)
{3, Xb5.Tree.new([a: 1])}Removes and returns the value associated with key in tree alongside the updated tree,
or raises if key is not present.
Behaves the same as pop/3 but raises a KeyError exception if key is not present
in tree.
Examples
iex> Xb5.Tree.pop!(Xb5.Tree.new([a: 1]), :a)
{1, Xb5.Tree.new([])}
iex> Xb5.Tree.pop!(Xb5.Tree.new([a: 1, b: 2]), :a)
{1, Xb5.Tree.new([b: 2])}
iex> Xb5.Tree.pop!(Xb5.Tree.new([a: 1]), :b)
** (KeyError) key :b not found in:
...Removes and returns {key, value, updated_tree} for the entry with the first (smallest) key.
Raises Xb5.EmptyError if tree is empty.
Examples
iex> Xb5.Tree.pop_first!(Xb5.Tree.new([a: 1, b: 2, c: 3]))
{:a, 1, Xb5.Tree.new([b: 2, c: 3])}
iex> Xb5.Tree.pop_first!(Xb5.Tree.new())
** (Xb5.EmptyError) empty errorRemoves and returns {key, value, updated_tree} for the entry with the last (largest) key.
Raises Xb5.EmptyError if tree is empty.
Examples
iex> Xb5.Tree.pop_last!(Xb5.Tree.new([a: 1, b: 2, c: 3]))
{:c, 3, Xb5.Tree.new([a: 1, b: 2])}
iex> Xb5.Tree.pop_last!(Xb5.Tree.new())
** (Xb5.EmptyError) empty errorLazily returns and removes the value associated with key in tree.
If key is present in tree, it returns {value, updated_tree} where value is the
value of the key and updated_tree is the result of removing key from tree. If key
is not present in tree, {fun_result, tree} is returned, where fun_result is the
result of applying fun.
This is useful if the default value is very expensive to calculate or generally difficult to setup and teardown again.
Examples
iex> tree = Xb5.Tree.new([a: 1])
iex> fun = fn ->
...> # some expensive operation here
...> 13
...> end
iex> Xb5.Tree.pop_lazy(tree, :a, fun)
{1, Xb5.Tree.new([])}
iex> Xb5.Tree.pop_lazy(tree, :b, fun)
{13, Xb5.Tree.new([a: 1])}Puts the given value under key in tree.
If key already exists, its value is replaced.
Examples
iex> Xb5.Tree.put(Xb5.Tree.new([a: 1]), :b, 2)
Xb5.Tree.new([a: 1, b: 2])
iex> Xb5.Tree.put(Xb5.Tree.new([a: 1, b: 2]), :a, 3)
Xb5.Tree.new([a: 3, b: 2])Puts the given value under key unless the entry key already exists in tree.
Examples
iex> Xb5.Tree.put_new(Xb5.Tree.new([a: 1]), :b, 2)
Xb5.Tree.new([a: 1, b: 2])
iex> Xb5.Tree.put_new(Xb5.Tree.new([a: 1, b: 2]), :a, 3)
Xb5.Tree.new([a: 1, b: 2])Evaluates fun and puts the result under key in tree unless key is already present.
This is useful when the value to put under key is expensive to calculate or generally
difficult to setup and teardown again.
Examples
iex> tree = Xb5.Tree.new([a: 1])
iex> fun = fn ->
...> # some expensive operation here
...> 3
...> end
iex> Xb5.Tree.put_new_lazy(tree, :a, fun)
Xb5.Tree.new([a: 1])
iex> Xb5.Tree.put_new_lazy(tree, :b, fun)
Xb5.Tree.new([a: 1, b: 3])Returns a new tree excluding the entries from tree for which fun returns a truthy value.
See also filter/2.
Examples
iex> Xb5.Tree.reject(Xb5.Tree.new([one: 1, two: 2, three: 3]), fn {_key, val} -> rem(val, 2) == 1 end)
Xb5.Tree.new([two: 2])Puts a value under key only if key already exists in tree.
If key is not present in tree, the tree is returned unchanged.
Examples
iex> Xb5.Tree.replace(Xb5.Tree.new([a: 1, b: 2]), :a, 3)
Xb5.Tree.new([a: 3, b: 2])
iex> Xb5.Tree.replace(Xb5.Tree.new([a: 1]), :b, 2)
Xb5.Tree.new([a: 1])Puts a value under key only if key already exists in tree.
If key is not present in tree, a KeyError exception is raised.
Examples
iex> Xb5.Tree.replace!(Xb5.Tree.new([a: 1, b: 2]), :a, 3)
Xb5.Tree.new([a: 3, b: 2])
iex> Xb5.Tree.replace!(Xb5.Tree.new([a: 1]), :b, 2)
** (KeyError) key :b not found in:
...Replaces the value under key using the given function only if key already exists
in tree.
In comparison to replace/3, this can be useful when it's expensive to calculate the value.
If key does not exist, the original tree is returned unchanged.
Examples
iex> Xb5.Tree.replace_lazy(Xb5.Tree.new([a: 1, b: 2]), :a, fn v -> v * 4 end)
Xb5.Tree.new([a: 4, b: 2])
iex> Xb5.Tree.replace_lazy(Xb5.Tree.new([a: 1, b: 2]), :c, fn v -> v * 4 end)
Xb5.Tree.new([a: 1, b: 2])@spec size(t()) :: non_neg_integer()
Returns the number of entries in tree.
Examples
iex> Xb5.Tree.size(Xb5.Tree.new([a: 1, b: 2, c: 3]))
3Takes all entries corresponding to the given keys in tree and extracts them into a
separate tree.
Returns a tuple with the new tree and the old tree with removed keys.
Keys for which there are no entries in tree are ignored.
Examples
iex> Xb5.Tree.split(Xb5.Tree.new([a: 1, b: 2, c: 3]), [:a, :c, :e])
{Xb5.Tree.new([a: 1, c: 3]), Xb5.Tree.new([b: 2])}Splits tree into two trees according to the given function fun.
fun receives each {key, value} pair in tree as its only argument. Returns a tuple
with the first tree containing all the entries for which fun returned a truthy value,
and a second tree with all the entries for which fun returned a falsy value (false
or nil).
Examples
iex> {while_true, while_false} = Xb5.Tree.split_with(Xb5.Tree.new([a: 1, b: 2, c: 3, d: 4]), fn {_k, v} -> rem(v, 2) == 0 end)
iex> while_true
Xb5.Tree.new([b: 2, d: 4])
iex> while_false
Xb5.Tree.new([a: 1, c: 3])
iex> {while_true, while_false} = Xb5.Tree.split_with(Xb5.Tree.new(), fn {_k, v} -> v > 50 end)
iex> while_true
Xb5.Tree.new([])
iex> while_false
Xb5.Tree.new([])@spec stream(t(key(), value()), order()) :: Enumerable.t()
Returns a lazy stream over all entries of tree as {key, value} pairs.
order controls traversal direction: :asc (ascending by key, the
default) or :desc (descending by key).
Examples
iex> tree = Xb5.Tree.new([{1, :a}, {2, :b}, {3, :c}])
iex> Xb5.Tree.stream(tree) |> Enum.to_list()
[{1, :a}, {2, :b}, {3, :c}]
iex> Xb5.Tree.stream(tree, :desc) |> Enum.to_list()
[{3, :c}, {2, :b}, {1, :a}]
iex> Xb5.Tree.stream(Xb5.Tree.new()) |> Enum.to_list()
[]Returns a lazy stream over entries of tree starting from key, yielding
{key, value} pairs.
For :asc (the default), starts at the first key greater than or equal
to key. For :desc, starts at the first key less than or equal to
key. Returns an empty stream if no such key exists.
Examples
iex> tree = Xb5.Tree.new([{1, :a}, {2, :b}, {3, :c}, {4, :d}, {5, :e}])
iex> Xb5.Tree.stream_from(tree, 3) |> Enum.to_list()
[{3, :c}, {4, :d}, {5, :e}]
iex> Xb5.Tree.stream_from(tree, 3, :desc) |> Enum.to_list()
[{3, :c}, {2, :b}, {1, :a}]
iex> Xb5.Tree.stream_from(tree, 6) |> Enum.to_list()
[]@spec structural_stats(t()) :: :xb5_structural_stats.t()
Returns structural statistics about the underlying B-tree.
Useful for inspecting tree balance and node utilization.
Examples
iex> Xb5.Tree.structural_stats(Xb5.Tree.new(Enum.map(1..100, &{&1, &1})))
[
height: 4,
node_counts: [
internal4: 2,
internal3: 3,
internal2: 3,
internal1: 1,
leaf4: 6,
leaf3: 14,
leaf2: 5,
leaf1: 0
],
node_percentages: [
internal4: 5.9,
internal3: 8.8,
internal2: 8.8,
internal1: 2.9,
leaf4: 17.6,
leaf3: 41.2,
leaf2: 14.7,
leaf1: 0.0
],
total_keys: 100,
key_percentages: [
internal4: 8.0,
internal3: 9.0,
internal2: 6.0,
internal1: 1.0,
leaf4: 24.0,
leaf3: 42.0,
leaf2: 10.0,
leaf1: 0.0
],
avg_keys_per_node: 2.9411764705882355,
avg_keys_per_internal_node: 2.6666666666666665,
avg_keys_per_leaf_node: 3.04
]Returns a new tree with all the key-value pairs in tree where the key is in keys.
If keys contains keys that are not in tree, they're simply ignored.
Examples
iex> Xb5.Tree.take(Xb5.Tree.new([a: 1, b: 2, c: 3]), [:a, :c, :e])
Xb5.Tree.new([a: 1, c: 3])Converts tree to a list.
Each key-value pair in the tree is converted to a two-element tuple {key, value} in the
resulting list. Entries are returned in ascending key order.
Examples
iex> Xb5.Tree.to_list(Xb5.Tree.new([a: 1, b: 2]))
[a: 1, b: 2]
iex> Xb5.Tree.to_list(Xb5.Tree.new([{1, "one"}, {2, "two"}]))
[{1, "one"}, {2, "two"}]Returns the size and root node of tree as %{size: n, root: node}.
Pass the result to :xb5_trees.wrap/1 to obtain a proper :xb5_trees term.
Examples
iex> %{size: size} = Xb5.Tree.unwrap!(Xb5.Tree.new([a: 1, b: 2, c: 3]))
iex> size
3@spec update( t(), key(), default :: value(), (existing_value :: value() -> new_value :: value()) ) :: t()
Updates the key in tree with the given function.
If key is present in tree then the existing value is passed to fun and its result
is used as the updated value of key. If key is not present in tree, default is
inserted as the value of key. The default value will not be passed through the update
function.
Examples
iex> Xb5.Tree.update(Xb5.Tree.new([a: 1]), :a, 13, fn existing_value -> existing_value * 2 end)
Xb5.Tree.new([a: 2])
iex> Xb5.Tree.update(Xb5.Tree.new([a: 1]), :b, 11, fn existing_value -> existing_value * 2 end)
Xb5.Tree.new([a: 1, b: 11])Updates key with the given function.
If key is present in tree then the existing value is passed to fun and its result
is used as the updated value of key. If key is not present in tree, a KeyError
exception is raised.
Examples
iex> Xb5.Tree.update!(Xb5.Tree.new([a: 1]), :a, &(&1 * 2))
Xb5.Tree.new([a: 2])
iex> Xb5.Tree.update!(Xb5.Tree.new([a: 1]), :b, &(&1 * 2))
** (KeyError) key :b not found in:
...Returns all values from tree in ascending key order.
Examples
iex> Xb5.Tree.values(Xb5.Tree.new([a: 1, b: 2]))
[1, 2]