{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE 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
$c== :: Relation -> Relation -> Bool
== :: Relation -> Relation -> Bool
$c/= :: Relation -> Relation -> Bool
/= :: 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
$ccompare :: Relation -> Relation -> Ordering
compare :: Relation -> Relation -> Ordering
$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
>= :: Relation -> Relation -> Bool
$cmax :: Relation -> Relation -> Relation
max :: Relation -> Relation -> Relation
$cmin :: Relation -> Relation -> Relation
min :: Relation -> Relation -> 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
$csucc :: Relation -> Relation
succ :: Relation -> Relation
$cpred :: Relation -> Relation
pred :: Relation -> Relation
$ctoEnum :: Int -> Relation
toEnum :: Int -> Relation
$cfromEnum :: Relation -> Int
fromEnum :: Relation -> Int
$cenumFrom :: Relation -> [Relation]
enumFrom :: Relation -> [Relation]
$cenumFromThen :: Relation -> Relation -> [Relation]
enumFromThen :: Relation -> Relation -> [Relation]
$cenumFromTo :: Relation -> Relation -> [Relation]
enumFromTo :: Relation -> Relation -> [Relation]
$cenumFromThenTo :: Relation -> Relation -> Relation -> [Relation]
enumFromThenTo :: Relation -> Relation -> Relation -> [Relation]
Enum, Relation
Relation -> Relation -> Bounded Relation
forall a. a -> a -> Bounded a
$cminBound :: Relation
minBound :: Relation
$cmaxBound :: Relation
maxBound :: 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
$cshowsPrec :: Int -> Relation -> ShowS
showsPrec :: Int -> Relation -> ShowS
$cshow :: Relation -> String
show :: Relation -> String
$cshowList :: [Relation] -> ShowS
showList :: [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
$creadsPrec :: Int -> ReadS Relation
readsPrec :: Int -> ReadS Relation
$creadList :: ReadS [Relation]
readList :: ReadS [Relation]
$creadPrec :: ReadPrec Relation
readPrec :: ReadPrec Relation
$creadListPrec :: ReadPrec [Relation]
readListPrec :: ReadPrec [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
$cfrom :: forall x. Relation -> Rep Relation x
from :: forall x. Relation -> Rep Relation x
$cto :: forall x. Rep Relation x -> Relation
to :: forall x. Rep Relation x -> Relation
Generic, Typeable Relation
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 -> Constr
Relation -> DataType
(forall b. Data b => b -> b) -> Relation -> 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)
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Relation -> c Relation
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Relation -> c Relation
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Relation
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Relation
$ctoConstr :: Relation -> Constr
toConstr :: Relation -> Constr
$cdataTypeOf :: Relation -> DataType
dataTypeOf :: Relation -> DataType
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Relation)
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Relation)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Relation)
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Relation)
$cgmapT :: (forall b. Data b => b -> b) -> Relation -> Relation
gmapT :: (forall b. Data b => b -> b) -> Relation -> Relation
$cgmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Relation -> r
gmapQl :: forall r r'.
(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
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Relation -> r
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> Relation -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> Relation -> [u]
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Relation -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Relation -> u
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Relation -> m Relation
gmapM :: forall (m :: * -> *).
Monad m =>
(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
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(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
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Relation -> m 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