{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE GeneralizedNewtypeDeriving#-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE RoleAnnotations #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE MonoLocalBinds #-}
{-# OPTIONS_GHC -fno-cse #-}
{-# OPTIONS_GHC -fno-full-laziness #-}
{-# OPTIONS_GHC -fno-float-in #-}
{-# OPTIONS_GHC -Wno-unused-binds #-}
module Data.HyperLogLog.Type
(
HyperLogLog(..)
, HasHyperLogLog(..)
, size
, insert
, insertHash
, intersectionSize
, cast
, coerceConfig
) where
import Control.DeepSeq (NFData (..))
import Control.Lens
import Control.Monad
import Crypto.MAC.SipHash
import Data.Approximate.Type
import Data.Bits.Extras
import qualified Data.Binary as Binary
import Data.Binary
import Data.Bytes.Put (runPutS)
import Data.Bytes.Serial
import Data.HyperLogLog.Config
import Data.Proxy
import Data.Reflection
import Data.Serialize as Serialize
import Data.Type.Coercion (Coercion(..))
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV
import GHC.Generics hiding (D, to)
import GHC.Int
#if !(MIN_VERSION_base(4,11,0))
import Data.Semigroup (Semigroup(..))
#endif
newtype HyperLogLog p = HyperLogLog { HyperLogLog p -> Vector Rank
runHyperLogLog :: V.Vector Rank }
deriving (HyperLogLog p -> HyperLogLog p -> Bool
(HyperLogLog p -> HyperLogLog p -> Bool)
-> (HyperLogLog p -> HyperLogLog p -> Bool) -> Eq (HyperLogLog p)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k (p :: k). HyperLogLog p -> HyperLogLog p -> Bool
/= :: HyperLogLog p -> HyperLogLog p -> Bool
$c/= :: forall k (p :: k). HyperLogLog p -> HyperLogLog p -> Bool
== :: HyperLogLog p -> HyperLogLog p -> Bool
$c== :: forall k (p :: k). HyperLogLog p -> HyperLogLog p -> Bool
Eq, Int -> HyperLogLog p -> ShowS
[HyperLogLog p] -> ShowS
HyperLogLog p -> String
(Int -> HyperLogLog p -> ShowS)
-> (HyperLogLog p -> String)
-> ([HyperLogLog p] -> ShowS)
-> Show (HyperLogLog p)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k (p :: k). Int -> HyperLogLog p -> ShowS
forall k (p :: k). [HyperLogLog p] -> ShowS
forall k (p :: k). HyperLogLog p -> String
showList :: [HyperLogLog p] -> ShowS
$cshowList :: forall k (p :: k). [HyperLogLog p] -> ShowS
show :: HyperLogLog p -> String
$cshow :: forall k (p :: k). HyperLogLog p -> String
showsPrec :: Int -> HyperLogLog p -> ShowS
$cshowsPrec :: forall k (p :: k). Int -> HyperLogLog p -> ShowS
Show, (forall x. HyperLogLog p -> Rep (HyperLogLog p) x)
-> (forall x. Rep (HyperLogLog p) x -> HyperLogLog p)
-> Generic (HyperLogLog p)
forall x. Rep (HyperLogLog p) x -> HyperLogLog p
forall x. HyperLogLog p -> Rep (HyperLogLog p) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k (p :: k) x. Rep (HyperLogLog p) x -> HyperLogLog p
forall k (p :: k) x. HyperLogLog p -> Rep (HyperLogLog p) x
$cto :: forall k (p :: k) x. Rep (HyperLogLog p) x -> HyperLogLog p
$cfrom :: forall k (p :: k) x. HyperLogLog p -> Rep (HyperLogLog p) x
Generic, HyperLogLog p -> ()
(HyperLogLog p -> ()) -> NFData (HyperLogLog p)
forall a. (a -> ()) -> NFData a
forall k (p :: k). HyperLogLog p -> ()
rnf :: HyperLogLog p -> ()
$crnf :: forall k (p :: k). HyperLogLog p -> ()
NFData)
type role HyperLogLog nominal
coerceConfig :: forall p q . (Reifies p Integer, Reifies q Integer) => Maybe (Coercion (HyperLogLog p) (HyperLogLog q))
coerceConfig :: Maybe (Coercion (HyperLogLog p) (HyperLogLog q))
coerceConfig | Proxy p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect (Proxy p
forall k (t :: k). Proxy t
Proxy :: Proxy p) Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Proxy q -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect (Proxy q
forall k (t :: k). Proxy t
Proxy :: Proxy q) = Coercion (HyperLogLog p) (HyperLogLog q)
-> Maybe (Coercion (HyperLogLog p) (HyperLogLog q))
forall a. a -> Maybe a
Just Coercion (HyperLogLog p) (HyperLogLog q)
forall k (a :: k) (b :: k). Coercible a b => Coercion a b
Coercion
| Bool
otherwise = Maybe (Coercion (HyperLogLog p) (HyperLogLog q))
forall a. Maybe a
Nothing
instance Serialize (HyperLogLog p)
instance Serial (HyperLogLog p) where
serialize :: HyperLogLog p -> m ()
serialize (HyperLogLog Vector Rank
v) = [Rank] -> m ()
forall a (m :: * -> *). (Serial a, MonadPut m) => a -> m ()
serialize (Vector Rank -> [Rank]
forall a. Unbox a => Vector a -> [a]
V.toList Vector Rank
v)
deserialize :: m (HyperLogLog p)
deserialize = ([Rank] -> HyperLogLog p) -> m [Rank] -> m (HyperLogLog p)
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM (Vector Rank -> HyperLogLog p
forall k (p :: k). Vector Rank -> HyperLogLog p
HyperLogLog (Vector Rank -> HyperLogLog p)
-> ([Rank] -> Vector Rank) -> [Rank] -> HyperLogLog p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Rank] -> Vector Rank
forall a. Unbox a => [a] -> Vector a
V.fromList) m [Rank]
forall a (m :: * -> *). (Serial a, MonadGet m) => m a
deserialize
instance Binary (HyperLogLog p) where
put :: HyperLogLog p -> Put
put (HyperLogLog Vector Rank
v) = [Rank] -> Put
forall t. Binary t => t -> Put
Binary.put (Vector Rank -> [Rank]
forall a. Unbox a => Vector a -> [a]
V.toList Vector Rank
v)
get :: Get (HyperLogLog p)
get = ([Rank] -> HyperLogLog p) -> Get [Rank] -> Get (HyperLogLog p)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Vector Rank -> HyperLogLog p
forall k (p :: k). Vector Rank -> HyperLogLog p
HyperLogLog (Vector Rank -> HyperLogLog p)
-> ([Rank] -> Vector Rank) -> [Rank] -> HyperLogLog p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Rank] -> Vector Rank
forall a. Unbox a => [a] -> Vector a
V.fromList) Get [Rank]
forall t. Binary t => Get t
Binary.get
class HasHyperLogLog a p | a -> p where
hyperLogLog :: Lens' a (HyperLogLog p)
instance HasHyperLogLog (HyperLogLog p) p where
hyperLogLog :: (HyperLogLog p -> f (HyperLogLog p))
-> HyperLogLog p -> f (HyperLogLog p)
hyperLogLog = (HyperLogLog p -> f (HyperLogLog p))
-> HyperLogLog p -> f (HyperLogLog p)
forall a. a -> a
id
_HyperLogLog :: Iso' (HyperLogLog p) (V.Vector Rank)
_HyperLogLog :: p (Vector Rank) (f (Vector Rank))
-> p (HyperLogLog p) (f (HyperLogLog p))
_HyperLogLog = (HyperLogLog p -> Vector Rank)
-> (Vector Rank -> HyperLogLog p)
-> Iso (HyperLogLog p) (HyperLogLog p) (Vector Rank) (Vector Rank)
forall s a b t. (s -> a) -> (b -> t) -> Iso s t a b
iso HyperLogLog p -> Vector Rank
forall k (p :: k). HyperLogLog p -> Vector Rank
runHyperLogLog Vector Rank -> HyperLogLog p
forall k (p :: k). Vector Rank -> HyperLogLog p
HyperLogLog
{-# INLINE _HyperLogLog #-}
instance Semigroup (HyperLogLog p) where
HyperLogLog Vector Rank
a <> :: HyperLogLog p -> HyperLogLog p -> HyperLogLog p
<> HyperLogLog Vector Rank
b = Vector Rank -> HyperLogLog p
forall k (p :: k). Vector Rank -> HyperLogLog p
HyperLogLog ((Rank -> Rank -> Rank) -> Vector Rank -> Vector Rank -> Vector Rank
forall a b c.
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector a -> Vector b -> Vector c
V.zipWith Rank -> Rank -> Rank
forall a. Ord a => a -> a -> a
max Vector Rank
a Vector Rank
b)
{-# INLINE (<>) #-}
instance Reifies p Integer => Monoid (HyperLogLog p) where
mempty :: HyperLogLog p
mempty = Vector Rank -> HyperLogLog p
forall k (p :: k). Vector Rank -> HyperLogLog p
HyperLogLog (Vector Rank -> HyperLogLog p) -> Vector Rank -> HyperLogLog p
forall a b. (a -> b) -> a -> b
$ Int -> Rank -> Vector Rank
forall a. Unbox a => Int -> a -> Vector a
V.replicate (Integer -> Int
numBuckets (Proxy p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect (Proxy p
forall k (t :: k). Proxy t
Proxy :: Proxy p))) Rank
0
{-# INLINE mempty #-}
mappend :: HyperLogLog p -> HyperLogLog p -> HyperLogLog p
mappend = HyperLogLog p -> HyperLogLog p -> HyperLogLog p
forall a. Semigroup a => a -> a -> a
(<>)
{-# INLINE mappend #-}
sipKey :: SipKey
sipKey :: SipKey
sipKey = Word64 -> Word64 -> SipKey
SipKey Word64
4 Word64
7
siphash :: Serial a => a -> Word64
siphash :: a -> Word64
siphash a
a = Word64
h
where !bs :: ByteString
bs = Put -> ByteString
runPutS (a -> Put
forall a (m :: * -> *). (Serial a, MonadPut m) => a -> m ()
serialize a
a)
(SipHash !Word64
h) = SipKey -> ByteString -> SipHash
hash SipKey
sipKey ByteString
bs
{-# INLINE siphash #-}
insert :: (Reifies s Integer, Serial a) => a -> HyperLogLog s -> HyperLogLog s
insert :: a -> HyperLogLog s -> HyperLogLog s
insert = Word32 -> HyperLogLog s -> HyperLogLog s
forall k (s :: k).
Reifies s Integer =>
Word32 -> HyperLogLog s -> HyperLogLog s
insertHash (Word32 -> HyperLogLog s -> HyperLogLog s)
-> (a -> Word32) -> a -> HyperLogLog s -> HyperLogLog s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64 -> Word32
forall a. Integral a => a -> Word32
w32 (Word64 -> Word32) -> (a -> Word64) -> a -> Word32
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Word64
forall a. Serial a => a -> Word64
siphash
{-# INLINE insert #-}
insertHash :: Reifies s Integer => Word32 -> HyperLogLog s -> HyperLogLog s
insertHash :: Word32 -> HyperLogLog s -> HyperLogLog s
insertHash Word32
h m :: HyperLogLog s
m@(HyperLogLog Vector Rank
v) = Vector Rank -> HyperLogLog s
forall k (p :: k). Vector Rank -> HyperLogLog p
HyperLogLog (Vector Rank -> HyperLogLog s) -> Vector Rank -> HyperLogLog s
forall a b. (a -> b) -> a -> b
$ (forall s. MVector s Rank -> ST s ()) -> Vector Rank -> Vector Rank
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
V.modify (\MVector s Rank
x -> do
Rank
old <- MVector (PrimState (ST s)) Rank -> Int -> ST s Rank
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
MV.read MVector s Rank
MVector (PrimState (ST s)) Rank
x Int
bk
Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Rank
rnk Rank -> Rank -> Bool
forall a. Ord a => a -> a -> Bool
> Rank
old) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST s)) Rank -> Int -> Rank -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
MV.write MVector s Rank
MVector (PrimState (ST s)) Rank
x Int
bk Rank
rnk
) Vector Rank
v where
!n :: Integer
n = HyperLogLog s -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect HyperLogLog s
m
!bk :: Int
bk = Integer -> Word32 -> Int
calcBucket Integer
n Word32
h
!rnk :: Rank
rnk = Integer -> Word32 -> Rank
calcRank Integer
n Word32
h
{-# INLINE insertHash #-}
size :: Reifies p Integer => HyperLogLog p -> Approximate Int64
size :: HyperLogLog p -> Approximate Int64
size m :: HyperLogLog p
m@(HyperLogLog Vector Rank
bs) = Log Double -> Int64 -> Int64 -> Int64 -> Approximate Int64
forall a. Log Double -> a -> a -> a -> Approximate a
Approximate Log Double
0.9972 Int64
l Int64
expected Int64
h where
n :: Integer
n = HyperLogLog p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect HyperLogLog p
m
m' :: Double
m' = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Integer -> Int
numBuckets Integer
n)
numZeros :: Double
numZeros = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Double) -> (Vector Rank -> Int) -> Vector Rank -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector Rank -> Int
forall a. Unbox a => Vector a -> Int
V.length (Vector Rank -> Int)
-> (Vector Rank -> Vector Rank) -> Vector Rank -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Rank -> Bool) -> Vector Rank -> Vector Rank
forall a. Unbox a => (a -> Bool) -> Vector a -> Vector a
V.filter (Rank -> Rank -> Bool
forall a. Eq a => a -> a -> Bool
== Rank
0) (Vector Rank -> Double) -> Vector Rank -> Double
forall a b. (a -> b) -> a -> b
$ Vector Rank
bs
res :: Double
res = case Double
raw Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
< Integer -> Double
smallRange Integer
n of
Bool
True | Double
numZeros Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
0 -> Double
m' Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double -> Double
forall a. Floating a => a -> a
log (Double
m' Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
numZeros)
| Bool
otherwise -> Double
raw
Bool
False | Double
raw Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
<= Double
interRange -> Double
raw
| Bool
otherwise -> Double
raw Double -> Double -> Double
forall a. Num a => a -> a -> a
+ (Double
raw Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
lim32) Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
raw
raw :: Double
raw = Integer -> Double
rawFact Integer
n Double -> Double -> Double
forall a. Num a => a -> a -> a
* (Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
sm)
sm :: Double
sm = Vector Double -> Double
forall a. (Unbox a, Num a) => Vector a -> a
V.sum (Vector Double -> Double) -> Vector Double -> Double
forall a b. (a -> b) -> a -> b
$ (Rank -> Double) -> Vector Rank -> Vector Double
forall a b. (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
V.map (\Rank
x -> Double
1 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ (Double
2 Double -> Rank -> Double
forall a b. (Fractional a, Integral b) => a -> b -> a
^^ Rank
x)) Vector Rank
bs
expected :: Int64
expected = Double -> Int64
forall a b. (RealFrac a, Integral b) => a -> b
round Double
res
sd :: Double
sd = Double
1.04 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double -> Double
forall a. Floating a => a -> a
sqrt Double
m'
l :: Int64
l = Double -> Int64
forall a b. (RealFrac a, Integral b) => a -> b
floor (Double -> Int64) -> Double -> Int64
forall a b. (a -> b) -> a -> b
$ Double -> Double -> Double
forall a. Ord a => a -> a -> a
max (Double
resDouble -> Double -> Double
forall a. Num a => a -> a -> a
*(Double
1Double -> Double -> Double
forall a. Num a => a -> a -> a
-Double
3Double -> Double -> Double
forall a. Num a => a -> a -> a
*Double
sd)) Double
0
h :: Int64
h = Double -> Int64
forall a b. (RealFrac a, Integral b) => a -> b
ceiling (Double -> Int64) -> Double -> Int64
forall a b. (a -> b) -> a -> b
$ Double
resDouble -> Double -> Double
forall a. Num a => a -> a -> a
*(Double
1Double -> Double -> Double
forall a. Num a => a -> a -> a
+Double
3Double -> Double -> Double
forall a. Num a => a -> a -> a
*Double
sd)
{-# INLINE size #-}
#ifdef HERBIE
{-# ANN size "NoHerbie" #-}
#endif
intersectionSize :: Reifies p Integer => [HyperLogLog p] -> Approximate Int64
intersectionSize :: [HyperLogLog p] -> Approximate Int64
intersectionSize [] = Approximate Int64
0
intersectionSize (HyperLogLog p
x:[HyperLogLog p]
xs) = Int64 -> Approximate Int64 -> Approximate Int64
forall a. Ord a => a -> Approximate a -> Approximate a
withMin Int64
0 (Approximate Int64 -> Approximate Int64)
-> Approximate Int64 -> Approximate Int64
forall a b. (a -> b) -> a -> b
$ HyperLogLog p -> Approximate Int64
forall k (p :: k).
Reifies p Integer =>
HyperLogLog p -> Approximate Int64
size HyperLogLog p
x Approximate Int64 -> Approximate Int64 -> Approximate Int64
forall a. Num a => a -> a -> a
+ [HyperLogLog p] -> Approximate Int64
forall k (p :: k).
Reifies p Integer =>
[HyperLogLog p] -> Approximate Int64
intersectionSize [HyperLogLog p]
xs Approximate Int64 -> Approximate Int64 -> Approximate Int64
forall a. Num a => a -> a -> a
- [HyperLogLog p] -> Approximate Int64
forall k (p :: k).
Reifies p Integer =>
[HyperLogLog p] -> Approximate Int64
intersectionSize (HyperLogLog p -> HyperLogLog p -> HyperLogLog p
forall a. Monoid a => a -> a -> a
mappend HyperLogLog p
x (HyperLogLog p -> HyperLogLog p)
-> [HyperLogLog p] -> [HyperLogLog p]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [HyperLogLog p]
xs)
{-# INLINE intersectionSize #-}
cast :: forall p q. (Reifies p Integer, Reifies q Integer) => HyperLogLog p -> Maybe (HyperLogLog q)
cast :: HyperLogLog p -> Maybe (HyperLogLog q)
cast HyperLogLog p
old
| Int
newBuckets Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
oldBuckets = HyperLogLog q -> Maybe (HyperLogLog q)
forall a. a -> Maybe a
Just (HyperLogLog q -> Maybe (HyperLogLog q))
-> HyperLogLog q -> Maybe (HyperLogLog q)
forall a b. (a -> b) -> a -> b
$ ASetter (HyperLogLog q) (HyperLogLog q) (Vector Rank) (Vector Rank)
-> (Vector Rank -> Vector Rank) -> HyperLogLog q -> HyperLogLog q
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
over ASetter (HyperLogLog q) (HyperLogLog q) (Vector Rank) (Vector Rank)
forall k (p :: k). Iso' (HyperLogLog p) (Vector Rank)
_HyperLogLog ((Vector Rank -> Vector Rank) -> HyperLogLog q -> HyperLogLog q)
-> HyperLogLog q -> (Vector Rank -> Vector Rank) -> HyperLogLog q
forall (f :: * -> *) a b. Functor f => f (a -> b) -> a -> f b
?? HyperLogLog q
forall a. Monoid a => a
mempty ((Vector Rank -> Vector Rank) -> HyperLogLog q)
-> (Vector Rank -> Vector Rank) -> HyperLogLog q
forall a b. (a -> b) -> a -> b
$ (forall s. MVector s Rank -> ST s ()) -> Vector Rank -> Vector Rank
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
V.modify ((forall s. MVector s Rank -> ST s ())
-> Vector Rank -> Vector Rank)
-> (forall s. MVector s Rank -> ST s ())
-> Vector Rank
-> Vector Rank
forall a b. (a -> b) -> a -> b
$ \MVector s Rank
m ->
Vector (Int, Rank) -> ((Int, Rank) -> ST s ()) -> ST s ()
forall (m :: * -> *) a b.
(Monad m, Unbox a) =>
Vector a -> (a -> m b) -> m ()
V.forM_ (Vector Rank -> Vector (Int, Rank)
forall a. Unbox a => Vector a -> Vector (Int, a)
V.indexed (Vector Rank -> Vector (Int, Rank))
-> Vector Rank -> Vector (Int, Rank)
forall a b. (a -> b) -> a -> b
$ HyperLogLog p
oldHyperLogLog p
-> Getting (Vector Rank) (HyperLogLog p) (Vector Rank)
-> Vector Rank
forall s a. s -> Getting a s a -> a
^.Getting (Vector Rank) (HyperLogLog p) (Vector Rank)
forall k (p :: k). Iso' (HyperLogLog p) (Vector Rank)
_HyperLogLog) (((Int, Rank) -> ST s ()) -> ST s ())
-> ((Int, Rank) -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \ (Int
i,Rank
o) -> do
let j :: Int
j = Int -> Int -> Int
forall a. Integral a => a -> a -> a
mod Int
i Int
newBuckets
Rank
a <- MVector (PrimState (ST s)) Rank -> Int -> ST s Rank
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
MV.read MVector s Rank
MVector (PrimState (ST s)) Rank
m Int
j
MVector (PrimState (ST s)) Rank -> Int -> Rank -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
MV.write MVector s Rank
MVector (PrimState (ST s)) Rank
m Int
j (Rank -> Rank -> Rank
forall a. Ord a => a -> a -> a
max Rank
o Rank
a)
| Bool
otherwise = Maybe (HyperLogLog q)
forall a. Maybe a
Nothing
where
newBuckets :: Int
newBuckets = Integer -> Int
numBuckets (Proxy q -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect (Proxy q
forall k (t :: k). Proxy t
Proxy :: Proxy q))
oldBuckets :: Int
oldBuckets = Integer -> Int
numBuckets (HyperLogLog p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect HyperLogLog p
old)
{-# INLINE cast #-}