-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Efficient algorithms for vector arrays
--   
--   Efficient algorithms for vector arrays
@package vector-algorithms
@version 0.5.4.2


-- | This module provides a radix sort for a subclass of unboxed arrays.
--   The radix class gives information on * the number of passes needed for
--   the data type
--   
--   <ul>
--   <li>the size of the auxiliary arrays</li>
--   <li>how to compute the pass-k radix of a value</li>
--   </ul>
--   
--   Radix sort is not a comparison sort, so it is able to achieve O(n) run
--   time, though it also uses O(n) auxiliary space. In addition, there is
--   a constant space overhead of 2*size*sizeOf(Int) for the sort, so it is
--   not advisable to use this sort for large numbers of very small arrays.
--   
--   A standard example (upon which one could base their own Radix
--   instance) is Word32:
--   
--   <ul>
--   <li>We choose to sort on r = 8 bits at a time</li>
--   <li>A Word32 has b = 32 bits total</li>
--   </ul>
--   
--   Thus, b/r = 4 passes are required, 2^r = 256 elements are needed in an
--   auxiliary array, and the radix function is:
--   
--   <pre>
--   radix k e = (e `shiftR` (k*8)) .&amp;. 256
--   </pre>
module Data.Vector.Algorithms.Radix

-- | Sorts an array based on the Radix instance.
sort :: (PrimMonad m, MVector v e, Radix e) => v (PrimState m) e -> m ()

-- | Radix sorts an array using custom radix information requires the
--   number of passes to fully sort the array, the size of of auxiliary
--   arrays necessary (should be one greater than the maximum value
--   returned by the radix function), and a radix function, which takes the
--   pass and an element, and returns the relevant radix.
sortBy :: (PrimMonad m, MVector v e) => Int -> Int -> (Int -> e -> Int) -> v (PrimState m) e -> m ()
class Radix e
passes :: Radix e => e -> Int
size :: Radix e => e -> Int
radix :: Radix e => Int -> e -> Int
instance (Radix i, Radix j) => Radix (i, j)
instance Radix Word64
instance Radix Word32
instance Radix Word16
instance Radix Word8
instance Radix Word
instance Radix Int64
instance Radix Int32
instance Radix Int16
instance Radix Int8
instance Radix Int


-- | This module implements several methods of searching for indicies to
--   insert elements into a sorted vector.
module Data.Vector.Algorithms.Search

-- | Finds an index in a given sorted vector at which the given element
--   could be inserted while maintaining the sortedness of the vector.
binarySearch :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m Int

-- | Finds an index in a given vector, which must be sorted with respect to
--   the given comparison function, at which the given element could be
--   inserted while preserving the vector's sortedness.
binarySearchBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int

-- | Given a vector sorted with respect to a given comparison function in
--   indices in [l,u), finds an index in [l,u] at which the given element
--   could be inserted while preserving sortedness.
binarySearchByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int

-- | Finds the lowest index in a given sorted vector at which the given
--   element could be inserted while maintaining the sortedness.
binarySearchL :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m Int

-- | Finds the lowest index in a given vector, which must be sorted with
--   respect to the given comparison function, at which the given element
--   could be inserted while preserving the sortedness.
binarySearchLBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int

-- | Given a vector sorted with respect to a given comparison function on
--   indices in [l,u), finds the lowest index in [l,u] at which the given
--   element could be inserted while preserving sortedness.
binarySearchLByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int

-- | Finds the greatest index in a given sorted vector at which the given
--   element could be inserted while maintaining sortedness.
binarySearchR :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m Int

-- | Finds the greatest index in a given vector, which must be sorted with
--   respect to the given comparison function, at which the given element
--   could be inserted while preserving the sortedness.
binarySearchRBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int

-- | Given a vector sorted with respect to the given comparison function on
--   indices in [l,u), finds the greatest index in [l,u] at which the given
--   element could be inserted while preserving sortedness.
binarySearchRByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | Optimal sorts for very small array sizes, or for small numbers of
--   particular indices in a larger array (to be used, for instance, for
--   sorting a median of 3 values into the lowest position in an array for
--   a median-of-3 quicksort).
module Data.Vector.Algorithms.Optimal

-- | Sorts the elements at the two given indices using the comparison. This
--   is essentially a compare-and-swap, although the first index is assumed
--   to be the <tt>lower</tt> of the two.
sort2ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Sorts the elements at the positions <tt>off</tt> and 'off + 1' in the
--   given array using the comparison.
sort2ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Sorts the elements at the three given indices. The indices are assumed
--   to be given from lowest to highest, so if 'l &lt; m &lt; u' then
--   'sort3ByIndex cmp a m l u' essentially sorts the median of three into
--   the lowest position in the array.
sort3ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Sorts the three elements starting at the given offset in the array.
sort3ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Sorts the elements at the four given indices. Like the 2 and 3 element
--   versions, this assumes that the indices are given in increasing order,
--   so it can be used to sort medians into particular positions and so on.
sort4ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> Int -> m ()

-- | Sorts the four elements beginning at the offset.
sort4ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | A simple insertion sort. Though it's O(n^2), its iterative nature can
--   be beneficial for small arrays. It is used to sort small segments of
--   an array by some of the more heavy-duty, recursive algorithms.
module Data.Vector.Algorithms.Insertion

-- | Sorts an entire array using the default comparison for the type
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()

-- | Sorts an entire array using a given comparison
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()

-- | Sorts the portion of an array delimited by [l,u)
sortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Sorts the portion of the array delimited by [l,u) under the assumption
--   that [l,m) is already sorted.
sortByBounds' :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | 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.
module Data.Vector.Algorithms.AmericanFlag

-- | 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.
sort :: (PrimMonad m, MVector v e, Lexicographic e, Ord e) => v (PrimState m) e -> 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.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> (e -> Int -> Bool) -> Int -> (Int -> e -> Int) -> v (PrimState m) e -> m ()

-- | The methods of this class specify the information necessary to sort
--   arrays using the default ordering. The name <a>Lexicographic</a> is
--   meant to convey that index should return results in a similar way to
--   indexing into a string.
class Lexicographic e
terminate :: Lexicographic e => e -> Int -> Bool
size :: Lexicographic e => e -> Int
index :: Lexicographic e => Int -> e -> Int
instance Lexicographic ByteString
instance Lexicographic Int
instance Lexicographic Int64
instance Lexicographic Int32
instance Lexicographic Int16
instance Lexicographic Int8
instance Lexicographic Word
instance Lexicographic Word64
instance Lexicographic Word32
instance Lexicographic Word16
instance Lexicographic Word8


-- | This module implements operations for working with a quaternary heap
--   stored in an unboxed array. Most heapsorts are defined in terms of a
--   binary heap, in which each internal node has at most two children. By
--   contrast, a quaternary heap has internal nodes with up to four
--   children. This reduces the number of comparisons in a heapsort
--   slightly, and improves locality (again, slightly) by flattening out
--   the heap.
module Data.Vector.Algorithms.Heap

-- | Sorts an entire array using the default ordering.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()

-- | Sorts an entire array using a custom ordering.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()

-- | Sorts a portion of an array [l,u) using a custom ordering
sortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Moves the lowest k elements to the front of the array. The elements
--   will be in no particular order.
select :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()

-- | Moves the <tt>lowest</tt> (as defined by the comparison) k elements to
--   the front of the array. The elements will be in no particular order.
selectBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Moves the <tt>lowest</tt> k elements in the portion [l,u) of the array
--   into the positions [l,k+l). The elements will be in no particular
--   order.
selectByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Moves the lowest k elements to the front of the array, sorted.
partialSort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()

-- | Moves the lowest k elements (as defined by the comparison) to the
--   front of the array, sorted.
partialSortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Moves the lowest k elements in the portion [l,u) of the array into
--   positions [l,k+l), sorted.
partialSortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Constructs a heap in a portion of an array [l, u)
heapify :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Given a heap stored in a portion of an array [l,u), swaps the top of
--   the heap with the element at u and rebuilds the heap.
pop :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Given a heap stored in a portion of an array [l,u) swaps the top of
--   the heap with the element at position t, and rebuilds the heap.
popTo :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Given a heap stored in a portion of an array [l,u), sorts the highest
--   values into [m,u). The elements in [l,m) are not in any particular
--   order.
sortHeap :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | This module implements various algorithms based on the introsort
--   algorithm, originally described by David R. Musser in the paper
--   /Introspective Sorting and Selection Algorithms/. It is also in
--   widespread practical use, as the standard unstable sort used in the
--   C++ Standard Template Library.
--   
--   Introsort is at its core a quicksort. The version implemented here has
--   the following optimizations that make it perform better in practice:
--   
--   <ul>
--   <li>Small segments of the array are left unsorted until a final
--   insertion sort pass. This is faster than recursing all the way down to
--   one-element arrays.</li>
--   <li>The pivot for segment [l,u) is chosen as the median of the
--   elements at l, u-1 and (u+l)/2. This yields good behavior on mostly
--   sorted (or reverse-sorted) arrays.</li>
--   <li>The algorithm tracks its recursion depth, and if it decides it is
--   taking too long (depth greater than 2 * lg n), it switches to a heap
--   sort to maintain O(n lg n) worst case behavior. (This is what makes
--   the algorithm introsort).</li>
--   </ul>
module Data.Vector.Algorithms.Intro

-- | Sorts an entire array using the default ordering.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()

-- | Sorts an entire array using a custom ordering.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()

-- | Sorts a portion of an array [l,u) using a custom ordering
sortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Moves the least k elements to the front of the array in no particular
--   order.
select :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()

-- | Moves the least k elements (as defined by the comparison) to the front
--   of the array in no particular order.
selectBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Moves the least k elements in the interval [l,u) to the positions
--   [l,k+l) in no particular order.
selectByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Moves the least k elements to the front of the array, sorted.
partialSort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()

-- | Moves the least k elements (as defined by the comparison) to the front
--   of the array, sorted.
partialSortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Moves the least k elements in the interval [l,u) to the positions
--   [l,k+l), sorted.
partialSortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | This module implements a simple top-down merge sort. The temporary
--   buffer is preallocated to 1/2 the size of the input array, and shared
--   through the entire sorting process to ease the amount of allocation
--   performed in total. This is a stable sort.
module Data.Vector.Algorithms.Merge

-- | Sorts an array using the default comparison.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()

-- | Sorts an array using a custom comparison.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering