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


-- | Sort primitive arrays
--   
--   This library provides a stable sorting algorithm for primitive arrays.
--   
--   The algorithm currently uses mergesort on large chunks and switches to
--   insertion sort on small chunks. The are also novel improvements to
--   increase the performance if the input array is already mostly sorted.
@package primitive-sort
@version 0.1.2.0


-- | Sort primitive arrays with a stable sorting algorithm. All functions
--   in this module are marked as <tt>INLINABLE</tt>, so they will
--   specialize when used in a monomorphic setting.
module Data.Primitive.Sort

-- | Sort an immutable array. Duplicate elements are preserved.
--   
--   <pre>
--   &gt;&gt;&gt; sort ([5,6,7,9,5,4,5,7] :: Array Int)
--   fromListN 8 [4,5,5,5,6,7,7,9]
--   </pre>
sort :: (Prim a, Ord a) => PrimArray a -> PrimArray a

-- | Sort an immutable array. Only a single copy of each duplicated element
--   is preserved.
--   
--   <pre>
--   &gt;&gt;&gt; sortUnique ([5,6,7,9,5,4,5,7] :: Array Int)
--   fromListN 5 [4,5,6,7,9]
--   </pre>
sortUnique :: (Prim a, Ord a) => PrimArray a -> PrimArray a

-- | Sort a tagged immutable array. Each element from the <tt>keys</tt>
--   array is paired up with an element from the <tt>values</tt> array at
--   the matching index. The sort permutes the <tt>values</tt> array so
--   that a value end up in the same position as its corresponding key. The
--   two argument array should be of the same length, but if one is shorter
--   than the other, the longer one will be truncated so that the lengths
--   match.
--   
--   <pre>
--   &gt;&gt;&gt; sortTagged ([5,6,7,5,5,7] :: Array Int) ([1,2,3,4,5,6] :: Array Int)
--   (fromListN 6 [5,5,5,6,7,7],fromListN 6 [1,4,5,2,3,6])
--   </pre>
--   
--   Since the sort is stable, the values corresponding to a key that
--   appears multiple times have their original order preserved.
sortTagged :: forall k v karr varr. (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v) => karr k -> varr v -> (karr k, varr v)

-- | Sort a tagged immutable array. Only a single copy of each duplicate
--   key is preserved, along with the last value from <tt>values</tt> that
--   corresponded to it. The two argument arrays should be of the same
--   length, but if one is shorter than the other, the longer one will be
--   truncated so that the lengths match.
--   
--   <pre>
--   &gt;&gt;&gt; sortUniqueTagged ([5,6,7,5,5,7] :: Array Int) ([1,2,3,4,5,6] :: Array Int)
--   (fromListN 3 [5,6,7],fromListN 3 [5,2,6])
--   </pre>
sortUniqueTagged :: forall k v karr varr. (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v) => karr k -> varr v -> (karr k, varr v)

-- | Sort the mutable array. This operation preserves duplicate elements.
--   The argument may either be modified in-place, or another array may be
--   allocated and returned. The argument may not be reused after being
--   passed to this function.
sortMutable :: (Prim a, Ord a) => MutablePrimArray s a -> ST s (MutablePrimArray s a)

-- | Sort an immutable array. Only a single copy of each duplicated element
--   is preserved. This operation may run in-place, or it may need to
--   allocate a new array, so the argument may not be reused after this
--   function is applied to it.
sortUniqueMutable :: forall s a. (Prim a, Ord a) => MutablePrimArray s a -> ST s (MutablePrimArray s a)

-- | Sort an array of a key type <tt>k</tt>, rearranging the values of type
--   <tt>v</tt> according to the element they correspond to in the key
--   array. The argument arrays may not be reused after they are passed to
--   the function.
sortTaggedMutable :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v) => Mutable karr s k -> Mutable varr s v -> ST s (Mutable karr s k, Mutable varr s v)
sortUniqueTaggedMutable :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v) => Mutable karr s k -> Mutable varr s v -> ST s (Mutable karr s k, Mutable varr s v)