>
>
> module Text.Regex.Deriv.Common
> ( Range(..), range, minRange, maxRange
> , Letter
> , PosEpsilon (..)
> , IsEpsilon (..)
> , IsPhi (..)
> , Simplifiable (..)
> , my_hash
> , my_lookup
> , GFlag (..)
> , IsGreedy (..)
> , nub2
> , nub3
> , preBinder
> , preBinder_
> , subBinder
> , mainBinder
> ) where
> import Data.Char (ord)
> import qualified Data.IntMap as IM
> import qualified Data.BitSet as BS
> import Data.List (nubBy)
>
>
> data Range = Range !Int !Int deriving (Show, Ord)
> instance Eq Range where
> (==) (Range x y) (Range w z) = (x == w) && (y == z)
> range :: Int -> Int -> Range
> range = Range
> minRange = fst
> maxRange = snd
>
> type Letter = (Char,Int)
>
> class PosEpsilon a where
> posEpsilon :: a -> Bool
>
> class IsEpsilon a where
> isEpsilon :: a -> Bool
>
> class IsPhi a where
> isPhi :: a -> Bool
> class Simplifiable a where
> simplify :: a -> a
> my_hash :: Int -> Char -> Int
> my_hash i x = (ord x) + 256 * i
the lookup function
> my_lookup :: Int -> Char -> IM.IntMap [Int] -> [Int]
> my_lookup i x dict = case IM.lookup (my_hash i x) dict of
> Just ys -> ys
> Nothing -> []
>
> data GFlag = Greedy
> | NotGreedy
> deriving Eq
> instance Show GFlag where
> show Greedy = ""
> show NotGreedy = "?"
> class IsGreedy a where
> isGreedy :: a -> Bool
>
> nub2 :: [(Int,a)] -> [(Int,a)]
> nub2 [] = []
> nub2 [x] = [x]
>
> nub2 ls = nub2sub IM.empty ls
>
> nub2sub im [] = []
> nub2sub im (x@(k,_):xs) =
>
> case IM.lookup k im of
> Just _ -> xs `seq` nub2sub im xs
> Nothing -> let im' = IM.insert k () im
> in im' `seq` xs `seq` x:(nub2sub im' xs)
>
> nub2aux bs [] acc = reverse acc
> nub2aux bs (x@(k,_):xs) acc =
> case bs `seq` k `seq` BS.member k bs of
> True -> xs `seq` nub2aux bs xs acc
> False -> let bs' = BS.insert k bs
> in bs' `seq` xs `seq` (nub2aux bs' xs (x:acc))
> nub3 :: [(Int,a,Int)] -> [(Int,a,Int)]
> nub3 [] = []
> nub3 [x] = [x]
> nub3 ls = nub3subsimple IM.empty ls
let (_,ls') = nub3sub IM.empty ls
in ls'
> nub3subsimple :: IM.IntMap () -> [(Int,a,Int)] -> [(Int,a,Int)]
> nub3subsimple im [] = []
> nub3subsimple im [ x ] = [ x ]
> nub3subsimple im (x@(k,f,0):xs) = x:(nub3subsimple im xs)
> nub3subsimple im (x@(k,f,1):xs) = let im' = IM.insert k () im
> in im' `seq` x:(nub3subsimple im' xs)
> nub3subsimple im (x@(k,f,n):xs) = case IM.lookup k im of
> Just _ -> nub3subsimple im xs
> Nothing -> let im' = IM.insert k () im
> in im' `seq` xs `seq` x:(nub3subsimple im' xs)
> nub3sub :: IM.IntMap () -> [(Int,a,Int)] -> (IM.IntMap (), [(Int,a,Int)])
>
> nub3sub im [] = (im,[])
> nub3sub im [(k,f,0)] = (im, [(k,f,0)])
> nub3sub im [(k,f,1)] = let im' = IM.insert k () im
> in (im', [(k,f,1)])
> nub3sub im (x@(k,f,0):xs) = let (im',xs') = nub3sub im xs
> in (im',x:xs')
> nub3sub im (x@(k,f,1):xs) = let im' = IM.insert k () im
> (im'', xs') = nub3sub im' xs
> in (im'', x:xs')
> nub3sub im (x@(k,f,n):xs) = case IM.lookup k im of
> Just _ -> nub3sub im xs
> Nothing -> let (im', xs') = nub3sub im xs
> in case IM.lookup k im' of
> Just _ -> (im', xs')
> Nothing -> (im', x:xs')
The smallest binder index capturing the prefix of the unanchored regex
> preBinder :: Int
> preBinder = 1
> preBinder_ :: Int
> preBinder_ = 2
The largest binder index capturing for the suffix of the unanchored regex
> subBinder :: Int
> subBinder = 2147483647
The binder index capturing substring which matches by the unanchored regex
> mainBinder :: Int
> mainBinder = 0