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


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


-- | 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.Array.Vector.Algorithms.Radix

-- | Sorts an array based on the Radix instance.
sort :: (Radix e) => MUArr e s -> ST s ()
class (UA e) => Radix e
passes :: (Radix e) => e -> Int
size :: (Radix e) => e -> Int
radix :: (Radix e) => Int -> e -> Int
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


-- | 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.Array.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 :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> ST s ()

-- | Sorts the elements at the positions <tt>off</tt> and 'off + 1' in the
--   given array using the comparison.
sort2ByOffset :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()

-- | 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 :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()

-- | Sorts the three elements starting at the given offset in the array.
sort3ByOffset :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()

-- | 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 :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> Int -> ST s ()

-- | Sorts the four elements beginning at the offset.
sort4ByOffset :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()


-- | 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.Array.Vector.Algorithms.Insertion

-- | Sorts an entire array using the default comparison for the type
sort :: (UA e, Ord e) => MUArr e s -> ST s ()

-- | Sorts an entire array using a given comparison
sortBy :: (UA e) => Comparison e -> MUArr e s -> ST s ()

-- | Sorts the portion of an array delimited by [l,u)
sortByBounds :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> ST s ()

-- | Sorts the portion of the array delimited by [l,u) under the assumption
--   that [l,m) is already sorted.
sortByBounds' :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()


-- | 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.Array.Vector.Algorithms.TriHeap

-- | Sorts an entire array using the default ordering.
sort :: (UA e, Ord e) => MUArr e s -> ST s ()

-- | Sorts an entire array using a custom ordering.
sortBy :: (UA e) => Comparison e -> MUArr e s -> ST s ()

-- | Sorts a portion of an array [l,u) using a custom ordering
sortByBounds :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> ST s ()

-- | Moves the lowest k elements to the front of the array. The elements
--   will be in no particular order.
select :: (UA e, Ord e) => MUArr e s -> Int -> ST s ()

-- | 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 :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()

-- | 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 :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()

-- | Moves the lowest k elements to the front of the array, sorted.
partialSort :: (UA e, Ord e) => MUArr e s -> Int -> ST s ()

-- | Moves the lowest k elements (as defined by the comparison) to the
--   front of the array, sorted.
partialSortBy :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()

-- | Moves the lowest k elements in the portion [l,u) of the array into
--   positions [l,k+l), sorted.
partialSortByBounds :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()

-- | Constructs a heap in a portion of an array [l, u)
heapify :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> ST s ()

-- | 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 :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> ST s ()

-- | 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 :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()

-- | 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 :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()


-- | 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.Array.Vector.Algorithms.Intro

-- | Sorts an entire array using the default ordering.
sort :: (UA e, Ord e) => MUArr e s -> ST s ()

-- | Sorts an entire array using a custom ordering.
sortBy :: (UA e) => Comparison e -> MUArr e s -> ST s ()

-- | Sorts a portion of an array [l,u) using a custom ordering
sortByBounds :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> ST s ()

-- | Moves the least k elements to the front of the array in no particular
--   order.
select :: (UA e, Ord e) => MUArr e s -> Int -> ST s ()

-- | Moves the least k elements (as defined by the comparison) to the front
--   of the array in no particular order.
selectBy :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()

-- | Moves the least k elements in the interval [l,u) to the positions
--   [l,k+l) in no particular order.
selectByBounds :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()

-- | Moves the least k elements to the front of the array, sorted.
partialSort :: (UA e, Ord e) => MUArr e s -> Int -> ST s ()

-- | Moves the least k elements (as defined by the comparison) to the front
--   of the array, sorted.
partialSortBy :: (UA e) => Comparison e -> MUArr e s -> Int -> ST s ()

-- | Moves the least k elements in the interval [l,u) to the positions
--   [l,k+l), sorted.
partialSortByBounds :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()


-- | 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.Array.Vector.Algorithms.Merge

-- | Sorts an array using the default comparison.
sort :: (Ord e, UA e) => MUArr e s -> ST s ()

-- | Sorts an array using a custom comparison.
sortBy :: (UA e) => Comparison e -> MUArr e s -> ST s ()

-- | Sorts a portion of an array [l,u) using a custom comparison.
sortByBounds :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> ST s ()


-- | The purpose of this module is to apply the algorithms on mutable
--   arrays in other packages to immutable arrays. The idea is to copy the
--   immutable array into a mutable intermediate, perform the algorithm on
--   the mutable array, and freeze it, yielding a new immutable array.
module Data.Array.Vector.Algorithms.Immutable

-- | Safely applies a mutable array algorithm to an immutable array.
apply :: (UA e) => (forall s. MUArr e s -> ST s ()) -> UArr e -> UArr e