Module TableRBT

Library with an implementation of tables as red-black trees:

A table is a finite mapping from keys to values. All the operations on tables are generic, i.e., one has to provide an explicit order predicate ("cmp" below) on elements. Each inner node in the red-black tree contains a key-value association.

Author: Johannes Koj, Michael Hanus, Bernd Brassel

Version: March 2005

Summary of exported operations:

emptyTableRBT :: Eq a => (a -> a -> Bool) -> RedBlackTree (a,b)   
Returns an empty table, i.e., an empty red-black tree.
isEmptyTable :: RedBlackTree (a,b) -> Bool   
tests whether a given table is empty
lookupRBT :: a -> RedBlackTree (a,b) -> Maybe b   
Looks up an entry in a table.
updateRBT :: a -> b -> RedBlackTree (a,b) -> RedBlackTree (a,b)   
Inserts or updates an element in a table.
tableRBT2list :: RedBlackTree (a,b) -> [(a,b)]   
Transforms the nodes of red-black tree into a list.
deleteRBT :: a -> RedBlackTree (a,b) -> RedBlackTree (a,b)   

Exported datatypes:


TableRBT

Type synonym: TableRBT a b = RedBlackTree (a,b)


Exported operations:

emptyTableRBT :: Eq a => (a -> a -> Bool) -> RedBlackTree (a,b)   

Returns an empty table, i.e., an empty red-black tree.

isEmptyTable :: RedBlackTree (a,b) -> Bool   

tests whether a given table is empty

Further infos:
  • solution complete, i.e., able to compute all solutions

lookupRBT :: a -> RedBlackTree (a,b) -> Maybe b   

Looks up an entry in a table.

Example call:
(lookupRBT k t)
Parameters:
  • k : a key under which a value is stored
  • t : a table (represented as a red-black tree)
Returns:
(Just v) if v is the value stored with key k, otherwise Nothing is returned.

updateRBT :: a -> b -> RedBlackTree (a,b) -> RedBlackTree (a,b)   

Inserts or updates an element in a table.

tableRBT2list :: RedBlackTree (a,b) -> [(a,b)]   

Transforms the nodes of red-black tree into a list.

Further infos:
  • solution complete, i.e., able to compute all solutions

deleteRBT :: a -> RedBlackTree (a,b) -> RedBlackTree (a,b)