Copyright	(c) 2008-2011 Dan Doel (c) Dong Han 2017-2018
License	BSD
Maintainer	winterland1989@gmail.com
Stability	experimental
Portability	non-portable
Safe Haskell	None
Language	Haskell2010

Z.Data.Vector.Sort

Contents

Sort
merge duplicated

Description

This module provide three stable sorting algorithms, which are:

mergeSort, a O(log(n)) general-purpose sorting algorithms for all different size vectors.
insertSort a O(n^2) sorting algorithms suitable for very small vectors.
radixSort a O(n) sorting algorithms based on Radix instance, which is prefered on large vectors.

Sorting is always performed in ascending order. To reverse the order, either use XXSortBy or use Down, RadixDown newtypes. In general changing comparing functions can be done by creating auxiliary newtypes and Ord instances (make sure you inline instance's method for performence!). Or Radix instances in radixSort case, for example:

data Foo = Foo { key :: Int16, ... }

instance Radix Foo where
    -- You should add INLINE pragmas to following methods
    bucketSize = bucketSize . key
    passes = passes . key
    radixLSB = radixLSB . key
    radix i = radix i . key
    radixMSB = radixMSB . key

Synopsis

mergeSort :: forall v a. (Vec v a, Ord a) => v a -> v a
mergeSortBy :: forall v a. Vec v a => (a -> a -> Ordering) -> v a -> v a
mergeTileSize :: Int
insertSort :: (Vec v a, Ord a) => v a -> v a
insertSortBy :: Vec v a => (a -> a -> Ordering) -> v a -> v a
newtype Down a = Down {
- getDown :: a
}
radixSort :: forall v a. (Vec v a, Radix a) => v a -> v a
class Radix a where
- bucketSize :: a -> Int
- passes :: a -> Int
- radixLSB :: a -> Int
- radix :: Int -> a -> Int
- radixMSB :: a -> Int
newtype RadixDown a = RadixDown a
mergeDupAdjacent :: forall v a. (Vec v a, Eq a) => v a -> v a
mergeDupAdjacentLeft :: forall v a. Vec v a => (a -> a -> Bool) -> v a -> v a
mergeDupAdjacentRight :: forall v a. Vec v a => (a -> a -> Bool) -> v a -> v a
mergeDupAdjacentBy :: forall v a. Vec v a => (a -> a -> Bool) -> (a -> a -> a) -> v a -> v a

Sort

mergeSort :: forall v a. (Vec v a, Ord a) => v a -> v a Source #

O(n*log(n)) Sort vector based on element's Ord instance with classic mergesort algorithm.

This is a stable sort, During sorting two O(n) worker arrays are needed, one of them will be freezed into the result vector. The merge sort only begin at tile size larger than mergeTileSize, each tile will be sorted with insertSort, then iteratively merged into larger array, until all elements are sorted.

mergeSortBy :: forall v a. Vec v a => (a -> a -> Ordering) -> v a -> v a Source #

mergeTileSize :: Int Source #

The mergesort tile size, mergeTileSize = 8.

insertSort :: (Vec v a, Ord a) => v a -> v a Source #

O(n^2) Sort vector based on element's Ord instance with simple insertion-sort algorithm.

This is a stable sort. O(n) extra space are needed, which will be freezed into result vector.

insertSortBy :: Vec v a => (a -> a -> Ordering) -> v a -> v a Source #

newtype Down a #

The Down type allows you to reverse sort order conveniently. A value of type Down a contains a value of type a (represented as Down a). If a has an Ord instance associated with it then comparing two values thus wrapped will give you the opposite of their normal sort order. This is particularly useful when sorting in generalised list comprehensions, as in: then sortWith by Down x

Since: base-4.6.0.0

Constructors

Down
Fields getDown :: a Since: base-4.14.0.0

Instances

Instances details

Monad Down	Since: base-4.11.0.0
Instance details Defined in Data.Ord Methods (>>=) :: Down a -> (a -> Down b) -> Down b # (>>) :: Down a -> Down b -> Down b # return :: a -> Down a #
Functor Down	Since: base-4.11.0.0
Instance details Defined in Data.Ord Methods fmap :: (a -> b) -> Down a -> Down b # (<$) :: a -> Down b -> Down a #
Applicative Down	Since: base-4.11.0.0
Instance details Defined in Data.Ord Methods pure :: a -> Down a # (<>) :: Down (a -> b) -> Down a -> Down b # liftA2 :: (a -> b -> c) -> Down a -> Down b -> Down c # (>) :: Down a -> Down b -> Down b # (<*) :: Down a -> Down b -> Down a #
Foldable Down	Since: base-4.12.0.0
Instance details Defined in Data.Foldable Methods fold :: Monoid m => Down m -> m # foldMap :: Monoid m => (a -> m) -> Down a -> m # foldMap' :: Monoid m => (a -> m) -> Down a -> m # foldr :: (a -> b -> b) -> b -> Down a -> b # foldr' :: (a -> b -> b) -> b -> Down a -> b # foldl :: (b -> a -> b) -> b -> Down a -> b # foldl' :: (b -> a -> b) -> b -> Down a -> b # foldr1 :: (a -> a -> a) -> Down a -> a # foldl1 :: (a -> a -> a) -> Down a -> a # toList :: Down a -> [a] # null :: Down a -> Bool # length :: Down a -> Int # elem :: Eq a => a -> Down a -> Bool # maximum :: Ord a => Down a -> a # minimum :: Ord a => Down a -> a # sum :: Num a => Down a -> a # product :: Num a => Down a -> a #
Traversable Down	Since: base-4.12.0.0
Instance details Defined in Data.Traversable Methods traverse :: Applicative f => (a -> f b) -> Down a -> f (Down b) # sequenceA :: Applicative f => Down (f a) -> f (Down a) # mapM :: Monad m => (a -> m b) -> Down a -> m (Down b) # sequence :: Monad m => Down (m a) -> m (Down a) #
Eq1 Down	Since: base-4.12.0.0
Instance details Defined in Data.Functor.Classes Methods liftEq :: (a -> b -> Bool) -> Down a -> Down b -> Bool #
Ord1 Down	Since: base-4.12.0.0
Instance details Defined in Data.Functor.Classes Methods liftCompare :: (a -> b -> Ordering) -> Down a -> Down b -> Ordering #
Read1 Down	Since: base-4.12.0.0
Instance details Defined in Data.Functor.Classes Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Down a) # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Down a] # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Down a) # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Down a] #
Show1 Down	Since: base-4.12.0.0
Instance details Defined in Data.Functor.Classes Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Down a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Down a] -> ShowS #
NFData1 Down	Since: deepseq-1.4.3.0
Instance details Defined in Control.DeepSeq Methods liftRnf :: (a -> ()) -> Down a -> () #
Unbox a => Vector Vector (Down a)
Instance details Defined in Data.Vector.Unboxed.Base Methods basicUnsafeFreeze :: PrimMonad m => Mutable Vector (PrimState m) (Down a) -> m (Vector (Down a)) # basicUnsafeThaw :: PrimMonad m => Vector (Down a) -> m (Mutable Vector (PrimState m) (Down a)) # basicLength :: Vector (Down a) -> Int # basicUnsafeSlice :: Int -> Int -> Vector (Down a) -> Vector (Down a) # basicUnsafeIndexM :: Monad m => Vector (Down a) -> Int -> m (Down a) # basicUnsafeCopy :: PrimMonad m => Mutable Vector (PrimState m) (Down a) -> Vector (Down a) -> m () # elemseq :: Vector (Down a) -> Down a -> b -> b #
Unbox a => MVector MVector (Down a)
Instance details Defined in Data.Vector.Unboxed.Base Methods basicLength :: MVector s (Down a) -> Int # basicUnsafeSlice :: Int -> Int -> MVector s (Down a) -> MVector s (Down a) # basicOverlaps :: MVector s (Down a) -> MVector s (Down a) -> Bool # basicUnsafeNew :: PrimMonad m => Int -> m (MVector (PrimState m) (Down a)) # basicInitialize :: PrimMonad m => MVector (PrimState m) (Down a) -> m () # basicUnsafeReplicate :: PrimMonad m => Int -> Down a -> m (MVector (PrimState m) (Down a)) # basicUnsafeRead :: PrimMonad m => MVector (PrimState m) (Down a) -> Int -> m (Down a) # basicUnsafeWrite :: PrimMonad m => MVector (PrimState m) (Down a) -> Int -> Down a -> m () # basicClear :: PrimMonad m => MVector (PrimState m) (Down a) -> m () # basicSet :: PrimMonad m => MVector (PrimState m) (Down a) -> Down a -> m () # basicUnsafeCopy :: PrimMonad m => MVector (PrimState m) (Down a) -> MVector (PrimState m) (Down a) -> m () # basicUnsafeMove :: PrimMonad m => MVector (PrimState m) (Down a) -> MVector (PrimState m) (Down a) -> m () # basicUnsafeGrow :: PrimMonad m => MVector (PrimState m) (Down a) -> Int -> m (MVector (PrimState m) (Down a)) #
Bounded a => Bounded (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods minBound :: Down a # maxBound :: Down a #
Enum a => Enum (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods succ :: Down a -> Down a # pred :: Down a -> Down a # toEnum :: Int -> Down a # fromEnum :: Down a -> Int # enumFrom :: Down a -> [Down a] # enumFromThen :: Down a -> Down a -> [Down a] # enumFromTo :: Down a -> Down a -> [Down a] # enumFromThenTo :: Down a -> Down a -> Down a -> [Down a] #
Eq a => Eq (Down a)	Since: base-4.6.0.0
Instance details Defined in Data.Ord Methods (==) :: Down a -> Down a -> Bool # (/=) :: Down a -> Down a -> Bool #
Floating a => Floating (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods pi :: Down a # exp :: Down a -> Down a # log :: Down a -> Down a # sqrt :: Down a -> Down a # (**) :: Down a -> Down a -> Down a # logBase :: Down a -> Down a -> Down a # sin :: Down a -> Down a # cos :: Down a -> Down a # tan :: Down a -> Down a # asin :: Down a -> Down a # acos :: Down a -> Down a # atan :: Down a -> Down a # sinh :: Down a -> Down a # cosh :: Down a -> Down a # tanh :: Down a -> Down a # asinh :: Down a -> Down a # acosh :: Down a -> Down a # atanh :: Down a -> Down a # log1p :: Down a -> Down a # expm1 :: Down a -> Down a # log1pexp :: Down a -> Down a # log1mexp :: Down a -> Down a #
Fractional a => Fractional (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods (/) :: Down a -> Down a -> Down a # recip :: Down a -> Down a # fromRational :: Rational -> Down a #
Integral a => Integral (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods quot :: Down a -> Down a -> Down a # rem :: Down a -> Down a -> Down a # div :: Down a -> Down a -> Down a # mod :: Down a -> Down a -> Down a # quotRem :: Down a -> Down a -> (Down a, Down a) # divMod :: Down a -> Down a -> (Down a, Down a) # toInteger :: Down a -> Integer #
Data a => Data (Down a)	Since: base-4.12.0.0
Instance details Defined in Data.Data Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Down a -> c (Down a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Down a) # toConstr :: Down a -> Constr # dataTypeOf :: Down a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Down a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Down a)) # gmapT :: (forall b. Data b => b -> b) -> Down a -> Down a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Down a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Down a -> r # gmapQ :: (forall d. Data d => d -> u) -> Down a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Down a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Down a -> m (Down a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Down a -> m (Down a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Down a -> m (Down a) #
Num a => Num (Down a)	Since: base-4.11.0.0
Instance details Defined in Data.Ord Methods (+) :: Down a -> Down a -> Down a # (-) :: Down a -> Down a -> Down a # (*) :: Down a -> Down a -> Down a # negate :: Down a -> Down a # abs :: Down a -> Down a # signum :: Down a -> Down a # fromInteger :: Integer -> Down a #
Ord a => Ord (Down a)	Since: base-4.6.0.0
Instance details Defined in Data.Ord Methods compare :: Down a -> Down a -> Ordering # (<) :: Down a -> Down a -> Bool # (<=) :: Down a -> Down a -> Bool # (>) :: Down a -> Down a -> Bool # (>=) :: Down a -> Down a -> Bool # max :: Down a -> Down a -> Down a # min :: Down a -> Down a -> Down a #
Read a => Read (Down a)	This instance would be equivalent to the derived instances of the `Down` newtype if the `getDown` field were removed Since: base-4.7.0.0
Instance details Defined in Data.Ord Methods readsPrec :: Int -> ReadS (Down a) # readList :: ReadS [Down a] # readPrec :: ReadPrec (Down a) # readListPrec :: ReadPrec [Down a] #
Real a => Real (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods toRational :: Down a -> Rational #
RealFloat a => RealFloat (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods floatRadix :: Down a -> Integer # floatDigits :: Down a -> Int # floatRange :: Down a -> (Int, Int) # decodeFloat :: Down a -> (Integer, Int) # encodeFloat :: Integer -> Int -> Down a # exponent :: Down a -> Int # significand :: Down a -> Down a # scaleFloat :: Int -> Down a -> Down a # isNaN :: Down a -> Bool # isInfinite :: Down a -> Bool # isDenormalized :: Down a -> Bool # isNegativeZero :: Down a -> Bool # isIEEE :: Down a -> Bool # atan2 :: Down a -> Down a -> Down a #
RealFrac a => RealFrac (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods properFraction :: Integral b => Down a -> (b, Down a) # truncate :: Integral b => Down a -> b # round :: Integral b => Down a -> b # ceiling :: Integral b => Down a -> b # floor :: Integral b => Down a -> b #
Show a => Show (Down a)	This instance would be equivalent to the derived instances of the `Down` newtype if the `getDown` field were removed Since: base-4.7.0.0
Instance details Defined in Data.Ord Methods showsPrec :: Int -> Down a -> ShowS # show :: Down a -> String # showList :: [Down a] -> ShowS #
Ix a => Ix (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods range :: (Down a, Down a) -> [Down a] # index :: (Down a, Down a) -> Down a -> Int # unsafeIndex :: (Down a, Down a) -> Down a -> Int # inRange :: (Down a, Down a) -> Down a -> Bool # rangeSize :: (Down a, Down a) -> Int # unsafeRangeSize :: (Down a, Down a) -> Int #
Generic (Down a)	Since: base-4.12.0.0
Instance details Defined in GHC.Generics Associated Types type Rep (Down a) :: Type -> Type # Methods from :: Down a -> Rep (Down a) x # to :: Rep (Down a) x -> Down a #
Semigroup a => Semigroup (Down a)	Since: base-4.11.0.0
Instance details Defined in Data.Ord Methods (<>) :: Down a -> Down a -> Down a # sconcat :: NonEmpty (Down a) -> Down a # stimes :: Integral b => b -> Down a -> Down a #
Monoid a => Monoid (Down a)	Since: base-4.11.0.0
Instance details Defined in Data.Ord Methods mempty :: Down a # mappend :: Down a -> Down a -> Down a # mconcat :: [Down a] -> Down a #
Storable a => Storable (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods sizeOf :: Down a -> Int # alignment :: Down a -> Int # peekElemOff :: Ptr (Down a) -> Int -> IO (Down a) # pokeElemOff :: Ptr (Down a) -> Int -> Down a -> IO () # peekByteOff :: Ptr b -> Int -> IO (Down a) # pokeByteOff :: Ptr b -> Int -> Down a -> IO () # peek :: Ptr (Down a) -> IO (Down a) # poke :: Ptr (Down a) -> Down a -> IO () #
Bits a => Bits (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods (.&.) :: Down a -> Down a -> Down a # (.\|.) :: Down a -> Down a -> Down a # xor :: Down a -> Down a -> Down a # complement :: Down a -> Down a # shift :: Down a -> Int -> Down a # rotate :: Down a -> Int -> Down a # zeroBits :: Down a # bit :: Int -> Down a # setBit :: Down a -> Int -> Down a # clearBit :: Down a -> Int -> Down a # complementBit :: Down a -> Int -> Down a # testBit :: Down a -> Int -> Bool # bitSizeMaybe :: Down a -> Maybe Int # bitSize :: Down a -> Int # isSigned :: Down a -> Bool # shiftL :: Down a -> Int -> Down a # unsafeShiftL :: Down a -> Int -> Down a # shiftR :: Down a -> Int -> Down a # unsafeShiftR :: Down a -> Int -> Down a # rotateL :: Down a -> Int -> Down a # rotateR :: Down a -> Int -> Down a # popCount :: Down a -> Int #
FiniteBits a => FiniteBits (Down a)	Since: base-4.14.0.0
Instance details Defined in Data.Ord Methods finiteBitSize :: Down a -> Int # countLeadingZeros :: Down a -> Int # countTrailingZeros :: Down a -> Int #
NFData a => NFData (Down a)	Since: deepseq-1.4.0.0
Instance details Defined in Control.DeepSeq Methods rnf :: Down a -> () #
Prim a => Prim (Down a)	Since: primitive-0.6.5.0
Instance details Defined in Data.Primitive.Types Methods sizeOf# :: Down a -> Int# # alignment# :: Down a -> Int# # indexByteArray# :: ByteArray# -> Int# -> Down a # readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Down a #) # writeByteArray# :: MutableByteArray# s -> Int# -> Down a -> State# s -> State# s # setByteArray# :: MutableByteArray# s -> Int# -> Int# -> Down a -> State# s -> State# s # indexOffAddr# :: Addr# -> Int# -> Down a # readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Down a #) # writeOffAddr# :: Addr# -> Int# -> Down a -> State# s -> State# s # setOffAddr# :: Addr# -> Int# -> Int# -> Down a -> State# s -> State# s #
Unbox a => Unbox (Down a)
Instance details Defined in Data.Vector.Unboxed.Base
Generic1 Down	Since: base-4.12.0.0
Instance details Defined in GHC.Generics Associated Types type Rep1 Down :: k -> Type # Methods from1 :: forall (a :: k). Down a -> Rep1 Down a # to1 :: forall (a :: k). Rep1 Down a -> Down a #
newtype MVector s (Down a)
Instance details Defined in Data.Vector.Unboxed.Base newtype MVector s (Down a) = MV_Down (MVector s a)
type Rep (Down a)
Instance details Defined in GHC.Generics type Rep (Down a) = D1 ('MetaData "Down" "Data.Ord" "base" 'True) (C1 ('MetaCons "Down" 'PrefixI 'True) (S1 ('MetaSel ('Just "getDown") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)))
newtype Vector (Down a)
Instance details Defined in Data.Vector.Unboxed.Base newtype Vector (Down a) = V_Down (Vector a)
type Rep1 Down
Instance details Defined in GHC.Generics type Rep1 Down = D1 ('MetaData "Down" "Data.Ord" "base" 'True) (C1 ('MetaCons "Down" 'PrefixI 'True) (S1 ('MetaSel ('Just "getDown") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1))

radixSort :: forall v a. (Vec v a, Radix a) => v a -> v a Source #

O(n) Sort vector based on element's Radix instance with radix-sort, (Least significant digit radix sorts variation).

This is a stable sort, one or two extra O(n) worker array are need depend on how many passes shall be performed, and a bucketSize counting bucket are also needed. This sort algorithms performed extremly well on small byte size types such as Int8 or Word8, while on larger type, constant passes may render this algorithm not suitable for small vectors (turning point around 2^(2*passes)).

class Radix a where Source #

Types contain radixs, which can be inspected with radix during different passes.

The default instances share a same bucketSize 256, which seems to be a good default.

Methods

bucketSize :: a -> Int Source #

The size of an auxiliary array, i.e. the counting bucket

passes :: a -> Int Source #

The number of passes necessary to sort an array of es, it equals to the key's byte number.

radixLSB :: a -> Int Source #

The radix function used in the first pass, works on the least significant bit.

radix :: Int -> a -> Int Source #

The radix function parameterized by the current pass (0 < pass < passes e-1).

radixMSB :: a -> Int Source #

The radix function used in the last pass, works on the most significant bit.

Instances

Instances details

Radix Int Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Int -> Int Source # passes :: Int -> Int Source # radixLSB :: Int -> Int Source # radix :: Int -> Int -> Int Source # radixMSB :: Int -> Int Source #
Radix Int8 Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Int8 -> Int Source # passes :: Int8 -> Int Source # radixLSB :: Int8 -> Int Source # radix :: Int -> Int8 -> Int Source # radixMSB :: Int8 -> Int Source #
Radix Int16 Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Int16 -> Int Source # passes :: Int16 -> Int Source # radixLSB :: Int16 -> Int Source # radix :: Int -> Int16 -> Int Source # radixMSB :: Int16 -> Int Source #
Radix Int32 Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Int32 -> Int Source # passes :: Int32 -> Int Source # radixLSB :: Int32 -> Int Source # radix :: Int -> Int32 -> Int Source # radixMSB :: Int32 -> Int Source #
Radix Int64 Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Int64 -> Int Source # passes :: Int64 -> Int Source # radixLSB :: Int64 -> Int Source # radix :: Int -> Int64 -> Int Source # radixMSB :: Int64 -> Int Source #
Radix Word Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Word -> Int Source # passes :: Word -> Int Source # radixLSB :: Word -> Int Source # radix :: Int -> Word -> Int Source # radixMSB :: Word -> Int Source #
Radix Word8 Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Word8 -> Int Source # passes :: Word8 -> Int Source # radixLSB :: Word8 -> Int Source # radix :: Int -> Word8 -> Int Source # radixMSB :: Word8 -> Int Source #
Radix Word16 Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Word16 -> Int Source # passes :: Word16 -> Int Source # radixLSB :: Word16 -> Int Source # radix :: Int -> Word16 -> Int Source # radixMSB :: Word16 -> Int Source #
Radix Word32 Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Word32 -> Int Source # passes :: Word32 -> Int Source # radixLSB :: Word32 -> Int Source # radix :: Int -> Word32 -> Int Source # radixMSB :: Word32 -> Int Source #
Radix Word64 Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: Word64 -> Int Source # passes :: Word64 -> Int Source # radixLSB :: Word64 -> Int Source # radix :: Int -> Word64 -> Int Source # radixMSB :: Word64 -> Int Source #
Radix a => Radix (RadixDown a) Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: RadixDown a -> Int Source # passes :: RadixDown a -> Int Source # radixLSB :: RadixDown a -> Int Source # radix :: Int -> RadixDown a -> Int Source # radixMSB :: RadixDown a -> Int Source #

newtype RadixDown a Source #

Similar to Down newtype for Ord, this newtype can inverse the order of a Radix instance when used in radixSort.

Constructors

RadixDown a

Instances

Instances details

Eq a => Eq (RadixDown a) Source #
Instance details Defined in Z.Data.Vector.Sort Methods (==) :: RadixDown a -> RadixDown a -> Bool # (/=) :: RadixDown a -> RadixDown a -> Bool #
Show a => Show (RadixDown a) Source #
Instance details Defined in Z.Data.Vector.Sort Methods showsPrec :: Int -> RadixDown a -> ShowS # show :: RadixDown a -> String # showList :: [RadixDown a] -> ShowS #
Prim a => Prim (RadixDown a) Source #
Instance details Defined in Z.Data.Vector.Sort Methods sizeOf# :: RadixDown a -> Int# # alignment# :: RadixDown a -> Int# # indexByteArray# :: ByteArray# -> Int# -> RadixDown a # readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, RadixDown a #) # writeByteArray# :: MutableByteArray# s -> Int# -> RadixDown a -> State# s -> State# s # setByteArray# :: MutableByteArray# s -> Int# -> Int# -> RadixDown a -> State# s -> State# s # indexOffAddr# :: Addr# -> Int# -> RadixDown a # readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, RadixDown a #) # writeOffAddr# :: Addr# -> Int# -> RadixDown a -> State# s -> State# s # setOffAddr# :: Addr# -> Int# -> Int# -> RadixDown a -> State# s -> State# s #
Unaligned a => Unaligned (RadixDown a) Source #
Instance details Defined in Z.Data.Vector.Sort Methods unalignedSize :: UnalignedSize (RadixDown a) Source # indexWord8ArrayAs# :: ByteArray# -> Int# -> RadixDown a Source # readWord8ArrayAs# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, RadixDown a #) Source # writeWord8ArrayAs# :: MutableByteArray# s -> Int# -> RadixDown a -> State# s -> State# s Source # peekMBA :: MutableByteArray# RealWorld -> Int -> IO (RadixDown a) Source # pokeMBA :: MutableByteArray# RealWorld -> Int -> RadixDown a -> IO () Source # indexBA :: ByteArray# -> Int -> RadixDown a Source #
Radix a => Radix (RadixDown a) Source #
Instance details Defined in Z.Data.Vector.Sort Methods bucketSize :: RadixDown a -> Int Source # passes :: RadixDown a -> Int Source # radixLSB :: RadixDown a -> Int Source # radix :: Int -> RadixDown a -> Int Source # radixMSB :: RadixDown a -> Int Source #

merge duplicated

mergeDupAdjacent :: forall v a. (Vec v a, Eq a) => v a -> v a Source #

merge duplicated adjacent element, prefer left element.

Use this function on a sorted vector will have the same effects as nub.

mergeDupAdjacentLeft Source #

Arguments

:: forall v a. Vec v a
=> (a -> a -> Bool)	equality tester, `left right -> eq left right`
-> v a
-> v a

Merge duplicated adjacent element, prefer left element.

mergeDupAdjacentRight Source #

Arguments

:: forall v a. Vec v a
=> (a -> a -> Bool)	equality tester, `left right -> eq left right`
-> v a
-> v a

Merge duplicated adjacent element, prefer right element.

mergeDupAdjacentBy Source #

Arguments

:: forall v a. Vec v a
=> (a -> a -> Bool)	equality tester, `left right -> eq left right`
-> (a -> a -> a)	the merger, `left right -> merge left right`
-> v a
-> v a

Merge duplicated adjacent element, based on a equality tester and a merger function.