-----------------------------------------------------------------------------
-- |
-- Module     : Algebra.Graph.Relation.Preorder
-- Copyright  : (c) Andrey Mokhov 2016-2021
-- License    : MIT (see the file LICENSE)
-- Maintainer : andrey.mokhov@gmail.com
-- Stability  : experimental
--
-- An abstract implementation of preorder relations. Use "Algebra.Graph.Class"
-- for polymorphic construction and manipulation.
-----------------------------------------------------------------------------
module Algebra.Graph.Relation.Preorder (
    -- * Data structure
    PreorderRelation, fromRelation, toRelation
    ) where

import Algebra.Graph.Relation
import Control.DeepSeq
import Data.String

import qualified Algebra.Graph.Class as C

-- TODO: Optimise the implementation by caching the results of preorder closure.
{-| The 'PreorderRelation' data type represents a
/binary relation that is both reflexive and transitive/. Preorders satisfy all
laws of the 'Preorder' type class and, in particular, the /self-loop/ axiom:

@'vertex' x == 'vertex' x * 'vertex' x@

and the /closure/ axiom:

@y /= 'empty' ==> x * y + x * z + y * z == x * y + y * z@

For example, the following holds:

@'path' xs == ('clique' xs :: PreorderRelation Int)@

The 'Show' instance produces reflexively and transitively closed expressions:

@show (1             :: PreorderRelation Int) == "edge 1 1"
show (1 * 2         :: PreorderRelation Int) == "edges [(1,1),(1,2),(2,2)]"
show (1 * 2 + 2 * 3 :: PreorderRelation Int) == "edges [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"@
-}
newtype PreorderRelation a = PreorderRelation { PreorderRelation a -> Relation a
fromPreorder :: Relation a }
    deriving (String -> PreorderRelation a
(String -> PreorderRelation a) -> IsString (PreorderRelation a)
forall a. IsString a => String -> PreorderRelation a
forall a. (String -> a) -> IsString a
fromString :: String -> PreorderRelation a
$cfromString :: forall a. IsString a => String -> PreorderRelation a
IsString, PreorderRelation a -> ()
(PreorderRelation a -> ()) -> NFData (PreorderRelation a)
forall a. NFData a => PreorderRelation a -> ()
forall a. (a -> ()) -> NFData a
rnf :: PreorderRelation a -> ()
$crnf :: forall a. NFData a => PreorderRelation a -> ()
NFData, Integer -> PreorderRelation a
PreorderRelation a -> PreorderRelation a
PreorderRelation a -> PreorderRelation a -> PreorderRelation a
(PreorderRelation a -> PreorderRelation a -> PreorderRelation a)
-> (PreorderRelation a -> PreorderRelation a -> PreorderRelation a)
-> (PreorderRelation a -> PreorderRelation a -> PreorderRelation a)
-> (PreorderRelation a -> PreorderRelation a)
-> (PreorderRelation a -> PreorderRelation a)
-> (PreorderRelation a -> PreorderRelation a)
-> (Integer -> PreorderRelation a)
-> Num (PreorderRelation a)
forall a. (Ord a, Num a) => Integer -> PreorderRelation a
forall a.
(Ord a, Num a) =>
PreorderRelation a -> PreorderRelation a
forall a.
(Ord a, Num a) =>
PreorderRelation a -> PreorderRelation a -> PreorderRelation a
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
fromInteger :: Integer -> PreorderRelation a
$cfromInteger :: forall a. (Ord a, Num a) => Integer -> PreorderRelation a
signum :: PreorderRelation a -> PreorderRelation a
$csignum :: forall a.
(Ord a, Num a) =>
PreorderRelation a -> PreorderRelation a
abs :: PreorderRelation a -> PreorderRelation a
$cabs :: forall a.
(Ord a, Num a) =>
PreorderRelation a -> PreorderRelation a
negate :: PreorderRelation a -> PreorderRelation a
$cnegate :: forall a.
(Ord a, Num a) =>
PreorderRelation a -> PreorderRelation a
* :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a
$c* :: forall a.
(Ord a, Num a) =>
PreorderRelation a -> PreorderRelation a -> PreorderRelation a
- :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a
$c- :: forall a.
(Ord a, Num a) =>
PreorderRelation a -> PreorderRelation a -> PreorderRelation a
+ :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a
$c+ :: forall a.
(Ord a, Num a) =>
PreorderRelation a -> PreorderRelation a -> PreorderRelation a
Num)

instance (Ord a, Show a) => Show (PreorderRelation a) where
    show :: PreorderRelation a -> String
show = Relation a -> String
forall a. Show a => a -> String
show (Relation a -> String)
-> (PreorderRelation a -> Relation a)
-> PreorderRelation a
-> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PreorderRelation a -> Relation a
forall a. Ord a => PreorderRelation a -> Relation a
toRelation

instance Ord a => Eq (PreorderRelation a) where
    PreorderRelation a
x == :: PreorderRelation a -> PreorderRelation a -> Bool
== PreorderRelation a
y = PreorderRelation a -> Relation a
forall a. Ord a => PreorderRelation a -> Relation a
toRelation PreorderRelation a
x Relation a -> Relation a -> Bool
forall a. Eq a => a -> a -> Bool
== PreorderRelation a -> Relation a
forall a. Ord a => PreorderRelation a -> Relation a
toRelation PreorderRelation a
y

instance Ord a => Ord (PreorderRelation a) where
    compare :: PreorderRelation a -> PreorderRelation a -> Ordering
compare PreorderRelation a
x PreorderRelation a
y = Relation a -> Relation a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (PreorderRelation a -> Relation a
forall a. Ord a => PreorderRelation a -> Relation a
toRelation PreorderRelation a
x) (PreorderRelation a -> Relation a
forall a. Ord a => PreorderRelation a -> Relation a
toRelation PreorderRelation a
y)

-- TODO: To be derived automatically using GeneralizedNewtypeDeriving in GHC 8.2
instance Ord a => C.Graph (PreorderRelation a) where
    type Vertex (PreorderRelation a) = a
    empty :: PreorderRelation a
empty       = Relation a -> PreorderRelation a
forall a. Relation a -> PreorderRelation a
PreorderRelation Relation a
forall a. Relation a
empty
    vertex :: Vertex (PreorderRelation a) -> PreorderRelation a
vertex      = Relation a -> PreorderRelation a
forall a. Relation a -> PreorderRelation a
PreorderRelation (Relation a -> PreorderRelation a)
-> (a -> Relation a) -> a -> PreorderRelation a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Relation a
forall a. a -> Relation a
vertex
    overlay :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a
overlay PreorderRelation a
x PreorderRelation a
y = Relation a -> PreorderRelation a
forall a. Relation a -> PreorderRelation a
PreorderRelation (Relation a -> PreorderRelation a)
-> Relation a -> PreorderRelation a
forall a b. (a -> b) -> a -> b
$ PreorderRelation a -> Relation a
forall a. PreorderRelation a -> Relation a
fromPreorder PreorderRelation a
x Relation a -> Relation a -> Relation a
forall a. Ord a => Relation a -> Relation a -> Relation a
`overlay` PreorderRelation a -> Relation a
forall a. PreorderRelation a -> Relation a
fromPreorder PreorderRelation a
y
    connect :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a
connect PreorderRelation a
x PreorderRelation a
y = Relation a -> PreorderRelation a
forall a. Relation a -> PreorderRelation a
PreorderRelation (Relation a -> PreorderRelation a)
-> Relation a -> PreorderRelation a
forall a b. (a -> b) -> a -> b
$ PreorderRelation a -> Relation a
forall a. PreorderRelation a -> Relation a
fromPreorder PreorderRelation a
x Relation a -> Relation a -> Relation a
forall a. Ord a => Relation a -> Relation a -> Relation a
`connect` PreorderRelation a -> Relation a
forall a. PreorderRelation a -> Relation a
fromPreorder PreorderRelation a
y

instance Ord a => C.Reflexive  (PreorderRelation a)
instance Ord a => C.Transitive (PreorderRelation a)
instance Ord a => C.Preorder   (PreorderRelation a)

-- | Construct a preorder relation from a 'Relation'.
-- Complexity: /O(1)/ time.
fromRelation :: Relation a -> PreorderRelation a
fromRelation :: Relation a -> PreorderRelation a
fromRelation = Relation a -> PreorderRelation a
forall a. Relation a -> PreorderRelation a
PreorderRelation

-- | Extract the underlying relation.
-- Complexity: /O(n * m * log(m))/ time.
toRelation :: Ord a => PreorderRelation a -> Relation a
toRelation :: PreorderRelation a -> Relation a
toRelation = Relation a -> Relation a
forall a. Ord a => Relation a -> Relation a
closure (Relation a -> Relation a)
-> (PreorderRelation a -> Relation a)
-> PreorderRelation a
-> Relation a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PreorderRelation a -> Relation a
forall a. PreorderRelation a -> Relation a
fromPreorder