module Set
	(Set, empty, sing, memSet,
	union, inter, diff, eqSet,
	subSet, makeSet, mapSet, filterSet,
	foldSet, showSet, card)	where

import Heap

newtype Set a = Set (Heap a)

instance (Eq a, Ord a) => Eq (Set a) where
	(==) = eqSet
instance Ord a => Ord (Set a) where
	(<=) = leqSet

-- Creates a new empty Set
empty :: Set a
empty = Set heapCreate

-- Makes a Set out of a
sing :: Ord a => a -> Set a
sing x = Set (heapInsert heapCreate x)

-- Checks whether a is a member of the Set
memSet :: Ord a => Set a -> a -> Bool
memSet (Set a) b
	| heapFind a b == 0	= False
	| otherwise			= True

union :: Ord a => Set a -> Set a -> Set a
union (Set a) (Set b) = Set (heapMerge a b)

inter :: Ord a => Set a -> Set a -> Set a
inter (Set a) (Set b) = Set (heapIntersect a b)

diff :: Ord a => Set a -> Set a -> Set a
diff (Set a) (Set b) = Set (heapDifference a b)

eqSet :: (Eq a, Ord a) => Set a -> Set a -> Bool
eqSet (Set a) (Set b) = heapEquals a b

leqSet :: Ord a => Set a -> Set a -> Bool
leqSet (Set a) (Set b) = heapLesserOrEq a b

-- Yes, they are reversed on purpose.
-- This asks heapContains "does b contain a?"
subSet :: Ord a => Set a -> Set a -> Bool
subSet (Set a) (Set b) = heapContains b a

makeSet :: Ord a => [a] -> Set a
makeSet []	= empty
makeSet a	= makeSetHelper a empty

makeSetHelper :: Ord a => [a] -> Set a -> Set a
makeSetHelper [] b = b
makeSetHelper (x:xs) (Set b) = makeSetHelper xs (Set (heapInsert b x))

mapSet :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
mapSet f (Set a) = Set (heapMap f a)

filterSet :: Ord a => (a -> Bool) -> Set a -> Set a
filterSet f (Set a) = Set (heapFilter f a)

-- The type differs from the prescribed (a -> a -> a) -> a -> Set a -> a
-- but that's only a good thing. This function is more general, thus more useful.
-- It will work fine if a is same type as b anyways, but now also if they differ.
foldSet :: Ord b => (a -> b -> a) -> a -> Set b -> a
foldSet f a (Set b) = heapFold f a b

showSet :: Ord a => (a -> String) -> Set a -> String
showSet f (Set a) = heapShow f a

card :: Set a -> Int
card (Set a) = heapSize a