-- | A collection of a number of data types and type classes shared by all
-- bitset variants.

module Data.PrimitiveArray.Index.BitSetClasses where

import           Control.DeepSeq (NFData(..))
import           Data.Aeson (FromJSON,ToJSON,FromJSONKey,ToJSONKey)
import           Data.Binary (Binary)
import           Data.Hashable (Hashable)
import           Data.Serialize (Serialize)
import           Data.Vector.Unboxed.Deriving
import           GHC.Generics (Generic)
import qualified Data.Vector.Fusion.Stream.Monadic as SM
import qualified Data.Vector.Unboxed as VU

import           Data.Bits.Ordered
import           Data.PrimitiveArray.Index.Class
import           Data.PrimitiveArray.Index.IOC



-- * Boundaries, the interface(s) for bitsets.

-- | Certain sets have an interface, a particular element with special
-- meaning. In this module, certain ``meanings'' are already provided.
-- These include a @First@ element and a @Last@ element. We phantom-type
-- these to reduce programming overhead.

newtype Boundary boundaryType ioc = Boundary { Boundary boundaryType ioc -> Int
getBoundary ∷ Int }
  deriving stock (Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
(Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool)
-> (Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool)
-> Eq (Boundary boundaryType ioc)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
/= :: Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
$c/= :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
== :: Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
$c== :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
Eq,Eq (Boundary boundaryType ioc)
Eq (Boundary boundaryType ioc)
-> (Boundary boundaryType ioc
    -> Boundary boundaryType ioc -> Ordering)
-> (Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool)
-> (Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool)
-> (Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool)
-> (Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool)
-> (Boundary boundaryType ioc
    -> Boundary boundaryType ioc -> Boundary boundaryType ioc)
-> (Boundary boundaryType ioc
    -> Boundary boundaryType ioc -> Boundary boundaryType ioc)
-> Ord (Boundary boundaryType ioc)
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Ordering
Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
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
forall k (boundaryType :: k) k (ioc :: k).
Eq (Boundary boundaryType ioc)
forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Ordering
forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
min :: Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
$cmin :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
max :: Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
$cmax :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
>= :: Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
$c>= :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
> :: Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
$c> :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
<= :: Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
$c<= :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
< :: Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
$c< :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Bool
compare :: Boundary boundaryType ioc -> Boundary boundaryType ioc -> Ordering
$ccompare :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc -> Ordering
$cp1Ord :: forall k (boundaryType :: k) k (ioc :: k).
Eq (Boundary boundaryType ioc)
Ord,(forall x.
 Boundary boundaryType ioc -> Rep (Boundary boundaryType ioc) x)
-> (forall x.
    Rep (Boundary boundaryType ioc) x -> Boundary boundaryType ioc)
-> Generic (Boundary boundaryType ioc)
forall x.
Rep (Boundary boundaryType ioc) x -> Boundary boundaryType ioc
forall x.
Boundary boundaryType ioc -> Rep (Boundary boundaryType ioc) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k (boundaryType :: k) k (ioc :: k) x.
Rep (Boundary boundaryType ioc) x -> Boundary boundaryType ioc
forall k (boundaryType :: k) k (ioc :: k) x.
Boundary boundaryType ioc -> Rep (Boundary boundaryType ioc) x
$cto :: forall k (boundaryType :: k) k (ioc :: k) x.
Rep (Boundary boundaryType ioc) x -> Boundary boundaryType ioc
$cfrom :: forall k (boundaryType :: k) k (ioc :: k) x.
Boundary boundaryType ioc -> Rep (Boundary boundaryType ioc) x
Generic)
  deriving newtype (Integer -> Boundary boundaryType ioc
Boundary boundaryType ioc -> Boundary boundaryType ioc
Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
(Boundary boundaryType ioc
 -> Boundary boundaryType ioc -> Boundary boundaryType ioc)
-> (Boundary boundaryType ioc
    -> Boundary boundaryType ioc -> Boundary boundaryType ioc)
-> (Boundary boundaryType ioc
    -> Boundary boundaryType ioc -> Boundary boundaryType ioc)
-> (Boundary boundaryType ioc -> Boundary boundaryType ioc)
-> (Boundary boundaryType ioc -> Boundary boundaryType ioc)
-> (Boundary boundaryType ioc -> Boundary boundaryType ioc)
-> (Integer -> Boundary boundaryType ioc)
-> Num (Boundary boundaryType ioc)
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
forall k (boundaryType :: k) k (ioc :: k).
Integer -> Boundary boundaryType ioc
forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc
forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
fromInteger :: Integer -> Boundary boundaryType ioc
$cfromInteger :: forall k (boundaryType :: k) k (ioc :: k).
Integer -> Boundary boundaryType ioc
signum :: Boundary boundaryType ioc -> Boundary boundaryType ioc
$csignum :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc
abs :: Boundary boundaryType ioc -> Boundary boundaryType ioc
$cabs :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc
negate :: Boundary boundaryType ioc -> Boundary boundaryType ioc
$cnegate :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Boundary boundaryType ioc
* :: Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
$c* :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
- :: Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
$c- :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
+ :: Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
$c+ :: forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc
-> Boundary boundaryType ioc -> Boundary boundaryType ioc
Num)

-- | Whenever we can not set the boundary we should have for a set, we use this
-- pattern. All legal boundaries are @>=0@. We also need to set the undefined
-- boundary to @0@, since the @linearIndex@ will use this value to add, which
-- for empty sets would reduce to @0 - UndefBoundary === 0@.

pattern UndefBoundary ∷ Boundary boundaryType ioc
pattern $bUndefBoundary :: Boundary boundaryType ioc
$mUndefBoundary :: forall r k1 k2 (boundaryType :: k1) (ioc :: k2).
Boundary boundaryType ioc -> (Void# -> r) -> (Void# -> r) -> r
UndefBoundary = Boundary 0

instance Show (Boundary i t) where
  show :: Boundary i t -> String
show (Boundary Int
i) = String
"(I:" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
i String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"

derivingUnbox "Boundary"
  [t| forall i t . Boundary i t → Int |]
  [| \(Boundary i) → i                |]
  [| Boundary                         |]

instance Binary    (Boundary i t)
instance Serialize (Boundary i t)
instance ToJSON    (Boundary i t)
instance FromJSON  (Boundary i t)
instance Hashable  (Boundary i t)

instance NFData (Boundary i t) where
  rnf :: Boundary i t -> ()
rnf (Boundary Int
i) = Int -> ()
forall a. NFData a => a -> ()
rnf Int
i
  {-# Inline rnf #-}

instance Index (Boundary i t) where
  newtype LimitType (Boundary i t) = LtBoundary Int
  linearIndex :: LimitType (Boundary i t) -> Boundary i t -> Int
linearIndex LimitType (Boundary i t)
_ (Boundary Int
z) = Int
z
  {-# INLINE linearIndex #-}
  size :: LimitType (Boundary i t) -> Int
size (LtBoundary h) = Int
h Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
  {-# INLINE size #-}
  inBounds :: LimitType (Boundary i t) -> Boundary i t -> Bool
inBounds (LtBoundary h) Boundary i t
z = Boundary i t
0 Boundary i t -> Boundary i t -> Bool
forall a. Ord a => a -> a -> Bool
<= Boundary i t
z Bool -> Bool -> Bool
&& Boundary i t -> Int
forall k (boundaryType :: k) k (ioc :: k).
Boundary boundaryType ioc -> Int
getBoundary Boundary i t
z Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
h
  {-# INLINE inBounds #-}
  zeroBound :: Boundary i t
zeroBound = Int -> Boundary i t
forall k k (boundaryType :: k) (ioc :: k).
Int -> Boundary boundaryType ioc
Boundary Int
0
  {-# Inline zeroBound #-}
  zeroBound' :: LimitType (Boundary i t)
zeroBound' = Int -> LimitType (Boundary i t)
forall k k (i :: k) (t :: k). Int -> LimitType (Boundary i t)
LtBoundary Int
0
  {-# Inline zeroBound' #-}
  totalSize :: LimitType (Boundary i t) -> [Integer]
totalSize (LtBoundary n) = [Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n]
  {-# Inline totalSize #-}
  fromLinearIndex :: LimitType (Boundary i t) -> Int -> Boundary i t
fromLinearIndex LimitType (Boundary i t)
_ = Int -> Boundary i t
forall k k (boundaryType :: k) (ioc :: k).
Int -> Boundary boundaryType ioc
Boundary
  {-# Inline fromLinearIndex #-}
  showBound :: LimitType (Boundary i t) -> [String]
showBound (LtBoundary b) = [String
"LtBoundary " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
b]
  showIndex :: Boundary i t -> [String]
showIndex (Boundary Int
b) = [String
"Boundary " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
b]

instance IndexStream z ⇒ IndexStream (z:.Boundary k I) where
  streamUp :: LimitType (z :. Boundary k I)
-> LimitType (z :. Boundary k I) -> Stream m (z :. Boundary k I)
streamUp   (ls:..LtBoundary l) (hs:..LtBoundary h) = (z -> m (z, Int))
-> ((z, Int) -> m (Step (z, Int) (z :. Boundary k I)))
-> Stream m z
-> Stream m (z :. Boundary k I)
forall (m :: * -> *) a s b.
Monad m =>
(a -> m s) -> (s -> m (Step s b)) -> Stream m a -> Stream m b
SM.flatten (Int -> Int -> z -> m (z, Int)
forall (m :: * -> *) b p a. Monad m => b -> p -> a -> m (a, b)
streamUpBndMk   Int
l Int
h) (Int -> Int -> (z, Int) -> m (Step (z, Int) (z :. Boundary k I))
forall k k (m :: * -> *) p a (boundaryType :: k) (ioc :: k).
Monad m =>
p
-> Int
-> (a, Int)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
streamUpBndStep   Int
l Int
h) (Stream m z -> Stream m (z :. Boundary k I))
-> Stream m z -> Stream m (z :. Boundary k I)
forall a b. (a -> b) -> a -> b
$ LimitType z -> LimitType z -> Stream m z
forall i (m :: * -> *).
(IndexStream i, Monad m) =>
LimitType i -> LimitType i -> Stream m i
streamUp   LimitType z
ls LimitType z
hs
  streamDown :: LimitType (z :. Boundary k I)
-> LimitType (z :. Boundary k I) -> Stream m (z :. Boundary k I)
streamDown (ls:..LtBoundary l) (hs:..LtBoundary h) = (z -> m (z, Int))
-> ((z, Int) -> m (Step (z, Int) (z :. Boundary k I)))
-> Stream m z
-> Stream m (z :. Boundary k I)
forall (m :: * -> *) a s b.
Monad m =>
(a -> m s) -> (s -> m (Step s b)) -> Stream m a -> Stream m b
SM.flatten (Int -> Int -> z -> m (z, Int)
forall (m :: * -> *) p b a. Monad m => p -> b -> a -> m (a, b)
streamDownBndMk Int
l Int
h) (Int -> Int -> (z, Int) -> m (Step (z, Int) (z :. Boundary k I))
forall k k (m :: * -> *) p a (boundaryType :: k) (ioc :: k).
Monad m =>
Int
-> p
-> (a, Int)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
streamDownBndStep Int
l Int
h) (Stream m z -> Stream m (z :. Boundary k I))
-> Stream m z -> Stream m (z :. Boundary k I)
forall a b. (a -> b) -> a -> b
$ LimitType z -> LimitType z -> Stream m z
forall i (m :: * -> *).
(IndexStream i, Monad m) =>
LimitType i -> LimitType i -> Stream m i
streamDown LimitType z
ls LimitType z
hs
  {-# Inline streamUp   #-}
  {-# Inline streamDown #-}

instance IndexStream (Z:.Boundary k I) ⇒ IndexStream (Boundary k I) where
  streamUp :: LimitType (Boundary k I)
-> LimitType (Boundary k I) -> Stream m (Boundary k I)
streamUp LimitType (Boundary k I)
l LimitType (Boundary k I)
h = ((Z :. Boundary k I) -> Boundary k I)
-> Stream m (Z :. Boundary k I) -> Stream m (Boundary k I)
forall (m :: * -> *) a b.
Monad m =>
(a -> b) -> Stream m a -> Stream m b
SM.map (\(Z
Z:.Boundary k I
i) -> Boundary k I
i) (Stream m (Z :. Boundary k I) -> Stream m (Boundary k I))
-> Stream m (Z :. Boundary k I) -> Stream m (Boundary k I)
forall a b. (a -> b) -> a -> b
$ LimitType (Z :. Boundary k I)
-> LimitType (Z :. Boundary k I) -> Stream m (Z :. Boundary k I)
forall i (m :: * -> *).
(IndexStream i, Monad m) =>
LimitType i -> LimitType i -> Stream m i
streamUp (LimitType Z
ZZLimitType Z
-> LimitType (Boundary k I) -> LimitType (Z :. Boundary k I)
forall zs z. LimitType zs -> LimitType z -> LimitType (zs :. z)
:..LimitType (Boundary k I)
l) (LimitType Z
ZZLimitType Z
-> LimitType (Boundary k I) -> LimitType (Z :. Boundary k I)
forall zs z. LimitType zs -> LimitType z -> LimitType (zs :. z)
:..LimitType (Boundary k I)
h)
  {-# Inline streamUp #-}
  streamDown :: LimitType (Boundary k I)
-> LimitType (Boundary k I) -> Stream m (Boundary k I)
streamDown LimitType (Boundary k I)
l LimitType (Boundary k I)
h = ((Z :. Boundary k I) -> Boundary k I)
-> Stream m (Z :. Boundary k I) -> Stream m (Boundary k I)
forall (m :: * -> *) a b.
Monad m =>
(a -> b) -> Stream m a -> Stream m b
SM.map (\(Z
Z:.Boundary k I
i) -> Boundary k I
i) (Stream m (Z :. Boundary k I) -> Stream m (Boundary k I))
-> Stream m (Z :. Boundary k I) -> Stream m (Boundary k I)
forall a b. (a -> b) -> a -> b
$ LimitType (Z :. Boundary k I)
-> LimitType (Z :. Boundary k I) -> Stream m (Z :. Boundary k I)
forall i (m :: * -> *).
(IndexStream i, Monad m) =>
LimitType i -> LimitType i -> Stream m i
streamDown (LimitType Z
ZZLimitType Z
-> LimitType (Boundary k I) -> LimitType (Z :. Boundary k I)
forall zs z. LimitType zs -> LimitType z -> LimitType (zs :. z)
:..LimitType (Boundary k I)
l) (LimitType Z
ZZLimitType Z
-> LimitType (Boundary k I) -> LimitType (Z :. Boundary k I)
forall zs z. LimitType zs -> LimitType z -> LimitType (zs :. z)
:..LimitType (Boundary k I)
h)
  {-# Inline streamDown #-}

streamUpBndMk :: b -> p -> a -> m (a, b)
streamUpBndMk b
l p
h a
z = (a, b) -> m (a, b)
forall (m :: * -> *) a. Monad m => a -> m a
return (a
z, b
l)
{-# Inline [0] streamUpBndMk #-}

streamUpBndStep :: p
-> Int
-> (a, Int)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
streamUpBndStep p
l Int
h (a
z , Int
k)
  | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
h     = Step (a, Int) (a :. Boundary boundaryType ioc)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (a, Int) (a :. Boundary boundaryType ioc)
 -> m (Step (a, Int) (a :. Boundary boundaryType ioc)))
-> Step (a, Int) (a :. Boundary boundaryType ioc)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
forall a b. (a -> b) -> a -> b
$ Step (a, Int) (a :. Boundary boundaryType ioc)
forall s a. Step s a
SM.Done
  | Bool
otherwise = Step (a, Int) (a :. Boundary boundaryType ioc)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (a, Int) (a :. Boundary boundaryType ioc)
 -> m (Step (a, Int) (a :. Boundary boundaryType ioc)))
-> Step (a, Int) (a :. Boundary boundaryType ioc)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
forall a b. (a -> b) -> a -> b
$ (a :. Boundary boundaryType ioc)
-> (a, Int) -> Step (a, Int) (a :. Boundary boundaryType ioc)
forall a s. a -> s -> Step s a
SM.Yield (a
za -> Boundary boundaryType ioc -> a :. Boundary boundaryType ioc
forall a b. a -> b -> a :. b
:.Int -> Boundary boundaryType ioc
forall k k (boundaryType :: k) (ioc :: k).
Int -> Boundary boundaryType ioc
Boundary Int
k) (a
z, Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
{-# Inline [0] streamUpBndStep #-}

streamDownBndMk :: p -> b -> a -> m (a, b)
streamDownBndMk p
l b
h a
z = (a, b) -> m (a, b)
forall (m :: * -> *) a. Monad m => a -> m a
return (a
z, b
h)
{-# Inline [0] streamDownBndMk #-}

streamDownBndStep :: Int
-> p
-> (a, Int)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
streamDownBndStep Int
l p
h (a
z , Int
k)
  | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
l     = Step (a, Int) (a :. Boundary boundaryType ioc)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (a, Int) (a :. Boundary boundaryType ioc)
 -> m (Step (a, Int) (a :. Boundary boundaryType ioc)))
-> Step (a, Int) (a :. Boundary boundaryType ioc)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
forall a b. (a -> b) -> a -> b
$ Step (a, Int) (a :. Boundary boundaryType ioc)
forall s a. Step s a
SM.Done
  | Bool
otherwise = Step (a, Int) (a :. Boundary boundaryType ioc)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (a, Int) (a :. Boundary boundaryType ioc)
 -> m (Step (a, Int) (a :. Boundary boundaryType ioc)))
-> Step (a, Int) (a :. Boundary boundaryType ioc)
-> m (Step (a, Int) (a :. Boundary boundaryType ioc))
forall a b. (a -> b) -> a -> b
$ (a :. Boundary boundaryType ioc)
-> (a, Int) -> Step (a, Int) (a :. Boundary boundaryType ioc)
forall a s. a -> s -> Step s a
SM.Yield (a
za -> Boundary boundaryType ioc -> a :. Boundary boundaryType ioc
forall a b. a -> b -> a :. b
:.Int -> Boundary boundaryType ioc
forall k k (boundaryType :: k) (ioc :: k).
Int -> Boundary boundaryType ioc
Boundary Int
k) (a
z,Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
{-# Inline [0] streamDownBndStep #-}

-- | Declare the interface to be the start of a path.

data First

-- | Declare the interface to be the end of a path.

data Last

-- | Declare the interface to match anything.
--
-- TODO needed? want to use later in ADPfusion

data Any



-- * Moving indices within sets.

-- | Successor and Predecessor for sets. Designed as a class to accomodate
-- sets with interfaces and without interfaces with one function.
--
-- The functions are not written recursively, as we currently only have
-- three cases, and we do not want to "reset" while generating successors
-- and predecessors.
--
-- Note that sets have a partial order. Within the group of element with
-- the same @popCount@, we use @popPermutation@ which has the same stepping
-- order for both, @setSucc@ and @setPred@.

class SetPredSucc s where
  -- | Set successor. The first argument is the lower set limit, the second
  -- the upper set limit, the third the current set.
  setSucc ∷ Int → Int → s → Maybe s
  -- | Set predecessor. The first argument is the lower set limit, the
  -- second the upper set limit, the third the current set.
  setPred ∷ Int → Int → s → Maybe s

-- | Masks are used quite often for different types of bitsets. We liberate
-- them as a type family.

type family Mask s ∷ *

-- | @Fixed@ allows us to fix some or all bits of a bitset, thereby
-- providing @succ/pred@ operations which are only partially free.
--
-- @f = getFixedMask .&. getFixed@ are the fixed bits.
-- @n = getFixed .&. complement getFixedMask@ are the free bits.
-- @to = complement getFixed@ is the to move mask
-- @n' = popShiftR to n@ yields the population after the move
-- @p = popPermutation undefined n'@ yields the new population permutation
-- @p' = popShiftL to p@ yields the population moved back
-- @final = p' .|. f@

data FixedMask t = FixedMask { FixedMask t -> Mask t
getMask ∷ (Mask t) , FixedMask t -> t
getFixed ∷ !t }

-- | Assuming a bitset on bits @[0 .. highbit]@, we can apply a mask that
-- stretches out those bits over @[0 .. higherBit]@ with @highbit <=
-- higherBit@. Any active interfaces are correctly set as well.

class ApplyMask s where
  applyMask :: Mask s → s → s



-- | for 'Test.QuickCheck.Arbitrary'

arbitraryBitSetMax ∷ Int
arbitraryBitSetMax :: Int
arbitraryBitSetMax = Int
6