Z-Data-0.8.3.0: Array, vector and text
Copyright(c) 2008-2011 Dan Doel (c) Dong Han 2017-2018
LicenseBSD
Maintainerwinterland1989@gmail.com
Stabilityexperimental
Portabilitynon-portable
Safe HaskellNone
LanguageHaskell2010

Z.Data.Vector.Sort

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

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

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 -> () #

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

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

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

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

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 #

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)))
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

Radix Int8 Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix Int16 Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix Int32 Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix Int64 Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix Word Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix Word8 Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix Word16 Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix Word32 Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix Word64 Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix a => Radix (RadixDown a) Source # 
Instance details

Defined in Z.Data.Vector.Sort

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

Prim a => Prim (RadixDown a) Source # 
Instance details

Defined in Z.Data.Vector.Sort

Unaligned a => Unaligned (RadixDown a) Source # 
Instance details

Defined in Z.Data.Vector.Sort

Radix a => Radix (RadixDown a) Source # 
Instance details

Defined in Z.Data.Vector.Sort

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.