{-# LANGUAGE DataKinds             #-}
{-# LANGUAGE KindSignatures        #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables   #-}
-- | This is non empty version of 'Data.TDigest.TDigest', i.e. this is not a 'Monoid',
-- but on the other hand, 'quantile' returns 'Double'  not @'Maybe' 'Double'@.
--
-- See "Data.TDigest" for documentation. The exports should be similar,
-- sans non-'Maybe' results.
--
-- === Examples
--
-- >>> quantile 0.99 (tdigest (1 :| [2..1000]) :: TDigest 25)
-- 990.5
--
-- >>> quantile 0.99 (tdigest (1 :| [2..1000]) :: TDigest 3)
-- 989.0...
--
-- t-Digest is more precise in tails, especially median is imprecise:
--
-- >>> median (forceCompress $ tdigest (1 :| [2..1000]) :: TDigest 25)
-- 497.6...
--
module Data.TDigest.Tree.NonEmpty (
    -- * Construction
    TDigest,
    tdigest,

    -- ** Population
    singleton,
    insert,
    insert',

    -- * Compression
    compress,
    forceCompress,

    -- * Statistics
    totalWeight,
    minimumValue,
    maximumValue,
    -- ** Percentile
    median,
    quantile,
    -- ** Mean & variance
    mean,
    variance,
    stddev,
    -- ** CDF
    cdf,
    icdf,

    -- * Debug
    size,
    valid,
    validate,
    debugPrint,
    ) where

import Prelude ()
import Prelude.Compat

import Control.DeepSeq         (NFData (..))
import Control.Monad           (when)
import Data.Binary             (Binary (..))
import Data.Functor.Identity   (Identity (..))
import Data.Semigroup          (Semigroup (..))
import Data.Semigroup.Foldable (Foldable1)
import Data.Semigroup.Reducer  (Reducer (..))
import GHC.TypeLits            (KnownNat)

import           Data.TDigest.Internal
import qualified Data.TDigest.Postprocess   as PP
import qualified Data.TDigest.Tree.Internal as T

newtype TDigest comp = TDigest { TDigest comp -> TDigest comp
unEmpty :: T.TDigest comp }

-------------------------------------------------------------------------------
-- Instances
-------------------------------------------------------------------------------

instance NFData (TDigest comp) where
    rnf :: TDigest comp -> ()
rnf (TDigest TDigest comp
t) = TDigest comp -> ()
forall a. NFData a => a -> ()
rnf TDigest comp
t

instance Show (TDigest comp) where
    showsPrec :: Int -> TDigest comp -> ShowS
showsPrec Int
d (TDigest TDigest comp
t) = Int -> TDigest comp -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
d TDigest comp
t

instance KnownNat comp => Semigroup (TDigest comp) where
    TDigest TDigest comp
a <> :: TDigest comp -> TDigest comp -> TDigest comp
<> TDigest TDigest comp
b = TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
TDigest (TDigest comp
a TDigest comp -> TDigest comp -> TDigest comp
forall a. Semigroup a => a -> a -> a
<>  TDigest comp
b)

instance KnownNat comp => Reducer Double (TDigest comp) where
    cons :: Double -> TDigest comp -> TDigest comp
cons = Double -> TDigest comp -> TDigest comp
forall (comp :: Nat).
KnownNat comp =>
Double -> TDigest comp -> TDigest comp
insert
    snoc :: TDigest comp -> Double -> TDigest comp
snoc = (Double -> TDigest comp -> TDigest comp)
-> TDigest comp -> Double -> TDigest comp
forall a b c. (a -> b -> c) -> b -> a -> c
flip Double -> TDigest comp -> TDigest comp
forall (comp :: Nat).
KnownNat comp =>
Double -> TDigest comp -> TDigest comp
insert
    unit :: Double -> TDigest comp
unit = Double -> TDigest comp
forall (comp :: Nat). KnownNat comp => Double -> TDigest comp
singleton

instance KnownNat comp => Binary (TDigest comp) where
    get :: Get (TDigest comp)
get = do
        TDigest comp
t <- Get (TDigest comp)
forall t. Binary t => Get t
get
        Bool -> Get () -> Get ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (TDigest comp -> Int
forall (comp :: Nat). TDigest comp -> Int
T.size TDigest comp
t Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0) (Get () -> Get ()) -> Get () -> Get ()
forall a b. (a -> b) -> a -> b
$ String -> Get ()
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"empty TDigest.NonEmpty"
        TDigest comp -> Get (TDigest comp)
forall (m :: * -> *) a. Monad m => a -> m a
return (TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
TDigest TDigest comp
t)

    put :: TDigest comp -> Put
put (TDigest TDigest comp
t) = TDigest comp -> Put
forall t. Binary t => t -> Put
put TDigest comp
t

instance PP.HasHistogram (TDigest comp) Identity where
    histogram :: TDigest comp -> Identity (NonEmpty HistBin)
histogram   = Identity (NonEmpty HistBin)
-> (NonEmpty HistBin -> Identity (NonEmpty HistBin))
-> Maybe (NonEmpty HistBin)
-> Identity (NonEmpty HistBin)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (String -> Identity (NonEmpty HistBin)
forall a. HasCallStack => String -> a
error String
"NonEmpty.histogram") NonEmpty HistBin -> Identity (NonEmpty HistBin)
forall a. a -> Identity a
Identity (Maybe (NonEmpty HistBin) -> Identity (NonEmpty HistBin))
-> (TDigest comp -> Maybe (NonEmpty HistBin))
-> TDigest comp
-> Identity (NonEmpty HistBin)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> Maybe (NonEmpty HistBin)
forall a (f :: * -> *).
HasHistogram a f =>
a -> f (NonEmpty HistBin)
PP.histogram (TDigest comp -> Maybe (NonEmpty HistBin))
-> (TDigest comp -> TDigest comp)
-> TDigest comp
-> Maybe (NonEmpty HistBin)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty
    totalWeight :: TDigest comp -> Double
totalWeight = TDigest comp -> Double
forall a (f :: * -> *). HasHistogram a f => a -> Double
PP.totalWeight (TDigest comp -> Double)
-> (TDigest comp -> TDigest comp) -> TDigest comp -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

-------------------------------------------------------------------------------
-- Functions
-------------------------------------------------------------------------------

overTDigest :: (T.TDigest c -> T.TDigest c) -> TDigest c -> TDigest c
overTDigest :: (TDigest c -> TDigest c) -> TDigest c -> TDigest c
overTDigest TDigest c -> TDigest c
f = TDigest c -> TDigest c
forall (comp :: Nat). TDigest comp -> TDigest comp
TDigest (TDigest c -> TDigest c)
-> (TDigest c -> TDigest c) -> TDigest c -> TDigest c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest c -> TDigest c
f (TDigest c -> TDigest c)
-> (TDigest c -> TDigest c) -> TDigest c -> TDigest c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest c -> TDigest c
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

singleton :: KnownNat comp => Double -> TDigest comp
singleton :: Double -> TDigest comp
singleton = TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
TDigest (TDigest comp -> TDigest comp)
-> (Double -> TDigest comp) -> Double -> TDigest comp
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Double -> TDigest comp
forall (comp :: Nat). KnownNat comp => Double -> TDigest comp
T.singleton

insert :: KnownNat comp => Double -> TDigest comp -> TDigest comp
insert :: Double -> TDigest comp -> TDigest comp
insert Double
x = TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
TDigest (TDigest comp -> TDigest comp)
-> (TDigest comp -> TDigest comp) -> TDigest comp -> TDigest comp
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Double -> TDigest comp -> TDigest comp
forall (comp :: Nat).
KnownNat comp =>
Double -> TDigest comp -> TDigest comp
T.insert Double
x (TDigest comp -> TDigest comp)
-> (TDigest comp -> TDigest comp) -> TDigest comp -> TDigest comp
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

insert' :: KnownNat comp => Double -> TDigest comp -> TDigest comp
insert' :: Double -> TDigest comp -> TDigest comp
insert' Double
x =  (TDigest comp -> TDigest comp) -> TDigest comp -> TDigest comp
forall (c :: Nat).
(TDigest c -> TDigest c) -> TDigest c -> TDigest c
overTDigest ((TDigest comp -> TDigest comp) -> TDigest comp -> TDigest comp)
-> (TDigest comp -> TDigest comp) -> TDigest comp -> TDigest comp
forall a b. (a -> b) -> a -> b
$ Double -> TDigest comp -> TDigest comp
forall (comp :: Nat).
KnownNat comp =>
Double -> TDigest comp -> TDigest comp
T.insert' Double
x

compress :: forall comp. KnownNat comp => TDigest comp -> TDigest comp
compress :: TDigest comp -> TDigest comp
compress = (TDigest comp -> TDigest comp) -> TDigest comp -> TDigest comp
forall (c :: Nat).
(TDigest c -> TDigest c) -> TDigest c -> TDigest c
overTDigest TDigest comp -> TDigest comp
forall (comp :: Nat). KnownNat comp => TDigest comp -> TDigest comp
T.compress

forceCompress :: forall comp. KnownNat comp => TDigest comp -> TDigest comp
forceCompress :: TDigest comp -> TDigest comp
forceCompress = (TDigest comp -> TDigest comp) -> TDigest comp -> TDigest comp
forall (c :: Nat).
(TDigest c -> TDigest c) -> TDigest c -> TDigest c
overTDigest TDigest comp -> TDigest comp
forall (comp :: Nat). KnownNat comp => TDigest comp -> TDigest comp
T.forceCompress

minimumValue :: TDigest comp -> Mean
minimumValue :: TDigest comp -> Double
minimumValue = TDigest comp -> Double
forall (comp :: Nat). TDigest comp -> Double
T.minimumValue (TDigest comp -> Double)
-> (TDigest comp -> TDigest comp) -> TDigest comp -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

maximumValue :: TDigest comp -> Mean
maximumValue :: TDigest comp -> Double
maximumValue = TDigest comp -> Double
forall (comp :: Nat). TDigest comp -> Double
T.maximumValue (TDigest comp -> Double)
-> (TDigest comp -> TDigest comp) -> TDigest comp -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

totalWeight :: TDigest comp -> Weight
totalWeight :: TDigest comp -> Double
totalWeight = TDigest comp -> Double
forall (comp :: Nat). TDigest comp -> Double
T.totalWeight (TDigest comp -> Double)
-> (TDigest comp -> TDigest comp) -> TDigest comp -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

median :: TDigest comp -> Double
median :: TDigest comp -> Double
median = Identity Double -> Double
forall a. Identity a -> a
runIdentity (Identity Double -> Double)
-> (TDigest comp -> Identity Double) -> TDigest comp -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> Identity Double
forall a (f :: * -> *). HasHistogram a f => a -> f Double
PP.median

quantile :: Double -> TDigest comp -> Double
quantile :: Double -> TDigest comp -> Double
quantile Double
q = Identity Double -> Double
forall a. Identity a -> a
runIdentity (Identity Double -> Double)
-> (TDigest comp -> Identity Double) -> TDigest comp -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Double -> TDigest comp -> Identity Double
forall a (f :: * -> *). HasHistogram a f => Double -> a -> f Double
PP.quantile Double
q

mean :: TDigest comp -> Double
mean :: TDigest comp -> Double
mean = Identity Double -> Double
forall a. Identity a -> a
runIdentity (Identity Double -> Double)
-> (TDigest comp -> Identity Double) -> TDigest comp -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> Identity Double
forall a (f :: * -> *). HasHistogram a f => a -> f Double
PP.mean

variance :: TDigest comp -> Double
variance :: TDigest comp -> Double
variance = Identity Double -> Double
forall a. Identity a -> a
runIdentity (Identity Double -> Double)
-> (TDigest comp -> Identity Double) -> TDigest comp -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> Identity Double
forall a (f :: * -> *). HasHistogram a f => a -> f Double
PP.variance

stddev :: TDigest comp -> Double
stddev :: TDigest comp -> Double
stddev = Identity Double -> Double
forall a. Identity a -> a
runIdentity (Identity Double -> Double)
-> (TDigest comp -> Identity Double) -> TDigest comp -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> Identity Double
forall a (f :: * -> *). HasHistogram a f => a -> f Double
PP.variance

-- | Alias of 'quantile'.
icdf :: Double -> TDigest comp -> Double
icdf :: Double -> TDigest comp -> Double
icdf = Double -> TDigest comp -> Double
forall (comp :: Nat). Double -> TDigest comp -> Double
quantile

cdf :: Double -> TDigest comp -> Double
cdf :: Double -> TDigest comp -> Double
cdf = Double -> TDigest comp -> Double
forall a (f :: * -> *). HasHistogram a f => Double -> a -> Double
PP.cdf

tdigest :: (Foldable1 f, KnownNat comp) => f Double -> TDigest comp
tdigest :: f Double -> TDigest comp
tdigest = TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
TDigest (TDigest comp -> TDigest comp)
-> (f Double -> TDigest comp) -> f Double -> TDigest comp
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f Double -> TDigest comp
forall (f :: * -> *) (comp :: Nat).
(Foldable f, KnownNat comp) =>
f Double -> TDigest comp
T.tdigest

size :: TDigest comp -> Int
size :: TDigest comp -> Int
size = TDigest comp -> Int
forall (comp :: Nat). TDigest comp -> Int
T.size (TDigest comp -> Int)
-> (TDigest comp -> TDigest comp) -> TDigest comp -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

valid :: TDigest comp -> Bool
valid :: TDigest comp -> Bool
valid = TDigest comp -> Bool
forall (comp :: Nat). TDigest comp -> Bool
T.valid (TDigest comp -> Bool)
-> (TDigest comp -> TDigest comp) -> TDigest comp -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

validate :: TDigest comp -> Either String (TDigest comp)
validate :: TDigest comp -> Either String (TDigest comp)
validate = (TDigest comp -> TDigest comp)
-> Either String (TDigest comp) -> Either String (TDigest comp)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
TDigest (Either String (TDigest comp) -> Either String (TDigest comp))
-> (TDigest comp -> Either String (TDigest comp))
-> TDigest comp
-> Either String (TDigest comp)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> Either String (TDigest comp)
forall (comp :: Nat). TDigest comp -> Either String (TDigest comp)
T.validate (TDigest comp -> Either String (TDigest comp))
-> (TDigest comp -> TDigest comp)
-> TDigest comp
-> Either String (TDigest comp)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

debugPrint :: TDigest comp -> IO ()
debugPrint :: TDigest comp -> IO ()
debugPrint = TDigest comp -> IO ()
forall (comp :: Nat). TDigest comp -> IO ()
T.debugPrint (TDigest comp -> IO ())
-> (TDigest comp -> TDigest comp) -> TDigest comp -> IO ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TDigest comp -> TDigest comp
forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty

-- $setup
-- >>> :set -XDataKinds
-- >>> import Prelude.Compat
-- >>> import Data.List.NonEmpty (NonEmpty (..))
-- >>> import Data.List.Compat (foldl')
--
-- >>> let merge [] ys = []; merge xs [] = xs; merge (x:xs) (y:ys) = x : y : merge xs ys
-- >>> let fairshuffle' xs = uncurry merge (splitAt (length xs `div` 2) xs)
-- >>> let fairshuffle xs = iterate fairshuffle' xs !! 5