module Hydra.Sorting where

import qualified Data.List as L
import qualified Data.Bifunctor as BF


-- Note: requires a DAG (the ordering is incomplete in the presence of cycles).
topologicalSort :: Eq a => [(a, [a])] -> Maybe [a]
topologicalSort :: forall a. Eq a => [(a, [a])] -> Maybe [a]
topologicalSort [(a, [a])]
pairs = if forall (t :: * -> *) a. Foldable t => t a -> Int
L.length [a]
result forall a. Ord a => a -> a -> Bool
< forall (t :: * -> *) a. Foldable t => t a -> Int
L.length [(a, [a])]
pairs
    then forall a. Maybe a
Nothing
    else forall a. a -> Maybe a
Just [a]
result
  where
    result :: [a]
result = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl forall {a}. Eq a => [a] -> (a, [a]) -> [a]
makePrecede [] [(a, [a])]
pairs
    makePrecede :: [a] -> (a, [a]) -> [a]
makePrecede [a]
ts (a
x, [a]
xs) = forall a. Eq a => [a] -> [a]
L.nub forall a b. (a -> b) -> a -> b
$
      case forall a. Eq a => a -> [a] -> Maybe Int
L.elemIndex a
x [a]
ts of
        Just Int
i -> forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a. [a] -> [a] -> [a]
(++) forall a b. (a -> b) -> a -> b
$ forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
BF.first (forall a. [a] -> [a] -> [a]
++ [a]
xs) forall a b. (a -> b) -> a -> b
$ forall a. Int -> [a] -> ([a], [a])
splitAt Int
i [a]
ts
        Maybe Int
_ -> [a]
ts forall a. [a] -> [a] -> [a]
++ [a]
xs forall a. [a] -> [a] -> [a]
++ [a
x]