{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE TemplateHaskellQuotes #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE TypeFamilies #-}
module Data.Word8Set (
Word8Set,
Key,
empty,
full,
singleton,
range,
insert,
delete,
alterF,
member,
notMember,
lookupLT,
lookupGT,
lookupLE,
lookupGE,
null,
isFull,
isSingleton,
isRange,
size,
isSubsetOf,
isProperSubsetOf,
disjoint,
union,
unions,
difference,
(\\),
intersection,
complement,
filter,
partition,
map,
foldr,
foldl,
foldr',
foldl',
findMin,
findMax,
deleteMin,
deleteMax,
maxView,
minView,
elems,
toList,
fromList,
fromFoldable,
toWord256,
fromWord256,
toASCII,
fromASCII,
) where
import Prelude
(Bool (..), Eq ((==)), Functor (fmap), Int, Maybe (..), Ord, Show (showsPrec), String, fromIntegral, fst, maybe, negate, not,
otherwise, return, showParen, showString, snd, ($), (&&), (+), (-), (.), (/=), (<=), (>))
import Algebra.Lattice (BoundedJoinSemiLattice (..), BoundedMeetSemiLattice (..), Lattice (..))
import Control.DeepSeq (NFData (..))
import Data.Bits ((.&.), (.|.))
import Data.Char (chr, ord)
import Data.Monoid (Monoid (..))
import Data.Semigroup (Semigroup (..))
import Data.WideWord.Word256 (Word256 (..))
import Data.Word (Word8)
import Test.QuickCheck (Arbitrary (..), CoArbitrary (..), Function (..), functionMap)
import Language.Haskell.TH.Syntax (Lift (..))
import qualified Data.Bits as Bits
import qualified Data.Foldable as F
import qualified GHC.Exts
newtype Word8Set = W8S Word256
deriving (Word8Set -> Word8Set -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Word8Set -> Word8Set -> Bool
$c/= :: Word8Set -> Word8Set -> Bool
== :: Word8Set -> Word8Set -> Bool
$c== :: Word8Set -> Word8Set -> Bool
Eq, Eq Word8Set
Word8Set -> Word8Set -> Bool
Word8Set -> Word8Set -> Ordering
Word8Set -> Word8Set -> Word8Set
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Word8Set -> Word8Set -> Word8Set
$cmin :: Word8Set -> Word8Set -> Word8Set
max :: Word8Set -> Word8Set -> Word8Set
$cmax :: Word8Set -> Word8Set -> Word8Set
>= :: Word8Set -> Word8Set -> Bool
$c>= :: Word8Set -> Word8Set -> Bool
> :: Word8Set -> Word8Set -> Bool
$c> :: Word8Set -> Word8Set -> Bool
<= :: Word8Set -> Word8Set -> Bool
$c<= :: Word8Set -> Word8Set -> Bool
< :: Word8Set -> Word8Set -> Bool
$c< :: Word8Set -> Word8Set -> Bool
compare :: Word8Set -> Word8Set -> Ordering
$ccompare :: Word8Set -> Word8Set -> Ordering
Ord)
type Key = Word8
instance Show Word8Set where
showsPrec :: Int -> Word8Set -> ShowS
showsPrec Int
d Word8Set
xs = 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
"fromList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (Word8Set -> [Word8]
toList Word8Set
xs)
instance NFData Word8Set where
rnf :: Word8Set -> ()
rnf (W8S Word256
xs) = forall a. NFData a => a -> ()
rnf Word256
xs
instance Lift Word8Set where
lift :: forall (m :: * -> *). Quote m => Word8Set -> m Exp
lift (W8S (Word256 Word64
a Word64
b Word64
c Word64
d)) =
[| W8S (Word256 a b c d) |]
#if MIN_VERSION_template_haskell(2,16,0)
liftTyped :: forall (m :: * -> *). Quote m => Word8Set -> Code m Word8Set
liftTyped (W8S (Word256 Word64
a Word64
b Word64
c Word64
d)) =
[|| W8S (Word256 a b c d) ||]
#endif
instance Semigroup Word8Set where
<> :: Word8Set -> Word8Set -> Word8Set
(<>) = Word8Set -> Word8Set -> Word8Set
union
instance Monoid Word8Set where
mempty :: Word8Set
mempty = Word8Set
empty
mappend :: Word8Set -> Word8Set -> Word8Set
mappend = forall a. Semigroup a => a -> a -> a
(<>)
instance Arbitrary Word8Set where
arbitrary :: Gen Word8Set
arbitrary = do
Word64
a <- forall a. Arbitrary a => Gen a
arbitrary
Word64
b <- forall a. Arbitrary a => Gen a
arbitrary
Word64
c <- forall a. Arbitrary a => Gen a
arbitrary
Word64
d <- forall a. Arbitrary a => Gen a
arbitrary
forall (m :: * -> *) a. Monad m => a -> m a
return (Word256 -> Word8Set
W8S (Word64 -> Word64 -> Word64 -> Word64 -> Word256
Word256 Word64
a Word64
b Word64
c Word64
d))
shrink :: Word8Set -> [Word8Set]
shrink Word8Set
xs = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [Word8] -> Word8Set
fromList (forall a. Arbitrary a => a -> [a]
shrink (Word8Set -> [Word8]
toList Word8Set
xs)) where
instance CoArbitrary Word8Set where
coarbitrary :: forall b. Word8Set -> Gen b -> Gen b
coarbitrary (W8S (Word256 Word64
a Word64
b Word64
c Word64
d)) = forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary (Word64
a,Word64
b,Word64
c,Word64
d)
instance Function Word8Set where
function :: forall b. (Word8Set -> b) -> Word8Set :-> b
function = forall b a c.
Function b =>
(a -> b) -> (b -> a) -> (a -> c) -> a :-> c
functionMap Word8Set -> (Word64, Word64, Word64, Word64)
from (Word64, Word64, Word64, Word64) -> Word8Set
to where
from :: Word8Set -> (Word64, Word64, Word64, Word64)
from (W8S (Word256 Word64
a Word64
b Word64
c Word64
d)) = (Word64
a, Word64
b, Word64
c, Word64
d)
to :: (Word64, Word64, Word64, Word64) -> Word8Set
to (Word64
a,Word64
b,Word64
c,Word64
d) = Word256 -> Word8Set
W8S (Word64 -> Word64 -> Word64 -> Word64 -> Word256
Word256 Word64
a Word64
b Word64
c Word64
d)
instance Lattice Word8Set where
\/ :: Word8Set -> Word8Set -> Word8Set
(\/) = Word8Set -> Word8Set -> Word8Set
union
/\ :: Word8Set -> Word8Set -> Word8Set
(/\) = Word8Set -> Word8Set -> Word8Set
intersection
instance BoundedJoinSemiLattice Word8Set where
bottom :: Word8Set
bottom = Word8Set
empty
instance BoundedMeetSemiLattice Word8Set where
top :: Word8Set
top = Word8Set
full
instance GHC.Exts.IsList Word8Set where
type Item Word8Set = Key
fromList :: [Item Word8Set] -> Word8Set
fromList = [Word8] -> Word8Set
fromList
toList :: Word8Set -> [Item Word8Set]
toList = Word8Set -> [Word8]
toList
empty :: Word8Set
empty :: Word8Set
empty = Word256 -> Word8Set
W8S forall a. Bits a => a
Bits.zeroBits
full :: Word8Set
full :: Word8Set
full = Word256 -> Word8Set
W8S Word256
ones
ones :: Word256
ones :: Word256
ones = forall a. Bits a => a -> a
Bits.complement forall a. Bits a => a
Bits.zeroBits
singleton :: Key -> Word8Set
singleton :: Word8 -> Word8Set
singleton Word8
x = Word256 -> Word8Set
W8S (forall a. Bits a => Int -> a
Bits.bit (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
x))
range :: Key -> Key -> Word8Set
range :: Word8 -> Word8 -> Word8Set
range Word8
mi Word8
ma
| Word8
mi forall a. Ord a => a -> a -> Bool
<= Word8
ma = Word256 -> Word8Set
W8S forall a b. (a -> b) -> a -> b
$ forall a. Bits a => a -> Int -> a
Bits.shiftL (forall a. Bits a => a -> Int -> a
Bits.shiftR Word256
ones (forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. Num a => a -> a
negate (Word8
1 forall a. Num a => a -> a -> a
+ Word8
ma forall a. Num a => a -> a -> a
- Word8
mi)))) (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
mi)
| Bool
otherwise = Word8Set
empty
insert :: Key -> Word8Set -> Word8Set
insert :: Word8 -> Word8Set -> Word8Set
insert Word8
x (W8S Word256
xs) = Word256 -> Word8Set
W8S (forall a. Bits a => a -> Int -> a
Bits.setBit Word256
xs (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
x))
delete :: Key -> Word8Set -> Word8Set
delete :: Word8 -> Word8Set -> Word8Set
delete Word8
x (W8S Word256
xs) = Word256 -> Word8Set
W8S (forall a. Bits a => a -> Int -> a
Bits.clearBit Word256
xs (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
x))
alterF :: Functor f => (Bool -> f Bool) -> Key -> Word8Set -> f Word8Set
alterF :: forall (f :: * -> *).
Functor f =>
(Bool -> f Bool) -> Word8 -> Word8Set -> f Word8Set
alterF Bool -> f Bool
f Word8
x Word8Set
xs
| Word8 -> Word8Set -> Bool
member Word8
x Word8Set
xs = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Bool
b -> if Bool
b then Word8Set
xs else Word8 -> Word8Set -> Word8Set
delete Word8
x Word8Set
xs) (Bool -> f Bool
f Bool
True)
| Bool
otherwise = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Bool
b -> if Bool
b then Word8 -> Word8Set -> Word8Set
insert Word8
x Word8Set
xs else Word8Set
xs) (Bool -> f Bool
f Bool
False)
null :: Word8Set -> Bool
null :: Word8Set -> Bool
null (W8S Word256
xs) = Word256
xs forall a. Eq a => a -> a -> Bool
== forall a. Bits a => a
Bits.zeroBits
isFull :: Word8Set -> Bool
isFull :: Word8Set -> Bool
isFull (W8S Word256
xs) = Word256
xs forall a. Eq a => a -> a -> Bool
== Word256
ones
size :: Word8Set -> Int
size :: Word8Set -> Int
size (W8S Word256
xs) = forall a. Bits a => a -> Int
Bits.popCount Word256
xs
member :: Key -> Word8Set -> Bool
member :: Word8 -> Word8Set -> Bool
member Word8
x (W8S Word256
xs) = forall a. Bits a => a -> Int -> Bool
Bits.testBit Word256
xs (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
x)
notMember :: Key -> Word8Set -> Bool
notMember :: Word8 -> Word8Set -> Bool
notMember Word8
x Word8Set
xs = Bool -> Bool
not (Word8 -> Word8Set -> Bool
member Word8
x Word8Set
xs)
isSubsetOf :: Word8Set -> Word8Set -> Bool
isSubsetOf :: Word8Set -> Word8Set -> Bool
isSubsetOf Word8Set
a Word8Set
b = Word8Set
b forall a. Eq a => a -> a -> Bool
== Word8Set -> Word8Set -> Word8Set
union Word8Set
a Word8Set
b
isProperSubsetOf :: Word8Set -> Word8Set -> Bool
isProperSubsetOf :: Word8Set -> Word8Set -> Bool
isProperSubsetOf Word8Set
a Word8Set
b = Word8Set
b forall a. Eq a => a -> a -> Bool
== Word8Set -> Word8Set -> Word8Set
union Word8Set
a Word8Set
b Bool -> Bool -> Bool
&& Word8Set
a forall a. Eq a => a -> a -> Bool
/= Word8Set
b
isSingleton :: Word8Set -> Maybe Key
isSingleton :: Word8Set -> Maybe Word8
isSingleton (W8S Word256
ws)
| forall a. Bits a => a -> Int
Bits.popCount Word256
ws forall a. Eq a => a -> a -> Bool
/= Int
1 = forall a. Maybe a
Nothing
| Bool
otherwise = forall a. a -> Maybe a
Just (forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. FiniteBits a => a -> Int
ctz Word256
ws))
isRange :: Word8Set -> Maybe (Key, Key)
isRange :: Word8Set -> Maybe (Word8, Word8)
isRange (W8S Word256
0) = forall a. Maybe a
Nothing
isRange (W8S Word256
ws) = if forall a. Bits a => a -> Int
Bits.popCount Word256
ws forall a. Num a => a -> a -> a
+ Int
l forall a. Num a => a -> a -> a
+ Int
r forall a. Eq a => a -> a -> Bool
== Int
256 then forall a. a -> Maybe a
Just (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
l, forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
255 forall a. Num a => a -> a -> a
- Int
r)) else forall a. Maybe a
Nothing
where
r :: Int
r = forall a. FiniteBits a => a -> Int
clz Word256
ws
l :: Int
l = forall a. FiniteBits a => a -> Int
ctz Word256
ws
disjoint :: Word8Set -> Word8Set -> Bool
disjoint :: Word8Set -> Word8Set -> Bool
disjoint Word8Set
xs Word8Set
ys = Word8Set -> Word8Set -> Word8Set
intersection Word8Set
xs Word8Set
ys forall a. Eq a => a -> a -> Bool
== Word8Set
empty
lookupLT :: Key -> Word8Set -> Maybe Key
lookupLT :: Word8 -> Word8Set -> Maybe Word8
lookupLT Word8
0 Word8Set
_ = forall a. Maybe a
Nothing
lookupLT Word8
x Word8Set
xs = Word8 -> Word8Set -> Maybe Word8
lookupLE (Word8
x forall a. Num a => a -> a -> a
- Word8
1) Word8Set
xs
lookupGT :: Key -> Word8Set -> Maybe Key
lookupGT :: Word8 -> Word8Set -> Maybe Word8
lookupGT Word8
255 Word8Set
_ = forall a. Maybe a
Nothing
lookupGT Word8
x Word8Set
xs = Word8 -> Word8Set -> Maybe Word8
lookupGE (Word8
x forall a. Num a => a -> a -> a
+ Word8
1) Word8Set
xs
lookupLE :: Key -> Word8Set -> Maybe Key
lookupLE :: Word8 -> Word8Set -> Maybe Word8
lookupLE Word8
x Word8Set
xs = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> a
fst (Word8Set -> Maybe (Word8, Word8Set)
maxView (Word8Set -> Word8Set -> Word8Set
intersection Word8Set
xs (Word8 -> Word8 -> Word8Set
range Word8
0 Word8
x)))
lookupGE :: Key -> Word8Set -> Maybe Key
lookupGE :: Word8 -> Word8Set -> Maybe Word8
lookupGE Word8
x Word8Set
xs = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> a
fst (Word8Set -> Maybe (Word8, Word8Set)
minView (Word8Set -> Word8Set -> Word8Set
intersection Word8Set
xs (Word8 -> Word8 -> Word8Set
range Word8
x Word8
255)))
complement :: Word8Set -> Word8Set
complement :: Word8Set -> Word8Set
complement (W8S Word256
xs) = Word256 -> Word8Set
W8S (forall a. Bits a => a -> a
Bits.complement Word256
xs)
union :: Word8Set -> Word8Set -> Word8Set
union :: Word8Set -> Word8Set -> Word8Set
union (W8S Word256
xs) (W8S Word256
ys) = Word256 -> Word8Set
W8S (Word256
xs forall a. Bits a => a -> a -> a
.|. Word256
ys)
unions :: F.Foldable f => f Word8Set -> Word8Set
unions :: forall (f :: * -> *). Foldable f => f Word8Set -> Word8Set
unions f Word8Set
xs = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' Word8Set -> Word8Set -> Word8Set
union Word8Set
empty f Word8Set
xs
intersection :: Word8Set -> Word8Set -> Word8Set
intersection :: Word8Set -> Word8Set -> Word8Set
intersection (W8S Word256
xs) (W8S Word256
ys) = Word256 -> Word8Set
W8S (Word256
xs forall a. Bits a => a -> a -> a
.&. Word256
ys)
difference :: Word8Set -> Word8Set -> Word8Set
difference :: Word8Set -> Word8Set -> Word8Set
difference Word8Set
xs Word8Set
ys = Word8Set -> Word8Set -> Word8Set
intersection Word8Set
xs (Word8Set -> Word8Set
complement Word8Set
ys)
(\\) :: Word8Set -> Word8Set -> Word8Set
Word8Set
m1 \\ :: Word8Set -> Word8Set -> Word8Set
\\ Word8Set
m2 = Word8Set -> Word8Set -> Word8Set
difference Word8Set
m1 Word8Set
m2
filter :: (Key -> Bool) -> Word8Set -> Word8Set
filter :: (Word8 -> Bool) -> Word8Set -> Word8Set
filter Word8 -> Bool
p = forall a. (a -> Word8 -> a) -> a -> Word8Set -> a
foldl' (\Word8Set
acc Word8
x -> if Word8 -> Bool
p Word8
x then Word8 -> Word8Set -> Word8Set
insert Word8
x Word8Set
acc else Word8Set
acc) Word8Set
empty
partition :: (Key -> Bool) -> Word8Set -> (Word8Set,Word8Set)
partition :: (Word8 -> Bool) -> Word8Set -> (Word8Set, Word8Set)
partition Word8 -> Bool
p = forall a. (a -> Word8 -> a) -> a -> Word8Set -> a
foldl' (\(Word8Set
l, Word8Set
r) Word8
x -> if Word8 -> Bool
p Word8
x then (Word8 -> Word8Set -> Word8Set
insert Word8
x Word8Set
l, Word8Set
r) else (Word8Set
l, Word8 -> Word8Set -> Word8Set
insert Word8
x Word8Set
r)) (Word8Set
empty, Word8Set
empty)
map :: (Key -> Key) -> Word8Set -> Word8Set
map :: (Word8 -> Word8) -> Word8Set -> Word8Set
map Word8 -> Word8
f = forall a. (a -> Word8 -> a) -> a -> Word8Set -> a
foldl' (\Word8Set
acc Word8
k -> Word8 -> Word8Set -> Word8Set
insert (Word8 -> Word8
f Word8
k) Word8Set
acc) Word8Set
empty
foldr :: (Key -> b -> b) -> b -> Word8Set -> b
foldr :: forall b. (Word8 -> b -> b) -> b -> Word8Set -> b
foldr Word8 -> b -> b
f b
z0 (W8S (Word256 Word64
a0 Word64
b0 Word64
c0 Word64
d0)) = Word64 -> Word64 -> Word64 -> Word64 -> b -> b
go0 Word64
a0 Word64
b0 Word64
c0 Word64
d0 b
z0 where
go0 :: Word64 -> Word64 -> Word64 -> Word64 -> b -> b
go0 Word64
0 !Word64
b !Word64
c !Word64
d b
acc = Word64 -> Word64 -> Word64 -> b -> b
go1 Word64
b Word64
c Word64
d b
acc
go0 Word64
a Word64
b Word64
c Word64
d b
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
clz Word64
a in Word64 -> Word64 -> Word64 -> Word64 -> b -> b
go0 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a (Int
63 forall a. Num a => a -> a -> a
- Int
x)) Word64
b Word64
c Word64
d (Word8 -> b -> b
f (Word8
255 forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)
go1 :: Word64 -> Word64 -> Word64 -> b -> b
go1 Word64
0 !Word64
c Word64
d b
acc = Word64 -> Word64 -> b -> b
go2 Word64
c Word64
d b
acc
go1 Word64
b Word64
c Word64
d b
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
clz Word64
b in Word64 -> Word64 -> Word64 -> b -> b
go1 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
b (Int
63 forall a. Num a => a -> a -> a
- Int
x)) Word64
c Word64
d (Word8 -> b -> b
f (Word8
191 forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)
go2 :: Word64 -> Word64 -> b -> b
go2 Word64
0 !Word64
d b
acc = Word64 -> b -> b
go3 Word64
d b
acc
go2 Word64
c Word64
d b
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
clz Word64
c in Word64 -> Word64 -> b -> b
go2 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
c (Int
63 forall a. Num a => a -> a -> a
- Int
x)) Word64
d (Word8 -> b -> b
f (Word8
127 forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)
go3 :: Word64 -> b -> b
go3 Word64
0 b
acc = b
acc
go3 Word64
a b
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
clz Word64
a in Word64 -> b -> b
go3 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a (Int
63 forall a. Num a => a -> a -> a
- Int
x)) (Word8 -> b -> b
f (Word8
63 forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)
foldr' :: (Key -> b -> b) -> b -> Word8Set -> b
foldr' :: forall b. (Word8 -> b -> b) -> b -> Word8Set -> b
foldr' Word8 -> b -> b
f b
z0 (W8S (Word256 Word64
a0 Word64
b0 Word64
c0 Word64
d0)) = Word64 -> Word64 -> Word64 -> Word64 -> b -> b
go0 Word64
a0 Word64
b0 Word64
c0 Word64
d0 b
z0 where
go0 :: Word64 -> Word64 -> Word64 -> Word64 -> b -> b
go0 Word64
0 !Word64
b !Word64
c !Word64
d !b
acc = Word64 -> Word64 -> Word64 -> b -> b
go1 Word64
b Word64
c Word64
d b
acc
go0 Word64
a Word64
b Word64
c Word64
d b
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
clz Word64
a in Word64 -> Word64 -> Word64 -> Word64 -> b -> b
go0 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a (Int
63 forall a. Num a => a -> a -> a
- Int
x)) Word64
b Word64
c Word64
d (Word8 -> b -> b
f (Word8
255 forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)
go1 :: Word64 -> Word64 -> Word64 -> b -> b
go1 Word64
0 !Word64
c Word64
d !b
acc = Word64 -> Word64 -> b -> b
go2 Word64
c Word64
d b
acc
go1 Word64
b Word64
c Word64
d b
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
clz Word64
b in Word64 -> Word64 -> Word64 -> b -> b
go1 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
b (Int
63 forall a. Num a => a -> a -> a
- Int
x)) Word64
c Word64
d (Word8 -> b -> b
f (Word8
191 forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)
go2 :: Word64 -> Word64 -> b -> b
go2 Word64
0 !Word64
d !b
acc = Word64 -> b -> b
go3 Word64
d b
acc
go2 Word64
c Word64
d b
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
clz Word64
c in Word64 -> Word64 -> b -> b
go2 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
c (Int
63 forall a. Num a => a -> a -> a
- Int
x)) Word64
d (Word8 -> b -> b
f (Word8
127 forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)
go3 :: Word64 -> b -> b
go3 Word64
0 !b
acc = b
acc
go3 Word64
a b
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
clz Word64
a in Word64 -> b -> b
go3 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a (Int
63 forall a. Num a => a -> a -> a
- Int
x)) (Word8 -> b -> b
f (Word8
63 forall a. Num a => a -> a -> a
- forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)
foldl :: (a -> Key -> a) -> a -> Word8Set -> a
foldl :: forall a. (a -> Word8 -> a) -> a -> Word8Set -> a
foldl a -> Word8 -> a
f a
z0 (W8S (Word256 Word64
a0 Word64
b0 Word64
c0 Word64
d0)) = Word64 -> Word64 -> Word64 -> Word64 -> a -> a
go0 Word64
a0 Word64
b0 Word64
c0 Word64
d0 a
z0 where
go0 :: Word64 -> Word64 -> Word64 -> Word64 -> a -> a
go0 !Word64
a !Word64
b !Word64
c Word64
0 a
acc = Word64 -> Word64 -> Word64 -> a -> a
go1 Word64
a Word64
b Word64
c a
acc
go0 Word64
a Word64
b Word64
c Word64
d a
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
ctz Word64
d in Word64 -> Word64 -> Word64 -> Word64 -> a -> a
go0 Word64
a Word64
b Word64
c (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
d Int
x) (a -> Word8 -> a
f a
acc (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x))
go1 :: Word64 -> Word64 -> Word64 -> a -> a
go1 !Word64
a !Word64
b Word64
0 a
acc = Word64 -> Word64 -> a -> a
go2 Word64
a Word64
b a
acc
go1 Word64
a Word64
b Word64
c a
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
ctz Word64
c in Word64 -> Word64 -> Word64 -> a -> a
go1 Word64
a Word64
b (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
c Int
x) (a -> Word8 -> a
f a
acc (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x forall a. Num a => a -> a -> a
+ Word8
64))
go2 :: Word64 -> Word64 -> a -> a
go2 !Word64
a Word64
0 a
acc = Word64 -> a -> a
go3 Word64
a a
acc
go2 Word64
a Word64
b a
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
ctz Word64
b in Word64 -> Word64 -> a -> a
go2 Word64
a (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
b Int
x) (a -> Word8 -> a
f a
acc (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x forall a. Num a => a -> a -> a
+ Word8
128))
go3 :: Word64 -> a -> a
go3 Word64
0 a
acc = a
acc
go3 Word64
a a
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
ctz Word64
a in Word64 -> a -> a
go3 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a Int
x) (a -> Word8 -> a
f a
acc (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x forall a. Num a => a -> a -> a
+ Word8
192))
foldl' :: (a -> Key -> a) -> a -> Word8Set -> a
foldl' :: forall a. (a -> Word8 -> a) -> a -> Word8Set -> a
foldl' a -> Word8 -> a
f a
z0 (W8S (Word256 Word64
a0 Word64
b0 Word64
c0 Word64
d0)) = Word64 -> Word64 -> Word64 -> Word64 -> a -> a
go0 Word64
a0 Word64
b0 Word64
c0 Word64
d0 a
z0 where
go0 :: Word64 -> Word64 -> Word64 -> Word64 -> a -> a
go0 !Word64
a !Word64
b !Word64
c Word64
0 !a
acc = Word64 -> Word64 -> Word64 -> a -> a
go1 Word64
a Word64
b Word64
c a
acc
go0 Word64
a Word64
b Word64
c Word64
d a
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
ctz Word64
d in Word64 -> Word64 -> Word64 -> Word64 -> a -> a
go0 Word64
a Word64
b Word64
c (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
d Int
x) (a -> Word8 -> a
f a
acc (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x))
go1 :: Word64 -> Word64 -> Word64 -> a -> a
go1 !Word64
a !Word64
b Word64
0 !a
acc = Word64 -> Word64 -> a -> a
go2 Word64
a Word64
b a
acc
go1 Word64
a Word64
b Word64
c a
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
ctz Word64
c in Word64 -> Word64 -> Word64 -> a -> a
go1 Word64
a Word64
b (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
c Int
x) (a -> Word8 -> a
f a
acc (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x forall a. Num a => a -> a -> a
+ Word8
64))
go2 :: Word64 -> Word64 -> a -> a
go2 !Word64
a Word64
0 !a
acc = Word64 -> a -> a
go3 Word64
a a
acc
go2 Word64
a Word64
b a
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
ctz Word64
b in Word64 -> Word64 -> a -> a
go2 Word64
a (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
b Int
x) (a -> Word8 -> a
f a
acc (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x forall a. Num a => a -> a -> a
+ Word8
128))
go3 :: Word64 -> a -> a
go3 Word64
0 !a
acc = a
acc
go3 Word64
a a
acc = let !x :: Int
x = forall a. FiniteBits a => a -> Int
ctz Word64
a in Word64 -> a -> a
go3 (forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a Int
x) (a -> Word8 -> a
f a
acc (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x forall a. Num a => a -> a -> a
+ Word8
192))
findMin :: Word8Set -> Word8
findMin :: Word8Set -> Word8
findMin (W8S Word256
xs) = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. FiniteBits a => a -> Int
ctz Word256
xs)
findMax :: Word8Set -> Word8
findMax :: Word8Set -> Word8
findMax (W8S Word256
xs) = forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
255 forall a. Num a => a -> a -> a
- forall a. FiniteBits a => a -> Int
clz Word256
xs)
deleteMin :: Word8Set -> Word8Set
deleteMin :: Word8Set -> Word8Set
deleteMin = forall b a. b -> (a -> b) -> Maybe a -> b
maybe Word8Set
empty forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8Set -> Maybe (Word8, Word8Set)
minView
deleteMax :: Word8Set -> Word8Set
deleteMax :: Word8Set -> Word8Set
deleteMax = forall b a. b -> (a -> b) -> Maybe a -> b
maybe Word8Set
empty forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8Set -> Maybe (Word8, Word8Set)
minView
maxView :: Word8Set -> Maybe (Key, Word8Set)
maxView :: Word8Set -> Maybe (Word8, Word8Set)
maxView Word8Set
xs
| Word8Set -> Bool
null Word8Set
xs = forall a. Maybe a
Nothing
| Bool
otherwise = let !x :: Word8
x = Word8Set -> Word8
findMax Word8Set
xs in forall a. a -> Maybe a
Just (Word8
x, Word8 -> Word8Set -> Word8Set
delete Word8
x Word8Set
xs)
minView :: Word8Set -> Maybe (Key, Word8Set)
minView :: Word8Set -> Maybe (Word8, Word8Set)
minView Word8Set
xs
| Word8Set -> Bool
null Word8Set
xs = forall a. Maybe a
Nothing
| Bool
otherwise = let !x :: Word8
x = Word8Set -> Word8
findMin Word8Set
xs in forall a. a -> Maybe a
Just (Word8
x, Word8 -> Word8Set -> Word8Set
delete Word8
x Word8Set
xs)
elems :: Word8Set -> [Key]
elems :: Word8Set -> [Word8]
elems = Word8Set -> [Word8]
toList
toList :: Word8Set -> [Key]
toList :: Word8Set -> [Word8]
toList Word8Set
xs = forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
GHC.Exts.build (\Word8 -> b -> b
c b
n -> forall b. (Word8 -> b -> b) -> b -> Word8Set -> b
foldr Word8 -> b -> b
c b
n Word8Set
xs)
fromList :: [Key] -> Word8Set
fromList :: [Word8] -> Word8Set
fromList [Word8]
w8s = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' (\Word8Set
acc Word8
x -> Word8 -> Word8Set -> Word8Set
insert Word8
x Word8Set
acc) Word8Set
empty [Word8]
w8s
fromFoldable :: F.Foldable f => f Key -> Word8Set
#if MIN_VERSION_base(4,13,0)
fromFoldable :: forall (f :: * -> *). Foldable f => f Word8 -> Word8Set
fromFoldable = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
F.foldMap' Word8 -> Word8Set
singleton
#else
fromFoldable = F.foldl' (\acc x -> insert x acc) empty
#endif
toWord256 :: Word8Set -> Word256
toWord256 :: Word8Set -> Word256
toWord256 (W8S Word256
xs) = Word256
xs
fromWord256 :: Word256 -> Word8Set
fromWord256 :: Word256 -> Word8Set
fromWord256 = Word256 -> Word8Set
W8S
toASCII :: Word8Set -> String
toASCII :: Word8Set -> String
toASCII = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int -> Char
chr forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8Set -> [Word8]
toList
fromASCII :: String -> Word8Set
fromASCII :: String -> Word8Set
fromASCII = [Word8] -> Word8Set
fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a b. (Integral a, Num b) => a -> b
fromIntegral forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Int
ord)
clz :: Bits.FiniteBits a => a -> Int
clz :: forall a. FiniteBits a => a -> Int
clz = forall a. FiniteBits a => a -> Int
Bits.countLeadingZeros
{-# INLINE clz #-}
ctz :: Bits.FiniteBits a => a -> Int
ctz :: forall a. FiniteBits a => a -> Int
ctz = forall a. FiniteBits a => a -> Int
Bits.countTrailingZeros
{-# INLINE ctz #-}