{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE CPP, DeriveDataTypeable, DeriveGeneric #-}
{-# LANGUAGE Safe #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.IntervalRelation
-- Copyright   :  (c) Masahiro Sakai 2016
-- License     :  BSD-style
--
-- Maintainer  :  masahiro.sakai@gmail.com
-- Stability   :  provisional
-- Portability :  non-portable (CPP, DeriveDataTypeable, DeriveGeneric)
--
-- Interval relations and their algebra.
--
-----------------------------------------------------------------------------
module Data.IntervalRelation
  ( Relation(..)
  , invert
  )
  where

import Data.Data
import GHC.Generics (Generic)

-- | Describes how two intervals @x@ and @y@ can be related.
-- See [Allen's interval algebra](https://en.wikipedia.org/wiki/Allen%27s_interval_algebra)
-- and [Intervals and their relations](http://marcosh.github.io/post/2020/05/04/intervals-and-their-relations.html).
data Relation
  = Before
  -- ^ Any element of @x@ is smaller than any element of @y@,
  -- and intervals are not connected. In other words, there exists an element
  -- that is bigger than any element of @x@ and smaller than any element of @y@.
  | JustBefore
  -- ^ Any element of @x@ is smaller than any element of @y@,
  -- but intervals are connected and non-empty. This implies that intersection
  -- of intervals is empty, and union is a single interval.
  | Overlaps
  -- ^ Intersection of @x@ and @y@ is non-empty,
  -- @x@ start and finishes earlier than @y@. This implies that union
  -- is a single interval, and @x@ finishes no earlier than @y@ starts.
  | Starts
  -- ^ @x@ is a proper subset of @y@,
  -- and they share lower bounds.
  | During
  -- ^ @x@ is a proper subset of @y@,
  -- but they share neither lower nor upper bounds.
  | Finishes
  -- ^ @x@ is a proper subset of @y@,
  -- and they share upper bounds.
  | Equal
  -- ^ Intervals are equal.
  | FinishedBy
  -- ^ Inverse of 'Finishes'.
  | Contains
  -- ^ Inverse of 'During'.
  | StartedBy
  -- ^ Inverse of 'Starts'.
  | OverlappedBy
  -- ^ Inverse of 'Overlaps'.
  | JustAfter
  -- ^ Inverse of 'JustBefore'.
  | After
  -- ^ Inverse of 'Before'.
  deriving (Relation -> Relation -> Bool
(Relation -> Relation -> Bool)
-> (Relation -> Relation -> Bool) -> Eq Relation
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Relation -> Relation -> Bool
$c/= :: Relation -> Relation -> Bool
== :: Relation -> Relation -> Bool
$c== :: Relation -> Relation -> Bool
Eq, Eq Relation
Eq Relation
-> (Relation -> Relation -> Ordering)
-> (Relation -> Relation -> Bool)
-> (Relation -> Relation -> Bool)
-> (Relation -> Relation -> Bool)
-> (Relation -> Relation -> Bool)
-> (Relation -> Relation -> Relation)
-> (Relation -> Relation -> Relation)
-> Ord Relation
Relation -> Relation -> Bool
Relation -> Relation -> Ordering
Relation -> Relation -> Relation
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Relation -> Relation -> Relation
$cmin :: Relation -> Relation -> Relation
max :: Relation -> Relation -> Relation
$cmax :: Relation -> Relation -> Relation
>= :: Relation -> Relation -> Bool
$c>= :: Relation -> Relation -> Bool
> :: Relation -> Relation -> Bool
$c> :: Relation -> Relation -> Bool
<= :: Relation -> Relation -> Bool
$c<= :: Relation -> Relation -> Bool
< :: Relation -> Relation -> Bool
$c< :: Relation -> Relation -> Bool
compare :: Relation -> Relation -> Ordering
$ccompare :: Relation -> Relation -> Ordering
$cp1Ord :: Eq Relation
Ord, Int -> Relation
Relation -> Int
Relation -> [Relation]
Relation -> Relation
Relation -> Relation -> [Relation]
Relation -> Relation -> Relation -> [Relation]
(Relation -> Relation)
-> (Relation -> Relation)
-> (Int -> Relation)
-> (Relation -> Int)
-> (Relation -> [Relation])
-> (Relation -> Relation -> [Relation])
-> (Relation -> Relation -> [Relation])
-> (Relation -> Relation -> Relation -> [Relation])
-> Enum Relation
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
enumFromThenTo :: Relation -> Relation -> Relation -> [Relation]
$cenumFromThenTo :: Relation -> Relation -> Relation -> [Relation]
enumFromTo :: Relation -> Relation -> [Relation]
$cenumFromTo :: Relation -> Relation -> [Relation]
enumFromThen :: Relation -> Relation -> [Relation]
$cenumFromThen :: Relation -> Relation -> [Relation]
enumFrom :: Relation -> [Relation]
$cenumFrom :: Relation -> [Relation]
fromEnum :: Relation -> Int
$cfromEnum :: Relation -> Int
toEnum :: Int -> Relation
$ctoEnum :: Int -> Relation
pred :: Relation -> Relation
$cpred :: Relation -> Relation
succ :: Relation -> Relation
$csucc :: Relation -> Relation
Enum, Relation
Relation -> Relation -> Bounded Relation
forall a. a -> a -> Bounded a
maxBound :: Relation
$cmaxBound :: Relation
minBound :: Relation
$cminBound :: Relation
Bounded, Int -> Relation -> ShowS
[Relation] -> ShowS
Relation -> String
(Int -> Relation -> ShowS)
-> (Relation -> String) -> ([Relation] -> ShowS) -> Show Relation
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Relation] -> ShowS
$cshowList :: [Relation] -> ShowS
show :: Relation -> String
$cshow :: Relation -> String
showsPrec :: Int -> Relation -> ShowS
$cshowsPrec :: Int -> Relation -> ShowS
Show, ReadPrec [Relation]
ReadPrec Relation
Int -> ReadS Relation
ReadS [Relation]
(Int -> ReadS Relation)
-> ReadS [Relation]
-> ReadPrec Relation
-> ReadPrec [Relation]
-> Read Relation
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Relation]
$creadListPrec :: ReadPrec [Relation]
readPrec :: ReadPrec Relation
$creadPrec :: ReadPrec Relation
readList :: ReadS [Relation]
$creadList :: ReadS [Relation]
readsPrec :: Int -> ReadS Relation
$creadsPrec :: Int -> ReadS Relation
Read, (forall x. Relation -> Rep Relation x)
-> (forall x. Rep Relation x -> Relation) -> Generic Relation
forall x. Rep Relation x -> Relation
forall x. Relation -> Rep Relation x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cto :: forall x. Rep Relation x -> Relation
$cfrom :: forall x. Relation -> Rep Relation x
Generic, Typeable Relation
DataType
Constr
Typeable Relation
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Relation -> c Relation)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c Relation)
-> (Relation -> Constr)
-> (Relation -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c Relation))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Relation))
-> ((forall b. Data b => b -> b) -> Relation -> Relation)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Relation -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Relation -> r)
-> (forall u. (forall d. Data d => d -> u) -> Relation -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> Relation -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Relation -> m Relation)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Relation -> m Relation)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Relation -> m Relation)
-> Data Relation
Relation -> DataType
Relation -> Constr
(forall b. Data b => b -> b) -> Relation -> Relation
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Relation -> c Relation
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Relation
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> Relation -> u
forall u. (forall d. Data d => d -> u) -> Relation -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Relation -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Relation -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Relation -> m Relation
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Relation -> m Relation
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Relation
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Relation -> c Relation
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Relation)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Relation)
$cAfter :: Constr
$cJustAfter :: Constr
$cOverlappedBy :: Constr
$cStartedBy :: Constr
$cContains :: Constr
$cFinishedBy :: Constr
$cEqual :: Constr
$cFinishes :: Constr
$cDuring :: Constr
$cStarts :: Constr
$cOverlaps :: Constr
$cJustBefore :: Constr
$cBefore :: Constr
$tRelation :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> Relation -> m Relation
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Relation -> m Relation
gmapMp :: (forall d. Data d => d -> m d) -> Relation -> m Relation
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Relation -> m Relation
gmapM :: (forall d. Data d => d -> m d) -> Relation -> m Relation
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Relation -> m Relation
gmapQi :: Int -> (forall d. Data d => d -> u) -> Relation -> u
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Relation -> u
gmapQ :: (forall d. Data d => d -> u) -> Relation -> [u]
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> Relation -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Relation -> r
$cgmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Relation -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Relation -> r
$cgmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Relation -> r
gmapT :: (forall b. Data b => b -> b) -> Relation -> Relation
$cgmapT :: (forall b. Data b => b -> b) -> Relation -> Relation
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Relation)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Relation)
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c Relation)
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Relation)
dataTypeOf :: Relation -> DataType
$cdataTypeOf :: Relation -> DataType
toConstr :: Relation -> Constr
$ctoConstr :: Relation -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Relation
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Relation
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Relation -> c Relation
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Relation -> c Relation
$cp1Data :: Typeable Relation
Data, Typeable)

-- | Inverts a relation, such that @'invert' ('Data.Interval.relate' x y) = 'Data.Interval.relate' y x@
invert :: Relation -> Relation
invert :: Relation -> Relation
invert Relation
relation = case Relation
relation of
  Relation
Before       -> Relation
After
  Relation
JustBefore   -> Relation
JustAfter
  Relation
Overlaps     -> Relation
OverlappedBy
  Relation
Starts       -> Relation
StartedBy
  Relation
During       -> Relation
Contains
  Relation
Finishes     -> Relation
FinishedBy
  Relation
Equal        -> Relation
Equal
  Relation
FinishedBy   -> Relation
Finishes
  Relation
Contains     -> Relation
During
  Relation
StartedBy    -> Relation
Starts
  Relation
OverlappedBy -> Relation
Overlaps
  Relation
JustAfter    -> Relation
JustBefore
  Relation
After        -> Relation
Before