-- | -- Module : Data.Median.Small -- Description : Optimal median-finding functions for small input. -- Copyright : (c) Donnacha Oisín Kidney, 2018 -- License : MIT -- Maintainer : mail@doisinkidney.com -- Stability : experimental -- Portability : portable -- -- This module provides optimal median-finding functions for small, -- fixed-size inputs. Each function returns the (0-based) index of the -- argument which is the median, according to the supplied relation. module Data.Median.Optimal (median3 ,median4 ,median5) where import GHC.Exts (inline) -- | Find the median of 3 items, optimally. -- -- >>> median3 (<=) 1 2 3 -- 1 -- >>> median3 (<=) 1 3 2 -- 2 -- >>> median3 (<=) 2 3 1 -- 0 -- -- prop> [x,y,z] !! median3 (<=) x y z === sort [x,y,z] !! 1 median3 :: (a -> a -> Bool) -> a -> a -> a -> Int median3 lte a b c = if inline lte a b then if inline lte a c then if inline lte b c then 1 else 2 else 0 else if inline lte b c then if inline lte a c then 0 else 2 else 1 {-# INLINE median3 #-} -- | Find the median of 4 items, optimally. -- -- >>> median4 (<=) 1 4 3 2 -- 2 -- >>> median4 (<=) 1 3 2 4 -- 1 -- >>> median4 (<=) 2 4 1 3 -- 3 -- >>> median4 (<=) 3 1 4 2 -- 0 -- -- prop> [w,x,y,z] !! median4 (<=) w x y z `elem` (init.tail.sort) [w,x,y,z] median4 :: (a -> a -> Bool) -> a -> a -> a -> a -> Int median4 lte a b c d = if inline lte a b then if inline lte c d then if inline lte b d then 1 else 3 else if inline lte b c then 1 else 2 else if inline lte c d then if inline lte a d then 0 else 3 else if inline lte a c then 0 else 2 {-# INLINE median4 #-} -- | Find the median of 5 items, optimally. -- -- >>> median5 (<=) 1 4 3 2 5 -- 2 -- >>> median5 (<=) 1 3 2 4 5 -- 1 -- >>> median5 (<=) 2 4 1 3 5 -- 3 -- >>> median5 (<=) 3 1 4 2 5 -- 0 -- >>> median5 (<=) 2 1 4 5 3 -- 4 -- -- prop> [v,w,x,y,z] !! median5 (<=) v w x y z === sort [v,w,x,y,z] !! 2 median5 :: (a -> a -> Bool) -> a -> a -> a -> a -> a -> Int median5 lte a b c d e = if inline lte a b then if inline lte c d then if inline lte a c then if inline lte b d then if inline lte b c then if inline lte a e then if inline lte c e then 2 else if inline lte b e then 4 else 1 else 1 else if inline lte a e then if inline lte b e then 1 else if inline lte c e then 4 else 2 else 2 else if inline lte a e then if inline lte d e then 3 else if inline lte c e then 4 else 2 else if inline lte d a then 3 else 2 else if inline lte b d then if inline lte c e then if inline lte b e then 1 else if inline lte a e then 4 else 0 else if inline lte b c then 1 else 0 else if inline lte d a then if inline lte c e then if inline lte a e then 0 else if inline lte d e then 4 else 3 else 3 else if inline lte c e then if inline lte d e then 3 else if inline lte a e then 4 else 0 else 0 else if inline lte a d then if inline lte b c then if inline lte b d then if inline lte a e then if inline lte d e then 3 else if inline lte b e then 4 else 1 else 1 else if inline lte a e then if inline lte b e then 1 else if inline lte d e then 4 else 3 else 3 else if inline lte a e then if inline lte c e then 2 else if inline lte d e then 4 else 3 else if inline lte c a then 2 else 3 else if inline lte b c then if inline lte d e then if inline lte b e then 1 else if inline lte a e then 4 else 0 else if inline lte b d then 1 else 0 else if inline lte c a then if inline lte d e then if inline lte a e then 0 else if inline lte c e then 4 else 2 else 2 else if inline lte d e then if inline lte c e then 2 else if inline lte a e then 4 else 0 else 0 else if inline lte c d then if inline lte b c then if inline lte a d then if inline lte a c then if inline lte b e then if inline lte c e then 2 else if inline lte a e then 4 else 0 else 0 else if inline lte b e then if inline lte a e then 0 else if inline lte c e then 4 else 2 else 2 else if inline lte b e then if inline lte d e then 3 else if inline lte c e then 4 else 2 else if inline lte d b then 3 else 2 else if inline lte a d then if inline lte c e then if inline lte a e then 0 else if inline lte b e then 4 else 1 else if inline lte a c then 0 else 1 else if inline lte d b then if inline lte c e then if inline lte b e then 1 else if inline lte d e then 4 else 3 else 3 else if inline lte c e then if inline lte d e then 3 else if inline lte b e then 4 else 1 else 1 else if inline lte b d then if inline lte a c then if inline lte a d then if inline lte b e then if inline lte d e then 3 else if inline lte a e then 4 else 0 else 0 else if inline lte b e then if inline lte a e then 0 else if inline lte d e then 4 else 3 else 3 else if inline lte b e then if inline lte c e then 2 else if inline lte d e then 4 else 3 else if inline lte c b then 2 else 3 else if inline lte a c then if inline lte d e then if inline lte a e then 0 else if inline lte b e then 4 else 1 else if inline lte a d then 0 else 1 else if inline lte c b then if inline lte d e then if inline lte b e then 1 else if inline lte c e then 4 else 2 else 2 else if inline lte d e then if inline lte c e then 2 else if inline lte b e then 4 else 1 else 1 {-# INLINE median5 #-} -- $setup -- >>> import Test.QuickCheck -- >>> import Data.List (sort)