Module ec_rbdict

.

Copyright © 2008 Robert Verding

Behaviours: ec_dictionary.

Description

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()

color() = r | b

dictionary()

dictionary(K, V) = empty | {color(), dictionary(K, V), ec_dictionary:key(K), ec_dictionary:value(V), dictionary(K, V)}

Function Index

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

Function Details

add/3

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

from_list/1

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

get/2

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

get/3

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

has_key/2

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

has_value/2

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

keys/1

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

new/0

new() -> dictionary(_K, _V)

remove/2

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

size/1

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

to_list/1

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


Generated by EDoc, Feb 15 2022, 15:17:47.