BalancedTree

v0.2.2

BalancedTree v0.2.2 BalancedTree View Source

This module provides an implementation of Prof. Arne Andersson’s Balanced Trees. BalancedTree is used to store and retrieve ordered data efficiently.

By default, two keys are considered equal if one is not less than < or greater than > the other. A different comparison function can be specified.

The implementation is largely taken from Erlang :gb_trees, with minor modifications to provide an interface similar to Elixir Map module.

Link to this section Summary

Types

key()

A key in the tree

t()

A balanced tree

value()

A value in the tree

Functions

delete(tree, key)

Deletes the entry for the given key from tree

empty?(tree)

Returns true if tree is empty

fetch(tree, key)

Fetches the value for a specific key in the given tree

fetch!(tree, key)

Fetches the value for a specific key in the given tree, raising an error if tree doesn’t contain key

get(tree, key, default \\ nil)

Gets the value for a specific key in tree

get_and_update(tree, key, fun)

Gets the value for key in tree and updates it, all in one pass

get_and_update!(tree, key, fun)

Gets the value fom key in tree and updates it. Raises if there is no key

has_key?(tree, key)

Returns wheter the given key exists in tree

map(tree, fun)

Maps function fun to all key-value pairs in tree

max(tree)

Returs the key-value pair associated with the largest key in tree

min(tree)

Returs the key-value pair associated with the smallest key in tree

new()

Returns a new empty tree

new(values, opts \\ [])

Creates a new tree from values

pop(tree, key, default \\ nil)

Returns and removes the value for key in tree

put(tree, key, value)

Puts the given value under key in tree

size(tree)

Returns the number of elements in tree

to_list(tree)

Converts tree to a list

Link to this section Types

Link to this type key() View Source 
key() :: any()

A key in the tree.

Link to this type t() View Source 
t() :: %BalancedTree{comparator: term(), root: term()}

A balanced tree.

Link to this type value() View Source 
value() :: any()

A value in the tree.

Link to this section Functions

Link to this function delete(tree, key) View Source 
delete(t(), key()) :: t()

Deletes the entry for the given key from tree.

Examples 

iex> BalancedTree.delete(BalancedTree.new([a: 1]), :a)
#BalancedTree<[]>
iex> BalancedTree.delete(BalancedTree.new([a: 1]), :b)
#BalancedTree<[a: 1]>
Link to this function empty?(tree) View Source 
empty?(t()) :: boolean()

Returns true if tree is empty.

Examples 

iex> BalancedTree.empty?(BalancedTree.new())
true
iex> BalancedTree.empty?(BalancedTree.new([a: 1]))
false
Link to this function fetch(tree, key) View Source 
fetch(t(), key()) :: {:ok, value()} | :error

Fetches the value for a specific key in the given tree.

Examples 

iex> BalancedTree.fetch(BalancedTree.new([a: 1]), :a)
{:ok, 1}
iex> BalancedTree.fetch(BalancedTree.new([a: 1]), :b)
:error
Link to this function fetch!(tree, key) View Source 
fetch!(t(), key()) :: value() | no_return()

Fetches the value for a specific key in the given tree, raising an error if tree doesn’t contain key.

Examples 

iex> BalancedTree.fetch!(BalancedTree.new([a: 1]), :a)
1
iex> BalancedTree.fetch!(BalancedTree.new([a: 1]), :b)
** (KeyError) key nil not found
Link to this function get(tree, key, default \\ nil) View Source 
get(t(), key(), value()) :: value()

Gets the value for a specific key in tree.

If key is present in tree with value, then value is returned. Otherwise, a default is returned.

Examples 

iex> BalancedTree.get(BalancedTree.new([a: 1]), :b)
nil
iex> BalancedTree.get(BalancedTree.new([a: 1]), :a)
1
iex> BalancedTree.get(BalancedTree.new([a: 1]), :b, 3)
3
Link to this function get_and_update(tree, key, fun) View Source 
get_and_update(t(), key(), (value() -> {get, value()} | :pop)) :: {get, t()} when get: term()

Gets the value for key in tree and updates it, all in one pass.

Examples 

iex> {1, tree} = BalancedTree.get_and_update(BalancedTree.new([a: 1]), :a, fn value ->
...>    {value, 2 * value}
...> end)
iex> tree
#BalancedTree<[a: 2]>
iex> {1, tree} = BalancedTree.get_and_update(BalancedTree.new([a: 1]), :a, fn _ ->
...>   :pop
...> end)
iex> tree
#BalancedTree<[]>
iex> {nil, tree} = BalancedTree.get_and_update(BalancedTree.new([a: 1]), :b, fn nil ->
...>   {nil, 2}
...> end)
iex> tree
#BalancedTree<[a: 1, b: 2]>
Link to this function get_and_update!(tree, key, fun) View Source 
get_and_update!(t(), key(), (value() -> {get, value()} | :pop)) ::
  {get, t()} |
  no_return() when get: term()

Gets the value fom key in tree and updates it. Raises if there is no key.

Examples 

iex> {1, tree} = BalancedTree.get_and_update!(BalancedTree.new([a: 1]), :a, fn value ->
...>   {value, 2 * value}
...> end)
iex> tree
#BalancedTree<[a: 2]>
iex> {1, tree} = BalancedTree.get_and_update!(BalancedTree.new([a: 1]), :a, fn _ ->
...>   :pop
...> end)
iex> tree
#BalancedTree<[]>
iex> BalancedTree.get_and_update!(BalancedTree.new([a: 1]), :b, fn _ ->
...>   :pop
...> end)
** (KeyError) key nil not found
Link to this function has_key?(tree, key) View Source 
has_key?(t(), key()) :: boolean()

Returns wheter the given key exists in tree.

Examples 

iex> BalancedTree.has_key?(BalancedTree.new([a: 1]), :a)
true
iex> BalancedTree.has_key?(BalancedTree.new([a: 1]), :b)
false
Link to this function map(tree, fun) View Source 
map(t(), (key(), value() -> value())) :: t()

Maps function fun to all key-value pairs in tree.

Examples 

iex> BalancedTree.map(BalancedTree.new([c: 3, b: 2, a: 1]), fn k, _ -> k end)
#BalancedTree<[a: :a, b: :b, c: :c]>
Link to this function max(tree) View Source 
max(t()) :: {key(), value()}

Returs the key-value pair associated with the largest key in tree.

Examples 

iex> BalancedTree.max(BalancedTree.new([b: 2, a: 1]))
{:b, 2}
iex> BalancedTree.max(BalancedTree.new([b: 2, a: 1], comparator: &bigger_to_smaller/2))
{:a, 1}
iex> BalancedTree.max(BalancedTree.new())
nil
Link to this function min(tree) View Source 
min(t()) :: {key(), value()}

Returs the key-value pair associated with the smallest key in tree.

Examples 

iex> BalancedTree.min(BalancedTree.new([b: 2, a: 1]))
{:a, 1}
iex> BalancedTree.min(BalancedTree.new([b: 2, a: 1], comparator: &bigger_to_smaller/2))
{:b, 2}
iex> BalancedTree.min(BalancedTree.new())
nil
Link to this function new() View Source 
new() :: t()

Returns a new empty tree.

Examples 

iex> BalancedTree.new
#BalancedTree<[]>
Link to this function new(values, opts \\ []) View Source 
new(Enumerable.t(), [{:comparator, (key(), key() -> :lt | :gt | :eq)}]) :: t()

Creates a new tree from values.

Options

  • :comparator function that takes two keys (a, b) and returns:

    • :lt if a < b
    • :gt if a > b
    • :eq if a == b

Examples 

iex> BalancedTree.new([{1, :a}, {2, :b}, {3, :c}])
#BalancedTree<[1 => :a, 2 => :b, 3 => :c]>

iex> BalancedTree.new([{1, :a}, {2, :b}, {3, :c}], comparator: &bigger_to_smaller/2)
#BalancedTree<[3 => :c, 2 => :b, 1 => :a]>
Link to this function pop(tree, key, default \\ nil) View Source 
pop(t(), key(), value()) :: {value(), t()}

Returns and removes the value for key in tree.

Examples 

iex> {1, tree} = BalancedTree.pop(BalancedTree.new([a: 1]), :a)
iex> tree
#BalancedTree<[]>
iex> {nil, tree} = BalancedTree.pop(BalancedTree.new([a: 1]), :b)
iex> tree
#BalancedTree<[a: 1]>
iex> {3, tree} = BalancedTree.pop(BalancedTree.new([a: 1]), :b, 3)
iex> tree
#BalancedTree<[a: 1]>
Link to this function put(tree, key, value) View Source 
put(t(), key(), value()) :: t()

Puts the given value under key in tree.

Examples 

iex> BalancedTree.put(BalancedTree.new([a: 1]), :b, 2)
#BalancedTree<[a: 1, b: 2]>
iex> BalancedTree.put(BalancedTree.new([a: 1, b: 2]), :b, 3)
#BalancedTree<[a: 1, b: 3]>
Link to this function size(tree) View Source 
size(t()) :: integer()

Returns the number of elements in tree.

Examples 

iex> BalancedTree.size(BalancedTree.new([a: 1]))
1
Link to this function to_list(tree) View Source 
to_list(t()) :: [{key(), value()}]

Converts tree to a list.

Examples 

iex> BalancedTree.to_list(BalancedTree.new([c: 1, b: 2, a: 3]))
[a: 3, b: 2, c: 1]