-- | This module provides Rotationsort variants for sorting lists using the
--   Sortable type
--
-- | I was having some issues with the swaps for larger input lists, so for now
--   these functions are only implemented for lists of length 3 or less.
module Data.Tensort.Subalgorithms.Rotationsort
  ( rotationsort,
    rotationsortAmbi,
    rotationsortReverse,
    rotationsortReverseAmbi,
  )
where

import Data.Tensort.Utils.ComparisonFunctions
  ( greaterThanOrEqualBit,
    greaterThanOrEqualRecord,
  )
import Data.Tensort.Utils.Types (Sortable (..))

-- | Takes a Sortable and returns a sorted Sortable using a Rotationsort
--  algorithm
--
--  I was having some issues with the swaps for larger input lists, so for now
--  this function is only implemented for lists of length 3 or less.

-- | ==== __Examples__
-- >>> rotationsort (SortBit [1,3,2])
-- SortBit [1,2,3]
--
-- >>> rotationsort (SortRec [(3, 1), (1, 3), (2, 2)])
-- SortRec [(3,1),(2,2),(1,3)]
rotationsort :: Sortable -> Sortable
rotationsort :: Sortable -> Sortable
rotationsort (SortBit [Int]
bits) =
  let result :: [Int]
result =
        (Int -> Int -> Bool) -> [Int] -> Int -> Bool -> Bool -> [Int]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable Int -> Int -> Bool
greaterThanOrEqualBit [Int]
bits Int
0 Bool
False Bool
False
   in [Int] -> Sortable
SortBit [Int]
result
rotationsort (SortRec [Record]
recs) =
  let result :: [Record]
result =
        (Record -> Record -> Bool)
-> [Record] -> Int -> Bool -> Bool -> [Record]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable Record -> Record -> Bool
greaterThanOrEqualRecord [Record]
recs Int
0 Bool
False Bool
False
   in [Record] -> Sortable
SortRec [Record]
result

-- | Takes a Sortable and returns a sorted Sortable using an Ambidextrous
--   Rotationsort algorithm
--
--  I was having some issues with the swaps for larger input lists, so for now
--  this function is only implemented for lists of length 3 or less.

-- | ==== __Examples__
-- >>> rotationsortAmbi (SortBit [1,3,2])
-- SortBit [1,2,3]
--
-- >>> rotationsortAmbi (SortRec [(3, 1), (1, 3), (2, 2)])
-- SortRec [(3,1),(2,2),(1,3)]
rotationsortAmbi :: Sortable -> Sortable
rotationsortAmbi :: Sortable -> Sortable
rotationsortAmbi (SortBit [Int]
bits) =
  let result :: [Int]
result =
        (Int -> Int -> Bool) -> [Int] -> Int -> Bool -> Bool -> [Int]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable Int -> Int -> Bool
greaterThanOrEqualBit [Int]
bits Int
0 Bool
True Bool
False
   in [Int] -> Sortable
SortBit [Int]
result
rotationsortAmbi (SortRec [Record]
recs) =
  let result :: [Record]
result =
        (Record -> Record -> Bool)
-> [Record] -> Int -> Bool -> Bool -> [Record]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable Record -> Record -> Bool
greaterThanOrEqualRecord [Record]
recs Int
0 Bool
True Bool
False
   in [Record] -> Sortable
SortRec [Record]
result

-- | Takes a Sortable and returns a sorted Sortable using a Reverse
--   Rotationsort algorithm
--
--   I was having some issues with the swaps for larger input lists, so for now
--   this function is only implemented for lists of length 3 or less.

-- | ==== __Examples__
-- >>> rotationsortReverse (SortBit [1,3,2])
-- SortBit [1,2,3]
--
-- >>> rotationsortReverse (SortRec [(3, 1), (1, 3), (2, 2)])
-- SortRec [(3,1),(2,2),(1,3)]
rotationsortReverse :: Sortable -> Sortable
rotationsortReverse :: Sortable -> Sortable
rotationsortReverse (SortBit [Int]
bits) =
  let result :: [Int]
result =
        (Int -> Int -> Bool) -> [Int] -> Int -> Bool -> Bool -> [Int]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
          Int -> Int -> Bool
greaterThanOrEqualBit
          [Int]
bits
          ([Int] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
bits Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
          Bool
False
          Bool
True
   in [Int] -> Sortable
SortBit [Int]
result
rotationsortReverse (SortRec [Record]
recs) =
  let result :: [Record]
result =
        (Record -> Record -> Bool)
-> [Record] -> Int -> Bool -> Bool -> [Record]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
          Record -> Record -> Bool
greaterThanOrEqualRecord
          [Record]
recs
          ([Record] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Record]
recs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
          Bool
False
          Bool
True
   in [Record] -> Sortable
SortRec [Record]
result

-- | Takes a Sortable and returns a sorted Sortable using an Ambidextrous
--   Reverse Rotationsort algorithm
--
--   I was having some issues with the swaps for larger input lists, so for now
--   this function is only implemented for lists of length 3 or less.

-- | ==== __Examples__
-- >>> rotationsortReverseAmbi (SortBit [1,3,2])
-- SortBit [1,2,3]
--
-- >>> rotationsortReverseAmbi (SortRec [(3, 1), (1, 3), (2, 2)])
-- SortRec [(3,1),(2,2),(1,3)]
rotationsortReverseAmbi :: Sortable -> Sortable
rotationsortReverseAmbi :: Sortable -> Sortable
rotationsortReverseAmbi (SortBit [Int]
bits) =
  let result :: [Int]
result =
        (Int -> Int -> Bool) -> [Int] -> Int -> Bool -> Bool -> [Int]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
          Int -> Int -> Bool
greaterThanOrEqualBit
          [Int]
bits
          ([Int] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
bits Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
          Bool
True
          Bool
True
   in [Int] -> Sortable
SortBit [Int]
result
rotationsortReverseAmbi (SortRec [Record]
recs) =
  let result :: [Record]
result =
        (Record -> Record -> Bool)
-> [Record] -> Int -> Bool -> Bool -> [Record]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
          Record -> Record -> Bool
greaterThanOrEqualRecord
          [Record]
recs
          ([Record] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Record]
recs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
          Bool
True
          Bool
True
   in [Record] -> Sortable
SortRec [Record]
result

rotationsortIterable ::
  (Ord a) =>
  (a -> a -> Bool) ->
  [a] ->
  Int ->
  Bool ->
  Bool ->
  [a]
rotationsortIterable :: forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isAmbi Bool
isReverse
  | [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
3 =
      [Char] -> [a]
forall a. HasCallStack => [Char] -> a
error
        [Char]
"From rotationsortIterable: algorithm not yet implemented for lists of length greater than 3"
  | Int
currentIndex Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
currentIndex Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs =
      [a]
xs
  | [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2 = [a]
xs
  | [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
2 =
      (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotatationsortPair a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isAmbi Bool
isReverse
  | Int
currentIndex Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Bool -> Int
firstIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse =
      (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortHead a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isAmbi Bool
isReverse
  | Int
currentIndex Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Bool -> Int
lastIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse =
      (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortLast a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isAmbi Bool
isReverse
  | Bool
otherwise =
      (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortMiddle a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isAmbi Bool
isReverse

rotatationsortPair ::
  (Ord a) =>
  (a -> a -> Bool) ->
  [a] ->
  Int ->
  Bool ->
  Bool ->
  [a]
rotatationsortPair :: forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotatationsortPair a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isAmbi Bool
isReverse =
  let x :: a
x = [a] -> a
forall a. HasCallStack => [a] -> a
head [a]
xs
      y :: a
y = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int
1
      secondElemGreater :: Bool
secondElemGreater = a -> a -> Bool
greaterThanOrEqual a
y a
x
      swappedXs :: [a]
swappedXs = a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a
x]
   in Bool -> [a] -> [a]
switch Bool
secondElemGreater [a]
swappedXs
  where
    switch :: Bool -> [a] -> [a]
switch Bool
secondElemGreater [a]
swappedXs
      | Bool -> Bool
not Bool
secondElemGreater =
          (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
            a -> a -> Bool
greaterThanOrEqual
            [a]
swappedXs
            (Int -> Bool -> Int
firstIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse)
            Bool
isAmbi
            Bool
isReverse
      | Bool
otherwise =
          (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
            a -> a -> Bool
greaterThanOrEqual
            [a]
xs
            (Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse)
            Bool
isAmbi
            Bool
isReverse

rotationsortHead ::
  (Ord a) =>
  (a -> a -> Bool) ->
  [a] ->
  Int ->
  Bool ->
  Bool ->
  [a]
rotationsortHead :: forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortHead a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isAmbi Bool
isReverse =
  let w :: a
w = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
lastIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse
      x :: a
x = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int
currentIndex
      y :: a
y = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse
      rotateToFirst :: [a]
rotateToFirst =
        if Bool
isReverse then [a
y] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
w] else [a
w] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
y]
      rotateBackward :: [a]
rotateBackward =
        if Bool
isReverse then [a
w] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
y] else [a
y] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
w]
   in [a] -> [a] -> [a]
switch
        [a]
rotateToFirst
        [a]
rotateBackward
  where
    switch :: [a] -> [a] -> [a]
switch
      [a]
rotateToFirst
      [a]
rotateBackward
        | Bool -> Bool
not ((a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
lastElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse) =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
rotateToFirst
              (Int -> Bool -> Int
firstIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse
        | Bool -> Bool
not ((a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
nextElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse) =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
rotateBackward
              (Int -> Bool -> Int
firstIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse
        | Bool
otherwise =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
xs
              (Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse

rotationsortMiddle ::
  (Ord a) =>
  (a -> a -> Bool) ->
  [a] ->
  Int ->
  Bool ->
  Bool ->
  [a]
rotationsortMiddle :: forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortMiddle a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isAmbi Bool
isReverse =
  let w :: a
w = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
prevIndex Int
currentIndex Bool
isReverse
      x :: a
x = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int
currentIndex
      y :: a
y = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse
      rotateBackward :: [a]
rotateBackward =
        if Bool
isReverse then [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
y] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
w] else [a
y] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
w] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x]
      rotateForward :: [a]
rotateForward =
        if Bool
isReverse then [a
y] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
w] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] else [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
y] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
w]
   in [a] -> [a] -> [a]
switch
        [a]
rotateBackward
        [a]
rotateForward
  where
    switch :: [a] -> [a] -> [a]
switch
      [a]
rotateBackward
      [a]
rotateForward
        | Bool -> Bool
not ((a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
nextElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse) =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
rotateBackward
              (Int -> Bool -> Int
firstIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse
        | Bool -> Bool
not Bool
isAmbi =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
xs
              (Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse
        | Bool -> Bool
not ((a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
prevElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse) =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
rotateForward
              (Int -> Bool -> Int
prevIndex Int
currentIndex Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse
        | Bool
otherwise =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
xs
              (Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse

rotationsortLast ::
  (Ord a) =>
  (a -> a -> Bool) ->
  [a] ->
  Int ->
  Bool ->
  Bool ->
  [a]
rotationsortLast :: forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortLast a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isAmbi Bool
isReverse =
  let w :: a
w = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
prevIndex Int
currentIndex Bool
isReverse
      x :: a
x = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int
currentIndex
      y :: a
y = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
firstIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse
      rotateForward :: [a]
rotateForward =
        if Bool
isReverse then [a
w] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
y] else [a
y] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
w]
      rotateToLast :: [a]
rotateToLast =
        if Bool
isReverse then [a
y] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
w] else [a
w] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x] [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
y]
   in [a] -> [a] -> [a]
switch
        [a]
rotateForward
        [a]
rotateToLast
  where
    switch :: [a] -> [a] -> [a]
switch
      [a]
rotateForward
      [a]
rotateToLast
        | Bool -> Bool
not Bool
isAmbi =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
xs
              (Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse
        | Bool -> Bool
not ((a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
firstElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse) =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
rotateToLast
              (Int -> Bool -> Int
prevIndex Int
currentIndex Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse
        | Bool -> Bool
not ((a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
prevElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse) =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
rotateForward
              (Int -> Bool -> Int
prevIndex Int
currentIndex Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse
        | Bool
otherwise =
            (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
forall a.
Ord a =>
(a -> a -> Bool) -> [a] -> Int -> Bool -> Bool -> [a]
rotationsortIterable
              a -> a -> Bool
greaterThanOrEqual
              [a]
xs
              (Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse)
              Bool
isAmbi
              Bool
isReverse

nextIndex :: Int -> Bool -> Int
nextIndex :: Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse
  | Bool
isReverse = Int
currentIndex Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
  | Bool
otherwise = Int
currentIndex Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1

prevIndex :: Int -> Bool -> Int
prevIndex :: Int -> Bool -> Int
prevIndex Int
currentIndex Bool
isReverse
  | Bool
isReverse = Int
currentIndex Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
  | Bool
otherwise = Int
currentIndex Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1

lastIndex :: Int -> Bool -> Int
lastIndex :: Int -> Bool -> Int
lastIndex Int
listLength Bool
isReverse
  | Bool
isReverse = Int
0
  | Bool
otherwise = Int
listLength Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1

firstIndex :: Int -> Bool -> Int
firstIndex :: Int -> Bool -> Int
firstIndex Int
listLength Bool
isReverse
  | Bool
isReverse = Int
listLength Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
  | Bool
otherwise = Int
0

nextElemOrdered :: (Ord a) => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
nextElemOrdered :: forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
nextElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse =
  let x :: a
x = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int
currentIndex
      y :: a
y = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
nextIndex Int
currentIndex Bool
isReverse
   in if Bool
isReverse then a -> a -> Bool
greaterThanOrEqual a
x a
y else a -> a -> Bool
greaterThanOrEqual a
y a
x

prevElemOrdered :: (Ord a) => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
prevElemOrdered :: forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
prevElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse =
  let x :: a
x = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int
currentIndex
      w :: a
w = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
prevIndex Int
currentIndex Bool
isReverse
   in if Bool
isReverse then a -> a -> Bool
greaterThanOrEqual a
w a
x else a -> a -> Bool
greaterThanOrEqual a
x a
w

firstElemOrdered :: (Ord a) => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
firstElemOrdered :: forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
firstElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse =
  let x :: a
x = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int
currentIndex
      w :: a
w = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
firstIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse
   in if Bool
isReverse then a -> a -> Bool
greaterThanOrEqual a
w a
x else a -> a -> Bool
greaterThanOrEqual a
x a
w

lastElemOrdered :: (Ord a) => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
lastElemOrdered :: forall a. Ord a => (a -> a -> Bool) -> [a] -> Int -> Bool -> Bool
lastElemOrdered a -> a -> Bool
greaterThanOrEqual [a]
xs Int
currentIndex Bool
isReverse =
  let x :: a
x = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int
currentIndex
      y :: a
y = [a]
xs [a] -> Int -> a
forall a. HasCallStack => [a] -> Int -> a
!! Int -> Bool -> Int
lastIndex ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs) Bool
isReverse
   in if Bool
isReverse then a -> a -> Bool
greaterThanOrEqual a
x a
y else a -> a -> Bool
greaterThanOrEqual a
y a
x