-- |
-- Module      : OAlg.Data.Ord
-- Description : ordering
-- Copyright   : (c) Erich Gut
-- License     : BSD3
-- Maintainer  : zerich.gut@gmail.com
--
-- "Data.Ord" enriched with some additional elements.
module OAlg.Data.Ord
  ( -- * Total
    module Ord
  , fcompare, wcompare, coCompare, compare2
  , sortFst, sortFstBy, sortSnd, sortSndBy
  , Closer(..), cmin, cmax, cspan, Span, enumSpan

    -- * Partial
  , POrd(..)
  )
  where

import Data.List (sortBy)
import Data.Ord as Ord

--------------------------------------------------------------------------------
-- fcompare -

-- | comparing according to the mapped values.
fcompare :: Ord i => (a -> i) -> a -> a -> Ordering
fcompare :: forall i a. Ord i => (a -> i) -> a -> a -> Ordering
fcompare a -> i
f a
x a
y = forall a. Ord a => a -> a -> Ordering
compare (a -> i
f a
x) (a -> i
f a
y)

--------------------------------------------------------------------------------
-- wcompare -

-- | comparing according to the given ordering relation on the mapped values.
wcompare :: (w -> w -> Ordering) -> (a -> w) -> a -> a -> Ordering
wcompare :: forall w a. (w -> w -> Ordering) -> (a -> w) -> a -> a -> Ordering
wcompare w -> w -> Ordering
cmp a -> w
f a
x a
y = w -> w -> Ordering
cmp (a -> w
f a
x) (a -> w
f a
y)

--------------------------------------------------------------------------------
-- coCompare -

-- | the /reverse/ ordering
coCompare :: (a -> a -> Ordering) -> a -> a -> Ordering
coCompare :: forall a. (a -> a -> Ordering) -> a -> a -> Ordering
coCompare a -> a -> Ordering
cmp a
x a
y = a -> a -> Ordering
cmp a
y a
x

--------------------------------------------------------------------------------
-- compare2 -

-- | comparing of pairs.
compare2 :: (a -> a -> Ordering) -> (b -> b -> Ordering) -> (a,b) -> (a,b) -> Ordering
compare2 :: forall a b.
(a -> a -> Ordering)
-> (b -> b -> Ordering) -> (a, b) -> (a, b) -> Ordering
compare2 a -> a -> Ordering
acmp b -> b -> Ordering
bcmp (a
a,b
b) (a
a',b
b') = case a
a a -> a -> Ordering
`acmp` a
a' of
  Ordering
EQ -> b
b b -> b -> Ordering
`bcmp` b
b'
  Ordering
o  -> Ordering
o

--------------------------------------------------------------------------------
-- sortFstBy -

-- | sorting according to the first component.
sortFstBy :: (a -> a -> Ordering) -> [(a,b)] -> [(a,b)]
sortFstBy :: forall a b. (a -> a -> Ordering) -> [(a, b)] -> [(a, b)]
sortFstBy a -> a -> Ordering
cmp = forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (forall w a. (w -> w -> Ordering) -> (a -> w) -> a -> a -> Ordering
wcompare a -> a -> Ordering
cmp forall a b. (a, b) -> a
fst)

--------------------------------------------------------------------------------
-- sortFst -

-- | sorting according to the first component.
sortFst :: Ord a => [(a,b)] -> [(a,b)]
sortFst :: forall a b. Ord a => [(a, b)] -> [(a, b)]
sortFst = forall a b. (a -> a -> Ordering) -> [(a, b)] -> [(a, b)]
sortFstBy forall a. Ord a => a -> a -> Ordering
compare

--------------------------------------------------------------------------------
-- sortSndBy -

-- | sorting according to the second component.
sortSndBy :: (b -> b -> Ordering) -> [(a,b)] -> [(a,b)]
sortSndBy :: forall b a. (b -> b -> Ordering) -> [(a, b)] -> [(a, b)]
sortSndBy b -> b -> Ordering
cmp = forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (forall w a. (w -> w -> Ordering) -> (a -> w) -> a -> a -> Ordering
wcompare b -> b -> Ordering
cmp forall a b. (a, b) -> b
snd)

--------------------------------------------------------------------------------
-- sortSnd -

-- | sorting according to the second component.
sortSnd :: Ord b => [(a,b)] -> [(a,b)]
sortSnd :: forall b a. Ord b => [(a, b)] -> [(a, b)]
sortSnd = forall b a. (b -> b -> Ordering) -> [(a, b)] -> [(a, b)]
sortSndBy forall a. Ord a => a -> a -> Ordering
compare

--------------------------------------------------------------------------------
-- Closer -

-- | the closer of a linear ordered @__x__@.
data Closer x
  = NegInf
  | It x
  | PosInf
  deriving (Int -> Closer x -> ShowS
forall x. Show x => Int -> Closer x -> ShowS
forall x. Show x => [Closer x] -> ShowS
forall x. Show x => Closer x -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Closer x] -> ShowS
$cshowList :: forall x. Show x => [Closer x] -> ShowS
show :: Closer x -> String
$cshow :: forall x. Show x => Closer x -> String
showsPrec :: Int -> Closer x -> ShowS
$cshowsPrec :: forall x. Show x => Int -> Closer x -> ShowS
Show,ReadPrec [Closer x]
ReadPrec (Closer x)
ReadS [Closer x]
forall x. Read x => ReadPrec [Closer x]
forall x. Read x => ReadPrec (Closer x)
forall x. Read x => Int -> ReadS (Closer x)
forall x. Read x => ReadS [Closer x]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Closer x]
$creadListPrec :: forall x. Read x => ReadPrec [Closer x]
readPrec :: ReadPrec (Closer x)
$creadPrec :: forall x. Read x => ReadPrec (Closer x)
readList :: ReadS [Closer x]
$creadList :: forall x. Read x => ReadS [Closer x]
readsPrec :: Int -> ReadS (Closer x)
$creadsPrec :: forall x. Read x => Int -> ReadS (Closer x)
Read,Closer x -> Closer x -> Bool
forall x. Eq x => Closer x -> Closer x -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Closer x -> Closer x -> Bool
$c/= :: forall x. Eq x => Closer x -> Closer x -> Bool
== :: Closer x -> Closer x -> Bool
$c== :: forall x. Eq x => Closer x -> Closer x -> Bool
Eq,Closer x -> Closer x -> Bool
Closer x -> Closer x -> Ordering
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {x}. Ord x => Eq (Closer x)
forall x. Ord x => Closer x -> Closer x -> Bool
forall x. Ord x => Closer x -> Closer x -> Ordering
forall x. Ord x => Closer x -> Closer x -> Closer x
min :: Closer x -> Closer x -> Closer x
$cmin :: forall x. Ord x => Closer x -> Closer x -> Closer x
max :: Closer x -> Closer x -> Closer x
$cmax :: forall x. Ord x => Closer x -> Closer x -> Closer x
>= :: Closer x -> Closer x -> Bool
$c>= :: forall x. Ord x => Closer x -> Closer x -> Bool
> :: Closer x -> Closer x -> Bool
$c> :: forall x. Ord x => Closer x -> Closer x -> Bool
<= :: Closer x -> Closer x -> Bool
$c<= :: forall x. Ord x => Closer x -> Closer x -> Bool
< :: Closer x -> Closer x -> Bool
$c< :: forall x. Ord x => Closer x -> Closer x -> Bool
compare :: Closer x -> Closer x -> Ordering
$ccompare :: forall x. Ord x => Closer x -> Closer x -> Ordering
Ord)

--------------------------------------------------------------------------------
-- cmax -

-- | the maximum of the items of a list, i.e. the smallest upper bound.
--
--  __Property__ Let @xs@ be in @[__x__]@ for a linear ordered @__x__@, then holds:
--  For all @x@ in @xs@ holds: @'It' x '<=' 'cmax' xs@.
cmax :: Ord x => [x] -> Closer x
cmax :: forall x. Ord x => [x] -> Closer x
cmax []     = forall x. Closer x
NegInf
cmax (x
x:[x]
xs) = forall a. Ord a => a -> a -> a
max (forall x. x -> Closer x
It x
x) (forall x. Ord x => [x] -> Closer x
cmax [x]
xs)

--------------------------------------------------------------------------------
-- cmin -

-- | the minimum of the items of a list, i.e. the biggest lower bound.
--
--  __Property__ Let @xs@ be in @[__x__]@ for a linear ordered @__x__@, then holds:
--  For all @x@ in @xs@ holds: @'cmin' xs '<=' 'It' x@.
cmin :: Ord x => [x] -> Closer x
cmin :: forall x. Ord x => [x] -> Closer x
cmin []     = forall x. Closer x
PosInf
cmin (x
x:[x]
xs) = forall a. Ord a => a -> a -> a
min (forall x. x -> Closer x
It x
x) (forall x. Ord x => [x] -> Closer x
cmin [x]
xs)

--------------------------------------------------------------------------------
-- Span -

-- | the span type.
type Span x = (Closer x,Closer x)

--------------------------------------------------------------------------------
-- cspan -

-- | @(l,u) = 'cspan' xs@ where @l@ is the minimum and @u@ the maximum of the items in
--   @xs@.
--
--  __Example__
--
-- >>> cspan "aeb"
-- (It 'a',It 'e')
--
-- >>> cspan ""
-- (PosInf,NegInf)
cspan :: Ord x => [x] -> Span x
cspan :: forall x. Ord x => [x] -> Span x
cspan []     = (forall x. Closer x
PosInf,forall x. Closer x
NegInf)
cspan (x
x:[x]
xs) = (forall a. Ord a => a -> a -> a
min (forall x. x -> Closer x
It x
x) Closer x
l,forall a. Ord a => a -> a -> a
max (forall x. x -> Closer x
It x
x) Closer x
u) where (Closer x
l,Closer x
u) = forall x. Ord x => [x] -> Span x
cspan [x]
xs

--------------------------------------------------------------------------------
-- enumSpan -

-- | @'enumSpan' i0 h@ enumerates the index, starting by @i0@ to @h@. 
enumSpan :: (Enum i, Ord i) => i -> Closer i -> [i]
enumSpan :: forall i. (Enum i, Ord i) => i -> Closer i -> [i]
enumSpan i
i0 Closer i
h | Closer i
h forall a. Ord a => a -> a -> Bool
< forall x. x -> Closer x
It i
i0 = []
enumSpan i
i0 Closer i
PosInf        = [i
i0..]
enumSpan i
i0 (It i
h)        = [i
i0..i
h]
enumSpan i
_ Closer i
NegInf         = []

--------------------------------------------------------------------------------
-- POrd -

-- | partially ordered types.
--
--  __Properties__ Let @__a__@ be an instance of 'POrd', then holds:
--
--  (1) For all @x@ in @__a__@ holds: @x '<<=' x@.
--
--  (2) For all @x@, @y@ in @__a__@ holds: If @x '<<=' y@ and @y '<<=' x@ then
--  @x '==' y@.
--
--  (3) For all @x@, @y@, @z@ in @__a__@ holds: If @x '<<=' y@ and @y '<<=' z@ then
--  @x '<<=' z@.
class Eq a => POrd a where

  infix 4 <<=
  (<<=) :: a -> a -> Bool