module Regex.Internal.Unique
  ( Unique(..)
  , UniqueSet
  , empty
  , member
  , insert
  ) where

import Data.Bits
import qualified Data.IntSet as IS

-- | A unique ID. Must be >= 0.
newtype Unique = Unique { Unique -> Int
unUnique :: Int }

-- | A set of 'Unique's. The bitmask is a set for IDs 0..63 (0..31 if 32-bit).
-- Set operations on this are very fast and speed up the common case of small
-- regexes a little bit, at the cost of a little more memory.
data UniqueSet = UniqueSet {-# UNPACK #-} !Int !IS.IntSet

empty :: UniqueSet
empty :: UniqueSet
empty = Int -> IntSet -> UniqueSet
UniqueSet Int
0 IntSet
IS.empty

member :: Unique -> UniqueSet -> Bool
member :: Unique -> UniqueSet -> Bool
member (Unique Int
u) (UniqueSet Int
m IntSet
is)
  | Int
u Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (Int
0 :: Int) = Int
m Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. (Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
u) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0
  | Bool
otherwise = Int
u Int -> IntSet -> Bool
`IS.member` IntSet
is

insert :: Unique -> UniqueSet -> UniqueSet
insert :: Unique -> UniqueSet -> UniqueSet
insert (Unique Int
u) (UniqueSet Int
m IntSet
is)
  | Int
u Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (Int
0 :: Int) = Int -> IntSet -> UniqueSet
UniqueSet (Int
m Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`unsafeShiftL` Int
u)) IntSet
is
  | Bool
otherwise = Int -> IntSet -> UniqueSet
UniqueSet Int
m (Int -> IntSet -> IntSet
IS.insert Int
u IntSet
is)