module Radix.Word8.Foundation ( Key , Prefix , Mask , beyond , upper , lower , zeroBit , mask , branchingBit ) where import Data.Bits import Data.Word -- | Key as stored in the data structure. type Key = Word8 -- | Part of the 'Key' from the largest bit to the 'Mask' bit, plus the 'Mask' bit. type Prefix = Word8 {-# INLINE beyond #-} -- | \(\mathcal{O}(1)\). -- Whether the key does not match the prefix. beyond :: Prefix -> Key -> Bool beyond p k = (k `xor` p) .&. (p `xor` negate p) /= 0 {-# INLINE upper #-} -- | \(\mathcal{O}(1)\). -- Largest key that can reside under this prefix. upper :: Prefix -> Key upper p = p .|. (p - 1) {-# INLINE lower #-} -- | \(\mathcal{O}(1)\). -- Smallest key that can reside under this prefix. lower :: Prefix -> Key lower p = p .&. (p - 1) -- | Masking bit. type Mask = Word8 {-# INLINE zeroBit #-} -- | Get the state of the masked bit from the 'Key'. zeroBit :: Key -> Mask -> Bool zeroBit k m = (k .&. m) == 0 {-# INLINE mask #-} -- | Trim the 'Key' down to a 'Prefix'. mask :: Key -> Mask -> Prefix mask k m = k .&. (negate m `xor` m) {-# INLINE branchingBit #-} -- | Finds the bit the two 'Prefix'es disagree on. branchingBit :: Prefix -> Prefix -> Mask branchingBit p o = 1 `unsafeShiftL` (7 - countLeadingZeros (p `xor` o))