Library with an implementation of sets as red-black trees.
All the operations on sets are generic, i.e., one has to provide
an explicit order predicate ("cmp" below) on elements.
Author: Johannes Koj, Michael Hanus, Bernd Brassel
Version: May 2003
Datatypes:
SetRBT
Functions:
deleteRBT
| elemRBT
| emptySetRBT
| insertMultiRBT
| insertRBT
| intersectRBT
| setRBT2list
| sortRBT
| unionRBT
|
Summary of exported functions:
|
emptySetRBT :: (a -> a -> Bool) -> RedBlackTree a 
|
|
Returns an empty set, i.e., an empty red-black tree
augmented with an order predicate.
|
|
elemRBT :: a -> RedBlackTree a -> Bool
|
|
Returns true if an element is contained in a (red-black tree) set.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
sortRBT :: (a -> a -> Bool) -> [a] -> [a]
|
|
Generic sort based on insertion into red-black trees.
|
|
Maybe
Prelude
RedBlackTree
Type synonym: SetRBT a = RedBlackTree a
emptySetRBT :: (a -> a -> Bool) -> RedBlackTree a
Returns an empty set, i.e., an empty red-black tree
augmented with an order predicate.
elemRBT :: a -> RedBlackTree a -> Bool
Returns true if an element is contained in a (red-black tree) set.
Example call: (elemRBT e s)
-
Parameters:
-
e
- an element to be checked for containment
-
s
- a set (represented as a red-black tree)
-
Returns:
-
True if e is contained in s
insertRBT :: a -> RedBlackTree a -> RedBlackTree a
Inserts an element into a set if it is not already there.
insertMultiRBT :: a -> RedBlackTree a -> RedBlackTree a
Inserts an element into a multiset.
Thus, the same element can have several occurrences in the multiset.
deleteRBT :: a -> RedBlackTree a -> RedBlackTree a
delete an element from a set.
Deletes only a single element from a multi set
setRBT2list :: RedBlackTree a -> [a]
Transforms a (red-black tree) set into an ordered list of its elements.
-
Further infos:
-
-
solution complete, i.e., able to compute all solutions
unionRBT :: RedBlackTree a -> RedBlackTree a -> RedBlackTree a
Computes the union of two (red-black tree) sets.
This is done by inserting all elements of the first set into the
second set.
intersectRBT :: RedBlackTree a -> RedBlackTree a -> RedBlackTree a
Computes the intersection of two (red-black tree) sets.
This is done by inserting all elements of the first set
contained in the second set into a new set, which order
is taken from the first set.
sortRBT :: (a -> a -> Bool) -> [a] -> [a]
Generic sort based on insertion into red-black trees.
The first argument is the order for the elements.
Generated by CurryDoc
(Version 0.4.1 of June 7, 2007) at Jun 16 17:15:31 2009