-- | This module provides the bubblesort function for sorting lists using the
--   Sortable type
module Data.Tensort.Subalgorithms.Exchangesort (exchangesort) where

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

-- | Takes a Sortable and returns a sorted Sortable using an Exchangesort
--   algorithm

-- | ==== __Examples__
-- >>> exchangesort (SortBit [16, 23, 4, 8, 15, 42])
-- SortBit [4,8,15,16,23,42]
--
-- >>> exchangesort (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)]
exchangesort :: Sortable -> Sortable
exchangesort :: Sortable -> Sortable
exchangesort (SortBit [Bit]
bits) = [Bit] -> Sortable
SortBit ((Bit -> Bit -> Bool) -> [Bit] -> Bit -> Bit -> [Bit]
forall a. Ord a => (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
exchangesortIterable Bit -> Bit -> Bool
greaterThanBit [Bit]
bits Bit
0 ([Bit] -> Bit
forall a. [a] -> Bit
forall (t :: * -> *) a. Foldable t => t a -> Bit
length [Bit]
bits Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
- Bit
1))
exchangesort (SortRec [Record]
recs) = [Record] -> Sortable
SortRec ((Record -> Record -> Bool) -> [Record] -> Bit -> Bit -> [Record]
forall a. Ord a => (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
exchangesortIterable Record -> Record -> Bool
greaterThanRecord [Record]
recs Bit
0 ([Record] -> Bit
forall a. [a] -> Bit
forall (t :: * -> *) a. Foldable t => t a -> Bit
length [Record]
recs Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
- Bit
1))

exchangesortIterable :: (Ord a) => (a -> a -> Bool) -> [a] -> Int -> Int -> [a]
exchangesortIterable :: forall a. Ord a => (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
exchangesortIterable a -> a -> Bool
greaterThan [a]
xs Bit
i Bit
j
  | Bit
i Bit -> Bit -> Bool
forall a. Ord a => a -> a -> Bool
> [a] -> Bit
forall a. [a] -> Bit
forall (t :: * -> *) a. Foldable t => t a -> Bit
length [a]
xs Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
- Bit
1 =
      [a]
xs
  | Bit
j Bit -> Bit -> Bool
forall a. Ord a => a -> a -> Bool
< Bit
0 =
      (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
forall a. Ord a => (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
exchangesortIterable a -> a -> Bool
greaterThan [a]
xs (Bit
i Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
+ Bit
1) ([a] -> Bit
forall a. [a] -> Bit
forall (t :: * -> *) a. Foldable t => t a -> Bit
length [a]
xs Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
- Bit
1)
  | Bit
i Bit -> Bit -> Bool
forall a. Eq a => a -> a -> Bool
== Bit
j =
      (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
forall a. Ord a => (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
exchangesortIterable a -> a -> Bool
greaterThan [a]
xs Bit
i (Bit
j Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
- Bit
1)
  | Bool
otherwise =
      let mini :: Bit
mini = Bit -> Bit -> Bit
forall a. Ord a => a -> a -> a
min Bit
i Bit
j
          maxi :: Bit
maxi = Bit -> Bit -> Bit
forall a. Ord a => a -> a -> a
max Bit
i Bit
j
          left :: [a]
left = Bit -> [a] -> [a]
forall a. Bit -> [a] -> [a]
take Bit
mini [a]
xs
          middle :: [a]
middle = Bit -> [a] -> [a]
forall a. Bit -> [a] -> [a]
take (Bit
maxi Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
- Bit
mini Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
- Bit
1) (Bit -> [a] -> [a]
forall a. Bit -> [a] -> [a]
drop (Bit
mini Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
+ Bit
1) [a]
xs)
          right :: [a]
right = Bit -> [a] -> [a]
forall a. Bit -> [a] -> [a]
drop (Bit
maxi Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
+ Bit
1) [a]
xs
          x :: a
x = [a]
xs [a] -> Bit -> a
forall a. HasCallStack => [a] -> Bit -> a
!! Bit
mini
          y :: a
y = [a]
xs [a] -> Bit -> a
forall a. HasCallStack => [a] -> Bit -> a
!! Bit
maxi
          leftElemGreater :: Bool
leftElemGreater = a -> a -> Bool
greaterThan a
x a
y
          swappedXs :: [a]
swappedXs = [a]
left [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
y] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
middle [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
right
       in if Bool
leftElemGreater
            then (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
forall a. Ord a => (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
exchangesortIterable a -> a -> Bool
greaterThan [a]
swappedXs Bit
i (Bit
j Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
- Bit
1)
            else (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
forall a. Ord a => (a -> a -> Bool) -> [a] -> Bit -> Bit -> [a]
exchangesortIterable a -> a -> Bool
greaterThan [a]
xs Bit
i (Bit
j Bit -> Bit -> Bit
forall a. Num a => a -> a -> a
- Bit
1)