{-# 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.Foldable1         (Foldable1)
import Data.Functor.Identity  (Identity (..))
import Data.Semigroup         (Semigroup (..))
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 { forall (comp :: Nat). TDigest comp -> TDigest comp
unEmpty :: T.TDigest comp }

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

instance NFData (TDigest comp) where
    rnf :: TDigest comp -> ()
rnf (TDigest TDigest comp
t) = 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) = 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 = forall (comp :: Nat). TDigest comp -> TDigest comp
TDigest (TDigest comp
a 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 = forall (comp :: Nat).
KnownNat comp =>
Double -> TDigest comp -> TDigest comp
insert
    snoc :: TDigest comp -> Double -> TDigest comp
snoc = forall a b c. (a -> b -> c) -> b -> a -> c
flip forall (comp :: Nat).
KnownNat comp =>
Double -> TDigest comp -> TDigest comp
insert
    unit :: Double -> TDigest comp
unit = 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 <- forall t. Binary t => Get t
get
        forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (forall (comp :: Nat). TDigest comp -> Int
T.size TDigest comp
t forall a. Ord a => a -> a -> Bool
<= Int
0) forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"empty TDigest.NonEmpty"
        forall (m :: * -> *) a. Monad m => a -> m a
return (forall (comp :: Nat). TDigest comp -> TDigest comp
TDigest TDigest comp
t)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

debugPrint :: TDigest comp -> IO ()
debugPrint :: forall (comp :: Nat). TDigest comp -> IO ()
debugPrint = forall (comp :: Nat). TDigest comp -> IO ()
T.debugPrint forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 (Prelude.length xs `div` 2) xs)
-- >>> let fairshuffle xs = iterate fairshuffle' xs !! 5