-- |
-- Module      : Foundation.Array.Bitmap
-- License     : BSD-style
-- Maintainer  : Vincent Hanquez <vincent@snarc.org>
-- Stability   : experimental
-- Portability : portable
--
-- A simple abstraction to a set of Bits (Bitmap)
--
-- Largely a placeholder for a more performant implementation,
-- most operation goes through the List representation (e.g. [Bool])
-- to conduct even the most trivial operation, leading to a lots of
-- unnecessary churn.
--
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveDataTypeable #-}
module Foundation.Array.Bitmap
    ( Bitmap
    , MutableBitmap
    , empty
    , append
    , concat
    , unsafeIndex
    , index
    , read
    , unsafeRead
    , write
    , unsafeWrite
    , snoc
    , cons
    ) where

import           Basement.UArray (UArray)
import qualified Basement.UArray as A
import           Basement.UArray.Mutable (MUArray)
import           Basement.Compat.Bifunctor (first, second, bimap)
import           Basement.Compat.Semigroup
import           Basement.Exception
import           Basement.Compat.Base
import           Basement.Types.OffsetSize
import           Basement.Monad

import qualified Foundation.Collection as C
import           Foundation.Numerical
import           Data.Bits hiding ((.<<.), (.>>.))
import           Foundation.Bits
import           GHC.ST
import qualified Data.List

data Bitmap = Bitmap (CountOf Bool) (UArray Word32)
    deriving (Typeable)

data MutableBitmap st = MutableBitmap (CountOf Bool) (MUArray Word32 st)

bitsPerTy :: Int
bitsPerTy :: Int
bitsPerTy = Int
32

shiftPerTy :: Int
shiftPerTy :: Int
shiftPerTy = Int
5

maskPerTy :: Int
maskPerTy :: Int
maskPerTy = Int
0x1f

instance Show Bitmap where
    show :: Bitmap -> String
show Bitmap
v = [Bool] -> String
forall a. Show a => a -> String
show (Bitmap -> [Item Bitmap]
forall l. IsList l => l -> [Item l]
toList Bitmap
v)
instance Eq Bitmap where
    == :: Bitmap -> Bitmap -> Bool
(==) = Bitmap -> Bitmap -> Bool
equal
instance Ord Bitmap where
    compare :: Bitmap -> Bitmap -> Ordering
compare = Bitmap -> Bitmap -> Ordering
vCompare
instance Semigroup Bitmap where
    <> :: Bitmap -> Bitmap -> Bitmap
(<>) = Bitmap -> Bitmap -> Bitmap
append
instance Monoid Bitmap where
    mempty :: Bitmap
mempty  = Bitmap
empty
    mconcat :: [Bitmap] -> Bitmap
mconcat = [Bitmap] -> Bitmap
concat

type instance C.Element Bitmap = Bool

instance IsList Bitmap where
    type Item Bitmap = Bool
    fromList :: [Item Bitmap] -> Bitmap
fromList = [Bool] -> Bitmap
[Item Bitmap] -> Bitmap
vFromList
    toList :: Bitmap -> [Item Bitmap]
toList = Bitmap -> [Bool]
Bitmap -> [Item Bitmap]
vToList

instance C.InnerFunctor Bitmap where
    imap :: (Element Bitmap -> Element Bitmap) -> Bitmap -> Bitmap
imap = (Bool -> Bool) -> Bitmap -> Bitmap
(Element Bitmap -> Element Bitmap) -> Bitmap -> Bitmap
map

instance C.Foldable Bitmap where
    foldr :: (Element Bitmap -> a -> a) -> a -> Bitmap -> a
foldr = (Element Bitmap -> a -> a) -> a -> Bitmap -> a
forall a. (Bool -> a -> a) -> a -> Bitmap -> a
foldr
    foldl' :: (a -> Element Bitmap -> a) -> a -> Bitmap -> a
foldl' = (a -> Element Bitmap -> a) -> a -> Bitmap -> a
forall a. (a -> Bool -> a) -> a -> Bitmap -> a
foldl'
    foldr' :: (Element Bitmap -> a -> a) -> a -> Bitmap -> a
foldr' = (Element Bitmap -> a -> a) -> a -> Bitmap -> a
forall a. (Bool -> a -> a) -> a -> Bitmap -> a
foldr'

instance C.Collection Bitmap where
    null :: Bitmap -> Bool
null = Bitmap -> Bool
null
    length :: Bitmap -> CountOf (Element Bitmap)
length = Bitmap -> CountOf Bool
Bitmap -> CountOf (Element Bitmap)
length
    elem :: Element Bitmap -> Bitmap -> Bool
elem Element Bitmap
e = Bool -> [Bool] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
Data.List.elem Bool
Element Bitmap
e ([Bool] -> Bool) -> (Bitmap -> [Bool]) -> Bitmap -> Bool
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Bitmap -> [Bool]
forall l. IsList l => l -> [Item l]
toList
    maximum :: NonEmpty Bitmap -> Element Bitmap
maximum = (Bool -> Bool) -> Bitmap -> Bool
any Bool -> Bool
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id (Bitmap -> Bool)
-> (NonEmpty Bitmap -> Bitmap) -> NonEmpty Bitmap -> Bool
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. NonEmpty Bitmap -> Bitmap
forall a. NonEmpty a -> a
C.getNonEmpty
    minimum :: NonEmpty Bitmap -> Element Bitmap
minimum = (Bool -> Bool) -> Bitmap -> Bool
all Bool -> Bool
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id (Bitmap -> Bool)
-> (NonEmpty Bitmap -> Bitmap) -> NonEmpty Bitmap -> Bool
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. NonEmpty Bitmap -> Bitmap
forall a. NonEmpty a -> a
C.getNonEmpty
    all :: (Element Bitmap -> Bool) -> Bitmap -> Bool
all = (Bool -> Bool) -> Bitmap -> Bool
(Element Bitmap -> Bool) -> Bitmap -> Bool
all
    any :: (Element Bitmap -> Bool) -> Bitmap -> Bool
any = (Bool -> Bool) -> Bitmap -> Bool
(Element Bitmap -> Bool) -> Bitmap -> Bool
any

instance C.Sequential Bitmap where
    take :: CountOf (Element Bitmap) -> Bitmap -> Bitmap
take = CountOf Bool -> Bitmap -> Bitmap
CountOf (Element Bitmap) -> Bitmap -> Bitmap
take
    drop :: CountOf (Element Bitmap) -> Bitmap -> Bitmap
drop = CountOf Bool -> Bitmap -> Bitmap
CountOf (Element Bitmap) -> Bitmap -> Bitmap
drop
    splitAt :: CountOf (Element Bitmap) -> Bitmap -> (Bitmap, Bitmap)
splitAt = CountOf Bool -> Bitmap -> (Bitmap, Bitmap)
CountOf (Element Bitmap) -> Bitmap -> (Bitmap, Bitmap)
splitAt
    revTake :: CountOf (Element Bitmap) -> Bitmap -> Bitmap
revTake CountOf (Element Bitmap)
n = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (CountOf (Element [Bool]) -> [Bool] -> [Bool]
forall c. Sequential c => CountOf (Element c) -> c -> c
C.revTake CountOf (Element [Bool])
CountOf (Element Bitmap)
n)
    revDrop :: CountOf (Element Bitmap) -> Bitmap -> Bitmap
revDrop CountOf (Element Bitmap)
n = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (CountOf (Element [Bool]) -> [Bool] -> [Bool]
forall c. Sequential c => CountOf (Element c) -> c -> c
C.revDrop CountOf (Element [Bool])
CountOf (Element Bitmap)
n)
    splitOn :: (Element Bitmap -> Bool) -> Bitmap -> [Bitmap]
splitOn = (Bool -> Bool) -> Bitmap -> [Bitmap]
(Element Bitmap -> Bool) -> Bitmap -> [Bitmap]
splitOn
    break :: (Element Bitmap -> Bool) -> Bitmap -> (Bitmap, Bitmap)
break = (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
(Element Bitmap -> Bool) -> Bitmap -> (Bitmap, Bitmap)
break
    breakEnd :: (Element Bitmap -> Bool) -> Bitmap -> (Bitmap, Bitmap)
breakEnd = (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
(Element Bitmap -> Bool) -> Bitmap -> (Bitmap, Bitmap)
breakEnd
    span :: (Element Bitmap -> Bool) -> Bitmap -> (Bitmap, Bitmap)
span = (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
(Element Bitmap -> Bool) -> Bitmap -> (Bitmap, Bitmap)
span
    filter :: (Element Bitmap -> Bool) -> Bitmap -> Bitmap
filter = (Bool -> Bool) -> Bitmap -> Bitmap
(Element Bitmap -> Bool) -> Bitmap -> Bitmap
filter
    reverse :: Bitmap -> Bitmap
reverse = Bitmap -> Bitmap
reverse
    snoc :: Bitmap -> Element Bitmap -> Bitmap
snoc = Bitmap -> Bool -> Bitmap
Bitmap -> Element Bitmap -> Bitmap
snoc
    cons :: Element Bitmap -> Bitmap -> Bitmap
cons = Bool -> Bitmap -> Bitmap
Element Bitmap -> Bitmap -> Bitmap
cons
    unsnoc :: Bitmap -> Maybe (Bitmap, Element Bitmap)
unsnoc = Bitmap -> Maybe (Bitmap, Bool)
Bitmap -> Maybe (Bitmap, Element Bitmap)
unsnoc
    uncons :: Bitmap -> Maybe (Element Bitmap, Bitmap)
uncons = Bitmap -> Maybe (Bool, Bitmap)
Bitmap -> Maybe (Element Bitmap, Bitmap)
uncons
    intersperse :: Element Bitmap -> Bitmap -> Bitmap
intersperse = Bool -> Bitmap -> Bitmap
Element Bitmap -> Bitmap -> Bitmap
intersperse
    find :: (Element Bitmap -> Bool) -> Bitmap -> Maybe (Element Bitmap)
find = (Bool -> Bool) -> Bitmap -> Maybe Bool
(Element Bitmap -> Bool) -> Bitmap -> Maybe (Element Bitmap)
find
    sortBy :: (Element Bitmap -> Element Bitmap -> Ordering) -> Bitmap -> Bitmap
sortBy = (Bool -> Bool -> Ordering) -> Bitmap -> Bitmap
(Element Bitmap -> Element Bitmap -> Ordering) -> Bitmap -> Bitmap
sortBy
    singleton :: Element Bitmap -> Bitmap
singleton = [Bool] -> Bitmap
forall l. IsList l => [Item l] -> l
fromList ([Bool] -> Bitmap) -> (Bool -> [Bool]) -> Bool -> Bitmap
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Bool -> [Bool] -> [Bool]
forall a. a -> [a] -> [a]
:[])
    replicate :: CountOf (Element Bitmap) -> Element Bitmap -> Bitmap
replicate CountOf (Element Bitmap)
n = [Bool] -> Bitmap
forall l. IsList l => [Item l] -> l
fromList ([Bool] -> Bitmap) -> (Bool -> [Bool]) -> Bool -> Bitmap
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. CountOf (Element [Bool]) -> Element [Bool] -> [Bool]
forall c. Sequential c => CountOf (Element c) -> Element c -> c
C.replicate CountOf (Element [Bool])
CountOf (Element Bitmap)
n

instance C.IndexedCollection Bitmap where
    (!) Bitmap
l Offset (Element Bitmap)
n
        | Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset Bool
Offset (Element Bitmap)
n (Bitmap -> CountOf Bool
length Bitmap
l) = Maybe (Element Bitmap)
forall a. Maybe a
Nothing
        | Bool
otherwise                     = Bool -> Maybe Bool
forall a. a -> Maybe a
Just (Bool -> Maybe Bool) -> Bool -> Maybe Bool
forall a b. (a -> b) -> a -> b
$ Bitmap -> Offset Bool -> Bool
index Bitmap
l Offset Bool
Offset (Element Bitmap)
n
    findIndex :: (Element Bitmap -> Bool)
-> Bitmap -> Maybe (Offset (Element Bitmap))
findIndex Element Bitmap -> Bool
predicate Bitmap
c = Offset Bool -> Maybe (Offset Bool)
loop Offset Bool
0
      where
        !len :: CountOf Bool
len = Bitmap -> CountOf Bool
length Bitmap
c
        loop :: Offset Bool -> Maybe (Offset Bool)
loop Offset Bool
i
            | Offset Bool
i Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len                  = Maybe (Offset Bool)
forall a. Maybe a
Nothing
            | Element Bitmap -> Bool
predicate (Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
c Offset Bool
i) = Offset Bool -> Maybe (Offset Bool)
forall a. a -> Maybe a
Just Offset Bool
i
            | Bool
otherwise                   = Maybe (Offset Bool)
forall a. Maybe a
Nothing

instance C.MutableCollection MutableBitmap where
    type MutableFreezed MutableBitmap = Bitmap
    type MutableKey MutableBitmap = Offset Bool
    type MutableValue MutableBitmap = Bool

    thaw :: MutableFreezed MutableBitmap
-> prim (MutableBitmap (PrimState prim))
thaw = MutableFreezed MutableBitmap
-> prim (MutableBitmap (PrimState prim))
forall (prim :: * -> *).
PrimMonad prim =>
Bitmap -> prim (MutableBitmap (PrimState prim))
thaw
    freeze :: MutableBitmap (PrimState prim)
-> prim (MutableFreezed MutableBitmap)
freeze = MutableBitmap (PrimState prim)
-> prim (MutableFreezed MutableBitmap)
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> prim Bitmap
freeze
    unsafeThaw :: MutableFreezed MutableBitmap
-> prim (MutableBitmap (PrimState prim))
unsafeThaw = MutableFreezed MutableBitmap
-> prim (MutableBitmap (PrimState prim))
forall (prim :: * -> *).
PrimMonad prim =>
Bitmap -> prim (MutableBitmap (PrimState prim))
unsafeThaw
    unsafeFreeze :: MutableBitmap (PrimState prim)
-> prim (MutableFreezed MutableBitmap)
unsafeFreeze = MutableBitmap (PrimState prim)
-> prim (MutableFreezed MutableBitmap)
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> prim Bitmap
unsafeFreeze

    mutNew :: CountOf (MutableValue MutableBitmap)
-> prim (MutableBitmap (PrimState prim))
mutNew = CountOf (MutableValue MutableBitmap)
-> prim (MutableBitmap (PrimState prim))
forall (prim :: * -> *).
PrimMonad prim =>
CountOf Bool -> prim (MutableBitmap (PrimState prim))
new
    mutUnsafeWrite :: MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap
-> MutableValue MutableBitmap
-> prim ()
mutUnsafeWrite = MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap
-> MutableValue MutableBitmap
-> prim ()
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
unsafeWrite
    mutUnsafeRead :: MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap -> prim (MutableValue MutableBitmap)
mutUnsafeRead = MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap -> prim (MutableValue MutableBitmap)
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
unsafeRead
    mutWrite :: MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap
-> MutableValue MutableBitmap
-> prim ()
mutWrite = MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap
-> MutableValue MutableBitmap
-> prim ()
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
write
    mutRead :: MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap -> prim (MutableValue MutableBitmap)
mutRead = MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap -> prim (MutableValue MutableBitmap)
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
read



bitmapIndex :: Offset Bool -> (Offset Word32, Int)
bitmapIndex :: Offset Bool -> (Offset Word32, Int)
bitmapIndex (Offset !Int
i) = (Int -> Offset Word32
forall ty. Int -> Offset ty
Offset (Int
i Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
shiftPerTy), Int
i Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
maskPerTy)
{-# INLINE bitmapIndex #-}

-- return the index in word32 quantity and mask to a bit in a bitmap
{-
bitmapAddr :: Int -> (# Int , Word #)
bitmapAddr !i = (# idx, mask #)
  where (!idx, !bitIdx) = bitmapIndex i
        !mask = case bitIdx of
                    0  -> 0x1
                    1  -> 0x2
                    2  -> 0x4
                    3  -> 0x8
                    4  -> 0x10
                    5  -> 0x20
                    6  -> 0x40
                    7  -> 0x80
                    8  -> 0x100
                    9  -> 0x200
                    10 -> 0x400
                    11 -> 0x800
                    12 -> 0x1000
                    13 -> 0x2000
                    14 -> 0x4000
                    15 -> 0x8000
                    16 -> 0x10000
                    17 -> 0x20000
                    18 -> 0x40000
                    19 -> 0x80000
                    20 -> 0x100000
                    21 -> 0x200000
                    22 -> 0x400000
                    23 -> 0x800000
                    24 -> 0x1000000
                    25 -> 0x2000000
                    26 -> 0x4000000
                    27 -> 0x8000000
                    28 -> 0x10000000
                    29 -> 0x20000000
                    30 -> 0x40000000
                    _  -> 0x80000000
-}

thaw :: PrimMonad prim => Bitmap -> prim (MutableBitmap (PrimState prim))
thaw :: Bitmap -> prim (MutableBitmap (PrimState prim))
thaw (Bitmap CountOf Bool
len UArray Word32
ba) = CountOf Bool
-> MUArray Word32 (PrimState prim)
-> MutableBitmap (PrimState prim)
forall st. CountOf Bool -> MUArray Word32 st -> MutableBitmap st
MutableBitmap CountOf Bool
len (MUArray Word32 (PrimState prim) -> MutableBitmap (PrimState prim))
-> prim (MUArray Word32 (PrimState prim))
-> prim (MutableBitmap (PrimState prim))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` MutableFreezed (MUArray Word32)
-> prim (MUArray Word32 (PrimState prim))
forall (c :: * -> *) (prim :: * -> *).
(MutableCollection c, PrimMonad prim) =>
MutableFreezed c -> prim (c (PrimState prim))
C.thaw UArray Word32
MutableFreezed (MUArray Word32)
ba

freeze :: PrimMonad prim => MutableBitmap (PrimState prim) -> prim Bitmap
freeze :: MutableBitmap (PrimState prim) -> prim Bitmap
freeze (MutableBitmap CountOf Bool
len MUArray Word32 (PrimState prim)
mba) = CountOf Bool -> UArray Word32 -> Bitmap
Bitmap CountOf Bool
len (UArray Word32 -> Bitmap) -> prim (UArray Word32) -> prim Bitmap
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` MUArray Word32 (PrimState prim)
-> prim (MutableFreezed (MUArray Word32))
forall (c :: * -> *) (prim :: * -> *).
(MutableCollection c, PrimMonad prim) =>
c (PrimState prim) -> prim (MutableFreezed c)
C.freeze MUArray Word32 (PrimState prim)
mba

unsafeThaw :: PrimMonad prim => Bitmap -> prim (MutableBitmap (PrimState prim))
unsafeThaw :: Bitmap -> prim (MutableBitmap (PrimState prim))
unsafeThaw (Bitmap CountOf Bool
len UArray Word32
ba) = CountOf Bool
-> MUArray Word32 (PrimState prim)
-> MutableBitmap (PrimState prim)
forall st. CountOf Bool -> MUArray Word32 st -> MutableBitmap st
MutableBitmap CountOf Bool
len (MUArray Word32 (PrimState prim) -> MutableBitmap (PrimState prim))
-> prim (MUArray Word32 (PrimState prim))
-> prim (MutableBitmap (PrimState prim))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` MutableFreezed (MUArray Word32)
-> prim (MUArray Word32 (PrimState prim))
forall (c :: * -> *) (prim :: * -> *).
(MutableCollection c, PrimMonad prim) =>
MutableFreezed c -> prim (c (PrimState prim))
C.unsafeThaw UArray Word32
MutableFreezed (MUArray Word32)
ba

unsafeFreeze :: PrimMonad prim => MutableBitmap (PrimState prim) -> prim Bitmap
unsafeFreeze :: MutableBitmap (PrimState prim) -> prim Bitmap
unsafeFreeze (MutableBitmap CountOf Bool
len MUArray Word32 (PrimState prim)
mba) = CountOf Bool -> UArray Word32 -> Bitmap
Bitmap CountOf Bool
len (UArray Word32 -> Bitmap) -> prim (UArray Word32) -> prim Bitmap
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` MUArray Word32 (PrimState prim)
-> prim (MutableFreezed (MUArray Word32))
forall (c :: * -> *) (prim :: * -> *).
(MutableCollection c, PrimMonad prim) =>
c (PrimState prim) -> prim (MutableFreezed c)
C.unsafeFreeze MUArray Word32 (PrimState prim)
mba

unsafeWrite :: PrimMonad prim => MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
unsafeWrite :: MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
unsafeWrite (MutableBitmap CountOf Bool
_ MUArray Word32 (PrimState prim)
ma) Offset Bool
i Bool
v = do
    let (Offset Word32
idx, Int
bitIdx) = Offset Bool -> (Offset Word32, Int)
bitmapIndex Offset Bool
i
    Word32
w <- MUArray Word32 (PrimState prim) -> Offset Word32 -> prim Word32
forall (prim :: * -> *) ty.
(PrimMonad prim, PrimType ty) =>
MUArray ty (PrimState prim) -> Offset ty -> prim ty
A.unsafeRead MUArray Word32 (PrimState prim)
ma Offset Word32
idx
    let w' :: Word32
w' = if Bool
v then Word32 -> Int -> Word32
forall a. Bits a => a -> Int -> a
setBit Word32
w Int
bitIdx else Word32 -> Int -> Word32
forall a. Bits a => a -> Int -> a
clearBit Word32
w Int
bitIdx
    MUArray Word32 (PrimState prim)
-> Offset Word32 -> Word32 -> prim ()
forall (prim :: * -> *) ty.
(PrimMonad prim, PrimType ty) =>
MUArray ty (PrimState prim) -> Offset ty -> ty -> prim ()
A.unsafeWrite MUArray Word32 (PrimState prim)
ma Offset Word32
idx Word32
w'
{-# INLINE unsafeWrite #-}

unsafeRead :: PrimMonad prim => MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
unsafeRead :: MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
unsafeRead (MutableBitmap CountOf Bool
_ MUArray Word32 (PrimState prim)
ma) Offset Bool
i = do
    let (Offset Word32
idx, Int
bitIdx) = Offset Bool -> (Offset Word32, Int)
bitmapIndex Offset Bool
i
    (Word32 -> Int -> Bool) -> Int -> Word32 -> Bool
forall a b c. (a -> b -> c) -> b -> a -> c
flip Word32 -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Int
bitIdx (Word32 -> Bool) -> prim Word32 -> prim Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` MUArray Word32 (PrimState prim) -> Offset Word32 -> prim Word32
forall (prim :: * -> *) ty.
(PrimMonad prim, PrimType ty) =>
MUArray ty (PrimState prim) -> Offset ty -> prim ty
A.unsafeRead MUArray Word32 (PrimState prim)
ma Offset Word32
idx
{-# INLINE unsafeRead #-}

write :: PrimMonad prim => MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
write :: MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
write MutableBitmap (PrimState prim)
mb Offset Bool
n Bool
val
    | Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset Bool
n CountOf Bool
len = OutOfBoundOperation -> Offset Bool -> CountOf Bool -> prim ()
forall (prim :: * -> *) ty a.
PrimMonad prim =>
OutOfBoundOperation -> Offset ty -> CountOf ty -> prim a
primOutOfBound OutOfBoundOperation
OOB_Write Offset Bool
n CountOf Bool
len
    | Bool
otherwise          = MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
unsafeWrite MutableBitmap (PrimState prim)
mb Offset Bool
n Bool
val
  where
    len :: CountOf Bool
len = MutableBitmap (PrimState prim) -> CountOf Bool
forall st. MutableBitmap st -> CountOf Bool
mutableLength MutableBitmap (PrimState prim)
mb
{-# INLINE write #-}

read :: PrimMonad prim => MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
read :: MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
read MutableBitmap (PrimState prim)
mb Offset Bool
n
    | Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset Bool
n CountOf Bool
len = OutOfBoundOperation -> Offset Bool -> CountOf Bool -> prim Bool
forall (prim :: * -> *) ty a.
PrimMonad prim =>
OutOfBoundOperation -> Offset ty -> CountOf ty -> prim a
primOutOfBound OutOfBoundOperation
OOB_Read Offset Bool
n CountOf Bool
len
    | Bool
otherwise        = MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
unsafeRead MutableBitmap (PrimState prim)
mb Offset Bool
n
  where len :: CountOf Bool
len = MutableBitmap (PrimState prim) -> CountOf Bool
forall st. MutableBitmap st -> CountOf Bool
mutableLength MutableBitmap (PrimState prim)
mb
{-# INLINE read #-}

-- | Return the element at a specific index from a Bitmap.
--
-- If the index @n is out of bounds, an error is raised.
index :: Bitmap -> Offset Bool -> Bool
index :: Bitmap -> Offset Bool -> Bool
index Bitmap
bits Offset Bool
n
    | Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset Bool
n CountOf Bool
len = OutOfBoundOperation -> Offset Bool -> CountOf Bool -> Bool
forall ty a. OutOfBoundOperation -> Offset ty -> CountOf ty -> a
outOfBound OutOfBoundOperation
OOB_Index Offset Bool
n CountOf Bool
len
    | Bool
otherwise          = Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
bits Offset Bool
n
  where len :: CountOf Bool
len = Bitmap -> CountOf Bool
length Bitmap
bits
{-# INLINE index #-}

-- | Return the element at a specific index from an array without bounds checking.
--
-- Reading from invalid memory can return unpredictable and invalid values.
-- use 'index' if unsure.
unsafeIndex :: Bitmap -> Offset Bool -> Bool
unsafeIndex :: Bitmap -> Offset Bool -> Bool
unsafeIndex (Bitmap CountOf Bool
_ UArray Word32
ba) Offset Bool
n =
    let (Offset Word32
idx, Int
bitIdx) = Offset Bool -> (Offset Word32, Int)
bitmapIndex Offset Bool
n
     in Word32 -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit (UArray Word32 -> Offset Word32 -> Word32
forall ty. PrimType ty => UArray ty -> Offset ty -> ty
A.unsafeIndex UArray Word32
ba Offset Word32
idx) Int
bitIdx

{-# INLINE unsafeIndex #-}

-----------------------------------------------------------------------
-- higher level collection implementation
-----------------------------------------------------------------------
length :: Bitmap -> CountOf Bool
length :: Bitmap -> CountOf Bool
length (Bitmap CountOf Bool
sz UArray Word32
_) = CountOf Bool
sz

mutableLength :: MutableBitmap st -> CountOf Bool
mutableLength :: MutableBitmap st -> CountOf Bool
mutableLength (MutableBitmap CountOf Bool
sz MUArray Word32 st
_) = CountOf Bool
sz

empty :: Bitmap
empty :: Bitmap
empty = CountOf Bool -> UArray Word32 -> Bitmap
Bitmap CountOf Bool
0 UArray Word32
forall a. Monoid a => a
mempty

new :: PrimMonad prim => CountOf Bool -> prim (MutableBitmap (PrimState prim))
new :: CountOf Bool -> prim (MutableBitmap (PrimState prim))
new sz :: CountOf Bool
sz@(CountOf Int
len) =
    CountOf Bool
-> MUArray Word32 (PrimState prim)
-> MutableBitmap (PrimState prim)
forall st. CountOf Bool -> MUArray Word32 st -> MutableBitmap st
MutableBitmap CountOf Bool
sz (MUArray Word32 (PrimState prim) -> MutableBitmap (PrimState prim))
-> prim (MUArray Word32 (PrimState prim))
-> prim (MutableBitmap (PrimState prim))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> CountOf Word32 -> prim (MUArray Word32 (PrimState prim))
forall (prim :: * -> *) ty.
(PrimMonad prim, PrimType ty) =>
CountOf ty -> prim (MUArray ty (PrimState prim))
A.new CountOf Word32
nbElements
  where
    nbElements :: CountOf Word32
    nbElements :: CountOf Word32
nbElements = Int -> CountOf Word32
forall ty. Int -> CountOf ty
CountOf ((Int
len Int -> Int -> Int
`alignRoundUp` Int
bitsPerTy) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
shiftPerTy)

-- | make an array from a list of elements.
vFromList :: [Bool] -> Bitmap
vFromList :: [Bool] -> Bitmap
vFromList [Bool]
allBools = (forall s. ST s Bitmap) -> Bitmap
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s Bitmap) -> Bitmap)
-> (forall s. ST s Bitmap) -> Bitmap
forall a b. (a -> b) -> a -> b
$ do
    MutableBitmap s
mbitmap <- CountOf Bool -> ST s (MutableBitmap (PrimState (ST s)))
forall (prim :: * -> *).
PrimMonad prim =>
CountOf Bool -> prim (MutableBitmap (PrimState prim))
new CountOf Bool
CountOf (Element [Bool])
len
    MutableBitmap (PrimState (ST s))
-> Offset Bool -> [Bool] -> ST s Bitmap
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim)
-> Offset Bool -> [Bool] -> prim Bitmap
loop MutableBitmap s
MutableBitmap (PrimState (ST s))
mbitmap Offset Bool
0 [Bool]
allBools
  where
    loop :: MutableBitmap (PrimState prim)
-> Offset Bool -> [Bool] -> prim Bitmap
loop MutableBitmap (PrimState prim)
mb Offset Bool
_ []     = MutableBitmap (PrimState prim) -> prim Bitmap
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> prim Bitmap
unsafeFreeze MutableBitmap (PrimState prim)
mb
    loop MutableBitmap (PrimState prim)
mb Offset Bool
i (Bool
x:[Bool]
xs) = MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
unsafeWrite MutableBitmap (PrimState prim)
mb Offset Bool
i Bool
x prim () -> prim Bitmap -> prim Bitmap
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> MutableBitmap (PrimState prim)
-> Offset Bool -> [Bool] -> prim Bitmap
loop MutableBitmap (PrimState prim)
mb (Offset Bool
iOffset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+Offset Bool
1) [Bool]
xs

{-
    runST $ do
    mba <- A.new nbElements
    ba  <- loop mba (0 :: Int) allBools
    pure (Bitmap len ba)
  where
    loop mba _ [] = A.unsafeFreeze mba
    loop mba i l  = do
        let (l1, l2) = C.splitAt bitsPerTy l
            w = toPacked l1
        A.unsafeWrite mba i w
        loop mba (i+1) l2

    toPacked :: [Bool] -> Word32
    toPacked l =
        C.foldl' (.|.) 0 $ Prelude.zipWith (\b w -> if b then (1 `shiftL` w) else 0) l (C.reverse [0..31])
-}
    len :: CountOf (Element [Bool])
len        = [Bool] -> CountOf (Element [Bool])
forall c. Collection c => c -> CountOf (Element c)
C.length [Bool]
allBools

-- | transform an array to a list.
vToList :: Bitmap -> [Bool]
vToList :: Bitmap -> [Bool]
vToList Bitmap
a = Offset Bool -> [Bool]
loop Offset Bool
0
  where len :: CountOf Bool
len = Bitmap -> CountOf Bool
length Bitmap
a
        loop :: Offset Bool -> [Bool]
loop Offset Bool
i | Offset Bool
i Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len  = []
               | Bool
otherwise = Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
a Offset Bool
i Bool -> [Bool] -> [Bool]
forall a. a -> [a] -> [a]
: Offset Bool -> [Bool]
loop (Offset Bool
iOffset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+Offset Bool
1)

-- | Check if two vectors are identical
equal :: Bitmap -> Bitmap -> Bool
equal :: Bitmap -> Bitmap -> Bool
equal Bitmap
a Bitmap
b
    | CountOf Bool
la CountOf Bool -> CountOf Bool -> Bool
forall a. Eq a => a -> a -> Bool
/= CountOf Bool
lb  = Bool
False
    | Bool
otherwise = Offset Bool -> Bool
loop Offset Bool
0
  where
    !la :: CountOf Bool
la = Bitmap -> CountOf Bool
length Bitmap
a
    !lb :: CountOf Bool
lb = Bitmap -> CountOf Bool
length Bitmap
b
    loop :: Offset Bool -> Bool
loop Offset Bool
n | Offset Bool
n Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
la = Bool
True
           | Bool
otherwise = (Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
a Offset Bool
n Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
b Offset Bool
n) Bool -> Bool -> Bool
&& Offset Bool -> Bool
loop (Offset Bool
nOffset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+Offset Bool
1)

-- | Compare 2 vectors
vCompare :: Bitmap -> Bitmap -> Ordering
vCompare :: Bitmap -> Bitmap -> Ordering
vCompare Bitmap
a Bitmap
b = Offset Bool -> Ordering
loop Offset Bool
0
  where
    !la :: CountOf Bool
la = Bitmap -> CountOf Bool
length Bitmap
a
    !lb :: CountOf Bool
lb = Bitmap -> CountOf Bool
length Bitmap
b
    loop :: Offset Bool -> Ordering
loop Offset Bool
n
        | Offset Bool
n Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
la = if CountOf Bool
la CountOf Bool -> CountOf Bool -> Bool
forall a. Eq a => a -> a -> Bool
== CountOf Bool
lb then Ordering
EQ else Ordering
LT
        | Offset Bool
n Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
lb = Ordering
GT
        | Bool
otherwise =
            case Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
a Offset Bool
n Bool -> Bool -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
b Offset Bool
n of
                Ordering
EQ -> Offset Bool -> Ordering
loop (Offset Bool
nOffset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+Offset Bool
1)
                Ordering
r  -> Ordering
r

-- | Append 2 arrays together by creating a new bigger array
--
-- TODO completely non optimized
append :: Bitmap -> Bitmap -> Bitmap
append :: Bitmap -> Bitmap -> Bitmap
append Bitmap
a Bitmap
b = [Item Bitmap] -> Bitmap
forall l. IsList l => [Item l] -> l
fromList ([Item Bitmap] -> Bitmap) -> [Item Bitmap] -> Bitmap
forall a b. (a -> b) -> a -> b
$ Bitmap -> [Item Bitmap]
forall l. IsList l => l -> [Item l]
toList Bitmap
a [Bool] -> [Bool] -> [Bool]
forall a. Monoid a => a -> a -> a
`mappend` Bitmap -> [Item Bitmap]
forall l. IsList l => l -> [Item l]
toList Bitmap
b

-- TODO completely non optimized
concat :: [Bitmap] -> Bitmap
concat :: [Bitmap] -> Bitmap
concat [Bitmap]
l = [Item Bitmap] -> Bitmap
forall l. IsList l => [Item l] -> l
fromList ([Item Bitmap] -> Bitmap) -> [Item Bitmap] -> Bitmap
forall a b. (a -> b) -> a -> b
$ [[Bool]] -> [Bool]
forall a. Monoid a => [a] -> a
mconcat ([[Bool]] -> [Bool]) -> [[Bool]] -> [Bool]
forall a b. (a -> b) -> a -> b
$ (Bitmap -> [Bool]) -> [Bitmap] -> [[Bool]]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Bitmap -> [Bool]
forall l. IsList l => l -> [Item l]
toList [Bitmap]
l

null :: Bitmap -> Bool
null :: Bitmap -> Bool
null (Bitmap CountOf Bool
nbBits UArray Word32
_) = CountOf Bool
nbBits CountOf Bool -> CountOf Bool -> Bool
forall a. Eq a => a -> a -> Bool
== CountOf Bool
0

take :: CountOf Bool -> Bitmap -> Bitmap
take :: CountOf Bool -> Bitmap -> Bitmap
take CountOf Bool
nbElems bits :: Bitmap
bits@(Bitmap CountOf Bool
nbBits UArray Word32
ba)
    | CountOf Bool
nbElems CountOf Bool -> CountOf Bool -> Bool
forall a. Ord a => a -> a -> Bool
<= CountOf Bool
0      = Bitmap
empty
    | CountOf Bool
nbElems CountOf Bool -> CountOf Bool -> Bool
forall a. Ord a => a -> a -> Bool
>= CountOf Bool
nbBits = Bitmap
bits
    | Bool
otherwise         = CountOf Bool -> UArray Word32 -> Bitmap
Bitmap CountOf Bool
nbElems UArray Word32
ba -- TODO : although it work right now, take on the underlaying ba too

drop :: CountOf Bool -> Bitmap -> Bitmap
drop :: CountOf Bool -> Bitmap -> Bitmap
drop CountOf Bool
nbElems bits :: Bitmap
bits@(Bitmap CountOf Bool
nbBits UArray Word32
_)
    | CountOf Bool
nbElems CountOf Bool -> CountOf Bool -> Bool
forall a. Ord a => a -> a -> Bool
<= CountOf Bool
0      = Bitmap
bits
    | CountOf Bool
nbElems CountOf Bool -> CountOf Bool -> Bool
forall a. Ord a => a -> a -> Bool
>= CountOf Bool
nbBits = Bitmap
empty
    | Bool
otherwise         = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (CountOf (Element [Bool]) -> [Bool] -> [Bool]
forall c. Sequential c => CountOf (Element c) -> c -> c
C.drop CountOf Bool
CountOf (Element [Bool])
nbElems) Bitmap
bits
        -- TODO: decide if we have drop easy by having a bit offset in the data structure
        -- or if we need to shift stuff around making all the indexing slighlty more complicated

splitAt :: CountOf Bool -> Bitmap -> (Bitmap, Bitmap)
splitAt :: CountOf Bool -> Bitmap -> (Bitmap, Bitmap)
splitAt CountOf Bool
n Bitmap
v = (CountOf Bool -> Bitmap -> Bitmap
take CountOf Bool
n Bitmap
v, CountOf Bool -> Bitmap -> Bitmap
drop CountOf Bool
n Bitmap
v)

-- unoptimised
splitOn :: (Bool -> Bool) -> Bitmap -> [Bitmap]
splitOn :: (Bool -> Bool) -> Bitmap -> [Bitmap]
splitOn Bool -> Bool
f Bitmap
bits = ([Bool] -> Bitmap) -> [[Bool]] -> [Bitmap]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [Bool] -> Bitmap
forall l. IsList l => [Item l] -> l
fromList ([[Bool]] -> [Bitmap]) -> [[Bool]] -> [Bitmap]
forall a b. (a -> b) -> a -> b
$ (Element [Bool] -> Bool) -> [Bool] -> [[Bool]]
forall c. Sequential c => (Element c -> Bool) -> c -> [c]
C.splitOn Bool -> Bool
Element [Bool] -> Bool
f ([Bool] -> [[Bool]]) -> [Bool] -> [[Bool]]
forall a b. (a -> b) -> a -> b
$ Bitmap -> [Item Bitmap]
forall l. IsList l => l -> [Item l]
toList Bitmap
bits

-- unoptimised
break :: (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
break :: (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
break Bool -> Bool
predicate Bitmap
v = Offset Bool -> (Bitmap, Bitmap)
findBreak Offset Bool
0
  where
    len :: CountOf Bool
len = Bitmap -> CountOf Bool
length Bitmap
v
    findBreak :: Offset Bool -> (Bitmap, Bitmap)
findBreak Offset Bool
i
        | Offset Bool
i Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = (Bitmap
v, Bitmap
empty)
        | Bool
otherwise  =
            if Bool -> Bool
predicate (Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
v Offset Bool
i)
                then CountOf Bool -> Bitmap -> (Bitmap, Bitmap)
splitAt (Offset Bool -> CountOf Bool
forall a. Offset a -> CountOf a
offsetAsSize Offset Bool
i) Bitmap
v
                else Offset Bool -> (Bitmap, Bitmap)
findBreak (Offset Bool
iOffset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+Offset Bool
1)

breakEnd :: (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
breakEnd :: (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
breakEnd Bool -> Bool
predicate = ([Bool] -> Bitmap)
-> ([Bool] -> Bitmap) -> ([Bool], [Bool]) -> (Bitmap, Bitmap)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [Bool] -> Bitmap
forall l. IsList l => [Item l] -> l
fromList [Bool] -> Bitmap
forall l. IsList l => [Item l] -> l
fromList (([Bool], [Bool]) -> (Bitmap, Bitmap))
-> (Bitmap -> ([Bool], [Bool])) -> Bitmap -> (Bitmap, Bitmap)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [Bool] -> Bool) -> [Bool] -> ([Bool], [Bool])
forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
C.breakEnd Bool -> Bool
Element [Bool] -> Bool
predicate ([Bool] -> ([Bool], [Bool]))
-> (Bitmap -> [Bool]) -> Bitmap -> ([Bool], [Bool])
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Bitmap -> [Bool]
forall l. IsList l => l -> [Item l]
toList

span :: (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
span :: (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
span Bool -> Bool
p = (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
break (Bool -> Bool
not (Bool -> Bool) -> (Bool -> Bool) -> Bool -> Bool
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Bool -> Bool
p)

map :: (Bool -> Bool) -> Bitmap -> Bitmap
map :: (Bool -> Bool) -> Bitmap -> Bitmap
map Bool -> Bool
f Bitmap
bits = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised ((Bool -> Bool) -> [Bool] -> [Bool]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Bool -> Bool
f) Bitmap
bits

--mapIndex :: (Int -> Bool -> Bool) -> Bitmap -> Bitmap
--mapIndex f Bitmap =

cons :: Bool -> Bitmap -> Bitmap
cons :: Bool -> Bitmap -> Bitmap
cons Bool
v Bitmap
l = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (Element [Bool] -> [Bool] -> [Bool]
forall c. Sequential c => Element c -> c -> c
C.cons Bool
Element [Bool]
v) Bitmap
l

snoc :: Bitmap -> Bool -> Bitmap
snoc :: Bitmap -> Bool -> Bitmap
snoc Bitmap
l Bool
v = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (([Bool] -> Bool -> [Bool]) -> Bool -> [Bool] -> [Bool]
forall a b c. (a -> b -> c) -> b -> a -> c
flip [Bool] -> Bool -> [Bool]
forall c. Sequential c => c -> Element c -> c
C.snoc Bool
v) Bitmap
l

-- unoptimised
uncons :: Bitmap -> Maybe (Bool, Bitmap)
uncons :: Bitmap -> Maybe (Bool, Bitmap)
uncons Bitmap
b = ((Bool, [Bool]) -> (Bool, Bitmap))
-> Maybe (Bool, [Bool]) -> Maybe (Bool, Bitmap)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([Bool] -> Bitmap) -> (Bool, [Bool]) -> (Bool, Bitmap)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second [Bool] -> Bitmap
forall l. IsList l => [Item l] -> l
fromList) (Maybe (Bool, [Bool]) -> Maybe (Bool, Bitmap))
-> Maybe (Bool, [Bool]) -> Maybe (Bool, Bitmap)
forall a b. (a -> b) -> a -> b
$ [Bool] -> Maybe (Element [Bool], [Bool])
forall c. Sequential c => c -> Maybe (Element c, c)
C.uncons ([Bool] -> Maybe (Element [Bool], [Bool]))
-> [Bool] -> Maybe (Element [Bool], [Bool])
forall a b. (a -> b) -> a -> b
$ Bitmap -> [Item Bitmap]
forall l. IsList l => l -> [Item l]
toList Bitmap
b

-- unoptimised
unsnoc :: Bitmap -> Maybe (Bitmap, Bool)
unsnoc :: Bitmap -> Maybe (Bitmap, Bool)
unsnoc Bitmap
b = (([Bool], Bool) -> (Bitmap, Bool))
-> Maybe ([Bool], Bool) -> Maybe (Bitmap, Bool)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([Bool] -> Bitmap) -> ([Bool], Bool) -> (Bitmap, Bool)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first [Bool] -> Bitmap
forall l. IsList l => [Item l] -> l
fromList) (Maybe ([Bool], Bool) -> Maybe (Bitmap, Bool))
-> Maybe ([Bool], Bool) -> Maybe (Bitmap, Bool)
forall a b. (a -> b) -> a -> b
$ [Bool] -> Maybe ([Bool], Element [Bool])
forall c. Sequential c => c -> Maybe (c, Element c)
C.unsnoc ([Bool] -> Maybe ([Bool], Element [Bool]))
-> [Bool] -> Maybe ([Bool], Element [Bool])
forall a b. (a -> b) -> a -> b
$ Bitmap -> [Item Bitmap]
forall l. IsList l => l -> [Item l]
toList Bitmap
b

intersperse :: Bool -> Bitmap -> Bitmap
intersperse :: Bool -> Bitmap -> Bitmap
intersperse Bool
b = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (Element [Bool] -> [Bool] -> [Bool]
forall c. Sequential c => Element c -> c -> c
C.intersperse Bool
Element [Bool]
b)

find :: (Bool -> Bool) -> Bitmap -> Maybe Bool
find :: (Bool -> Bool) -> Bitmap -> Maybe Bool
find Bool -> Bool
predicate Bitmap
vec = Offset Bool -> Maybe Bool
loop Offset Bool
0
  where
    !len :: CountOf Bool
len = Bitmap -> CountOf Bool
length Bitmap
vec
    loop :: Offset Bool -> Maybe Bool
loop Offset Bool
i
        | Offset Bool
i Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = Maybe Bool
forall a. Maybe a
Nothing
        | Bool
otherwise  =
            let e :: Bool
e = Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
vec Offset Bool
i
             in if Bool -> Bool
predicate Bool
e then Bool -> Maybe Bool
forall a. a -> Maybe a
Just Bool
e else Offset Bool -> Maybe Bool
loop (Offset Bool
iOffset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+Offset Bool
1)

sortBy :: (Bool -> Bool -> Ordering) -> Bitmap -> Bitmap
sortBy :: (Bool -> Bool -> Ordering) -> Bitmap -> Bitmap
sortBy Bool -> Bool -> Ordering
by Bitmap
bits = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised ((Element [Bool] -> Element [Bool] -> Ordering) -> [Bool] -> [Bool]
forall c.
Sequential c =>
(Element c -> Element c -> Ordering) -> c -> c
C.sortBy Bool -> Bool -> Ordering
Element [Bool] -> Element [Bool] -> Ordering
by) Bitmap
bits

filter :: (Bool -> Bool) -> Bitmap -> Bitmap
filter :: (Bool -> Bool) -> Bitmap -> Bitmap
filter Bool -> Bool
predicate Bitmap
vec = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised ((Bool -> Bool) -> [Bool] -> [Bool]
forall a. (a -> Bool) -> [a] -> [a]
Data.List.filter Bool -> Bool
predicate) Bitmap
vec

reverse :: Bitmap -> Bitmap
reverse :: Bitmap -> Bitmap
reverse Bitmap
bits = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised [Bool] -> [Bool]
forall c. Sequential c => c -> c
C.reverse Bitmap
bits

foldr :: (Bool -> a -> a) -> a -> Bitmap -> a
foldr :: (Bool -> a -> a) -> a -> Bitmap -> a
foldr Bool -> a -> a
f a
initialAcc Bitmap
vec = Offset Bool -> a
loop Offset Bool
0
  where
    len :: CountOf Bool
len = Bitmap -> CountOf Bool
length Bitmap
vec
    loop :: Offset Bool -> a
loop Offset Bool
i
        | Offset Bool
i Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = a
initialAcc
        | Bool
otherwise  = Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
vec Offset Bool
i Bool -> a -> a
`f` Offset Bool -> a
loop (Offset Bool
iOffset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+Offset Bool
1)

foldr' :: (Bool -> a -> a) -> a -> Bitmap -> a
foldr' :: (Bool -> a -> a) -> a -> Bitmap -> a
foldr' = (Bool -> a -> a) -> a -> Bitmap -> a
forall a. (Bool -> a -> a) -> a -> Bitmap -> a
foldr

foldl' :: (a -> Bool -> a) -> a -> Bitmap -> a
foldl' :: (a -> Bool -> a) -> a -> Bitmap -> a
foldl' a -> Bool -> a
f a
initialAcc Bitmap
vec = Offset Bool -> a -> a
loop Offset Bool
0 a
initialAcc
  where
    len :: CountOf Bool
len = Bitmap -> CountOf Bool
length Bitmap
vec
    loop :: Offset Bool -> a -> a
loop Offset Bool
i !a
acc
        | Offset Bool
i Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = a
acc
        | Bool
otherwise  = Offset Bool -> a -> a
loop (Offset Bool
iOffset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+Offset Bool
1) (a -> Bool -> a
f a
acc (Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
vec Offset Bool
i))

all :: (Bool -> Bool) -> Bitmap -> Bool
all :: (Bool -> Bool) -> Bitmap -> Bool
all Bool -> Bool
p Bitmap
bm = Offset Bool -> Bool
loop Offset Bool
0
  where
    len :: CountOf Bool
len = Bitmap -> CountOf Bool
length Bitmap
bm
    loop :: Offset Bool -> Bool
loop !Offset Bool
i
      | Offset Bool
i Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = Bool
True
      | Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> Bool
p (Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
bm Offset Bool
i) = Bool
False
      | Bool
otherwise = Offset Bool -> Bool
loop (Offset Bool
i Offset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+ Offset Bool
1)

any :: (Bool -> Bool) -> Bitmap -> Bool
any :: (Bool -> Bool) -> Bitmap -> Bool
any Bool -> Bool
p Bitmap
bm = Offset Bool -> Bool
loop Offset Bool
0
  where
    len :: CountOf Bool
len = Bitmap -> CountOf Bool
length Bitmap
bm
    loop :: Offset Bool -> Bool
loop !Offset Bool
i
      | Offset Bool
i Offset Bool -> CountOf Bool -> Bool
forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = Bool
False
      | Bool -> Bool
p (Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
bm Offset Bool
i) = Bool
True
      | Bool
otherwise = Offset Bool -> Bool
loop (Offset Bool
i Offset Bool -> Offset Bool -> Offset Bool
forall a. Additive a => a -> a -> a
+ Offset Bool
1)

unoptimised :: ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised :: ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised [Bool] -> [Bool]
f = [Bool] -> Bitmap
vFromList ([Bool] -> Bitmap) -> (Bitmap -> [Bool]) -> Bitmap -> Bitmap
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. [Bool] -> [Bool]
f ([Bool] -> [Bool]) -> (Bitmap -> [Bool]) -> Bitmap -> [Bool]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Bitmap -> [Bool]
vToList