{-# LANGUAGE TypeSynonymInstances, FlexibleInstances, DeriveDataTypeable #-}
{- |
Module      :  ./CSL/TreePO.hs
Description :  Handling of tree-like partial ordering relations
Copyright   :  (c) Ewaryst Schulz, DFKI Bremen 2010
License     :  GPLv2 or higher, see LICENSE.txt

Maintainer  :  ewaryst.schulz@dfki.de
Stability   :  experimental
Portability :  portable

This module defines a basic datatype for tree-like partial orderings such as
encountered, e.g., in the set lattice.
 -}

module CSL.TreePO
{- ( Incomparable (..)
    , SetOrdering (..)
    , SetOrInterval (..)
    , swapCompare
    , swapCmp
    , combineCmp
    ) -}
    where

import Data.Data
import qualified Data.Set as Set

{- ----------------------------------------------------------------------
Datatypes for comparison
---------------------------------------------------------------------- -}

data Incomparable = Disjoint | Overlap deriving (Incomparable -> Incomparable -> Bool
(Incomparable -> Incomparable -> Bool)
-> (Incomparable -> Incomparable -> Bool) -> Eq Incomparable
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Incomparable -> Incomparable -> Bool
$c/= :: Incomparable -> Incomparable -> Bool
== :: Incomparable -> Incomparable -> Bool
$c== :: Incomparable -> Incomparable -> Bool
Eq, Int -> Incomparable -> ShowS
[Incomparable] -> ShowS
Incomparable -> String
(Int -> Incomparable -> ShowS)
-> (Incomparable -> String)
-> ([Incomparable] -> ShowS)
-> Show Incomparable
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Incomparable] -> ShowS
$cshowList :: [Incomparable] -> ShowS
show :: Incomparable -> String
$cshow :: Incomparable -> String
showsPrec :: Int -> Incomparable -> ShowS
$cshowsPrec :: Int -> Incomparable -> ShowS
Show, Typeable, Typeable Incomparable
Constr
DataType
Typeable Incomparable =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> Incomparable -> c Incomparable)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c Incomparable)
-> (Incomparable -> Constr)
-> (Incomparable -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c Incomparable))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c Incomparable))
-> ((forall b. Data b => b -> b) -> Incomparable -> Incomparable)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Incomparable -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Incomparable -> r)
-> (forall u. (forall d. Data d => d -> u) -> Incomparable -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> Incomparable -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable)
-> Data Incomparable
Incomparable -> Constr
Incomparable -> DataType
(forall b. Data b => b -> b) -> Incomparable -> Incomparable
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Incomparable -> c Incomparable
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Incomparable
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) -> Incomparable -> u
forall u. (forall d. Data d => d -> u) -> Incomparable -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Incomparable -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Incomparable -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Incomparable -> m Incomparable
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Incomparable -> m Incomparable
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Incomparable
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Incomparable -> c Incomparable
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Incomparable)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c Incomparable)
$cOverlap :: Constr
$cDisjoint :: Constr
$tIncomparable :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Incomparable -> m Incomparable
gmapMp :: (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Incomparable -> m Incomparable
gmapM :: (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Incomparable -> m Incomparable
gmapQi :: Int -> (forall d. Data d => d -> u) -> Incomparable -> u
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Incomparable -> u
gmapQ :: (forall d. Data d => d -> u) -> Incomparable -> [u]
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> Incomparable -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Incomparable -> r
$cgmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Incomparable -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Incomparable -> r
$cgmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Incomparable -> r
gmapT :: (forall b. Data b => b -> b) -> Incomparable -> Incomparable
$cgmapT :: (forall b. Data b => b -> b) -> Incomparable -> Incomparable
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c Incomparable)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c Incomparable)
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c Incomparable)
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Incomparable)
dataTypeOf :: Incomparable -> DataType
$cdataTypeOf :: Incomparable -> DataType
toConstr :: Incomparable -> Constr
$ctoConstr :: Incomparable -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Incomparable
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Incomparable
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Incomparable -> c Incomparable
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Incomparable -> c Incomparable
$cp1Data :: Typeable Incomparable
Data)

data SetOrdering = Comparable Ordering | Incomparable Incomparable
  deriving (SetOrdering -> SetOrdering -> Bool
(SetOrdering -> SetOrdering -> Bool)
-> (SetOrdering -> SetOrdering -> Bool) -> Eq SetOrdering
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SetOrdering -> SetOrdering -> Bool
$c/= :: SetOrdering -> SetOrdering -> Bool
== :: SetOrdering -> SetOrdering -> Bool
$c== :: SetOrdering -> SetOrdering -> Bool
Eq, Typeable, Typeable SetOrdering
Constr
DataType
Typeable SetOrdering =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> SetOrdering -> c SetOrdering)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c SetOrdering)
-> (SetOrdering -> Constr)
-> (SetOrdering -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c SetOrdering))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c SetOrdering))
-> ((forall b. Data b => b -> b) -> SetOrdering -> SetOrdering)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r)
-> (forall u. (forall d. Data d => d -> u) -> SetOrdering -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> SetOrdering -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering)
-> Data SetOrdering
SetOrdering -> Constr
SetOrdering -> DataType
(forall b. Data b => b -> b) -> SetOrdering -> SetOrdering
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetOrdering -> c SetOrdering
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c SetOrdering
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) -> SetOrdering -> u
forall u. (forall d. Data d => d -> u) -> SetOrdering -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrdering -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrdering -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c SetOrdering
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetOrdering -> c SetOrdering
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c SetOrdering)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c SetOrdering)
$cIncomparable :: Constr
$cComparable :: Constr
$tSetOrdering :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering
gmapMp :: (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering
gmapM :: (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering
gmapQi :: Int -> (forall d. Data d => d -> u) -> SetOrdering -> u
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> SetOrdering -> u
gmapQ :: (forall d. Data d => d -> u) -> SetOrdering -> [u]
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> SetOrdering -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrdering -> r
$cgmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrdering -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrdering -> r
$cgmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrdering -> r
gmapT :: (forall b. Data b => b -> b) -> SetOrdering -> SetOrdering
$cgmapT :: (forall b. Data b => b -> b) -> SetOrdering -> SetOrdering
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c SetOrdering)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c SetOrdering)
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c SetOrdering)
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c SetOrdering)
dataTypeOf :: SetOrdering -> DataType
$cdataTypeOf :: SetOrdering -> DataType
toConstr :: SetOrdering -> Constr
$ctoConstr :: SetOrdering -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c SetOrdering
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c SetOrdering
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetOrdering -> c SetOrdering
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetOrdering -> c SetOrdering
$cp1Data :: Typeable SetOrdering
Data)

instance Show SetOrdering where
    show :: SetOrdering -> String
show (Comparable LT) = "<"
    show (Comparable GT) = ">"
    show (Comparable EQ) = "="
    show (Incomparable x :: Incomparable
x) = Incomparable -> String
forall a. Show a => a -> String
show Incomparable
x


{- | We represent Intervals with opened or closed end points over a linearly
   ordered type 'a' as closed intervals over the type '(a, InfDev)', for
   infinitesimal deviation.
   - '(x, EpsLeft)' means an epsilon to the left of x
   - '(x, Zero)' means x
   - '(x, EpsRight)' means an epsilon to the right of x
   We have EpsLeft < Zero < EpsRight and the ordering of 'a' lifts to the
   lexicographical ordering of '(a, InfDev)' which captures well our intended
   meaning.
   We inject the type 'a' into the type '(a, InfDev)'
   by mapping 'x' to '(x, Zero)'.
   The mapping of intrvals is as follows:
   A left opened interval starting at x becomes a left closed interval starting
   at '(x, EpsRight)'.
   We have:
   'forall y > x. (y, _) > (x, EpsRight)', hence in particular
   '(y, Zero) > (x, EpsRight)'
   but also
   '(x, Zero) < (x, EpsRight)'

   Analogously we represent a right opened one ending at y as a closed one
   ending at '(x, EpsLeft)'.
-}
data InfDev = EpsLeft | Zero | EpsRight deriving (InfDev -> InfDev -> Bool
(InfDev -> InfDev -> Bool)
-> (InfDev -> InfDev -> Bool) -> Eq InfDev
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: InfDev -> InfDev -> Bool
$c/= :: InfDev -> InfDev -> Bool
== :: InfDev -> InfDev -> Bool
$c== :: InfDev -> InfDev -> Bool
Eq, Int -> InfDev -> ShowS
[InfDev] -> ShowS
InfDev -> String
(Int -> InfDev -> ShowS)
-> (InfDev -> String) -> ([InfDev] -> ShowS) -> Show InfDev
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [InfDev] -> ShowS
$cshowList :: [InfDev] -> ShowS
show :: InfDev -> String
$cshow :: InfDev -> String
showsPrec :: Int -> InfDev -> ShowS
$cshowsPrec :: Int -> InfDev -> ShowS
Show, Typeable, Typeable InfDev
Constr
DataType
Typeable InfDev =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> InfDev -> c InfDev)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c InfDev)
-> (InfDev -> Constr)
-> (InfDev -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c InfDev))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfDev))
-> ((forall b. Data b => b -> b) -> InfDev -> InfDev)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> InfDev -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> InfDev -> r)
-> (forall u. (forall d. Data d => d -> u) -> InfDev -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> InfDev -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> InfDev -> m InfDev)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> InfDev -> m InfDev)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> InfDev -> m InfDev)
-> Data InfDev
InfDev -> Constr
InfDev -> DataType
(forall b. Data b => b -> b) -> InfDev -> InfDev
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> InfDev -> c InfDev
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c InfDev
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) -> InfDev -> u
forall u. (forall d. Data d => d -> u) -> InfDev -> [u]
forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r
forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> InfDev -> m InfDev
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> InfDev -> m InfDev
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c InfDev
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> InfDev -> c InfDev
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c InfDev)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfDev)
$cEpsRight :: Constr
$cZero :: Constr
$cEpsLeft :: Constr
$tInfDev :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> InfDev -> m InfDev
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> InfDev -> m InfDev
gmapMp :: (forall d. Data d => d -> m d) -> InfDev -> m InfDev
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> InfDev -> m InfDev
gmapM :: (forall d. Data d => d -> m d) -> InfDev -> m InfDev
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> InfDev -> m InfDev
gmapQi :: Int -> (forall d. Data d => d -> u) -> InfDev -> u
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> InfDev -> u
gmapQ :: (forall d. Data d => d -> u) -> InfDev -> [u]
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> InfDev -> [u]
gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r
$cgmapQr :: forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r
gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r
$cgmapQl :: forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r
gmapT :: (forall b. Data b => b -> b) -> InfDev -> InfDev
$cgmapT :: (forall b. Data b => b -> b) -> InfDev -> InfDev
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfDev)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfDev)
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c InfDev)
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c InfDev)
dataTypeOf :: InfDev -> DataType
$cdataTypeOf :: InfDev -> DataType
toConstr :: InfDev -> Constr
$ctoConstr :: InfDev -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c InfDev
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c InfDev
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> InfDev -> c InfDev
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> InfDev -> c InfDev
$cp1Data :: Typeable InfDev
Data)

instance Ord InfDev where
    compare :: InfDev -> InfDev -> Ordering
compare x :: InfDev
x y :: InfDev
y
        | InfDev
x InfDev -> InfDev -> Bool
forall a. Eq a => a -> a -> Bool
== InfDev
y = Ordering
EQ
        | Bool
otherwise =
            case (InfDev
x, InfDev
y) of
              (EpsLeft, _) -> Ordering
LT
              (EpsRight, _) -> Ordering
GT
              _ -> Ordering -> Ordering
swapCompare (Ordering -> Ordering) -> Ordering -> Ordering
forall a b. (a -> b) -> a -> b
$ InfDev -> InfDev -> Ordering
forall a. Ord a => a -> a -> Ordering
compare InfDev
y InfDev
x

newtype CIType a = CIType (a, InfDev) deriving (CIType a -> CIType a -> Bool
(CIType a -> CIType a -> Bool)
-> (CIType a -> CIType a -> Bool) -> Eq (CIType a)
forall a. Eq a => CIType a -> CIType a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: CIType a -> CIType a -> Bool
$c/= :: forall a. Eq a => CIType a -> CIType a -> Bool
== :: CIType a -> CIType a -> Bool
$c== :: forall a. Eq a => CIType a -> CIType a -> Bool
Eq, Int -> CIType a -> ShowS
[CIType a] -> ShowS
CIType a -> String
(Int -> CIType a -> ShowS)
-> (CIType a -> String) -> ([CIType a] -> ShowS) -> Show (CIType a)
forall a. Show a => Int -> CIType a -> ShowS
forall a. Show a => [CIType a] -> ShowS
forall a. Show a => CIType a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [CIType a] -> ShowS
$cshowList :: forall a. Show a => [CIType a] -> ShowS
show :: CIType a -> String
$cshow :: forall a. Show a => CIType a -> String
showsPrec :: Int -> CIType a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> CIType a -> ShowS
Show, Typeable, Typeable (CIType a)
Constr
DataType
Typeable (CIType a) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> CIType a -> c (CIType a))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (CIType a))
-> (CIType a -> Constr)
-> (CIType a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (CIType a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (CIType a)))
-> ((forall b. Data b => b -> b) -> CIType a -> CIType a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> CIType a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> CIType a -> r)
-> (forall u. (forall d. Data d => d -> u) -> CIType a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> CIType a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> CIType a -> m (CIType a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> CIType a -> m (CIType a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> CIType a -> m (CIType a))
-> Data (CIType a)
CIType a -> Constr
CIType a -> DataType
(forall d. Data d => c (t d)) -> Maybe (c (CIType a))
(forall b. Data b => b -> b) -> CIType a -> CIType a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> CIType a -> c (CIType a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (CIType a)
forall a. Data a => Typeable (CIType a)
forall a. Data a => CIType a -> Constr
forall a. Data a => CIType a -> DataType
forall a.
Data a =>
(forall b. Data b => b -> b) -> CIType a -> CIType a
forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> CIType a -> u
forall a u.
Data a =>
(forall d. Data d => d -> u) -> CIType a -> [u]
forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> CIType a -> r
forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> CIType a -> r
forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (CIType a)
forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> CIType a -> c (CIType a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (CIType a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a))
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) -> CIType a -> u
forall u. (forall d. Data d => d -> u) -> CIType a -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> CIType a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> CIType a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (CIType a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> CIType a -> c (CIType a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (CIType a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a))
$cCIType :: Constr
$tCIType :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
gmapMp :: (forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
gmapM :: (forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> CIType a -> m (CIType a)
gmapQi :: Int -> (forall d. Data d => d -> u) -> CIType a -> u
$cgmapQi :: forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> CIType a -> u
gmapQ :: (forall d. Data d => d -> u) -> CIType a -> [u]
$cgmapQ :: forall a u.
Data a =>
(forall d. Data d => d -> u) -> CIType a -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> CIType a -> r
$cgmapQr :: forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> CIType a -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> CIType a -> r
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> CIType a -> r
gmapT :: (forall b. Data b => b -> b) -> CIType a -> CIType a
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b) -> CIType a -> CIType a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (CIType a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (CIType a))
dataTypeOf :: CIType a -> DataType
$cdataTypeOf :: forall a. Data a => CIType a -> DataType
toConstr :: CIType a -> Constr
$ctoConstr :: forall a. Data a => CIType a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (CIType a)
$cgunfold :: forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (CIType a)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> CIType a -> c (CIType a)
$cgfoldl :: forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> CIType a -> c (CIType a)
$cp1Data :: forall a. Data a => Typeable (CIType a)
Data)

{- | This type with the given ordering is to represent opened/closed intervals
over 'a' as closed intervals over '(a, InfDev)' -}
instance Ord a => Ord (CIType a) where
    compare :: CIType a -> CIType a -> Ordering
compare (CIType (x :: a
x, a :: InfDev
a)) (CIType (y :: a
y, b :: InfDev
b)) =
        case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
          EQ -> InfDev -> InfDev -> Ordering
forall a. Ord a => a -> a -> Ordering
compare InfDev
a InfDev
b
          res :: Ordering
res -> Ordering
res


-- | A finite set or an interval. True = closed, False = opened interval border.
data SetOrInterval a = Set (Set.Set a)
                     | IntVal (a, Bool) (a, Bool)
                       deriving (SetOrInterval a -> SetOrInterval a -> Bool
(SetOrInterval a -> SetOrInterval a -> Bool)
-> (SetOrInterval a -> SetOrInterval a -> Bool)
-> Eq (SetOrInterval a)
forall a. Eq a => SetOrInterval a -> SetOrInterval a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SetOrInterval a -> SetOrInterval a -> Bool
$c/= :: forall a. Eq a => SetOrInterval a -> SetOrInterval a -> Bool
== :: SetOrInterval a -> SetOrInterval a -> Bool
$c== :: forall a. Eq a => SetOrInterval a -> SetOrInterval a -> Bool
Eq, Eq (SetOrInterval a)
Eq (SetOrInterval a) =>
(SetOrInterval a -> SetOrInterval a -> Ordering)
-> (SetOrInterval a -> SetOrInterval a -> Bool)
-> (SetOrInterval a -> SetOrInterval a -> Bool)
-> (SetOrInterval a -> SetOrInterval a -> Bool)
-> (SetOrInterval a -> SetOrInterval a -> Bool)
-> (SetOrInterval a -> SetOrInterval a -> SetOrInterval a)
-> (SetOrInterval a -> SetOrInterval a -> SetOrInterval a)
-> Ord (SetOrInterval a)
SetOrInterval a -> SetOrInterval a -> Bool
SetOrInterval a -> SetOrInterval a -> Ordering
SetOrInterval a -> SetOrInterval a -> SetOrInterval a
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
forall a. Ord a => Eq (SetOrInterval a)
forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool
forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Ordering
forall a.
Ord a =>
SetOrInterval a -> SetOrInterval a -> SetOrInterval a
min :: SetOrInterval a -> SetOrInterval a -> SetOrInterval a
$cmin :: forall a.
Ord a =>
SetOrInterval a -> SetOrInterval a -> SetOrInterval a
max :: SetOrInterval a -> SetOrInterval a -> SetOrInterval a
$cmax :: forall a.
Ord a =>
SetOrInterval a -> SetOrInterval a -> SetOrInterval a
>= :: SetOrInterval a -> SetOrInterval a -> Bool
$c>= :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool
> :: SetOrInterval a -> SetOrInterval a -> Bool
$c> :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool
<= :: SetOrInterval a -> SetOrInterval a -> Bool
$c<= :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool
< :: SetOrInterval a -> SetOrInterval a -> Bool
$c< :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool
compare :: SetOrInterval a -> SetOrInterval a -> Ordering
$ccompare :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (SetOrInterval a)
Ord, Int -> SetOrInterval a -> ShowS
[SetOrInterval a] -> ShowS
SetOrInterval a -> String
(Int -> SetOrInterval a -> ShowS)
-> (SetOrInterval a -> String)
-> ([SetOrInterval a] -> ShowS)
-> Show (SetOrInterval a)
forall a. Show a => Int -> SetOrInterval a -> ShowS
forall a. Show a => [SetOrInterval a] -> ShowS
forall a. Show a => SetOrInterval a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [SetOrInterval a] -> ShowS
$cshowList :: forall a. Show a => [SetOrInterval a] -> ShowS
show :: SetOrInterval a -> String
$cshow :: forall a. Show a => SetOrInterval a -> String
showsPrec :: Int -> SetOrInterval a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> SetOrInterval a -> ShowS
Show, Typeable, Typeable (SetOrInterval a)
Constr
DataType
Typeable (SetOrInterval a) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (SetOrInterval a))
-> (SetOrInterval a -> Constr)
-> (SetOrInterval a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (SetOrInterval a)))
-> ((forall b. Data b => b -> b)
    -> SetOrInterval a -> SetOrInterval a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r)
-> (forall u.
    (forall d. Data d => d -> u) -> SetOrInterval a -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d)
    -> SetOrInterval a -> m (SetOrInterval a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> SetOrInterval a -> m (SetOrInterval a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> SetOrInterval a -> m (SetOrInterval a))
-> Data (SetOrInterval a)
SetOrInterval a -> Constr
SetOrInterval a -> DataType
(forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a))
(forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetOrInterval a)
forall a. (Data a, Ord a) => Typeable (SetOrInterval a)
forall a. (Data a, Ord a) => SetOrInterval a -> Constr
forall a. (Data a, Ord a) => SetOrInterval a -> DataType
forall a.
(Data a, Ord a) =>
(forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a
forall a u.
(Data a, Ord a) =>
Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u
forall a u.
(Data a, Ord a) =>
(forall d. Data d => d -> u) -> SetOrInterval a -> [u]
forall a r r'.
(Data a, Ord a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r
forall a r r'.
(Data a, Ord a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r
forall a (m :: * -> *).
(Data a, Ord a, Monad m) =>
(forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
forall a (m :: * -> *).
(Data a, Ord a, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
forall a (c :: * -> *).
(Data a, Ord a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetOrInterval a)
forall a (c :: * -> *).
(Data a, Ord a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SetOrInterval a))
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) -> SetOrInterval a -> u
forall u. (forall d. Data d => d -> u) -> SetOrInterval a -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetOrInterval a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SetOrInterval a))
$cIntVal :: Constr
$cSet :: Constr
$tSetOrInterval :: DataType
gmapMo :: (forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, Ord a, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
gmapMp :: (forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, Ord a, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
gmapM :: (forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Ord a, Monad m) =>
(forall d. Data d => d -> m d)
-> SetOrInterval a -> m (SetOrInterval a)
gmapQi :: Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u
$cgmapQi :: forall a u.
(Data a, Ord a) =>
Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u
gmapQ :: (forall d. Data d => d -> u) -> SetOrInterval a -> [u]
$cgmapQ :: forall a u.
(Data a, Ord a) =>
(forall d. Data d => d -> u) -> SetOrInterval a -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r
$cgmapQr :: forall a r r'.
(Data a, Ord a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r
$cgmapQl :: forall a r r'.
(Data a, Ord a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r
gmapT :: (forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a
$cgmapT :: forall a.
(Data a, Ord a) =>
(forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SetOrInterval a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SetOrInterval a))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a))
dataTypeOf :: SetOrInterval a -> DataType
$cdataTypeOf :: forall a. (Data a, Ord a) => SetOrInterval a -> DataType
toConstr :: SetOrInterval a -> Constr
$ctoConstr :: forall a. (Data a, Ord a) => SetOrInterval a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetOrInterval a)
$cgunfold :: forall a (c :: * -> *).
(Data a, Ord a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SetOrInterval a)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a)
$cgfoldl :: forall a (c :: * -> *).
(Data a, Ord a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a)
$cp1Data :: forall a. (Data a, Ord a) => Typeable (SetOrInterval a)
Data)

-- | A closed interval
data ClosedInterval a = ClosedInterval a a
  deriving (ClosedInterval a -> ClosedInterval a -> Bool
(ClosedInterval a -> ClosedInterval a -> Bool)
-> (ClosedInterval a -> ClosedInterval a -> Bool)
-> Eq (ClosedInterval a)
forall a. Eq a => ClosedInterval a -> ClosedInterval a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ClosedInterval a -> ClosedInterval a -> Bool
$c/= :: forall a. Eq a => ClosedInterval a -> ClosedInterval a -> Bool
== :: ClosedInterval a -> ClosedInterval a -> Bool
$c== :: forall a. Eq a => ClosedInterval a -> ClosedInterval a -> Bool
Eq, Eq (ClosedInterval a)
Eq (ClosedInterval a) =>
(ClosedInterval a -> ClosedInterval a -> Ordering)
-> (ClosedInterval a -> ClosedInterval a -> Bool)
-> (ClosedInterval a -> ClosedInterval a -> Bool)
-> (ClosedInterval a -> ClosedInterval a -> Bool)
-> (ClosedInterval a -> ClosedInterval a -> Bool)
-> (ClosedInterval a -> ClosedInterval a -> ClosedInterval a)
-> (ClosedInterval a -> ClosedInterval a -> ClosedInterval a)
-> Ord (ClosedInterval a)
ClosedInterval a -> ClosedInterval a -> Bool
ClosedInterval a -> ClosedInterval a -> Ordering
ClosedInterval a -> ClosedInterval a -> ClosedInterval a
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
forall a. Ord a => Eq (ClosedInterval a)
forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool
forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Ordering
forall a.
Ord a =>
ClosedInterval a -> ClosedInterval a -> ClosedInterval a
min :: ClosedInterval a -> ClosedInterval a -> ClosedInterval a
$cmin :: forall a.
Ord a =>
ClosedInterval a -> ClosedInterval a -> ClosedInterval a
max :: ClosedInterval a -> ClosedInterval a -> ClosedInterval a
$cmax :: forall a.
Ord a =>
ClosedInterval a -> ClosedInterval a -> ClosedInterval a
>= :: ClosedInterval a -> ClosedInterval a -> Bool
$c>= :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool
> :: ClosedInterval a -> ClosedInterval a -> Bool
$c> :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool
<= :: ClosedInterval a -> ClosedInterval a -> Bool
$c<= :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool
< :: ClosedInterval a -> ClosedInterval a -> Bool
$c< :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool
compare :: ClosedInterval a -> ClosedInterval a -> Ordering
$ccompare :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (ClosedInterval a)
Ord, Int -> ClosedInterval a -> ShowS
[ClosedInterval a] -> ShowS
ClosedInterval a -> String
(Int -> ClosedInterval a -> ShowS)
-> (ClosedInterval a -> String)
-> ([ClosedInterval a] -> ShowS)
-> Show (ClosedInterval a)
forall a. Show a => Int -> ClosedInterval a -> ShowS
forall a. Show a => [ClosedInterval a] -> ShowS
forall a. Show a => ClosedInterval a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ClosedInterval a] -> ShowS
$cshowList :: forall a. Show a => [ClosedInterval a] -> ShowS
show :: ClosedInterval a -> String
$cshow :: forall a. Show a => ClosedInterval a -> String
showsPrec :: Int -> ClosedInterval a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> ClosedInterval a -> ShowS
Show, Typeable, Typeable (ClosedInterval a)
Constr
DataType
Typeable (ClosedInterval a) =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g)
 -> ClosedInterval a
 -> c (ClosedInterval a))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (ClosedInterval a))
-> (ClosedInterval a -> Constr)
-> (ClosedInterval a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (ClosedInterval a)))
-> ((forall b. Data b => b -> b)
    -> ClosedInterval a -> ClosedInterval a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r)
-> (forall u.
    (forall d. Data d => d -> u) -> ClosedInterval a -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d)
    -> ClosedInterval a -> m (ClosedInterval a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> ClosedInterval a -> m (ClosedInterval a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> ClosedInterval a -> m (ClosedInterval a))
-> Data (ClosedInterval a)
ClosedInterval a -> Constr
ClosedInterval a -> DataType
(forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a))
(forall b. Data b => b -> b)
-> ClosedInterval a -> ClosedInterval a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (ClosedInterval a)
forall a. Data a => Typeable (ClosedInterval a)
forall a. Data a => ClosedInterval a -> Constr
forall a. Data a => ClosedInterval a -> DataType
forall a.
Data a =>
(forall b. Data b => b -> b)
-> ClosedInterval a -> ClosedInterval a
forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u
forall a u.
Data a =>
(forall d. Data d => d -> u) -> ClosedInterval a -> [u]
forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r
forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r
forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (ClosedInterval a)
forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (ClosedInterval a))
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) -> ClosedInterval a -> u
forall u. (forall d. Data d => d -> u) -> ClosedInterval a -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (ClosedInterval a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (ClosedInterval a))
$cClosedInterval :: Constr
$tClosedInterval :: DataType
gmapMo :: (forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
gmapMp :: (forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
gmapM :: (forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d)
-> ClosedInterval a -> m (ClosedInterval a)
gmapQi :: Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u
$cgmapQi :: forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u
gmapQ :: (forall d. Data d => d -> u) -> ClosedInterval a -> [u]
$cgmapQ :: forall a u.
Data a =>
(forall d. Data d => d -> u) -> ClosedInterval a -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r
$cgmapQr :: forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r
gmapT :: (forall b. Data b => b -> b)
-> ClosedInterval a -> ClosedInterval a
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b)
-> ClosedInterval a -> ClosedInterval a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (ClosedInterval a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (ClosedInterval a))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a))
dataTypeOf :: ClosedInterval a -> DataType
$cdataTypeOf :: forall a. Data a => ClosedInterval a -> DataType
toConstr :: ClosedInterval a -> Constr
$ctoConstr :: forall a. Data a => ClosedInterval a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (ClosedInterval a)
$cgunfold :: forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (ClosedInterval a)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a)
$cgfoldl :: forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a)
$cp1Data :: forall a. Data a => Typeable (ClosedInterval a)
Data)

-- | Infinite integers = integers augmented by -Infty and +Infty
data InfInt = PosInf | NegInf | FinInt Integer
  deriving (Int -> InfInt -> ShowS
[InfInt] -> ShowS
InfInt -> String
(Int -> InfInt -> ShowS)
-> (InfInt -> String) -> ([InfInt] -> ShowS) -> Show InfInt
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [InfInt] -> ShowS
$cshowList :: [InfInt] -> ShowS
show :: InfInt -> String
$cshow :: InfInt -> String
showsPrec :: Int -> InfInt -> ShowS
$cshowsPrec :: Int -> InfInt -> ShowS
Show, InfInt -> InfInt -> Bool
(InfInt -> InfInt -> Bool)
-> (InfInt -> InfInt -> Bool) -> Eq InfInt
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: InfInt -> InfInt -> Bool
$c/= :: InfInt -> InfInt -> Bool
== :: InfInt -> InfInt -> Bool
$c== :: InfInt -> InfInt -> Bool
Eq, Typeable, Typeable InfInt
Constr
DataType
Typeable InfInt =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> InfInt -> c InfInt)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c InfInt)
-> (InfInt -> Constr)
-> (InfInt -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c InfInt))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfInt))
-> ((forall b. Data b => b -> b) -> InfInt -> InfInt)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> InfInt -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> InfInt -> r)
-> (forall u. (forall d. Data d => d -> u) -> InfInt -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> InfInt -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> InfInt -> m InfInt)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> InfInt -> m InfInt)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> InfInt -> m InfInt)
-> Data InfInt
InfInt -> Constr
InfInt -> DataType
(forall b. Data b => b -> b) -> InfInt -> InfInt
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> InfInt -> c InfInt
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c InfInt
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) -> InfInt -> u
forall u. (forall d. Data d => d -> u) -> InfInt -> [u]
forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r
forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> InfInt -> m InfInt
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> InfInt -> m InfInt
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c InfInt
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> InfInt -> c InfInt
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c InfInt)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfInt)
$cFinInt :: Constr
$cNegInf :: Constr
$cPosInf :: Constr
$tInfInt :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> InfInt -> m InfInt
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> InfInt -> m InfInt
gmapMp :: (forall d. Data d => d -> m d) -> InfInt -> m InfInt
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> InfInt -> m InfInt
gmapM :: (forall d. Data d => d -> m d) -> InfInt -> m InfInt
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> InfInt -> m InfInt
gmapQi :: Int -> (forall d. Data d => d -> u) -> InfInt -> u
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> InfInt -> u
gmapQ :: (forall d. Data d => d -> u) -> InfInt -> [u]
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> InfInt -> [u]
gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r
$cgmapQr :: forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r
gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r
$cgmapQl :: forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r
gmapT :: (forall b. Data b => b -> b) -> InfInt -> InfInt
$cgmapT :: (forall b. Data b => b -> b) -> InfInt -> InfInt
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfInt)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfInt)
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c InfInt)
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c InfInt)
dataTypeOf :: InfInt -> DataType
$cdataTypeOf :: InfInt -> DataType
toConstr :: InfInt -> Constr
$ctoConstr :: InfInt -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c InfInt
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c InfInt
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> InfInt -> c InfInt
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> InfInt -> c InfInt
$cp1Data :: Typeable InfInt
Data)

instance Ord InfInt where
    compare :: InfInt -> InfInt -> Ordering
compare x :: InfInt
x y :: InfInt
y
        | InfInt
x InfInt -> InfInt -> Bool
forall a. Eq a => a -> a -> Bool
== InfInt
y = Ordering
EQ
        | Bool
otherwise =
            case (InfInt
x, InfInt
y) of
              (NegInf, _) -> Ordering
LT
              (PosInf, _) -> Ordering
GT
              (FinInt a :: Integer
a, FinInt b :: Integer
b) -> Integer -> Integer -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Integer
a Integer
b
              _ -> Ordering -> Ordering
swapCompare (Ordering -> Ordering) -> Ordering -> Ordering
forall a b. (a -> b) -> a -> b
$ InfInt -> InfInt -> Ordering
forall a. Ord a => a -> a -> Ordering
compare InfInt
y InfInt
x


class Continuous a

class Discrete a where
    nextA :: a -> a
    prevA :: a -> a
    intsizeA :: a -> a -> Maybe Integer


instance Discrete InfInt where
    nextA :: InfInt -> InfInt
nextA (FinInt a :: Integer
a) = Integer -> InfInt
FinInt (Integer -> InfInt) -> Integer -> InfInt
forall a b. (a -> b) -> a -> b
$ Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ 1
    nextA x :: InfInt
x = InfInt
x
    prevA :: InfInt -> InfInt
prevA (FinInt a :: Integer
a) = Integer -> InfInt
FinInt (Integer -> InfInt) -> Integer -> InfInt
forall a b. (a -> b) -> a -> b
$ Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- 1
    prevA x :: InfInt
x = InfInt
x
    intsizeA :: InfInt -> InfInt -> Maybe Integer
intsizeA (FinInt a :: Integer
a) (FinInt b :: Integer
b) = Integer -> Maybe Integer
forall a. a -> Maybe a
Just (Integer -> Maybe Integer) -> Integer -> Maybe Integer
forall a b. (a -> b) -> a -> b
$ (1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+) (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Integer -> Integer
forall a. Num a => a -> a
abs (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
a
    intsizeA _ _ = Maybe Integer
forall a. Maybe a
Nothing

{- ----------------------------------------------------------------------
Comparison facility for sets
---------------------------------------------------------------------- -}

{- | Compares closed intervals [l1, r1] and [l2, r2]. Assumes
non-singular intervals, i.e., l1 < r1 and l2 < r2.
Works only for linearly ordered types. -}
cmpClosedInts :: Ord a => ClosedInterval a -- ^ [l1, r1]
              -> ClosedInterval a -- ^ [l2, r2]
              -> SetOrdering
cmpClosedInts :: ClosedInterval a -> ClosedInterval a -> SetOrdering
cmpClosedInts (ClosedInterval l1 :: a
l1 r1 :: a
r1) (ClosedInterval l2 :: a
l2 r2 :: a
r2)
    | a
l1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
l2 Bool -> Bool -> Bool
&& a
r1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
r2 = Ordering -> SetOrdering
Comparable Ordering
EQ
    | a
l1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
l2 Bool -> Bool -> Bool
&& a
r1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
r2 = Ordering -> SetOrdering
Comparable Ordering
GT
    | a
l1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
l2 Bool -> Bool -> Bool
&& a
r1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
r2 = Ordering -> SetOrdering
Comparable Ordering
LT
    | a
r1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
l2 Bool -> Bool -> Bool
|| a
r2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
l1 = Incomparable -> SetOrdering
Incomparable Incomparable
Disjoint
    | Bool
otherwise = Incomparable -> SetOrdering
Incomparable Incomparable
Overlap

{- ----------------------------------------------------------------------
Comparison for discrete types
---------------------------------------------------------------------- -}

-- | Membership in 'SetOrInterval'
membSoID :: (Discrete a, Ord a) => a -> SetOrInterval a -> Bool
membSoID :: a -> SetOrInterval a -> Bool
membSoID x :: a
x (Set s :: Set a
s) = a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member a
x Set a
s
membSoID x :: a
x i :: SetOrInterval a
i = let ClosedInterval a :: a
a b :: a
b = SetOrInterval a -> ClosedInterval a
forall a.
(Discrete a, Ord a) =>
SetOrInterval a -> ClosedInterval a
setToClosedIntD SetOrInterval a
i in a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
a Bool -> Bool -> Bool
&& a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
b

-- | Checks if the set is empty.
nullSoID :: (Discrete a, Ord a) => SetOrInterval a -> Bool
nullSoID :: SetOrInterval a -> Bool
nullSoID (Set s :: Set a
s) = Set a -> Bool
forall a. Set a -> Bool
Set.null Set a
s
nullSoID i :: SetOrInterval a
i = let ClosedInterval a :: a
a b :: a
b = SetOrInterval a -> ClosedInterval a
forall a.
(Discrete a, Ord a) =>
SetOrInterval a -> ClosedInterval a
setToClosedIntD SetOrInterval a
i in a
a a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
b

{- | If the set is singular, i.e., consists only from one point, then we
return this point. Reports error on empty SoI's. -}
toSingularD :: (Discrete a, Ord a) => SetOrInterval a -> Maybe a
toSingularD :: SetOrInterval a -> Maybe a
toSingularD d :: SetOrInterval a
d
    | SetOrInterval a -> Bool
forall a. (Discrete a, Ord a) => SetOrInterval a -> Bool
nullSoID SetOrInterval a
d = String -> Maybe a
forall a. HasCallStack => String -> a
error "toSingularD: empty set"
    | Bool
otherwise =
        case SetOrInterval a
d of
          Set s :: Set a
s
              | Set a -> Int
forall a. Set a -> Int
Set.size Set a
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ Set a -> a
forall a. Set a -> a
Set.findMin Set a
s
              | Bool
otherwise -> Maybe a
forall a. Maybe a
Nothing
          _ -> let ClosedInterval a :: a
a b :: a
b = SetOrInterval a -> ClosedInterval a
forall a.
(Discrete a, Ord a) =>
SetOrInterval a -> ClosedInterval a
setToClosedIntD SetOrInterval a
d
               in if a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b then a -> Maybe a
forall a. a -> Maybe a
Just a
a else Maybe a
forall a. Maybe a
Nothing

-- | Transforms a 'SetOrInterval' to a closed representation
setToClosedIntD :: (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a
setToClosedIntD :: SetOrInterval a -> ClosedInterval a
setToClosedIntD (Set s :: Set a
s) = a -> a -> ClosedInterval a
forall a. a -> a -> ClosedInterval a
ClosedInterval (Set a -> a
forall a. Set a -> a
Set.findMin Set a
s) (a -> ClosedInterval a) -> a -> ClosedInterval a
forall a b. (a -> b) -> a -> b
$ Set a -> a
forall a. Set a -> a
Set.findMax Set a
s
setToClosedIntD (IntVal (l :: a
l, bL :: Bool
bL) (r :: a
r, bR :: Bool
bR)) =
    a -> a -> ClosedInterval a
forall a. a -> a -> ClosedInterval a
ClosedInterval (if Bool
bL then a
l else a -> a
forall a. Discrete a => a -> a
nextA a
l) (a -> ClosedInterval a) -> a -> ClosedInterval a
forall a b. (a -> b) -> a -> b
$ if Bool
bR then a
r else a -> a
forall a. Discrete a => a -> a
prevA a
r


-- | Compare sets over discrete types
cmpSoIsD :: (Discrete a, Ord a) =>
           SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsD :: SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsD d1 :: SetOrInterval a
d1 d2 :: SetOrInterval a
d2 =
    case (SetOrInterval a -> Maybe a
forall a. (Discrete a, Ord a) => SetOrInterval a -> Maybe a
toSingularD SetOrInterval a
d1, SetOrInterval a -> Maybe a
forall a. (Discrete a, Ord a) => SetOrInterval a -> Maybe a
toSingularD SetOrInterval a
d2) of
      (Just x1 :: a
x1, Just x2 :: a
x2)
          | a
x1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x2 -> Ordering -> SetOrdering
Comparable Ordering
EQ
          | Bool
otherwise -> Incomparable -> SetOrdering
Incomparable Incomparable
Disjoint
      (Just x :: a
x, _)
          | a -> SetOrInterval a -> Bool
forall a. (Discrete a, Ord a) => a -> SetOrInterval a -> Bool
membSoID a
x SetOrInterval a
d2 -> Ordering -> SetOrdering
Comparable Ordering
LT
          | Bool
otherwise -> Incomparable -> SetOrdering
Incomparable Incomparable
Disjoint
      (_, Just x :: a
x)
          | a -> SetOrInterval a -> Bool
forall a. (Discrete a, Ord a) => a -> SetOrInterval a -> Bool
membSoID a
x SetOrInterval a
d1 -> Ordering -> SetOrdering
Comparable Ordering
GT
          | Bool
otherwise -> Incomparable -> SetOrdering
Incomparable Incomparable
Disjoint
      _ -> SetOrInterval a -> SetOrInterval a -> SetOrdering
forall a.
(Discrete a, Ord a) =>
SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsExD SetOrInterval a
d1 SetOrInterval a
d2 -- singular cases are dispelled here


{- | Compare sets helper function which only works on regular (non-singular)
sets -}
cmpSoIsExD :: (Discrete a, Ord a) =>
              SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsExD :: SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsExD i1 :: SetOrInterval a
i1@(IntVal _ _) i2 :: SetOrInterval a
i2@(IntVal _ _) =
    ClosedInterval a -> ClosedInterval a -> SetOrdering
forall a.
Ord a =>
ClosedInterval a -> ClosedInterval a -> SetOrdering
cmpClosedInts (SetOrInterval a -> ClosedInterval a
forall a.
(Discrete a, Ord a) =>
SetOrInterval a -> ClosedInterval a
setToClosedIntD SetOrInterval a
i1) (ClosedInterval a -> SetOrdering)
-> ClosedInterval a -> SetOrdering
forall a b. (a -> b) -> a -> b
$ SetOrInterval a -> ClosedInterval a
forall a.
(Discrete a, Ord a) =>
SetOrInterval a -> ClosedInterval a
setToClosedIntD SetOrInterval a
i2

cmpSoIsExD s1 :: SetOrInterval a
s1@(Set _) s2 :: SetOrInterval a
s2@(Set _) = SetOrInterval a -> SetOrInterval a -> SetOrdering
forall a.
Ord a =>
SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsEx SetOrInterval a
s1 SetOrInterval a
s2

cmpSoIsExD i1 :: SetOrInterval a
i1@(IntVal _ _) s2 :: SetOrInterval a
s2@(Set s :: Set a
s) =
    let ci2 :: ClosedInterval a
ci2@(ClosedInterval a2 :: a
a2 b2 :: a
b2) = SetOrInterval a -> ClosedInterval a
forall a.
(Discrete a, Ord a) =>
SetOrInterval a -> ClosedInterval a
setToClosedIntD SetOrInterval a
s2
    in case ClosedInterval a -> ClosedInterval a -> SetOrdering
forall a.
Ord a =>
ClosedInterval a -> ClosedInterval a -> SetOrdering
cmpClosedInts (SetOrInterval a -> ClosedInterval a
forall a.
(Discrete a, Ord a) =>
SetOrInterval a -> ClosedInterval a
setToClosedIntD SetOrInterval a
i1) ClosedInterval a
ci2 of
      Comparable EQ -> case a -> a -> Maybe Integer
forall a. Discrete a => a -> a -> Maybe Integer
intsizeA a
a2 a
b2 of
                         Just dst :: Integer
dst
                             | Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Set a -> Int
forall a. Set a -> Int
Set.size Set a
s) Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
dst ->
                                 Ordering -> SetOrdering
Comparable Ordering
EQ
                             | Bool
otherwise -> Ordering -> SetOrdering
Comparable Ordering
GT
                         -- Nothing means infinite. This is a misuse!
                         _ -> String -> SetOrdering
forall a. HasCallStack => String -> a
error "cmpSoIsExD: unbounded finite set!"
      Comparable LT -> Incomparable -> SetOrdering
Incomparable (Incomparable -> SetOrdering) -> Incomparable -> SetOrdering
forall a b. (a -> b) -> a -> b
$ if (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a -> SetOrInterval a -> Bool
forall a. (Discrete a, Ord a) => a -> SetOrInterval a -> Bool
`membSoID` SetOrInterval a
i1) ([a] -> Bool) -> [a] -> Bool
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
Set.toList Set a
s
                       then Incomparable
Overlap
                       else Incomparable
Disjoint
      so :: SetOrdering
so -> SetOrdering
so

cmpSoIsExD s1 :: SetOrInterval a
s1 i2 :: SetOrInterval a
i2 = SetOrdering -> SetOrdering
swapCmp (SetOrdering -> SetOrdering) -> SetOrdering -> SetOrdering
forall a b. (a -> b) -> a -> b
$ SetOrInterval a -> SetOrInterval a -> SetOrdering
forall a.
(Discrete a, Ord a) =>
SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsExD SetOrInterval a
i2 SetOrInterval a
s1

{- ----------------------------------------------------------------------
Comparison for continuous types
---------------------------------------------------------------------- -}

-- | Membership in 'SetOrInterval'
membSoI :: Ord a => a -> SetOrInterval a -> Bool
membSoI :: a -> SetOrInterval a -> Bool
membSoI x :: a
x (Set s :: Set a
s) = a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member a
x Set a
s
membSoI x :: a
x i :: SetOrInterval a
i = let ClosedInterval a :: CIType a
a b :: CIType a
b = SetOrInterval a -> ClosedInterval (CIType a)
forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a)
setToClosedInt SetOrInterval a
i
                  x' :: CIType a
x' = (a, InfDev) -> CIType a
forall a. (a, InfDev) -> CIType a
CIType (a
x, InfDev
Zero) in CIType a
x' CIType a -> CIType a -> Bool
forall a. Ord a => a -> a -> Bool
>= CIType a
a Bool -> Bool -> Bool
&& CIType a
x' CIType a -> CIType a -> Bool
forall a. Ord a => a -> a -> Bool
<= CIType a
b

{- | Checks if the set is empty.
Only for continuous types. -}
nullSoI :: (Continuous a, Ord a) => SetOrInterval a -> Bool
nullSoI :: SetOrInterval a -> Bool
nullSoI (Set s :: Set a
s) = Set a -> Bool
forall a. Set a -> Bool
Set.null Set a
s
nullSoI (IntVal (a :: a
a, bA :: Bool
bA) (b :: a
b, bB :: Bool
bB)) = a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b Bool -> Bool -> Bool
&& Bool -> Bool
not (Bool
bA Bool -> Bool -> Bool
&& Bool
bB)

{- | If the set is singular, i.e., consists only from one point, then we
return this point. Reports error on empty SoI's.
Only for continuous types. -}
toSingular :: (Continuous a, Ord a) => SetOrInterval a -> Maybe a
toSingular :: SetOrInterval a -> Maybe a
toSingular d :: SetOrInterval a
d
    | SetOrInterval a -> Bool
forall a. (Continuous a, Ord a) => SetOrInterval a -> Bool
nullSoI SetOrInterval a
d = String -> Maybe a
forall a. HasCallStack => String -> a
error "toSingular: empty set"
    | Bool
otherwise =
        case SetOrInterval a
d of
          Set s :: Set a
s
              | Set a -> Int
forall a. Set a -> Int
Set.size Set a
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ Set a -> a
forall a. Set a -> a
Set.findMin Set a
s
              | Bool
otherwise -> Maybe a
forall a. Maybe a
Nothing
          IntVal (a :: a
a, _) (b :: a
b, _)
              | a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b -> a -> Maybe a
forall a. a -> Maybe a
Just a
a
              | Bool
otherwise -> Maybe a
forall a. Maybe a
Nothing

{- | Transforms a 'SetOrInterval' to a closed representation
Only for continuous types. -}
setToClosedInt :: Ord a =>
                  SetOrInterval a -> ClosedInterval (CIType a)
setToClosedInt :: SetOrInterval a -> ClosedInterval (CIType a)
setToClosedInt (Set s :: Set a
s) = CIType a -> CIType a -> ClosedInterval (CIType a)
forall a. a -> a -> ClosedInterval a
ClosedInterval ((a, InfDev) -> CIType a
forall a. (a, InfDev) -> CIType a
CIType (Set a -> a
forall a. Set a -> a
Set.findMin Set a
s, InfDev
Zero))
                         (CIType a -> ClosedInterval (CIType a))
-> CIType a -> ClosedInterval (CIType a)
forall a b. (a -> b) -> a -> b
$ (a, InfDev) -> CIType a
forall a. (a, InfDev) -> CIType a
CIType (Set a -> a
forall a. Set a -> a
Set.findMax Set a
s, InfDev
Zero)
setToClosedInt (IntVal (l :: a
l, bL :: Bool
bL) (r :: a
r, bR :: Bool
bR)) =
    CIType a -> CIType a -> ClosedInterval (CIType a)
forall a. a -> a -> ClosedInterval a
ClosedInterval ((a, InfDev) -> CIType a
forall a. (a, InfDev) -> CIType a
CIType (a
l, if Bool
bL then InfDev
Zero else InfDev
EpsRight))
                       (CIType a -> ClosedInterval (CIType a))
-> CIType a -> ClosedInterval (CIType a)
forall a b. (a -> b) -> a -> b
$ (a, InfDev) -> CIType a
forall a. (a, InfDev) -> CIType a
CIType (a
r, if Bool
bR then InfDev
Zero else InfDev
EpsLeft)

-- | Compare sets over continuous types
cmpSoIs :: (Continuous a, Ord a) =>
           SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIs :: SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIs d1 :: SetOrInterval a
d1 d2 :: SetOrInterval a
d2 =
    case (SetOrInterval a -> Maybe a
forall a. (Continuous a, Ord a) => SetOrInterval a -> Maybe a
toSingular SetOrInterval a
d1, SetOrInterval a -> Maybe a
forall a. (Continuous a, Ord a) => SetOrInterval a -> Maybe a
toSingular SetOrInterval a
d2) of
      (Just x1 :: a
x1, Just x2 :: a
x2)
          | a
x1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x2 -> Ordering -> SetOrdering
Comparable Ordering
EQ
          | Bool
otherwise -> Incomparable -> SetOrdering
Incomparable Incomparable
Disjoint
      (Just x :: a
x, _)
          | a -> SetOrInterval a -> Bool
forall a. Ord a => a -> SetOrInterval a -> Bool
membSoI a
x SetOrInterval a
d2 -> Ordering -> SetOrdering
Comparable Ordering
LT
          | Bool
otherwise -> Incomparable -> SetOrdering
Incomparable Incomparable
Disjoint
      (_, Just x :: a
x)
          | a -> SetOrInterval a -> Bool
forall a. Ord a => a -> SetOrInterval a -> Bool
membSoI a
x SetOrInterval a
d1 -> Ordering -> SetOrdering
Comparable Ordering
GT
          | Bool
otherwise -> Incomparable -> SetOrdering
Incomparable Incomparable
Disjoint
      _ -> SetOrInterval a -> SetOrInterval a -> SetOrdering
forall a.
Ord a =>
SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsEx SetOrInterval a
d1 SetOrInterval a
d2 -- singular cases are dispelled here


{- | Compare sets helper function which only works on regular (non-singular)
sets -}
cmpSoIsEx :: (Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsEx :: SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsEx (Set s1 :: Set a
s1) (Set s2 :: Set a
s2)
    | Set a
s1 Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
== Set a
s2 = Ordering -> SetOrdering
Comparable Ordering
EQ
    | Set a
s1 Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
`Set.isSubsetOf` Set a
s2 = Ordering -> SetOrdering
Comparable Ordering
LT
    | Set a
s2 Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
`Set.isSubsetOf` Set a
s1 = Ordering -> SetOrdering
Comparable Ordering
GT
    | Set a -> Bool
forall a. Set a -> Bool
Set.null (Set a -> Bool) -> Set a -> Bool
forall a b. (a -> b) -> a -> b
$ Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
Set.intersection Set a
s1 Set a
s2 = Incomparable -> SetOrdering
Incomparable Incomparable
Disjoint
    | Bool
otherwise = Incomparable -> SetOrdering
Incomparable Incomparable
Overlap

cmpSoIsEx i1 :: SetOrInterval a
i1@(IntVal _ _) i2 :: SetOrInterval a
i2@(IntVal _ _) =
    ClosedInterval (CIType a)
-> ClosedInterval (CIType a) -> SetOrdering
forall a.
Ord a =>
ClosedInterval a -> ClosedInterval a -> SetOrdering
cmpClosedInts (SetOrInterval a -> ClosedInterval (CIType a)
forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a)
setToClosedInt SetOrInterval a
i1) (ClosedInterval (CIType a) -> SetOrdering)
-> ClosedInterval (CIType a) -> SetOrdering
forall a b. (a -> b) -> a -> b
$ SetOrInterval a -> ClosedInterval (CIType a)
forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a)
setToClosedInt SetOrInterval a
i2

cmpSoIsEx i1 :: SetOrInterval a
i1@(IntVal _ _) s2 :: SetOrInterval a
s2@(Set s :: Set a
s) =
    case ClosedInterval (CIType a)
-> ClosedInterval (CIType a) -> SetOrdering
forall a.
Ord a =>
ClosedInterval a -> ClosedInterval a -> SetOrdering
cmpClosedInts (SetOrInterval a -> ClosedInterval (CIType a)
forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a)
setToClosedInt SetOrInterval a
i1) (ClosedInterval (CIType a) -> SetOrdering)
-> ClosedInterval (CIType a) -> SetOrdering
forall a b. (a -> b) -> a -> b
$ SetOrInterval a -> ClosedInterval (CIType a)
forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a)
setToClosedInt SetOrInterval a
s2 of
      Comparable EQ -> Ordering -> SetOrdering
Comparable Ordering
GT
      Comparable LT -> Incomparable -> SetOrdering
Incomparable (Incomparable -> SetOrdering) -> Incomparable -> SetOrdering
forall a b. (a -> b) -> a -> b
$ if (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a -> SetOrInterval a -> Bool
forall a. Ord a => a -> SetOrInterval a -> Bool
`membSoI` SetOrInterval a
i1) ([a] -> Bool) -> [a] -> Bool
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
Set.toList Set a
s
                       then Incomparable
Overlap
                       else Incomparable
Disjoint
      so :: SetOrdering
so -> SetOrdering
so

cmpSoIsEx s1 :: SetOrInterval a
s1 i2 :: SetOrInterval a
i2 = SetOrdering -> SetOrdering
swapCmp (SetOrdering -> SetOrdering) -> SetOrdering -> SetOrdering
forall a b. (a -> b) -> a -> b
$ SetOrInterval a -> SetOrInterval a -> SetOrdering
forall a.
Ord a =>
SetOrInterval a -> SetOrInterval a -> SetOrdering
cmpSoIsEx SetOrInterval a
i2 SetOrInterval a
s1


{- ----------------------------------------------------------------------
Combining comparison results
---------------------------------------------------------------------- -}

swapCompare :: Ordering -> Ordering
swapCompare :: Ordering -> Ordering
swapCompare GT = Ordering
LT
swapCompare LT = Ordering
GT
swapCompare x :: Ordering
x = Ordering
x


swapCmp :: SetOrdering -> SetOrdering
swapCmp :: SetOrdering -> SetOrdering
swapCmp (Comparable x :: Ordering
x) = Ordering -> SetOrdering
Comparable (Ordering -> SetOrdering) -> Ordering -> SetOrdering
forall a b. (a -> b) -> a -> b
$ Ordering -> Ordering
swapCompare Ordering
x
swapCmp x :: SetOrdering
x = SetOrdering
x

{- | We combine the comparison outcome of the individual parameters with
     the following (symmetrical => commutative) table:

>     \ | > < = O D
>     -------------
>     > | > O > O D
>     < |   < < O D
>     = |     = O D
>     O |       O D
>     D |         D
>
>     , where
>
>     >       | <      | =     | O       | D
>     ---------------------------------------------
>     RightOf | LeftOf | Equal | Overlap | Disjoint


The purpose of this table is to use it for cartesian products as follows

Let

A', A'' \subset A
B', B'' \subset B


In order to get the comparison result for A' x B' and A'' x B'' we compare

A' and A'' as well as B' and B'' and combine the results with the above table.

Note that for empty sets the comparable results <,>,= are preferred over the
disjoint result.
-}

combineCmp :: SetOrdering -> SetOrdering -> SetOrdering
combineCmp :: SetOrdering -> SetOrdering -> SetOrdering
combineCmp x :: SetOrdering
x y :: SetOrdering
y
    | SetOrdering
x SetOrdering -> SetOrdering -> Bool
forall a. Eq a => a -> a -> Bool
== SetOrdering
y = SetOrdering
x -- idempotence
    | Bool
otherwise =
        case (SetOrdering
x, SetOrdering
y) of
          (_, Incomparable Disjoint) -> Incomparable -> SetOrdering
Incomparable Incomparable
Disjoint
          (Incomparable Overlap, _) -> Incomparable -> SetOrdering
Incomparable Incomparable
Overlap
          (Comparable EQ, _) -> SetOrdering
y -- neutral element
          (Comparable GT, Comparable LT) -> Incomparable -> SetOrdering
Incomparable Incomparable
Overlap
          _ -> SetOrdering -> SetOrdering -> SetOrdering
combineCmp SetOrdering
y SetOrdering
x -- commutative (should capture all cases)