    -- |
    -- 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
    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 = 32

    shiftPerTy :: Int
    shiftPerTy :: Int
    shiftPerTy = 5

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

    instance Show Bitmap where
        show :: Bitmap -> String
    show v :: 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
        mappend :: Bitmap -> Bitmap -> Bitmap
    mappend = Bitmap -> Bitmap -> Bitmap
    append
        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 e :: 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 n :: 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 n :: 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 n :: 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
        (!) l :: Bitmap
    l n :: 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 (Element Bitmap)
    forall a. a -> Maybe a
    Just (Bool -> Maybe (Element Bitmap)) -> Bool -> Maybe (Element Bitmap)
    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 predicate :: Element Bitmap -> Bool
    predicate c :: Bitmap
    c = Offset Bool -> Maybe (Offset Bool)
    loop 0
          where
            !len :: CountOf Bool
    len = Bitmap -> CountOf Bool
    length Bitmap
    c
            loop :: Offset Bool -> Maybe (Offset Bool)
    loop i :: 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 len :: CountOf Bool
    len ba :: 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 len :: CountOf Bool
    len mba :: 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 len :: CountOf Bool
    len ba :: 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 len :: CountOf Bool
    len mba :: 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 _ ma :: MUArray Word32 (PrimState prim)
    ma) i :: Offset Bool
    i v :: Bool
    v = do
        let (idx :: Offset Word32
    idx, bitIdx :: 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 _ ma :: MUArray Word32 (PrimState prim)
    ma) i :: Offset Bool
    i = do
        let (idx :: Offset Word32
    idx, bitIdx :: 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 mb :: MutableBitmap (PrimState prim)
    mb n :: Offset Bool
    n val :: 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 mb :: MutableBitmap (PrimState prim)
    mb n :: 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 bits :: Bitmap
    bits n :: 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 _ ba :: UArray Word32
    ba) n :: Offset Bool
    n =
        let (idx :: Offset Word32
    idx, bitIdx :: 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 sz :: CountOf Bool
    sz _) = CountOf Bool
    sz

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

    empty :: Bitmap
    empty :: Bitmap
    empty = CountOf Bool -> UArray Word32 -> Bitmap
    Bitmap 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 len :: 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 allBools :: [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 0 [Bool]
    allBools
      where
        loop :: MutableBitmap (PrimState prim)
    -> Offset Bool -> [Bool] -> prim Bitmap
    loop mb :: MutableBitmap (PrimState prim)
    mb _ []     = MutableBitmap (PrimState prim) -> prim Bitmap
    forall (prim :: * -> *).
    PrimMonad prim =>
    MutableBitmap (PrimState prim) -> prim Bitmap
    unsafeFreeze MutableBitmap (PrimState prim)
    mb
        loop mb :: MutableBitmap (PrimState prim)
    mb i :: Offset Bool
    i (x :: Bool
    x:xs :: [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
    +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 a :: Bitmap
    a = Offset Bool -> [Bool]
    loop 0
      where len :: CountOf Bool
    len = Bitmap -> CountOf Bool
    length Bitmap
    a
            loop :: Offset Bool -> [Bool]
    loop i :: 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
    +1)

    -- | Check if two vectors are identical
    equal :: Bitmap -> Bitmap -> Bool
    equal :: Bitmap -> Bitmap -> Bool
    equal a :: Bitmap
    a b :: 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 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 n :: 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
    +1)

    -- | Compare 2 vectors
    vCompare :: Bitmap -> Bitmap -> Ordering
    vCompare :: Bitmap -> Bitmap -> Ordering
    vCompare a :: Bitmap
    a b :: Bitmap
    b = Offset Bool -> Ordering
    loop 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 n :: 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
                    EQ -> Offset Bool -> Ordering
    loop (Offset Bool
    nOffset Bool -> Offset Bool -> Offset Bool
    forall a. Additive a => a -> a -> a
    +1)
                    r :: 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 a :: Bitmap
    a b :: 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 l :: [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]] -> [Item Bitmap]
    forall a. Monoid a => [a] -> a
    mconcat ([[Bool]] -> [Item Bitmap]) -> [[Bool]] -> [Item Bitmap]
    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 nbBits :: CountOf Bool
    nbBits _) = CountOf Bool
    nbBits CountOf Bool -> CountOf Bool -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0

    take :: CountOf Bool -> Bitmap -> Bitmap
    take :: CountOf Bool -> Bitmap -> Bitmap
    take nbElems :: CountOf Bool
    nbElems bits :: Bitmap
    bits@(Bitmap nbBits :: CountOf Bool
    nbBits ba :: UArray Word32
    ba)
        | CountOf Bool
    nbElems CountOf Bool -> CountOf Bool -> Bool
    forall a. Ord a => a -> a -> 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 nbElems :: CountOf Bool
    nbElems bits :: Bitmap
    bits@(Bitmap nbBits :: CountOf Bool
    nbBits _)
        | CountOf Bool
    nbElems CountOf Bool -> CountOf Bool -> Bool
    forall a. Ord a => a -> a -> 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 n :: CountOf Bool
    n v :: 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 f :: Bool -> Bool
    f bits :: 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 predicate :: Bool -> Bool
    predicate v :: Bitmap
    v = Offset Bool -> (Bitmap, Bitmap)
    findBreak 0
      where
        len :: CountOf Bool
    len = Bitmap -> CountOf Bool
    length Bitmap
    v
        findBreak :: Offset Bool -> (Bitmap, Bitmap)
    findBreak i :: 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
    +1)

    breakEnd :: (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
    breakEnd :: (Bool -> Bool) -> Bitmap -> (Bitmap, Bitmap)
    breakEnd predicate :: 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 p :: 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 f :: Bool -> Bool
    f bits :: 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 v :: Bool
    v l :: 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 l :: Bitmap
    l v :: 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 b :: 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 (Bool, [Bool])
    forall c. Sequential c => c -> Maybe (Element c, c)
    C.uncons ([Bool] -> Maybe (Bool, [Bool])) -> [Bool] -> Maybe (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 b :: 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], Bool)
    forall c. Sequential c => c -> Maybe (c, Element c)
    C.unsnoc ([Bool] -> Maybe ([Bool], Bool)) -> [Bool] -> Maybe ([Bool], 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 b :: 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 predicate :: Bool -> Bool
    predicate vec :: Bitmap
    vec = Offset Bool -> Maybe Bool
    loop 0
      where
        !len :: CountOf Bool
    len = Bitmap -> CountOf Bool
    length Bitmap
    vec
        loop :: Offset Bool -> Maybe Bool
    loop i :: 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
    +1)

    sortBy :: (Bool -> Bool -> Ordering) -> Bitmap -> Bitmap
    sortBy :: (Bool -> Bool -> Ordering) -> Bitmap -> Bitmap
    sortBy by :: Bool -> Bool -> Ordering
    by bits :: 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 predicate :: Bool -> Bool
    predicate vec :: 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 bits :: 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 f :: Bool -> a -> a
    f initialAcc :: a
    initialAcc vec :: Bitmap
    vec = Offset Bool -> a
    loop 0
      where
        len :: CountOf Bool
    len = Bitmap -> CountOf Bool
    length Bitmap
    vec
        loop :: Offset Bool -> a
    loop i :: 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
    +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' f :: a -> Bool -> a
    f initialAcc :: a
    initialAcc vec :: Bitmap
    vec = Offset Bool -> a -> a
    loop 0 a
    initialAcc
      where
        len :: CountOf Bool
    len = Bitmap -> CountOf Bool
    length Bitmap
    vec
        loop :: Offset Bool -> a -> a
    loop i :: 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
    +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 p :: Bool -> Bool
    p bm :: Bitmap
    bm = Offset Bool -> Bool
    loop 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
    + 1)

    any :: (Bool -> Bool) -> Bitmap -> Bool
    any :: (Bool -> Bool) -> Bitmap -> Bool
    any p :: Bool -> Bool
    p bm :: Bitmap
    bm = Offset Bool -> Bool
    loop 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
    + 1)

    unoptimised :: ([Bool] -> [Bool]) -> Bitmap -> Bitmap
    unoptimised :: ([Bool] -> [Bool]) -> Bitmap -> Bitmap
    unoptimised f :: [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