{-# LANGUAGE ScopedTypeVariables #-}
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Data.Array.IO
import Data.Foldable
import Data.Binary
import Data.Int
import qualified Data.ByteString.Lazy as B
import Control.Monad
import System.IO
import System.Random
import System.Directory
import System.Environment

partition :: (Enum b, Num b, Ord e, Ix b, MArray a e m) => a b e -> b -> b -> b -> m b
partition arr left right pivotIndex = do
  pivotValue <- readArray arr pivotIndex
  swap arr pivotIndex right
  storeIndex <- foreachWith [left..right-1] left (\i storeIndex -> do
	val <- readArray arr i
	if (val <= pivotValue)
	  then do
	    swap arr i storeIndex
	    return (storeIndex + 1)
	  else do
	    return storeIndex )
  swap arr storeIndex right
  return storeIndex

qsort :: (Integral t, Ord e, Ix t, MArray a e m) => a t e -> t -> t -> m ()
qsort arr left right = when (right > left) $ do
  let pivotIndex = left + ((right-left) `div` 2)
  newPivot <- partition arr left right pivotIndex
  qsort arr left (newPivot - 1)
  qsort arr (newPivot + 1) right

swap :: (Ix i, MArray a e m) => a i e -> i -> i -> m ()
swap arr left right = do
    leftVal <- readArray arr left
    rightVal <- readArray arr right
    writeArray arr left rightVal
    writeArray arr right leftVal

foreachWith xs v f = foldlM (flip f) v xs

size :: N
size = 1000000

path :: String
path = "dataH.dat"

type N = Int32

generate :: N -> N -> UArray N N
generate size seed = listArray (fromIntegral 0, size) $ take ((fromIntegral size) + 1) . randomRs (-224, 228) . mkStdGen $ fromIntegral seed

main :: IO ()
main = do
  fileExist <- doesFileExist path
  if fileExist
	then do
	  (arrRead :: UArray N N) <- return . decode =<< B.readFile path
	  (arrMutable :: IOUArray N N) <- thaw arrRead
	  qsort arrMutable 0 size
	  (arrSorted :: UArray N N) <- freeze arrMutable
	  print $ arrSorted ! 1
	  print $ arrSorted ! size
	else do 
      (B.writeFile path . encode) $ generate size (42 :: N)
      print "Run me again!"