{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances #-}
{-# LANGUAGE Safe #-}

{- |
    Module      :  SDP.Index
    Copyright   :  (c) Andrey Mulik 2019
    License     :  BSD-style
    Maintainer  :  work.a.mulik@gmail.com
    Portability :  portable
    
    "SDP.Sort" provides 'Sort' - class of sortable immutable structures.
-}
module SDP.Sort
(
  -- * Sort
  Sort (..), sort, sortOn, sorted, sortedOn
)
where

import Prelude ()
import SDP.SafePrelude
import SDP.Zip

import qualified Data.List as L

default ()

--------------------------------------------------------------------------------

-- | 'Sort' is class of types that can be sorted.
class Sort s e | s -> e
  where
    {-# MINIMAL sortBy, sortedBy #-}
    
    {- |
      Checks if structure is already sorted. Should always return 'True' for
      structures with less than 2 elements.
    -}
    sortedBy :: (e -> e -> Bool) -> s -> Bool
    
    -- | 'sortBy' function is common sorting algorithm.
    sortBy :: Compare e -> s -> s

instance Sort [a] a
  where
    sortedBy :: (a -> a -> Bool) -> [a] -> Bool
sortedBy a -> a -> Bool
f (a
e : [a]
es) = (a -> a -> Bool) -> [a] -> [a] -> Bool
forall (z :: * -> *) a b.
Zip z =>
(a -> b -> Bool) -> z a -> z b -> Bool
all2 a -> a -> Bool
f (a
e a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
es) [a]
es
    sortedBy a -> a -> Bool
_    []    = Bool
True
    
    sortBy :: Compare a -> [a] -> [a]
sortBy = Compare a -> [a] -> [a]
forall a. Compare a -> [a] -> [a]
L.sortBy

--------------------------------------------------------------------------------

-- | Checks if the structure is 'sorted'.
sorted :: (Sort s e, Ord e) => s -> Bool
sorted :: s -> Bool
sorted =  (e -> e -> Bool) -> s -> Bool
forall s e. Sort s e => (e -> e -> Bool) -> s -> Bool
sortedBy e -> e -> Bool
forall a. Ord a => a -> a -> Bool
(<=)

-- | Sort by comparing the results of a given function applied to each element.
sortedOn :: (Sort s e, Ord o) => (e -> o) -> s -> Bool
sortedOn :: (e -> o) -> s -> Bool
sortedOn =  (e -> e -> Bool) -> s -> Bool
forall s e. Sort s e => (e -> e -> Bool) -> s -> Bool
sortedBy ((e -> e -> Bool) -> s -> Bool)
-> ((e -> o) -> e -> e -> Bool) -> (e -> o) -> s -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((o -> o -> Bool) -> (e -> o) -> e -> e -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
on o -> o -> Bool
forall a. Ord a => a -> a -> Bool
(<=))

-- | 'sort' is just @'sortBy' 'compare'@
sort :: (Sort s e, Ord e) => s -> s
sort :: s -> s
sort =  Compare e -> s -> s
forall s e. Sort s e => Compare e -> s -> s
sortBy Compare e
forall a. Ord a => a -> a -> Ordering
compare

-- | Sort by comparing the results of a given function applied to each element.
sortOn :: (Sort s e, Ord o) => (e -> o) -> s -> s
sortOn :: (e -> o) -> s -> s
sortOn =  Compare e -> s -> s
forall s e. Sort s e => Compare e -> s -> s
sortBy (Compare e -> s -> s)
-> ((e -> o) -> Compare e) -> (e -> o) -> s -> s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (e -> o) -> Compare e
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing