module Data.Attoparsec.Text.FastSet
(
FastSet
, fromList
, set
, member
, charClass
) where
import Data.List (sort)
import qualified Data.Array.Base as AB
import qualified Data.Array.Unboxed as A
import qualified Data.Text as T
newtype FastSet = FastSet (A.UArray Int Char)
deriving (Eq, Ord, Show)
set :: T.Text -> FastSet
set t = mkSet (T.length t) (sort $ T.unpack t)
fromList :: [Char] -> FastSet
fromList cs = mkSet (length cs) (sort cs)
mkSet :: Int -> [Char] -> FastSet
mkSet l = FastSet . A.listArray (0,l1)
member :: Char -> FastSet -> Bool
member c (FastSet a) = uncurry search (A.bounds a)
where search lo hi
| hi < lo = False
| otherwise =
let mid = (lo + hi) `div` 2
in case compare c (AB.unsafeAt a mid) of
GT -> search (mid + 1) hi
LT -> search lo (mid 1)
_ -> True
charClass :: String -> FastSet
charClass = fromList . go
where go (a:'-':b:xs) = [a..b] ++ go xs
go (x:xs) = x : go xs
go _ = ""