{-# 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 = forall a. Show a => a -> String
show (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
vFromList
toList :: Bitmap -> [Item Bitmap]
toList = Bitmap -> [Bool]
vToList
instance C.InnerFunctor Bitmap where
imap :: (Element Bitmap -> Element Bitmap) -> Bitmap -> Bitmap
imap = (Bool -> Bool) -> Bitmap -> Bitmap
map
instance C.Foldable Bitmap where
foldr :: forall a. (Element Bitmap -> a -> a) -> a -> Bitmap -> a
foldr = forall a. (Bool -> a -> a) -> a -> Bitmap -> a
foldr
foldl' :: forall a. (a -> Element Bitmap -> a) -> a -> Bitmap -> a
foldl' = forall a. (a -> Bool -> a) -> a -> Bitmap -> a
foldl'
foldr' :: forall a. (Element Bitmap -> a -> a) -> a -> Bitmap -> a
foldr' = 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
length
elem :: forall a.
(Eq a, a ~ Element Bitmap) =>
Element Bitmap -> Bitmap -> Bool
elem Element Bitmap
e = forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
Data.List.elem Element Bitmap
e forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall l. IsList l => l -> [Item l]
toList
maximum :: forall a.
(Ord a, a ~ Element Bitmap) =>
NonEmpty Bitmap -> Element Bitmap
maximum = (Bool -> Bool) -> Bitmap -> Bool
any forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall a. NonEmpty a -> a
C.getNonEmpty
minimum :: forall a.
(Ord a, a ~ Element Bitmap) =>
NonEmpty Bitmap -> Element Bitmap
minimum = (Bool -> Bool) -> Bitmap -> Bool
all forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall a. NonEmpty a -> a
C.getNonEmpty
all :: (Element Bitmap -> Bool) -> Bitmap -> Bool
all = (Bool -> Bool) -> Bitmap -> Bool
all
any :: (Element Bitmap -> Bool) -> Bitmap -> Bool
any = (Bool -> Bool) -> Bitmap -> Bool
any
instance C.Sequential Bitmap where
take :: CountOf (Element Bitmap) -> Bitmap -> Bitmap
take = CountOf Bool -> Bitmap -> Bitmap
take
drop :: CountOf (Element Bitmap) -> Bitmap -> Bitmap
drop = CountOf Bool -> Bitmap -> Bitmap
drop
splitAt :: CountOf (Element Bitmap) -> Bitmap -> (Bitmap, Bitmap)
splitAt = CountOf Bool -> Bitmap -> (Bitmap, Bitmap)
splitAt
revTake :: CountOf (Element Bitmap) -> Bitmap -> Bitmap
revTake CountOf (Element Bitmap)
n = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (forall c. Sequential c => CountOf (Element c) -> c -> c
C.revTake CountOf (Element Bitmap)
n)
revDrop :: CountOf (Element Bitmap) -> Bitmap -> Bitmap
revDrop CountOf (Element Bitmap)
n = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (forall c. Sequential c => CountOf (Element c) -> c -> c
C.revDrop CountOf (Element Bitmap)
n)
splitOn :: (Element Bitmap -> Bool) -> Bitmap -> [Bitmap]
splitOn = (Bool -> Bool) -> Bitmap -> [Bitmap]
splitOn
break :: (Element Bitmap -> Bool) -> Bitmap -> (Bitmap, Bitmap)
break = (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
break
breakEnd :: (Element Bitmap -> Bool) -> Bitmap -> (Bitmap, Bitmap)
breakEnd = (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
breakEnd
span :: (Element Bitmap -> Bool) -> Bitmap -> (Bitmap, Bitmap)
span = (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
span
filter :: (Element Bitmap -> Bool) -> Bitmap -> Bitmap
filter = (Bool -> Bool) -> Bitmap -> Bitmap
filter
reverse :: Bitmap -> Bitmap
reverse = Bitmap -> Bitmap
reverse
snoc :: Bitmap -> Element Bitmap -> Bitmap
snoc = Bitmap -> Bool -> Bitmap
snoc
cons :: Element Bitmap -> Bitmap -> Bitmap
cons = Bool -> Bitmap -> Bitmap
cons
unsnoc :: Bitmap -> Maybe (Bitmap, Element Bitmap)
unsnoc = Bitmap -> Maybe (Bitmap, Bool)
unsnoc
uncons :: Bitmap -> Maybe (Element Bitmap, Bitmap)
uncons = Bitmap -> Maybe (Bool, Bitmap)
uncons
intersperse :: Element Bitmap -> Bitmap -> Bitmap
intersperse = Bool -> Bitmap -> Bitmap
intersperse
find :: (Element Bitmap -> Bool) -> Bitmap -> Maybe (Element Bitmap)
find = (Bool -> Bool) -> Bitmap -> Maybe Bool
find
sortBy :: (Element Bitmap -> Element Bitmap -> Ordering) -> Bitmap -> Bitmap
sortBy = (Bool -> Bool -> Ordering) -> Bitmap -> Bitmap
sortBy
singleton :: Element Bitmap -> Bitmap
singleton = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (forall a. a -> [a] -> [a]
:[])
replicate :: CountOf (Element Bitmap) -> Element Bitmap -> Bitmap
replicate CountOf (Element Bitmap)
n = forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => CountOf (Element c) -> Element c -> c
C.replicate CountOf (Element Bitmap)
n
instance C.IndexedCollection Bitmap where
! :: Bitmap -> Offset (Element Bitmap) -> Maybe (Element Bitmap)
(!) Bitmap
l Offset (Element Bitmap)
n
| forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset (Element Bitmap)
n (Bitmap -> CountOf Bool
length Bitmap
l) = forall a. Maybe a
Nothing
| Bool
otherwise = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ Bitmap -> Offset Bool -> Bool
index Bitmap
l 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 forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = forall a. Maybe a
Nothing
| Element Bitmap -> Bool
predicate (Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
c Offset Bool
i) = forall a. a -> Maybe a
Just Offset Bool
i
| Bool
otherwise = forall a. Maybe a
Nothing
instance C.MutableCollection MutableBitmap where
type MutableFreezed MutableBitmap = Bitmap
type MutableKey MutableBitmap = Offset Bool
type MutableValue MutableBitmap = Bool
thaw :: forall (prim :: * -> *).
PrimMonad prim =>
MutableFreezed MutableBitmap
-> prim (MutableBitmap (PrimState prim))
thaw = forall (prim :: * -> *).
PrimMonad prim =>
Bitmap -> prim (MutableBitmap (PrimState prim))
thaw
freeze :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim)
-> prim (MutableFreezed MutableBitmap)
freeze = forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> prim Bitmap
freeze
unsafeThaw :: forall (prim :: * -> *).
PrimMonad prim =>
MutableFreezed MutableBitmap
-> prim (MutableBitmap (PrimState prim))
unsafeThaw = forall (prim :: * -> *).
PrimMonad prim =>
Bitmap -> prim (MutableBitmap (PrimState prim))
unsafeThaw
unsafeFreeze :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim)
-> prim (MutableFreezed MutableBitmap)
unsafeFreeze = forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> prim Bitmap
unsafeFreeze
mutNew :: forall (prim :: * -> *).
PrimMonad prim =>
CountOf (MutableValue MutableBitmap)
-> prim (MutableBitmap (PrimState prim))
mutNew = forall (prim :: * -> *).
PrimMonad prim =>
CountOf Bool -> prim (MutableBitmap (PrimState prim))
new
mutUnsafeWrite :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap
-> MutableValue MutableBitmap
-> prim ()
mutUnsafeWrite = forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
unsafeWrite
mutUnsafeRead :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap -> prim (MutableValue MutableBitmap)
mutUnsafeRead = forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
unsafeRead
mutWrite :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap
-> MutableValue MutableBitmap
-> prim ()
mutWrite = forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
write
mutRead :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim)
-> MutableKey MutableBitmap -> prim (MutableValue MutableBitmap)
mutRead = 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) = (forall ty. Int -> Offset ty
Offset (Int
i forall a. Bits a => a -> Int -> a
.>>. Int
shiftPerTy), Int
i forall a. Bits a => a -> a -> a
.&. Int
maskPerTy)
{-# INLINE bitmapIndex #-}
thaw :: PrimMonad prim => Bitmap -> prim (MutableBitmap (PrimState prim))
thaw :: forall (prim :: * -> *).
PrimMonad prim =>
Bitmap -> prim (MutableBitmap (PrimState prim))
thaw (Bitmap CountOf Bool
len UArray Word32
ba) = forall st. CountOf Bool -> MUArray Word32 st -> MutableBitmap st
MutableBitmap CountOf Bool
len forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` forall (c :: * -> *) (prim :: * -> *).
(MutableCollection c, PrimMonad prim) =>
MutableFreezed c -> prim (c (PrimState prim))
C.thaw UArray Word32
ba
freeze :: PrimMonad prim => MutableBitmap (PrimState prim) -> prim Bitmap
freeze :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> prim Bitmap
freeze (MutableBitmap CountOf Bool
len MUArray Word32 (PrimState prim)
mba) = CountOf Bool -> UArray Word32 -> Bitmap
Bitmap CountOf Bool
len forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` 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 :: forall (prim :: * -> *).
PrimMonad prim =>
Bitmap -> prim (MutableBitmap (PrimState prim))
unsafeThaw (Bitmap CountOf Bool
len UArray Word32
ba) = forall st. CountOf Bool -> MUArray Word32 st -> MutableBitmap st
MutableBitmap CountOf Bool
len forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` forall (c :: * -> *) (prim :: * -> *).
(MutableCollection c, PrimMonad prim) =>
MutableFreezed c -> prim (c (PrimState prim))
C.unsafeThaw UArray Word32
ba
unsafeFreeze :: PrimMonad prim => MutableBitmap (PrimState prim) -> prim Bitmap
unsafeFreeze :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> prim Bitmap
unsafeFreeze (MutableBitmap CountOf Bool
len MUArray Word32 (PrimState prim)
mba) = CountOf Bool -> UArray Word32 -> Bitmap
Bitmap CountOf Bool
len forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` 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 :: forall (prim :: * -> *).
PrimMonad prim =>
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 <- 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 forall a. Bits a => a -> Int -> a
setBit Word32
w Int
bitIdx else forall a. Bits a => a -> Int -> a
clearBit Word32
w Int
bitIdx
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 :: forall (prim :: * -> *).
PrimMonad prim =>
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
forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. Bits a => a -> Int -> Bool
testBit Int
bitIdx forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` 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 :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
write MutableBitmap (PrimState prim)
mb Offset Bool
n Bool
val
| forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset Bool
n CountOf Bool
len = 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 = 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 = forall st. MutableBitmap st -> CountOf Bool
mutableLength MutableBitmap (PrimState prim)
mb
{-# INLINE write #-}
read :: PrimMonad prim => MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
read :: forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
read MutableBitmap (PrimState prim)
mb Offset Bool
n
| forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset Bool
n CountOf Bool
len = 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 = forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> prim Bool
unsafeRead MutableBitmap (PrimState prim)
mb Offset Bool
n
where len :: CountOf Bool
len = 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
| forall ty. Offset ty -> CountOf ty -> Bool
isOutOfBound Offset Bool
n CountOf Bool
len = 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 forall a. Bits a => a -> Int -> Bool
testBit (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 :: forall st. 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 forall a. Monoid a => a
mempty
new :: PrimMonad prim => CountOf Bool -> prim (MutableBitmap (PrimState prim))
new :: forall (prim :: * -> *).
PrimMonad prim =>
CountOf Bool -> prim (MutableBitmap (PrimState prim))
new sz :: CountOf Bool
sz@(CountOf Int
len) =
forall st. CountOf Bool -> MUArray Word32 st -> MutableBitmap st
MutableBitmap CountOf Bool
sz forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> 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 = forall ty. Int -> CountOf ty
CountOf ((Int
len Int -> Int -> Int
`alignRoundUp` Int
bitsPerTy) forall a. Bits a => a -> Int -> a
.>>. Int
shiftPerTy)
vFromList :: [Bool] -> Bitmap
vFromList :: [Bool] -> Bitmap
vFromList [Bool]
allBools = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
MutableBitmap s
mbitmap <- forall (prim :: * -> *).
PrimMonad prim =>
CountOf Bool -> prim (MutableBitmap (PrimState prim))
new CountOf (Element [Bool])
len
forall {prim :: * -> *}.
PrimMonad prim =>
MutableBitmap (PrimState prim)
-> Offset Bool -> [Bool] -> prim Bitmap
loop MutableBitmap s
mbitmap Offset Bool
0 [Bool]
allBools
where
loop :: MutableBitmap (PrimState prim)
-> Offset Bool -> [Bool] -> prim Bitmap
loop MutableBitmap (PrimState prim)
mb Offset Bool
_ [] = 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) = forall (prim :: * -> *).
PrimMonad prim =>
MutableBitmap (PrimState prim) -> Offset Bool -> Bool -> prim ()
unsafeWrite MutableBitmap (PrimState prim)
mb Offset Bool
i Bool
x 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
iforall a. Additive a => a -> a -> a
+Offset Bool
1) [Bool]
xs
len :: CountOf (Element [Bool])
len = 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 forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = []
| Bool
otherwise = Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
a Offset Bool
i forall a. a -> [a] -> [a]
: Offset Bool -> [Bool]
loop (Offset Bool
iforall 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 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 forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
la = Bool
True
| Bool
otherwise = (Bitmap -> Offset Bool -> Bool
unsafeIndex Bitmap
a Offset Bool
n 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
nforall 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 forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
la = if CountOf Bool
la forall a. Eq a => a -> a -> Bool
== CountOf Bool
lb then Ordering
EQ else Ordering
LT
| Offset Bool
n 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 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
nforall 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 = forall l. IsList l => [Item l] -> l
fromList forall a b. (a -> b) -> a -> b
$ forall l. IsList l => l -> [Item l]
toList Bitmap
a forall a. Monoid a => a -> a -> a
`mappend` forall l. IsList l => l -> [Item l]
toList Bitmap
b
concat :: [Bitmap] -> Bitmap
concat :: [Bitmap] -> Bitmap
concat [Bitmap]
l = forall l. IsList l => [Item l] -> l
fromList forall a b. (a -> b) -> a -> b
$ forall a. Monoid a => [a] -> a
mconcat forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap 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 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 forall a. Ord a => a -> a -> Bool
<= CountOf Bool
0 = Bitmap
empty
| CountOf Bool
nbElems 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 forall a. Ord a => a -> a -> Bool
<= CountOf Bool
0 = Bitmap
bits
| CountOf Bool
nbElems forall a. Ord a => a -> a -> Bool
>= CountOf Bool
nbBits = Bitmap
empty
| Bool
otherwise = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (forall c. Sequential c => CountOf (Element c) -> c -> c
C.drop CountOf 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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall l. IsList l => [Item l] -> l
fromList forall a b. (a -> b) -> a -> b
$ forall c. Sequential c => (Element c -> Bool) -> c -> [c]
C.splitOn Bool -> Bool
f forall a b. (a -> b) -> a -> b
$ 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 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 (forall a. Offset a -> CountOf a
offsetAsSize Offset Bool
i) Bitmap
v
else Offset Bool -> (Bitmap, Bitmap)
findBreak (Offset Bool
iforall 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 = forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap forall l. IsList l => [Item l] -> l
fromList forall l. IsList l => [Item l] -> l
fromList forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall c. Sequential c => (Element c -> Bool) -> c -> (c, c)
C.breakEnd Bool -> Bool
predicate forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. 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 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 (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 (forall c. Sequential c => Element c -> c -> c
C.cons Bool
v) Bitmap
l
snoc :: Bitmap -> Bool -> Bitmap
snoc :: Bitmap -> Bool -> Bitmap
snoc Bitmap
l Bool
v = ([Bool] -> [Bool]) -> Bitmap -> Bitmap
unoptimised (forall a b c. (a -> b -> c) -> b -> a -> c
flip 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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second forall l. IsList l => [Item l] -> l
fromList) forall a b. (a -> b) -> a -> b
$ forall c. Sequential c => c -> Maybe (Element c, c)
C.uncons forall a b. (a -> b) -> a -> b
$ forall l. IsList l => l -> [Item l]
toList Bitmap
b
unsnoc :: Bitmap -> Maybe (Bitmap, Bool)
unsnoc :: Bitmap -> Maybe (Bitmap, Bool)
unsnoc Bitmap
b = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first forall l. IsList l => [Item l] -> l
fromList) forall a b. (a -> b) -> a -> b
$ forall c. Sequential c => c -> Maybe (c, Element c)
C.unsnoc forall a b. (a -> b) -> a -> b
$ 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 (forall c. Sequential c => Element c -> c -> c
C.intersperse 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 forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = 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 forall a. a -> Maybe a
Just Bool
e else Offset Bool -> Maybe Bool
loop (Offset Bool
iforall 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 (forall c.
Sequential c =>
(Element c -> Element c -> Ordering) -> c -> c
C.sortBy Bool -> 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 (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 forall c. Sequential c => c -> c
C.reverse Bitmap
bits
foldr :: (Bool -> a -> a) -> a -> Bitmap -> a
foldr :: forall a. (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 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
iforall a. Additive a => a -> a -> a
+Offset Bool
1)
foldr' :: (Bool -> a -> a) -> a -> Bitmap -> a
foldr' :: forall a. (Bool -> a -> a) -> a -> Bitmap -> a
foldr' = forall a. (Bool -> a -> a) -> a -> Bitmap -> a
foldr
foldl' :: (a -> Bool -> a) -> a -> Bitmap -> a
foldl' :: forall a. (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 forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = a
acc
| Bool
otherwise = Offset Bool -> a -> a
loop (Offset Bool
iforall 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 forall ty. Offset ty -> CountOf ty -> Bool
.==# CountOf Bool
len = Bool
True
| Bool -> Bool
not 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 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 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 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 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 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