module Data.Array.Vector.Algorithms.Optimal
( sort2ByIndex
, sort2ByOffset
, sort3ByIndex
, sort3ByOffset
, sort4ByIndex
, sort4ByOffset
, Comparison
) where
import Control.Monad.ST
import Data.Array.Vector
import Data.Array.Vector.Algorithms.Common
sort2ByOffset :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()
sort2ByOffset cmp a off = sort2ByIndex cmp a off (off + 1)
sort2ByIndex :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> ST s ()
sort2ByIndex cmp a i j = do
a0 <- readMU a i
a1 <- readMU a j
case cmp a0 a1 of
GT -> writeMU a i a1 >> writeMU a j a0
_ -> return ()
sort3ByOffset :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()
sort3ByOffset cmp a off = sort3ByIndex cmp a off (off + 1) (off + 2)
sort3ByIndex :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()
sort3ByIndex cmp a i j k = do
a0 <- readMU a i
a1 <- readMU a j
a2 <- readMU a k
case cmp a0 a1 of
GT -> case cmp a0 a2 of
GT -> case cmp a2 a1 of
GT -> do writeMU a i a1
writeMU a j a2
writeMU a k a0
_ -> do writeMU a i a2
writeMU a k a0
_ -> do writeMU a i a1
writeMU a j a0
_ -> case cmp a1 a2 of
GT -> case cmp a2 a0 of
GT -> do writeMU a j a2
writeMU a k a1
_ -> do writeMU a i a2
writeMU a k a1
writeMU a j a0
_ -> return ()
sort4ByOffset :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()
sort4ByOffset cmp a off = sort4ByIndex cmp a off (off + 1) (off + 2) (off + 3)
sort4ByIndex :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> Int -> ST s ()
sort4ByIndex cmp a i j k l = do
a0 <- readMU a i
a1 <- readMU a j
a2 <- readMU a k
a3 <- readMU a l
case cmp a0 a1 of
LT -> case cmp a1 a2 of
LT -> case cmp a1 a3 of
LT -> case cmp a2 a3 of
GT -> do writeMU a k a3
writeMU a l a2
_ -> return ()
_ -> do case cmp a0 a3 of
LT -> writeMU a j a3
_ -> do writeMU a j a0
writeMU a i a3
writeMU a l a2
writeMU a k a1
_ -> case cmp a0 a2 of
LT -> case cmp a2 a3 of
LT -> case cmp a1 a3 of
LT -> do writeMU a j a2
writeMU a k a1
_ -> do writeMU a l a1
writeMU a j a2
writeMU a k a3
_ -> case cmp a0 a3 of
LT -> do writeMU a l a1
writeMU a j a3
_ -> do writeMU a i a3
writeMU a l a1
writeMU a j a0
_ -> case cmp a0 a3 of
LT -> do writeMU a i a2
case cmp a1 a3 of
LT -> writeMU a k a1
_ -> do writeMU a k a3
writeMU a l a1
writeMU a j a0
_ -> case cmp a2 a3 of
LT -> do writeMU a i a2
writeMU a k a0
writeMU a j a3
writeMU a l a1
_ -> do writeMU a j a2
writeMU a k a0
writeMU a i a3
writeMU a l a1
_ -> case cmp a0 a2 of
LT -> case cmp a0 a3 of
LT -> do writeMU a i a1
writeMU a j a0
case cmp a2 a3 of
GT -> do writeMU a k a3
writeMU a l a2
_ -> return ()
_ -> do case cmp a1 a3 of
LT -> do writeMU a i a1
writeMU a j a3
_ -> writeMU a i a3
writeMU a l a2
writeMU a k a0
_ -> case cmp a1 a2 of
LT -> case cmp a2 a3 of
LT -> do writeMU a i a1
writeMU a j a2
case cmp a0 a3 of
LT -> writeMU a k a0
_ -> do writeMU a k a3
writeMU a l a0
_ -> do case cmp a1 a3 of
LT -> do writeMU a i a1
writeMU a j a3
_ -> writeMU a i a3
writeMU a l a0
_ -> case cmp a1 a3 of
LT -> do writeMU a i a2
case cmp a0 a3 of
LT -> writeMU a k a0
_ -> do writeMU a k a3
writeMU a l a0
_ -> case cmp a2 a3 of
LT -> do writeMU a i a2
writeMU a k a1
writeMU a j a3
writeMU a l a0
_ -> do writeMU a i a3
writeMU a l a0
writeMU a j a2
writeMU a k a1