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_dictionaryDATA 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)}