{-# 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 #-}
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 #-}
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 #-}
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 #-}
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)
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
len :: CountOf (Element [Bool])
len = [Bool] -> CountOf (Element [Bool])
forall c. Collection c => c -> CountOf (Element c)
C.length [Bool]
allBools
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)
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)
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 :: 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
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
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
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)
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
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
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
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
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