Data.PrimitiveArray.Index.Set

Set with and without interfaces. We provide instances for sets, and sets with one or two interfaces. The First and Last annotation is purely cosmetical (apart from introducing type safety).

newtypes, data types, classes.

newtype Interface t

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.

Constructors

Iter

Fields

getIter :: Int

Instances

Vector Vector (Interface t)

MVector MVector (Interface t)

Eq (Interface t)

Num (Interface t)

Ord (Interface t)

Show (Interface t)

Generic (Interface t)

ToJSON (Interface t)

FromJSON (Interface t)

Binary (Interface t)

Serialize (Interface t)

NFData (Interface t)

Hashable (Interface t)

Unbox (Interface t)

Index (Interface i)

data MVector s0 (Interface t0) = MV_Interface (MVector s Int)

type Rep (Interface t)

data Vector (Interface t0) = V_Interface (Vector Int)

data First

Declare the interface to be the start of a path.

data Last

Declare the interface to be the end of a path.

data Any

Declare the interface to match anything.

TODO needed? want to use later in ADPfusion

newtype BitSet t

Newtype for a bitset. We'd use Words but that requires more shape instances.

TODO can we use Words now?

Constructors

BitSet

Fields

getBitSet :: Int

Instances

Vector Vector (BitSet t)

MVector MVector (BitSet t)

Eq (BitSet t)

Num (BitSet t)

Ord (BitSet t)

Read (BitSet t)

Show (BitSet t)

Generic (BitSet t)

Arbitrary (BitSet t)

ToJSON (BitSet t)

FromJSON (BitSet t)

Bits (BitSet t)

FiniteBits (BitSet t)

Binary (BitSet t)

Ranked (BitSet t)

Serialize (BitSet t)

NFData (BitSet t)

Hashable (BitSet t)

Unbox (BitSet t)

IndexStream ((:.) Z (BitSet t)) => IndexStream (BitSet t)

Index (BitSet t)

ApplyMask (BitSet t)

SetPredSucc (Fixed (BitSet t))

SetPredSucc (BitSet t)

IndexStream z => IndexStream ((:.) z (BitSet C))

IndexStream z => IndexStream ((:.) z (BitSet O))

IndexStream z => IndexStream ((:.) z (BitSet I))

data MVector s0 (BitSet t0) = MV_BitSet (MVector s Int)

type Rep (BitSet t)

data Vector (BitSet t0) = V_BitSet (Vector Int)

type Mask (BitSet t) = BitSet t

bitSetI :: Int -> BitSet I

bitSetO :: Int -> BitSet O

bitSetC :: Int -> BitSet C

data BS1 i t

A bitset with one interface.

Constructors

BS1 !(BitSet t) !(Interface i)

Instances

SetPredSucc (Fixed (BS1 i t))

Show (BS1 i t)

Arbitrary (BS1 i t)

IndexStream z => IndexStream ((:.) z (BS1 i C))

IndexStream z => IndexStream ((:.) z (BS1 i O))

IndexStream z => IndexStream ((:.) z (BS1 i I))

IndexStream ((:.) Z (BS1 i t)) => IndexStream (BS1 i t)

Index (BS1 i t)

ApplyMask (BS1 i t)

SetPredSucc (BS1 i t)

type Mask (BS1 i t) = BitSet t

data BS2 i j t

A bitset with two interfaces.

Constructors

BS2 !(BitSet t) !(Interface i) !(Interface j)

Instances

SetPredSucc (Fixed (BS2 i j t))

IndexStream z => IndexStream ((:.) z (BS2 i j C))

IndexStream z => IndexStream ((:.) z (BS2 i j O))

IndexStream z => IndexStream ((:.) z (BS2 i j I))

Show (BS2 i j t)

Arbitrary (BS2 i j t)

IndexStream ((:.) Z (BS2 i j t)) => IndexStream (BS2 i j t)

Index (BS2 i j t)

ApplyMask (BS2 i j t)

SetPredSucc (BS2 i j t)

type Mask (BS2 i j t) = BitSet t

class SetPredSucc s where

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.

Methods

setSucc :: s -> s -> s -> Maybe s

Set successor. The first argument is the lower set limit, the second the upper set limit, the third the current set.

setPred :: s -> s -> s -> Maybe s

Set predecessor. The first argument is the lower set limit, the second the upper set limit, the third the current set.

Instances

SetPredSucc (Fixed (BS2 i j t))

SetPredSucc (Fixed (BS1 i t))

SetPredSucc (Fixed (BitSet t))

SetPredSucc (BitSet t)

SetPredSucc (BS1 i t)

SetPredSucc (BS2 i j t)

type family Mask s :: *

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

Instances

type Mask (BitSet t) = BitSet t

type Mask (BS1 i t) = BitSet t

type Mask (BS2 i j t) = BitSet t

data Fixed t

Fixed allows us to fix some or all bits of a bitset, thereby providing succ/pred operations which are only partially free.

The mask is lazy, this allows us to have undefined for l and h.

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

Constructors

Fixed

Fields

getFixedMask :: Mask t

getFixed :: !t

Instances

(Unbox t0, Unbox (Mask t0)) => Vector Vector (Fixed t)

(Unbox t0, Unbox (Mask t0)) => MVector MVector (Fixed t)

(Eq t, Eq (Mask t)) => Eq (Fixed t)

(Ord t, Ord (Mask t)) => Ord (Fixed t)

(Read t, Read (Mask t)) => Read (Fixed t)

(Show t, Show (Mask t)) => Show (Fixed t)

(Generic t, Generic (Mask t)) => Generic (Fixed t)

(Arbitrary t, Arbitrary (Mask t)) => Arbitrary (Fixed t)

(Generic t, Generic (Mask t), Binary t, Binary (Mask t)) => Binary (Fixed t)

(Generic t, Generic (Mask t), Serialize t, Serialize (Mask t)) => Serialize (Fixed t)

NFData (Fixed t)

(Generic t, Generic (Mask t), Hashable t, Hashable (Mask t)) => Hashable (Fixed t)

(Unbox t0, Unbox (Mask t0)) => Unbox (Fixed t)

SetPredSucc (Fixed (BS2 i j t))

SetPredSucc (Fixed (BS1 i t))

SetPredSucc (Fixed (BitSet t))

data MVector s0 (Fixed t0) = MV_Fixed (MVector s (Mask t, t))

type Rep (Fixed t)

data Vector (Fixed t0) = V_Fixed (Vector (Mask t, t))

class ApplyMask s where

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.

Methods

applyMask :: Mask s -> s -> s

Instances

ApplyMask (BitSet t)

ApplyMask (BS1 i t)

ApplyMask (BS2 i j t)

Instances

streamUpBsMk :: (Monad m, Ord a) => a -> a -> t -> m (t, Maybe a)

streamUpBsStep :: (Monad m, SetPredSucc s) => s -> s -> (t, Maybe s) -> m (Step (t, Maybe s) (t :. s))

streamDownBsMk :: (Monad m, Ord a) => a -> a -> t -> m (t, Maybe a)

streamDownBsStep :: (Monad m, SetPredSucc s) => s -> s -> (t, Maybe s) -> m (Step (t, Maybe s) (t :. s))

BS1

streamUpBsIMk :: Monad m => BS1 a i -> BS1 b i -> z -> m (z, Maybe (BS1 c i))

streamUpBsIStep :: (Monad m, SetPredSucc s) => s -> s -> (t, Maybe s) -> m (Step (t, Maybe s) (t :. s))

streamDownBsIMk :: Monad m => BS1 a i -> BS1 b i -> z -> m (z, Maybe (BS1 c i))

streamDownBsIStep :: (Monad m, SetPredSucc s) => s -> s -> (t, Maybe s) -> m (Step (t, Maybe s) (t :. s))

BS2

streamUpBsIiMk :: Monad m => BS2 a b i -> BS2 c d i -> z -> m (z, Maybe (BS2 e f i))

streamUpBsIiStep :: (Monad m, SetPredSucc s) => s -> s -> (t, Maybe s) -> m (Step (t, Maybe s) (t :. s))

streamDownBsIiMk :: Monad m => BS2 a b i -> BS2 c d i -> z -> m (z, Maybe (BS2 e f i))

streamDownBsIiStep :: (Monad m, SetPredSucc s) => s -> s -> (t, Maybe s) -> m (Step (t, Maybe s) (t :. s))

Set predecessor and successor

testBsS :: BitSet t -> Maybe (Fixed (BitSet t))

arbitraryBitSetMax :: Integer