{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE BangPatterns #-}

module Main(main) where

import Criterion
import Criterion.Main

sort = mergeAll . sequences
sort' = mergeAll . sequences'

sequences :: [Int] -> [[Int]]
sequences (a:b:xs)
  | a `compare` b == GT = descending b [a]  xs
  | otherwise       = ascending  b (a:) xs
sequences xs = [xs]

descending a as (b:bs)
  | a `compare` b == GT = descending b (a:as) bs
descending a as bs  = (a:as): sequences bs

ascending a as (b:bs)
  | a `compare` b /= GT = ascending b (\ys -> as (a:ys)) bs
ascending a as bs   = as [a]: sequences bs

ascending' :: Int -> [Int] -> ([Int],[Int])
ascending' a (b:bs)
  | a `compare` b /= GT = let (as'  , bs') = ascending' b bs
                           in (b:as', bs')
ascending' a bs = ([],bs)

descending' a as (b:bs)
  | a `compare` b == GT = descending b (a:as) bs
descending' a as bs  = (a:as): sequences' bs

sequences' (a:b:xs)
  | a `compare` b == GT = descending' b [a] xs
  | otherwise           = let (as,bs) = ascending' b xs
                           in (a:b:as) : sequences bs       

mergeAll [x] = x
mergeAll xs  = mergeAll (mergePairs xs)

mergePairs (a:b:xs) = merge a b: mergePairs xs
mergePairs xs       = xs

merge as@(a:as') bs@(b:bs')
  | a `compare` b == GT = b:merge as  bs'
  | otherwise       = a:merge as' bs
merge [] bs         = bs
merge as []         = as

sawtooth :: (Int, Int, Int, Int) -> [Int]
sawtooth (max, pdelta, ndelta, length) 
     = take length (cycle ([0,pdelta..max-1] ++ [max, max + ndelta..1]))

oldSort = mergeAll . map (\x -> [x])

main = defaultMain 
  ( 
    bench "sawtooth"  (nf (length . sort  . sawtooth) (10^4,1,-1,10^6)) :
    bench "sawtooth'" (nf (length . sort' . sawtooth) (10^4,1,-1,10^6)) : 
    bench "sawtooth2"  (nf (length . sort  . sawtooth) (10^4,1,-1000,10^6)) :
    bench "sawtooth2'" (nf (length . sort' . sawtooth) (10^4,1,-1000,10^6)) :
    bench "asc"  (nf (length . sort .  enumFromTo 1) (10^6)) :  
    bench "asc'" (nf (length . sort' . enumFromTo 1) (10^6)) :
    bench "desc"  (nf (\n -> length . sort  $ [n, n-1..1]) (10^6)) :
    bench "desc'" (nf (\n -> length . sort' $ [n, n-1..1]) (10^6)) :
    [] )
 