{-# OPTIONS -fno-spec-constr-count #-}
module Algo.AwShCC (awshcc) where

import Data.Vector.Unboxed as V

awshcc :: (Int, Vector Int, Vector Int) -> Vector Int
{-# NOINLINE awshcc #-}
awshcc (n, es1, es2) = concomp ds es1' es2'
    where
      ds = V.enumFromTo 0 (n-1) V.++ V.enumFromTo 0 (n-1)
      es1' = es1 V.++ es2
      es2' = es2 V.++ es1

      starCheck ds = V.backpermute st' gs
        where
          gs  = V.backpermute ds ds
          st  = V.zipWith (==) ds gs
          st' = V.update st . V.filter (not . snd)
                            $ V.zip gs st

      concomp ds es1 es2
        | V.and (starCheck ds'') = ds''
        | otherwise              = concomp (V.backpermute ds'' ds'') es1 es2
        where
          ds'  = V.update ds
               . V.map (\(di, dj, gi) -> (di, dj))
               . V.filter (\(di, dj, gi) -> gi == di && di > dj)
               $ V.zip3 (V.backpermute ds es1)
                        (V.backpermute ds es2)
                        (V.backpermute ds (V.backpermute ds es1))

          ds'' = V.update ds'
               . V.map (\(di, dj, st) -> (di, dj))
               . V.filter (\(di, dj, st) -> st && di /= dj)
               $ V.zip3 (V.backpermute ds' es1)
                        (V.backpermute ds' es2)
                        (V.backpermute (starCheck ds') es1)