A.RBTree.Map (Aja v0.4.3) View Source

A low-level implementation of a Red-Black Tree Map, used under the hood in A.RBMap and A.OrdMap.

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_trees 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.RBMap.

Probably the only case you might be interested in A.RBTree.Map itself is if you want to implement your own data structures on the top of it, or out of curiosity.

Examples

iex> A.RBTree.Map.new([])
:E
iex> map = A.RBTree.Map.new([b: "B", c: "C", a: "A"])
{:B, {:R, :E, :a, "A", :E}, :b, "B", {:R, :E, :c, "C", :E}}
iex> A.RBTree.Map.fetch(map, :c)
{:ok, "C"}
iex> {:new, _new_map} = A.RBTree.Map.insert(map, :bar, "BAR")
{:new, {:B, {:B, {:R, :E, :a, "A", :E}, :b, "B", :E}, :bar, "BAR", {:B, :E, :c, "C", :E}}}
iex> {"B", _new_map} = A.RBTree.Map.pop(map, :b)
{"B", {:B, {:R, :E, :a, "A", :E}, :c, "C", :E}}
iex> A.RBTree.Map.pop(map, :bar)
:error
iex> A.RBTree.Map.new([b: "B", x: "X", c: "C", a: "A"]) |> A.RBTree.Map.to_list()
[a: "A", b: "B", c: "C", x: "X"]

For the curious reader: more about deletion

Insertion is easy enough in an immutable Red-Black Tree, deletion however is pretty tricky. Two implementations have been tried:

this approach from Matt Might
Deletion: The curse of the red-black tree from Germane and Might

1. The Haskell implementation used as a reference has a bug and seems not to be respecting the Red-Black invariant, as suggested here.

2. was retained and it was confirmed that the Red-Black invariant was maintained.

Finally, a third approach from Kahr's (example Haskell implementation) seems to be faster and might be tried in future iterations.

Note about numbers

Unlike regular maps, A.RBTree.Maps only uses ordering for key comparisons, meaning integers and floats are indistiguinshable as keys.

iex> %{1 => "一", 2 => "二"} |> Map.fetch(2)
{:ok, "二"}
iex> %{1 => "一", 2 => "二"} |> Map.fetch(2.0)
:error
iex> A.RBTree.Map.new(%{1 => "一", 2 => "二"}) |> A.RBTree.Map.fetch(2)
{:ok, "二"}
iex> A.RBTree.Map.new(%{1 => "一", 2 => "二"}) |> A.RBTree.Map.fetch(2.0)
{:ok, "二"}

Erlang's :gb_trees module works the same.

Link to this section Summary

Types

color()

iterator(key, value)

key()

tree()

tree(key, value)

value()

Functions

black_height(arg1)

check_invariant(root)

Checks the red-black invariant is respected

empty()

fetch(arg1, key)

Finds the value corresponding to the given key if exists.

foldl(tree, acc, fun)

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

foldr(tree, acc, fun)

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

height(arg1)

insert(root, key, value)

Inserts the key-value pair in a map tree and returns the updated tree.

insert_many(tree, list)

Adds many key-values to an existing map tree, and returns both the new tree and the number of new entries created.

iterator(root)

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

max(arg1)

Finds the leftmost (smallest) element of a tree

min(arg1)

Finds the rightmost (largest) element of a tree

new(list)

Initializes a map tree from an enumerable.

next(list)

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

node_count(root)

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

pop(tree, key)

Finds and removes the value corresponding for the given key if exists in a map tree, and returns both that value and the new tree.

pop_max(tree)

Finds and removes the rightmost (largest) key in a map tree.

pop_min(tree)

Finds and removes the leftmost (smallest) key in a map tree.

reduce(tree, acc, fun)

Helper to implement Enumerable.reduce/3 in data structures using the underlying tree.

to_list(root)

Returns the tree as a list.

Link to this section Types

color()

Specs

color() :: :R | :B

iterator(key, value)

Specs

iterator(key, value) :: [tree(key, value)]

key()

Specs

key() :: term()

tree()

Specs

tree() :: tree(key(), value())

tree(key, value)

Specs

tree(key, value) ::
  :E | {color(), tree(key, value), key, value, tree(key, value)}

value()

Specs

value() :: term()

Link to this section Functions

black_height(arg1)

check_invariant(root)

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.Map.check_invariant(:E)
{:ok, 0}
iex> A.RBTree.Map.check_invariant({:B, :E, 1, nil, :E})
{:ok, 1}
iex> A.RBTree.Map.check_invariant({:R, :E, 1, nil, :E})
{:error, "No red root allowed"}
iex> A.RBTree.Map.check_invariant({:B, {:B, :E, 1, nil, :E}, 2, nil, :E})
{:error, "Inconsistent black length"}
iex> A.RBTree.Map.check_invariant({:B, {:R, {:R, :E, 1, nil, :E}, 2, nil, :E}, 3, nil, :E})
{:error, "Red tree has red child"}

empty()

Specs

empty() :: tree()

fetch(arg1, key)

Specs

fetch(tree(k, v), k) :: v when k: key(), v: value()

Finds the value corresponding to the given key if exists.

Examples

iex> tree = A.RBTree.Map.new(%{a: "A", b: "B", c: "C"})
iex> A.RBTree.Map.fetch(tree, :b)
{:ok, "B"}
iex> A.RBTree.Map.fetch(tree, :d)
:error

foldl(tree, acc, fun)

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

Examples

iex> tree = A.RBTree.Map.new(%{22 => "22", 11 => "11", 33 => "33"})
iex> A.RBTree.Map.foldl(tree, 0, fn key, _value, acc -> acc + key end)
66
iex> A.RBTree.Map.foldl(tree, [], fn key, value, acc -> [{key, value} | acc] end)
[{33, "33"}, {22, "22"}, {11, "11"}]

foldr(tree, acc, fun)

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> tree = A.RBTree.Map.new(%{22 => "22", 11 => "11", 33 => "33"})
iex> A.RBTree.Map.foldr(tree, 0, fn key, _value, acc -> acc + key end)
66
iex> A.RBTree.Map.foldr(tree, [], fn key, value, acc -> [{key, value} | acc] end)
[{11, "11"}, {22, "22"}, {33, "33"}]

height(arg1)

insert(root, key, value)

Specs

insert(tree(k, v), k, v) :: {:new | :overwrite, tree(k, v)}
when k: key(), v: value()

Inserts the key-value pair in a map tree and returns the updated tree.

Returns a {:new, new_tree} tuple when the key was newly created, a {:overwrite, new_tree} tuple when the key was already present.

Examples

iex> tree = A.RBTree.Map.new(%{1 => "A", 3 => "C"})
iex> A.RBTree.Map.insert(tree, 2, "B")
{:new, {:B, {:B, :E, 1, "A", :E}, 2, "B", {:B, :E, 3, "C", :E}}}
iex> A.RBTree.Map.insert(tree, 3, "C!!!")
{:overwrite, {:B, :E, 1, "A", {:R, :E, 3, "C!!!", :E}}}

insert_many(tree, list)

Specs

insert_many(tree(k, v), Enumerable.t()) :: {non_neg_integer(), tree(k, v)}
when k: key(), v: value()

Adds many key-values to an existing map tree, and returns both the new tree and the number of new entries created.

Returns a {inserted, new_tree} tuple when inserted is the number of newly created entries. Updating existing keys do not count. This is useful to keep track of size changes.

Examples

iex> tree = A.RBTree.Map.new(%{1 => "A", 2 => "B"})
iex> A.RBTree.Map.insert_many(tree, %{2 => "B", 3 => "C"})
{1, {:B, {:B, :E, 1, "A", :E}, 2, "B", {:B, :E, 3, "C", :E}}}

iterator(root)

Specs

iterator(tree(k, v)) :: iterator(k, v) when k: key(), v: value()

iterator(iterator(k, v)) :: {k, v, iterator(k, v)} | nil
when k: key(), v: value()

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.Map.new([a: 22, b: 11]) |> A.RBTree.Map.iterator()
iex> {k1, v1, iterator} = A.RBTree.Map.next(iterator)
iex> {k2, v2, iterator} = A.RBTree.Map.next(iterator)
iex> A.RBTree.Map.next(iterator)
nil
iex> [k1, v1, k2, v2]
[:a, 22, :b, 11]

max(arg1)

Specs

max(tree(k, v)) :: {k, v} | nil when k: key(), v: value()

Finds the leftmost (smallest) element of a tree

Examples

iex> A.RBTree.Map.new([b: "B", d: "D", a: "A", c: "C"]) |> A.RBTree.Map.max()
{:d, "D"}
iex> A.RBTree.Map.new([]) |> A.RBTree.Map.max()
nil

min(arg1)

Specs

min(tree(k, v)) :: {k, v} | nil when k: key(), v: value()

Finds the rightmost (largest) element of a tree

Examples

iex> A.RBTree.Map.new([b: "B", d: "D", a: "A", c: "C"]) |> A.RBTree.Map.min()
{:a, "A"}
iex> A.RBTree.Map.new([]) |> A.RBTree.Map.min()
nil

new(list)

Specs

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

Initializes a map tree from an enumerable.

Examples

iex> A.RBTree.Map.new(%{1 => "A", 2 => "B", 3 => "C"})
{:B, {:B, :E, 1, "A", :E}, 2, "B", {:B, :E, 3, "C", :E}}

next(list)

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

Examples

iex> iterator = A.RBTree.Map.new([a: 22, b: 11]) |> A.RBTree.Map.iterator()
iex> {k1, v1, iterator} = A.RBTree.Map.next(iterator)
iex> {k2, v2, iterator} = A.RBTree.Map.next(iterator)
iex> A.RBTree.Map.next(iterator)
nil
iex> [k1, v1, k2, v2]
[:a, 22, :b, 11]

node_count(root)

Specs

node_count(tree()) :: non_neg_integer()

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

Examples

iex> tree = A.RBTree.Map.new([{1,:a}, {2, :b}, {2.0, :c}, {3, :d}, {3.0, :e}, {3, :f}])
iex> A.RBTree.Map.node_count(tree)
3
iex> A.RBTree.Map.node_count(A.RBTree.Map.empty())
0

pop(tree, key)

Specs

pop(tree(k, v), k) :: {v, tree(k, v)} | :error when k: key(), v: value()

Finds and removes the value corresponding for the given key if exists in a map tree, and returns both that value and the new tree.

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

Examples

iex> tree = A.RBTree.Map.new(%{a: "A", b: "B", c: "C"})
iex> {"B", _new_tree} = A.RBTree.Map.pop(tree, :b)
{"B", {:B, :E, :a, "A", {:R, :E, :c, "C", :E}}}
iex> :error = A.RBTree.Map.pop(tree, :d)
:error

pop_max(tree)

Specs

pop_max(tree(k, v)) :: {k, v, tree(k, v)} | :error when k: key(), v: value()

Finds and removes the rightmost (largest) key in a map tree.

Returns both the key-value pair and the new tree.

Examples

iex> tree = A.RBTree.Map.new(%{a: "A", b: "B", c: "C"})
iex> {:c, "C", new_tree} = A.RBTree.Map.pop_max(tree)
iex> new_tree
{:B, :E, :a, "A", {:R, :E, :b, "B", :E}}
iex> :error = A.RBTree.Map.pop_max(A.RBTree.Map.empty())
:error

pop_min(tree)

Specs

pop_min(tree(k, v)) :: {k, v, tree(k, v)} | :error when k: key(), v: value()

Finds and removes the leftmost (smallest) key in a map tree.

Returns both the key-value pair and the new tree.

Examples

iex> tree = A.RBTree.Map.new(%{a: "A", b: "B", c: "C"})
iex> {:a, "A", new_tree} = A.RBTree.Map.pop_min(tree)
iex> new_tree
{:B, {:R, :E, :b, "B", :E}, :c, "C", :E}
iex> :error = A.RBTree.Map.pop_min(A.RBTree.Map.empty())
:error

reduce(tree, acc, fun)

Helper to implement Enumerable.reduce/3 in data structures using the underlying tree.

to_list(root)

Specs

to_list(tree(k, v)) :: [{k, v}] when k: key(), v: value()

Returns the tree as a list.

Examples

iex> A.RBTree.Map.new([b: "B", c: "C", a: "A"]) |> A.RBTree.Map.to_list()
[{:a, "A"}, {:b, "B"}, {:c, "C"}]
iex> A.RBTree.Map.empty() |> A.RBTree.Map.to_list()
[]