PAKCS
Exported names: Imported modules:

Module RedBlackTree

Library with an implementation of red-black trees:

Serves as the base for both TableRBT and SetRBT All the operations on trees are generic, i.e., one has to provide two explicit order predicates ("lessThan" and "eq"below) on elements.

Author: Johannes Koj, Michael Hanus, Bernd Brassel

Version: March 2005

Summary of exported operations:

empty :: (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> RedBlackTree a   
The three relations are inserted into the structure by function empty.
isEmpty :: RedBlackTree a -> Bool   
Test on emptyness
newTreeLike :: RedBlackTree a -> RedBlackTree a   
Creates a new empty red black tree from with the same ordering as a give one.
lookup :: a -> RedBlackTree a -> Maybe a   
Returns an element if it is contained in a red-black tree.
update :: a -> RedBlackTree a -> RedBlackTree a   
Updates/inserts an element into a RedBlackTree.
delete :: a -> RedBlackTree a -> RedBlackTree a   
Deletes entry from red black tree.
tree2list :: RedBlackTree a -> [a]   
Transforms a red-black tree into an ordered list of its elements.
sortBy :: Eq a => (a -> a -> Bool) -> [a] -> [a]   
Generic sort based on insertion into red-black trees.
setInsertEquivalence :: (a -> a -> Bool) -> RedBlackTree a -> RedBlackTree a   
For compatibility with old version only

Exported datatypes:

RedBlackTree

A red-black tree consists of a tree structure and three order predicates. These predicates generalize the red black tree. They define 1) equality when inserting into the tree
eg for a set eqInsert is (==), for a multiset it is ( -> False) for a lookUp-table it is ((==) . fst) 2) equality for looking up values eg for a set eqLookUp is (==), for a multiset it is (==) for a lookUp-table it is ((==) . fst) 3) the (less than) relation for the binary search tree

Constructors:

Exported operations:

empty :: (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> RedBlackTree a   

The three relations are inserted into the structure by function empty. Returns an empty tree, i.e., an empty red-black tree augmented with the order predicates.

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

isEmpty :: RedBlackTree a -> Bool   

Test on emptyness

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

newTreeLike :: RedBlackTree a -> RedBlackTree a   

Creates a new empty red black tree from with the same ordering as a give one.

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

lookup :: a -> RedBlackTree a -> Maybe a   

Returns an element if it is contained in a red-black tree.

Example call:
(lookup p t)
Parameters:
  • p : a pattern for an element to look up in the tree
  • t : a red-black tree
Returns:
the contained True if p matches in t

update :: a -> RedBlackTree a -> RedBlackTree a   

Updates/inserts an element into a RedBlackTree.

delete :: a -> RedBlackTree a -> RedBlackTree a   

Deletes entry from red black tree.

tree2list :: RedBlackTree a -> [a]   

Transforms a red-black tree into an ordered list of its elements.

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

sortBy :: Eq a => (a -> a -> Bool) -> [a] -> [a]   

Generic sort based on insertion into red-black trees. The first argument is the order for the elements.

setInsertEquivalence :: (a -> a -> Bool) -> RedBlackTree a -> RedBlackTree a   

For compatibility with old version only

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