ec_rbdict

.

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_dictionary

DATA TYPES

color() = r | b
dictionary(K, V) = empty | {color(), dictionary(K, V), key(K) (see module ec_dictionary), value(V) (see module ec_dictionary), dictionary(K, V)}

Functions


new() -> dictionary(_K, _V)

has_key(K::key(K) (see module ec_dictionary), X2::dictionary(K, _V)) -> boolean()

get(K::key(K) (see module ec_dictionary), X2::dictionary(K, V)) -> value(V) (see module ec_dictionary)

get(K::key(K) (see module ec_dictionary), Default::value(V) (see module ec_dictionary), X3::dictionary(K, V)) -> value(V) (see module ec_dictionary)

add(Key::key(K) (see module ec_dictionary), Value::value(V) (see module ec_dictionary), Dict::dictionary(K, V)) -> dictionary(K, V)

remove(Key::key(K) (see module ec_dictionary), Dictionary::dictionary(K, V)) -> dictionary(K, V)

has_value(Value::value(V) (see module ec_dictionary), Dict::dictionary(_K, V)) -> boolean()

size(T::dictionary(_K, _V)) -> non_neg_integer()

to_list(T::dictionary(K, V)) -> [{key(K) (see module ec_dictionary), value(V) (see module ec_dictionary)}]

from_list(L::[{key(K) (see module ec_dictionary), value(V) (see module ec_dictionary)}]) -> dictionary(K, V)

keys(Dict::dictionary(K, _V)) -> [key(K) (see module ec_dictionary)]

View Functions