vector-algorithms-0.9.1.0: Efficient algorithms for vector arrays

Copyright | (c) 2011 Dan Doel
Maintainer | Dan Doel <dan.doel@gmail.com>
Stability | Experimental
Portability | Non-portable (FlexibleContexts, ScopedTypeVariables)
Safe Haskell | None
Language | Haskell2010

Data.Vector.Algorithms.AmericanFlag

Description

This module implements American flag sort: an in-place, unstable, bucket sort. Also in contrast to radix sort, the values are inspected in a big endian order, and buckets are sorted via recursive splitting. This, however, makes it sensible for sorting strings in lexicographic order (provided indexing is fast).

The algorithm works as follows: at each stage, the array is looped over, counting the number of elements for each bucket. Then, starting at the beginning of the array, elements are permuted in place to reside in the proper bucket, following chains until they reach back to the current base index. Finally, each bucket is sorted recursively. This lends itself well to the aforementioned variable-length strings, and so the algorithm takes a stopping predicate, which is given a representative of the stripe, rather than running for a set number of iterations.

Synopsis

- sort :: forall e m v. (PrimMonad m, MVector v e, Lexicographic e, Ord e) => v (PrimState m) e -> m ()
- sortUniq :: forall e m v. (PrimMonad m, MVector v e, Lexicographic e, Ord e) => v (PrimState m) e -> m (v (PrimState m) e)
- sortBy :: (PrimMonad m, MVector v e) => Comparison e -> (e -> Int -> Bool) -> Int -> (Int -> e -> Int) -> v (PrimState m) e -> m ()
- sortUniqBy :: (PrimMonad m, MVector v e) => Comparison e -> (e -> Int -> Bool) -> Int -> (Int -> e -> Int) -> v (PrimState m) e -> m (v (PrimState m) e)
- terminate :: Lexicographic e => e -> Int -> Bool
- class Lexicographic e where
  - extent :: e -> Int
  - size :: Proxy e -> Int
  - index :: Int -> e -> Int

# Documentation

sort :: forall e m v. (PrimMonad m, MVector v e, Lexicographic e, Ord e) => v (PrimState m) e -> m () Source #

Sorts an array using the default ordering. Both Lexicographic and Ord are necessary because the algorithm falls back to insertion sort for sufficiently small arrays.

sortUniq :: forall e m v. (PrimMonad m, MVector v e, Lexicographic e, Ord e) => v (PrimState m) e -> m (v (PrimState m) e) Source #

A variant on `sort` that returns a vector of unique elements.

sortBy Source #

Arguments

:: (PrimMonad m, MVector v e) |
=> Comparison e | a comparison for the insertion sort flalback
-> (e -> Int -> Bool) | determines whether a stripe is complete
-> Int | the number of buckets necessary
-> (Int -> e -> Int) | the big-endian radix function
-> v (PrimState m) e | the array to be sorted
-> m () |

A fully parameterized version of the sorting algorithm. Again, this function takes both radix information and a comparison, because the algorithms falls back to insertion sort for small arrays.

sortUniqBy Source #

Arguments

:: (PrimMonad m, MVector v e) |
=> Comparison e | a comparison for the insertion sort flalback
-> (e -> Int -> Bool) | determines whether a stripe is complete
-> Int | the number of buckets necessary
-> (Int -> e -> Int) | the big-endian radix function
-> v (PrimState m) e | the array to be sorted
-> m (v (PrimState m) e) |

A variant on `sortBy` which returns a vector of unique elements.

terminate :: Lexicographic e => e -> Int -> Bool Source #

Given a representative of a stripe and an index number, this function determines whether to stop sorting.

class Lexicographic e where Source #

The methods of this class specify the information necessary to sort arrays using the default ordering. The name `Lexicographic` is meant to convey that index should return results in a similar way to indexing into a string.

Methods

extent :: e -> Int Source #

Computes the length of a representative of a stripe. It should take `n` passes to sort values of extent `n`. The extent may not be uniform across all values of the type.

size :: Proxy e -> Int Source #

The size of the bucket array necessary for sorting es

index :: Int -> e -> Int Source #

Determines which bucket a given element should inhabit for a particular iteration.

#### Instances

Instances details

Lexicographic ByteString Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: ByteString -> Int Source # size :: Proxy ByteString -> Int Source # index :: Int -> ByteString -> Int Source #
Lexicographic Int16 Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Int16 -> Int Source # size :: Proxy Int16 -> Int Source # index :: Int -> Int16 -> Int Source #
Lexicographic Int32 Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Int32 -> Int Source # size :: Proxy Int32 -> Int Source # index :: Int -> Int32 -> Int Source #
Lexicographic Int64 Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Int64 -> Int Source # size :: Proxy Int64 -> Int Source # index :: Int -> Int64 -> Int Source #
Lexicographic Int8 Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Int8 -> Int Source # size :: Proxy Int8 -> Int Source # index :: Int -> Int8 -> Int Source #
Lexicographic Word16 Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Word16 -> Int Source # size :: Proxy Word16 -> Int Source # index :: Int -> Word16 -> Int Source #
Lexicographic Word32 Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Word32 -> Int Source # size :: Proxy Word32 -> Int Source # index :: Int -> Word32 -> Int Source #
Lexicographic Word64 Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Word64 -> Int Source # size :: Proxy Word64 -> Int Source # index :: Int -> Word64 -> Int Source #
Lexicographic Word8 Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Word8 -> Int Source # size :: Proxy Word8 -> Int Source # index :: Int -> Word8 -> Int Source #
Lexicographic Int Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Int -> Int Source # size :: Proxy Int -> Int Source # index :: Int -> Int -> Int Source #
Lexicographic Word Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Word -> Int Source # size :: Proxy Word -> Int Source # index :: Int -> Word -> Int Source #
(Lexicographic a, Lexicographic b) => Lexicographic (Either a b) Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: Either a b -> Int Source # size :: Proxy (Either a b) -> Int Source # index :: Int -> Either a b -> Int Source #
(Lexicographic a, Lexicographic b) => Lexicographic (a, b) Source # |
Instance details Defined in Data.Vector.Algorithms.AmericanFlag Methods extent :: (a, b) -> Int Source # size :: Proxy (a, b) -> Int Source # index :: Int -> (a, b) -> Int Source #