- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
topSort :: V.Vector ([Int], [Int])
-> Either String [Int]
topSort kob =
let
sup u k = do
let max i = (i,) . head . snd <$> k `MV.read` i
l <- mapM max u
case filter (uncurry (==)) l of
[(a,_)] -> return $ Right a
x -> return $ Left "Topology error"
rewrite k s (i, j) = do
let f x | x == s && j < 0 = []
| x == s = [j]
| otherwise = [x]
when (j>=0) $ MV.modify k (_1 %~ (i:)) j
MV.modify k (_2 %~ (>>= f)) i
go u k =
readSTRef u >>= \case
[a] -> return $ Right [a]
u_ -> sup u_ k >>= \case
Right s -> do
modifySTRef' u $ Data.List.delete s
s_d <- fst <$> MV.read k s
mapM_ (rewrite k s) $ zip s_d (tail s_d ++ [-1])
tail <- go u k
return $ (s:) <$> tail
Left err ->
return $ Left err
in runST $ do
u <- newSTRef $ [0..V.length kob-1]
k <- V.thaw kob
liftM reverse <$> go u k