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

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
    v (PrimState m) e -> m ()
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 = v (PrimState m) e -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
MV.length v (PrimState m) e
v
    if Int -> Bool
forall a. Integral a => a -> Bool
odd Int
l
        then v (PrimState m) e
v v (PrimState m) e -> Int -> m e
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
`MV.read` ((Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2)
        else do
            e
x0 <- v (PrimState m) e
v v (PrimState m) e -> Int -> m e
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
`MV.read` ((Int
l Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
            e
x1 <- v (PrimState m) e
v v (PrimState m) e -> Int -> m e
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
`MV.read` (Int
l Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2)
            e -> m e
forall (f :: * -> *) a. Applicative f => a -> f a
pure (e -> m e) -> e -> m e
forall a b. (a -> b) -> a -> b
$ (e
x0 e -> e -> e
forall a. Num a => a -> a -> a
+ e
x1) e -> e -> e
forall a. Fractional a => a -> a -> a
/ e
2