# `Xb5.Tree`
[🔗](https://github.com/g-andrade/xb5_elixir/blob/1.0.0/lib/xb5/tree.ex#L1)

An ordered key-value store backed by a [B-tree](https://en.wikipedia.org/wiki/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}

# `key`

```elixir
@type key() :: term()
```

# `order`

```elixir
@type order() :: :asc | :desc
```

# `t`

```elixir
@type t() :: t(key(), value())
```

# `t`

```elixir
@type t(key, value) :: %Xb5.Tree{
  root: :xb5_trees_node.t(key, value),
  size: non_neg_integer()
}
```

# `value`

```elixir
@type value() :: term()
```

# `delete`

```elixir
@spec delete(t(), key()) :: t()
```

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])

# `drop`

```elixir
@spec drop(t(), [key()]) :: t()
```

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])

# `equal?`

```elixir
@spec equal?(t(), t()) :: boolean()
```

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]))
    false

# `fetch`

```elixir
@spec fetch(t(), key()) :: {:ok, value()} | :error
```

Fetches 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)
    :error

# `fetch!`

```elixir
@spec fetch!(t(), key()) :: value()
```

Fetches 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) end

# `filter`

```elixir
@spec filter(t(key(), value()), ({key(), value()} -> as_boolean(term()))) ::
  t(key(), value())
```

Returns 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])

# `first`

```elixir
@spec first(t(key(), value()), default) :: {key(), value()} | default
when default: term()
```

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)
    :empty

# `first!`

```elixir
@spec first!(t(key(), value())) :: {key(), value()}
```

Returns 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 error

# `from_keys`

```elixir
@spec from_keys(Enumerable.t(key()), value()) :: t(key(), value())
```

Builds 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])

# `get`

```elixir
@spec get(t(), key(), value()) :: value()
```

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

# `get_and_update`

```elixir
@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])}

# `get_and_update!`

```elixir
@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([])}

# `get_lazy`

```elixir
@spec get_lazy(t(), key(), (-> value())) :: value()
```

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)
    13

# `has_key?`

```elixir
@spec has_key?(t(), key()) :: boolean()
```

Returns 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)
    false

# `higher`

```elixir
@spec higher(t(key(), value()), key()) :: {key(), value()} | :error
```

Returns 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)
    :error

# `intersect`

```elixir
@spec intersect(t(), t()) :: t()
```

Intersects 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"])

# `intersect`

```elixir
@spec intersect(t(), t(), (key(), value(), value() -> value())) :: t()
```

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])

# `keys`

```elixir
@spec keys(t()) :: [key()]
```

Returns all keys from `tree` in ascending order.

## Examples

    iex> Xb5.Tree.keys(Xb5.Tree.new([a: 1, b: 2]))
    [:a, :b]

# `last`

```elixir
@spec last(t(key(), value()), default) :: {key(), value()} | default
when default: term()
```

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)
    :empty

# `last!`

```elixir
@spec last!(t(key(), value())) :: {key(), value()}
```

Returns 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 error

# `lower`

```elixir
@spec lower(t(key(), value()), key()) :: {key(), value()} | :error
```

Returns 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

# `map`

```elixir
@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])

# `merge`

```elixir
@spec merge(t(), t()) :: t()
```

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])

# `merge`

```elixir
@spec merge(t(), t(), (key(), value(), value() -> value())) :: t()
```

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])

# `new`

```elixir
@spec new() :: t()
```

Returns a new empty tree.

## Examples

    iex> Xb5.Tree.new()
    Xb5.Tree.new([])

# `new`

```elixir
@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])

# `new`

```elixir
@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])

# `pop`

```elixir
@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])}

# `pop!`

```elixir
@spec pop!(t(), key()) :: {value(), updated_map :: t()}
```

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

# `pop_first!`

```elixir
@spec pop_first!(t(key(), value())) :: {key(), value(), t(key(), value())}
```

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 error

# `pop_last!`

```elixir
@spec pop_last!(t(key(), value())) :: {key(), value(), t(key(), value())}
```

Removes 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 error

# `pop_lazy`

```elixir
@spec pop_lazy(t(), key(), (-> value())) :: {value(), t()}
```

Lazily 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])}

# `put`

```elixir
@spec put(t(), key(), value()) :: t()
```

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])

# `put_new`

```elixir
@spec put_new(t(), key(), value()) :: t()
```

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])

# `put_new_lazy`

```elixir
@spec put_new_lazy(t(), key(), (-> value())) :: t()
```

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])

# `reject`

```elixir
@spec reject(t(key(), value()), ({key(), value()} -> as_boolean(term()))) ::
  t(key(), value())
```

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])

# `replace`

```elixir
@spec replace(t(), key(), value()) :: t()
```

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])

# `replace!`

```elixir
@spec replace!(t(), key(), value()) :: t()
```

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

# `replace_lazy`

```elixir
@spec replace_lazy(t(), key(), (existing_value :: value() -> new_value :: value())) ::
  t()
```

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])

# `size`

```elixir
@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]))
    3

# `split`

```elixir
@spec split(t(), [key()]) :: {t(), t()}
```

Takes 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])}

# `split_with`

```elixir
@spec split_with(t(), ({key(), value()} -> as_boolean(term()))) :: {t(), t()}
```

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

# `stream`

```elixir
@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()
    []

# `stream_from`

```elixir
@spec stream_from(t(key(), value()), key(), order()) :: Enumerable.t()
```

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

# `structural_stats`

```elixir
@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
    ]

# `take`

```elixir
@spec take(t(), [key()]) :: t()
```

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])

# `to_list`

```elixir
@spec to_list(t(key(), value())) :: [value()]
```

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"}]

# `unwrap!`

```elixir
@spec unwrap!(t(key(), value())) :: :xb5_trees.unwrapped_tree(key(), value())
```

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

# `update`

```elixir
@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])

# `update!`

```elixir
@spec update!(t(), key(), (existing_value :: value() -> new_value :: value())) :: t()
```

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

# `values`

```elixir
@spec values(t()) :: [value()]
```

Returns all values from `tree` in ascending key order.

## Examples

    iex> Xb5.Tree.values(Xb5.Tree.new([a: 1, b: 2]))
    [1, 2]

---

*Consult [api-reference.md](api-reference.md) for complete listing*