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 73 74 75 76 |
---------------------------------------------------------------------------- --- 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 ---------------------------------------------------------------------------- module Data.Set.RBTree where import qualified Data.RedBlackTree as RBT import Data.Maybe (isJust) import Prelude hiding (empty) type SetRBT a = RBT.RedBlackTree a --- Returns an empty set, i.e., an empty red-black tree --- augmented with an order predicate. empty :: Eq a => (a -> a -> Bool) -> SetRBT a empty = RBT.empty (==) (==) --- Returns an empty set that uses the Ord's ordering predicate. emptyOrd :: Ord a => SetRBT a emptyOrd = empty (<) --- Test for an empty set. null :: SetRBT _ -> Bool null = 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 member :: a -> SetRBT a -> Bool member e = isJust . (RBT.lookup e) --- Inserts an element into a set if it is not already there. insert :: a -> SetRBT a -> SetRBT a insert = RBT.update --- Inserts an element into a multiset. --- Thus, the same element can have several occurrences in the multiset. insertMulti :: Eq a => a -> SetRBT a -> SetRBT a insertMulti e = RBT.setInsertEquivalence (==) . RBT.update e . RBT.setInsertEquivalence (\ _ _ -> False) --- delete an element from a set. --- Deletes only a single element from a multi set delete :: a -> SetRBT a -> SetRBT a delete = RBT.delete --- Transforms a (red-black tree) set into an ordered list of its elements. toList :: SetRBT a -> [a] toList = RBT.toList --- Computes the union of two (red-black tree) sets. --- This is done by inserting all elements of the first set into the --- second set. union :: SetRBT a -> SetRBT a -> SetRBT a union s1 s2 = foldr insert s2 (toList 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. intersection :: SetRBT a -> SetRBT a -> SetRBT a intersection s1 s2 = foldr insert (RBT.newTreeLike s1) (filter (`member` s2) (toList s1)) --- Generic sort based on insertion into red-black trees. --- The first argument is the order for the elements. sortBy :: Eq a => (a -> a -> Bool) -> [a] -> [a] sortBy = RBT.sortBy |