sort.hs

{-# Language MultiParamTypeClasses, FunctionalDependencies #-}

module Sort

  ( windowSort
  , Windowed(..)
  )

where

import Data.List
import Data.Ord

-- TODO: Consider using associated types instead of functional dependencies: http://www.haskell.org/haskellwiki/GHC/Type_families

class (Ord t, Num t) => Windowed a t | a -> t where
  windowTag :: a -> t
  dataTag   :: a -> t

type SB a = (a -> a -> Ordering) -> [a] -> [a]

insertionSortBy :: SB a
insertionSortBy cmp = foldr (insertBy cmp) []

windowSort :: (Windowed a t) => t -> [a] -> [a]
windowSort = ws sortBy

ws :: (Windowed a t) => SB a -> t -> [a] -> [a]
ws _ _ [] = []
ws sorter delta l@(x:xs)
  | abs (windowTag x - dataTag x) > delta = ws sorter delta xs -- Drop invalid items
  | otherwise = start ++ ws insertionSortBy delta (finish ++ end)
    where
      dataLimit = (<= dx) . dataTag
      start     = takeWhile dataLimit sorted
      finish    = dropWhile dataLimit sorted

      sorted    = sorter (comparing dataTag) beginning

      windowLimit = (<= window) . windowTag
      beginning   = takeWhile windowLimit l
      end         = dropWhile windowLimit l

      dx        = dataTag x
      wx        = windowTag x
      window    = delta + wx