PAKCS
Exported names: Imported modules:

Module Data.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 order predicates on elements.

Author: Johannes Koj, Michael Hanus, Bernd Brassel

Version: December 2018

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.
toList :: 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.

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