-- | This module provides the quicksort function for sorting lists using the
--   Sortable type
module Data.Tensort.OtherSorts.Quicksort (quicksort) where

import Data.Tensort.Utils.ComparisonFunctions (greaterThanBit, greaterThanRecord)
import Data.Tensort.Utils.Types (Bit, Record, Sortable (..))

-- | Takes a Sortable and returns a sorted Sortable using a Quicksort algorithm

-- | ==== __Examples__
--  >>> quicksort (SortBit [16, 23, 4, 8, 15, 42])
--  SortBit [4,8,15,16,23,42]
--
--  >>> quicksort (SortRec [(1, 16), (5, 23), (2, 4) ,(3, 8), (0, 15) , (4, 42)])
--  SortRec [(2,4),(3,8),(0,15),(1,16),(5,23),(4,42)]
quicksort :: Sortable -> Sortable
quicksort :: Sortable -> Sortable
quicksort (SortBit []) = [Bit] -> Sortable
SortBit []
quicksort (SortBit [Bit
x]) = [Bit] -> Sortable
SortBit [Bit
x]
quicksort (SortBit [Bit]
xs) = [Bit] -> Sortable
SortBit ([Bit] -> [Bit]
quicksortBits [Bit]
xs)
quicksort (SortRec []) = [Record] -> Sortable
SortRec []
quicksort (SortRec [Record
x]) = [Record] -> Sortable
SortRec [Record
x]
quicksort (SortRec [Record]
xs) = [Record] -> Sortable
SortRec ([Record] -> [Record]
quicksortRecs [Record]
xs)

quicksortBits :: [Bit] -> [Bit]
quicksortBits :: [Bit] -> [Bit]
quicksortBits [] = []
quicksortBits [Bit
x] = [Bit
x]
quicksortBits [Bit]
xs =
  let ([Bit]
lower, Bit
pivot, [Bit]
upper) = [Bit] -> ([Bit], Bit, [Bit])
getPartitionsBits [Bit]
xs
   in [Bit] -> [Bit]
quicksortBits [Bit]
lower [Bit] -> [Bit] -> [Bit]
forall a. [a] -> [a] -> [a]
++ [Bit
pivot] [Bit] -> [Bit] -> [Bit]
forall a. [a] -> [a] -> [a]
++ [Bit] -> [Bit]
quicksortBits [Bit]
upper

getPartitionsBits :: [Bit] -> ([Bit], Bit, [Bit])
getPartitionsBits :: [Bit] -> ([Bit], Bit, [Bit])
getPartitionsBits [] = [Char] -> ([Bit], Bit, [Bit])
forall a. HasCallStack => [Char] -> a
error [Char]
"From getPartitionsBits: empty input list"
getPartitionsBits [Bit
x] = ([], Bit
x, [])
getPartitionsBits (Bit
x : [Bit]
xs) = (Bit -> ([Bit], Bit, [Bit]) -> ([Bit], Bit, [Bit]))
-> ([Bit], Bit, [Bit]) -> [Bit] -> ([Bit], Bit, [Bit])
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Bit -> ([Bit], Bit, [Bit]) -> ([Bit], Bit, [Bit])
acc ([], Bit
x, []) [Bit]
xs
  where
    acc :: Bit -> ([Bit], Bit, [Bit]) -> ([Bit], Bit, [Bit])
    acc :: Bit -> ([Bit], Bit, [Bit]) -> ([Bit], Bit, [Bit])
acc Bit
y ([Bit]
lower, Bit
pivot, [Bit]
upper)
      | Bit -> Bit -> Bool
greaterThanBit Bit
y Bit
pivot = ([Bit]
lower, Bit
pivot, Bit
y Bit -> [Bit] -> [Bit]
forall a. a -> [a] -> [a]
: [Bit]
upper)
      | Bool
otherwise = (Bit
y Bit -> [Bit] -> [Bit]
forall a. a -> [a] -> [a]
: [Bit]
lower, Bit
pivot, [Bit]
upper)

quicksortRecs :: [Record] -> [Record]
quicksortRecs :: [Record] -> [Record]
quicksortRecs [] = []
quicksortRecs [Record
x] = [Record
x]
quicksortRecs [Record]
xs =
  let ([Record]
lower, Record
pivot, [Record]
upper) = [Record] -> ([Record], Record, [Record])
getPartitionsRecs [Record]
xs
   in [Record] -> [Record]
quicksortRecs [Record]
lower [Record] -> [Record] -> [Record]
forall a. [a] -> [a] -> [a]
++ [Record
pivot] [Record] -> [Record] -> [Record]
forall a. [a] -> [a] -> [a]
++ [Record] -> [Record]
quicksortRecs [Record]
upper

getPartitionsRecs :: [Record] -> ([Record], Record, [Record])
getPartitionsRecs :: [Record] -> ([Record], Record, [Record])
getPartitionsRecs [] = [Char] -> ([Record], Record, [Record])
forall a. HasCallStack => [Char] -> a
error [Char]
"From getPartitionsRecs: empty input list"
getPartitionsRecs [Record
x] = ([], Record
x, [])
getPartitionsRecs (Record
x : [Record]
xs) = (Record
 -> ([Record], Record, [Record]) -> ([Record], Record, [Record]))
-> ([Record], Record, [Record])
-> [Record]
-> ([Record], Record, [Record])
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Record
-> ([Record], Record, [Record]) -> ([Record], Record, [Record])
acc ([], Record
x, []) [Record]
xs
  where
    acc :: Record -> ([Record], Record, [Record]) -> ([Record], Record, [Record])
    acc :: Record
-> ([Record], Record, [Record]) -> ([Record], Record, [Record])
acc Record
y ([Record]
lower, Record
pivot, [Record]
upper)
      | Record -> Record -> Bool
greaterThanRecord Record
y Record
pivot = ([Record]
lower, Record
pivot, Record
y Record -> [Record] -> [Record]
forall a. a -> [a] -> [a]
: [Record]
upper)
      | Bool
otherwise = (Record
y Record -> [Record] -> [Record]
forall a. a -> [a] -> [a]
: [Record]
lower, Record
pivot, [Record]
upper)