{-# LANGUAGE FlexibleInstances #-}

-- | This module implements a simple \"pure\" graph interface, destined
-- to be used for the complex graph operations required by VersionDag.
--
-- We instance 'Show' for debugging purposes.
module Graphs.PureGraph(
   PureGraph(..),
   NodeData(..),
   ArcData(..),

   emptyPureGraph, -- :: Ord nodeInfo => PureGraph nodeInfo arcInfo

   addNode, -- :: Ord nodeInfo
      -- => PureGraph nodeInfo arcInfo -> nodeInfo -> [(arcInfo,nodeInfo)]
      -- -> PureGraph nodeInfo arcInfo

   deleteNode, -- :: Ord nodeInfo
      -- => PureGraph nodeInfo arcInfo -> nodeInfo
      -- -> PureGraph nodeInfo arcInfo

   mapArcInfo,
      -- :: (arcInfo1 -> arcInfo2) -> PureGraph nodeInfo arcInfo1
      -- -> PureGraph nodeInfo arcInfo2

   parentNodes,
      -- :: NodeData nodeInfo arcInfo -> [nodeInfo]



   toAllNodes, -- :: Ord nodeInfo => PureGraph nodeInfo arcInfo -> [nodeInfo]
   toNodeParents,
      -- :: Ord nodeInfo => PureGraph nodeInfo arcInfo -> nodeInfo
      -- -> Maybe [nodeInfo]
      -- returns Nothing if the node does not exist.

   nodeExists, -- :: PureGraph nodeInfo arcInfo -> nodeInfo -> Bool

   ) where

import qualified Data.Map as Map

import Graphs.Graph(PartialShow(..))

-- ------------------------------------------------------------------------
-- Datatypes
-- ------------------------------------------------------------------------

-- | node given with their parent nodes.  The parents should always come
-- before their children in the list.
newtype PureGraph nodeInfo arcInfo = PureGraph {
   PureGraph nodeInfo arcInfo
-> Map nodeInfo (NodeData nodeInfo arcInfo)
nodeDataFM :: Map.Map nodeInfo (NodeData nodeInfo arcInfo)
   }

data NodeData nodeInfo arcInfo = NodeData {
   NodeData nodeInfo arcInfo -> [ArcData nodeInfo arcInfo]
parents :: [ArcData nodeInfo arcInfo]
   } deriving (Int -> NodeData nodeInfo arcInfo -> ShowS
[NodeData nodeInfo arcInfo] -> ShowS
NodeData nodeInfo arcInfo -> String
(Int -> NodeData nodeInfo arcInfo -> ShowS)
-> (NodeData nodeInfo arcInfo -> String)
-> ([NodeData nodeInfo arcInfo] -> ShowS)
-> Show (NodeData nodeInfo arcInfo)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
Int -> NodeData nodeInfo arcInfo -> ShowS
forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
[NodeData nodeInfo arcInfo] -> ShowS
forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
NodeData nodeInfo arcInfo -> String
showList :: [NodeData nodeInfo arcInfo] -> ShowS
$cshowList :: forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
[NodeData nodeInfo arcInfo] -> ShowS
show :: NodeData nodeInfo arcInfo -> String
$cshow :: forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
NodeData nodeInfo arcInfo -> String
showsPrec :: Int -> NodeData nodeInfo arcInfo -> ShowS
$cshowsPrec :: forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
Int -> NodeData nodeInfo arcInfo -> ShowS
Show,NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
(NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool)
-> (NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool)
-> Eq (NodeData nodeInfo arcInfo)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall nodeInfo arcInfo.
(Eq arcInfo, Eq nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
/= :: NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
$c/= :: forall nodeInfo arcInfo.
(Eq arcInfo, Eq nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
== :: NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
$c== :: forall nodeInfo arcInfo.
(Eq arcInfo, Eq nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
Eq,Eq (NodeData nodeInfo arcInfo)
Eq (NodeData nodeInfo arcInfo)
-> (NodeData nodeInfo arcInfo
    -> NodeData nodeInfo arcInfo -> Ordering)
-> (NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool)
-> (NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool)
-> (NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool)
-> (NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool)
-> (NodeData nodeInfo arcInfo
    -> NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo)
-> (NodeData nodeInfo arcInfo
    -> NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo)
-> Ord (NodeData nodeInfo arcInfo)
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Ordering
NodeData nodeInfo arcInfo
-> NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo
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 nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
Eq (NodeData nodeInfo arcInfo)
forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Ordering
forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo
-> NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo
min :: NodeData nodeInfo arcInfo
-> NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo
$cmin :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo
-> NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo
max :: NodeData nodeInfo arcInfo
-> NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo
$cmax :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo
-> NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo
>= :: NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
$c>= :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
> :: NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
$c> :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
<= :: NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
$c<= :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
< :: NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
$c< :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Bool
compare :: NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Ordering
$ccompare :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
NodeData nodeInfo arcInfo -> NodeData nodeInfo arcInfo -> Ordering
$cp1Ord :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
Eq (NodeData nodeInfo arcInfo)
Ord)

data ArcData nodeInfo arcInfo = ArcData {
   ArcData nodeInfo arcInfo -> arcInfo
arcInfo :: arcInfo,
   ArcData nodeInfo arcInfo -> nodeInfo
target :: nodeInfo
   } deriving (Int -> ArcData nodeInfo arcInfo -> ShowS
[ArcData nodeInfo arcInfo] -> ShowS
ArcData nodeInfo arcInfo -> String
(Int -> ArcData nodeInfo arcInfo -> ShowS)
-> (ArcData nodeInfo arcInfo -> String)
-> ([ArcData nodeInfo arcInfo] -> ShowS)
-> Show (ArcData nodeInfo arcInfo)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
Int -> ArcData nodeInfo arcInfo -> ShowS
forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
[ArcData nodeInfo arcInfo] -> ShowS
forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
ArcData nodeInfo arcInfo -> String
showList :: [ArcData nodeInfo arcInfo] -> ShowS
$cshowList :: forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
[ArcData nodeInfo arcInfo] -> ShowS
show :: ArcData nodeInfo arcInfo -> String
$cshow :: forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
ArcData nodeInfo arcInfo -> String
showsPrec :: Int -> ArcData nodeInfo arcInfo -> ShowS
$cshowsPrec :: forall nodeInfo arcInfo.
(Show arcInfo, Show nodeInfo) =>
Int -> ArcData nodeInfo arcInfo -> ShowS
Show,ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
(ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool)
-> (ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool)
-> Eq (ArcData nodeInfo arcInfo)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall nodeInfo arcInfo.
(Eq arcInfo, Eq nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
/= :: ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
$c/= :: forall nodeInfo arcInfo.
(Eq arcInfo, Eq nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
== :: ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
$c== :: forall nodeInfo arcInfo.
(Eq arcInfo, Eq nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
Eq,Eq (ArcData nodeInfo arcInfo)
Eq (ArcData nodeInfo arcInfo)
-> (ArcData nodeInfo arcInfo
    -> ArcData nodeInfo arcInfo -> Ordering)
-> (ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool)
-> (ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool)
-> (ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool)
-> (ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool)
-> (ArcData nodeInfo arcInfo
    -> ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo)
-> (ArcData nodeInfo arcInfo
    -> ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo)
-> Ord (ArcData nodeInfo arcInfo)
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Ordering
ArcData nodeInfo arcInfo
-> ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo
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 nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
Eq (ArcData nodeInfo arcInfo)
forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Ordering
forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo
-> ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo
min :: ArcData nodeInfo arcInfo
-> ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo
$cmin :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo
-> ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo
max :: ArcData nodeInfo arcInfo
-> ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo
$cmax :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo
-> ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo
>= :: ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
$c>= :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
> :: ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
$c> :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
<= :: ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
$c<= :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
< :: ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
$c< :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Bool
compare :: ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Ordering
$ccompare :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
ArcData nodeInfo arcInfo -> ArcData nodeInfo arcInfo -> Ordering
$cp1Ord :: forall nodeInfo arcInfo.
(Ord arcInfo, Ord nodeInfo) =>
Eq (ArcData nodeInfo arcInfo)
Ord)

-- ---------------------------------------------------------------------------
-- Instances
-- ---------------------------------------------------------------------------

-- The Show instances are mainly there for debugging purposes.
instance (Show nodeInfo,Show arcInfo)
      => Show (PureGraph nodeInfo arcInfo) where
   show :: PureGraph nodeInfo arcInfo -> String
show (PureGraph Map nodeInfo (NodeData nodeInfo arcInfo)
fm) = [(nodeInfo, NodeData nodeInfo arcInfo)] -> String
forall a. Show a => a -> String
show (Map nodeInfo (NodeData nodeInfo arcInfo)
-> [(nodeInfo, NodeData nodeInfo arcInfo)]
forall k a. Map k a -> [(k, a)]
Map.toList Map nodeInfo (NodeData nodeInfo arcInfo)
fm)

instance Show (PartialShow (PureGraph nodeInfo arcInfo)) where
   show :: PartialShow (PureGraph nodeInfo arcInfo) -> String
show (PartialShow (PureGraph Map nodeInfo (NodeData nodeInfo arcInfo)
fm)) = String
"NParents dump :"
      String -> ShowS
forall a. [a] -> [a] -> [a]
++ PartialShow [NodeData nodeInfo arcInfo] -> String
forall a. Show a => a -> String
show ([NodeData nodeInfo arcInfo]
-> PartialShow [NodeData nodeInfo arcInfo]
forall a. a -> PartialShow a
PartialShow (Map nodeInfo (NodeData nodeInfo arcInfo)
-> [NodeData nodeInfo arcInfo]
forall k a. Map k a -> [a]
Map.elems Map nodeInfo (NodeData nodeInfo arcInfo)
fm))

instance Show (PartialShow (NodeData nodeInfo arcInfo)) where
   show :: PartialShow (NodeData nodeInfo arcInfo) -> String
show (PartialShow NodeData nodeInfo arcInfo
nodeData) = String
"#"String -> ShowS
forall a. [a] -> [a] -> [a]
++Int -> String
forall a. Show a => a -> String
show ([ArcData nodeInfo arcInfo] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (NodeData nodeInfo arcInfo -> [ArcData nodeInfo arcInfo]
forall nodeInfo arcInfo.
NodeData nodeInfo arcInfo -> [ArcData nodeInfo arcInfo]
parents NodeData nodeInfo arcInfo
nodeData))

-- ---------------------------------------------------------------------------
-- Creating and modifying graphs
-- ---------------------------------------------------------------------------

emptyPureGraph :: Ord nodeInfo => PureGraph nodeInfo arcInfo
emptyPureGraph :: PureGraph nodeInfo arcInfo
emptyPureGraph = Map nodeInfo (NodeData nodeInfo arcInfo)
-> PureGraph nodeInfo arcInfo
forall nodeInfo arcInfo.
Map nodeInfo (NodeData nodeInfo arcInfo)
-> PureGraph nodeInfo arcInfo
PureGraph Map nodeInfo (NodeData nodeInfo arcInfo)
forall k a. Map k a
Map.empty

-- | add a node with given parent arcs from it.
addNode :: Ord nodeInfo
   => PureGraph nodeInfo arcInfo -> nodeInfo -> [(arcInfo,nodeInfo)]
   -> PureGraph nodeInfo arcInfo
addNode :: PureGraph nodeInfo arcInfo
-> nodeInfo -> [(arcInfo, nodeInfo)] -> PureGraph nodeInfo arcInfo
addNode (PureGraph Map nodeInfo (NodeData nodeInfo arcInfo)
fm) nodeInfo
newNode [(arcInfo, nodeInfo)]
newArcs =
   Map nodeInfo (NodeData nodeInfo arcInfo)
-> PureGraph nodeInfo arcInfo
forall nodeInfo arcInfo.
Map nodeInfo (NodeData nodeInfo arcInfo)
-> PureGraph nodeInfo arcInfo
PureGraph (nodeInfo
-> NodeData nodeInfo arcInfo
-> Map nodeInfo (NodeData nodeInfo arcInfo)
-> Map nodeInfo (NodeData nodeInfo arcInfo)
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert
      nodeInfo
newNode
      (NodeData :: forall nodeInfo arcInfo.
[ArcData nodeInfo arcInfo] -> NodeData nodeInfo arcInfo
NodeData {parents :: [ArcData nodeInfo arcInfo]
parents = ((arcInfo, nodeInfo) -> ArcData nodeInfo arcInfo)
-> [(arcInfo, nodeInfo)] -> [ArcData nodeInfo arcInfo]
forall a b. (a -> b) -> [a] -> [b]
map
         (\ (arcInfo
arcInfo,nodeInfo
target) -> ArcData :: forall nodeInfo arcInfo.
arcInfo -> nodeInfo -> ArcData nodeInfo arcInfo
ArcData {arcInfo :: arcInfo
arcInfo = arcInfo
arcInfo,target :: nodeInfo
target = nodeInfo
target})
         [(arcInfo, nodeInfo)]
newArcs
         }) Map nodeInfo (NodeData nodeInfo arcInfo)
fm
      )

-- | NB.  The graph will end up ill-formed if you delete a node which
-- has parent arcs pointing to it.
deleteNode :: Ord nodeInfo
   => PureGraph nodeInfo arcInfo -> nodeInfo -> PureGraph nodeInfo arcInfo
deleteNode :: PureGraph nodeInfo arcInfo
-> nodeInfo -> PureGraph nodeInfo arcInfo
deleteNode (PureGraph Map nodeInfo (NodeData nodeInfo arcInfo)
fm) nodeInfo
node = Map nodeInfo (NodeData nodeInfo arcInfo)
-> PureGraph nodeInfo arcInfo
forall nodeInfo arcInfo.
Map nodeInfo (NodeData nodeInfo arcInfo)
-> PureGraph nodeInfo arcInfo
PureGraph (nodeInfo
-> Map nodeInfo (NodeData nodeInfo arcInfo)
-> Map nodeInfo (NodeData nodeInfo arcInfo)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete nodeInfo
node Map nodeInfo (NodeData nodeInfo arcInfo)
fm)


-- ---------------------------------------------------------------------------
-- Other Elementary functions
-- ---------------------------------------------------------------------------

toAllNodes :: Ord nodeInfo => PureGraph nodeInfo arcInfo -> [nodeInfo]
toAllNodes :: PureGraph nodeInfo arcInfo -> [nodeInfo]
toAllNodes (PureGraph Map nodeInfo (NodeData nodeInfo arcInfo)
fm) = Map nodeInfo (NodeData nodeInfo arcInfo) -> [nodeInfo]
forall k a. Map k a -> [k]
Map.keys Map nodeInfo (NodeData nodeInfo arcInfo)
fm

toNodeParents :: Ord nodeInfo => PureGraph nodeInfo arcInfo -> nodeInfo
   -> Maybe [nodeInfo]
toNodeParents :: PureGraph nodeInfo arcInfo -> nodeInfo -> Maybe [nodeInfo]
toNodeParents (PureGraph Map nodeInfo (NodeData nodeInfo arcInfo)
fm) nodeInfo
nodeInfo =
   do
      NodeData nodeInfo arcInfo
nodeData <- nodeInfo
-> Map nodeInfo (NodeData nodeInfo arcInfo)
-> Maybe (NodeData nodeInfo arcInfo)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup nodeInfo
nodeInfo Map nodeInfo (NodeData nodeInfo arcInfo)
fm
      [nodeInfo] -> Maybe [nodeInfo]
forall (m :: * -> *) a. Monad m => a -> m a
return (NodeData nodeInfo arcInfo -> [nodeInfo]
forall nodeInfo arcInfo. NodeData nodeInfo arcInfo -> [nodeInfo]
parentNodes NodeData nodeInfo arcInfo
nodeData)

nodeExists :: Ord nodeInfo => PureGraph nodeInfo arcInfo -> nodeInfo -> Bool
nodeExists :: PureGraph nodeInfo arcInfo -> nodeInfo -> Bool
nodeExists (PureGraph Map nodeInfo (NodeData nodeInfo arcInfo)
fm) nodeInfo
nodeInfo = nodeInfo -> Map nodeInfo (NodeData nodeInfo arcInfo) -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member nodeInfo
nodeInfo Map nodeInfo (NodeData nodeInfo arcInfo)
fm

mapArcInfo :: (arcInfo1 -> arcInfo2) -> PureGraph nodeInfo arcInfo1
   -> PureGraph nodeInfo arcInfo2
mapArcInfo :: (arcInfo1 -> arcInfo2)
-> PureGraph nodeInfo arcInfo1 -> PureGraph nodeInfo arcInfo2
mapArcInfo arcInfo1 -> arcInfo2
mapArc (PureGraph Map nodeInfo (NodeData nodeInfo arcInfo1)
fm) =
   Map nodeInfo (NodeData nodeInfo arcInfo2)
-> PureGraph nodeInfo arcInfo2
forall nodeInfo arcInfo.
Map nodeInfo (NodeData nodeInfo arcInfo)
-> PureGraph nodeInfo arcInfo
PureGraph ((nodeInfo
 -> NodeData nodeInfo arcInfo1 -> NodeData nodeInfo arcInfo2)
-> Map nodeInfo (NodeData nodeInfo arcInfo1)
-> Map nodeInfo (NodeData nodeInfo arcInfo2)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey
      (\ nodeInfo
_ NodeData nodeInfo arcInfo1
nodeData1 ->
         let
            parents1 :: [ArcData nodeInfo arcInfo1]
parents1 = NodeData nodeInfo arcInfo1 -> [ArcData nodeInfo arcInfo1]
forall nodeInfo arcInfo.
NodeData nodeInfo arcInfo -> [ArcData nodeInfo arcInfo]
parents NodeData nodeInfo arcInfo1
nodeData1
            parents2 :: [ArcData nodeInfo arcInfo2]
parents2 = (ArcData nodeInfo arcInfo1 -> ArcData nodeInfo arcInfo2)
-> [ArcData nodeInfo arcInfo1] -> [ArcData nodeInfo arcInfo2]
forall a b. (a -> b) -> [a] -> [b]
map
               (\ ArcData nodeInfo arcInfo1
arcData1 -> ArcData nodeInfo arcInfo1
arcData1 {arcInfo :: arcInfo2
arcInfo = arcInfo1 -> arcInfo2
mapArc (ArcData nodeInfo arcInfo1 -> arcInfo1
forall nodeInfo arcInfo. ArcData nodeInfo arcInfo -> arcInfo
arcInfo ArcData nodeInfo arcInfo1
arcData1)})
               [ArcData nodeInfo arcInfo1]
parents1
         in
            NodeData nodeInfo arcInfo1
nodeData1 {parents :: [ArcData nodeInfo arcInfo2]
parents = [ArcData nodeInfo arcInfo2]
parents2}
         )
      Map nodeInfo (NodeData nodeInfo arcInfo1)
fm
      )

parentNodes :: NodeData nodeInfo arcInfo -> [nodeInfo]
parentNodes :: NodeData nodeInfo arcInfo -> [nodeInfo]
parentNodes NodeData nodeInfo arcInfo
nodeData = (ArcData nodeInfo arcInfo -> nodeInfo)
-> [ArcData nodeInfo arcInfo] -> [nodeInfo]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ArcData nodeInfo arcInfo -> nodeInfo
forall nodeInfo arcInfo. ArcData nodeInfo arcInfo -> nodeInfo
target (NodeData nodeInfo arcInfo -> [ArcData nodeInfo arcInfo]
forall nodeInfo arcInfo.
NodeData nodeInfo arcInfo -> [ArcData nodeInfo arcInfo]
parents NodeData nodeInfo arcInfo
nodeData)