Module Data.Set.RBTree

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: December 2018

Summary of exported operations:

 empty :: Eq a => (a -> a -> Bool) -> RedBlackTree a    Returns an empty set, i.e., an empty red-black tree augmented with an order predicate. null :: RedBlackTree a -> Bool    Test for an empty set. member :: a -> RedBlackTree a -> Bool    Returns true if an element is contained in a (red-black tree) set. insert :: a -> RedBlackTree a -> RedBlackTree a    Inserts an element into a set if it is not already there. insertMulti :: Eq a => a -> RedBlackTree a -> RedBlackTree a    Inserts an element into a multiset. delete :: a -> RedBlackTree a -> RedBlackTree a    delete an element from a set. toList :: RedBlackTree a -> [a]    Transforms a (red-black tree) set into an ordered list of its elements. union :: RedBlackTree a -> RedBlackTree a -> RedBlackTree a    Computes the union of two (red-black tree) sets. intersection :: RedBlackTree a -> RedBlackTree a -> RedBlackTree a    Computes the intersection of two (red-black tree) sets. sortBy :: Eq a => (a -> a -> Bool) -> [a] -> [a]    Generic sort based on insertion into red-black trees.

Exported datatypes:

SetRBT

Type synonym: SetRBT a = RedBlackTree a

Exported operations:

 empty :: Eq a => (a -> a -> Bool) -> RedBlackTree a    Returns an empty set, i.e., an empty red-black tree augmented with an order predicate. Further infos: solution complete, i.e., able to compute all solutions
 null :: RedBlackTree a -> Bool    Test for an empty set. Further infos: solution complete, i.e., able to compute all solutions
 member :: a -> RedBlackTree a -> Bool    Returns true if an element is contained in a (red-black tree) set. Example call: (member 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
 insert :: a -> RedBlackTree a -> RedBlackTree a    Inserts an element into a set if it is not already there.
 insertMulti :: Eq a => a -> RedBlackTree a -> RedBlackTree a    Inserts an element into a multiset. Thus, the same element can have several occurrences in the multiset.
 delete :: a -> RedBlackTree a -> RedBlackTree a    delete an element from a set. Deletes only a single element from a multi set
 toList :: 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
 union :: 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.
 intersection :: 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.
 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.