{-# OPTIONS_GHC -fspec-constr #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveDataTypeable #-}
#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Trustworthy #-}
#endif
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.CharSet
-- Copyright   :  (c) Edward Kmett 2010-2011
-- License     :  BSD3
-- Maintainer  :  ekmett@gmail.com
-- Stability   :  experimental
-- Portability :  portable
--
-- A CharSet is an /efficient/ representation of a set of 'Char' values
-- designed for fast membership tests.
--
-- As an example @build isAlpha@ will create a set of alphabetic characters.
-- We can then use 'member' on the generated set to /efficiently/ test if a
-- given @Char@ represents an alphabetic character.
--
-- Designed to be imported qualified:
--
-- > import Data.CharSet (CharSet)
-- > import qualified Data.CharSet as CharSet
--
-------------------------------------------------------------------------------

module Data.CharSet
    (
    -- * Set type
      CharSet(..)
    -- * Operators
    , (\\)
    -- * Query
    , null
    , size
    , member
    , notMember
    , overlaps, isSubsetOf
    , isComplemented
    -- * Construction
    , build
    , empty
    , singleton
    , full
    , insert
    , delete
    , complement
    , range
    -- * Combine
    , union
    , intersection
    , difference
    -- * Filter
    , filter
    , partition
    -- * Map
    , map
    -- * Fold
    , fold
    -- * Conversion
    -- ** List
    , toList
    , fromList
    -- ** Ordered list
    , toAscList
    , fromAscList
    , fromDistinctAscList
    -- ** IntMaps
    , fromCharSet
    , toCharSet
    -- ** Array
    , toArray
    ) where

#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 608
import Data.String (IsString(..))
-- <<< -XOverloadedStrings >>> was introduced by GHC 6.8.1
#endif

import Data.Array.Unboxed hiding (range)
import Data.Data
import Data.Function (on)
import Data.IntSet (IntSet)
import Data.CharSet.ByteSet (ByteSet)
import qualified Data.CharSet.ByteSet as ByteSet
import Data.Bits hiding (complement)
import Data.Word
import Data.ByteString.Internal (c2w)
import Data.Semigroup
import qualified Data.IntSet as I
import qualified Data.List as L
import Prelude hiding (filter, map, null)
import qualified Prelude as P
import Text.Read

-- | Stored as a (possibly negated) IntSet and a fast set used for the head byte.
--
-- The set of valid (possibly negated) head bytes is stored unboxed as a 32-byte
-- bytestring-based lookup table.
data CharSet = CharSet
    !Bool    -- Whether ByteSet and IntSet are negated
    !ByteSet -- Set of head bytes, unboxed
    !IntSet  -- Set of characters in the charset
  deriving Typeable

#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 608
-- | @= CharSet.`fromList`@
instance IsString CharSet where
  fromString :: String -> CharSet
fromString = String -> CharSet
fromList
#endif

charSet :: Bool -> IntSet -> CharSet
charSet :: Bool -> IntSet -> CharSet
charSet Bool
b IntSet
s = Bool -> ByteSet -> IntSet -> CharSet
CharSet Bool
b ([Word8] -> ByteSet
ByteSet.fromList (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Int -> Word8
headByte (IntSet -> [Int]
I.toAscList IntSet
s))) IntSet
s

headByte :: Int -> Word8
headByte :: Int -> Word8
headByte Int
i
  | Int
i forall a. Ord a => a -> a -> Bool
<= Int
0x7f   = forall a. Enum a => Int -> a
toEnum Int
i
  | Int
i forall a. Ord a => a -> a -> Bool
<= Int
0x7ff  = forall a. Enum a => Int -> a
toEnum forall a b. (a -> b) -> a -> b
$ Int
0x80 forall a. Num a => a -> a -> a
+ (Int
i forall a. Bits a => a -> Int -> a
`shiftR` Int
6)
  | Int
i forall a. Ord a => a -> a -> Bool
<= Int
0xffff = forall a. Enum a => Int -> a
toEnum forall a b. (a -> b) -> a -> b
$ Int
0xe0 forall a. Num a => a -> a -> a
+ (Int
i forall a. Bits a => a -> Int -> a
`shiftR` Int
12)
  | Bool
otherwise   = forall a. Enum a => Int -> a
toEnum forall a b. (a -> b) -> a -> b
$ Int
0xf0 forall a. Num a => a -> a -> a
+ (Int
i forall a. Bits a => a -> Int -> a
`shiftR` Int
18)

pos :: IntSet -> CharSet
pos :: IntSet -> CharSet
pos = Bool -> IntSet -> CharSet
charSet Bool
True

neg :: IntSet -> CharSet
neg :: IntSet -> CharSet
neg = Bool -> IntSet -> CharSet
charSet Bool
False

(\\) :: CharSet -> CharSet -> CharSet
\\ :: CharSet -> CharSet -> CharSet
(\\) = CharSet -> CharSet -> CharSet
difference

-- | Applies a predicate across the whole range of possible character values
-- to create a set of only those characters which satisfy the predicate.
--
-- As an example @build isAlpha@ will generate a CharSet of all
-- alphabetic characters.
build :: (Char -> Bool) -> CharSet
build :: (Char -> Bool) -> CharSet
build Char -> Bool
p = String -> CharSet
fromDistinctAscList forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
P.filter Char -> Bool
p [forall a. Bounded a => a
minBound .. forall a. Bounded a => a
maxBound]
{-# INLINE build #-}

map :: (Char -> Char) -> CharSet -> CharSet
map :: (Char -> Char) -> CharSet -> CharSet
map Char -> Char
f (CharSet Bool
True ByteSet
_ IntSet
i) = IntSet -> CharSet
pos ((Int -> Int) -> IntSet -> IntSet
I.map (forall a. Enum a => a -> Int
fromEnum forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Char
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => Int -> a
toEnum) IntSet
i)
map Char -> Char
f (CharSet Bool
False ByteSet
_ IntSet
i) = String -> CharSet
fromList forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
P.map Char -> Char
f forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
P.filter (\Char
x -> forall a. Enum a => a -> Int
fromEnum Char
x Int -> IntSet -> Bool
`I.notMember` IntSet
i) [Char
ul..Char
uh]
{-# INLINE map #-}

isComplemented :: CharSet -> Bool
isComplemented :: CharSet -> Bool
isComplemented (CharSet Bool
True ByteSet
_ IntSet
_) = Bool
False
isComplemented (CharSet Bool
False ByteSet
_ IntSet
_) = Bool
True
{-# INLINE isComplemented #-}

toList :: CharSet -> String
toList :: CharSet -> String
toList (CharSet Bool
True ByteSet
_ IntSet
i) = forall a b. (a -> b) -> [a] -> [b]
P.map forall a. Enum a => Int -> a
toEnum (IntSet -> [Int]
I.toList IntSet
i)
toList (CharSet Bool
False ByteSet
_ IntSet
i) = forall a. (a -> Bool) -> [a] -> [a]
P.filter (\Char
x -> forall a. Enum a => a -> Int
fromEnum Char
x Int -> IntSet -> Bool
`I.notMember` IntSet
i) [Char
ul..Char
uh]
{-# INLINE toList #-}

toAscList :: CharSet -> String
toAscList :: CharSet -> String
toAscList (CharSet Bool
True ByteSet
_ IntSet
i) = forall a b. (a -> b) -> [a] -> [b]
P.map forall a. Enum a => Int -> a
toEnum (IntSet -> [Int]
I.toAscList IntSet
i)
toAscList (CharSet Bool
False ByteSet
_ IntSet
i) = forall a. (a -> Bool) -> [a] -> [a]
P.filter (\Char
x -> forall a. Enum a => a -> Int
fromEnum Char
x Int -> IntSet -> Bool
`I.notMember` IntSet
i) [Char
ul..Char
uh]
{-# INLINE toAscList #-}

empty :: CharSet
empty :: CharSet
empty = IntSet -> CharSet
pos IntSet
I.empty

singleton :: Char -> CharSet
singleton :: Char -> CharSet
singleton = IntSet -> CharSet
pos forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntSet
I.singleton forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => a -> Int
fromEnum
{-# INLINE singleton #-}

full :: CharSet
full :: CharSet
full = IntSet -> CharSet
neg IntSet
I.empty

-- | /O(n)/ worst case
null :: CharSet -> Bool
null :: CharSet -> Bool
null (CharSet Bool
True ByteSet
_ IntSet
i) = IntSet -> Bool
I.null IntSet
i
null (CharSet Bool
False ByteSet
_ IntSet
i) = IntSet -> Int
I.size IntSet
i forall a. Eq a => a -> a -> Bool
== Int
numChars
{-# INLINE null #-}

-- | /O(n)/
size :: CharSet -> Int
size :: CharSet -> Int
size (CharSet Bool
True ByteSet
_ IntSet
i) = IntSet -> Int
I.size IntSet
i
size (CharSet Bool
False ByteSet
_ IntSet
i) = Int
numChars forall a. Num a => a -> a -> a
- IntSet -> Int
I.size IntSet
i
{-# INLINE size #-}

insert :: Char -> CharSet -> CharSet
insert :: Char -> CharSet -> CharSet
insert Char
c (CharSet Bool
True ByteSet
_ IntSet
i) = IntSet -> CharSet
pos (Int -> IntSet -> IntSet
I.insert (forall a. Enum a => a -> Int
fromEnum Char
c) IntSet
i)
insert Char
c (CharSet Bool
False ByteSet
_ IntSet
i) = IntSet -> CharSet
neg (Int -> IntSet -> IntSet
I.delete (forall a. Enum a => a -> Int
fromEnum Char
c) IntSet
i)
{-# INLINE insert #-}

range :: Char -> Char -> CharSet
range :: Char -> Char -> CharSet
range Char
a Char
b
  | Char
a forall a. Ord a => a -> a -> Bool
<= Char
b = String -> CharSet
fromDistinctAscList [Char
a..Char
b]
  | Bool
otherwise = CharSet
empty

delete :: Char -> CharSet -> CharSet
delete :: Char -> CharSet -> CharSet
delete Char
c (CharSet Bool
True ByteSet
_ IntSet
i) = IntSet -> CharSet
pos (Int -> IntSet -> IntSet
I.delete (forall a. Enum a => a -> Int
fromEnum Char
c) IntSet
i)
delete Char
c (CharSet Bool
False ByteSet
_ IntSet
i) = IntSet -> CharSet
neg (Int -> IntSet -> IntSet
I.insert (forall a. Enum a => a -> Int
fromEnum Char
c) IntSet
i)
{-# INLINE delete #-}

complement :: CharSet -> CharSet
complement :: CharSet -> CharSet
complement (CharSet Bool
True ByteSet
s IntSet
i) = Bool -> ByteSet -> IntSet -> CharSet
CharSet Bool
False ByteSet
s IntSet
i
complement (CharSet Bool
False ByteSet
s IntSet
i) = Bool -> ByteSet -> IntSet -> CharSet
CharSet Bool
True ByteSet
s IntSet
i
{-# INLINE complement #-}

union :: CharSet -> CharSet -> CharSet
union :: CharSet -> CharSet -> CharSet
union (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = IntSet -> CharSet
pos (IntSet -> IntSet -> IntSet
I.union IntSet
i IntSet
j)
union (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = IntSet -> CharSet
neg (IntSet -> IntSet -> IntSet
I.difference IntSet
j IntSet
i)
union (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = IntSet -> CharSet
neg (IntSet -> IntSet -> IntSet
I.difference IntSet
i IntSet
j)
union (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = IntSet -> CharSet
neg (IntSet -> IntSet -> IntSet
I.intersection IntSet
i IntSet
j)
{-# INLINE union #-}

intersection :: CharSet -> CharSet -> CharSet
intersection :: CharSet -> CharSet -> CharSet
intersection (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = IntSet -> CharSet
pos (IntSet -> IntSet -> IntSet
I.intersection IntSet
i IntSet
j)
intersection (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = IntSet -> CharSet
pos (IntSet -> IntSet -> IntSet
I.difference IntSet
i IntSet
j)
intersection (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = IntSet -> CharSet
pos (IntSet -> IntSet -> IntSet
I.difference IntSet
j IntSet
i)
intersection (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = IntSet -> CharSet
neg (IntSet -> IntSet -> IntSet
I.union IntSet
i IntSet
j)
{-# INLINE intersection #-}

difference :: CharSet -> CharSet -> CharSet
difference :: CharSet -> CharSet -> CharSet
difference (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = IntSet -> CharSet
pos (IntSet -> IntSet -> IntSet
I.difference IntSet
i IntSet
j)
difference (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = IntSet -> CharSet
pos (IntSet -> IntSet -> IntSet
I.intersection IntSet
i IntSet
j)
difference (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = IntSet -> CharSet
neg (IntSet -> IntSet -> IntSet
I.union IntSet
i IntSet
j)
difference (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = IntSet -> CharSet
pos (IntSet -> IntSet -> IntSet
I.difference IntSet
j IntSet
i)
{-# INLINE difference #-}

member :: Char -> CharSet -> Bool
member :: Char -> CharSet -> Bool
member Char
c (CharSet Bool
True ByteSet
b IntSet
i)
  | Char
c forall a. Ord a => a -> a -> Bool
<= forall a. Enum a => Int -> a
toEnum Int
0x7f = Word8 -> ByteSet -> Bool
ByteSet.member (Char -> Word8
c2w Char
c) ByteSet
b
  | Bool
otherwise        = Int -> IntSet -> Bool
I.member (forall a. Enum a => a -> Int
fromEnum Char
c) IntSet
i
member Char
c (CharSet Bool
False ByteSet
b IntSet
i)
  | Char
c forall a. Ord a => a -> a -> Bool
<= forall a. Enum a => Int -> a
toEnum Int
0x7f = Bool -> Bool
not (Word8 -> ByteSet -> Bool
ByteSet.member (Char -> Word8
c2w Char
c) ByteSet
b)
  | Bool
otherwise        = Int -> IntSet -> Bool
I.notMember (forall a. Enum a => a -> Int
fromEnum Char
c) IntSet
i
{-# INLINE member #-}

notMember :: Char -> CharSet -> Bool
notMember :: Char -> CharSet -> Bool
notMember Char
c CharSet
s = Bool -> Bool
not (Char -> CharSet -> Bool
member Char
c CharSet
s)
{-# INLINE notMember #-}

fold :: (Char -> b -> b) -> b -> CharSet -> b
fold :: forall b. (Char -> b -> b) -> b -> CharSet -> b
fold Char -> b -> b
f b
z (CharSet Bool
True ByteSet
_ IntSet
i) = forall b. (Int -> b -> b) -> b -> IntSet -> b
I.fold (Char -> b -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => Int -> a
toEnum) b
z IntSet
i
fold Char -> b -> b
f b
z (CharSet Bool
False ByteSet
_ IntSet
i) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Char -> b -> b
f b
z forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
P.filter (\Char
x -> forall a. Enum a => a -> Int
fromEnum Char
x Int -> IntSet -> Bool
`I.notMember` IntSet
i) [Char
ul..Char
uh]
{-# INLINE fold #-}

filter :: (Char -> Bool) -> CharSet -> CharSet
filter :: (Char -> Bool) -> CharSet -> CharSet
filter Char -> Bool
p (CharSet Bool
True ByteSet
_ IntSet
i) = IntSet -> CharSet
pos ((Int -> Bool) -> IntSet -> IntSet
I.filter (Char -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => Int -> a
toEnum) IntSet
i)
filter Char -> Bool
p (CharSet Bool
False ByteSet
_ IntSet
i) = IntSet -> CharSet
neg forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Int -> IntSet -> IntSet
I.insert) IntSet
i forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
P.filter (\Int
x -> (Int
x Int -> IntSet -> Bool
`I.notMember` IntSet
i) Bool -> Bool -> Bool
&& Bool -> Bool
not (Char -> Bool
p (forall a. Enum a => Int -> a
toEnum Int
x))) [Int
ol..Int
oh]
{-# INLINE filter #-}

partition :: (Char -> Bool) -> CharSet -> (CharSet, CharSet)
partition :: (Char -> Bool) -> CharSet -> (CharSet, CharSet)
partition Char -> Bool
p (CharSet Bool
True ByteSet
_ IntSet
i) = (IntSet -> CharSet
pos IntSet
l, IntSet -> CharSet
pos IntSet
r)
    where (IntSet
l,IntSet
r) = (Int -> Bool) -> IntSet -> (IntSet, IntSet)
I.partition (Char -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => Int -> a
toEnum) IntSet
i
partition Char -> Bool
p (CharSet Bool
False ByteSet
_ IntSet
i) = (IntSet -> CharSet
neg (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Int -> IntSet -> IntSet
I.insert IntSet
i [Int]
l), IntSet -> CharSet
neg (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Int -> IntSet -> IntSet
I.insert IntSet
i [Int]
r))
    where ([Int]
l,[Int]
r) = forall a. (a -> Bool) -> [a] -> ([a], [a])
L.partition (Char -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => Int -> a
toEnum) forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
P.filter (\Int
x -> Int
x Int -> IntSet -> Bool
`I.notMember` IntSet
i) [Int
ol..Int
oh]
{-# INLINE partition #-}

overlaps :: CharSet -> CharSet -> Bool
overlaps :: CharSet -> CharSet -> Bool
overlaps (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = Bool -> Bool
not (IntSet -> Bool
I.null (IntSet -> IntSet -> IntSet
I.intersection IntSet
i IntSet
j))
overlaps (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = Bool -> Bool
not (IntSet -> IntSet -> Bool
I.isSubsetOf IntSet
j IntSet
i)
overlaps (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = Bool -> Bool
not (IntSet -> IntSet -> Bool
I.isSubsetOf IntSet
i IntSet
j)
overlaps (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\Int
x -> Int -> IntSet -> Bool
I.notMember Int
x IntSet
i Bool -> Bool -> Bool
&& Int -> IntSet -> Bool
I.notMember Int
x IntSet
j) [Int
ol..Int
oh] -- not likely
{-# INLINE overlaps #-}

isSubsetOf :: CharSet -> CharSet -> Bool
isSubsetOf :: CharSet -> CharSet -> Bool
isSubsetOf (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = IntSet -> IntSet -> Bool
I.isSubsetOf IntSet
i IntSet
j
isSubsetOf (CharSet Bool
True ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = IntSet -> Bool
I.null (IntSet -> IntSet -> IntSet
I.intersection IntSet
i IntSet
j)
isSubsetOf (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
True ByteSet
_ IntSet
j) = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (\Int
x -> Int -> IntSet -> Bool
I.member Int
x IntSet
i Bool -> Bool -> Bool
&& Int -> IntSet -> Bool
I.member Int
x IntSet
j) [Int
ol..Int
oh] -- not bloody likely
isSubsetOf (CharSet Bool
False ByteSet
_ IntSet
i) (CharSet Bool
False ByteSet
_ IntSet
j) = IntSet -> IntSet -> Bool
I.isSubsetOf IntSet
j IntSet
i
{-# INLINE isSubsetOf #-}

fromList :: String -> CharSet
fromList :: String -> CharSet
fromList = IntSet -> CharSet
pos forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> IntSet
I.fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
P.map forall a. Enum a => a -> Int
fromEnum
{-# INLINE fromList #-}

fromAscList :: String -> CharSet
fromAscList :: String -> CharSet
fromAscList = IntSet -> CharSet
pos forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> IntSet
I.fromAscList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
P.map forall a. Enum a => a -> Int
fromEnum
{-# INLINE fromAscList #-}

fromDistinctAscList :: String -> CharSet
fromDistinctAscList :: String -> CharSet
fromDistinctAscList = IntSet -> CharSet
pos forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> IntSet
I.fromDistinctAscList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
P.map forall a. Enum a => a -> Int
fromEnum
{-# INLINE fromDistinctAscList #-}

-- isProperSubsetOf :: CharSet -> CharSet -> Bool
-- isProperSubsetOf (P i) (P j) = I.isProperSubsetOf i j
-- isProperSubsetOf (P i) (N j) = null (I.intersection i j) && ...
-- isProperSubsetOf (N i) (N j) = I.isProperSubsetOf j i

ul, uh :: Char
ul :: Char
ul = forall a. Bounded a => a
minBound
uh :: Char
uh = forall a. Bounded a => a
maxBound
{-# INLINE ul #-}
{-# INLINE uh #-}

ol, oh :: Int
ol :: Int
ol = forall a. Enum a => a -> Int
fromEnum Char
ul
oh :: Int
oh = forall a. Enum a => a -> Int
fromEnum Char
uh
{-# INLINE ol #-}
{-# INLINE oh #-}

numChars :: Int
numChars :: Int
numChars = Int
oh forall a. Num a => a -> a -> a
- Int
ol forall a. Num a => a -> a -> a
+ Int
1
{-# INLINE numChars #-}

instance Data CharSet where
  gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> CharSet -> c CharSet
gfoldl forall d b. Data d => c (d -> b) -> d -> c b
k forall g. g -> c g
z CharSet
set
    | CharSet -> Bool
isComplemented CharSet
set = forall g. g -> c g
z CharSet -> CharSet
complement forall d b. Data d => c (d -> b) -> d -> c b
`k` CharSet -> CharSet
complement CharSet
set
    | Bool
otherwise          = forall g. g -> c g
z String -> CharSet
fromList forall d b. Data d => c (d -> b) -> d -> c b
`k` CharSet -> String
toList CharSet
set

  toConstr :: CharSet -> Constr
toConstr CharSet
set
    | CharSet -> Bool
isComplemented CharSet
set = Constr
complementConstr
    | Bool
otherwise = Constr
fromListConstr

  dataTypeOf :: CharSet -> DataType
dataTypeOf CharSet
_ = DataType
charSetDataType

  gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c CharSet
gunfold forall b r. Data b => c (b -> r) -> c r
k forall r. r -> c r
z Constr
c = case Constr -> Int
constrIndex Constr
c of
    Int
1 -> forall b r. Data b => c (b -> r) -> c r
k (forall r. r -> c r
z String -> CharSet
fromList)
    Int
2 -> forall b r. Data b => c (b -> r) -> c r
k (forall r. r -> c r
z CharSet -> CharSet
complement)
    Int
_ -> forall a. HasCallStack => String -> a
error String
"gunfold"

fromListConstr :: Constr
fromListConstr :: Constr
fromListConstr   = DataType -> String -> [String] -> Fixity -> Constr
mkConstr DataType
charSetDataType String
"fromList" [] Fixity
Prefix
{-# NOINLINE fromListConstr #-}

complementConstr :: Constr
complementConstr :: Constr
complementConstr = DataType -> String -> [String] -> Fixity -> Constr
mkConstr DataType
charSetDataType String
"complement" [] Fixity
Prefix
{-# NOINLINE complementConstr #-}

charSetDataType :: DataType
charSetDataType :: DataType
charSetDataType  = String -> [Constr] -> DataType
mkDataType String
"Data.CharSet.CharSet" [Constr
fromListConstr, Constr
complementConstr]
{-# NOINLINE charSetDataType #-}

-- returns an intset and if the charSet is positive
fromCharSet :: CharSet -> (Bool, IntSet)
fromCharSet :: CharSet -> (Bool, IntSet)
fromCharSet (CharSet Bool
b ByteSet
_ IntSet
i) = (Bool
b, IntSet
i)
{-# INLINE fromCharSet #-}

toCharSet :: IntSet -> CharSet
toCharSet :: IntSet -> CharSet
toCharSet = IntSet -> CharSet
pos
{-# INLINE toCharSet #-}

instance Eq CharSet where
  == :: CharSet -> CharSet -> Bool
(==) = forall a. Eq a => a -> a -> Bool
(==) forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` CharSet -> String
toAscList

instance Ord CharSet where
  compare :: CharSet -> CharSet -> Ordering
compare = forall a. Ord a => a -> a -> Ordering
compare forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` CharSet -> String
toAscList

instance Bounded CharSet where
  minBound :: CharSet
minBound = CharSet
empty
  maxBound :: CharSet
maxBound = CharSet
full

-- TODO return a tighter bounded array perhaps starting from the least element present to the last element present?
toArray :: CharSet -> UArray Char Bool
toArray :: CharSet -> UArray Char Bool
toArray CharSet
set = forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
(i, i) -> [(i, e)] -> a i e
array (forall a. Bounded a => a
minBound, forall a. Bounded a => a
maxBound) forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Char
x -> (Char
x, Char
x Char -> CharSet -> Bool
`member` CharSet
set)) [forall a. Bounded a => a
minBound .. forall a. Bounded a => a
maxBound]

instance Show CharSet where
  showsPrec :: Int -> CharSet -> ShowS
showsPrec Int
d CharSet
i
    | CharSet -> Bool
isComplemented CharSet
i = Bool -> ShowS -> ShowS
showParen (Int
d forall a. Ord a => a -> a -> Bool
> Int
10) forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"complement " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (CharSet -> CharSet
complement CharSet
i)
    | Bool
otherwise        = Bool -> ShowS -> ShowS
showParen (Int
d forall a. Ord a => a -> a -> Bool
> Int
10) forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"fromDistinctAscList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (CharSet -> String
toAscList CharSet
i)

instance Read CharSet where
  readPrec :: ReadPrec CharSet
readPrec = forall a. ReadPrec a -> ReadPrec a
parens forall a b. (a -> b) -> a -> b
$ ReadPrec CharSet
complemented forall a. ReadPrec a -> ReadPrec a -> ReadPrec a
+++ ReadPrec CharSet
normal
    where
      complemented :: ReadPrec CharSet
complemented = forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 forall a b. (a -> b) -> a -> b
$ do
        Ident String
"complement" <- ReadPrec Lexeme
lexP
        CharSet -> CharSet
complement forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` forall a. ReadPrec a -> ReadPrec a
step forall a. Read a => ReadPrec a
readPrec
      normal :: ReadPrec CharSet
normal = forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 forall a b. (a -> b) -> a -> b
$ do
        Ident String
"fromDistinctAscList" <- ReadPrec Lexeme
lexP
        String -> CharSet
fromDistinctAscList forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` forall a. ReadPrec a -> ReadPrec a
step forall a. Read a => ReadPrec a
readPrec

instance Semigroup CharSet where
  <> :: CharSet -> CharSet -> CharSet
(<>) = CharSet -> CharSet -> CharSet
union

instance Monoid CharSet where
  mempty :: CharSet
mempty = CharSet
empty
#if !(MIN_VERSION_base(4,11,0))
  mappend = union
#endif