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 (<)
(less-than) on elements.
Author: Johannes Koj, Michael Hanus, Bernd Brassel
Version: March 2013
emptySetRBT
:: (a -> a -> Bool) -> RedBlackTree a
Returns an empty set, i.e., an empty red-black tree augmented with an order predicate. |
isEmptySetRBT
:: RedBlackTree a -> Bool
Test for an empty set. |
elemRBT
:: a -> RedBlackTree a -> Bool
Returns true if an element is contained in a (red-black tree) set. |
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. |
deleteRBT
:: a -> RedBlackTree a -> RedBlackTree a
delete an element from a set. |
setRBT2list
:: RedBlackTree a -> [a]
Transforms a (red-black tree) set into an ordered list of its elements. |
unionRBT
:: RedBlackTree a -> RedBlackTree a -> RedBlackTree a
Computes the union of two (red-black tree) sets. |
intersectRBT
:: RedBlackTree a -> RedBlackTree a -> RedBlackTree a
Computes the intersection of two (red-black tree) sets. |
sortRBT
:: (a -> a -> Bool) -> [a] -> [a]
Generic sort based on insertion into red-black trees. |
Type synonym: SetRBT a = RedBlackTree a
Returns an empty set, i.e., an empty red-black tree augmented with an order predicate. |
Test for an empty set.
|
Returns true if an element is contained in a (red-black tree) set.
|
Inserts an element into a set if it is not already there. |
Inserts an element into a multiset. Thus, the same element can have several occurrences in the multiset. |
delete an element from a set. Deletes only a single element from a multi set |
Transforms a (red-black tree) set into an ordered list of its elements.
|
Computes the union of two (red-black tree) sets. This is done by inserting all elements of the first set into the second set. |
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. |
Generic sort based on insertion into red-black trees. The first argument is the order for the elements. |