{-# LANGUAGE ExplicitForAll   #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies     #-}
{-# LANGUAGE UnicodeSyntax    #-}

-- | Efficient sets over bounded enumerations, using bitwise operations based on

-- [containers](https://hackage.haskell.org/package/containers-0.6.0.1/docs/src/Data.IntSet.Internal.html)

-- and

-- [EdisonCore](https://hackage.haskell.org/package/EdisonCore-1.3.2.1/docs/src/Data-Edison-Coll-EnumSet.html).

-- In many cases, @EnumSet@s may be optimised away entirely by constant folding

-- at compile-time. For example, in the following code:

--

-- @

-- import Data.Enum.Set as E

--

-- data Foo = A | B | C | D | E | F | G | H deriving (Bounded, Enum, Eq, Ord)

--

-- instance E.AsEnumSet Foo

--

-- addFoos :: E.EnumSet Foo -> E.EnumSet Foo

-- addFoos = E.delete A . E.insert B

--

-- bar :: E.EnumSet Foo

-- bar = addFoos $ E.fromFoldable [A, C, E]

--

-- barHasA :: Bool

-- barHasA = E.member A bar

-- @

--

-- With @-O@ or @-O2@, @bar@ will compile to @GHC.Types.W\# 22\#\#@ and

-- @barHasA@ will compile to @GHC.Types.False@.

--

-- By default, 'Word's are used as the representation. Other representations may

-- be chosen in the class instance:

--

-- @

-- {-\# LANGUAGE TypeFamilies \#-}

--

-- import Data.Enum.Set as E

-- import Data.Word (Word64)

--

-- data Foo = A | B | C | D | E | F | G | H deriving (Bounded, Enum, Eq, Ord, Show)

--

-- instance E.AsEnumSet Foo where

--     type EnumSetRep Foo = Word64

--

-- @

--

-- For type @EnumSet E@, @EnumSetRep E@ should be a @Word@-like type that

-- implements 'Bits' and 'Num', and @E@ should be a type that implements 'Eq'

-- and 'Enum' equivalently and is a bijection to 'Int' over its range.

-- @EnumSet E@ can only store a value of @E@ if the result of applying

-- 'fromEnum' to the value is positive and less than the number of bits in

-- @EnumSetRep E@. For this reason, it is preferable for @E@ to be a type that

-- derives @Eq@ and @Enum@, and for @EnumSetRep E@ to have more bits than the

-- number of constructors of @E@.

--

-- If the highest @fromEnum@ value of @E@ is 29, @EnumSetRep E@ should be

-- 'Word', because it always has at least 30 bits. This is the

-- default implementation.

-- Otherwise, options include 'Data.Word.Word32', 'Data.Word.Word64', and the

-- [wide-word](https://hackage.haskell.org/package/wide-word-0.1.0.8/) package's

-- [Data.WideWord.Word128](https://hackage.haskell.org/package/wide-word-0.1.0.8/docs/Data-WideWord-Word128.html).

-- Foreign types may also be used.

--

-- Note: complexity calculations assume that @EnumSetRep E@ implements 'Bits'

-- with constant-time functions, as is the case with @Word@ etc. Otherwise, the

-- complexity of those operations should be added to the complexity of @EnumSet@

-- functions.

module Data.Enum.Set
  ( AsEnumSet(..)
  -- * Set type

  , EnumSet
    -- * Construction

  , empty
  , singleton
  , fromFoldable

  -- * Insertion

  , insert

  -- * Deletion

  , delete

  -- * Query

  , member
  , notMember
  , null
  , size
  , isSubsetOf

  -- * Combine

  , union
  , difference
  , (\\)
  , symmetricDifference
  , intersection

  -- * Filter

  , filter
  , partition

  -- * Map

  , map

  -- * Folds

  , foldl, foldl', foldr, foldr'
  , foldl1, foldl1', foldr1, foldr1'

  -- ** Special folds

  , foldMap
  , traverse
  , any
  , all

   -- * Min/Max

  , minimum
  , maximum
  , deleteMin
  , deleteMax
  , minView
  , maxView

  -- * Conversion

  , toList
  , fromRaw
  , toRaw
  ) where

import Prelude hiding (all, any, filter, foldl, foldl1, foldMap, foldr, foldr1, map, maximum, minimum, null, traverse)

import Data.Bits

import qualified Data.Enum.Set.Base as E

class (Enum a, FiniteBits (EnumSetRep a), Num (EnumSetRep a)) => AsEnumSet a where
    type EnumSetRep a
    type EnumSetRep a = Word

type EnumSet a = E.EnumSet (EnumSetRep a) a

{--------------------------------------------------------------------
  Construction
--------------------------------------------------------------------}

-- | /O(1)/. The empty set.

empty :: ∀ a. AsEnumSet a => EnumSet a
empty :: EnumSet a
empty = EnumSet a
forall k w (a :: k). Bits w => EnumSet w a
E.empty
{-# INLINE empty #-}

-- | /O(1)/. A set of one element.

singleton :: ∀ a. AsEnumSet a => a -> EnumSet a
singleton :: a -> EnumSet a
singleton = a -> EnumSet a
forall w a. (Bits w, Enum a) => a -> EnumSet w a
E.singleton
{-# INLINE singleton #-}

-- | /O(n)/. Create a set from a finite foldable data structure.

fromFoldable :: ∀ f a. (Foldable f, AsEnumSet a) => f a -> EnumSet a
fromFoldable :: f a -> EnumSet a
fromFoldable = f a -> EnumSet a
forall (f :: * -> *) w a.
(Foldable f, Bits w, Enum a) =>
f a -> EnumSet w a
E.fromFoldable
{-# INLINE fromFoldable #-}

{--------------------------------------------------------------------
  Insertion
--------------------------------------------------------------------}

-- | /O(1)/. Add a value to the set.

insert :: ∀ a. AsEnumSet a => a -> EnumSet a -> EnumSet a
insert :: a -> EnumSet a -> EnumSet a
insert = a -> EnumSet a -> EnumSet a
forall w a. (Bits w, Enum a) => a -> EnumSet w a -> EnumSet w a
E.insert
{-# INLINE insert #-}

{--------------------------------------------------------------------
  Deletion
--------------------------------------------------------------------}

-- | /O(1)/. Delete a value in the set.

delete :: ∀ a. AsEnumSet a => a -> EnumSet a -> EnumSet a
delete :: a -> EnumSet a -> EnumSet a
delete = a -> EnumSet a -> EnumSet a
forall w a. (Bits w, Enum a) => a -> EnumSet w a -> EnumSet w a
E.delete
{-# INLINE delete #-}

{--------------------------------------------------------------------
  Query
--------------------------------------------------------------------}

-- | /O(1)/. Is the value a member of the set?

member :: ∀ a. AsEnumSet a => a -> EnumSet a -> Bool
member :: a -> EnumSet a -> Bool
member = a -> EnumSet a -> Bool
forall w a. (Bits w, Enum a) => a -> EnumSet w a -> Bool
E.member
{-# INLINE member #-}

-- | /O(1)/. Is the value not in the set?

notMember :: ∀ a. AsEnumSet a => a -> EnumSet a -> Bool
notMember :: a -> EnumSet a -> Bool
notMember = a -> EnumSet a -> Bool
forall w a. (Bits w, Enum a) => a -> EnumSet w a -> Bool
E.notMember
{-# INLINE notMember #-}

-- | /O(1)/. Is this the empty set?

null :: ∀ a. AsEnumSet a => EnumSet a -> Bool
null :: EnumSet a -> Bool
null = EnumSet a -> Bool
forall k w (a :: k). Bits w => EnumSet w a -> Bool
E.null
{-# INLINE null #-}

-- | /O(1)/. The number of elements in the set.

size :: ∀ a. AsEnumSet a => EnumSet a -> Int
size :: EnumSet a -> Int
size = EnumSet a -> Int
forall k w (a :: k). (Bits w, Num w) => EnumSet w a -> Int
E.size
{-# INLINE size #-}

-- | /O(1)/. Is this a subset?

-- @(s1 \`isSubsetOf\` s2)@ tells whether @s1@ is a subset of @s2@.

isSubsetOf :: ∀ a. AsEnumSet a => EnumSet a -> EnumSet a -> Bool
isSubsetOf :: EnumSet a -> EnumSet a -> Bool
isSubsetOf = EnumSet a -> EnumSet a -> Bool
forall k w (a :: k). Bits w => EnumSet w a -> EnumSet w a -> Bool
E.isSubsetOf
{-# INLINE isSubsetOf #-}

{--------------------------------------------------------------------
  Combine
--------------------------------------------------------------------}

-- | /O(1)/. The union of two sets.

union :: ∀ a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
union :: EnumSet a -> EnumSet a -> EnumSet a
union = EnumSet a -> EnumSet a -> EnumSet a
forall k w (a :: k).
Bits w =>
EnumSet w a -> EnumSet w a -> EnumSet w a
E.union
{-# INLINE union #-}

-- | /O(1)/. Difference between two sets.

difference :: ∀ a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
difference :: EnumSet a -> EnumSet a -> EnumSet a
difference = EnumSet a -> EnumSet a -> EnumSet a
forall k w (a :: k).
Bits w =>
EnumSet w a -> EnumSet w a -> EnumSet w a
E.difference
{-# INLINE difference #-}

-- | /O(1)/. See 'difference'.

(\\) :: ∀ a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
\\ :: EnumSet a -> EnumSet a -> EnumSet a
(\\) = EnumSet a -> EnumSet a -> EnumSet a
forall k w (a :: k).
Bits w =>
EnumSet w a -> EnumSet w a -> EnumSet w a
E.difference
infixl 9 \\
{-# INLINE (\\) #-}

-- | /O(1)/. Elements which are in either set, but not both.

symmetricDifference :: ∀ a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
symmetricDifference :: EnumSet a -> EnumSet a -> EnumSet a
symmetricDifference = EnumSet a -> EnumSet a -> EnumSet a
forall k w (a :: k).
Bits w =>
EnumSet w a -> EnumSet w a -> EnumSet w a
E.symmetricDifference
{-# INLINE symmetricDifference #-}

-- | /O(1)/. The intersection of two sets.

intersection :: ∀ a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
intersection :: EnumSet a -> EnumSet a -> EnumSet a
intersection = EnumSet a -> EnumSet a -> EnumSet a
forall k w (a :: k).
Bits w =>
EnumSet w a -> EnumSet w a -> EnumSet w a
E.intersection
{-# INLINE intersection #-}

{--------------------------------------------------------------------
  Filter
--------------------------------------------------------------------}

-- | /O(n)/. Filter all elements that satisfy some predicate.

filter :: ∀ a. AsEnumSet a => (a -> Bool) -> EnumSet a -> EnumSet a
filter :: (a -> Bool) -> EnumSet a -> EnumSet a
filter = (a -> Bool) -> EnumSet a -> EnumSet a
forall w a.
(FiniteBits w, Num w, Enum a) =>
(a -> Bool) -> EnumSet w a -> EnumSet w a
E.filter
{-# INLINE filter #-}

-- | /O(n)/. Partition the set according to some predicate.

-- The first set contains all elements that satisfy the predicate,

-- the second all elements that fail the predicate.

partition :: ∀ a. AsEnumSet a
          => (a -> Bool) -> EnumSet a -> (EnumSet a, EnumSet a)
partition :: (a -> Bool) -> EnumSet a -> (EnumSet a, EnumSet a)
partition = (a -> Bool) -> EnumSet a -> (EnumSet a, EnumSet a)
forall w a.
(FiniteBits w, Num w, Enum a) =>
(a -> Bool) -> EnumSet w a -> (EnumSet w a, EnumSet w a)
E.partition
{-# INLINE partition #-}

{--------------------------------------------------------------------
  Map
--------------------------------------------------------------------}

-- | /O(n)/.

-- @'map' f s@ is the set obtained by applying @f@ to each element of @s@.

--

-- It's worth noting that the size of the result may be smaller if,

-- for some @(x,y)@, @x \/= y && f x == f y@

map :: ∀ a b. (AsEnumSet a, AsEnumSet b) => (a -> b) -> EnumSet a -> EnumSet b
map :: (a -> b) -> EnumSet a -> EnumSet b
map = (a -> b) -> EnumSet a -> EnumSet b
forall v w a b.
(FiniteBits v, FiniteBits w, Num v, Num w, Enum a, Enum b) =>
(a -> b) -> EnumSet v a -> EnumSet w b
E.map'

{--------------------------------------------------------------------
  Folds
--------------------------------------------------------------------}

-- | /O(n)/. Left fold.

foldl :: ∀ a b. AsEnumSet a => (b -> a -> b) -> b -> EnumSet a -> b
foldl :: (b -> a -> b) -> b -> EnumSet a -> b
foldl = (b -> a -> b) -> b -> EnumSet a -> b
forall w a b.
(FiniteBits w, Num w, Enum a) =>
(b -> a -> b) -> b -> EnumSet w a -> b
E.foldl
{-# INLINE foldl #-}

-- | /O(n)/. Left fold with strict accumulator.

foldl' :: ∀ a b. AsEnumSet a => (b -> a -> b) -> b -> EnumSet a -> b
foldl' :: (b -> a -> b) -> b -> EnumSet a -> b
foldl' = (b -> a -> b) -> b -> EnumSet a -> b
forall w a b.
(FiniteBits w, Num w, Enum a) =>
(b -> a -> b) -> b -> EnumSet w a -> b
E.foldl'
{-# INLINE foldl' #-}

-- | /O(n)/. Right fold.

foldr :: ∀ a b. AsEnumSet a => (a -> b -> b) -> b -> EnumSet a -> b
foldr :: (a -> b -> b) -> b -> EnumSet a -> b
foldr = (a -> b -> b) -> b -> EnumSet a -> b
forall w a b.
(FiniteBits w, Num w, Enum a) =>
(a -> b -> b) -> b -> EnumSet w a -> b
E.foldr
{-# INLINE foldr #-}

-- | /O(n)/. Right fold with strict accumulator.

foldr' :: ∀ a b. AsEnumSet a => (a -> b -> b) -> b -> EnumSet a -> b
foldr' :: (a -> b -> b) -> b -> EnumSet a -> b
foldr' = (a -> b -> b) -> b -> EnumSet a -> b
forall w a b.
(FiniteBits w, Num w, Enum a) =>
(a -> b -> b) -> b -> EnumSet w a -> b
E.foldr'
{-# INLINE foldr' #-}

-- | /O(n)/. Left fold on non-empty sets.

foldl1 :: ∀ a. AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
foldl1 :: (a -> a -> a) -> EnumSet a -> a
foldl1 = (a -> a -> a) -> EnumSet a -> a
forall w a.
(FiniteBits w, Num w, Enum a) =>
(a -> a -> a) -> EnumSet w a -> a
E.foldl1
{-# INLINE foldl1 #-}

-- | /O(n)/. Left fold on non-empty sets with strict accumulator.

foldl1' :: ∀ a. AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
foldl1' :: (a -> a -> a) -> EnumSet a -> a
foldl1' = (a -> a -> a) -> EnumSet a -> a
forall w a.
(FiniteBits w, Num w, Enum a) =>
(a -> a -> a) -> EnumSet w a -> a
E.foldl1'
{-# INLINE foldl1' #-}

-- | /O(n)/. Right fold on non-empty sets.

foldr1 :: ∀ a. AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
foldr1 :: (a -> a -> a) -> EnumSet a -> a
foldr1 = (a -> a -> a) -> EnumSet a -> a
forall w a.
(FiniteBits w, Num w, Enum a) =>
(a -> a -> a) -> EnumSet w a -> a
E.foldr1
{-# INLINE foldr1 #-}

-- | /O(n)/. Right fold on non-empty sets with strict accumulator.

foldr1' :: ∀ a. AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
foldr1' :: (a -> a -> a) -> EnumSet a -> a
foldr1' = (a -> a -> a) -> EnumSet a -> a
forall w a.
(FiniteBits w, Num w, Enum a) =>
(a -> a -> a) -> EnumSet w a -> a
E.foldr1'
{-# INLINE foldr1'  #-}

-- | /O(n)/. Map each element of the structure to a monoid, and combine the

-- results.

foldMap :: ∀ m a. (Monoid m, AsEnumSet a) => (a -> m) -> EnumSet a -> m
foldMap :: (a -> m) -> EnumSet a -> m
foldMap = (a -> m) -> EnumSet a -> m
forall m w a.
(Monoid m, FiniteBits w, Num w, Enum a) =>
(a -> m) -> EnumSet w a -> m
E.foldMap
{-# INLINE foldMap #-}

traverse :: ∀ f a. (Applicative f, AsEnumSet a)
         => (a -> f a) -> EnumSet a -> f (EnumSet a)
traverse :: (a -> f a) -> EnumSet a -> f (EnumSet a)
traverse = (a -> f a) -> EnumSet a -> f (EnumSet a)
forall (f :: * -> *) w a.
(Applicative f, FiniteBits w, Num w, Enum a) =>
(a -> f a) -> EnumSet w a -> f (EnumSet w a)
E.traverse
{-# INLINE traverse #-}

-- | /O(n)/. Check if all elements satisfy some predicate.

all :: ∀ a. AsEnumSet a => (a -> Bool) -> EnumSet a -> Bool
all :: (a -> Bool) -> EnumSet a -> Bool
all = (a -> Bool) -> EnumSet a -> Bool
forall w a.
(FiniteBits w, Num w, Enum a) =>
(a -> Bool) -> EnumSet w a -> Bool
E.all
{-# INLINE all #-}

-- | /O(n)/. Check if any element satisfies some predicate.

any :: ∀ a. AsEnumSet a => (a -> Bool) -> EnumSet a -> Bool
any :: (a -> Bool) -> EnumSet a -> Bool
any = (a -> Bool) -> EnumSet a -> Bool
forall w a.
(FiniteBits w, Num w, Enum a) =>
(a -> Bool) -> EnumSet w a -> Bool
E.any
{-# INLINE any #-}

{--------------------------------------------------------------------
  Min/Max
--------------------------------------------------------------------}

-- | /O(1)/. The minimal element of a non-empty set.

minimum :: ∀ a. AsEnumSet a => EnumSet a -> a
minimum :: EnumSet a -> a
minimum = EnumSet a -> a
forall w a. (FiniteBits w, Num w, Enum a) => EnumSet w a -> a
E.minimum
{-# INLINE minimum #-}

-- | /O(1)/. The maximal element of a non-empty set.

maximum :: ∀ a. AsEnumSet a => EnumSet a -> a
maximum :: EnumSet a -> a
maximum = EnumSet a -> a
forall w a. (FiniteBits w, Num w, Enum a) => EnumSet w a -> a
E.maximum
{-# INLINE maximum #-}

-- | /O(1)/. Delete the minimal element.

deleteMin :: ∀ a. AsEnumSet a => EnumSet a -> EnumSet a
deleteMin :: EnumSet a -> EnumSet a
deleteMin = EnumSet a -> EnumSet a
forall k w (a :: k).
(FiniteBits w, Num w) =>
EnumSet w a -> EnumSet w a
E.deleteMin
{-# INLINE deleteMin #-}

-- | /O(1)/. Delete the maximal element.

deleteMax :: ∀ a. AsEnumSet a => EnumSet a -> EnumSet a
deleteMax :: EnumSet a -> EnumSet a
deleteMax = EnumSet a -> EnumSet a
forall k w (a :: k).
(FiniteBits w, Num w) =>
EnumSet w a -> EnumSet w a
E.deleteMax
{-# INLINE deleteMax #-}

-- | /O(1)/. Retrieves the minimal element of the set,

-- and the set stripped of that element,

-- or Nothing if passed an empty set.

minView :: ∀ a. AsEnumSet a => EnumSet a -> Maybe (a, EnumSet a)
minView :: EnumSet a -> Maybe (a, EnumSet a)
minView = EnumSet a -> Maybe (a, EnumSet a)
forall w a.
(FiniteBits w, Num w, Enum a) =>
EnumSet w a -> Maybe (a, EnumSet w a)
E.minView
{-# INLINE minView #-}

-- | /O(1)/. Retrieves the maximal element of the set,

-- and the set stripped of that element,

-- or Nothing if passed an empty set.

maxView :: ∀ a. AsEnumSet a => EnumSet a -> Maybe (a, EnumSet a)
maxView :: EnumSet a -> Maybe (a, EnumSet a)
maxView = EnumSet a -> Maybe (a, EnumSet a)
forall w a.
(FiniteBits w, Num w, Enum a) =>
EnumSet w a -> Maybe (a, EnumSet w a)
E.maxView
{-# INLINE maxView #-}

{--------------------------------------------------------------------
  Conversion
--------------------------------------------------------------------}

-- | /O(n)/. Convert the set to a list of values.

toList :: ∀ a. AsEnumSet a => EnumSet a -> [a]
toList :: EnumSet a -> [a]
toList = EnumSet a -> [a]
forall w a. (FiniteBits w, Num w, Enum a) => EnumSet w a -> [a]
E.toList
{-# INLINE toList #-}

-- | /O(1)/. Convert a representation into an @EnumSet@.

-- Intended for use with foreign types.

fromRaw :: ∀ a. AsEnumSet a => EnumSetRep a -> EnumSet a
fromRaw :: EnumSetRep a -> EnumSet a
fromRaw = EnumSetRep a -> EnumSet a
forall k w (a :: k). w -> EnumSet w a
E.fromRaw
{-# INLINE fromRaw #-}

-- | /O(1)/. Convert an @EnumSet@ into its representation.

-- Intended for use with foreign types.

toRaw :: ∀ a. AsEnumSet a => EnumSet a -> EnumSetRep a
toRaw :: EnumSet a -> EnumSetRep a
toRaw = EnumSet a -> EnumSetRep a
forall k w (a :: k). EnumSet w a -> w
E.toRaw
{-# INLINE toRaw #-}