module Data.Regex.Antimirov.Simplify where
import qualified Data.Set as Set
import Data.Regex.Antimirov.Regex
simplify (Literal a) = Literal a
simplify Empty = Empty
simplify arg@(Or _ _) = foldl1 Or (map simplify $ Set.elems $ getOr arg)
simplify (Then r1' r2')
| Empty <- r1 = r2
| Empty <- r2 = r1
| otherwise = Then r1 r2
where
r1 = simplify r1'
r2 = simplify r2'
simplify (Star r)
| rset == Set.empty = Empty
| otherwise = Star (simplify $ foldl1 Or $ Set.toList rset)
where
rset = Set.filter (/= Empty) $ cluster r
cluster Empty = Set.empty
cluster (Literal a) = Set.singleton (Literal a)
cluster (Or r1 r2) = cluster r1 `Set.union` cluster r2
cluster a@(Then r1 r2)
| nullable r1 && nullable r2 = cluster r1 `Set.union` cluster r2
| otherwise = Set.singleton a
cluster (Star r) = cluster r
getOr :: Ord a => Regex a -> Set.Set (Regex a)
getOr (Or r1 r2) = getOr r1 `Set.union` getOr r2
getOr r = Set.singleton r