Module "RedBlackTree.curry"

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 Braßel

Version: March 2005

Datatypes:
RedBlackTree

Functions:
delete | empty | isEmpty | lookup | newTreeLike | setInsertEquivalence | sort | tree2list | update

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.

sort  :: (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

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 functions:

---

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

---

sort :: (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

---

---

Generated by CurryDoc (Version 0.4.1 of June 7, 2007) at Aug 28 15:29:52 2008