{-# LANGUAGE BangPatterns          #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE TemplateHaskellQuotes #-}
{-# LANGUAGE Trustworthy           #-}
{-# LANGUAGE TypeFamilies          #-}
-- | The 'Word8Set' type represents a set of elements of type 'Word8'.
--
-- The interface of this module mimics the "Data.Set" and/or "Data.IntSet"
-- module interfaces from @containers package.
--
-- These module is intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.
--
-- @
-- import Data.Word8Set (Word8Set)
-- import qualified Data.Word8Set as W8S
-- @
--
-- == Implementation
-- The implementation is based on 'Word256' type. 'Word8Set' is 256 bits.
--
module Data.Word8Set (
    -- * Set type
    Word8Set,
    Key,

    -- * Construction
    empty,
    full,
    singleton,
    range,

    -- * Insertion
    insert,

    -- * Deletion
    delete,

    -- * Generalized insertion/deletion
    alterF,

    -- * Query
    member,
    notMember,
    lookupLT,
    lookupGT,
    lookupLE,
    lookupGE,
    null,
    isFull,
    isSingleton,
    isRange,
    size,
    isSubsetOf,
    isProperSubsetOf,
    disjoint,

    -- * Combine
    union,
    unions,
    difference,
    symmetricDifference,
    (\\),
    intersection,
    complement,

    -- * Filter
    filter,
    partition,

    -- * Map
    map,

    -- * Folds
    foldr,
    foldl,

    -- ** Strict folds
    foldr',
    foldl',

    -- * Min\/Max
    findMin,
    findMax,
    deleteMin,
    deleteMax,
    maxView,
    minView,

    -- * Conversion
    -- ** to/fromList
    elems,
    toList,
    fromList,
    fromFoldable,

    -- ** to/from Word256
    toWord256,
    fromWord256,

    -- ** to/from ASCII Strings
    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 Algebra.Heyting (Heyting (..))
import Algebra.PartialOrd (PartialOrd (..))
import Control.DeepSeq       (NFData (..))
import Data.Bits             ((.&.), (.|.))
import Data.Char             (chr, ord)
import Data.Monoid           (Monoid (..))
import Data.Semigroup        (Semigroup (..))
import Data.String           (IsString (..))
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

-- $setup
-- >>> import Prelude (even, (+), flip)

-------------------------------------------------------------------------------
-- Types
-------------------------------------------------------------------------------

-- | A set of 'Word8' numbers.
--
-- Implemented using 'Word256'.
newtype Word8Set = W8S Word256
  deriving (Word8Set -> Word8Set -> Bool
(Word8Set -> Word8Set -> Bool)
-> (Word8Set -> Word8Set -> Bool) -> Eq Word8Set
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Word8Set -> Word8Set -> Bool
== :: Word8Set -> Word8Set -> Bool
$c/= :: Word8Set -> Word8Set -> Bool
/= :: Word8Set -> Word8Set -> Bool
Eq, Eq Word8Set
Eq Word8Set =>
(Word8Set -> Word8Set -> Ordering)
-> (Word8Set -> Word8Set -> Bool)
-> (Word8Set -> Word8Set -> Bool)
-> (Word8Set -> Word8Set -> Bool)
-> (Word8Set -> Word8Set -> Bool)
-> (Word8Set -> Word8Set -> Word8Set)
-> (Word8Set -> Word8Set -> Word8Set)
-> Ord 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
$ccompare :: Word8Set -> Word8Set -> Ordering
compare :: Word8Set -> Word8Set -> Ordering
$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
>= :: Word8Set -> Word8Set -> Bool
$cmax :: Word8Set -> Word8Set -> Word8Set
max :: Word8Set -> Word8Set -> Word8Set
$cmin :: Word8Set -> Word8Set -> Word8Set
min :: Word8Set -> Word8Set -> Word8Set
Ord)

-- | Key of 'Word8Set' is 'Word8'.
type Key = Word8

-------------------------------------------------------------------------------
-- Instances
-------------------------------------------------------------------------------

instance Show Word8Set where
    showsPrec :: Int -> Word8Set -> ShowS
showsPrec Int
d Word8Set
xs = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [Word8] -> ShowS
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) = Word256 -> ()
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)) =
        [|| Word256 -> Word8Set
W8S (Word64 -> Word64 -> Word64 -> Word64 -> Word256
Word256 Word64
a Word64
b Word64
c Word64
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 = Word8Set -> Word8Set -> Word8Set
forall a. Semigroup a => a -> a -> a
(<>)

instance Arbitrary Word8Set where
    arbitrary :: Gen Word8Set
arbitrary = do
        Word64
a <- Gen Word64
forall a. Arbitrary a => Gen a
arbitrary
        Word64
b <- Gen Word64
forall a. Arbitrary a => Gen a
arbitrary
        Word64
c <- Gen Word64
forall a. Arbitrary a => Gen a
arbitrary
        Word64
d <- Gen Word64
forall a. Arbitrary a => Gen a
arbitrary
        Word8Set -> Gen Word8Set
forall a. a -> Gen a
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 = ([Word8] -> Word8Set) -> [[Word8]] -> [Word8Set]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [Word8] -> Word8Set
fromList ([Word8] -> [[Word8]]
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)) = (Word64, Word64, Word64, Word64) -> Gen b -> Gen b
forall b. (Word64, Word64, Word64, Word64) -> Gen b -> Gen b
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 = (Word8Set -> (Word64, Word64, Word64, Word64))
-> ((Word64, Word64, Word64, Word64) -> Word8Set)
-> (Word8Set -> b)
-> Word8Set :-> b
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

-- |
--
-- @since 0.1.1
instance Heyting Word8Set where
    Word8Set
a ==> :: Word8Set -> Word8Set -> Word8Set
==> Word8Set
b = Word8Set -> Word8Set
forall a. Heyting a => a -> a
neg Word8Set
a Word8Set -> Word8Set -> Word8Set
forall a. Lattice a => a -> a -> a
\/ Word8Set
b 
    neg :: Word8Set -> Word8Set
neg     = Word8Set -> Word8Set
complement
    Word8Set
a <=> :: Word8Set -> Word8Set -> Word8Set
<=> Word8Set
b = Word8Set -> Word8Set
complement (Word8Set -> Word8Set -> Word8Set
symmetricDifference Word8Set
a Word8Set
b)

-- | @'leq' = 'isSubsetOf'@
--
-- @since 0.1.1
instance PartialOrd Word8Set where
    leq :: Word8Set -> Word8Set -> Bool
leq = Word8Set -> Word8Set -> Bool
isSubsetOf

instance GHC.Exts.IsList Word8Set where
  type Item Word8Set = Key
  fromList :: [Item Word8Set] -> Word8Set
fromList = [Word8] -> Word8Set
[Item Word8Set] -> Word8Set
fromList
  toList :: Word8Set -> [Item Word8Set]
toList   = Word8Set -> [Word8]
Word8Set -> [Item Word8Set]
toList

-- | @'fromString' = 'fromASCII'@
--
-- @since 0.1.1
instance IsString Word8Set where
    fromString :: String -> Word8Set
fromString = String -> Word8Set
fromASCII

-------------------------------------------------------------------------------
-- Construction
-------------------------------------------------------------------------------

-- | The empty set.
--
-- >>> empty
-- fromList []
--
empty :: Word8Set
empty :: Word8Set
empty = Word256 -> Word8Set
W8S Word256
forall a. Bits a => a
Bits.zeroBits

-- | The full set.
--
-- >>> full
-- fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,...,255]
--
full :: Word8Set
full :: Word8Set
full = Word256 -> Word8Set
W8S Word256
ones

ones :: Word256
ones :: Word256
ones = Word256 -> Word256
forall a. Bits a => a -> a
Bits.complement Word256
forall a. Bits a => a
Bits.zeroBits

-- | A set of one element.
--
-- >>> singleton 127
-- fromList [127]
--
singleton :: Key -> Word8Set
singleton :: Word8 -> Word8Set
singleton Word8
x = Word256 -> Word8Set
W8S (Int -> Word256
forall a. Bits a => Int -> a
Bits.bit (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
x))

-- | A set of inclusive range.
--
-- >>> range 10 20
-- fromList [10,11,12,13,14,15,16,17,18,19,20]
--
range :: Key -> Key -> Word8Set
range :: Word8 -> Word8 -> Word8Set
range Word8
mi Word8
ma
    | Word8
mi Word8 -> Word8 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word8
ma  = Word256 -> Word8Set
W8S (Word256 -> Word8Set) -> Word256 -> Word8Set
forall a b. (a -> b) -> a -> b
$ Word256 -> Int -> Word256
forall a. Bits a => a -> Int -> a
Bits.shiftL (Word256 -> Int -> Word256
forall a. Bits a => a -> Int -> a
Bits.shiftR Word256
ones (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word8 -> Word8
forall a. Num a => a -> a
negate (Word8
1 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
+ Word8
ma Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
mi)))) (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
mi)
    | Bool
otherwise = Word8Set
empty

-------------------------------------------------------------------------------
-- Insertion
-------------------------------------------------------------------------------

-- | Add a value to the set.
--
-- >>> insert 10 (range 15 20)
-- fromList [10,15,16,17,18,19,20]
--
-- >>> insert 10 (range 10 15)
-- fromList [10,11,12,13,14,15]
--
insert :: Key -> Word8Set -> Word8Set
insert :: Word8 -> Word8Set -> Word8Set
insert Word8
x (W8S Word256
xs) = Word256 -> Word8Set
W8S (Word256 -> Int -> Word256
forall a. Bits a => a -> Int -> a
Bits.setBit Word256
xs (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
x))

-------------------------------------------------------------------------------
-- Deletion
-------------------------------------------------------------------------------

-- | Delete a value in the set. Returns the original set when the value was not present.
--
-- >>> delete 10 (range 5 15)
-- fromList [5,6,7,8,9,11,12,13,14,15]
--
-- >>> delete 10 (range 1 10)
-- fromList [1,2,3,4,5,6,7,8,9]
--
delete :: Key -> Word8Set -> Word8Set
delete :: Word8 -> Word8Set -> Word8Set
delete Word8
x (W8S Word256
xs) = Word256 -> Word8Set
W8S (Word256 -> Int -> Word256
forall a. Bits a => a -> Int -> a
Bits.clearBit Word256
xs (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
x))

-------------------------------------------------------------------------------
-- Generalized insertion/deletion
-------------------------------------------------------------------------------

-- | Generalized insetion deletion.
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 = (Bool -> Word8Set) -> f Bool -> f Word8Set
forall a b. (a -> b) -> f a -> f b
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   = (Bool -> Word8Set) -> f Bool -> f Word8Set
forall a b. (a -> b) -> f a -> f b
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)

-------------------------------------------------------------------------------
-- Query
-------------------------------------------------------------------------------

-- | Is the set empty?
--
-- >>> null empty
-- True
--
-- >>> null (range 10 20)
-- False
--
null :: Word8Set -> Bool
null :: Word8Set -> Bool
null (W8S Word256
xs) = Word256
xs Word256 -> Word256 -> Bool
forall a. Eq a => a -> a -> Bool
== Word256
forall a. Bits a => a
Bits.zeroBits

-- | Is the set full?
--
-- >>> isFull full
-- True
--
-- >>> isFull (range 1 255)
-- False
--
isFull :: Word8Set -> Bool
isFull :: Word8Set -> Bool
isFull (W8S Word256
xs) = Word256
xs Word256 -> Word256 -> Bool
forall a. Eq a => a -> a -> Bool
== Word256
ones

-- | Cardinality of the set.
--
-- >>> size empty
-- 0
--
-- >>> size (union (range 10 20) (range 30 40))
-- 22
--
size :: Word8Set -> Int
size :: Word8Set -> Int
size (W8S Word256
xs) = Word256 -> Int
forall a. Bits a => a -> Int
Bits.popCount Word256
xs

-- | Is the value a member of the set?
--
-- >>> member 5 (range 10 20)
-- False
--
-- >>> member 15 (range 10 20)
-- True
--
member :: Key -> Word8Set -> Bool
member :: Word8 -> Word8Set -> Bool
member Word8
x (W8S Word256
xs) = Word256 -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
Bits.testBit Word256
xs (Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
x)

-- | Is the element not in the set?
--
-- >>> notMember 5 (range 10 20)
-- True
--
-- >>> notMember 15 (range 10 20)
-- False
--
notMember :: Key -> Word8Set -> Bool
notMember :: Word8 -> Word8Set -> Bool
notMember Word8
x Word8Set
xs = Bool -> Bool
not (Word8 -> Word8Set -> Bool
member Word8
x Word8Set
xs)

-- | Is this a subset? @(s1 `isSubsetOf` s2)@ tells whether s1 is a subset of s2.
--
-- >>> isSubsetOf (range 10 20) (range 5 25)
-- True
--
-- >>> isSubsetOf (range 10 20) (range 10 20)
-- True
--
-- >>> isSubsetOf (range 5 25) (range 10 20)
-- False
--
isSubsetOf :: Word8Set -> Word8Set -> Bool
isSubsetOf :: Word8Set -> Word8Set -> Bool
isSubsetOf Word8Set
a Word8Set
b = Word8Set
b Word8Set -> Word8Set -> Bool
forall a. Eq a => a -> a -> Bool
== Word8Set -> Word8Set -> Word8Set
union Word8Set
a Word8Set
b

-- | Is this a proper subset? Is this a proper subset? (ie. a subset but not equal).
--
-- >>> isProperSubsetOf (range 10 20) (range 5 25)
-- True
--
-- >>> isProperSubsetOf (range 10 20) (range 10 20)
-- False
--
-- >>> isProperSubsetOf (range 5 25) (range 10 20)
-- False
--
isProperSubsetOf :: Word8Set -> Word8Set -> Bool
isProperSubsetOf :: Word8Set -> Word8Set -> Bool
isProperSubsetOf Word8Set
a Word8Set
b = Word8Set
b Word8Set -> Word8Set -> Bool
forall a. Eq a => a -> a -> Bool
== Word8Set -> Word8Set -> Word8Set
union Word8Set
a Word8Set
b Bool -> Bool -> Bool
&& Word8Set
a Word8Set -> Word8Set -> Bool
forall a. Eq a => a -> a -> Bool
/= Word8Set
b

-- | Is set singleton?
--
-- >>> isSingleton empty
-- Nothing
--
-- >>> isSingleton full
-- Nothing
--
-- >>> isSingleton (singleton 5)
-- Just 5
--
-- >>> isSingleton (fromList [3, 5])
-- Nothing
--
isSingleton :: Word8Set -> Maybe Key
isSingleton :: Word8Set -> Maybe Word8
isSingleton (W8S Word256
ws)
    | Word256 -> Int
forall a. Bits a => a -> Int
Bits.popCount Word256
ws Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
1 = Maybe Word8
forall a. Maybe a
Nothing
    | Bool
otherwise             = Word8 -> Maybe Word8
forall a. a -> Maybe a
Just (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word256 -> Int
forall a. FiniteBits a => a -> Int
ctz Word256
ws))

-- | Is set of the form @'range' l r@?
--
-- >>> isRange empty
-- Nothing
--
-- >>> isRange full
-- Just (0,255)
--
-- >>> isRange (singleton 5)
-- Just (5,5)
--
-- >>> isRange (range 10 20)
-- Just (10,20)
--
-- >>> isRange (fromList [3, 5])
-- Nothing
--
isRange :: Word8Set -> Maybe (Key, Key)
isRange :: Word8Set -> Maybe (Word8, Word8)
isRange (W8S Word256
0)  = Maybe (Word8, Word8)
forall a. Maybe a
Nothing
isRange (W8S Word256
ws) = if Word256 -> Int
forall a. Bits a => a -> Int
Bits.popCount Word256
ws Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
256 then (Word8, Word8) -> Maybe (Word8, Word8)
forall a. a -> Maybe a
Just (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
l, Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
255 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
r)) else Maybe (Word8, Word8)
forall a. Maybe a
Nothing
  where
    r :: Int
r = Word256 -> Int
forall a. FiniteBits a => a -> Int
clz Word256
ws
    l :: Int
l = Word256 -> Int
forall a. FiniteBits a => a -> Int
ctz Word256
ws

-- | Check whether two sets are disjoint (i.e. their intersection is empty).
--
-- >>> disjoint (range 11 20) (range 21 30)
-- True
--
disjoint :: Word8Set -> Word8Set -> Bool
disjoint :: Word8Set -> Word8Set -> Bool
disjoint Word8Set
xs Word8Set
ys = Word8Set -> Word8Set -> Word8Set
intersection Word8Set
xs Word8Set
ys Word8Set -> Word8Set -> Bool
forall a. Eq a => a -> a -> Bool
== Word8Set
empty

-- | Find largest element smaller than the given one.
--
-- >>> lookupLT 3 (fromList [3, 5])
-- Nothing
-- >>> lookupLT 5 (fromList [3, 5])
-- Just 3
--
-- >>> lookupLT 0 full
-- Nothing
lookupLT :: Key -> Word8Set -> Maybe Key
lookupLT :: Word8 -> Word8Set -> Maybe Word8
lookupLT Word8
0 Word8Set
_  = Maybe Word8
forall a. Maybe a
Nothing
lookupLT Word8
x Word8Set
xs = Word8 -> Word8Set -> Maybe Word8
lookupLE (Word8
x Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
1) Word8Set
xs

-- | Find smallest element greater than the given one.
--
-- >>> lookupGT 4 (fromList [3, 5])
-- Just 5
--
-- >>> lookupGT 5 (fromList [3, 5])
-- Nothing
--
-- >>> lookupGT 255 full
-- Nothing
--
lookupGT :: Key -> Word8Set -> Maybe Key
lookupGT :: Word8 -> Word8Set -> Maybe Word8
lookupGT Word8
255 Word8Set
_  = Maybe Word8
forall a. Maybe a
Nothing
lookupGT Word8
x   Word8Set
xs = Word8 -> Word8Set -> Maybe Word8
lookupGE (Word8
x Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
+ Word8
1) Word8Set
xs

-- | Find largest element smaller or equal to the given one.
--
-- >>> lookupLE 2 (fromList [3, 5])
-- Nothing
--
-- >>> lookupLE 4 (fromList [3, 5])
-- Just 3
--
-- >>> lookupLE 5 (fromList [3, 5])
-- Just 5
--
lookupLE :: Key -> Word8Set -> Maybe Key
lookupLE :: Word8 -> Word8Set -> Maybe Word8
lookupLE Word8
x Word8Set
xs = ((Word8, Word8Set) -> Word8)
-> Maybe (Word8, Word8Set) -> Maybe Word8
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Word8, Word8Set) -> Word8
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)))

-- | Find smallest element greater or equal to the given one.
--
-- >>> lookupGE 3 (fromList [3, 5])
-- Just 3
--
-- >>> lookupGE 4 (fromList [3, 5])
-- Just 5
--
-- >>> lookupGE 6 (fromList [3, 5])
-- Nothing
--
lookupGE :: Key -> Word8Set -> Maybe Key
lookupGE :: Word8 -> Word8Set -> Maybe Word8
lookupGE Word8
x Word8Set
xs = ((Word8, Word8Set) -> Word8)
-> Maybe (Word8, Word8Set) -> Maybe Word8
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Word8, Word8Set) -> Word8
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)))

-------------------------------------------------------------------------------
-- Combine
-------------------------------------------------------------------------------

-- | The complement of the set.
complement :: Word8Set -> Word8Set
complement :: Word8Set -> Word8Set
complement (W8S Word256
xs) = Word256 -> Word8Set
W8S (Word256 -> Word256
forall a. Bits a => a -> a
Bits.complement Word256
xs)

-- | The union of two sets.
union :: Word8Set -> Word8Set -> Word8Set
union :: Word8Set -> Word8Set -> Word8Set
union (W8S Word256
xs) (W8S Word256
ys) = Word256 -> Word8Set
W8S (Word256
xs Word256 -> Word256 -> Word256
forall a. Bits a => a -> a -> a
.|. Word256
ys)

-- | The union of a list of sets.
unions :: F.Foldable f => f Word8Set -> Word8Set
unions :: forall (f :: * -> *). Foldable f => f Word8Set -> Word8Set
unions f Word8Set
xs = (Word8Set -> Word8Set -> Word8Set)
-> Word8Set -> f Word8Set -> Word8Set
forall b a. (b -> a -> b) -> b -> f a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' Word8Set -> Word8Set -> Word8Set
union Word8Set
empty f Word8Set
xs

-- | The intersection between two sets.
intersection :: Word8Set -> Word8Set -> Word8Set
intersection :: Word8Set -> Word8Set -> Word8Set
intersection (W8S Word256
xs) (W8S Word256
ys) = Word256 -> Word8Set
W8S (Word256
xs Word256 -> Word256 -> Word256
forall a. Bits a => a -> a -> a
.&. Word256
ys)

-- | Difference between two sets.
difference :: Word8Set -> Word8Set -> Word8Set
difference :: Word8Set -> Word8Set -> Word8Set
difference Word8Set
xs Word8Set
ys = Word8Set -> Word8Set -> Word8Set
intersection Word8Set
xs (Word8Set -> Word8Set
complement Word8Set
ys)

-- | Symmetric difference between two sets
--
-- @
-- 'symmetricDifference' xs ys = 'difference' ('union' xs ys) ('intersection' xs ys)
-- @
--
-- >>> symmetricDifference (range 10 20) (range 15 25)
-- fromList [10,11,12,13,14,21,22,23,24,25]
--
-- @since 0.1.1
--
symmetricDifference :: Word8Set -> Word8Set -> Word8Set
symmetricDifference :: Word8Set -> Word8Set -> Word8Set
symmetricDifference (W8S Word256
xs) (W8S Word256
ys) = Word256 -> Word8Set
W8S (Word256 -> Word256 -> Word256
forall a. Bits a => a -> a -> a
Bits.xor Word256
xs Word256
ys)

-- | See 'difference'.
(\\) :: Word8Set -> Word8Set -> Word8Set
Word8Set
m1 \\ :: Word8Set -> Word8Set -> Word8Set
\\ Word8Set
m2 = Word8Set -> Word8Set -> Word8Set
difference Word8Set
m1 Word8Set
m2

-------------------------------------------------------------------------------
-- Filter
-------------------------------------------------------------------------------

-- | Filter all elements that satisfy some predicate.
--
-- >>> filter even (range 10 20)
-- fromList [10,12,14,16,18,20]
--
filter :: (Key -> Bool) -> Word8Set -> Word8Set
filter :: (Word8 -> Bool) -> Word8Set -> Word8Set
filter Word8 -> Bool
p = (Word8Set -> Word8 -> Word8Set) -> Word8Set -> Word8Set -> Word8Set
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 the set according to some predicate.
--
-- >>> partition even (range 10 20)
-- (fromList [10,12,14,16,18,20],fromList [11,13,15,17,19])
--
partition :: (Key -> Bool) -> Word8Set -> (Word8Set,Word8Set)
partition :: (Word8 -> Bool) -> Word8Set -> (Word8Set, Word8Set)
partition Word8 -> Bool
p = ((Word8Set, Word8Set) -> Word8 -> (Word8Set, Word8Set))
-> (Word8Set, Word8Set) -> Word8Set -> (Word8Set, Word8Set)
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
-------------------------------------------------------------------------------

-- |  @'map' f s@ is the set obtained by applying @f@ to each element of @s@.
--
-- >>> map (+ 1) (fromList [0, 10, 250, 255])
-- fromList [0,1,11,251]
--
map :: (Key -> Key) -> Word8Set -> Word8Set
map :: (Word8 -> Word8) -> Word8Set -> Word8Set
map Word8 -> Word8
f = (Word8Set -> Word8 -> Word8Set) -> Word8Set -> Word8Set -> Word8Set
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

-------------------------------------------------------------------------------
-- Folds
-------------------------------------------------------------------------------

-- | Lazy right fold.
--
-- >>> foldr (:) [] (unions [range 10 20, range 70 73, range 130 132, range 200 202, singleton 255])
-- [10,11,12,13,14,15,16,17,18,19,20,70,71,72,73,130,131,132,200,201,202,255]
--
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
clz Word64
a in Word64 -> Word64 -> Word64 -> Word64 -> b -> b
go0 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x)) Word64
b Word64
c Word64
d (Word8 -> b -> b
f (Word8
255 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Int -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
clz Word64
b in Word64 -> Word64 -> Word64 -> b -> b
go1 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
b (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x)) Word64
c Word64
d (Word8 -> b -> b
f (Word8
191 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Int -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
clz Word64
c in Word64 -> Word64 -> b -> b
go2 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
c (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x)) Word64
d (Word8 -> b -> b
f (Word8
127 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Int -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
clz Word64
a in Word64 -> b -> b
go3 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x)) (Word8 -> b -> b
f (Word8
63 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)

-- | Strict right fold.
--
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
clz Word64
a in Word64 -> Word64 -> Word64 -> Word64 -> b -> b
go0 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x)) Word64
b Word64
c Word64
d (Word8 -> b -> b
f (Word8
255 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Int -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
clz Word64
b in Word64 -> Word64 -> Word64 -> b -> b
go1 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
b (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x)) Word64
c Word64
d (Word8 -> b -> b
f (Word8
191 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Int -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
clz Word64
c in Word64 -> Word64 -> b -> b
go2 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
c (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x)) Word64
d (Word8 -> b -> b
f (Word8
127 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Int -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
clz Word64
a in Word64 -> b -> b
go3 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x)) (Word8 -> b -> b
f (Word8
63 Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x) b
acc)

-- | Lazy left fold.
--
-- >>> foldl (flip (:)) [] (unions [range 10 20, range 70 73, range 130 132, range 200 202, singleton 255])
-- [255,202,201,200,132,131,130,73,72,71,70,20,19,18,17,16,15,14,13,12,11,10]
--
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
ctz Word64
d in Word64 -> Word64 -> Word64 -> Word64 -> a -> a
go0 Word64
a Word64
b Word64
c (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
d Int
x) (a -> Word8 -> a
f a
acc (Int -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
ctz Word64
c in Word64 -> Word64 -> Word64 -> a -> a
go1 Word64
a Word64
b (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
c Int
x) (a -> Word8 -> a
f a
acc (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x Word8 -> Word8 -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
ctz Word64
b in Word64 -> Word64 -> a -> a
go2 Word64
a (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
b Int
x) (a -> Word8 -> a
f a
acc (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x Word8 -> Word8 -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
ctz Word64
a in Word64 -> a -> a
go3 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a Int
x) (a -> Word8 -> a
f a
acc (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
+ Word8
192))

-- | Strict left fold.
--
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
ctz Word64
d in Word64 -> Word64 -> Word64 -> Word64 -> a -> a
go0 Word64
a Word64
b Word64
c (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
d Int
x) (a -> Word8 -> a
f a
acc (Int -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
ctz Word64
c in Word64 -> Word64 -> Word64 -> a -> a
go1 Word64
a Word64
b (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
c Int
x) (a -> Word8 -> a
f a
acc (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x Word8 -> Word8 -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
ctz Word64
b in Word64 -> Word64 -> a -> a
go2 Word64
a (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
b Int
x) (a -> Word8 -> a
f a
acc (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x Word8 -> Word8 -> Word8
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 = Word64 -> Int
forall a. FiniteBits a => a -> Int
ctz Word64
a in Word64 -> a -> a
go3 (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
Bits.clearBit Word64
a Int
x) (a -> Word8 -> a
f a
acc (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
+ Word8
192))

-------------------------------------------------------------------------------
-- Min/Max
-------------------------------------------------------------------------------

-- | The minimal element of the set.
--
-- >>> findMin (fromList [3, 5])
-- 3
--
-- Returns 0 for empty set.
--
-- >>> findMin empty
-- 0
--
findMin :: Word8Set -> Word8
findMin :: Word8Set -> Word8
findMin (W8S Word256
xs) = Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word256 -> Int
forall a. FiniteBits a => a -> Int
ctz Word256
xs)

-- | The maximal element of the set.
--
-- >>> findMax (fromList [3, 5])
-- 5
--
-- Returns 255 for empty set.
--
-- >>> findMax empty
-- 255
--
findMax :: Word8Set -> Word8
findMax :: Word8Set -> Word8
findMax (W8S Word256
xs) = Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
255 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Word256 -> Int
forall a. FiniteBits a => a -> Int
clz Word256
xs)

-- | Delete the minimal element. Returns an empty set if the set is empty.
deleteMin :: Word8Set -> Word8Set
deleteMin :: Word8Set -> Word8Set
deleteMin = Word8Set
-> ((Word8, Word8Set) -> Word8Set)
-> Maybe (Word8, Word8Set)
-> Word8Set
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Word8Set
empty (Word8, Word8Set) -> Word8Set
forall a b. (a, b) -> b
snd (Maybe (Word8, Word8Set) -> Word8Set)
-> (Word8Set -> Maybe (Word8, Word8Set)) -> Word8Set -> Word8Set
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8Set -> Maybe (Word8, Word8Set)
minView

-- | Delete the maximal element. Returns an empty set if the set is empty.
deleteMax :: Word8Set -> Word8Set
deleteMax :: Word8Set -> Word8Set
deleteMax = Word8Set
-> ((Word8, Word8Set) -> Word8Set)
-> Maybe (Word8, Word8Set)
-> Word8Set
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Word8Set
empty (Word8, Word8Set) -> Word8Set
forall a b. (a, b) -> b
snd (Maybe (Word8, Word8Set) -> Word8Set)
-> (Word8Set -> Maybe (Word8, Word8Set)) -> Word8Set -> Word8Set
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8Set -> Maybe (Word8, Word8Set)
minView

-- | Retrieves the maximal key of the set, and the set
-- stripped of that element, or 'Nothing' if passed an empty set.
--
-- >>> maxView (fromList [3, 5])
-- Just (5,fromList [3])
--
-- >>> maxView empty
-- Nothing
--
maxView :: Word8Set -> Maybe (Key, Word8Set)
maxView :: Word8Set -> Maybe (Word8, Word8Set)
maxView Word8Set
xs
    | Word8Set -> Bool
null Word8Set
xs   = Maybe (Word8, Word8Set)
forall a. Maybe a
Nothing
    | Bool
otherwise = let !x :: Word8
x = Word8Set -> Word8
findMax Word8Set
xs in (Word8, Word8Set) -> Maybe (Word8, Word8Set)
forall a. a -> Maybe a
Just (Word8
x, Word8 -> Word8Set -> Word8Set
delete Word8
x Word8Set
xs)

-- | Retrieves the minimal key of the set, and the set
-- stripped of that element, or 'Nothing' if passed an empty set.
--
-- >>> minView (fromList [3, 5])
-- Just (3,fromList [5])
--
-- >>> minView empty
-- Nothing
--
minView :: Word8Set -> Maybe (Key, Word8Set)
minView :: Word8Set -> Maybe (Word8, Word8Set)
minView Word8Set
xs
    | Word8Set -> Bool
null Word8Set
xs   = Maybe (Word8, Word8Set)
forall a. Maybe a
Nothing
    | Bool
otherwise = let !x :: Word8
x = Word8Set -> Word8
findMin Word8Set
xs in (Word8, Word8Set) -> Maybe (Word8, Word8Set)
forall a. a -> Maybe a
Just (Word8
x, Word8 -> Word8Set -> Word8Set
delete Word8
x Word8Set
xs)

-------------------------------------------------------------------------------
-- List
-------------------------------------------------------------------------------

-- | The elements of a set in ascending order.
elems :: Word8Set -> [Key]
elems :: Word8Set -> [Word8]
elems = Word8Set -> [Word8]
toList

-- | The elements of a set in ascending order.
toList :: Word8Set -> [Key]
toList :: Word8Set -> [Word8]
toList Word8Set
xs = (forall b. (Word8 -> b -> b) -> b -> b) -> [Word8]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
GHC.Exts.build (\Word8 -> b -> b
c b
n -> (Word8 -> b -> b) -> b -> Word8Set -> b
forall b. (Word8 -> b -> b) -> b -> Word8Set -> b
foldr Word8 -> b -> b
c b
n Word8Set
xs)

-- | Create a set from a list of 'Word8's.
fromList :: [Key] -> Word8Set
fromList :: [Word8] -> Word8Set
fromList [Word8]
w8s = (Word8Set -> Word8 -> Word8Set) -> Word8Set -> [Word8] -> Word8Set
forall b a. (b -> a -> b) -> b -> [a] -> b
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

-- | Create a set from a foldable of 'Word8's.
fromFoldable :: F.Foldable f => f Key -> Word8Set
#if MIN_VERSION_base(4,13,0)
fromFoldable :: forall (f :: * -> *). Foldable f => f Word8 -> Word8Set
fromFoldable = (Word8 -> Word8Set) -> f Word8 -> Word8Set
forall m a. Monoid m => (a -> m) -> f a -> m
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

-------------------------------------------------------------------------------
-- Word256
-------------------------------------------------------------------------------

-- | Convert set to 'Word256'.
toWord256 :: Word8Set -> Word256
toWord256 :: Word8Set -> Word256
toWord256 (W8S Word256
xs) = Word256
xs

-- | Create set from 'Word256'.
fromWord256 :: Word256 -> Word8Set
fromWord256 :: Word256 -> Word8Set
fromWord256 = Word256 -> Word8Set
W8S

-------------------------------------------------------------------------------
-- ASCII
-------------------------------------------------------------------------------

-- | Create ASCII string from a set.
--
-- >>> toASCII (range 100 120)
-- "defghijklmnopqrstuvwx"
--
toASCII :: Word8Set -> String
toASCII :: Word8Set -> String
toASCII = (Word8 -> Char) -> [Word8] -> String
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int -> Char
chr (Int -> Char) -> (Word8 -> Int) -> Word8 -> Char
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral) ([Word8] -> String) -> (Word8Set -> [Word8]) -> Word8Set -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8Set -> [Word8]
toList

-- | Create set from ASCII string.
--
-- >>> fromASCII "foobar"
-- fromList [97,98,102,111,114]
--
-- Non-ASCII codepoints are truncated:
--
-- >>> fromASCII "\1000"
-- fromList [232]
--
fromASCII :: String -> Word8Set
fromASCII :: String -> Word8Set
fromASCII = [Word8] -> Word8Set
fromList ([Word8] -> Word8Set) -> (String -> [Word8]) -> String -> Word8Set
forall b c a. (b -> c) -> (a -> b) -> a -> c
.  (Char -> Word8) -> String -> [Word8]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Word8) -> (Char -> Int) -> Char -> Word8
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Int
ord)

-------------------------------------------------------------------------------
-- Helpers
-------------------------------------------------------------------------------

clz :: Bits.FiniteBits a => a -> Int
clz :: forall a. FiniteBits a => a -> Int
clz = a -> Int
forall a. FiniteBits a => a -> Int
Bits.countLeadingZeros
{-# INLINE clz #-}

ctz :: Bits.FiniteBits a => a -> Int
ctz :: forall a. FiniteBits a => a -> Int
ctz = a -> Int
forall a. FiniteBits a => a -> Int
Bits.countTrailingZeros
{-# INLINE ctz #-}