{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE DeriveGeneric #-}
module DataSketches.Quantiles.RelativeErrorQuantile (
ReqSketch (criterion)
, mkReqSketch
, RankAccuracy(..)
, Criterion(..)
, count
, null
, sum
, maximum
, minimum
, retainedItemCount
, relativeStandardError
, countWithCriterion
, probabilityMassFunction
, quantile
, quantiles
, rank
, rankLowerBound
, ranks
, rankUpperBound
, cumulativeDistributionFunction
, getK
, merge
, insert
, rankAccuracy
, isEstimationMode
, isLessThanOrEqual
, CumulativeDistributionInvariants(..)
, mkAuxiliaryFromReqSketch
, computeTotalRetainedItems
) where
import Control.DeepSeq
import Control.Monad (when, unless, foldM, foldM_)
import Control.Monad.Primitive
import Control.Monad.Trans
import Data.Bits (shiftL)
import Data.Vector ((!), imapM_)
import qualified Data.Vector as Vector
import Data.Primitive.MutVar
import Data.Proxy
import Data.Word
import DataSketches.Quantiles.RelativeErrorQuantile.Internal.Constants
import DataSketches.Quantiles.RelativeErrorQuantile.Types
import DataSketches.Quantiles.RelativeErrorQuantile.Internal.Compactor (ReqCompactor)
import DataSketches.Quantiles.RelativeErrorQuantile.Internal.Auxiliary (ReqAuxiliary)
import qualified DataSketches.Quantiles.RelativeErrorQuantile.Internal.Auxiliary as Auxiliary
import qualified DataSketches.Quantiles.RelativeErrorQuantile.Internal.Compactor as Compactor
import qualified DataSketches.Quantiles.RelativeErrorQuantile.Internal.DoubleBuffer as DoubleBuffer
import DataSketches.Quantiles.RelativeErrorQuantile.Internal.URef
import GHC.TypeLits
import Data.Maybe (isNothing)
import qualified Data.Foldable
import qualified Data.List
import GHC.Exception.Type (Exception)
import Control.Exception (throw, assert)
import GHC.Generics
import System.Random.MWC (Gen, create)
import qualified Data.Vector.Generic.Mutable as MG
import Prelude hiding (sum, minimum, maximum, null)
data ReqSketch s = ReqSketch
{ ReqSketch s -> Word32
k :: !Word32
, ReqSketch s -> RankAccuracy
rankAccuracySetting :: !RankAccuracy
, ReqSketch s -> Criterion
criterion :: !Criterion
, ReqSketch s -> Gen s
sketchRng :: {-# UNPACK #-} !(Gen s)
, ReqSketch s -> URef s Word64
totalN :: {-# UNPACK #-} !(URef s Word64)
, ReqSketch s -> URef s Double
minValue :: {-# UNPACK #-} !(URef s Double)
, ReqSketch s -> URef s Double
maxValue :: {-# UNPACK #-} !(URef s Double)
, ReqSketch s -> URef s Double
sumValue :: {-# UNPACK #-} !(URef s Double)
, ReqSketch s -> URef s Int
retainedItems :: {-# UNPACK #-} !(URef s Int)
, ReqSketch s -> URef s Int
maxNominalCapacitiesSize :: {-# UNPACK #-} !(URef s Int)
, ReqSketch s -> MutVar s (Maybe ReqAuxiliary)
aux :: {-# UNPACK #-} !(MutVar s (Maybe ReqAuxiliary))
, ReqSketch s -> MutVar s (Vector (ReqCompactor s))
compactors :: {-# UNPACK #-} !(MutVar s (Vector.Vector (ReqCompactor s)))
} deriving ((forall x. ReqSketch s -> Rep (ReqSketch s) x)
-> (forall x. Rep (ReqSketch s) x -> ReqSketch s)
-> Generic (ReqSketch s)
forall x. Rep (ReqSketch s) x -> ReqSketch s
forall x. ReqSketch s -> Rep (ReqSketch s) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall s x. Rep (ReqSketch s) x -> ReqSketch s
forall s x. ReqSketch s -> Rep (ReqSketch s) x
$cto :: forall s x. Rep (ReqSketch s) x -> ReqSketch s
$cfrom :: forall s x. ReqSketch s -> Rep (ReqSketch s) x
Generic)
instance NFData (ReqSketch s) where
rnf :: ReqSketch s -> ()
rnf !ReqSketch s
rs = ()
instance TakeSnapshot ReqSketch where
data Snapshot ReqSketch = ReqSketchSnapshot
{ Snapshot ReqSketch -> RankAccuracy
snapshotRankAccuracySetting :: !RankAccuracy
, Snapshot ReqSketch -> Criterion
snapshotCriterion :: !Criterion
, Snapshot ReqSketch -> Word64
snapshotTotalN :: !Word64
, Snapshot ReqSketch -> Double
snapshotMinValue :: !Double
, Snapshot ReqSketch -> Double
snapshotMaxValue :: !Double
, Snapshot ReqSketch -> Int
snapshotRetainedItems :: !Int
, Snapshot ReqSketch -> Int
snapshotMaxNominalCapacitiesSize :: !Int
, Snapshot ReqSketch -> Vector (Snapshot ReqCompactor)
snapshotCompactors :: !(Vector.Vector (Snapshot ReqCompactor))
}
takeSnapshot :: ReqSketch (PrimState m) -> m (Snapshot ReqSketch)
takeSnapshot ReqSketch{Word32
Gen (PrimState m)
MutVar (PrimState m) (Maybe ReqAuxiliary)
MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
URef (PrimState m) Double
URef (PrimState m) Int
URef (PrimState m) Word64
RankAccuracy
Criterion
compactors :: MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
aux :: MutVar (PrimState m) (Maybe ReqAuxiliary)
maxNominalCapacitiesSize :: URef (PrimState m) Int
retainedItems :: URef (PrimState m) Int
sumValue :: URef (PrimState m) Double
maxValue :: URef (PrimState m) Double
minValue :: URef (PrimState m) Double
totalN :: URef (PrimState m) Word64
sketchRng :: Gen (PrimState m)
criterion :: Criterion
rankAccuracySetting :: RankAccuracy
k :: Word32
compactors :: forall s. ReqSketch s -> MutVar s (Vector (ReqCompactor s))
aux :: forall s. ReqSketch s -> MutVar s (Maybe ReqAuxiliary)
maxNominalCapacitiesSize :: forall s. ReqSketch s -> URef s Int
retainedItems :: forall s. ReqSketch s -> URef s Int
sumValue :: forall s. ReqSketch s -> URef s Double
maxValue :: forall s. ReqSketch s -> URef s Double
minValue :: forall s. ReqSketch s -> URef s Double
totalN :: forall s. ReqSketch s -> URef s Word64
sketchRng :: forall s. ReqSketch s -> Gen s
rankAccuracySetting :: forall s. ReqSketch s -> RankAccuracy
k :: forall s. ReqSketch s -> Word32
criterion :: forall s. ReqSketch s -> Criterion
..} = RankAccuracy
-> Criterion
-> Word64
-> Double
-> Double
-> Int
-> Int
-> Vector (Snapshot ReqCompactor)
-> Snapshot ReqSketch
ReqSketchSnapshot RankAccuracy
rankAccuracySetting Criterion
criterion
(Word64
-> Double
-> Double
-> Int
-> Int
-> Vector (Snapshot ReqCompactor)
-> Snapshot ReqSketch)
-> m Word64
-> m (Double
-> Double
-> Int
-> Int
-> Vector (Snapshot ReqCompactor)
-> Snapshot ReqSketch)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> URef (PrimState m) Word64 -> m Word64
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef URef (PrimState m) Word64
totalN
m (Double
-> Double
-> Int
-> Int
-> Vector (Snapshot ReqCompactor)
-> Snapshot ReqSketch)
-> m Double
-> m (Double
-> Int
-> Int
-> Vector (Snapshot ReqCompactor)
-> Snapshot ReqSketch)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> URef (PrimState m) Double -> m Double
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef URef (PrimState m) Double
minValue
m (Double
-> Int
-> Int
-> Vector (Snapshot ReqCompactor)
-> Snapshot ReqSketch)
-> m Double
-> m (Int
-> Int -> Vector (Snapshot ReqCompactor) -> Snapshot ReqSketch)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> URef (PrimState m) Double -> m Double
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef URef (PrimState m) Double
maxValue
m (Int
-> Int -> Vector (Snapshot ReqCompactor) -> Snapshot ReqSketch)
-> m Int
-> m (Int -> Vector (Snapshot ReqCompactor) -> Snapshot ReqSketch)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> URef (PrimState m) Int -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef URef (PrimState m) Int
retainedItems
m (Int -> Vector (Snapshot ReqCompactor) -> Snapshot ReqSketch)
-> m Int
-> m (Vector (Snapshot ReqCompactor) -> Snapshot ReqSketch)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> URef (PrimState m) Int -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef URef (PrimState m) Int
maxNominalCapacitiesSize
m (Vector (Snapshot ReqCompactor) -> Snapshot ReqSketch)
-> m (Vector (Snapshot ReqCompactor)) -> m (Snapshot ReqSketch)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
compactors m (Vector (ReqCompactor (PrimState m)))
-> (Vector (ReqCompactor (PrimState m))
-> m (Vector (Snapshot ReqCompactor)))
-> m (Vector (Snapshot ReqCompactor))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (ReqCompactor (PrimState m) -> m (Snapshot ReqCompactor))
-> Vector (ReqCompactor (PrimState m))
-> m (Vector (Snapshot ReqCompactor))
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM ReqCompactor (PrimState m) -> m (Snapshot ReqCompactor)
forall (a :: * -> *) (m :: * -> *).
(TakeSnapshot a, PrimMonad m) =>
a (PrimState m) -> m (Snapshot a)
takeSnapshot)
deriving instance Show (Snapshot ReqSketch)
mkReqSketch :: forall m. (PrimMonad m)
=> Word32
-> RankAccuracy
-> m (ReqSketch (PrimState m))
mkReqSketch :: Word32 -> RankAccuracy -> m (ReqSketch (PrimState m))
mkReqSketch Word32
k RankAccuracy
rank = do
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Word32 -> Bool
forall a. Integral a => a -> Bool
even Word32
k Bool -> Bool -> Bool
&& Word32
k Word32 -> Word32 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word32
4 Bool -> Bool -> Bool
&& Word32
k Word32 -> Word32 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word32
1024) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ String -> m ()
forall a. HasCallStack => String -> a
error String
"k must be divisible by 2, and satisfy 4 <= k <= 1024"
ReqSketch (PrimState m)
r <- Word32
-> RankAccuracy
-> Criterion
-> Gen (PrimState m)
-> URef (PrimState m) Word64
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m)
forall s.
Word32
-> RankAccuracy
-> Criterion
-> Gen s
-> URef s Word64
-> URef s Double
-> URef s Double
-> URef s Double
-> URef s Int
-> URef s Int
-> MutVar s (Maybe ReqAuxiliary)
-> MutVar s (Vector (ReqCompactor s))
-> ReqSketch s
ReqSketch Word32
k RankAccuracy
rank Criterion
(:<)
(Gen (PrimState m)
-> URef (PrimState m) Word64
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
-> m (Gen (PrimState m))
-> m (URef (PrimState m) Word64
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> m (Gen (PrimState m))
forall (m :: * -> *). PrimMonad m => m (Gen (PrimState m))
create
m (URef (PrimState m) Word64
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
-> m (URef (PrimState m) Word64)
-> m (URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Word64 -> m (URef (PrimState m) Word64)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
a -> m (URef (PrimState m) a)
newURef Word64
0
m (URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
-> m (URef (PrimState m) Double)
-> m (URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Double -> m (URef (PrimState m) Double)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
a -> m (URef (PrimState m) a)
newURef (Double
0 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
0)
m (URef (PrimState m) Double
-> URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
-> m (URef (PrimState m) Double)
-> m (URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Double -> m (URef (PrimState m) Double)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
a -> m (URef (PrimState m) a)
newURef (Double
0 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
0)
m (URef (PrimState m) Double
-> URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
-> m (URef (PrimState m) Double)
-> m (URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Double -> m (URef (PrimState m) Double)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
a -> m (URef (PrimState m) a)
newURef Double
0
m (URef (PrimState m) Int
-> URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
-> m (URef (PrimState m) Int)
-> m (URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Int -> m (URef (PrimState m) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
a -> m (URef (PrimState m) a)
newURef Int
0
m (URef (PrimState m) Int
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
-> m (URef (PrimState m) Int)
-> m (MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Int -> m (URef (PrimState m) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
a -> m (URef (PrimState m) a)
newURef Int
0
m (MutVar (PrimState m) (Maybe ReqAuxiliary)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
-> m (MutVar (PrimState m) (Maybe ReqAuxiliary))
-> m (MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Maybe ReqAuxiliary -> m (MutVar (PrimState m) (Maybe ReqAuxiliary))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar Maybe ReqAuxiliary
forall a. Maybe a
Nothing
m (MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> ReqSketch (PrimState m))
-> m (MutVar (PrimState m) (Vector (ReqCompactor (PrimState m))))
-> m (ReqSketch (PrimState m))
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Vector (ReqCompactor (PrimState m))
-> m (MutVar (PrimState m) (Vector (ReqCompactor (PrimState m))))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar Vector (ReqCompactor (PrimState m))
forall a. Vector a
Vector.empty
ReqSketch (PrimState m) -> m ()
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m ()
grow ReqSketch (PrimState m)
r
ReqSketch (PrimState m) -> m (ReqSketch (PrimState m))
forall (f :: * -> *) a. Applicative f => a -> f a
pure ReqSketch (PrimState m)
r
mkAuxiliaryFromReqSketch :: PrimMonad m => ReqSketch (PrimState m) -> m ReqAuxiliary
mkAuxiliaryFromReqSketch :: ReqSketch (PrimState m) -> m ReqAuxiliary
mkAuxiliaryFromReqSketch ReqSketch (PrimState m)
this = do
Word64
total <- ReqSketch (PrimState m) -> m Word64
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Word64
count ReqSketch (PrimState m)
this
Int
retainedItems <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
retainedItemCount ReqSketch (PrimState m)
this
Vector (ReqCompactor (PrimState m))
compactors <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch (PrimState m)
this
RankAccuracy
-> Word64
-> Int
-> Vector (ReqCompactor (PrimState m))
-> m ReqAuxiliary
forall (m :: * -> *) s.
(PrimMonad m, s ~ PrimState m) =>
RankAccuracy
-> Word64 -> Int -> Vector (ReqCompactor s) -> m ReqAuxiliary
Auxiliary.mkAuxiliary (ReqSketch (PrimState m) -> RankAccuracy
forall s. ReqSketch s -> RankAccuracy
rankAccuracySetting ReqSketch (PrimState m)
this) Word64
total Int
retainedItems Vector (ReqCompactor (PrimState m))
compactors
getAux :: PrimMonad m => ReqSketch (PrimState m) -> m (Maybe ReqAuxiliary)
getAux :: ReqSketch (PrimState m) -> m (Maybe ReqAuxiliary)
getAux = MutVar (PrimState m) (Maybe ReqAuxiliary) -> m (Maybe ReqAuxiliary)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar (MutVar (PrimState m) (Maybe ReqAuxiliary)
-> m (Maybe ReqAuxiliary))
-> (ReqSketch (PrimState m)
-> MutVar (PrimState m) (Maybe ReqAuxiliary))
-> ReqSketch (PrimState m)
-> m (Maybe ReqAuxiliary)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m)
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
forall s. ReqSketch s -> MutVar s (Maybe ReqAuxiliary)
aux
getCompactors :: PrimMonad m => ReqSketch (PrimState m) -> m (Vector.Vector (ReqCompactor (PrimState m)))
getCompactors :: ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors = MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar (MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> m (Vector (ReqCompactor (PrimState m))))
-> (ReqSketch (PrimState m)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m))))
-> ReqSketch (PrimState m)
-> m (Vector (ReqCompactor (PrimState m)))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
forall s. ReqSketch s -> MutVar s (Vector (ReqCompactor s))
compactors
getNumLevels :: PrimMonad m => ReqSketch (PrimState m) -> m Int
getNumLevels :: ReqSketch (PrimState m) -> m Int
getNumLevels = (Vector (ReqCompactor (PrimState m)) -> Int)
-> m (Vector (ReqCompactor (PrimState m))) -> m Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Vector (ReqCompactor (PrimState m)) -> Int
forall a. Vector a -> Int
Vector.length (m (Vector (ReqCompactor (PrimState m))) -> m Int)
-> (ReqSketch (PrimState m)
-> m (Vector (ReqCompactor (PrimState m))))
-> ReqSketch (PrimState m)
-> m Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors
getIsEmpty :: PrimMonad m => ReqSketch (PrimState m) -> m Bool
getIsEmpty :: ReqSketch (PrimState m) -> m Bool
getIsEmpty = (Word64 -> Bool) -> m Word64 -> m Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0) (m Word64 -> m Bool)
-> (ReqSketch (PrimState m) -> m Word64)
-> ReqSketch (PrimState m)
-> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. URef (PrimState m) Word64 -> m Word64
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Word64 -> m Word64)
-> (ReqSketch (PrimState m) -> URef (PrimState m) Word64)
-> ReqSketch (PrimState m)
-> m Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> URef (PrimState m) Word64
forall s. ReqSketch s -> URef s Word64
totalN
getK :: ReqSketch s -> Word32
getK :: ReqSketch s -> Word32
getK = ReqSketch s -> Word32
forall s. ReqSketch s -> Word32
k
retainedItemCount :: PrimMonad m => ReqSketch (PrimState m) -> m Int
retainedItemCount :: ReqSketch (PrimState m) -> m Int
retainedItemCount = URef (PrimState m) Int -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Int -> m Int)
-> (ReqSketch (PrimState m) -> URef (PrimState m) Int)
-> ReqSketch (PrimState m)
-> m Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> URef (PrimState m) Int
forall s. ReqSketch s -> URef s Int
retainedItems
getMaxNominalCapacity :: PrimMonad m => ReqSketch (PrimState m) -> m Int
getMaxNominalCapacity :: ReqSketch (PrimState m) -> m Int
getMaxNominalCapacity = URef (PrimState m) Int -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Int -> m Int)
-> (ReqSketch (PrimState m) -> URef (PrimState m) Int)
-> ReqSketch (PrimState m)
-> m Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> URef (PrimState m) Int
forall s. ReqSketch s -> URef s Int
maxNominalCapacitiesSize
data CumulativeDistributionInvariants
= CumulativeDistributionInvariantsSplitsAreEmpty
| CumulativeDistributionInvariantsSplitsAreNotFinite
| CumulativeDistributionInvariantsSplitsAreNotUniqueAndMontonicallyIncreasing
deriving (Int -> CumulativeDistributionInvariants -> ShowS
[CumulativeDistributionInvariants] -> ShowS
CumulativeDistributionInvariants -> String
(Int -> CumulativeDistributionInvariants -> ShowS)
-> (CumulativeDistributionInvariants -> String)
-> ([CumulativeDistributionInvariants] -> ShowS)
-> Show CumulativeDistributionInvariants
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [CumulativeDistributionInvariants] -> ShowS
$cshowList :: [CumulativeDistributionInvariants] -> ShowS
show :: CumulativeDistributionInvariants -> String
$cshow :: CumulativeDistributionInvariants -> String
showsPrec :: Int -> CumulativeDistributionInvariants -> ShowS
$cshowsPrec :: Int -> CumulativeDistributionInvariants -> ShowS
Show, CumulativeDistributionInvariants
-> CumulativeDistributionInvariants -> Bool
(CumulativeDistributionInvariants
-> CumulativeDistributionInvariants -> Bool)
-> (CumulativeDistributionInvariants
-> CumulativeDistributionInvariants -> Bool)
-> Eq CumulativeDistributionInvariants
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: CumulativeDistributionInvariants
-> CumulativeDistributionInvariants -> Bool
$c/= :: CumulativeDistributionInvariants
-> CumulativeDistributionInvariants -> Bool
== :: CumulativeDistributionInvariants
-> CumulativeDistributionInvariants -> Bool
$c== :: CumulativeDistributionInvariants
-> CumulativeDistributionInvariants -> Bool
Eq)
instance Exception CumulativeDistributionInvariants
validateSplits :: Monad m => [Double] -> m ()
validateSplits :: [Double] -> m ()
validateSplits [Double]
splits = do
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when ([Double] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Data.Foldable.null [Double]
splits) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
CumulativeDistributionInvariants -> m ()
forall a e. Exception e => e -> a
throw CumulativeDistributionInvariants
CumulativeDistributionInvariantsSplitsAreEmpty
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when ((Double -> Bool) -> [Double] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any Double -> Bool
forall a. RealFloat a => a -> Bool
isInfinite [Double]
splits Bool -> Bool -> Bool
|| (Double -> Bool) -> [Double] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any Double -> Bool
forall a. RealFloat a => a -> Bool
isNaN [Double]
splits) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
CumulativeDistributionInvariants -> m ()
forall a e. Exception e => e -> a
throw CumulativeDistributionInvariants
CumulativeDistributionInvariantsSplitsAreNotFinite
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when ([Double] -> [Double]
forall a. Eq a => [a] -> [a]
Data.List.nub ([Double] -> [Double]
forall a. Ord a => [a] -> [a]
Data.List.sort [Double]
splits) [Double] -> [Double] -> Bool
forall a. Eq a => a -> a -> Bool
/= [Double]
splits) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
CumulativeDistributionInvariants -> m ()
forall a e. Exception e => e -> a
throw CumulativeDistributionInvariants
CumulativeDistributionInvariantsSplitsAreNotUniqueAndMontonicallyIncreasing
getCounts :: (PrimMonad m) => ReqSketch (PrimState m) -> [Double] -> m [Word64]
getCounts :: ReqSketch (PrimState m) -> [Double] -> m [Word64]
getCounts ReqSketch (PrimState m)
this [Double]
values = do
Vector (ReqCompactor (PrimState m))
compactors <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch (PrimState m)
this
let numValues :: Int
numValues = [Double] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Double]
values
numCompactors :: Int
numCompactors = Vector (ReqCompactor (PrimState m)) -> Int
forall a. Vector a -> Int
Vector.length Vector (ReqCompactor (PrimState m))
compactors
ans :: [Word64]
ans = Int -> Word64 -> [Word64]
forall a. Int -> a -> [a]
replicate Int
numValues Word64
0
Bool
isEmpty <- ReqSketch (PrimState m) -> m Bool
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Bool
getIsEmpty ReqSketch (PrimState m)
this
if Bool
isEmpty
then [Word64] -> m [Word64]
forall (f :: * -> *) a. Applicative f => a -> f a
pure []
else ([Word64] -> Int -> ReqCompactor (PrimState m) -> m [Word64])
-> [Word64] -> Vector (ReqCompactor (PrimState m)) -> m [Word64]
forall (m :: * -> *) a b.
Monad m =>
(a -> Int -> b -> m a) -> a -> Vector b -> m a
Vector.ifoldM [Word64] -> Int -> ReqCompactor (PrimState m) -> m [Word64]
doCount [Word64]
ans Vector (ReqCompactor (PrimState m))
compactors
where
doCount :: [Word64] -> Int -> ReqCompactor (PrimState m) -> m [Word64]
doCount [Word64]
acc Int
index ReqCompactor (PrimState m)
compactor = do
let wt :: Word64
wt = (Word64
1 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ReqCompactor (PrimState m) -> Word8
forall s. ReqCompactor s -> Word8
Compactor.getLgWeight ReqCompactor (PrimState m)
compactor)) :: Word64
DoubleBuffer (PrimState m)
buff <- ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
Compactor.getBuffer ReqCompactor (PrimState m)
compactor
let updateCounts :: DoubleBuffer (PrimState m) -> Word64 -> m Word64
updateCounts DoubleBuffer (PrimState m)
buff Word64
value = do
Int
count_ <- DoubleBuffer (PrimState m) -> Double -> Criterion -> m Int
forall (m :: * -> *).
PrimMonad m =>
DoubleBuffer (PrimState m) -> Double -> Criterion -> m Int
DoubleBuffer.getCountWithCriterion DoubleBuffer (PrimState m)
buff ([Double]
values [Double] -> Int -> Double
forall a. [a] -> Int -> a
!! Int
index) (ReqSketch (PrimState m) -> Criterion
forall s. ReqSketch s -> Criterion
criterion ReqSketch (PrimState m)
this)
Word64 -> m Word64
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Word64 -> m Word64) -> Word64 -> m Word64
forall a b. (a -> b) -> a -> b
$ Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
value Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
count_ Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
wt
(Word64 -> m Word64) -> [Word64] -> m [Word64]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM (DoubleBuffer (PrimState m) -> Word64 -> m Word64
updateCounts DoubleBuffer (PrimState m)
buff) [Word64]
acc
getPMForCDF :: (PrimMonad m) => ReqSketch (PrimState m) -> [Double] -> m [Word64]
getPMForCDF :: ReqSketch (PrimState m) -> [Double] -> m [Word64]
getPMForCDF ReqSketch (PrimState m)
this [Double]
splits = do
() <- [Double] -> m ()
forall (m :: * -> *). Monad m => [Double] -> m ()
validateSplits [Double]
splits
let numSplits :: Int
numSplits = [Double] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Double]
splits
numBuckets :: Int
numBuckets = Int
numSplits
[Word64]
splitCounts <- ReqSketch (PrimState m) -> [Double] -> m [Word64]
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> [Double] -> m [Word64]
getCounts ReqSketch (PrimState m)
this [Double]
splits
Word64
n <- ReqSketch (PrimState m) -> m Word64
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Word64
count ReqSketch (PrimState m)
this
[Word64] -> m [Word64]
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([Word64] -> m [Word64]) -> [Word64] -> m [Word64]
forall a b. (a -> b) -> a -> b
$ ([Word64] -> [Word64] -> [Word64]
forall a. [a] -> [a] -> [a]
++ [Word64
n]) ([Word64] -> [Word64]) -> [Word64] -> [Word64]
forall a b. (a -> b) -> a -> b
$ Int -> [Word64] -> [Word64]
forall a. Int -> [a] -> [a]
take Int
numBuckets [Word64]
splitCounts
cumulativeDistributionFunction
:: (PrimMonad m)
=> ReqSketch (PrimState m)
-> [Double]
-> m (Maybe [Double])
cumulativeDistributionFunction :: ReqSketch (PrimState m) -> [Double] -> m (Maybe [Double])
cumulativeDistributionFunction ReqSketch (PrimState m)
this [Double]
splitPoints = do
[Word64]
buckets <- ReqSketch (PrimState m) -> [Double] -> m [Word64]
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> [Double] -> m [Word64]
getPMForCDF ReqSketch (PrimState m)
this [Double]
splitPoints
Bool
isEmpty <- ReqSketch (PrimState m) -> m Bool
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Bool
getIsEmpty ReqSketch (PrimState m)
this
if Bool
isEmpty
then Maybe [Double] -> m (Maybe [Double])
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe [Double]
forall a. Maybe a
Nothing
else do
let numBuckets :: Int
numBuckets = [Double] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Double]
splitPoints Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
Word64
n <- ReqSketch (PrimState m) -> m Word64
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Word64
count ReqSketch (PrimState m)
this
Maybe [Double] -> m (Maybe [Double])
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe [Double] -> m (Maybe [Double]))
-> Maybe [Double] -> m (Maybe [Double])
forall a b. (a -> b) -> a -> b
$ [Double] -> Maybe [Double]
forall a. a -> Maybe a
Just ([Double] -> Maybe [Double]) -> [Double] -> Maybe [Double]
forall a b. (a -> b) -> a -> b
$ (Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Word64 -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
n) (Double -> Double) -> (Word64 -> Double) -> Word64 -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64 -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64 -> Double) -> [Word64] -> [Double]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Word64]
buckets
rankAccuracy :: ReqSketch s -> RankAccuracy
rankAccuracy :: ReqSketch s -> RankAccuracy
rankAccuracy = ReqSketch s -> RankAccuracy
forall s. ReqSketch s -> RankAccuracy
rankAccuracySetting
relativeStandardError
:: Int
-> Double
-> RankAccuracy
-> Word64
-> Double
relativeStandardError :: Int -> Double -> RankAccuracy -> Word64 -> Double
relativeStandardError Int
k Double
rank_ RankAccuracy
hra = Int -> Int -> Double -> Int -> Bool -> Word64 -> Double
getRankUB Int
k Int
2 Double
rank_ Int
1 Bool
isHra
where
isHra :: Bool
isHra = case RankAccuracy
hra of
RankAccuracy
HighRanksAreAccurate -> Bool
True
RankAccuracy
_ -> Bool
False
minimum :: PrimMonad m => ReqSketch (PrimState m) -> m Double
minimum :: ReqSketch (PrimState m) -> m Double
minimum = URef (PrimState m) Double -> m Double
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Double -> m Double)
-> (ReqSketch (PrimState m) -> URef (PrimState m) Double)
-> ReqSketch (PrimState m)
-> m Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> URef (PrimState m) Double
forall s. ReqSketch s -> URef s Double
minValue
maximum :: PrimMonad m => ReqSketch (PrimState m) -> m Double
maximum :: ReqSketch (PrimState m) -> m Double
maximum = URef (PrimState m) Double -> m Double
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Double -> m Double)
-> (ReqSketch (PrimState m) -> URef (PrimState m) Double)
-> ReqSketch (PrimState m)
-> m Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> URef (PrimState m) Double
forall s. ReqSketch s -> URef s Double
maxValue
count :: PrimMonad m => ReqSketch (PrimState m) -> m Word64
count :: ReqSketch (PrimState m) -> m Word64
count = URef (PrimState m) Word64 -> m Word64
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Word64 -> m Word64)
-> (ReqSketch (PrimState m) -> URef (PrimState m) Word64)
-> ReqSketch (PrimState m)
-> m Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> URef (PrimState m) Word64
forall s. ReqSketch s -> URef s Word64
totalN
countWithCriterion :: (PrimMonad m, s ~ PrimState m) => ReqSketch s -> Double -> m Word64
countWithCriterion :: ReqSketch s -> Double -> m Word64
countWithCriterion ReqSketch s
s Double
value = Word64 -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64 -> Word64) -> m Word64 -> m Word64
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> do
Bool
empty <- ReqSketch (PrimState m) -> m Bool
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Bool
null ReqSketch s
ReqSketch (PrimState m)
s
if Bool
empty
then Word64 -> m Word64
forall (f :: * -> *) a. Applicative f => a -> f a
pure Word64
0
else do
Vector (ReqCompactor s)
compactors <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch s
ReqSketch (PrimState m)
s
let go :: Word64 -> ReqCompactor s -> m Word64
go !Word64
accum ReqCompactor s
compactor = do
let wt :: Word64
wt = (Word64
1 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Word8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ReqCompactor s -> Word8
forall s. ReqCompactor s -> Word8
Compactor.getLgWeight ReqCompactor s
compactor)) :: Word64
DoubleBuffer s
buf <- ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
Compactor.getBuffer ReqCompactor s
ReqCompactor (PrimState m)
compactor
Int
count_ <- DoubleBuffer (PrimState m) -> Double -> Criterion -> m Int
forall (m :: * -> *).
PrimMonad m =>
DoubleBuffer (PrimState m) -> Double -> Criterion -> m Int
DoubleBuffer.getCountWithCriterion DoubleBuffer s
DoubleBuffer (PrimState m)
buf Double
value (ReqSketch s -> Criterion
forall s. ReqSketch s -> Criterion
criterion ReqSketch s
s)
Word64 -> m Word64
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Word64
accum Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
count_ Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
wt))
(Word64 -> ReqCompactor s -> m Word64)
-> Word64 -> Vector (ReqCompactor s) -> m Word64
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> Vector b -> m a
Vector.foldM Word64 -> ReqCompactor s -> m Word64
go Word64
0 Vector (ReqCompactor s)
compactors
sum :: (PrimMonad m) => ReqSketch (PrimState m) -> m Double
sum :: ReqSketch (PrimState m) -> m Double
sum = URef (PrimState m) Double -> m Double
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Double -> m Double)
-> (ReqSketch (PrimState m) -> URef (PrimState m) Double)
-> ReqSketch (PrimState m)
-> m Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> URef (PrimState m) Double
forall s. ReqSketch s -> URef s Double
sumValue
probabilityMassFunction
:: (PrimMonad m)
=> ReqSketch (PrimState m)
-> [Double]
-> m [Double]
probabilityMassFunction :: ReqSketch (PrimState m) -> [Double] -> m [Double]
probabilityMassFunction ReqSketch (PrimState m)
this [Double]
splitPoints = do
Bool
isEmpty <- ReqSketch (PrimState m) -> m Bool
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Bool
getIsEmpty ReqSketch (PrimState m)
this
if Bool
isEmpty
then [Double] -> m [Double]
forall (f :: * -> *) a. Applicative f => a -> f a
pure []
else do
let numBuckets :: Int
numBuckets = [Double] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Double]
splitPoints Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
[Double]
buckets <- (Word64 -> Double) -> [Word64] -> [Double]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Word64 -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral ([Word64] -> [Double]) -> m [Word64] -> m [Double]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ReqSketch (PrimState m) -> [Double] -> m [Word64]
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> [Double] -> m [Word64]
getPMForCDF ReqSketch (PrimState m)
this [Double]
splitPoints
Double
total <- Word64 -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64 -> Double) -> m Word64 -> m Double
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ReqSketch (PrimState m) -> m Word64
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Word64
count ReqSketch (PrimState m)
this
let computeProb :: (Int, Double) -> Double
computeProb (Int
0, Double
bucket) = Double
bucket Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
total
computeProb (Int
i, Double
bucket) = (Double
prevBucket Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
bucket) Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
total
where prevBucket :: Double
prevBucket = [Double]
buckets [Double] -> Int -> Double
forall a. [a] -> Int -> a
!! Int
i Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
1
probs :: [Double]
probs = (Int, Double) -> Double
computeProb ((Int, Double) -> Double) -> [(Int, Double)] -> [Double]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Int] -> [Double] -> [(Int, Double)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
0..] [Double]
buckets
[Double] -> m [Double]
forall (f :: * -> *) a. Applicative f => a -> f a
pure [Double]
probs
quantile
:: (PrimMonad m)
=> ReqSketch (PrimState m)
-> Double
-> m Double
quantile :: ReqSketch (PrimState m) -> Double -> m Double
quantile ReqSketch (PrimState m)
this Double
normRank = do
Bool
isEmpty <- ReqSketch (PrimState m) -> m Bool
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Bool
getIsEmpty ReqSketch (PrimState m)
this
if Bool
isEmpty
then Double -> m Double
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Double
0Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/Double
0)
else do
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Double
normRank Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
< Double
0 Bool -> Bool -> Bool
|| Double
normRank Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
1.0) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$
String -> m ()
forall a. HasCallStack => String -> a
error (String -> m ()) -> String -> m ()
forall a b. (a -> b) -> a -> b
$ String
"Normalized rank must be in the range [0.0, 1.0]: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Double -> String
forall a. Show a => a -> String
show Double
normRank
Maybe ReqAuxiliary
currAuxiliary <- ReqSketch (PrimState m) -> m (Maybe ReqAuxiliary)
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Maybe ReqAuxiliary)
getAux ReqSketch (PrimState m)
this
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Maybe ReqAuxiliary -> Bool
forall a. Maybe a -> Bool
isNothing Maybe ReqAuxiliary
currAuxiliary) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
Word64
total <- ReqSketch (PrimState m) -> m Word64
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Word64
count ReqSketch (PrimState m)
this
Int
retainedItems <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
retainedItemCount ReqSketch (PrimState m)
this
Vector (ReqCompactor (PrimState m))
compactors <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch (PrimState m)
this
ReqAuxiliary
newAuxiliary <- RankAccuracy
-> Word64
-> Int
-> Vector (ReqCompactor (PrimState m))
-> m ReqAuxiliary
forall (m :: * -> *) s.
(PrimMonad m, s ~ PrimState m) =>
RankAccuracy
-> Word64 -> Int -> Vector (ReqCompactor s) -> m ReqAuxiliary
Auxiliary.mkAuxiliary (ReqSketch (PrimState m) -> RankAccuracy
forall s. ReqSketch s -> RankAccuracy
rankAccuracySetting ReqSketch (PrimState m)
this) Word64
total Int
retainedItems Vector (ReqCompactor (PrimState m))
compactors
MutVar (PrimState m) (Maybe ReqAuxiliary)
-> Maybe ReqAuxiliary -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar (ReqSketch (PrimState m)
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
forall s. ReqSketch s -> MutVar s (Maybe ReqAuxiliary)
aux ReqSketch (PrimState m)
this) (ReqAuxiliary -> Maybe ReqAuxiliary
forall a. a -> Maybe a
Just ReqAuxiliary
newAuxiliary)
Maybe ReqAuxiliary
mAuxiliary <- ReqSketch (PrimState m) -> m (Maybe ReqAuxiliary)
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Maybe ReqAuxiliary)
getAux ReqSketch (PrimState m)
this
case Maybe ReqAuxiliary
mAuxiliary of
Just ReqAuxiliary
auxiliary -> Double -> m Double
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Double -> m Double) -> Double -> m Double
forall a b. (a -> b) -> a -> b
$! ReqAuxiliary -> Double -> Criterion -> Double
Auxiliary.getQuantile ReqAuxiliary
auxiliary Double
normRank (Criterion -> Double) -> Criterion -> Double
forall a b. (a -> b) -> a -> b
$ ReqSketch (PrimState m) -> Criterion
forall s. ReqSketch s -> Criterion
criterion ReqSketch (PrimState m)
this
Maybe ReqAuxiliary
Nothing -> String -> m Double
forall a. HasCallStack => String -> a
error String
"invariant violated: aux is not set"
quantiles
:: (PrimMonad m)
=> ReqSketch (PrimState m)
-> [Double]
-> m [Double]
quantiles :: ReqSketch (PrimState m) -> [Double] -> m [Double]
quantiles ReqSketch (PrimState m)
this [Double]
normRanks = do
Bool
isEmpty <- ReqSketch (PrimState m) -> m Bool
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Bool
getIsEmpty ReqSketch (PrimState m)
this
if Bool
isEmpty
then [Double] -> m [Double]
forall (f :: * -> *) a. Applicative f => a -> f a
pure []
else (Double -> m Double) -> [Double] -> m [Double]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM (ReqSketch (PrimState m) -> Double -> m Double
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> Double -> m Double
quantile ReqSketch (PrimState m)
this) [Double]
normRanks
rank :: (PrimMonad m)
=> ReqSketch (PrimState m)
-> Double
-> m Double
rank :: ReqSketch (PrimState m) -> Double -> m Double
rank ReqSketch (PrimState m)
s Double
value = do
Bool
isEmpty <- ReqSketch (PrimState m) -> m Bool
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Bool
null ReqSketch (PrimState m)
s
if Bool
isEmpty
then Double -> m Double
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Double
0 Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
0)
else do
Word64
nnCount <- ReqSketch (PrimState m) -> Double -> m Word64
forall (m :: * -> *) s.
(PrimMonad m, s ~ PrimState m) =>
ReqSketch s -> Double -> m Word64
countWithCriterion ReqSketch (PrimState m)
s Double
value
Word64
total <- URef (PrimState m) Word64 -> m Word64
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Word64 -> m Word64)
-> URef (PrimState m) Word64 -> m Word64
forall a b. (a -> b) -> a -> b
$ ReqSketch (PrimState m) -> URef (PrimState m) Word64
forall s. ReqSketch s -> URef s Word64
totalN ReqSketch (PrimState m)
s
Double -> m Double
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Word64 -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
nnCount Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Word64 -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
total)
rankLowerBound
:: (PrimMonad m)
=> ReqSketch (PrimState m)
-> Double
-> Int
-> m Double
rankLowerBound :: ReqSketch (PrimState m) -> Double -> Int -> m Double
rankLowerBound ReqSketch (PrimState m)
this Double
rank Int
numStdDev = do
Int
numLevels <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
getNumLevels ReqSketch (PrimState m)
this
let k :: Int
k = Word32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word32 -> Int) -> Word32 -> Int
forall a b. (a -> b) -> a -> b
$ ReqSketch (PrimState m) -> Word32
forall s. ReqSketch s -> Word32
getK ReqSketch (PrimState m)
this
Word64
total <- ReqSketch (PrimState m) -> m Word64
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Word64
count ReqSketch (PrimState m)
this
Double -> m Double
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Double -> m Double) -> Double -> m Double
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Double -> Int -> Bool -> Word64 -> Double
getRankLB Int
k Int
numLevels Double
rank Int
numStdDev (ReqSketch (PrimState m) -> RankAccuracy
forall s. ReqSketch s -> RankAccuracy
rankAccuracySetting ReqSketch (PrimState m)
this RankAccuracy -> RankAccuracy -> Bool
forall a. Eq a => a -> a -> Bool
== RankAccuracy
HighRanksAreAccurate) Word64
total
ranks :: (PrimMonad m, s ~ PrimState m) => ReqSketch s -> [Double] -> m [Double]
ranks :: ReqSketch s -> [Double] -> m [Double]
ranks ReqSketch s
s [Double]
values = (Double -> m Double) -> [Double] -> m [Double]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM (ReqSketch (PrimState m) -> Double -> m Double
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> Double -> m Double
rank ReqSketch s
ReqSketch (PrimState m)
s) [Double]
values
rankUpperBound
:: (PrimMonad m)
=> ReqSketch (PrimState m)
-> Double
-> Int
-> m Double
rankUpperBound :: ReqSketch (PrimState m) -> Double -> Int -> m Double
rankUpperBound ReqSketch (PrimState m)
this Double
rank Int
numStdDev= do
Int
numLevels <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
getNumLevels ReqSketch (PrimState m)
this
let k :: Int
k = Word32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word32 -> Int) -> Word32 -> Int
forall a b. (a -> b) -> a -> b
$ ReqSketch (PrimState m) -> Word32
forall s. ReqSketch s -> Word32
getK ReqSketch (PrimState m)
this
Word64
total <- ReqSketch (PrimState m) -> m Word64
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Word64
count ReqSketch (PrimState m)
this
Double -> m Double
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Double -> m Double) -> Double -> m Double
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Double -> Int -> Bool -> Word64 -> Double
getRankUB Int
k Int
numLevels Double
rank Int
numStdDev (ReqSketch (PrimState m) -> RankAccuracy
forall s. ReqSketch s -> RankAccuracy
rankAccuracySetting ReqSketch (PrimState m)
this RankAccuracy -> RankAccuracy -> Bool
forall a. Eq a => a -> a -> Bool
== RankAccuracy
HighRanksAreAccurate) Word64
total
null :: (PrimMonad m) => ReqSketch (PrimState m) -> m Bool
null :: ReqSketch (PrimState m) -> m Bool
null = (Word64 -> Bool) -> m Word64 -> m Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0) (m Word64 -> m Bool)
-> (ReqSketch (PrimState m) -> m Word64)
-> ReqSketch (PrimState m)
-> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. URef (PrimState m) Word64 -> m Word64
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Word64 -> m Word64)
-> (ReqSketch (PrimState m) -> URef (PrimState m) Word64)
-> ReqSketch (PrimState m)
-> m Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> URef (PrimState m) Word64
forall s. ReqSketch s -> URef s Word64
totalN
isEstimationMode :: PrimMonad m => ReqSketch (PrimState m) -> m Bool
isEstimationMode :: ReqSketch (PrimState m) -> m Bool
isEstimationMode = (Int -> Bool) -> m Int -> m Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
1) (m Int -> m Bool)
-> (ReqSketch (PrimState m) -> m Int)
-> ReqSketch (PrimState m)
-> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
getNumLevels
isLessThanOrEqual :: ReqSketch s -> Bool
isLessThanOrEqual :: ReqSketch s -> Bool
isLessThanOrEqual ReqSketch s
s = case ReqSketch s -> Criterion
forall s. ReqSketch s -> Criterion
criterion ReqSketch s
s of
Criterion
(:<) -> Bool
False
Criterion
(:<=) -> Bool
True
computeMaxNominalSize :: PrimMonad m => ReqSketch (PrimState m) -> m Int
computeMaxNominalSize :: ReqSketch (PrimState m) -> m Int
computeMaxNominalSize ReqSketch (PrimState m)
this = do
Vector (ReqCompactor (PrimState m))
compactors <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch (PrimState m)
this
(Int -> ReqCompactor (PrimState m) -> m Int)
-> Int -> Vector (ReqCompactor (PrimState m)) -> m Int
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> Vector b -> m a
Vector.foldM Int -> ReqCompactor (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
Int -> ReqCompactor (PrimState m) -> m Int
countNominalCapacity Int
0 Vector (ReqCompactor (PrimState m))
compactors
where
countNominalCapacity :: Int -> ReqCompactor (PrimState m) -> m Int
countNominalCapacity Int
acc ReqCompactor (PrimState m)
compactor = do
Int
nominalCapacity <- ReqCompactor (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqCompactor (PrimState m) -> m Int
Compactor.getNominalCapacity ReqCompactor (PrimState m)
compactor
Int -> m Int
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> m Int) -> Int -> m Int
forall a b. (a -> b) -> a -> b
$ Int
nominalCapacity Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
acc
computeTotalRetainedItems :: PrimMonad m => ReqSketch (PrimState m) -> m Int
computeTotalRetainedItems :: ReqSketch (PrimState m) -> m Int
computeTotalRetainedItems ReqSketch (PrimState m)
this = do
Vector (ReqCompactor (PrimState m))
compactors <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch (PrimState m)
this
(Int -> ReqCompactor (PrimState m) -> m Int)
-> Int -> Vector (ReqCompactor (PrimState m)) -> m Int
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> Vector b -> m a
Vector.foldM Int -> ReqCompactor (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
Int -> ReqCompactor (PrimState m) -> m Int
countBuffer Int
0 Vector (ReqCompactor (PrimState m))
compactors
where
countBuffer :: Int -> ReqCompactor (PrimState m) -> m Int
countBuffer Int
acc ReqCompactor (PrimState m)
compactor = do
DoubleBuffer (PrimState m)
buff <- ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
Compactor.getBuffer ReqCompactor (PrimState m)
compactor
Int
buffSize <- DoubleBuffer (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
DoubleBuffer (PrimState m) -> m Int
DoubleBuffer.getCount DoubleBuffer (PrimState m)
buff
Int -> m Int
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> m Int) -> Int -> m Int
forall a b. (a -> b) -> a -> b
$ Int
buffSize Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
acc
grow :: (PrimMonad m) => ReqSketch (PrimState m) -> m ()
grow :: ReqSketch (PrimState m) -> m ()
grow ReqSketch (PrimState m)
this = do
Word8
lgWeight <- Int -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Word8) -> m Int -> m Word8
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
getNumLevels ReqSketch (PrimState m)
this
let rankAccuracy :: RankAccuracy
rankAccuracy = ReqSketch (PrimState m) -> RankAccuracy
forall s. ReqSketch s -> RankAccuracy
rankAccuracySetting ReqSketch (PrimState m)
this
sectionSize :: Word32
sectionSize = ReqSketch (PrimState m) -> Word32
forall s. ReqSketch s -> Word32
getK ReqSketch (PrimState m)
this
ReqCompactor (PrimState m)
newCompactor <- Gen (PrimState m)
-> Word8
-> RankAccuracy
-> Word32
-> m (ReqCompactor (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
Gen (PrimState m)
-> Word8
-> RankAccuracy
-> Word32
-> m (ReqCompactor (PrimState m))
Compactor.mkReqCompactor (ReqSketch (PrimState m) -> Gen (PrimState m)
forall s. ReqSketch s -> Gen s
sketchRng ReqSketch (PrimState m)
this) Word8
lgWeight RankAccuracy
rankAccuracy Word32
sectionSize
MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
-> (Vector (ReqCompactor (PrimState m))
-> Vector (ReqCompactor (PrimState m)))
-> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> (a -> a) -> m ()
modifyMutVar' (ReqSketch (PrimState m)
-> MutVar (PrimState m) (Vector (ReqCompactor (PrimState m)))
forall s. ReqSketch s -> MutVar s (Vector (ReqCompactor s))
compactors ReqSketch (PrimState m)
this) (Vector (ReqCompactor (PrimState m))
-> ReqCompactor (PrimState m)
-> Vector (ReqCompactor (PrimState m))
forall a. Vector a -> a -> Vector a
`Vector.snoc` ReqCompactor (PrimState m)
newCompactor)
Int
maxNominalCapacity <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
computeMaxNominalSize ReqSketch (PrimState m)
this
URef (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> a -> m ()
writeURef (ReqSketch (PrimState m) -> URef (PrimState m) Int
forall s. ReqSketch s -> URef s Int
maxNominalCapacitiesSize ReqSketch (PrimState m)
this) Int
maxNominalCapacity
compress :: (PrimMonad m) => ReqSketch (PrimState m) -> m ()
compress :: ReqSketch (PrimState m) -> m ()
compress ReqSketch (PrimState m)
this = do
Vector (ReqCompactor (PrimState m))
compactors <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch (PrimState m)
this
let compressionStep :: Int -> ReqCompactor (PrimState m) -> m ()
compressionStep Int
height ReqCompactor (PrimState m)
compactor = do
Int
buffSize <- DoubleBuffer (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
DoubleBuffer (PrimState m) -> m Int
DoubleBuffer.getCount (DoubleBuffer (PrimState m) -> m Int)
-> m (DoubleBuffer (PrimState m)) -> m Int
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
Compactor.getBuffer ReqCompactor (PrimState m)
compactor
Int
nominalCapacity <- ReqCompactor (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqCompactor (PrimState m) -> m Int
Compactor.getNominalCapacity ReqCompactor (PrimState m)
compactor
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
buffSize Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
nominalCapacity) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
Int
numLevels <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
getNumLevels ReqSketch (PrimState m)
this
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
height Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
numLevels) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
ReqSketch (PrimState m) -> m ()
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m ()
grow ReqSketch (PrimState m)
this
Vector (ReqCompactor (PrimState m))
compactors' <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch (PrimState m)
this
CompactorReturn (PrimState m)
cReturn <- ReqCompactor (PrimState m) -> m (CompactorReturn (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
ReqCompactor (PrimState m) -> m (CompactorReturn (PrimState m))
Compactor.compact ReqCompactor (PrimState m)
compactor
let topCompactor :: ReqCompactor (PrimState m)
topCompactor = Vector (ReqCompactor (PrimState m))
compactors' Vector (ReqCompactor (PrimState m))
-> Int -> ReqCompactor (PrimState m)
forall a. Vector a -> Int -> a
! (Int
height Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
DoubleBuffer (PrimState m)
buff <- ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
Compactor.getBuffer ReqCompactor (PrimState m)
topCompactor
DoubleBuffer (PrimState m) -> DoubleBuffer (PrimState m) -> m ()
forall (m :: * -> *).
(PrimMonad m, HasCallStack) =>
DoubleBuffer (PrimState m) -> DoubleBuffer (PrimState m) -> m ()
DoubleBuffer.mergeSortIn DoubleBuffer (PrimState m)
buff (DoubleBuffer (PrimState m) -> m ())
-> DoubleBuffer (PrimState m) -> m ()
forall a b. (a -> b) -> a -> b
$ CompactorReturn (PrimState m) -> DoubleBuffer (PrimState m)
forall s. CompactorReturn s -> DoubleBuffer s
Compactor.crDoubleBuffer CompactorReturn (PrimState m)
cReturn
URef (PrimState m) Int -> (Int -> Int) -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> (a -> a) -> m ()
modifyURef (ReqSketch (PrimState m) -> URef (PrimState m) Int
forall s. ReqSketch s -> URef s Int
retainedItems ReqSketch (PrimState m)
this) (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ CompactorReturn (PrimState m) -> Int
forall s. CompactorReturn s -> Int
Compactor.crDeltaRetItems CompactorReturn (PrimState m)
cReturn)
URef (PrimState m) Int -> (Int -> Int) -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> (a -> a) -> m ()
modifyURef (ReqSketch (PrimState m) -> URef (PrimState m) Int
forall s. ReqSketch s -> URef s Int
maxNominalCapacitiesSize ReqSketch (PrimState m)
this) (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ CompactorReturn (PrimState m) -> Int
forall s. CompactorReturn s -> Int
Compactor.crDeltaNominalSize CompactorReturn (PrimState m)
cReturn)
(Int -> ReqCompactor (PrimState m) -> m ())
-> Vector (ReqCompactor (PrimState m)) -> m ()
forall (m :: * -> *) a b.
Monad m =>
(Int -> a -> m b) -> Vector a -> m ()
imapM_ Int -> ReqCompactor (PrimState m) -> m ()
compressionStep Vector (ReqCompactor (PrimState m))
compactors
MutVar (PrimState m) (Maybe ReqAuxiliary)
-> Maybe ReqAuxiliary -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar (ReqSketch (PrimState m)
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
forall s. ReqSketch s -> MutVar s (Maybe ReqAuxiliary)
aux ReqSketch (PrimState m)
this) Maybe ReqAuxiliary
forall a. Maybe a
Nothing
merge
:: (PrimMonad m, s ~ PrimState m)
=> ReqSketch s
-> ReqSketch s
-> m (ReqSketch s)
merge :: ReqSketch s -> ReqSketch s -> m (ReqSketch s)
merge ReqSketch s
this ReqSketch s
other = do
Bool
otherIsEmpty <- ReqSketch (PrimState m) -> m Bool
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Bool
getIsEmpty ReqSketch s
ReqSketch (PrimState m)
other
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless Bool
otherIsEmpty (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
let rankAccuracy :: RankAccuracy
rankAccuracy = ReqSketch s -> RankAccuracy
forall s. ReqSketch s -> RankAccuracy
rankAccuracySetting ReqSketch s
this
otherRankAccuracy :: RankAccuracy
otherRankAccuracy = ReqSketch s -> RankAccuracy
forall s. ReqSketch s -> RankAccuracy
rankAccuracySetting ReqSketch s
other
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (RankAccuracy
rankAccuracy RankAccuracy -> RankAccuracy -> Bool
forall a. Eq a => a -> a -> Bool
/= RankAccuracy
otherRankAccuracy) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$
String -> m ()
forall a. HasCallStack => String -> a
error String
"Both sketches must have the same HighRankAccuracy setting."
Word64
otherN <- ReqSketch (PrimState m) -> m Word64
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Word64
count ReqSketch s
ReqSketch (PrimState m)
other
URef (PrimState m) Word64 -> (Word64 -> Word64) -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> (a -> a) -> m ()
modifyURef (ReqSketch s -> URef s Word64
forall s. ReqSketch s -> URef s Word64
totalN ReqSketch s
this) (Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
otherN)
Double
thisMin <- ReqSketch (PrimState m) -> m Double
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Double
minimum ReqSketch s
ReqSketch (PrimState m)
this
Double
thisMax <- ReqSketch (PrimState m) -> m Double
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Double
maximum ReqSketch s
ReqSketch (PrimState m)
this
Double
otherMin <- ReqSketch (PrimState m) -> m Double
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Double
minimum ReqSketch s
ReqSketch (PrimState m)
other
Double
otherMax <- ReqSketch (PrimState m) -> m Double
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Double
maximum ReqSketch s
ReqSketch (PrimState m)
other
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Double -> Bool
forall a. RealFloat a => a -> Bool
isNaN Double
thisMin Bool -> Bool -> Bool
|| Double
otherMin Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
< Double
thisMin) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
URef (PrimState m) Double -> Double -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> a -> m ()
writeURef (ReqSketch s -> URef s Double
forall s. ReqSketch s -> URef s Double
minValue ReqSketch s
this) Double
otherMin
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Double -> Bool
forall a. RealFloat a => a -> Bool
isNaN Double
thisMax Bool -> Bool -> Bool
|| Double
otherMax Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
< Double
thisMax) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
URef (PrimState m) Double -> Double -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> a -> m ()
writeURef (ReqSketch s -> URef s Double
forall s. ReqSketch s -> URef s Double
maxValue ReqSketch s
this) Double
otherMax
Int
numRequiredCompactors <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
getNumLevels ReqSketch s
ReqSketch (PrimState m)
other
Int -> m ()
growUntil Int
numRequiredCompactors
Vector (ReqCompactor s)
thisCompactors <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch s
ReqSketch (PrimState m)
this
Vector (ReqCompactor s)
otherCompactors <- ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch s
ReqSketch (PrimState m)
other
(ReqCompactor s -> ReqCompactor s -> m (ReqCompactor s))
-> Vector (ReqCompactor s) -> Vector (ReqCompactor s) -> m ()
forall (m :: * -> *) a b c.
Monad m =>
(a -> b -> m c) -> Vector a -> Vector b -> m ()
Vector.zipWithM_ ReqCompactor s -> ReqCompactor s -> m (ReqCompactor s)
forall (m :: * -> *) s.
(PrimMonad m, s ~ PrimState m) =>
ReqCompactor (PrimState m)
-> ReqCompactor (PrimState m) -> m (ReqCompactor s)
Compactor.merge Vector (ReqCompactor s)
thisCompactors Vector (ReqCompactor s)
otherCompactors
Int
maxNominalCapacity <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
computeMaxNominalSize ReqSketch s
ReqSketch (PrimState m)
this
Int
totalRetainedItems <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
computeTotalRetainedItems ReqSketch s
ReqSketch (PrimState m)
this
URef (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> a -> m ()
writeURef (ReqSketch s -> URef s Int
forall s. ReqSketch s -> URef s Int
maxNominalCapacitiesSize ReqSketch s
this) Int
maxNominalCapacity
URef (PrimState m) Int -> Int -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> a -> m ()
writeURef (ReqSketch s -> URef s Int
forall s. ReqSketch s -> URef s Int
retainedItems ReqSketch s
this) Int
totalRetainedItems
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
totalRetainedItems Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
maxNominalCapacity) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
ReqSketch (PrimState m) -> m ()
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m ()
compress ReqSketch s
ReqSketch (PrimState m)
this
Int
maxNominalCapacity' <- URef (PrimState m) Int -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Int -> m Int)
-> URef (PrimState m) Int -> m Int
forall a b. (a -> b) -> a -> b
$ ReqSketch s -> URef s Int
forall s. ReqSketch s -> URef s Int
maxNominalCapacitiesSize ReqSketch s
this
Int
totalRetainedItems' <- URef (PrimState m) Int -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> m a
readURef (URef (PrimState m) Int -> m Int)
-> URef (PrimState m) Int -> m Int
forall a b. (a -> b) -> a -> b
$ ReqSketch s -> URef s Int
forall s. ReqSketch s -> URef s Int
retainedItems ReqSketch s
this
Bool -> m () -> m ()
forall a. HasCallStack => Bool -> a -> a
assert (Int
totalRetainedItems' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
maxNominalCapacity') (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$
MutVar (PrimState m) (Maybe ReqAuxiliary)
-> Maybe ReqAuxiliary -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar (ReqSketch s -> MutVar s (Maybe ReqAuxiliary)
forall s. ReqSketch s -> MutVar s (Maybe ReqAuxiliary)
aux ReqSketch s
this) Maybe ReqAuxiliary
forall a. Maybe a
Nothing
ReqSketch s -> m (ReqSketch s)
forall (f :: * -> *) a. Applicative f => a -> f a
pure ReqSketch s
this
where
growUntil :: Int -> m ()
growUntil Int
target = do
Int
numCompactors <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
getNumLevels ReqSketch s
ReqSketch (PrimState m)
this
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
numCompactors Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
target) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$
ReqSketch (PrimState m) -> m ()
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m ()
grow ReqSketch s
ReqSketch (PrimState m)
this
insert :: (PrimMonad m) => ReqSketch (PrimState m) -> Double -> m ()
insert :: ReqSketch (PrimState m) -> Double -> m ()
insert ReqSketch (PrimState m)
this Double
item = do
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Double -> Bool
forall a. RealFloat a => a -> Bool
isNaN Double
item) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
Bool
isEmpty <- ReqSketch (PrimState m) -> m Bool
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Bool
getIsEmpty ReqSketch (PrimState m)
this
if Bool
isEmpty
then do
URef (PrimState m) Double -> Double -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> a -> m ()
writeURef (ReqSketch (PrimState m) -> URef (PrimState m) Double
forall s. ReqSketch s -> URef s Double
minValue ReqSketch (PrimState m)
this) Double
item
URef (PrimState m) Double -> Double -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> a -> m ()
writeURef (ReqSketch (PrimState m) -> URef (PrimState m) Double
forall s. ReqSketch s -> URef s Double
maxValue ReqSketch (PrimState m)
this) Double
item
else do
Double
min_ <- ReqSketch (PrimState m) -> m Double
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Double
minimum ReqSketch (PrimState m)
this
Double
max_ <- ReqSketch (PrimState m) -> m Double
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Double
maximum ReqSketch (PrimState m)
this
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Double
item Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
< Double
min_) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ URef (PrimState m) Double -> Double -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> a -> m ()
writeURef (ReqSketch (PrimState m) -> URef (PrimState m) Double
forall s. ReqSketch s -> URef s Double
minValue ReqSketch (PrimState m)
this) Double
item
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Double
item Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
max_) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ URef (PrimState m) Double -> Double -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> a -> m ()
writeURef (ReqSketch (PrimState m) -> URef (PrimState m) Double
forall s. ReqSketch s -> URef s Double
maxValue ReqSketch (PrimState m)
this) Double
item
ReqCompactor (PrimState m)
compactor <- Vector (ReqCompactor (PrimState m)) -> ReqCompactor (PrimState m)
forall a. Vector a -> a
Vector.head (Vector (ReqCompactor (PrimState m)) -> ReqCompactor (PrimState m))
-> m (Vector (ReqCompactor (PrimState m)))
-> m (ReqCompactor (PrimState m))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
getCompactors ReqSketch (PrimState m)
this
DoubleBuffer (PrimState m)
buff <- ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
ReqCompactor (PrimState m) -> m (DoubleBuffer (PrimState m))
Compactor.getBuffer ReqCompactor (PrimState m)
compactor
DoubleBuffer (PrimState m) -> Double -> m ()
forall (m :: * -> *).
PrimMonad m =>
DoubleBuffer (PrimState m) -> Double -> m ()
DoubleBuffer.append DoubleBuffer (PrimState m)
buff Double
item
URef (PrimState m) Int -> (Int -> Int) -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> (a -> a) -> m ()
modifyURef (ReqSketch (PrimState m) -> URef (PrimState m) Int
forall s. ReqSketch s -> URef s Int
retainedItems ReqSketch (PrimState m)
this) (Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
URef (PrimState m) Word64 -> (Word64 -> Word64) -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> (a -> a) -> m ()
modifyURef (ReqSketch (PrimState m) -> URef (PrimState m) Word64
forall s. ReqSketch s -> URef s Word64
totalN ReqSketch (PrimState m)
this) (Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+Word64
1)
URef (PrimState m) Double -> (Double -> Double) -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
URef (PrimState m) a -> (a -> a) -> m ()
modifyURef (ReqSketch (PrimState m) -> URef (PrimState m) Double
forall s. ReqSketch s -> URef s Double
sumValue ReqSketch (PrimState m)
this) (Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
item)
Int
retItems <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
retainedItemCount ReqSketch (PrimState m)
this
Int
maxNominalCapacity <- ReqSketch (PrimState m) -> m Int
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m Int
getMaxNominalCapacity ReqSketch (PrimState m)
this
Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
retItems Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
maxNominalCapacity) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
DoubleBuffer (PrimState m) -> m ()
forall (m :: * -> *).
PrimMonad m =>
DoubleBuffer (PrimState m) -> m ()
DoubleBuffer.sort DoubleBuffer (PrimState m)
buff
ReqSketch (PrimState m) -> m ()
forall (m :: * -> *).
PrimMonad m =>
ReqSketch (PrimState m) -> m ()
compress ReqSketch (PrimState m)
this
MutVar (PrimState m) (Maybe ReqAuxiliary)
-> Maybe ReqAuxiliary -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar (ReqSketch (PrimState m)
-> MutVar (PrimState m) (Maybe ReqAuxiliary)
forall s. ReqSketch s -> MutVar s (Maybe ReqAuxiliary)
aux ReqSketch (PrimState m)
this) Maybe ReqAuxiliary
forall a. Maybe a
Nothing
getRankLB :: Int -> Int -> Double -> Int -> Bool -> Word64 -> Double
getRankLB :: Int -> Int -> Double -> Int -> Bool -> Word64 -> Double
getRankLB Int
k Int
levels Double
rank Int
numStdDev Bool
hra Word64
totalN = if Int -> Int -> Double -> Bool -> Word64 -> Bool
exactRank Int
k Int
levels Double
rank Bool
hra Word64
totalN
then Double
rank
else Double -> Double -> Double
forall a. Ord a => a -> a -> a
max Double
lbRel Double
lbFix
where
relative :: Double
relative = Double
relRseFactor Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k Double -> Double -> Double
forall a. Num a => a -> a -> a
* (if Bool
hra then Double
1.0 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
rank else Double
rank)
fixed :: Double
fixed = Double
fixRseFactor Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k
lbRel :: Double
lbRel = Double
rank Double -> Double -> Double
forall a. Num a => a -> a -> a
- Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
numStdDev Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
relative
lbFix :: Double
lbFix = Double
rank Double -> Double -> Double
forall a. Num a => a -> a -> a
- Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
numStdDev Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
fixed
getRankUB :: Int -> Int -> Double -> Int -> Bool -> Word64 -> Double
getRankUB :: Int -> Int -> Double -> Int -> Bool -> Word64 -> Double
getRankUB Int
k Int
levels Double
rank Int
numStdDev Bool
hra Word64
totalN = if Int -> Int -> Double -> Bool -> Word64 -> Bool
exactRank Int
k Int
levels Double
rank Bool
hra Word64
totalN
then Double
rank
else Double -> Double -> Double
forall a. Ord a => a -> a -> a
min Double
ubRel Double
ubFix
where
relative :: Double
relative = Double
relRseFactor Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k Double -> Double -> Double
forall a. Num a => a -> a -> a
* (if Bool
hra then Double
1.0 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
rank else Double
rank)
fixed :: Double
fixed = Double
fixRseFactor Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k
ubRel :: Double
ubRel = Double
rank Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
numStdDev Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
relative
ubFix :: Double
ubFix = Double
rank Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
numStdDev Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
fixed
exactRank :: Int -> Int -> Double -> Bool -> Word64 -> Bool
exactRank :: Int -> Int -> Double -> Bool -> Word64 -> Bool
exactRank Int
k Int
levels Double
rank Bool
hra Word64
totalN = (Int
levels Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
|| Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
totalN Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
baseCap) Bool -> Bool -> Bool
|| (Bool
hra Bool -> Bool -> Bool
&& Double
rank Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
>= Double
1.0 Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
exactRankThresh Bool -> Bool -> Bool
|| Bool -> Bool
not Bool
hra Bool -> Bool -> Bool
&& Double
rank Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
<= Double
exactRankThresh)
where
baseCap :: Int
baseCap = Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
forall a. Num a => a
initNumberOfSections
exactRankThresh :: Double
exactRankThresh :: Double
exactRankThresh = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
baseCap Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Word64 -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
totalN