{-# LANGUAGE PatternGuards #-}

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