--import Gofer
import List


copy                :: Int -> a -> [a]
copy n x             = take n (repeat x)

data Valdom3  = NO | PO | FO

instance Eq Valdom3 where
	 NO == NO = True
	 PO == PO = True
	 FO == FO = True
	 _  == _  = False

instance Ord Valdom3 where
	 NO <= NO = True
	 NO <= PO = True
	 NO <= FO = True
	 PO <= PO = True
	 PO <= FO = True
	 FO <= FO = True
	 _  <= _  = False

instance Show Valdom3 where
	 show NO = "NO"
	 show PO = "PO"
	 show FO = "FO"


meet_max_val :: Valdom3 -> Valdom3 -> Valdom3
meet_max_val a b = min a b      
meet_min_val :: Valdom3 -> Valdom3 -> Valdom3
meet_min_val  a b
	 | max a b /= FO = NO
	 | otherwise = min a b



meet_max :: [Valdom3] -> [Valdom3] -> [Valdom3]
meet_max [] [] = []
meet_max (a:aa) (b:bb) = ((meet_max_val a b):(meet_max aa bb))	 
	 
meet_min :: [Valdom3] -> [Valdom3] -> [Valdom3]
meet_min [] [] = []
meet_min (a:aa) (b:bb) = ((meet_min_val a b):(meet_min aa bb))	 
	 



meet_min_notBOT :: [Valdom3] -> [Valdom3] -> Bool
meet_min_notBOT a b = not (bot (meet_min a b))

meet_min_X :: [Valdom3] -> [Valdom3] -> Bool
meet_min_X a b = (meet_min a b) == a

meet_min_Y :: [Valdom3] -> [Valdom3] -> Bool
meet_min_Y a b = (meet_min a b) == b

meet_max_notBOT :: [Valdom3] -> [Valdom3] -> Bool
meet_max_notBOT a b = not (bot (meet_max a b)) 

meet_max_X :: [Valdom3] -> [Valdom3] -> Bool
meet_max_X a b = (meet_max a b) == a

meet_max_Y :: [Valdom3] -> [Valdom3] -> Bool
meet_max_Y a b = (meet_max a b) == b



bot :: [Valdom3] -> Bool
bot [] = True
bot (a:aa)  
    | a /= NO = False
    | otherwise = bot aa





------------------------------------------------------------------------------
-- L(X)
left :: [Valdom3] -> [Valdom3]
left (a:aa) 
     | a==PO = (PO:(copy ((length aa)) NO))
     | a==FO = (NO:copy ((length aa)) NO)
     | a==NO = FO:(left aa) 

-- R(X)
right :: [Valdom3] -> [Valdom3]
right aa = reverse (left (reverse aa))


data Bool3 = T | M | F

instance Eq Bool3 where
	 T == T = True
	 M == M = True
	 F == F = True
	 _ == _ = False

instance Ord Bool3 where
	 F <= F = True
	 F <= M = True
	 F <= T = True
	 M <= M = True
	 M <= T = True
	 T <= T = True
	 _ <= _ = False

instance Show Bool3 where
	 show F = "F"
	 show M = "M"
	 show T = "T"


-- X << Y
leftOver :: [Valdom3] -> [Valdom3] -> Bool3
leftOver a b 
	 | ((meet_max (left a) (left b)) == (left a) && (meet_max (left a) (left b)) /= (left b)) = T
	 | ((meet_max (left a) (left b)) == (left a) && (meet_max (left a) (left b)) == (left b)) && ((meet_min (left a) (left b)) < (meet_max (left a) (left b))) = M
	 | otherwise = F

-- X >> Y
rightOver :: [Valdom3] -> [Valdom3] -> Bool3
rightOver a b 
	  | ((meet_max (right a) (right b)) == (right a) && (meet_max (right a) (right b)) /= (right b)) = T
	  | ((meet_max (right a) (right b)) == (right a) && (meet_max (right a) (right b)) == (right b)) && ((meet_min (right a) (right b)) < (meet_max (right a) (right b))) = M
	  |  otherwise  = F


-- X <| Y
rightIn :: [Valdom3] -> [Valdom3] -> Bool3
rightIn a b 
	| elem FO (meet_min (left a) b) = T
	| length (filter (NO /=) (meet_min (left a) b)) > 1 = T
	| length (filter (NO /=) (meet_min (left a) b)) == 1 = M	
	| otherwise = F

-- X |> Y
leftIn :: [Valdom3] -> [Valdom3] -> Bool3
leftIn a b 
       | elem FO (meet_min (right a) b) = T
       | length (filter (NO /=) (meet_min (right a) b)) > 1 = T
       | length (filter (NO /=) (meet_min (right a) b)) == 1 = M
       | otherwise = F



--gets the big value as first parameter, returns True if the big sticks out to the left
leftCheckFI :: [Valdom3] -> [Valdom3] -> Bool
leftCheckFI a b
	  | rightIn b a == T = True
	  | leftIn b a == T = False
	  | rightIn b a == M = True
	  | otherwise = leftCheckFO a b


rightCheckFI :: [Valdom3] -> [Valdom3] -> Bool
rightCheckFI a b
	   | leftIn b a == T = True 
	   | rightIn b a == T = False
	   | leftIn b a == M = True 
	   | otherwise = rightCheckFO a b



leftCheckFO :: [Valdom3] -> [Valdom3] -> Bool
leftCheckFO a b = (leftOver a b) /= F && (leftOver a b) >= (rightOver a b)

rightCheckFO :: [Valdom3] -> [Valdom3] -> Bool
rightCheckFO a b = (rightOver a b) /= F && (rightOver a b) > (leftOver a b)


-----------------------------------------------------------------------------

data Bool5 = T5 | FLO | FRO | FLI | FRI

instance Eq Bool5 where
	 T5 == T5 = True
	 FLO == FLO = True
	 FRO == FRO = True
	 FLI == FLI = True
	 FRI == FRI = True
	 _ == _ = False


instance Show Bool5 where
	 show T5 = "T5"
	 show FLO = "FLO"
	 show FRO = "FRO"
	 show FLI = "FLI"
	 show FRI = "FRI"


meet_min_notBOT_9 :: [Valdom3] -> [Valdom3] -> Bool5
meet_min_notBOT_9 a b 
		  | (meet_min_notBOT a b == False) && (leftCheckFO a b)  = FLO 
		  | (meet_min_notBOT a b == False) && (rightCheckFO a b)  = FRO   
		  | (meet_min_notBOT a b == True)  = T5 

meet_min_X_9 :: [Valdom3] -> [Valdom3] -> Bool5
meet_min_X_9 a b 
	     | (meet_min_X a b == False) && (meet_min_Y a b == False) && (leftCheckFO a b)  = FLO 
	     | (meet_min_X a b == False) && (meet_min_Y a b == True) && (leftCheckFI a b)  = FLI 
	     | (meet_min_X a b == False) && (meet_min_Y a b == False) && (rightCheckFO a b)   = FRO 
	     | (meet_min_X a b == False) && (meet_min_Y a b == True) && (rightCheckFI a b)  = FRI 
	     | (meet_min_X a b == True) = T5

meet_min_Y_9 :: [Valdom3] -> [Valdom3] -> Bool5
meet_min_Y_9 a b 
	     | (meet_min_Y a b == False) && (meet_min_X a b == False) && (leftCheckFO a b)  = FLO 
	     | (meet_min_Y a b == False) && (meet_min_X a b == True) && (rightCheckFI b a) = FLI 
	     | (meet_min_Y a b == False) && (meet_min_X a b == False) && (rightCheckFO a b)  = FRO 
	     | (meet_min_Y a b == False) && (meet_min_X a b == True) && (leftCheckFI b a)  = FRI 
	     | (meet_min_Y a b == True) = T5


meet_max_notBOT_9 :: [Valdom3] -> [Valdom3] -> Bool5
meet_max_notBOT_9 a b 
		  | (meet_max_notBOT a b == False) && (leftCheckFO a b)  = FLO 
		  | (meet_max_notBOT a b == False) && (rightCheckFO a b)  = FRO   
		  | (meet_max_notBOT a b == True)  = T5 

meet_max_X_9 :: [Valdom3] -> [Valdom3] -> Bool5
meet_max_X_9 a b 
	     | (meet_max_X a b == False) && (meet_max_Y a b == False) && (leftCheckFO a b)  = FLO 
	     | (meet_max_X a b == False) && (meet_max_Y a b == True) && (leftCheckFI a b)  = FLI 
	     | (meet_max_X a b == False) && (meet_max_Y a b == False) && (rightCheckFO a b)   = FRO 
	     | (meet_max_X a b == False) && (meet_max_Y a b == True) && (rightCheckFI a b)  = FRI 
	     | (meet_max_X a b == True) = T5

meet_max_Y_9 :: [Valdom3] -> [Valdom3] -> Bool5
meet_max_Y_9 a b 
	     | (meet_max_Y a b == False) && (meet_max_X a b == False) && (leftCheckFO a b)  = FLO 
	     | (meet_max_Y a b == False) && (meet_max_X a b == True) && (rightCheckFI b a) = FLI 
	     | (meet_max_Y a b == False) && (meet_max_X a b == False) && (rightCheckFO a b)  = FRO 
	     | (meet_max_Y a b == False) && (meet_max_X a b == True) && (leftCheckFI b a)  = FRI 
	     | (meet_max_Y a b == True) = T5




------------------------------------------------------------------------------

rcc9min :: [Valdom3] -> [Valdom3] -> RCC9T
rcc9min a b 
	| ((meet_min_notBOT_9 a b == FLO) && (meet_min_X_9 a b == FLO) && (meet_min_Y_9 a b) == FLO) = DRL9
	| ((meet_min_notBOT_9 a b == FRO) && (meet_min_X_9 a b == FRO) && (meet_min_Y_9 a b) == FRO) = DRR9
	| ((meet_min_notBOT_9 a b == T5) && (meet_min_X_9 a b == FLO) && (meet_min_Y_9 a b) == FLO) = POL9
	| ((meet_min_notBOT_9 a b == T5) && (meet_min_X_9 a b == FRO) && (meet_min_Y_9 a b) == FRO) = POR9
	| ((meet_min_notBOT_9 a b == T5) && (meet_min_X_9 a b == T5) && (meet_min_Y_9 a b) == FLI) = PPL9
	| ((meet_min_notBOT_9 a b == T5) && (meet_min_X_9 a b == T5) && (meet_min_Y_9 a b) == FRI) = PPR9
	| ((meet_min_notBOT_9 a b == T5) && (meet_min_X_9 a b == FLI) && (meet_min_Y_9 a b) == T5) = PPIL9
	| ((meet_min_notBOT_9 a b == T5) && (meet_min_X_9 a b == FRI) && (meet_min_Y_9 a b) == T5) = PPIR9
	| ((meet_min_notBOT_9 a b == T5) && (meet_min_X_9 a b == T5) && (meet_min_Y_9 a b) == T5) = EL9


rcc9max :: [Valdom3] -> [Valdom3] -> RCC9T
rcc9max a b 
	| ((meet_max_notBOT_9 a b == FLO) && (meet_max_X_9 a b == FLO) && (meet_max_Y_9 a b) == FLO) = DRL9
	| ((meet_max_notBOT_9 a b == FRO) && (meet_max_X_9 a b == FRO) && (meet_max_Y_9 a b) == FRO) = DRR9
	| ((meet_max_notBOT_9 a b == T5) && (meet_max_X_9 a b == FLO) && (meet_max_Y_9 a b) == FLO) = POL9
	| ((meet_max_notBOT_9 a b == T5) && (meet_max_X_9 a b == FRO) && (meet_max_Y_9 a b) == FRO) = POR9
	| ((meet_max_notBOT_9 a b == T5) && (meet_max_X_9 a b == T5) && (meet_max_Y_9 a b) == FLI) = PPL9
	| ((meet_max_notBOT_9 a b == T5) && (meet_max_X_9 a b == T5) && (meet_max_Y_9 a b) == FRI) = PPR9
	| ((meet_max_notBOT_9 a b == T5) && (meet_max_X_9 a b == FLI) && (meet_max_Y_9 a b) == T5) = PPIL9
	| ((meet_max_notBOT_9 a b == T5) && (meet_max_X_9 a b == FRI) && (meet_max_Y_9 a b) == T5) = PPIR9
	| ((meet_max_notBOT_9 a b == T5) && (meet_max_X_9 a b == T5) && (meet_max_Y_9 a b) == T5) = EL9




data RCC9T = DRL9 | DRR9 | POL9 | POR9 | EL9 | PPL9 | PPR9 | PPIL9 | PPIR9

instance Eq RCC9T where
	DRL9 == DRL9 = True
	DRR9 == DRR9 = True
	POL9 == POL9 = True
	POR9 == POR9 = True
	EL9 == EL9 = True
	PPL9 == PPL9 = True
	PPR9 == PPR9 = True
	PPIL9 == PPIL9 = True
	PPIR9 == PPIR9 = True
	_ == _ = False

instance Show RCC9T where
	 show DRL9 = "DRL9"
	 show DRR9 = "DRR9"
	 show POL9 = "POL9"
	 show POR9 = "POR9"
	 show EL9 = "EL9"
	 show PPL9 = "PPL9"
	 show PPR9 = "PPR9"
	 show PPIL9 = "PPIL9"
	 show PPIR9 = "PPIR9"


rcc9 :: [Valdom3] -> [Valdom3] -> (RCC9T,RCC9T)
rcc9 a b = (rcc9min a b,rcc9max a b) 

-----------------------------------------------------------------------------

    
	     


intervals = [[PO,NO,NO],[PO,PO,NO],[FO,NO,NO],[FO,PO,NO],[PO,FO,NO],[PO,FO,PO],[PO,FO,FO],[FO,FO,FO],[NO,FO,FO],[NO,PO,FO],[NO,PO,PO],[NO,PO,NO],[NO,NO,PO],[NO,FO,FO]]


--intervals = [[PO,NO],[PO,PO],[NO,PO],[FO,NO],[NO,FO],[FO,FO],[FO,PO],[PO,FO] ]

--intervals = [[PO],[FO]]

rels = [ (a,b,rcc9 a b) | a<-intervals, b<-intervals ]

compute_relation_pairs = nub [ (rcc9 a b) | a<-intervals, b<-intervals ]