module Median ( median ) where

import           Control.Monad.Primitive      (PrimMonad, PrimState)
import qualified Data.Vector.Algorithms.Merge as Merge
import           Data.Vector.Generic.Mutable  (MVector)
import qualified Data.Vector.Generic.Mutable  as MV

{-# INLINABLE median #-}
median :: (PrimMonad m, MVector v e, Ord e, Fractional e) => v (PrimState m) e -> m e
median :: forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e, Ord e, Fractional e) =>
v (PrimState m) e -> m e
median v (PrimState m) e
v = do
    forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e, Ord e) =>
v (PrimState m) e -> m ()
Merge.sort v (PrimState m) e
v
    let l :: Int
l = forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
MV.length v (PrimState m) e
v
    if forall a. Integral a => a -> Bool
odd Int
l
        then v (PrimState m) e
v forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
`MV.read` ((Int
l forall a. Num a => a -> a -> a
- Int
1) forall a. Integral a => a -> a -> a
`div` Int
2)
        else do
            e
x0 <- v (PrimState m) e
v forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
`MV.read` ((Int
l forall a. Integral a => a -> a -> a
`div` Int
2) forall a. Num a => a -> a -> a
- Int
1)
            e
x1 <- v (PrimState m) e
v forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
`MV.read` (Int
l forall a. Integral a => a -> a -> a
`div` Int
2)
            forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ (e
x0 forall a. Num a => a -> a -> a
+ e
x1) forall a. Fractional a => a -> a -> a
/ e
2