{-
 - Mængder impl. med rød-sorte træer
 -
 - (c) svalle@imada.sdu.dk
 -}

module Set where

import RedBlackTree

newtype Set a = SetI (Tree a)

---------------------------------------------------------------------------
-- empty - en tom mængde
empty :: Set a
empty = SetI (emptyTree)

---------------------------------------------------------------------------
-- sing - en mængde med et element
sing :: Ord a => a -> Set a
sing x = SetI (ins x emptyTree)


---------------------------------------------------------------------------
-- memSet - er et element med i mængden?
memset :: Ord a => Set a -> a -> Bool
memset (SetI t) y = search t y

---------------------------------------------------------------------------
-- union - find foreningsmængden af to mængder
union :: Ord a => Set a -> Set a -> Set a
union = applyS uni

uni [] ys = ys
uni xs [] = xs
uni xx@(x:xs) yx@(y:ys)
  | x < y     = x : uni xs yx
  | x == y    = x : uni xs ys
  | x > y     = y : uni xx ys


---------------------------------------------------------------------------
-- inter -- finder fællesmængden af to mængder
inter :: Ord a => Set a -> Set a -> Set a 
inter = applyS int

int [] _  = []
int _  [] = []
int xx@(x:xs) yx@(y:ys)
  | x < y     =     int xs yx
  | x == y    = x : int xs ys
  | x > y     =     int xx ys

---------------------------------------------------------------------------
-- subset -- afgør om den første mgd er indeholdt i den anden
subset :: Ord a => Set a -> Set a -> Bool
subset = applyB subS

subS [] _  = True
subS _  [] = False
subS xx@(x:xs) (y:ys)
  | x < y     = False
  | x == y    = subS xs ys
  | x > y     = subS xx ys

---------------------------------------------------------------------------
-- eqSet -- afgør om to mængder er ens
eqSet :: Eq a => Set a -> Set a -> Bool
eqSet = applyB (==)

---------------------------------------------------------------------------
-- makeSet -- lav en mængde ud fra en liste af elementer
makeSet :: Ord a => [a] -> Set a
makeSet = SetI . list2tree


---------------------------------------------------------------------------
-- mapSet -- kør en fkt. på mængden
mapSet :: Ord b => (a -> b) -> Set a -> Set b
mapSet f (SetI t) = SetI $ list2tree $ map f $ tree2list t


---------------------------------------------------------------------------
-- filterSet -- udvælg elementer fra mængden
filterSet :: Ord a => (a -> Bool) -> Set a -> Set a
filterSet p (SetI t) = SetI $ list2tree $ filter p $ tree2list t

---------------------------------------------------------------------------
-- foldSet -- kør en fkt. på hele mængden
foldSet :: (a -> b -> b) -> b -> Set a -> b
foldSet f x (SetI t) = foldr f x $ tree2list t

---------------------------------------------------------------------------
-- showSet -- vis mængden
showSet :: (a->String) -> Set a -> String
showSet f (SetI t) = concat $ map ((++"\n").f) $ tree2list t
                     
---------------------------------------------------------------------------
-- card -- angiv antallet af elementer i mængden
card :: Set a -> Int
card (SetI t) = length $ tree2list t

---------------------------------------------------------------------------
-- applyS -- må kun bruges med funktioner, f, som
-- bevarer sorteringen + ikke laver dubbletter

applyS :: ([a] -> [a] -> [a]) -> Set a -> Set a -> Set a
applyS f (SetI a) (SetI b) = SetI (slist2tree (f (tree2list a) (tree2list b)))

---------------------------------------------------------------------------
-- applyB -- brug en fkt på træerne lavet om til lister
applyB :: ([a] -> [a] -> Bool) -> Set a -> Set a -> Bool
applyB f (SetI a) (SetI b) = f (tree2list a) (tree2list b)