Copyright © 2008 Robert Verding
Behaviours: ec_dictionary.
Rbdict implements a Key - Value dictionary. An rbdict is a representation of a dictionary, where a red-black tree is used to store the keys and values.
This module implents exactly the same interface as the module ec_dictionary but with a defined representation. One difference is that while dict considers two keys as different if they do not match (=:=), this module considers two keys as different if and only if they do not compare equal (==).
The algorithms here are taken directly from Okasaki and Rbset in ML/Scheme. The interface is compatible with the standard dict interface.
The following structures are used to build the the RB-dict:
{r,Left,Key,Val,Right} {b,Left,Key,Val,Right} empty
It is interesting to note that expanding out the first argument of l/rbalance, the colour, in store etc. is actually slower than not doing it. Measured.
see ec_dictionarycolor() = r | b
dictionary(K, V) = empty | {color(), dictionary(K, V), ec_dictionary:key(K), ec_dictionary:value(V), dictionary(K, V)}
add/3 | |
from_list/1 | |
get/2 | |
get/3 | |
has_key/2 | |
has_value/2 | |
keys/1 | |
new/0 | |
remove/2 | |
size/1 | |
to_list/1 |
add(Key::ec_dictionary:key(K), Value::ec_dictionary:value(V), Dict::dictionary(K, V)) -> dictionary(K, V)
from_list(L::[{ec_dictionary:key(K), ec_dictionary:value(V)}]) -> dictionary(K, V)
get(K::ec_dictionary:key(K), X2::dictionary(K, V)) -> ec_dictionary:value(V)
get(K::ec_dictionary:key(K), Default::ec_dictionary:value(V), X3::dictionary(K, V)) -> ec_dictionary:value(V)
has_key(K::ec_dictionary:key(K), X2::dictionary(K, _V)) -> boolean()
has_value(Value::ec_dictionary:value(V), Dict::dictionary(_K, V)) -> boolean()
keys(Dict::dictionary(K, _V)) -> [ec_dictionary:key(K)]
new() -> dictionary(_K, _V)
remove(Key::ec_dictionary:key(K), Dictionary::dictionary(K, V)) -> dictionary(K, V)
size(T::dictionary(_K, _V)) -> non_neg_integer()
to_list(T::dictionary(K, V)) -> [{ec_dictionary:key(K), ec_dictionary:value(V)}]
Generated by EDoc, May 1 2024, 06:09:58.