findhole.hs

import Data.Bits (clearBit, testBit)
import Data.Foldable (foldl')

data FindHoleError = MaxTooBig deriving (Show)

findholes :: Integer -> Integer -> [Int] -> Either FindHoleError [Int]
findholes min max xs
  | max < (fromIntegral (maxBound :: Int)) = Right $ map (+ imin) (findholes' mask $ map (+ (-imin)) xs)
  | otherwise = Left MaxTooBig
  where
    mask = (2 ^ (max - min + 1)) - 1
    imin = fromIntegral min

findholes' :: Integer -> [Int] -> [Int]
findholes' mask xs = unmask $ foldl' clearBit mask xs

unmask mask = filter (testBit mask) [0..maxbit]
  where
    maxbit = floor (logBase 2 $ fromIntegral mask)


-- > findhole 100 1025 ([102..944]++[946..1023]++[102,101])
-- Right [100,945,1024,1025]