rbtree v0.1.6 Tree
A set of functions for red-black tree.
Red-black tree is a self-balancing binary search tree data structure. Although Elixir has excellent support for hash map, it does not include any sorted or ordered data structures. This package will be the underlying data structure for SortedMap and SortedSet. In addition to usual operations, it also supports ordinal indexing with time complexity O(log(N)) for versatility.
Author: Ricky Hanrickylqhan@gmail.com Modified from Data.Set.RBtree package in Haskell.
Link to this section Summary
Functions
Invoked in order to access the value stored under key in the given term term
Invoked in order to access the value stored under key in the given term term,
defaulting to default if not present
Invoked in order to access the value under key and update it at the same time
Invoked to “pop” the value under key out of the given term
Link to this section Functions
Invoked in order to access the value stored under key in the given term term.
This function should return {:ok, value} where value is the value under
key if it succeeded, or :error if the key does not exist in the structure.
Many of the functions defined in the Access module internally call this
function. This function is also used when the square-brackets access syntax
(structure[key]) is used: the fetch/2 callback implemented by the module
that defines the structure struct is invoked and if it returns {:ok,
value} then value is returned, or if it returns :error then nil is
returned.
See the Map.fetch/2 and Keyword.fetch/2 implementations for examples of
how to implement this callback.
Callback implementation for Access.fetch/2.
Invoked in order to access the value stored under key in the given term term,
defaulting to default if not present.
This function should return the value under the key key in term if there’s
such key, otherwise default.
For most data structures, this can be implemented using fetch/2 internally;
for example:
def get(structure, key, default) do
case fetch(structure, key) do
{:ok, value} -> value
:error -> default
end
end
See the Map.get/3 and Keyword.get/3 implementations for more examples.
Callback implementation for Access.get/3.
Invoked in order to access the value under key and update it at the same time.
The implementation of this callback should invoke the passed function with the
value under key key in the passed structure, or nil if the key is not
present. This function should return either {value_to_return, new_value} or
:pop.
If it returns {value_to_return, new_value}, the return value of this
callback should be {value_to_return, new_term} where new_term is term
after updating the value of key with new_value.
If it returns :pop, the return value of this callback should be {value,
new_term} where value is the value under key or nil if not present, and
new_term is term without the key key.
See the implementations of Map.get_and_update/3 or Keyword.get_and_update/3
for more examples.
Callback implementation for Access.get_and_update/3.
Invoked to “pop” the value under key out of the given term.
When the key key exists in the given term, the implementation should
return a {value, new_term} tuple where value is the value that was under
key and new_term is term without key.
When the key key is not present in the given term, a tuple {value, term}
should be returned, where value is implementation-defined.
See the implementations for Map.pop/3 or Keyword.pop/3 for more examples.
Callback implementation for Access.pop/2.