-- 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.2


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

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

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

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

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


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

-- | 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 :: (UA e) => Int -> Int -> (Int -> e -> Int) -> 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 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


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

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

-- | Uses a function to compute a key for each element which the algorithm
--   should use in lieu of the actual element. For instance:
--   
--   <pre>
--   usingKeys sortBy f arr
--   </pre>
--   
--   should produce the same results as:
--   
--   <pre>
--   sortBy (comparing f) arr
--   </pre>
--   
--   the difference being that usingKeys computes each key only once which
--   can be more efficient for expensive key functions.
usingKeys :: (UA e, UA k, Ord k) => (forall e'. (UA e') => Comparison e' -> MUArr e' s -> ST s ()) -> (e -> k) -> MUArr e s -> ST s ()

-- | As usingKeys, only the key function has access to the array index at
--   which each element is stored.
usingIxKeys :: (UA e, UA k, Ord k) => (forall e'. (UA e') => Comparison e' -> MUArr e' s -> ST s ()) -> (Int -> e -> k) -> MUArr e s -> ST s ()