{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE FlexibleContexts #-}
-- |
-- Module      : Data.Massiv.Array.Ops.Sort
-- Copyright   : (c) Alexey Kuleshevich 2018-2021
-- License     : BSD3
-- Maintainer  : Alexey Kuleshevich <lehins@yandex.ru>
-- Stability   : experimental
-- Portability : non-portable
--
module Data.Massiv.Array.Ops.Sort
  ( tally
  , quicksort
  , quicksortBy
  , quicksortByM
  , quicksortM_
  , quicksortByM_
  , unsafeUnstablePartitionRegionM
  ) where

import Control.Monad.IO.Unlift
import Control.Monad (when)
import Control.Scheduler
import Data.Massiv.Array.Delayed.Stream
import Data.Massiv.Array.Mutable
import Data.Massiv.Array.Ops.Transform
import Data.Massiv.Core.Common
import Data.Massiv.Vector (scatMaybes, sunfoldrN)
import System.IO.Unsafe

-- | Count number of occurrences of each element in the array. Results will be
-- sorted in ascending order of the element.
--
-- ==== __Example__
--
-- >>> import Data.Massiv.Array as A
-- >>> xs = fromList Seq [2, 4, 3, 2, 4, 5, 2, 1] :: Array P Ix1 Int
-- >>> xs
-- Array P Seq (Sz1 8)
--   [ 2, 4, 3, 2, 4, 5, 2, 1 ]
-- >>> tally xs
-- Array DS Seq (Sz1 5)
--   [ (1,1), (2,3), (3,1), (4,2), (5,1) ]
--
-- @since 0.4.4
tally :: (Mutable r Ix1 e, Resize r ix, Load r ix e, Ord e) => Array r ix e -> Vector DS (e, Int)
tally :: Array r ix e -> Vector DS (e, Int)
tally Array r ix e
arr
  | Array r ix e -> Bool
forall r ix e. Load r ix e => Array r ix e -> Bool
isEmpty Array r ix e
arr = Comp -> Vector DS (e, Int) -> Vector DS (e, Int)
forall r ix e.
Construct r ix e =>
Comp -> Array r ix e -> Array r ix e
setComp (Array r ix e -> Comp
forall r ix e. Load r ix e => Array r ix e -> Comp
getComp Array r ix e
arr) Vector DS (e, Int)
forall r ix e. Construct r ix e => Array r ix e
empty
  | Bool
otherwise = Array DS Int (Maybe (e, Int)) -> Vector DS (e, Int)
forall r ix a.
Stream r ix (Maybe a) =>
Array r ix (Maybe a) -> Vector DS a
scatMaybes (Array DS Int (Maybe (e, Int)) -> Vector DS (e, Int))
-> Array DS Int (Maybe (e, Int)) -> Vector DS (e, Int)
forall a b. (a -> b) -> a -> b
$ Sz1
-> ((Int, Int, e) -> Maybe (Maybe (e, Int), (Int, Int, e)))
-> (Int, Int, e)
-> Array DS Int (Maybe (e, Int))
forall s e. Sz1 -> (s -> Maybe (e, s)) -> s -> Vector DS e
sunfoldrN (Sz1
sz Sz1 -> Sz1 -> Sz1
forall a. Num a => a -> a -> a
+ Sz1
1) (Int, Int, e) -> Maybe (Maybe (e, Int), (Int, Int, e))
forall b. Num b => (Int, b, e) -> Maybe (Maybe (e, b), (Int, b, e))
count (Int
0, Int
0, Array r Int e
sorted Array r Int e -> Int -> e
forall r ix e. Manifest r ix e => Array r ix e -> ix -> e
! Int
0)
  where
    sz :: Sz1
sz@(Sz Int
k) = Array r Int e -> Sz1
forall r ix e. Load r ix e => Array r ix e -> Sz ix
size Array r Int e
sorted
    count :: (Int, b, e) -> Maybe (Maybe (e, b), (Int, b, e))
count (!Int
i, !b
n, !e
prev)
      | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
k =
        let !e' :: e
e' = Array r Int e -> Int -> e
forall r ix e. Source r ix e => Array r ix e -> Int -> e
unsafeLinearIndex Array r Int e
sorted Int
i
         in if e
prev e -> e -> Bool
forall a. Eq a => a -> a -> Bool
== e
e'
              then (Maybe (e, b), (Int, b, e)) -> Maybe (Maybe (e, b), (Int, b, e))
forall a. a -> Maybe a
Just (Maybe (e, b)
forall a. Maybe a
Nothing, (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, b
n b -> b -> b
forall a. Num a => a -> a -> a
+ b
1, e
prev))
              else (Maybe (e, b), (Int, b, e)) -> Maybe (Maybe (e, b), (Int, b, e))
forall a. a -> Maybe a
Just ((e, b) -> Maybe (e, b)
forall a. a -> Maybe a
Just (e
prev, b
n), (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, b
1, e
e'))
      | Bool
otherwise = (Maybe (e, b), (Int, b, e)) -> Maybe (Maybe (e, b), (Int, b, e))
forall a. a -> Maybe a
Just ((e, b) -> Maybe (e, b)
forall a. a -> Maybe a
Just (e
prev, b
n), (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, b
n, e
prev))
    {-# INLINE count #-}
    sorted :: Array r Int e
sorted = Array r Int e -> Array r Int e
forall r e.
(Mutable r Int e, Ord e) =>
Array r Int e -> Array r Int e
quicksort (Array r Int e -> Array r Int e) -> Array r Int e -> Array r Int e
forall a b. (a -> b) -> a -> b
$ Array r ix e -> Array r Int e
forall r ix e.
(Load r ix e, Resize r ix) =>
Array r ix e -> Array r Int e
flatten Array r ix e
arr
{-# INLINE tally #-}


unsafeUnstablePartitionRegionM' ::
     forall r e m. (Mutable r Ix1 e, PrimMonad m)
  => MArray (PrimState m) r Ix1 e
  -> (e -> m Bool)
  -> Ix1 -- ^ Start index of the region
  -> Ix1 -- ^ End index of the region
  -> m Ix1
unsafeUnstablePartitionRegionM' :: MArray (PrimState m) r Int e
-> (e -> m Bool) -> Int -> Int -> m Int
unsafeUnstablePartitionRegionM' MArray (PrimState m) r Int e
marr e -> m Bool
f Int
start Int
end = Int -> Int -> m Int
fromLeft Int
start (Int
end Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  where
    fromLeft :: Int -> Int -> m Int
fromLeft Int
i Int
j
      | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j = Int -> m Int
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
i
      | Bool
otherwise = do
        Bool
e <- e -> m Bool
f (e -> m Bool) -> m e -> m Bool
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MArray (PrimState m) r Int e -> Int -> m e
forall r ix e (m :: * -> *).
(Mutable r ix e, PrimMonad m) =>
MArray (PrimState m) r ix e -> Int -> m e
unsafeLinearRead MArray (PrimState m) r Int e
marr Int
i
        if Bool
e
          then Int -> Int -> m Int
fromLeft (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int
j
          else Int -> Int -> m Int
fromRight Int
i (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
    fromRight :: Int -> Int -> m Int
fromRight Int
i Int
j
      | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j = Int -> m Int
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
i
      | Bool
otherwise = do
        e
x <- MArray (PrimState m) r Int e -> Int -> m e
forall r ix e (m :: * -> *).
(Mutable r ix e, PrimMonad m) =>
MArray (PrimState m) r ix e -> Int -> m e
unsafeLinearRead MArray (PrimState m) r Int e
marr Int
j
        Bool
e <- e -> m Bool
f e
x
        if Bool
e
          then do
            MArray (PrimState m) r Int e -> Int -> e -> m ()
forall r ix e (m :: * -> *).
(Mutable r ix e, PrimMonad m) =>
MArray (PrimState m) r ix e -> Int -> e -> m ()
unsafeLinearWrite MArray (PrimState m) r Int e
marr Int
j (e -> m ()) -> m e -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MArray (PrimState m) r Int e -> Int -> m e
forall r ix e (m :: * -> *).
(Mutable r ix e, PrimMonad m) =>
MArray (PrimState m) r ix e -> Int -> m e
unsafeLinearRead MArray (PrimState m) r Int e
marr Int
i
            MArray (PrimState m) r Int e -> Int -> e -> m ()
forall r ix e (m :: * -> *).
(Mutable r ix e, PrimMonad m) =>
MArray (PrimState m) r ix e -> Int -> e -> m ()
unsafeLinearWrite MArray (PrimState m) r Int e
marr Int
i e
x
            Int -> Int -> m Int
fromLeft (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int
j
          else Int -> Int -> m Int
fromRight Int
i (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
{-# INLINE unsafeUnstablePartitionRegionM' #-}


-- TODO: Replace `unsafeUnstablePartitionRegionM` with `unsafeUnstablePartitionRegionM'`
-- | Partition a segment of a vector. Starting and ending indices are unchecked.
--
-- @since 0.3.2
unsafeUnstablePartitionRegionM ::
     forall r e m. (Mutable r Ix1 e, PrimMonad m)
  => MVector (PrimState m) r e
  -> (e -> Bool)
  -> Ix1 -- ^ Start index of the region
  -> Ix1 -- ^ End index of the region
  -> m Ix1
unsafeUnstablePartitionRegionM :: MVector (PrimState m) r e -> (e -> Bool) -> Int -> Int -> m Int
unsafeUnstablePartitionRegionM MVector (PrimState m) r e
marr e -> Bool
f = MVector (PrimState m) r e -> (e -> m Bool) -> Int -> Int -> m Int
forall r e (m :: * -> *).
(Mutable r Int e, PrimMonad m) =>
MArray (PrimState m) r Int e
-> (e -> m Bool) -> Int -> Int -> m Int
unsafeUnstablePartitionRegionM' MVector (PrimState m) r e
marr (Bool -> m Bool
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> m Bool) -> (e -> Bool) -> e -> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. e -> Bool
f)
{-# INLINE unsafeUnstablePartitionRegionM #-}


-- | This is an implementation of [Quicksort](https://en.wikipedia.org/wiki/Quicksort), which is an
-- efficient, but unstable sort that uses Median-of-three for pivot choosing, as such it performs
-- very well not only for random values, but also for common edge cases like already sorted,
-- reversed sorted and arrays with many duplicate elements. It will also respect the computation
-- strategy and will result in a nice speed up for systems with multiple CPUs.
--
-- @since 0.3.2
quicksort ::
     (Mutable r Ix1 e, Ord e) => Array r Ix1 e -> Array r Ix1 e
quicksort :: Array r Int e -> Array r Int e
quicksort Array r Int e
arr = IO (Array r Int e) -> Array r Int e
forall a. IO a -> a
unsafePerformIO (IO (Array r Int e) -> Array r Int e)
-> IO (Array r Int e) -> Array r Int e
forall a b. (a -> b) -> a -> b
$ Array r Int e
-> (Scheduler IO () -> MArray RealWorld r Int e -> IO ())
-> IO (Array r Int e)
forall r ix e (m :: * -> *) a.
(Mutable r ix e, MonadUnliftIO m) =>
Array r ix e
-> (Scheduler m () -> MArray RealWorld r ix e -> m a)
-> m (Array r ix e)
withMArray_ Array r Int e
arr Scheduler IO () -> MArray RealWorld r Int e -> IO ()
forall e r (m :: * -> *).
(Ord e, Mutable r Int e, PrimMonad m) =>
Scheduler m () -> MVector (PrimState m) r e -> m ()
quicksortM_
{-# INLINE quicksort #-}


-- | Same as `quicksortBy`, but instead of `Ord` constraint expects a custom `Ordering`.
--
-- @since 0.6.1
quicksortByM ::
     (Mutable r Ix1 e, MonadUnliftIO m) => (e -> e -> m Ordering) -> Vector r e -> m (Vector r e)
quicksortByM :: (e -> e -> m Ordering) -> Vector r e -> m (Vector r e)
quicksortByM e -> e -> m Ordering
f Vector r e
arr = ((forall a. m a -> IO a) -> IO (Vector r e)) -> m (Vector r e)
forall (m :: * -> *) b.
MonadUnliftIO m =>
((forall a. m a -> IO a) -> IO b) -> m b
withRunInIO (((forall a. m a -> IO a) -> IO (Vector r e)) -> m (Vector r e))
-> ((forall a. m a -> IO a) -> IO (Vector r e)) -> m (Vector r e)
forall a b. (a -> b) -> a -> b
$ \forall a. m a -> IO a
run -> Vector r e
-> (Scheduler IO () -> MArray RealWorld r Int e -> IO ())
-> IO (Vector r e)
forall r ix e (m :: * -> *) a.
(Mutable r ix e, MonadUnliftIO m) =>
Array r ix e
-> (Scheduler m () -> MArray RealWorld r ix e -> m a)
-> m (Array r ix e)
withMArray_ Vector r e
arr ((e -> e -> IO Ordering)
-> Scheduler IO () -> MVector (PrimState IO) r e -> IO ()
forall r e (m :: * -> *).
(Mutable r Int e, PrimMonad m) =>
(e -> e -> m Ordering)
-> Scheduler m () -> MVector (PrimState m) r e -> m ()
quicksortByM_ (\e
x e
y -> m Ordering -> IO Ordering
forall a. m a -> IO a
run (e -> e -> m Ordering
f e
x e
y)))
{-# INLINE quicksortByM #-}

-- | Same as `quicksortBy`, but instead of `Ord` constraint expects a custom `Ordering`.
--
-- @since 0.6.1
quicksortBy ::
     (Mutable r Ix1 e) => (e -> e -> Ordering) -> Vector r e -> Vector r e
quicksortBy :: (e -> e -> Ordering) -> Vector r e -> Vector r e
quicksortBy e -> e -> Ordering
f Vector r e
arr =
  IO (Vector r e) -> Vector r e
forall a. IO a -> a
unsafePerformIO (IO (Vector r e) -> Vector r e) -> IO (Vector r e) -> Vector r e
forall a b. (a -> b) -> a -> b
$ Vector r e
-> (Scheduler IO () -> MArray RealWorld r Int e -> IO ())
-> IO (Vector r e)
forall r ix e (m :: * -> *) a.
(Mutable r ix e, MonadUnliftIO m) =>
Array r ix e
-> (Scheduler m () -> MArray RealWorld r ix e -> m a)
-> m (Array r ix e)
withMArray_ Vector r e
arr ((e -> e -> IO Ordering)
-> Scheduler IO () -> MVector (PrimState IO) r e -> IO ()
forall r e (m :: * -> *).
(Mutable r Int e, PrimMonad m) =>
(e -> e -> m Ordering)
-> Scheduler m () -> MVector (PrimState m) r e -> m ()
quicksortByM_ (\e
x e
y -> Ordering -> IO Ordering
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Ordering -> IO Ordering) -> Ordering -> IO Ordering
forall a b. (a -> b) -> a -> b
$ e -> e -> Ordering
f e
x e
y))
{-# INLINE quicksortBy #-}

-- | Mutable version of `quicksort`
--
-- @since 0.3.2
quicksortM_ ::
     (Ord e, Mutable r Ix1 e, PrimMonad m)
  => Scheduler m ()
  -> MVector (PrimState m) r e
  -> m ()
quicksortM_ :: Scheduler m () -> MVector (PrimState m) r e -> m ()
quicksortM_ = (e -> e -> m Bool)
-> (e -> e -> m Bool)
-> Scheduler m ()
-> MVector (PrimState m) r e
-> m ()
forall r e (m :: * -> *).
(Mutable r Int e, PrimMonad m) =>
(e -> e -> m Bool)
-> (e -> e -> m Bool)
-> Scheduler m ()
-> MVector (PrimState m) r e
-> m ()
quicksortInternalM_ (\e
e1 e
e2 -> Bool -> m Bool
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> m Bool) -> Bool -> m Bool
forall a b. (a -> b) -> a -> b
$ e
e1 e -> e -> Bool
forall a. Ord a => a -> a -> Bool
< e
e2) (\e
e1 e
e2 -> Bool -> m Bool
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> m Bool) -> Bool -> m Bool
forall a b. (a -> b) -> a -> b
$ e
e1 e -> e -> Bool
forall a. Eq a => a -> a -> Bool
== e
e2)
{-# INLINE quicksortM_ #-}


-- | Same as `quicksortM_`, but instead of `Ord` constraint expects a custom `Ordering`.
--
-- @since 0.6.1
quicksortByM_ ::
     (Mutable r Ix1 e, PrimMonad m)
  => (e -> e -> m Ordering)
  -> Scheduler m ()
  -> MVector (PrimState m) r e
  -> m ()
quicksortByM_ :: (e -> e -> m Ordering)
-> Scheduler m () -> MVector (PrimState m) r e -> m ()
quicksortByM_ e -> e -> m Ordering
compareM =
  (e -> e -> m Bool)
-> (e -> e -> m Bool)
-> Scheduler m ()
-> MVector (PrimState m) r e
-> m ()
forall r e (m :: * -> *).
(Mutable r Int e, PrimMonad m) =>
(e -> e -> m Bool)
-> (e -> e -> m Bool)
-> Scheduler m ()
-> MVector (PrimState m) r e
-> m ()
quicksortInternalM_ (\e
x e
y -> (Ordering
LT Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
==) (Ordering -> Bool) -> m Ordering -> m Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> e -> e -> m Ordering
compareM e
x e
y) (\e
x e
y -> (Ordering
EQ Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
==) (Ordering -> Bool) -> m Ordering -> m Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> e -> e -> m Ordering
compareM e
x e
y)
{-# INLINE quicksortByM_ #-}


quicksortInternalM_ ::
     (Mutable r Ix1 e, PrimMonad m)
  => (e -> e -> m Bool)
  -> (e -> e -> m Bool)
  -> Scheduler m ()
  -> MVector (PrimState m) r e
  -> m ()
quicksortInternalM_ :: (e -> e -> m Bool)
-> (e -> e -> m Bool)
-> Scheduler m ()
-> MVector (PrimState m) r e
-> m ()
quicksortInternalM_ e -> e -> m Bool
fLT e -> e -> m Bool
fEQ Scheduler m ()
scheduler MVector (PrimState m) r e
marr =
  Scheduler m () -> m () -> m ()
forall (m :: * -> *) a. Scheduler m a -> m a -> m ()
scheduleWork Scheduler m ()
scheduler (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Int -> m ()
forall t. (Ord t, Num t) => t -> Int -> Int -> m ()
qsort (Scheduler m () -> Int
forall (m :: * -> *) a. Scheduler m a -> Int
numWorkers Scheduler m ()
scheduler) Int
0 (Sz1 -> Int
forall ix. Sz ix -> ix
unSz (MVector (PrimState m) r e -> Sz1
forall r ix e s. Mutable r ix e => MArray s r ix e -> Sz ix
msize MVector (PrimState m) r e
marr) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
  where
    ltSwap :: Int -> Int -> m e
ltSwap Int
i Int
j = do
      e
ei <- MVector (PrimState m) r e -> Int -> m e
forall r ix e (m :: * -> *).
(Mutable r ix e, PrimMonad m) =>
MArray (PrimState m) r ix e -> Int -> m e
unsafeLinearRead MVector (PrimState m) r e
marr Int
i
      e
ej <- MVector (PrimState m) r e -> Int -> m e
forall r ix e (m :: * -> *).
(Mutable r ix e, PrimMonad m) =>
MArray (PrimState m) r ix e -> Int -> m e
unsafeLinearRead MVector (PrimState m) r e
marr Int
j
      Bool
lt <- e -> e -> m Bool
fLT e
ei e
ej
      if Bool
lt
        then do
          MVector (PrimState m) r e -> Int -> e -> m ()
forall r ix e (m :: * -> *).
(Mutable r ix e, PrimMonad m) =>
MArray (PrimState m) r ix e -> Int -> e -> m ()
unsafeLinearWrite MVector (PrimState m) r e
marr Int
i e
ej
          MVector (PrimState m) r e -> Int -> e -> m ()
forall r ix e (m :: * -> *).
(Mutable r ix e, PrimMonad m) =>
MArray (PrimState m) r ix e -> Int -> e -> m ()
unsafeLinearWrite MVector (PrimState m) r e
marr Int
j e
ei
          e -> m e
forall (f :: * -> *) a. Applicative f => a -> f a
pure e
ei
        else e -> m e
forall (f :: * -> *) a. Applicative f => a -> f a
pure e
ej
    {-# INLINE ltSwap #-}
    getPivot :: Int -> Int -> m e
getPivot Int
lo Int
hi = do
      let !mid :: Int
mid = (Int
hi Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lo) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
      e
_ <- Int -> Int -> m e
ltSwap Int
mid Int
lo
      e
_ <- Int -> Int -> m e
ltSwap Int
hi Int
lo
      Int -> Int -> m e
ltSwap Int
mid Int
hi
    {-# INLINE getPivot #-}
    qsort :: t -> Int -> Int -> m ()
qsort !t
n !Int
lo !Int
hi =
      Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
lo Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
hi) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
        e
p <- Int -> Int -> m e
getPivot Int
lo Int
hi
        Int
l <- MVector (PrimState m) r e -> (e -> m Bool) -> Int -> Int -> m Int
forall r e (m :: * -> *).
(Mutable r Int e, PrimMonad m) =>
MArray (PrimState m) r Int e
-> (e -> m Bool) -> Int -> Int -> m Int
unsafeUnstablePartitionRegionM' MVector (PrimState m) r e
marr (e -> e -> m Bool
`fLT` e
p) Int
lo (Int
hi Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
        Int
h <- MVector (PrimState m) r e -> (e -> m Bool) -> Int -> Int -> m Int
forall r e (m :: * -> *).
(Mutable r Int e, PrimMonad m) =>
MArray (PrimState m) r Int e
-> (e -> m Bool) -> Int -> Int -> m Int
unsafeUnstablePartitionRegionM' MVector (PrimState m) r e
marr (e -> e -> m Bool
`fEQ` e
p) Int
l Int
hi
        if t
n t -> t -> Bool
forall a. Ord a => a -> a -> Bool
> t
0
          then do
            let !n' :: t
n' = t
n t -> t -> t
forall a. Num a => a -> a -> a
- t
1
            Scheduler m () -> m () -> m ()
forall (m :: * -> *) a. Scheduler m a -> m a -> m ()
scheduleWork Scheduler m ()
scheduler (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ t -> Int -> Int -> m ()
qsort t
n' Int
lo (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
            Scheduler m () -> m () -> m ()
forall (m :: * -> *) a. Scheduler m a -> m a -> m ()
scheduleWork Scheduler m ()
scheduler (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ t -> Int -> Int -> m ()
qsort t
n' Int
h Int
hi
          else do
            t -> Int -> Int -> m ()
qsort t
n Int
lo (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
            t -> Int -> Int -> m ()
qsort t
n Int
h Int
hi
{-# INLINE quicksortInternalM_ #-}