sSA      !"#$%&'()*+,-./0123456789:;<=>? @ (c) 2008-2011 Dan DoelDan Doel ExperimentalPortableNone3=K9A type of comparisons between two values of a given type.ABCABCABC(c) 2008-2011 Dan DoelDan Doel <dan.doel@gmail.com> Experimental3Non-portable (scoped type variables, bang patterns)None=JKM5The number of passes necessary to sort an array of esThe size of an auxiliary array4The radix function parameterized by the current pass+Sorts an array based on the Radix instance.CRadix 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.the number of passesthe size of auxiliary arraysthe radix functionthe array to be sortedDEFGHIJKLMNOPQRDEFGHIJKLMNOPQR((c) 2009-2015 Dan Doel, 2015 Tim BaumannDan Doel <dan.doel@gmail.com> ExperimentalNon-portable (bang patterns)None=KFinds an index in a given sorted vector at which the given element could be inserted while maintaining the sortedness of the vector.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. 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. Finds the lowest index in a given sorted vector at which the given element could be inserted while maintaining the sortedness. 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. 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. }Finds the greatest index in a given sorted vector at which the given element could be inserted while maintaining sortedness.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.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.Given a predicate that is guaraneteed 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.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).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.MBegins searching at the start of the vector, in increasing steps of size 2^n.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.KBegins searching at the end of the vector, in increasing steps of size 2^n.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.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. lulu   (c) 2008-2010 Dan DoelDan Doel ExperimentalPortableNone$Sorts the elements at the positions off8 and 'off + 1' in the given array using the comparison.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 lower of the two.CSorts the three elements starting at the given offset in the array.Sorts the elements at the three given indices. The indices are assumed to be given from lowest to highest, so if 'l < m < u' then 'sort3ByIndex cmp a m l u' essentially sorts the median of three into the lowest position in the array.0Sorts the four elements beginning at the offset.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.(c) 2008-2010 Dan DoelDan Doel ExperimentalPortableNone=K?Sorts an entire array using the default comparison for the type.Sorts an entire array using a given comparison0Sorts the portion of an array delimited by [l,u)eSorts the portion of the array delimited by [l,u) under the assumption that [l,m) is already sorted.SS(c) 2011 Dan DoelDan Doel <dan.doel@gmail.com> Experimental4Non-portable (FlexibleContexts, ScopedTypeVariables)None3=KM qThe methods of this class specify the information necessary to sort arrays using the default ordering. The name  b is meant to convey that index should return results in a similar way to indexing into a string.!pGiven a representative of a stripe and an index number, this function should determine whether to stop sorting."5The size of the bucket array necessary for sorting es#SDetermines which bucket a given element should inhabit for a particular iteration.$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.%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. !"#$%,a comparison for the insertion sort flalback'determines whether a stripe is completethe number of buckets necessarythe big-endian radix functionthe array to be sortedTUVWXYZ[\]^_`abc !"#$%$% !"# !"#$%TUVWXYZ[\]^_`abc((c) 2013-2015 Dan Doel, 2015 Tim BaumannDan Doel <dan.doel@gmail.com> ExperimentalNon-portable (bang patterns)None &,Sorts an array using the default comparison.')Sorts an array using a custom comparison.dComputes the minimum run size for the sort. The goal is to choose a size such that there are almost if not exactly 2^n chunks of that size in the array.eIdentify the next run (that is a monotonically increasing or strictly decreasing sequence) in the slice [l,u) in vec. Returns the order and length of the run.fTests if a temporary buffer has a given size. If not, allocates a new buffer and returns it instead of the old temporary buffer.gCopy the slice [i,i+len) from vec to tmpBuf. If tmpBuf is not large enough, a new buffer is allocated and used. Returns the buffer.hlNumber of consecutive times merge chooses the element from the same run before galloping mode is activated.iMerge the adjacent sorted slices [l,m) and [m,u) in vec. This is done by copying the slice [l,m) to a temporary buffer. Returns the (enlarged) temporary buffer.jMerge the adjacent sorted slices [l,m) and [m,u) in vec. This is done by copying the slice [j,k) to a temporary buffer. Returns the (enlarged) temporary buffer.kMerge the adjacent sorted slices A=[l,m) and B=[m,u) in vec. This begins with galloping searches to find the index of vec[m] in A and the index of vec[m-1] in B to reduce the sizes of A and B. Then it uses j or iQ depending on whether A or B is larger. Returns the (enlarged) temporary buffer. lmn&'delufgilenvectmpBufhiveclmutmpBufjveclmutmpBufkveclmutmpBuf&'&' lnm&'defghijk(c) 2008-2015 Dan DoelDan Doel <dan.doel@gmail.com> ExperimentalNon-portable (type operators)None=JK(1Sorts an entire array using the default ordering.).Sorts an entire array using a custom ordering.*9Sorts a portion of an array [l,u) using a custom ordering+dMoves the lowest k elements to the front of the array. The elements will be in no particular order.,Moves the lowest (as defined by the comparison) k elements to the front of the array. The elements will be in no particular order.- Moves the lowestx k elements in the portion [l,u) of the array into the positions [l,k+l). The elements will be in no particular order..>Moves the lowest k elements to the front of the array, sorted.AThe remaining values of the array will be in no particular order./^Moves the lowest k elements (as defined by the comparison) to the front of the array, sorted.AThe remaining values of the array will be in no particular order.0^Moves the lowest k elements in the portion [l,u) of the array into positions [l,k+l), sorted.qThe remaining values in [l,u) will be in no particular order. Values outside the range [l,u) will be unaffected.1LConstructs a heap in a portion of an array [l, u), using the values therein.Note: 1w is more efficient than constructing a heap by repeated insertion. Repeated insertion has complexity O(n*log n) while 1U is able to construct a heap in O(n), where n is the number of elements in the heap.2{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.3Given 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.4Given 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.5Given 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].bNote: it is best to only use this operation when incremental construction of a heap is required. 1] is capable of building a heap in O(n) time, while repeated insertion takes O(n*log n) time.()*lower index, lupper index, u+number of elements to select, k,number of elements to select, k-number of elements to select, klower index, lupper index, u.number of elements to sort, k/number of elements to sort, k0number of elements to sort, klower index, lupper index, u1lower index, lupper index, u2lower heap index, lupper heap index, u3lower heap index, lupper heap index, uindex to pop to, t4lower heap index, l&lower bound of final sorted portion, mupper heap index, u5lower heap index, lupper heap index, uelement to be inserted, eop()*+,-./012345()*+,-./012345()*+,-./012345op(c) 2008-2015 Dan DoelDan Doel <dan.doel@gmail.com> Experimental,Non-portable (type operators, bang patterns)None=JKM 61Sorts an entire array using the default ordering.7.Sorts an entire array using a custom ordering.89Sorts a portion of an array [l,u) using a custom ordering9MMoves the least k elements to the front of the array in no particular order.:lMoves the least k elements (as defined by the comparison) to the front of the array in no particular order.;bMoves the least k elements in the interval [l,u) to the positions [l,k+l) in no particular order.<=Moves the least k elements to the front of the array, sorted.=]Moves the least k elements (as defined by the comparison) to the front of the array, sorted.>SMoves the least k elements in the interval [l,u) to the positions [l,k+l), sorted. 678lower index, lupper index, uq9number of elements to select, k:number of elements to select, k;number of elements to select, klower bound, lupper bound, u<number of elements to sort, k=number of elements to sort, k>number of elements to sort, klower index, lupper index, urst 6789:;<=> 6789:;<=> 678q9:;<=>rst (c) 2008-2011 Dan DoelDan Doel <dan.doel@gmail.com> ExperimentalPortableNone=K?,Sorts an array using the default comparison.@)Sorts an array using a custom comparison.?@uvw?@?@?@uvwx     !"#$%&'()*+',-./0123456',-./01   7 8 9:;<=>?@ABCDEFGHIJ<KLMNOPQRSTUVWXYZ[\]^_`abcdefghM i ` Mjvector-algorithms-0.7.0.1Data.Vector.Algorithms.SearchData.Vector.Algorithms.RadixData.Vector.Algorithms.Optimal Data.Vector.Algorithms.Insertion#Data.Vector.Algorithms.AmericanFlagData.Vector.Algorithms.TimData.Vector.Algorithms.HeapData.Vector.Algorithms.IntroData.Vector.Algorithms.MergeData.Vector.Algorithms.Common ComparisonRadixpassessizeradixsortsortBy binarySearchbinarySearchBybinarySearchByBounds binarySearchLbinarySearchLBybinarySearchLByBounds binarySearchRbinarySearchRBybinarySearchRByBounds binarySearchPbinarySearchPBoundsgallopingSearchLeftPgallopingSearchRightPgallopingSearchLeftPBoundsgallopingSearchRightPBounds sort2ByOffset sort2ByIndex sort3ByOffset sort3ByIndex sort4ByOffset sort4ByIndex sortByBounds sortByBounds' Lexicographic terminateindexselectselectByselectByBounds partialSort partialSortBypartialSortByBoundsheapifypoppopTosortHeap heapInsert copyOffsetinc countLoop radixLoopbody accumulatemoveLoop $fRadix(,) $fRadixWord64 $fRadixWord32 $fRadixWord16 $fRadixWord8 $fRadixWord $fRadixInt64 $fRadixInt32 $fRadixInt16 $fRadixInt8 $fRadixIntinsertflagLooppermute countStripe threshold$fLexicographicByteString$fLexicographicInt$fLexicographicInt64$fLexicographicInt32$fLexicographicInt16$fLexicographicInt8$fLexicographicWord$fLexicographicWord64$fLexicographicWord32$fLexicographicWord16$fLexicographicWord8minrunnextRunensureCapacity cloneSlice minGallopmergeLomergeHimergeOrder Descending Ascending siftByOffset maximumChild introsort partitionByilgmergeSortWithBuf