1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

----------------------------------------------------------------------------
--- 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
--- @category algorithm
----------------------------------------------------------------------------

module SetRBT where

import qualified RedBlackTree as RBT
import           Maybe               (isJust)

type SetRBT a = RBT.RedBlackTree a

--- Returns an empty set, i.e., an empty red-black tree
--- augmented with an order predicate.
emptySetRBT :: (a -> a -> Bool) -> SetRBT a
emptySetRBT = RBT.empty (==) (==)

--- Test for an empty set.
isEmptySetRBT :: SetRBT _ -> Bool
isEmptySetRBT = RBT.isEmpty

--- Returns true if an element is contained in a (red-black tree) set.
--- @param e - an element to be checked for containment
--- @param s - a set (represented as a red-black tree)
--- @return True if e is contained in s
elemRBT :: a -> SetRBT a -> Bool
elemRBT e = isJust . (RBT.lookup e)

--- Inserts an element into a set if it is not already there.
insertRBT :: a -> SetRBT a -> SetRBT a
insertRBT = RBT.update

--- Inserts an element into a multiset.
--- Thus, the same element can have several occurrences in the multiset.
insertMultiRBT :: a -> SetRBT a -> SetRBT a
insertMultiRBT e = RBT.setInsertEquivalence (==)
                 . RBT.update e
                 . RBT.setInsertEquivalence (\ _ _ -> False)

--- delete an element from a set.
--- Deletes only a single element from a multi set
deleteRBT :: a -> SetRBT a -> SetRBT a
deleteRBT = RBT.delete

--- Transforms a (red-black tree) set into an ordered list of its elements.
setRBT2list :: SetRBT a -> [a]
setRBT2list = RBT.tree2list

--- Computes the union of two (red-black tree) sets.
--- This is done by inserting all elements of the first set into the
--- second set.
unionRBT :: SetRBT a -> SetRBT a -> SetRBT a
unionRBT s1 s2 = foldr insertRBT s2 (setRBT2list s1)

--- 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.
intersectRBT :: SetRBT a -> SetRBT a -> SetRBT a
intersectRBT s1 s2 = foldr insertRBT (RBT.newTreeLike s1)
                     (filter (`elemRBT` s2) (setRBT2list s1))

--- Generic sort based on insertion into red-black trees.
--- The first argument is the order for the elements.
sortRBT  :: (a -> a -> Bool) -> [a] -> [a]
sortRBT = RBT.sortBy