{-
%------------------------------------------------------------------------------
% Copyright (C) 1997, 1998, 2008 Joern Dinkla, www.dinkla.net
%------------------------------------------------------------------------------
%
% see
%     Joern Dinkla, Geometrische Algorithmen in Haskell, Diploma Thesis,
%     University of Bonn, Germany, 1998. 
%
-}

-- | Order statistics, see [CLR90, ch. 10.3].
-- Warning: The suboptimal algorithm 'naiveSelect' shows a much better real-life performance for many inputs.

module GeomAlg.External.OrderStat (
	-- * An optimal version with O(n) running time.
	selectBy, select, medianBy, median,
	-- * Naive version with O(n log n) running time.
        naiveSelectBy, naiveSelect, naiveMedianBy, naiveMedian 
       ) where

import GeomAlg.External.Sorting (sortBy, partition, isortBy, partition3)
import GeomAlg.External.Utilities (isSingleton, leqRel, longerThan, splitsAt)

-- | Select the ith element with respect to the 'Ordering' @cmp@. The first element has an index of 0. This functions takes O(n) time.
selectBy		      :: (a -> a -> Ordering) -> Int -> [a] -> a
selectBy cmp i xs
  | xs `longerThan` 5         = if i < k then selectBy cmp i ls 
                                else if i < l then head es
                                else selectBy cmp (i-l) hs
  | otherwise                 = sort xs !! i
  where 
    m                         = medianOfMedians xs
    (ls, es, hs)	      = partition3 (flip cmp (medianOfMedians xs)) xs
    k			      = length ls
    l			      = k + length es
    leq			      = leqRel cmp
    sort		      = isortBy leq
    medianOfMedians           = head . until isSingleton (map (median5 . sort) . splitsAt 5)
    median5 [_,_,x,_,_]       = x
    median5 [_,x,y,_]         = if x `leq` y then x else y
    median5 [_,x,_]           = x
    median5 [x,y]             = if x `leq` y then x else y
    median5 [x]               = x

-- | Select with respect to the class 'Ord', i. e. the function 'compare'.
select           	      :: Ord a => Int -> [a] -> a
select			      = selectBy compare

-- | 'medianBy' selects the median of a list with respect to an 'Ordering' relation.
medianBy		      :: (a -> a -> Ordering) -> [a] -> a
medianBy cmp xs               = selectBy cmp (length xs `div` 2) xs

-- | Selects the median with respect to 'Ord'.
median			      :: Ord a => [a] -> a
median			      = medianBy compare

-- | The naive version uses '!!' and 'sortBy'.
naiveSelectBy                 :: (a -> a -> Ordering) -> Int -> [a] -> a
naiveSelectBy cmp k xs        = sortBy (leqRel cmp) xs !! k

-- | Naive selection with respect to 'Ord'.
naiveSelect                   :: Ord a => Int -> [a] -> a
naiveSelect		      = naiveSelectBy compare

-- | Naive median with respect to the 'Ordering' @cmp@.
naiveMedianBy       	      :: (a -> a -> Ordering) -> [a] -> a
naiveMedianBy cmp xs          = naiveSelectBy cmp (length xs `div` 2) xs

-- | Naive median with a worst case running time of O(n log n).
naiveMedian                   :: Ord a => [a] -> a
naiveMedian	              = naiveMedianBy compare