All Packages
All Categories
By Author

ap (3)
cp (3)
dp (3)
exe (3)
gui (0)
gui/gtk (0)
gui/tk (4)
io (1)
lib (11)
math (0)
net (9)
nlp (18)
op (4)
os (2)
program (3)
sp (2)
tool (9)
wp (2)
xml (2)


blurb:Red-Black Tree
author:Filip Konvicka
Red-Black Tree

Provides a pure-Oz implementation of a sorted associative container. 
The underlying red-black tree allows for log(n) element access, 
constant time neighborhood exploration etc. By default, the keys must be mutually comparable using Value.'<', otherwise one can specify a custom key comparator when the tree is created.

The implementation provides similar interface as e.g. the standard Dictionary module. In addition to the standard interface, there are RB-tree specific functions. See the module source code for further info (the exported functions are documented in Javadocs style).

WARNING: this data structure is *NOT THREAD-SAFE*, i.e. concurrent access might cause undesired effects. Synchronization is available as a compilation flag ("LOCKING"), but this is not usable in nested spaces, where this causes situatedness violation. Therefore, access from multiple threads needs external synchronization. Note however, that concurrent access that does not change the *keys* of the tree is guaranteed to be thread-safe.