# A.RBTree.Set (Aja v0.4.3) View Source

A low-level implementation of a Red-Black Tree Set, used under the hood in `A.RBSet`

.

Implementation following Chris Okasaki's "Purely Functional Data Structures", with the delete method as described in Deletion: The curse of the red-black tree from German and Might.

It should have equivalent performance as `:gb_sets`

from the Erlang standard library (see benchmarks).

## Disclaimer

This module is the low-level implementation behind other data structures, it is NOT meant to be used directly.

If you want something ready to use, you should check `A.RBSet`

.

## Examples

```
iex> A.RBTree.Set.new([])
:E
iex> set = A.RBTree.Set.new([2.0, 3, 2, 1, 3, 3])
{:B, {:R, :E, 1, :E}, 2, {:R, :E, 3, :E}}
iex> A.RBTree.Set.member?(set, 3)
true
iex> {:new, _new_set} = A.RBTree.Set.insert(set, 2.5)
{:new, {:B, {:B, {:R, :E, 1, :E}, 2, :E}, 2.5, {:B, :E, 3, :E}}}
iex> A.RBTree.Set.delete(set, 2)
{:B, {:R, :E, 1, :E}, 3, :E}
iex> A.RBTree.Set.delete(set, 4)
:error
iex> A.RBTree.Set.new([9, 8, 8, 7, 4, 1, 1, 2, 3, 3, 3, 9, 5, 6]) |> A.RBTree.Set.to_list()
[1, 2, 3, 4, 5, 6, 7, 8, 9]
```

## Note about numbers

Unlike regular maps, `A.RBTree.Set`

s only uses ordering for key comparisons,
meaning integers and floats are indistiguinshable as keys.

```
iex> MapSet.new([1, 2, 3]) |> MapSet.member?(2.0)
false
iex> A.RBTree.Set.new([1, 2, 3]) |> A.RBTree.Set.member?(2.0)
true
```

Erlang's `:gb_sets`

module works the same.

# Link to this section Summary

## Functions

Checks the red-black invariant is respected

Finds and removes the given `value`

if exists, and returns the new tree.

Folds (reduces) the given tree from the left with a function. Requires an accumulator.

Folds (reduces) the given tree from the right with a function. Requires an accumulator.

Inserts the value in a set tree and returns the updated tree.

Adds many values to an existing set tree, and returns both the new tree and the number of newly inserted values.

Returns an iterator looping on a tree from left-to-right.

Finds the leftmost (smallest) element of a tree

Checks the presence of a value in a set.

Finds the rightmost (largest) element of a tree

Initializes a set tree from an enumerable.

Walk a tree using an iterator yielded by `iterator/1`

.

Computes the "length" of the tree by looping and counting each node.

Finds and removes the rightmost (largest) element in a set tree.

Finds and removes the leftmost (smallest) element in a set tree.

Helper to implement `Enumerable.reduce/3`

in data structures using
the underlying tree.

Returns the tree as a list.

# Link to this section Types

# Link to this section Functions

## Specs

check_invariant(tree()) :: {:ok, non_neg_integer()} | {:error, String.t()}

Checks the red-black invariant is respected:

Each tree is either red or black. The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis. (All leaves (NIL) are black.) If a tree is red, then both its children are black. Every path from a given tree to any of its descendant NIL trees goes through the same number of black trees.

Returns either an `{:ok, black_height}`

tuple if respected and `black_height`

is consistent,
or an `{:error, reason}`

tuple if violated.

## Examples

```
iex> A.RBTree.Set.check_invariant(:E)
{:ok, 0}
iex> A.RBTree.Set.check_invariant({:B, :E, 1, :E})
{:ok, 1}
iex> A.RBTree.Set.check_invariant({:R, :E, 1, :E})
{:error, "No red root allowed"}
iex> A.RBTree.Set.check_invariant({:B, {:B, :E, 1, :E}, 2, :E})
{:error, "Inconsistent black length"}
iex> A.RBTree.Set.check_invariant({:B, {:R, {:R, :E, 1, :E}, 2, :E}, 3, :E})
{:error, "Red tree has red child"}
```

## Specs

Finds and removes the given `value`

if exists, and returns the new tree.

Uses the deletion algorithm as described in Deletion: The curse of the red-black tree.

## Examples

```
iex> tree = A.RBTree.Set.new([1, 2, 3, 4])
iex> A.RBTree.Set.delete(tree, 3)
{:B, {:B, :E, 1, :E}, 2, {:B, :E, 4, :E}}
iex> :error = A.RBTree.Set.delete(tree, 0)
:error
```

## Specs

empty() :: tree()

Folds (reduces) the given tree from the left with a function. Requires an accumulator.

## Examples

```
iex> A.RBTree.Set.new([22, 11, 33]) |> A.RBTree.Set.foldl(0, &+/2)
66
iex> A.RBTree.Set.new([22, 11, 33]) |> A.RBTree.Set.foldl([], &([2 * &1 | &2]))
[66, 44, 22]
```

Folds (reduces) the given tree from the right with a function. Requires an accumulator.

Unlike linked lists, this is as efficient as `foldl/3`

. This can typically save a call
to `Enum.reverse/1`

on the result when building a list.

## Examples

```
iex> A.RBTree.Set.new([22, 11, 33]) |> A.RBTree.Set.foldr(0, &+/2)
66
iex> A.RBTree.Set.new([22, 11, 33]) |> A.RBTree.Set.foldr([], &([2 * &1 | &2]))
[22, 44, 66]
```

## Specs

Inserts the value in a set tree and returns the updated tree.

Returns a `{:new, new_tree}`

tuple when the value was newly inserted.
Returns a `{:overwrite, new_tree}`

tuple when a non-striclty
equal value was already present.

Because `1.0`

and `1`

compare as equal values, inserting `1.0`

can
overwrite `1`

and `new_tree`

is going to be different.

## Examples

```
iex> tree = A.RBTree.Set.new([1, 3])
iex> A.RBTree.Set.insert(tree, 2)
{:new, {:B, {:B, :E, 1, :E}, 2, {:B, :E, 3, :E}}}
iex> A.RBTree.Set.insert(tree, 3.0)
{:overwrite, {:B, :E, 1, {:R, :E, 3.0, :E}}}
```

## Specs

insert_many(tree(el), Enumerable.t()) :: {non_neg_integer(), tree(el)} when el: element()

Adds many values to an existing set tree, and returns both the new tree and the number of newly inserted values.

Returns a `{inserted, new_tree}`

tuple when `inserted`

is the number of newly inserted
values. Overwriting existing values do not count. This is useful to keep track of size
changes.

## Examples

```
iex> tree = A.RBTree.Set.new([1, 2])
iex> A.RBTree.Set.insert_many(tree, [2, 2.0, 3, 3.0])
{1, {:B, {:B, :E, 1, :E}, 2.0, {:B, :E, 3.0, :E}}}
```

## Specs

iterator(tree(el)) :: iterator(el) when el: element()

iterator(iterator(el)) :: {el, iterator(el)} | nil when el: element()

Returns an iterator looping on a tree from left-to-right.

The resulting iterator should be looped over using `next/1`

.

## Examples

```
iex> iterator = A.RBTree.Set.new([22, 11]) |> A.RBTree.Set.iterator()
iex> {i1, iterator} = A.RBTree.Set.next(iterator)
iex> {i2, iterator} = A.RBTree.Set.next(iterator)
iex> A.RBTree.Set.next(iterator)
nil
iex> [i1, i2]
[11, 22]
```

## Specs

Finds the leftmost (smallest) element of a tree

## Examples

```
iex> A.RBTree.Set.new(["B", "D", "A", "C"]) |> A.RBTree.Set.max()
{:ok, "D"}
iex> A.RBTree.Set.new([]) |> A.RBTree.Set.max()
:error
```

## Specs

Checks the presence of a value in a set.

Like all `A.RBTree.Set`

functions, uses `==/2`

for comparison,
not strict equality `===/2`

.

## Examples

```
iex> tree = A.RBTree.Set.new([1, 2, 3])
iex> A.RBTree.Set.member?(tree, 2)
true
iex> A.RBTree.Set.member?(tree, 4)
false
iex> A.RBTree.Set.member?(tree, 2.0)
true
```

## Specs

Finds the rightmost (largest) element of a tree

## Examples

```
iex> A.RBTree.Set.new(["B", "D", "A", "C"]) |> A.RBTree.Set.min()
{:ok, "A"}
iex> A.RBTree.Set.new([]) |> A.RBTree.Set.min()
:error
```

## Specs

new(Enumerable.t()) :: tree()

Initializes a set tree from an enumerable.

## Examples

```
iex> A.RBTree.Set.new([3, 2, 1, 2, 3])
{:B, {:B, :E, 1, :E}, 2, {:B, :E, 3, :E}}
```

Walk a tree using an iterator yielded by `iterator/1`

.

## Examples

```
iex> iterator = A.RBTree.Set.new([22, 11]) |> A.RBTree.Set.iterator()
iex> {i1, iterator} = A.RBTree.Set.next(iterator)
iex> {i2, iterator} = A.RBTree.Set.next(iterator)
iex> A.RBTree.Set.next(iterator)
nil
iex> [i1, i2]
[11, 22]
```

## Specs

node_count(tree(el)) :: non_neg_integer() when el: element()

Computes the "length" of the tree by looping and counting each node.

## Examples

```
iex> tree = A.RBTree.Set.new([1, 2, 2.0, 3, 3.0, 3])
iex> A.RBTree.Set.node_count(tree)
3
iex> A.RBTree.Set.node_count(A.RBTree.Set.empty())
0
```

## Specs

Finds and removes the rightmost (largest) element in a set tree.

Returns both the element and the new tree.

## Examples

```
iex> tree = A.RBTree.Set.new([1, 2, 3, 4])
iex> {4, new_tree} = A.RBTree.Set.pop_max(tree)
iex> new_tree
{:B, {:B, :E, 1, :E}, 2, {:B, :E, 3, :E}}
iex> :error = A.RBTree.Set.pop_max(A.RBTree.Set.empty())
:error
```

## Specs

Finds and removes the leftmost (smallest) element in a set tree.

Returns both the element and the new tree.

## Examples

```
iex> tree = A.RBTree.Set.new([1, 2, 3, 4])
iex> {1, new_tree} = A.RBTree.Set.pop_min(tree)
iex> new_tree
{:B, {:R, :E, 2, :E}, 3, {:R, :E, 4, :E}}
iex> :error = A.RBTree.Set.pop_min(A.RBTree.Set.empty())
:error
```

Helper to implement `Enumerable.reduce/3`

in data structures using
the underlying tree.

## Specs

Returns the tree as a list.

## Examples

```
iex> A.RBTree.Set.new([3, 2, 2.0, 3, 3.0, 1, 3]) |> A.RBTree.Set.to_list()
[1, 2.0, 3]
iex> A.RBTree.Set.new([b: "B", c: "C", a: "A"]) |> A.RBTree.Set.to_list()
[{:a, "A"}, {:b, "B"}, {:c, "C"}]
iex> A.RBTree.Set.empty() |> A.RBTree.Set.to_list()
[]
```