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


-- | Efficient algorithms for vector arrays
--   
--   Efficient algorithms for vector arrays be sure to compile with -O2,
--   and -fvia-C -optc-O3 is recommended.
@package vector-algorithms
@version 0.3


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

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

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

-- | Given an array 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 array 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 array, 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 an array 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

-- | 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 operations for working with a trinary 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 trinary heap has internal nodes with up to three 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.TriHeap

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

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

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


-- | The purpose of this module is to supply various combinators for
--   commonly used idioms for the algorithms in this package. Examples at
--   the time of this writing include running an algorithm keyed on some
--   function of the elements (but only computing said function once per
--   element), and safely applying the algorithms on mutable arrays to
--   immutable arrays.
module Data.Vector.Algorithms.Combinators

-- | Safely applies a mutable array algorithm to an immutable array.
apply :: (Vector v e) => (forall s mv. (MVector mv e) => mv s e -> ST s ()) -> v e -> v e