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


-- | Efficient algorithms for sorting vector arrays. At some stage other
--   vector algorithms may be added.
@package vector-algorithms
@version 0.9.1.0


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

-- | A variant on <a>sort</a> that returns a vector of unique elements.
sortUniq :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m (v (PrimState m) e)

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

-- | A variant on <a>sortBy</a> which returns a vector of unique elements.
sortUniqBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m (v (PrimState m) e)

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

-- | A variant on <a>sort</a> that returns a vector of unique elements.
sortUniq :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m (v (PrimState m) e)

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

-- | A variant on <a>sortBy</a> which returns a vector of unique elements.
sortUniqBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m (v (PrimState m) e)

-- | 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 :: forall e m v. (PrimMonad m, MVector v e, Lexicographic e, Ord e) => v (PrimState m) e -> m ()

-- | A variant on <a>sort</a> that returns a vector of unique elements.
sortUniq :: forall e m v. (PrimMonad m, MVector v e, Lexicographic e, Ord e) => v (PrimState m) e -> m (v (PrimState m) e)

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

-- | A variant on <a>sortBy</a> which returns a vector of unique elements.
sortUniqBy :: (PrimMonad m, MVector v e) => Comparison e -> (e -> Int -> Bool) -> Int -> (Int -> e -> Int) -> v (PrimState m) e -> m (v (PrimState m) e)

-- | Given a representative of a stripe and an index number, this function
--   determines whether to stop sorting.
terminate :: Lexicographic e => e -> Int -> Bool

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

-- | Computes the length of a representative of a stripe. It should take
--   <tt>n</tt> passes to sort values of extent <tt>n</tt>. The extent may
--   not be uniform across all values of the type.
extent :: Lexicographic e => e -> Int

-- | The size of the bucket array necessary for sorting es
size :: Lexicographic e => Proxy e -> Int

-- | Determines which bucket a given element should inhabit for a
--   particular iteration.
index :: Lexicographic e => Int -> e -> Int
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic Data.ByteString.Internal.Type.ByteString
instance (Data.Vector.Algorithms.AmericanFlag.Lexicographic a, Data.Vector.Algorithms.AmericanFlag.Lexicographic b) => Data.Vector.Algorithms.AmericanFlag.Lexicographic (GHC.Internal.Data.Either.Either a b)
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Types.Int
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Internal.Int.Int16
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Internal.Int.Int32
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Internal.Int.Int64
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Internal.Int.Int8
instance (Data.Vector.Algorithms.AmericanFlag.Lexicographic a, Data.Vector.Algorithms.AmericanFlag.Lexicographic b) => Data.Vector.Algorithms.AmericanFlag.Lexicographic (a, b)
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Types.Word
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Internal.Word.Word16
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Internal.Word.Word32
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Internal.Word.Word64
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Internal.Word.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 ()

-- | A variant on <a>sort</a> that returns a vector of unique elements.
sortUniq :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m (v (PrimState m) e)

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

-- | A variant on <a>sortBy</a> which returns a vector of unique elements.
sortUniqBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m (v (PrimState m) e)

-- | 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 lowest (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.
--   
--   The remaining values of the array will be in no particular order.
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.
--   
--   The remaining values of the array will be in no particular order.
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.
--   
--   The remaining values in [l,u) will be in no particular order. Values
--   outside the range [l,u) will be unaffected.
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), using the values
--   therein.
--   
--   Note: <a>heapify</a> is more efficient than constructing a heap by
--   repeated insertion. Repeated insertion has complexity O(n*log n) while
--   <a>heapify</a> is able to construct a heap in O(n), where n is the
--   number of elements in the heap.
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 ()

-- | Given a heap stored in a portion of an array [l,u) and an element e,
--   inserts the element into the heap, resulting in a heap in [l,u].
--   
--   Note: it is best to only use this operation when incremental
--   construction of a heap is required. <a>heapify</a> is capable of
--   building a heap in O(n) time, while repeated insertion takes O(n*log
--   n) time.
heapInsert :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> e -> 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 ()

-- | A variant on <a>sort</a> that returns a vector of unique elements.
sortUniq :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m (v (PrimState m) e)

-- | A variant on <a>sortBy</a> which returns a vector of unique elements.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()

-- | Sorts an entire array using a custom ordering returning a vector of
--   the unique elements.
sortUniqBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m (v (PrimState m) e)

-- | 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 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;. 255
--   </pre>
module Data.Vector.Algorithms.Radix

-- | Sorts an array based on the Radix instance.
sort :: forall e m v. (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

-- | The number of passes necessary to sort an array of es
passes :: Radix e => e -> Int

-- | The size of an auxiliary array
size :: Radix e => e -> Int

-- | The radix function parameterized by the current pass
radix :: Radix e => Int -> e -> Int
instance Data.Vector.Algorithms.Radix.Radix GHC.Types.Int
instance Data.Vector.Algorithms.Radix.Radix GHC.Internal.Int.Int16
instance Data.Vector.Algorithms.Radix.Radix GHC.Internal.Int.Int32
instance Data.Vector.Algorithms.Radix.Radix GHC.Internal.Int.Int64
instance Data.Vector.Algorithms.Radix.Radix GHC.Internal.Int.Int8
instance (Data.Vector.Algorithms.Radix.Radix i, Data.Vector.Algorithms.Radix.Radix j) => Data.Vector.Algorithms.Radix.Radix (i, j)
instance Data.Vector.Algorithms.Radix.Radix GHC.Types.Word
instance Data.Vector.Algorithms.Radix.Radix GHC.Internal.Word.Word16
instance Data.Vector.Algorithms.Radix.Radix GHC.Internal.Word.Word32
instance Data.Vector.Algorithms.Radix.Radix GHC.Internal.Word.Word64
instance Data.Vector.Algorithms.Radix.Radix GHC.Internal.Word.Word8


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

-- | Given a predicate that is guaranteed to be monotone on the given
--   vector, finds the first index at which the predicate returns True, or
--   the length of the array if the predicate is false for the entire
--   array.
binarySearchP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int

-- | Given a predicate that is guaranteed to be monotone on the indices
--   [l,u) in a given vector, finds the index in [l,u] at which the
--   predicate turns from False to True (yielding u if the entire interval
--   is False).
binarySearchPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> Int -> Int -> m Int

-- | Given a predicate that is guaranteed to be monotone on the vector
--   elements in order, finds the index at which the predicate turns from
--   False to True. The length of the vector is returned if the predicate
--   is False for the entire vector.
--   
--   Begins searching at the start of the vector, in increasing steps of
--   size 2^n.
gallopingSearchLeftP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int

-- | Given a predicate that is guaranteed to be monotone on the indices
--   [l,u) in a given vector, finds the index in [l,u] at which the
--   predicate turns from False to True (yielding u if the entire interval
--   is False). Begins searching at l, going right in increasing
--   (2^n)-steps.
gallopingSearchLeftPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> Int -> Int -> m Int

-- | Given a predicate that is guaranteed to be monotone on the vector
--   elements in order, finds the index at which the predicate turns from
--   False to True. The length of the vector is returned if the predicate
--   is False for the entire vector.
--   
--   Begins searching at the end of the vector, in increasing steps of size
--   2^n.
gallopingSearchRightP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int

-- | Given a predicate that is guaranteed to be monotone on the indices
--   [l,u) in a given vector, finds the index in [l,u] at which the
--   predicate turns from False to True (yielding u if the entire interval
--   is False). Begins searching at u, going left in increasing
--   (2^n)-steps.
gallopingSearchRightPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> Int -> Int -> m Int

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

module Data.Vector.Algorithms

-- | The <a>nub</a> function which removes duplicate elements from a
--   vector.
nub :: (Vector v e, Ord e) => v e -> v e

-- | A version of <a>nub</a> with a custom comparison predicate.
--   
--   <i>Note:</i> This function makes use of <tt>sortByUniq</tt> using the
--   intro sort algorithm.
nubBy :: Vector v e => Comparison e -> v e -> v e

-- | The <a>nubByMut</a> function takes in an in-place sort algorithm and
--   uses it to do a de-deduplicated sort. It then uses this to remove
--   duplicate elements from the input.
--   
--   <i>Note:</i> Since this algorithm needs the original input and so
--   copies before sorting in-place. As such, it is safe to use on
--   immutable inputs.
nubByMut :: (PrimMonad m, MVector v e) => (Comparison e -> v (PrimState m) e -> m (v (PrimState m) e)) -> Comparison e -> v (PrimState m) e -> m (v (PrimState m) e)


-- | Timsort is a complex, adaptive, bottom-up merge sort. It is designed
--   to minimize comparisons as much as possible, even at some cost in
--   overhead. Thus, it may not be ideal for sorting simple primitive
--   types, for which comparison is cheap. It may, however, be
--   significantly faster for sorting arrays of complex values (strings
--   would be an example, though an algorithm not based on comparison would
--   probably be superior in that particular case).
--   
--   For more information on the details of the algorithm, read on.
--   
--   The first step of the algorithm is to identify runs of elements. These
--   can either be non-decreasing or strictly decreasing sequences of
--   elements in the input. Strictly decreasing sequences are used rather
--   than non-increasing so that they can be easily reversed in place
--   without the sort becoming unstable.
--   
--   If the natural runs are too short, they are padded to a minimum value.
--   The minimum is chosen based on the length of the array, and padded
--   runs are put in order using insertion sort. The length of the minimum
--   run size is determined as follows:
--   
--   <ul>
--   <li>If the length of the array is less than 64, the minimum size is
--   the length of the array, and insertion sort is used for the
--   entirety</li>
--   <li>Otherwise, a value between 32 and 64 is chosen such that N/min is
--   either equal to or just below a power of two. This avoids having a
--   small chunk left over to merge into much larger chunks at the
--   end.</li>
--   </ul>
--   
--   This is accomplished by taking the the mininum to be the lowest six
--   bits containing the highest set bit, and adding one if any other bits
--   are set. For instance:
--   
--   length: 00000000 00000000 00000000 00011011 = 25 min: 00000000
--   00000000 00000000 00011011 = 25
--   
--   length: 00000000 11111100 00000000 00000000 = 63 * 2^18 min: 00000000
--   00000000 00000000 00111111 = 63
--   
--   length: 00000000 11111100 00000000 00000001 = 63 * 2^18 + 1 min:
--   00000000 00000000 00000000 01000000 = 64
--   
--   Once chunks can be produced, the next step is merging them. The
--   indices of all runs are stored in a stack. When we identify a new run,
--   we push it onto the stack. However, certain invariants are maintained
--   of the stack entries. Namely:
--   
--   if stk = _ :&gt; z :&gt; y :&gt; x length x + length y &lt; length z
--   
--   if stk = _ :&gt; y :&gt; x length x &lt; length y
--   
--   This ensures that the chunks stored are decreasing, and that the chunk
--   sizes follow something like the fibonacci sequence, ensuring there at
--   most log-many chunks at any time. If pushing a new chunk on the stack
--   would violate either of the invariants, we first perform a merge.
--   
--   If length x + length y &gt;= length z, then y is merged with the
--   smaller of x and z (if they are tied, x is chosen, because it is more
--   likely to be cached). If, further, length x &gt;= length y then they
--   are merged. These steps are repeated until the invariants are
--   established.
--   
--   The last important piece of the algorithm is the merging. At first,
--   two chunks are merged element-wise. However, while doing so, counts
--   are kept of the number of elements taken from one chunk without any
--   from its partner. If this count exceeds a threshold, the merge
--   switches to searching for elements from one chunk in the other, and
--   copying chunks at a time. If these chunks start falling below the
--   threshold, the merge switches back to element-wise.
--   
--   The search used in the merge is also special. It uses a galloping
--   strategy, where exponentially increasing indices are tested, and once
--   two such indices are determined to bracket the desired value, binary
--   search is used to find the exact index within that range. This is
--   asymptotically the same as simply using binary search, but is likely
--   to do fewer comparisons than binary search would.
--   
--   One aspect that is not yet implemented from the original Tim sort is
--   the adjustment of the above threshold. When galloping saves time, the
--   threshold is lowered, and when it doesn't, it is raised. This may be
--   implemented in the future.
module Data.Vector.Algorithms.Tim

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

-- | A variant on <a>sort</a> that returns a vector of unique elements.
sortUniq :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m (v (PrimState m) e)

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

-- | A variant on <a>sortBy</a> which returns a vector of unique elements.
sortUniqBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m (v (PrimState m) e)
instance GHC.Classes.Eq Data.Vector.Algorithms.Tim.Order
instance GHC.Internal.Show.Show Data.Vector.Algorithms.Tim.Order
