module GNFA
where
import RegExp
import qualified SimpRegExp as R
import qualified NFAe as Ne
import Auxfuns

import PP
import PrintNFAe

data GNFA q s = GNFA { states :: [q],
                       symbols :: [s],
                       delta :: q -> q -> RegExp s,
                       start :: q,
                       final :: q
                     }

data Distinguished = Start | Final deriving (Eq,Ord,Show)

mkunion [] = Empty
mkunion [r] = r
mkunion (r:rs) = Union r (mkunion rs)

nfaeToGnfa (Ne.NFAe { Ne.states = bigQ, Ne.symbols = sigma, Ne.delta = d, Ne.start = q0, Ne.final = f})
    = GNFA { states = (map Left [Start, Final]) ++ (map Right bigQ),
             symbols = sigma, 
             delta = d',
             start = Left Start,
             final = Left Final
           }
      where
        sigmaE            = Nothing : map Just sigma
        dGraph            = [((Right p,Right q), mkunion [maybeRegExp a | a <- sigmaE, elem q (d p a)])
                                 | p <- bigQ, q <- bigQ] 
        initialTransition = [((Left Start, Right q0),Lambda)]
        finalTransitions  = [((Right q, Left Final),Lambda) | q <- f]
        alist             = dGraph ++ initialTransition ++ finalTransitions
        d' p q            = case lookup (p,q) alist of { Just r -> r; Nothing -> Empty }
                          
maybeRegExp (Just a) = One a
maybeRegExp Nothing = Lambda

rip m = let distinguished = [start m, final m]
            candidate = filter (\q -> not $ elem q distinguished) (states m)
            d = delta m
        in case candidate of 
             [] -> m
             (qrip:qs) -> m {states = distinguished ++ qs, delta = d'}
                 where d' p q = Union (Cat (Cat r1 (Star r2)) r3) r4
                           where
                             r1 = d p qrip
                             r2 = d qrip qrip
                             r3 = d qrip q
                             r4 = d p q

simp m = m { delta = \p q -> R.simp (delta m p q) }

iter 0 f x = x
iter n f x = f (iter (n-1) f x)

gnfaToRegExp m = simp $ iter ((length $ states m) - 2) rip m

iter' 0 f x = [x]
iter' n f x = x : iter' (n-1) f (f x)

gnfaToRegExp' m = iter' ((length $ states m) - 2) (simp . rip) m