-- |

-- 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
  ( module Ord
  , fcompare, wcompare, coCompare, compare2
  , sortFst, sortFstBy, sortSnd, sortSndBy
  , Closure(..), cmin, cmax, cspan, Span, enumSpan
  )
  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 = i -> i -> Ordering
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 = ((a, b) -> (a, b) -> Ordering) -> [(a, b)] -> [(a, b)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy ((a -> a -> Ordering)
-> ((a, b) -> a) -> (a, b) -> (a, b) -> Ordering
forall w a. (w -> w -> Ordering) -> (a -> w) -> a -> a -> Ordering
wcompare a -> a -> Ordering
cmp (a, b) -> a
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 = (a -> a -> Ordering) -> [(a, b)] -> [(a, b)]
forall a b. (a -> a -> Ordering) -> [(a, b)] -> [(a, b)]
sortFstBy a -> a -> Ordering
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 = ((a, b) -> (a, b) -> Ordering) -> [(a, b)] -> [(a, b)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy ((b -> b -> Ordering)
-> ((a, b) -> b) -> (a, b) -> (a, b) -> Ordering
forall w a. (w -> w -> Ordering) -> (a -> w) -> a -> a -> Ordering
wcompare b -> b -> Ordering
cmp (a, b) -> b
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 = (b -> b -> Ordering) -> [(a, b)] -> [(a, b)]
forall b a. (b -> b -> Ordering) -> [(a, b)] -> [(a, b)]
sortSndBy b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare

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

-- Closure -


-- | the closer of a linear ordered @__x__@.

data Closure x
  = NegInf
  | It x
  | PosInf
  deriving (Int -> Closure x -> ShowS
[Closure x] -> ShowS
Closure x -> String
(Int -> Closure x -> ShowS)
-> (Closure x -> String)
-> ([Closure x] -> ShowS)
-> Show (Closure x)
forall x. Show x => Int -> Closure x -> ShowS
forall x. Show x => [Closure x] -> ShowS
forall x. Show x => Closure x -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall x. Show x => Int -> Closure x -> ShowS
showsPrec :: Int -> Closure x -> ShowS
$cshow :: forall x. Show x => Closure x -> String
show :: Closure x -> String
$cshowList :: forall x. Show x => [Closure x] -> ShowS
showList :: [Closure x] -> ShowS
Show,ReadPrec [Closure x]
ReadPrec (Closure x)
Int -> ReadS (Closure x)
ReadS [Closure x]
(Int -> ReadS (Closure x))
-> ReadS [Closure x]
-> ReadPrec (Closure x)
-> ReadPrec [Closure x]
-> Read (Closure x)
forall x. Read x => ReadPrec [Closure x]
forall x. Read x => ReadPrec (Closure x)
forall x. Read x => Int -> ReadS (Closure x)
forall x. Read x => ReadS [Closure x]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: forall x. Read x => Int -> ReadS (Closure x)
readsPrec :: Int -> ReadS (Closure x)
$creadList :: forall x. Read x => ReadS [Closure x]
readList :: ReadS [Closure x]
$creadPrec :: forall x. Read x => ReadPrec (Closure x)
readPrec :: ReadPrec (Closure x)
$creadListPrec :: forall x. Read x => ReadPrec [Closure x]
readListPrec :: ReadPrec [Closure x]
Read,Closure x -> Closure x -> Bool
(Closure x -> Closure x -> Bool)
-> (Closure x -> Closure x -> Bool) -> Eq (Closure x)
forall x. Eq x => Closure x -> Closure x -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall x. Eq x => Closure x -> Closure x -> Bool
== :: Closure x -> Closure x -> Bool
$c/= :: forall x. Eq x => Closure x -> Closure x -> Bool
/= :: Closure x -> Closure x -> Bool
Eq,Eq (Closure x)
Eq (Closure x) =>
(Closure x -> Closure x -> Ordering)
-> (Closure x -> Closure x -> Bool)
-> (Closure x -> Closure x -> Bool)
-> (Closure x -> Closure x -> Bool)
-> (Closure x -> Closure x -> Bool)
-> (Closure x -> Closure x -> Closure x)
-> (Closure x -> Closure x -> Closure x)
-> Ord (Closure x)
Closure x -> Closure x -> Bool
Closure x -> Closure x -> Ordering
Closure x -> Closure x -> Closure x
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 (Closure x)
forall x. Ord x => Closure x -> Closure x -> Bool
forall x. Ord x => Closure x -> Closure x -> Ordering
forall x. Ord x => Closure x -> Closure x -> Closure x
$ccompare :: forall x. Ord x => Closure x -> Closure x -> Ordering
compare :: Closure x -> Closure x -> Ordering
$c< :: forall x. Ord x => Closure x -> Closure x -> Bool
< :: Closure x -> Closure x -> Bool
$c<= :: forall x. Ord x => Closure x -> Closure x -> Bool
<= :: Closure x -> Closure x -> Bool
$c> :: forall x. Ord x => Closure x -> Closure x -> Bool
> :: Closure x -> Closure x -> Bool
$c>= :: forall x. Ord x => Closure x -> Closure x -> Bool
>= :: Closure x -> Closure x -> Bool
$cmax :: forall x. Ord x => Closure x -> Closure x -> Closure x
max :: Closure x -> Closure x -> Closure x
$cmin :: forall x. Ord x => Closure x -> Closure x -> Closure x
min :: Closure x -> Closure x -> Closure x
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] -> Closure x
cmax :: forall x. Ord x => [x] -> Closure x
cmax []     = Closure x
forall x. Closure x
NegInf
cmax (x
x:[x]
xs) = Closure x -> Closure x -> Closure x
forall a. Ord a => a -> a -> a
max (x -> Closure x
forall x. x -> Closure x
It x
x) ([x] -> Closure x
forall x. Ord x => [x] -> Closure 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] -> Closure x
cmin :: forall x. Ord x => [x] -> Closure x
cmin []     = Closure x
forall x. Closure x
PosInf
cmin (x
x:[x]
xs) = Closure x -> Closure x -> Closure x
forall a. Ord a => a -> a -> a
min (x -> Closure x
forall x. x -> Closure x
It x
x) ([x] -> Closure x
forall x. Ord x => [x] -> Closure x
cmin [x]
xs)

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

-- Span -


-- | the span type.

type Span x = (Closure x,Closure 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 []     = (Closure x
forall x. Closure x
PosInf,Closure x
forall x. Closure x
NegInf)
cspan (x
x:[x]
xs) = (Closure x -> Closure x -> Closure x
forall a. Ord a => a -> a -> a
min (x -> Closure x
forall x. x -> Closure x
It x
x) Closure x
l,Closure x -> Closure x -> Closure x
forall a. Ord a => a -> a -> a
max (x -> Closure x
forall x. x -> Closure x
It x
x) Closure x
u) where (Closure x
l,Closure x
u) = [x] -> (Closure x, Closure x)
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 -> Closure i -> [i]
enumSpan :: forall i. (Enum i, Ord i) => i -> Closure i -> [i]
enumSpan i
i0 Closure i
h | Closure i
h Closure i -> Closure i -> Bool
forall a. Ord a => a -> a -> Bool
< i -> Closure i
forall x. x -> Closure x
It i
i0 = []
enumSpan i
i0 Closure i
PosInf        = [i
i0..]
enumSpan i
i0 (It i
h)        = [i
i0..i
h]
enumSpan i
_ Closure i
NegInf         = []