module Autolib.Util.Sort

( sort, sortBy
, insert, insertBy
, nub, nubBy
, rise, riseBy
)

where

import Autolib.Util.Hide

-- utils ----------------------------------------------------------

hide :: ( a -> b ) -> a -> ( b, Hide a )
hide :: forall a b. (a -> b) -> a -> (b, Hide a)
hide a -> b
f a
x = ( a -> b
f a
x, a -> Hide a
forall a. a -> Hide a
Hide a
x )

seek :: ( b, Hide a) -> a
seek :: forall b a. (b, Hide a) -> a
seek ( b
_, Hide a
x ) = a
x

-- | merge sort
sort :: Ord a => [a] -> [a]
sort :: forall a. Ord a => [a] -> [a]
sort [] = []; sort [a
x] = [a
x]
sort [a]
xs = let ([a]
pre, [a]
post) = [a] -> ([a], [a])
forall {a}. [a] -> ([a], [a])
halves [a]
xs in [a] -> [a] -> [a]
forall {a}. Ord a => [a] -> [a] -> [a]
merge ([a] -> [a]
forall a. Ord a => [a] -> [a]
sort [a]
pre) ([a] -> [a]
forall a. Ord a => [a] -> [a]
sort [a]
post)
   where halves :: [a] -> ([a], [a])
halves [] = ([], [])
	 halves (a
x : [a]
xs) = let ([a]
pre, [a]
post) = [a] -> ([a], [a])
halves [a]
xs in (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
post, [a]
pre)
	 merge :: [a] -> [a] -> [a]
merge [] [a]
ys = [a]
ys; merge [a]
xs [] = [a]
xs
	 merge (a
x : [a]
xs) (a
y : [a]
ys) =
	       if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y then a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
xs (a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
ys)
			 else a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs) [a]
ys

sortBy :: Ord b => (a -> b) -> [a] -> [a]
sortBy :: forall b a. Ord b => (a -> b) -> [a] -> [a]
sortBy a -> b
f [a]
xs = ((b, Hide a) -> a) -> [(b, Hide a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (b, Hide a) -> a
forall b a. (b, Hide a) -> a
seek ([(b, Hide a)] -> [a]) -> [(b, Hide a)] -> [a]
forall a b. (a -> b) -> a -> b
$ [(b, Hide a)] -> [(b, Hide a)]
forall a. Ord a => [a] -> [a]
sort ([(b, Hide a)] -> [(b, Hide a)]) -> [(b, Hide a)] -> [(b, Hide a)]
forall a b. (a -> b) -> a -> b
$ (a -> (b, Hide a)) -> [a] -> [(b, Hide a)]
forall a b. (a -> b) -> [a] -> [b]
map ((a -> b) -> a -> (b, Hide a)
forall a b. (a -> b) -> a -> (b, Hide a)
hide a -> b
f) [a]
xs


insert :: Ord a => a -> [a] -> [a]
insert :: forall a. Ord a => a -> [a] -> [a]
insert a
x [] = [a
x]
insert a
x (a
y : [a]
ys) = 
    if a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
y then a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
ys else a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a -> [a] -> [a]
forall a. Ord a => a -> [a] -> [a]
insert a
x [a]
ys

insertBy :: Ord b => (a -> b) -> a -> [a] -> [a]
insertBy :: forall b a. Ord b => (a -> b) -> a -> [a] -> [a]
insertBy a -> b
f a
x [a]
xs = ((b, Hide a) -> a) -> [(b, Hide a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (b, Hide a) -> a
forall b a. (b, Hide a) -> a
seek ([(b, Hide a)] -> [a]) -> [(b, Hide a)] -> [a]
forall a b. (a -> b) -> a -> b
$ (b, Hide a) -> [(b, Hide a)] -> [(b, Hide a)]
forall a. Ord a => a -> [a] -> [a]
insert ((a -> b) -> a -> (b, Hide a)
forall a b. (a -> b) -> a -> (b, Hide a)
hide a -> b
f a
x) ((a -> (b, Hide a)) -> [a] -> [(b, Hide a)]
forall a b. (a -> b) -> [a] -> [b]
map ((a -> b) -> a -> (b, Hide a)
forall a b. (a -> b) -> a -> (b, Hide a)
hide a -> b
f) [a]
xs)


nub :: Ord a =>  [a] -> [a]
nub :: forall a. Ord a => [a] -> [a]
nub [] = []
nub (a
x : [a]
ys) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
forall a. Ord a => [a] -> [a]
nub ( (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
x) [a]
ys )


nubBy :: Ord b => (a -> b) -> [a] -> [a]
nubBy :: forall b a. Ord b => (a -> b) -> [a] -> [a]
nubBy a -> b
f [a]
xs = ((b, Hide a) -> a) -> [(b, Hide a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (b, Hide a) -> a
forall b a. (b, Hide a) -> a
seek ([(b, Hide a)] -> [a]) -> [(b, Hide a)] -> [a]
forall a b. (a -> b) -> a -> b
$ [(b, Hide a)] -> [(b, Hide a)]
forall a. Ord a => [a] -> [a]
nub ([(b, Hide a)] -> [(b, Hide a)]) -> [(b, Hide a)] -> [(b, Hide a)]
forall a b. (a -> b) -> a -> b
$ (a -> (b, Hide a)) -> [a] -> [(b, Hide a)]
forall a b. (a -> b) -> [a] -> [b]
map ((a -> b) -> a -> (b, Hide a)
forall a b. (a -> b) -> a -> (b, Hide a)
hide a -> b
f) [a]
xs

-- | produce strictly increasing subsequence
rise :: Ord a => [a] -> [a]
rise :: forall a. Ord a => [a] -> [a]
rise [] = []
rise (a
x : [a]
ys) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
forall a. Ord a => [a] -> [a]
rise ( (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
x) [a]
ys )

riseBy :: Ord b => (a -> b) -> [a] -> [a]
riseBy :: forall b a. Ord b => (a -> b) -> [a] -> [a]
riseBy a -> b
f [a]
xs = ((b, Hide a) -> a) -> [(b, Hide a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (b, Hide a) -> a
forall b a. (b, Hide a) -> a
seek ([(b, Hide a)] -> [a]) -> [(b, Hide a)] -> [a]
forall a b. (a -> b) -> a -> b
$ [(b, Hide a)] -> [(b, Hide a)]
forall a. Ord a => [a] -> [a]
rise ([(b, Hide a)] -> [(b, Hide a)]) -> [(b, Hide a)] -> [(b, Hide a)]
forall a b. (a -> b) -> a -> b
$ (a -> (b, Hide a)) -> [a] -> [(b, Hide a)]
forall a b. (a -> b) -> [a] -> [b]
map ((a -> b) -> a -> (b, Hide a)
forall a b. (a -> b) -> a -> (b, Hide a)
hide a -> b
f) [a]
xs