module Data.Vector.Sort.Bucket where

import qualified Data.Vector.Unboxed as U

bucketSort :: Int -> U.Vector Int -> U.Vector Int
bucketSort :: Int -> Vector Int -> Vector Int
bucketSort Int
bucketSize =
  ((Int, Int) -> Vector Int) -> Vector (Int, Int) -> Vector Int
forall a b.
(Unbox a, Unbox b) =>
(a -> Vector b) -> Vector a -> Vector b
U.concatMap ((Int -> Int -> Vector Int) -> (Int, Int) -> Vector Int
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((Int -> Int -> Vector Int) -> (Int, Int) -> Vector Int)
-> (Int -> Int -> Vector Int) -> (Int, Int) -> Vector Int
forall a b. (a -> b) -> a -> b
$ (Int -> Int -> Vector Int) -> Int -> Int -> Vector Int
forall a b c. (a -> b -> c) -> b -> a -> c
flip Int -> Int -> Vector Int
forall a. Unbox a => Int -> a -> Vector a
U.replicate)
    (Vector (Int, Int) -> Vector Int)
-> (Vector Int -> Vector (Int, Int)) -> Vector Int -> Vector Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector Int -> Vector (Int, Int)
forall a. Unbox a => Vector a -> Vector (Int, a)
U.indexed
    (Vector Int -> Vector (Int, Int))
-> (Vector Int -> Vector Int) -> Vector Int -> Vector (Int, Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int -> Int)
-> Vector Int -> Vector (Int, Int) -> Vector Int
forall a b.
(Unbox a, Unbox b) =>
(a -> b -> a) -> Vector a -> Vector (Int, b) -> Vector a
U.unsafeAccumulate Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Vector Int
forall a. Unbox a => Int -> a -> Vector a
U.replicate Int
bucketSize Int
0)
    (Vector (Int, Int) -> Vector Int)
-> (Vector Int -> Vector (Int, Int)) -> Vector Int -> Vector Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> (Int, Int)) -> Vector Int -> Vector (Int, Int)
forall a b. (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
U.map ((Int -> Int -> (Int, Int)) -> Int -> Int -> (Int, Int)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (,) Int
1)
{-# INLINE bucketSort #-}