-----------------------------------------------------------------------------
-- |
-- Module     : Algebra.Graph.Internal
-- Copyright  : (c) Andrey Mokhov 2016-2022
-- License    : MIT (see the file LICENSE)
-- Maintainer : andrey.mokhov@gmail.com
-- Stability  : experimental
--
-- __Alga__ is a library for algebraic construction and manipulation of graphs
-- in Haskell. See <https://github.com/snowleopard/alga-paper this paper> for the
-- motivation behind the library, the underlying theory, and implementation details.
--
-- This module defines various internal utilities and data structures used
-- throughout the library, such as lists with fast concatenation. The API
-- is unstable and unsafe, and is exposed only for documentation.
-----------------------------------------------------------------------------
module Algebra.Graph.Internal (
    -- * Data structures
    List,

    -- * Graph traversal
    Focus (..), emptyFocus, vertexFocus, overlayFoci, connectFoci, foldr1Safe,
    maybeF,

    -- * Utilities
    cartesianProductWith, coerce00, coerce10, coerce20, coerce01, coerce11,
    coerce21
    ) where

import Data.Coerce
import Data.Foldable
import Data.IntSet (IntSet)
import Data.Semigroup (Endo (..))
import Data.Set (Set)

import qualified Data.IntSet as IntSet
import qualified Data.Set    as Set
import qualified GHC.Exts    as Exts

-- | An abstract list data type with /O(1)/ time concatenation (the current
-- implementation uses difference lists). Here @a@ is the type of list elements.
-- 'List' @a@ is a 'Monoid': 'mempty' corresponds to the empty list and two lists
-- can be concatenated with 'mappend' (or operator 'Data.Semigroup.<>'). Singleton
-- lists can be constructed using the function 'pure' from the 'Applicative'
-- instance. 'List' @a@ is also an instance of 'IsList', therefore you can use
-- list literals, e.g. @[1,4]@ @::@ 'List' @Int@ is the same as 'pure' @1@
-- 'Data.Semigroup.<>' 'pure' @4@; note that this requires the @OverloadedLists@
-- GHC extension. To extract plain Haskell lists you can use the 'toList'
-- function from the 'Foldable' instance.
newtype List a = List (Endo [a]) deriving (Monoid, Semigroup)

instance Show a => Show (List a) where
    show = show . toList

instance Eq a => Eq (List a) where
    x == y = toList x == toList y

instance Ord a => Ord (List a) where
    compare x y = compare (toList x) (toList y)

-- TODO: Add rewrite rules? fromList . toList == toList . fromList == id
instance Exts.IsList (List a) where
    type Item (List a) = a
    fromList        = List . Endo . (<>)
    toList (List x) = appEndo x []

instance Foldable List where
    foldMap f = foldMap f . Exts.toList
    toList    = Exts.toList

instance Functor List where
    fmap f = Exts.fromList . map f . toList

instance Applicative List where
    pure    = List . Endo . (:)
    f <*> x = Exts.fromList (toList f <*> toList x)

instance Monad List where
    return  = pure
    x >>= f = Exts.fromList (toList x >>= toList . f)

-- | The /focus/ of a graph expression is a flattened representation of the
-- subgraph under focus, its context, as well as the list of all encountered
-- vertices. See 'Algebra.Graph.removeEdge' for a use-case example.
data Focus a = Focus
    { ok :: Bool     -- ^ True if focus on the specified subgraph is obtained.
    , is :: List a   -- ^ Inputs into the focused subgraph.
    , os :: List a   -- ^ Outputs out of the focused subgraph.
    , vs :: List a } -- ^ All vertices (leaves) of the graph expression.

-- | Focus on the empty graph.
emptyFocus :: Focus a
emptyFocus = Focus False mempty mempty mempty

-- | Focus on the graph with a single vertex, given a predicate indicating
-- whether the vertex is of interest.
vertexFocus :: (a -> Bool) -> a -> Focus a
vertexFocus f x = Focus (f x) mempty mempty (pure x)

-- | Overlay two foci.
overlayFoci :: Focus a -> Focus a -> Focus a
overlayFoci x y = Focus (ok x || ok y) (is x <> is y) (os x <> os y) (vs x <> vs y)

-- | Connect two foci.
connectFoci :: Focus a -> Focus a -> Focus a
connectFoci x y = Focus (ok x || ok y) (xs <> is y) (os x <> ys) (vs x <> vs y)
  where
    xs = if ok y then vs x else is x
    ys = if ok x then vs y else os y

-- | A safe version of 'foldr1'.
foldr1Safe :: (a -> a -> a) -> [a] -> Maybe a
foldr1Safe f = foldr (maybeF f) Nothing
{-# INLINE foldr1Safe #-}

-- | An auxiliary function that tries to apply a function to a base case and a
-- 'Maybe' value and returns 'Just' the result or 'Just' the base case.
maybeF :: (a -> b -> a) -> a -> Maybe b -> Maybe a
maybeF f x = Just . maybe x (f x)
{-# INLINE maybeF #-}

-- TODO: Can we implement this faster via 'Set.cartesianProduct'?
-- | Compute the Cartesian product of two sets, applying a function to each
-- resulting pair.
cartesianProductWith :: Ord c => (a -> b -> c) -> Set a -> Set b -> Set c
cartesianProductWith f x y =
    Set.fromList [ f a b | a <- Set.toAscList x, b <- Set.toAscList y ]

-- TODO: Get rid of this boilerplate.

-- | Help GHC with type inference when direct use of 'coerce' does not compile.
coerce00 :: Coercible f g => f x -> g x
coerce00 = coerce

-- | Help GHC with type inference when direct use of 'coerce' does not compile.
coerce10 :: (Coercible a b, Coercible f g) => (a -> f x) -> (b -> g x)
coerce10 = coerce

-- | Help GHC with type inference when direct use of 'coerce' does not compile.
coerce20 :: (Coercible a b, Coercible c d, Coercible f g)
         => (a -> c -> f x) -> (b -> d -> g x)
coerce20 = coerce

-- | Help GHC with type inference when direct use of 'coerce' does not compile.
coerce01 :: (Coercible a b, Coercible f g) => (f x -> a) -> (g x -> b)
coerce01 = coerce

-- | Help GHC with type inference when direct use of 'coerce' does not compile.
coerce11 :: (Coercible a b, Coercible c d, Coercible f g)
         => (a -> f x -> c) -> (b -> g x -> d)
coerce11 = coerce

-- | Help GHC with type inference when direct use of 'coerce' does not compile.
coerce21 :: (Coercible a b, Coercible c d, Coercible p q, Coercible f g)
         => (a -> c -> f x -> p) -> (b -> d -> g x -> q)
coerce21 = coerce