packages feed

pykinos-core-0.1.0.2: src/Pykinos/Bitset/Roaring.hs

{-# LANGUAGE BangPatterns, UnboxedTuples #-}

{- |
Module      : Pykinos.Bitset.Roaring
Description : Serried Roaring Bitmap with unboxed primitive chunk layout
Copyright   : (c) Nadia Yvette Chambers, 2026
License     : EUPL-1.2
Maintainer  : Nadia Chambers <nadia.yvette.chambers@ik.me>
Stability   : experimental
Portability : non-portable (GHC extensions, primitive arrays)

Implements compressed Roaring Bitmaps based on Chambi, Lemire, Kaser, and Godin (2016),
/"Better alternative to compressed bitmaps: Roaring bitmaps"/.

= Architectural Mechanics

A 32-bit integer \(x \in [0, 2^{32}-1]\) is partitioned into:
* A 16-bit chunk key: \(\text{hi} = \lfloor x / 2^{16} \rfloor\)
* A 16-bit in-chunk offset: \(\text{lo} = x \bmod 2^{16}\)

Within each 16-bit universe of 65,536 integers, data is stored in one of two formats:
1. **'ArrayChunk' (Sparse):** When cardinality \(< 4096\) elements, integers are stored
   as a sorted contiguous 'PrimArray Word16'. Space consumed is \(2 \times \text{cardinality}\) bytes.
2. **'BitmapChunk' (Dense):** When cardinality \(\ge 4096\) elements, integers are stored
   as an unboxed bitset of 1024 64-bit words (8192 bytes = 65,536 bits).

Set operations ('unionRoaring', 'intersectRoaring', 'differenceRoaring') execute via
two-finger merges over sorted chunk keys and utilize bitwise vector primitives for bitmap chunks.
-}
module Pykinos.Bitset.Roaring
  ( -- * Roaring Bitmap Types
    RoaringIntSet(..)
  , RoaringChunk(..)
    -- * Construction & Empty Sets
  , emptyRoaring
  , singletonRoaring
  , fromListRoaring
    -- * Queries & Predicates
  , nullRoaring
  , memberRoaring
  , toListRoaring
  , foldlRoaring'
    -- * Set Algebra
  , insertRoaring
  , deleteRoaring
  , unionRoaring
  , intersectRoaring
  , differenceRoaring
  ) where

import Control.Monad.ST (runST)
import Data.Bits (Bits(..), (.|.), (.&.), shiftL, shiftR, popCount)
import Data.Primitive.PrimArray
import Data.Primitive.SmallArray
import Data.Word (Word16, Word64)

-- | A 16-bit chunk inside a Roaring Bitmap:
--   * 'ArrayChunk' stores sorted 'Word16' offsets when cardinality < 4096.
--   * 'BitmapChunk' stores 1024 'Word64' bitmasks (65536 bits = 8 KB) when dense.
data RoaringChunk
  = ArrayChunk  {-# UNPACK #-} !(PrimArray Word16)
  | BitmapChunk {-# UNPACK #-} !(PrimArray Word64)
  deriving (Eq, Show)

-- | Serried Roaring Bitmap indexed by sorted 16-bit high keys.
--   Key blocks live entirely in unpinned 'PrimArray' memory (zero GC pointer tracing).
data RoaringIntSet = RoaringIntSet
  { risHighKeys :: {-# UNPACK #-} !(PrimArray Word16)
  , risChunks   :: {-# UNPACK #-} !(SmallArray RoaringChunk)
  } deriving (Eq, Show)

{-# INLINE splitKey #-}
splitKey :: Int -> (Word16, Word16)
splitKey !x =
  let !u = fromIntegral x :: Word
  in (fromIntegral (u `shiftR` 16), fromIntegral (u .&. 0xFFFF))

-- | Construct an empty 'RoaringIntSet'.
--
-- Running time: \(O(1)\).
{-# INLINE emptyRoaring #-}
emptyRoaring :: RoaringIntSet
emptyRoaring = RoaringIntSet (primArrayFromList []) (smallArrayFromList [])

-- | Test whether the 'RoaringIntSet' is empty.
--
-- Running time: \(O(1)\).
{-# INLINE nullRoaring #-}
nullRoaring :: RoaringIntSet -> Bool
nullRoaring (RoaringIntSet keys _) = sizeofPrimArray keys == 0

-- | Construct a single-element 'RoaringIntSet'.
--
-- Running time: \(O(1)\).
{-# INLINE singletonRoaring #-}
singletonRoaring :: Int -> RoaringIntSet
singletonRoaring !x =
  let (!hi, !lo) = splitKey x
  in RoaringIntSet
       (primArrayFromList [hi])
       (smallArrayFromList [ArrayChunk (primArrayFromList [lo])])

-- | Binary search over an unboxed 'PrimArray Word16'.
binarySearchW16 :: PrimArray Word16 -> Word16 -> Either Int Int
binarySearchW16 !arr !target = go 0 (sizeofPrimArray arr - 1)
  where
    go !lo !hi
      | lo > hi   = Left lo
      | otherwise =
          let !mid = (lo + hi) ` unsafeShiftR` 1
              !v   = indexPrimArray arr mid
          in if v == target
               then Right mid
               else if v < target
                 then go (mid + 1) hi
                 else go lo (mid - 1)

{-# INLINE memberRoaring #-}
memberRoaring :: Int -> RoaringIntSet -> Bool
memberRoaring !x (RoaringIntSet keys chunks) =
  let (!hi, !lo) = splitKey x
  in case binarySearchW16 keys hi of
       Left _     -> False
       Right !idx ->
         case indexSmallArray chunks idx of
           ArrayChunk arr ->
             case binarySearchW16 arr lo of
               Right _ -> True
               Left _  -> False
           BitmapChunk bmap ->
             let !wordIdx = fromIntegral lo `unsafeShiftR` 6
                 !bitIdx  = fromIntegral lo .&. 63
                 !w       = indexPrimArray bmap wordIdx
             in (w .&. (1 `unsafeShiftL` bitIdx)) /= 0

insertRoaring :: Int -> RoaringIntSet -> RoaringIntSet
insertRoaring !x r@(RoaringIntSet keys chunks) =
  let (!hi, !lo) = splitKey x
  in case binarySearchW16 keys hi of
       Left !insIdx ->
         let !newKeys   = insertPrimW16 keys insIdx hi
             !newChunk  = ArrayChunk (primArrayFromList [lo])
             !newChunks = insertSmall chunks insIdx newChunk
         in RoaringIntSet newKeys newChunks
       Right !idx ->
         let !oldChunk = indexSmallArray chunks idx
             !updChunk = insertIntoChunk lo oldChunk
         in if updChunk == oldChunk
              then r
              else RoaringIntSet keys (replaceSmall chunks idx updChunk)

insertIntoChunk :: Word16 -> RoaringChunk -> RoaringChunk
insertIntoChunk !lo (ArrayChunk arr) =
  case binarySearchW16 arr lo of
    Right _     -> ArrayChunk arr
    Left !insAt ->
      let !arr' = insertPrimW16 arr insAt lo
      in if sizeofPrimArray arr' >= 4096
           then arrayToBitmap arr'
           else ArrayChunk arr'
insertIntoChunk !lo (BitmapChunk bmap) = runST $ do
  let !wIdx = fromIntegral lo `unsafeShiftR` 6
      !bIdx = fromIntegral lo .&. 63
      !oldW = indexPrimArray bmap wIdx
      !newW = oldW .|. (1 `unsafeShiftL` bIdx)
  if oldW == newW
    then pure (BitmapChunk bmap)
    else do
      m <- thawPrimArray bmap 0 1024
      writePrimArray m wIdx newW
      BitmapChunk <$> unsafeFreezePrimArray m

deleteRoaring :: Int -> RoaringIntSet -> RoaringIntSet
deleteRoaring !x r@(RoaringIntSet keys chunks) =
  let (!hi, !lo) = splitKey x
  in case binarySearchW16 keys hi of
       Left _     -> r
       Right !idx ->
         case deleteFromChunk lo (indexSmallArray chunks idx) of
           Nothing       -> RoaringIntSet (deletePrimW16 keys idx) (deleteSmall chunks idx)
           Just !chunk'  -> RoaringIntSet keys (replaceSmall chunks idx chunk')

deleteFromChunk :: Word16 -> RoaringChunk -> Maybe RoaringChunk
deleteFromChunk !lo (ArrayChunk arr) =
  case binarySearchW16 arr lo of
    Left _ -> Just (ArrayChunk arr)
    Right !i
      | sizeofPrimArray arr <= 1 -> Nothing
      | otherwise                -> Just (ArrayChunk (deletePrimW16 arr i))
deleteFromChunk !lo (BitmapChunk bmap) =
  let !wIdx = fromIntegral lo `unsafeShiftR` 6
      !bIdx = fromIntegral lo .&. 63
      !oldW = indexPrimArray bmap wIdx
      !newW = oldW .&. complement (1 `unsafeShiftL` bIdx)
  in if oldW == newW
       then Just (BitmapChunk bmap)
       else
         let !bmap' = runST $ do
               m <- thawPrimArray bmap 0 1024
               writePrimArray m wIdx newW
               unsafeFreezePrimArray m
             !pop = popCountBitmap bmap'
         in if pop == 0
              then Nothing
              else if pop < 4096
                then Just (bitmapToArray bmap')
                else Just (BitmapChunk bmap')

-- | Two-finger merge union over sorted 16-bit chunk keys.
unionRoaring :: RoaringIntSet -> RoaringIntSet -> RoaringIntSet
unionRoaring (RoaringIntSet kA cA) (RoaringIntSet kB cB) =
  let !nA = sizeofPrimArray kA
      !nB = sizeofPrimArray kB
      go !i !j !accK !accC
        | i >= nA && j >= nB =
            RoaringIntSet (primArrayFromList (reverse accK)) (smallArrayFromList (reverse accC))
        | i >= nA =
            go i (j + 1) (indexPrimArray kB j : accK) (indexSmallArray cB j : accC)
        | j >= nB =
            go (i + 1) j (indexPrimArray kA i : accK) (indexSmallArray cA i : accC)
        | otherwise =
            let !hiA = indexPrimArray kA i
                !hiB = indexPrimArray kB j
            in case compare hiA hiB of
                 LT -> go (i + 1) j (hiA : accK) (indexSmallArray cA i : accC)
                 GT -> go i (j + 1) (hiB : accK) (indexSmallArray cB j : accC)
                 EQ ->
                   let !merged = unionChunk (indexSmallArray cA i) (indexSmallArray cB j)
                   in go (i + 1) (j + 1) (hiA : accK) (merged : accC)
  in go 0 0 [] []

unionChunk :: RoaringChunk -> RoaringChunk -> RoaringChunk
unionChunk (BitmapChunk bA) (BitmapChunk bB) = BitmapChunk $ runST $ do
  m <- newPrimArray 1024
  let loop !k
        | k >= 1024 = unsafeFreezePrimArray m
        | otherwise = do
            writePrimArray m k (indexPrimArray bA k .|. indexPrimArray bB k)
            loop (k + 1)
  loop 0
unionChunk (ArrayChunk aA) (BitmapChunk bB) =
  unionChunk (arrayToBitmap aA) (BitmapChunk bB)
unionChunk (BitmapChunk bA) (ArrayChunk aB) =
  unionChunk (BitmapChunk bA) (arrayToBitmap aB)
unionChunk (ArrayChunk aA) (ArrayChunk aB) =
  let !u = mergeSortedW16 aA aB
  in if sizeofPrimArray u >= 4096 then arrayToBitmap u else ArrayChunk u

-- | High-speed chunk intersection.
intersectRoaring :: RoaringIntSet -> RoaringIntSet -> RoaringIntSet
intersectRoaring (RoaringIntSet kA cA) (RoaringIntSet kB cB) =
  let !nA = sizeofPrimArray kA
      !nB = sizeofPrimArray kB
      go !i !j !accK !accC
        | i >= nA || j >= nB =
            RoaringIntSet (primArrayFromList (reverse accK)) (smallArrayFromList (reverse accC))
        | otherwise =
            let !hiA = indexPrimArray kA i
                !hiB = indexPrimArray kB j
            in case compare hiA hiB of
                 LT -> go (i + 1) j accK accC
                 GT -> go i (j + 1) accK accC
                 EQ ->
                   case intersectChunk (indexSmallArray cA i) (indexSmallArray cB j) of
                     Nothing  -> go (i + 1) (j + 1) accK accC
                     Just !ch -> go (i + 1) (j + 1) (hiA : accK) (ch : accC)
  in go 0 0 [] []

intersectChunk :: RoaringChunk -> RoaringChunk -> Maybe RoaringChunk
intersectChunk (BitmapChunk bA) (BitmapChunk bB) =
  let !bOut = runST $ do
        m <- newPrimArray 1024
        let loop !k
              | k >= 1024 = unsafeFreezePrimArray m
              | otherwise = do
                  writePrimArray m k (indexPrimArray bA k .&. indexPrimArray bB k)
                  loop (k + 1)
        loop 0
      !pop = popCountBitmap bOut
  in if pop == 0
       then Nothing
       else if pop < 4096
         then Just (bitmapToArray bOut)
         else Just (BitmapChunk bOut)
intersectChunk (ArrayChunk aA) (ArrayChunk aB) =
  let !inter = intersectSortedW16 aA aB
  in if sizeofPrimArray inter == 0 then Nothing else Just (ArrayChunk inter)
intersectChunk (ArrayChunk a) b@(BitmapChunk _) =
  let !filtered = filterW16 (`memberChunk` b) a
  in if sizeofPrimArray filtered == 0 then Nothing else Just (ArrayChunk filtered)
intersectChunk a@(BitmapChunk _) (ArrayChunk b) =
  intersectChunk (ArrayChunk b) a

-- | Two-finger difference over sorted 16-bit chunk keys.
differenceRoaring :: RoaringIntSet -> RoaringIntSet -> RoaringIntSet
differenceRoaring (RoaringIntSet kA cA) (RoaringIntSet kB cB) =
  let !nA = sizeofPrimArray kA
      !nB = sizeofPrimArray kB
      go !i !j !accK !accC
        | i >= nA =
            RoaringIntSet (primArrayFromList (reverse accK)) (smallArrayFromList (reverse accC))
        | j >= nB =
            go (i + 1) j (indexPrimArray kA i : accK) (indexSmallArray cA i : accC)
        | otherwise =
            let !hiA = indexPrimArray kA i
                !hiB = indexPrimArray kB j
            in case compare hiA hiB of
                 LT -> go (i + 1) j (hiA : accK) (indexSmallArray cA i : accC)
                 GT -> go i (j + 1) accK accC
                 EQ ->
                   case diffChunk (indexSmallArray cA i) (indexSmallArray cB j) of
                     Nothing  -> go (i + 1) (j + 1) accK accC
                     Just !ch -> go (i + 1) (j + 1) (hiA : accK) (ch : accC)
  in go 0 0 [] []

diffChunk :: RoaringChunk -> RoaringChunk -> Maybe RoaringChunk
diffChunk (ArrayChunk aA) bB =
  let !filtered = filterW16 (\lo -> not (memberChunk lo bB)) aA
  in if sizeofPrimArray filtered == 0 then Nothing else Just (ArrayChunk filtered)
diffChunk (BitmapChunk bA) (ArrayChunk aB) =
  let !bOut = runST $ do
        m <- thawPrimArray bA 0 1024
        let !n = sizeofPrimArray aB
            loop !i
              | i >= n = unsafeFreezePrimArray m
              | otherwise = do
                  let !lo = indexPrimArray aB i
                      !wIdx = fromIntegral lo `unsafeShiftR` 6
                      !bIdx = fromIntegral lo .&. 63
                  oldW <- readPrimArray m wIdx
                  writePrimArray m wIdx (oldW .&. complement (1 `unsafeShiftL` bIdx))
                  loop (i + 1)
        loop 0
      !pop = popCountBitmap bOut
  in if pop == 0
       then Nothing
       else if pop < 4096
         then Just (bitmapToArray bOut)
         else Just (BitmapChunk bOut)
diffChunk (BitmapChunk bA) (BitmapChunk bB) =
  let !bOut = runST $ do
        m <- newPrimArray 1024
        let loop !k
              | k >= 1024 = unsafeFreezePrimArray m
              | otherwise = do
                  writePrimArray m k (indexPrimArray bA k .&. complement (indexPrimArray bB k))
                  loop (k + 1)
        loop 0
      !pop = popCountBitmap bOut
  in if pop == 0
       then Nothing
       else if pop < 4096
         then Just (bitmapToArray bOut)
         else Just (BitmapChunk bOut)

fromListRoaring :: [Int] -> RoaringIntSet
fromListRoaring = foldl' (flip insertRoaring) emptyRoaring

toListRoaring :: RoaringIntSet -> [Int]
toListRoaring (RoaringIntSet keys chunks) =
  let !n = sizeofPrimArray keys
      chunkToList !hi (ArrayChunk arr) =
        let !m = sizeofPrimArray arr
        in [ combineKey hi (indexPrimArray arr i) | i <- [0 .. m - 1] ]
      chunkToList !hi (BitmapChunk bmap) =
        [ combineKey hi (fromIntegral ((wIdx `unsafeShiftL` 6) .|. bIdx))
        | wIdx <- [0 .. 1023]
        , let !w = indexPrimArray bmap wIdx
        , w /= 0
        , bIdx <- [0 .. 63]
        , (w .&. (1 `unsafeShiftL` bIdx)) /= 0
        ]
  in concat [ chunkToList (indexPrimArray keys i) (indexSmallArray chunks i) | i <- [0 .. n - 1] ]

{-# INLINE combineKey #-}
combineKey :: Word16 -> Word16 -> Int
combineKey !hi !lo =
  fromIntegral ((fromIntegral hi `shiftL` 16) .|. (fromIntegral lo :: Word))

foldlRoaring' :: (a -> Int -> a) -> a -> RoaringIntSet -> a
foldlRoaring' f !z0 !r = foldl' f z0 (toListRoaring r)

-- Helpers

memberChunk :: Word16 -> RoaringChunk -> Bool
memberChunk !lo (ArrayChunk arr) =
  case binarySearchW16 arr lo of
    Right _ -> True
    Left _  -> False
memberChunk !lo (BitmapChunk bmap) =
  let !wIdx = fromIntegral lo `unsafeShiftR` 6
      !bIdx = fromIntegral lo .&. 63
      !w    = indexPrimArray bmap wIdx
  in (w .&. (1 `unsafeShiftL` bIdx)) /= 0

insertPrimW16 :: PrimArray Word16 -> Int -> Word16 -> PrimArray Word16
insertPrimW16 !arr !idx !val = runST $ do
  let !n = sizeofPrimArray arr
  m <- newPrimArray (n + 1)
  copyPrimArray m 0 arr 0 idx
  writePrimArray m idx val
  copyPrimArray m (idx + 1) arr idx (n - idx)
  unsafeFreezePrimArray m

deletePrimW16 :: PrimArray Word16 -> Int -> PrimArray Word16
deletePrimW16 !arr !idx = runST $ do
  let !n = sizeofPrimArray arr
  m <- newPrimArray (n - 1)
  copyPrimArray m 0 arr 0 idx
  copyPrimArray m idx arr (idx + 1) (n - idx - 1)
  unsafeFreezePrimArray m

insertSmall :: SmallArray a -> Int -> a -> SmallArray a
insertSmall !arr !idx val = runST $ do
  let !n = sizeofSmallArray arr
  m <- newSmallArray (n + 1) val
  copySmallArray m 0 arr 0 idx
  writeSmallArray m idx val
  copySmallArray m (idx + 1) arr idx (n - idx)
  unsafeFreezeSmallArray m

deleteSmall :: SmallArray a -> Int -> SmallArray a
deleteSmall !arr !idx = runST $ do
  let !n = sizeofSmallArray arr
  m <- newSmallArray (n - 1) (indexSmallArray arr (if idx == 0 then 1 else 0))
  copySmallArray m 0 arr 0 idx
  copySmallArray m idx arr (idx + 1) (n - idx - 1)
  unsafeFreezeSmallArray m

replaceSmall :: SmallArray a -> Int -> a -> SmallArray a
replaceSmall !arr !idx val = runST $ do
  let !n = sizeofSmallArray arr
  m <- thawSmallArray arr 0 n
  writeSmallArray m idx val
  unsafeFreezeSmallArray m

arrayToBitmap :: PrimArray Word16 -> RoaringChunk
arrayToBitmap !arr = runST $ do
  m <- newPrimArray 1024
  setPrimArray m 0 1024 0
  let !n = sizeofPrimArray arr
      loop !i
        | i >= n = BitmapChunk <$> unsafeFreezePrimArray m
        | otherwise = do
            let !lo = indexPrimArray arr i
                !wIdx = fromIntegral lo `unsafeShiftR` 6
                !bIdx = fromIntegral lo .&. 63
            oldW <- readPrimArray m wIdx
            writePrimArray m wIdx (oldW .|. (1 `unsafeShiftL` bIdx))
            loop (i + 1)
  loop 0

bitmapToArray :: PrimArray Word64 -> RoaringChunk
bitmapToArray !bmap =
  let !elements = [ fromIntegral ((wIdx `unsafeShiftL` 6) .|. bIdx) :: Word16
                  | wIdx <- [0..1023]
                  , let !w = indexPrimArray bmap wIdx
                  , w /= 0
                  , bIdx <- [0..63]
                  , (w .&. (1 `unsafeShiftL` bIdx)) /= 0
                  ]
  in ArrayChunk (primArrayFromList elements)

popCountBitmap :: PrimArray Word64 -> Int
popCountBitmap !bmap =
  let go !i !acc
        | i >= 1024 = acc
        | otherwise = go (i + 1) (acc + popCount (indexPrimArray bmap i))
  in go 0 0

mergeSortedW16 :: PrimArray Word16 -> PrimArray Word16 -> PrimArray Word16
mergeSortedW16 !aA !aB =
  let !nA = sizeofPrimArray aA
      !nB = sizeofPrimArray aB
      go !i !j !acc
        | i >= nA && j >= nB = primArrayFromList (reverse acc)
        | i >= nA = go i (j + 1) (indexPrimArray aB j : acc)
        | j >= nB = go (i + 1) j (indexPrimArray aA i : acc)
        | otherwise =
            let !vA = indexPrimArray aA i
                !vB = indexPrimArray aB j
            in case compare vA vB of
                 LT -> go (i + 1) j (vA : acc)
                 GT -> go i (j + 1) (vB : acc)
                 EQ -> go (i + 1) (j + 1) (vA : acc)
  in go 0 0 []

intersectSortedW16 :: PrimArray Word16 -> PrimArray Word16 -> PrimArray Word16
intersectSortedW16 !aA !aB =
  let !nA = sizeofPrimArray aA
      !nB = sizeofPrimArray aB
      go !i !j !acc
        | i >= nA || j >= nB = primArrayFromList (reverse acc)
        | otherwise =
            let !vA = indexPrimArray aA i
                !vB = indexPrimArray aB j
            in case compare vA vB of
                 LT -> go (i + 1) j acc
                 GT -> go i (j + 1) acc
                 EQ -> go (i + 1) (j + 1) (vA : acc)
  in go 0 0 []

filterW16 :: (Word16 -> Bool) -> PrimArray Word16 -> PrimArray Word16
filterW16 p !arr =
  let !n = sizeofPrimArray arr
      go !i !acc
        | i >= n    = primArrayFromList (reverse acc)
        | otherwise =
            let !v = indexPrimArray arr i
            in if p v then go (i + 1) (v : acc) else go (i + 1) acc
  in go 0 []