pykinos-core-0.1.0.2: src/Pykinos/IntMap/ART.hs
{-# LANGUAGE BangPatterns, DeriveTraversable #-}
{- |
Module : Pykinos.IntMap.ART
Description : Adaptive Radix Tree (ART) with 4-tier unboxed fanout
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 the Adaptive Radix Tree (ART) space-efficient radix tree layout derived from
Leis et al. (ICDE 2013), /"The Adaptive Radix Tree: ARTful Indexing for Main Memory Databases"/.
= Architectural Mechanics
Traditional radix trees (tries) face a trade-off between span width and space consumption:
* Large spans (e.g. 256 children per node) waste significant memory on sparse branches.
* Small spans (e.g. 2 or 4 children) create tall trees requiring excessive pointer hops.
ART solves this dynamically by employing 4 distinct node structures that expand
and adapt dynamically based on child count:
1. **'ARTNode4' (1 to 4 children):**
Stores up to 4 child pointers alongside an unboxed 4-byte key array. Search executes
via a linear scan over the 4-byte array.
2. **'ARTNode16' (5 to 16 children):**
Stores up to 16 child pointers alongside 16 sorted key bytes.
3. **'ARTNode48' (17 to 48 children):**
Stores a 256-byte direct lookup table mapping byte values to child array indices (0..47),
using 255 as the empty sentinel. Child pointers reside in a compact 48-element array.
4. **'ARTNode256' (49 to 256 children):**
Full direct lookup array of 256 child pointers indexed directly by byte value.
= Path Compression
Single-child subtrees are collapsed into path-compressed prefixes ('pref' and 'sh'),
ensuring tree height is bounded strictly by key length (up to 8 bytes for 64-bit 'Int' keys).
-}
module Pykinos.IntMap.ART
( -- * ART IntMap Type
ARTIntMap(..)
-- * Construction & Empty Maps
, emptyART
, singletonART
, artFromList
-- * Queries
, artLookup
, artMember
, artToList
, artKeysSet
-- * Insertion & Deletion
, artInsert
, artInsertWith
, artDelete
) where
import Control.Monad (when)
import Control.Monad.ST (runST)
import Data.Bits ((.&.), unsafeShiftR)
import Data.Primitive.PrimArray
import Data.Primitive.SmallArray
import Data.Word (Word8)
import Pykinos.Bitset.Roaring (RoaringIntSet, fromListRoaring)
-- | Adaptive Radix Tree (ART) IntMap with 4-tier span fanout:
--
-- * 'ARTLeaf' : Path-compressed single key-value leaf.
-- * 'ARTNode4' : 1..4 children (unboxed 'Word8' key bytes + 'SmallArray' children).
-- * 'ARTNode16' : 5..16 children (sorted 'Word8' key bytes + 'SmallArray' children).
-- * 'ARTNode48' : 17..48 children (256-byte direct index table + up to 48 children).
-- * 'ARTNode256': 49..256 children (direct 256-slot 'SmallArray').
data ARTIntMap a
= ARTEmpty
| ARTLeaf {-# UNPACK #-} !Int a
-- ^ Path-compressed leaf storing full 64-bit key and associated value.
| ARTNode4 {-# UNPACK #-} !Int {-# UNPACK #-} !Int
{-# UNPACK #-} !(PrimArray Word8)
{-# UNPACK #-} !(SmallArray (ARTIntMap a))
-- ^ Small node storing 1..4 child pointers.
| ARTNode16 {-# UNPACK #-} !Int {-# UNPACK #-} !Int
{-# UNPACK #-} !(PrimArray Word8)
{-# UNPACK #-} !(SmallArray (ARTIntMap a))
-- ^ Medium node storing 5..16 child pointers.
| ARTNode48 {-# UNPACK #-} !Int {-# UNPACK #-} !Int
{-# UNPACK #-} !(PrimArray Word8)
{-# UNPACK #-} !(SmallArray (ARTIntMap a))
-- ^ Large node storing 17..48 child pointers with 256-byte index map.
| ARTNode256 {-# UNPACK #-} !Int {-# UNPACK #-} !Int
{-# UNPACK #-} !(SmallArray (ARTIntMap a))
-- ^ Full 256-slot direct-indexed radix node.
deriving (Eq, Show, Functor, Foldable, Traversable)
-- | Construct an empty Adaptive Radix Tree.
--
-- Running time: \(O(1)\).
{-# INLINE emptyART #-}
emptyART :: ARTIntMap a
emptyART = ARTEmpty
-- | Construct a single-element Adaptive Radix Tree.
--
-- Running time: \(O(1)\).
{-# INLINE singletonART #-}
singletonART :: Int -> a -> ARTIntMap a
singletonART !k = ARTLeaf k
-- | Extract the relevant byte at bit-shift position 'shiftBits' from key 'k'.
{-# INLINE extractByte #-}
extractByte :: Int -> Int -> Word8
extractByte !k !shiftBits = fromIntegral ((k `unsafeShiftR` shiftBits) .&. 0xFF)
-- | Check whether key 'k' matches the path-compressed prefix of a node.
{-# INLINE prefixMatch #-}
prefixMatch :: Int -> Int -> Int -> Bool
prefixMatch !k !pref !shiftBits =
let !highShift = shiftBits + 8
in (highShift >= 64) || ((k `unsafeShiftR` highShift) == (pref `unsafeShiftR` highShift))
-- | Lookup a value associated with key 'k' in the Adaptive Radix Tree.
--
-- Running time: \(O(k)\) where \(k \le 8\) bytes for 64-bit keys.
artLookup :: Int -> ARTIntMap a -> Maybe a
artLookup !_ ARTEmpty = Nothing
artLookup !k (ARTLeaf lk v)
| k == lk = Just v
| otherwise = Nothing
artLookup !k (ARTNode4 pref sh keys children)
| not (prefixMatch k pref sh) = Nothing
| otherwise =
let !b = extractByte k sh
in case findByteLinear keys b of
Just !idx -> artLookup k (indexSmallArray children idx)
Nothing -> Nothing
artLookup !k (ARTNode16 pref sh keys children)
| not (prefixMatch k pref sh) = Nothing
| otherwise =
let !b = extractByte k sh
in case findByteLinear keys b of
Just !idx -> artLookup k (indexSmallArray children idx)
Nothing -> Nothing
artLookup !k (ARTNode48 pref sh dir children)
| not (prefixMatch k pref sh) = Nothing
| otherwise =
let !b = extractByte k sh
!slot = indexPrimArray dir (fromIntegral b)
in if slot == 255
then Nothing
else artLookup k (indexSmallArray children (fromIntegral slot))
artLookup !k (ARTNode256 pref sh children)
| not (prefixMatch k pref sh) = Nothing
| otherwise =
let !b = extractByte k sh
in case indexSmallArray children (fromIntegral b) of
ARTEmpty -> Nothing
!child -> artLookup k child
-- | Check whether key 'k' is a member of the Adaptive Radix Tree.
--
-- Running time: \(O(k)\).
{-# INLINE artMember #-}
artMember :: Int -> ARTIntMap a -> Bool
artMember !k !m = case artLookup k m of { Just _ -> True; Nothing -> False }
-- | Insert a key-value association into the ART, replacing any existing value.
--
-- Running time: \(O(k)\) where \(k \le 8\) steps.
artInsert :: Int -> a -> ARTIntMap a -> ARTIntMap a
artInsert !k = artInsertWith const k
-- | Insert with a combining function for resolving existing values.
--
-- Running time: \(O(k)\).
artInsertWith :: (a -> a -> a) -> Int -> a -> ARTIntMap a -> ARTIntMap a
artInsertWith f !k v = go 56
where
go !_ ARTEmpty = ARTLeaf k v
go !sh (ARTLeaf lk lv)
| k == lk = ARTLeaf k (f v lv)
| otherwise = splitLeaves sh k v lk lv
go !sh node@(ARTNode4 pref nodeSh keys children)
| not (prefixMatch k pref nodeSh) = splitPrefix sh k v pref nodeSh node
| otherwise =
let !b = extractByte k nodeSh
in case findByteLinear keys b of
Just !idx ->
let !child' = artInsertWith f k v (indexSmallArray children idx)
in ARTNode4 pref nodeSh keys (replaceSmallSlot children idx child')
Nothing ->
if sizeofPrimArray keys < 4
then
let !keys' = appendByte keys b
!children' = appendSmallSlot children (ARTLeaf k v)
in ARTNode4 pref nodeSh keys' children'
else growNode4To16 pref nodeSh keys children b (ARTLeaf k v)
go !sh node@(ARTNode16 pref nodeSh keys children)
| not (prefixMatch k pref nodeSh) = splitPrefix sh k v pref nodeSh node
| otherwise =
let !b = extractByte k nodeSh
in case findByteLinear keys b of
Just !idx ->
let !child' = artInsertWith f k v (indexSmallArray children idx)
in ARTNode16 pref nodeSh keys (replaceSmallSlot children idx child')
Nothing ->
if sizeofPrimArray keys < 16
then
let !keys' = appendByte keys b
!children' = appendSmallSlot children (ARTLeaf k v)
in ARTNode16 pref nodeSh keys' children'
else growNode16To48 pref nodeSh keys children b (ARTLeaf k v)
go !sh node@(ARTNode48 pref nodeSh dir children)
| not (prefixMatch k pref nodeSh) = splitPrefix sh k v pref nodeSh node
| otherwise =
let !b = extractByte k nodeSh
!slot = indexPrimArray dir (fromIntegral b)
in if slot /= 255
then
let !child' = artInsertWith f k v (indexSmallArray children (fromIntegral slot))
in ARTNode48 pref nodeSh dir (replaceSmallSlot children (fromIntegral slot) child')
else
let !cLen = sizeofSmallArray children
in if cLen < 48
then
let !dir' = updateByte dir (fromIntegral b) (fromIntegral cLen)
!children' = appendSmallSlot children (ARTLeaf k v)
in ARTNode48 pref nodeSh dir' children'
else growNode48To256 pref nodeSh dir children (fromIntegral b) (ARTLeaf k v)
go !sh node@(ARTNode256 pref nodeSh children)
| not (prefixMatch k pref nodeSh) = splitPrefix sh k v pref nodeSh node
| otherwise =
let !b = fromIntegral (extractByte k nodeSh)
!oldChild = indexSmallArray children b
!newChild = case oldChild of
ARTEmpty -> ARTLeaf k v
_ -> artInsertWith f k v oldChild
in ARTNode256 pref nodeSh (replaceSmallSlot children b newChild)
-- | Split two conflicting leaves into a shared prefix branch node.
splitLeaves :: Int -> Int -> a -> Int -> a -> ARTIntMap a
splitLeaves !sh !k1 v1 !k2 v2 =
let go !s
| s < 0 = ARTLeaf k1 v1
| otherwise =
let !b1 = extractByte k1 s
!b2 = extractByte k2 s
in if b1 == b2
then
let !child = go (s - 8)
in ARTNode4 k1 s (primArrayFromList [b1]) (smallArrayFromList [child])
else
let !keys = primArrayFromList [b1, b2]
!vals = smallArrayFromList [ARTLeaf k1 v1, ARTLeaf k2 v2]
in ARTNode4 k1 s keys vals
in go sh
-- | Split a node's path prefix when an incoming key diverges.
splitPrefix :: Int -> Int -> a -> Int -> Int -> ARTIntMap a -> ARTIntMap a
splitPrefix !sh !k v !pref !nodeSh !origNode =
let go !s
| s <= nodeSh = origNode
| otherwise =
let !bNew = extractByte k s
!bNode = extractByte pref s
in if bNew == bNode
then
let !child = go (s - 8)
in ARTNode4 pref s (primArrayFromList [bNode]) (smallArrayFromList [child])
else
let !keys = primArrayFromList [bNew, bNode]
!vals = smallArrayFromList [ARTLeaf k v, origNode]
in ARTNode4 pref s keys vals
in go sh
-- | Expand an overflowing 'ARTNode4' (4 children) into an 'ARTNode16'.
growNode4To16 :: Int -> Int -> PrimArray Word8 -> SmallArray (ARTIntMap a) -> Word8 -> ARTIntMap a -> ARTIntMap a
growNode4To16 !pref !sh !k4 !c4 !newB !newChild =
let !keys16 = appendByte k4 newB
!c16 = appendSmallSlot c4 newChild
in ARTNode16 pref sh keys16 c16
-- | Expand an overflowing 'ARTNode16' (16 children) into an 'ARTNode48'.
growNode16To48 :: Int -> Int -> PrimArray Word8 -> SmallArray (ARTIntMap a) -> Word8 -> ARTIntMap a -> ARTIntMap a
growNode16To48 !pref !sh !k16 !c16 !newB !newChild =
let !dir = runST $ do
m <- newPrimArray 256
setPrimArray m 0 256 (255 :: Word8)
let !n = sizeofPrimArray k16
let loop !i
| i >= n = pure ()
| otherwise = do
let !b = indexPrimArray k16 i
writePrimArray m (fromIntegral b) (fromIntegral i :: Word8)
loop (i + 1)
loop 0
writePrimArray m (fromIntegral newB) (fromIntegral n :: Word8)
unsafeFreezePrimArray m
!c48 = appendSmallSlot c16 newChild
in ARTNode48 pref sh dir c48
-- | Expand an overflowing 'ARTNode48' (48 children) into an 'ARTNode256'.
growNode48To256 :: Int -> Int -> PrimArray Word8 -> SmallArray (ARTIntMap a) -> Int -> ARTIntMap a -> ARTIntMap a
growNode48To256 !pref !sh !dir !children !newB !newChild =
let !arr256 = runST $ do
m <- newSmallArray 256 ARTEmpty
let loop !b
| b >= 256 = do
writeSmallArray m newB newChild
unsafeFreezeSmallArray m
| otherwise = do
let !slot = fromIntegral (indexPrimArray dir b) :: Int
when (slot /= 255) $
writeSmallArray m b (indexSmallArray children slot)
loop (b + 1)
loop 0
in ARTNode256 pref sh arr256
-- | Delete a key and its associated value from the Adaptive Radix Tree.
--
-- Running time: \(O(n)\) via rebuild.
artDelete :: Int -> ARTIntMap a -> ARTIntMap a
artDelete !target m =
artFromList [ (k, v) | (k, v) <- artToList m, k /= target ]
-- | Convert an Adaptive Radix Tree into a list of key-value associations.
--
-- Running time: \(O(n)\).
artToList :: ARTIntMap a -> [(Int, a)]
artToList ARTEmpty = []
artToList (ARTLeaf k v) = [(k, v)]
artToList (ARTNode4 _ _ _ children) = concatMap artToList (smallToList children)
artToList (ARTNode16 _ _ _ children) = concatMap artToList (smallToList children)
artToList (ARTNode48 _ _ _ children) = concatMap artToList (smallToList children)
artToList (ARTNode256 _ _ children) = concatMap artToList (smallToList children)
-- | Construct an Adaptive Radix Tree from a list of key-value associations.
--
-- Running time: \(O(n \cdot k)\).
artFromList :: [(Int, a)] -> ARTIntMap a
artFromList = foldl' (\acc (k, v) -> artInsert k v acc) emptyART
-- | Extract all keys in the tree into a compressed 'RoaringIntSet'.
--
-- Running time: \(O(n)\).
artKeysSet :: ARTIntMap a -> RoaringIntSet
artKeysSet !m = fromListRoaring (map fst (artToList m))
-- | Linear search for byte 'b' in primitive array.
findByteLinear :: PrimArray Word8 -> Word8 -> Maybe Int
findByteLinear !arr !b =
let !n = sizeofPrimArray arr
go !i
| i >= n = Nothing
| indexPrimArray arr i == b = Just i
| otherwise = go (i + 1)
in go 0
-- | Append a single byte to an immutable primitive array.
appendByte :: PrimArray Word8 -> Word8 -> PrimArray Word8
appendByte !arr !b = runST $ do
let !n = sizeofPrimArray arr
m <- newPrimArray (n + 1)
copyPrimArray m 0 arr 0 n
writePrimArray m n b
unsafeFreezePrimArray m
-- | Update a single byte in a primitive array.
updateByte :: PrimArray Word8 -> Int -> Word8 -> PrimArray Word8
updateByte !arr !idx !val = runST $ do
let !n = sizeofPrimArray arr
m <- thawPrimArray arr 0 n
writePrimArray m idx val
unsafeFreezePrimArray m
-- | Replace a slot in an immutable SmallArray.
replaceSmallSlot :: SmallArray a -> Int -> a -> SmallArray a
replaceSmallSlot !arr !idx !val = runST $ do
let !n = sizeofSmallArray arr
m <- thawSmallArray arr 0 n
writeSmallArray m idx val
unsafeFreezeSmallArray m
-- | Append a slot to an immutable SmallArray.
appendSmallSlot :: SmallArray a -> a -> SmallArray a
appendSmallSlot !arr !val = runST $ do
let !n = sizeofSmallArray arr
m <- newSmallArray (n + 1) val
copySmallArray m 0 arr 0 n
unsafeFreezeSmallArray m
-- | Convert an immutable SmallArray to a list.
smallToList :: SmallArray a -> [a]
smallToList !arr = [ indexSmallArray arr i | i <- [0 .. sizeofSmallArray arr - 1] ]