--1
data Dom a = Empty
	| Full
	| Ran a a
	| (Dom a) :|: (Dom a)
	| (Dom a) :&: (Dom a)
	deriving (Show,Read,Eq,Ord)
--2
exist :: Ord a => a -> Dom a -> Bool
exist x Empty = False
exist x Full = True
exist x (Ran a b) = a <= x && x <= b
exist x (a :|: b) = exist x a || exist x b
exist x (a :&: b) = exist x a && exist x b
--3
overlap :: Ord a => Dom a -> Dom a-> Bool
overlap (Ran a b) (Ran c d) = (b >= c && a <= c) || (a >= c && d >= a) ||
   (a >= c && b <= d) || (c >= a && d <= b)
overlap Empty (Ran a b) = False
overlap Full (Ran a b) = True
overlap (Ran a b) Empty = False
overlap (Ran a b) Full = True
--4
normalize :: Dom a -> Dom a
normalize Empty = Empty
normalize Full = Full
normalize (Ran a b) = (Ran a b)

normalize (c :|: (a :&: b)) = (normalize (c :|: a)) :&: (normalize c :|: b)
normalize ((a :&: b) :|: c) = (normalize (a :|: c)) :&: (normalize b :|: c)
normalize (a :|: b ) = normalize a :|: normalize b

normalize ((a :|: b) :&: c) = (normalize (a :&: c)) :|: (normalize b :&: c)
normalize (c :&: (a :|: b)) = (normalize (c :&: a)) :|: (normalize c :&: b)
normalize (a :&: b) = (normalize a) :&: (normalize b)
--5
newtype SDom a = S (Dom a) deriving Show
newtype PDom a = P (Dom a) deriving Show

instance Monoid (SDom a) where
	mempty = S Empty
	mappend (S x) (S y) = S (x :|: y)

instance Monoid (PDom a) where
	mempty = P Full
	mappend (P x) (P y) = P (x :&: y)
--6
optimize :: Ord a => Dom a -> Dom a
optimize ((Ran a b) :|: Empty) = (Ran a b)
optimize ((Ran a b) :&: Empty) = (Ran a b)
optimize ((Ran a b) :|: Full) = (Ran a b)
optimize ((Ran a b) :&: Full) = (Ran a b)

optimize (Empty :|: (Ran a b)) = (Ran a b)
optimize (Empty :&: (Ran a b)) = (Ran a b)
optimize (Full :|: (Ran a b)) = (Ran a b)
optimize (Full :&: (Ran a b)) = (Ran a b)

optimize ((Ran a b) :&: (Ran c d)) = --intersectie
	if not (overlap (Ran a b) (Ran c d)) then (Ran a b) :&: (Ran c d)
		else if (a <= c && b <= d) then (Ran c b)
			else if (a >= c && b <= d) then (Ran a b)
				else if (a >= c && b >= d) then (Ran a d)
					else (Ran c d) --(a <= c && b >= d)

optimize ((Ran a b) :|: (Ran c d)) = --reuniune
	if not (overlap (Ran a b) (Ran c d)) then (Ran a b) :|: (Ran c d)
		else if (a <= c && b <= d) then (Ran a d)
			else if (a >= c && b <= d) then (Ran c d)
				else if (a >= c && b >= d) then (Ran c b)
					else (Ran a b) --(a <= c && b >= d)
--7
{-
data MyList a =
	Null
	| Elem a
	| MyList a :++: MyList a
	deriving Show

add :: a -> MyList a -> MyList a
add x xs = Elem x :++: xs

myList :: MyList Int
myList = add 1 $ add 2 $ add 3 $ add 4 $ add 5 Null

foldrZ :: (a -> b -> b) -> b -> MyList a -> b
foldrZ f e Null = e
foldrZ f e (Elem x) = f x e
foldrZ f e (xs :++: ys) = foldrZ f (foldrZ f e ys) xs

instance Foldable MyList where
	foldr = foldrZ
-}

data DomF a = Empty -- interval vid (multimea vida)
	| Ran a a -- interval inchis [a,b]
	| (DomF a) :|: (DomF a) -- reuniunea a 2 intervale A U B
	deriving Show

foldDom :: (a -> b -> b) -> b -> DomF a -> b
foldDom f e d = faux d e
	where  faux Empty e = e
		   faux (Ran x y) e = f x (f y e)
		   faux (x :|: y) e = faux y (faux x e)

instance Foldable MyList where
	foldr = foldDom