-- |
-- Module      :  Data.MinMax
-- Copyright   :  (c) OleksandrZhabenko 2020
-- License     :  MIT
-- Stability   :  Experimental
-- Maintainer  :  olexandr543@yahoo.com
--
-- Functions to find both minimum and maximum elements of the 'F.Foldable' structure of the 'Ord'ered elements.

module Data.MinMax where

import Prelude hiding (takeWhile,dropWhile,span)
import Data.Maybe (fromJust)
import Data.SubG
import qualified Data.Foldable as F
import qualified Data.List as L (sort)

-- | Returns a pair where the first element is the minimum element from the two given ones and the second one is the maximum. If the arguments are
-- equal then the tuple contains equal elements.
minmaxP :: (Ord a) => a -> a -> (a,a)
minmaxP x y
 | x < y = (x,y)
 | otherwise = (y,x)

-- | A ternary predicate to check whether the third argument lies between the first two unequal ones or whether they are all equal.
betweenNX :: (Ord a) => a -> a -> a -> Bool
betweenNX x y z
 | x == y = x == z
 | z < k && z > t = True
 | otherwise = False
      where (t,k) = minmaxP x y

-- | Finds out the minimum and maximum values of the finite structure. If the latter one is empty returns 'Nothing', if all the elements are equal
-- (or it has just one) then it returns 'Just' tuple of equal elements.
minMax :: (Ord a, Foldable t) => t a -> Maybe (a, a)
minMax xs
 | F.null xs = Nothing
 | otherwise = Just . F.foldr f (x,x) $ xs
      where x = fromJust . safeHeadG $ xs
            f z (x,y)
              | z < x = (z,y)
              | z > y = (x,z)
              | otherwise = (x,y)

-- | A generalized variant of the 'minMax' where you can specify your own comparison function.
minMaxBy :: (Ord a, Foldable t) => (a -> a -> Ordering) -> t a -> Maybe (a, a)
minMaxBy g xs
 | F.null xs = Nothing
 | otherwise = Just . F.foldr f (x,x) $ xs
      where x = fromJust . safeHeadG $ xs
            f z (x,y)
              | g z x == LT = (z,y)
              | g z y == GT = (x,z)
              | otherwise = (x,y)

-- | Given a finite structure with at least 3 elements returns a tuple with the two most minimum elements
-- (the first one is less than the second one) and the maximum element. If the structure has less elements, returns 'Nothing'.
-- Uses just three passes through the structure, so may be more efficient than some other approaches.
minMax21 :: (Ord a, InsertLeft t a, Monoid (t a)) => t a -> Maybe ((a,a), a)
minMax21 xs
 | F.length xs < 3 = Nothing
 | otherwise = Just . F.foldr f ((n,p),q) $ str1
      where x = fromJust . safeHeadG $ xs
            (str1,str2) = splitAtEndG 3 xs
            [n,p,q] = L.sort . F.toList $ str2
            f z ((x,y),t)
              | z > t = ((x,y),z)
              | z < y = if z > x then ((x,z),t) else ((z,x),t)
              | otherwise = ((x,y),t)

-- | Given a finite structure with at least 3 elements returns a tuple with the minimum element
-- and two maximum elements (the first one is less than the second one). If the structure has less elements, returns 'Nothing'.
-- Uses just three passes through the structure, so may be more efficient than some other approaches.
minMax12 :: (Ord a, InsertLeft t a, Monoid (t a)) => t a -> Maybe (a, (a,a))
minMax12 xs
 | F.length xs < 3 = Nothing
 | otherwise = Just . F.foldr f (n,(p,q)) $ str1
      where x = fromJust . safeHeadG $ xs
            (str1,str2) = splitAtEndG 3 xs
            [n,p,q] = L.sort . F.toList $ str2
            f z (x,(y,t))
              | z < x = (z,(y,t))
              | z > y = if z < t then (x,(z,t)) else (x,(t,z))
              | otherwise = (x,(y,t))

-- | Given a finite structure with at least 4 elements returns a tuple with two minimum elements
-- and two maximum elements. If the structure has less elements, returns 'Nothing'.
-- Uses just three passes through the structure, so may be more efficient than some other approaches.
minMax22 :: (Ord a, InsertLeft t a, Monoid (t a)) => t a -> Maybe ((a,a), (a,a))
minMax22 xs
 | F.length xs < 4 = Nothing
 | otherwise = Just . F.foldr f ((n,p),(q,r)) $ str1
      where x = fromJust . safeHeadG $ xs
            (str1,str2) = splitAtEndG 4 xs
            [n,p,q,r] = L.sort . F.toList $ str2
            f z ((x,y),(t,w))
              | z < y = if z > x then ((x,z),(t,w)) else ((z,x),(t,w))
              | z > t = if z < w then ((x,y),(z,w)) else ((x,y),(w,z))
              | otherwise = ((x,y),(t,w))