module Hakyll.Core.DirectedGraph.DependencySolver
( solveDependencies
) where
import Prelude
import qualified Prelude as P
import Data.Set (Set)
import Data.Maybe (mapMaybe)
import qualified Data.Map as M
import qualified Data.Set as S
import Hakyll.Core.DirectedGraph
import Hakyll.Core.DirectedGraph.Internal
solveDependencies :: Ord a
=> DirectedGraph a
-> [a]
solveDependencies = P.reverse . order [] [] S.empty
order :: Ord a
=> [a]
-> [Node a]
-> Set a
-> DirectedGraph a
-> [a]
order temp stack set graph@(DirectedGraph graph')
| M.null graph' = temp
| otherwise = case stack of
[] ->
let (tag, node) = M.findMin graph'
in order temp (node : stack) (S.insert tag set) graph
(node : stackTail) ->
let tag = nodeTag node
deps = S.toList $ nodeNeighbours node
unsatisfied = mapMaybe (`M.lookup` graph') deps
in case unsatisfied of
[] -> order (tag : temp) stackTail (S.delete tag set)
(DirectedGraph $ M.delete tag graph')
(dep : _) -> if nodeTag dep `S.member` set
then cycleError
else order temp (dep : node : stackTail)
(S.insert (nodeTag dep) set)
graph
where
cycleError = error $ "Hakyll.Core.DirectedGraph.DependencySolver.order: "
++ "Cycle detected!"