diff options
Diffstat (limited to 'include/EASTL/sort.h')
| -rw-r--r-- | include/EASTL/sort.h | 2022 |
1 files changed, 0 insertions, 2022 deletions
diff --git a/include/EASTL/sort.h b/include/EASTL/sort.h deleted file mode 100644 index fb1c6e5..0000000 --- a/include/EASTL/sort.h +++ /dev/null @@ -1,2022 +0,0 @@ -/////////////////////////////////////////////////////////////////////////////// -// Copyright (c) Electronic Arts Inc. All rights reserved. -////////////////////////////////////////////////////////////////////////////// - -////////////////////////////////////////////////////////////////////////////// -// This file implements sorting algorithms. Some of these are equivalent to -// std C++ sorting algorithms, while others don't have equivalents in the -// C++ standard. We implement the following sorting algorithms: -// is_sorted -- -// sort -- Unstable. The implementation of this is mapped to quick_sort by default. -// quick_sort -- Unstable. This is actually an intro-sort (quick sort with switch to insertion sort). -// tim_sort -- Stable. -// tim_sort_buffer -- Stable. -// partial_sort -- Unstable. -// insertion_sort -- Stable. -// shell_sort -- Unstable. -// heap_sort -- Unstable. -// stable_sort -- Stable. The implementation of this is simply mapped to merge_sort. -// merge -- -// merge_sort -- Stable. -// merge_sort_buffer -- Stable. -// nth_element -- Unstable. -// radix_sort -- Stable. Important and useful sort for integral data, and faster than all others for this. -// comb_sort -- Unstable. Possibly the best combination of small code size but fast sort. -// bubble_sort -- Stable. Useful in practice for sorting tiny sets of data (<= 10 elements). -// selection_sort* -- Unstable. -// shaker_sort* -- Stable. -// bucket_sort* -- Stable. -// -// * Found in sort_extra.h. -// -// Additional sorting and related algorithms we may want to implement: -// partial_sort_copy This would be like the std STL version. -// paritition This would be like the std STL version. This is not categorized as a sort routine by the language standard. -// stable_partition This would be like the std STL version. -// counting_sort Maybe we don't want to implement this. -// -////////////////////////////////////////////////////////////////////////////// - - -#ifndef EASTL_SORT_H -#define EASTL_SORT_H - - -#include <EASTL/internal/config.h> -#include <EASTL/internal/move_help.h> -#include <EASTL/iterator.h> -#include <EASTL/memory.h> -#include <EASTL/algorithm.h> -#include <EASTL/functional.h> -#include <EASTL/heap.h> -#include <EASTL/allocator.h> -#include <EASTL/memory.h> - - -#if defined(EA_PRAGMA_ONCE_SUPPORTED) - #pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result. -#endif - - -// EASTL_PLATFORM_PREFERRED_ALIGNMENT -// -// Allows for slightly faster buffers in some cases. -// -#if !defined(EASTL_PLATFORM_PREFERRED_ALIGNMENT) - #if defined(EA_PROCESSOR_ARM) - #define EASTL_PLATFORM_PREFERRED_ALIGNMENT 8 - #else - #define EASTL_PLATFORM_PREFERRED_ALIGNMENT 16 - #endif -#endif - - -namespace eastl -{ - - /// is_sorted - /// - /// Returns true if the range [first, last) is sorted. - /// An empty range is considered to be sorted. - /// To test if a range is reverse-sorted, use 'greater' as the comparison - /// instead of 'less'. - /// - /// Example usage: - /// vector<int> intArray; - /// bool bIsSorted = is_sorted(intArray.begin(), intArray.end()); - /// bool bIsReverseSorted = is_sorted(intArray.begin(), intArray.end(), greater<int>()); - /// - template <typename ForwardIterator, typename StrictWeakOrdering> - bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare) - { - if(first != last) - { - ForwardIterator current = first; - - for(++current; current != last; first = current, ++current) - { - if(compare(*current, *first)) - { - EASTL_VALIDATE_COMPARE(!compare(*first, *current)); // Validate that the compare function is sane. - return false; - } - } - } - return true; - } - - template <typename ForwardIterator> - inline bool is_sorted(ForwardIterator first, ForwardIterator last) - { - typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less; - - return eastl::is_sorted<ForwardIterator, Less>(first, last, Less()); - } - - - - /// is_sorted_until - /// - /// Returns an iterator to the first element in the range [first,last) which does not follow an ascending order. - /// The range between first and the iterator returned is sorted. - /// If the entire range is sorted, the function returns last. - /// The elements are compared using operator< for the first version, and comp for the second. - /// - /// Example usage: - /// vector<int> intArray; - /// vector<int>::iterator unsorted_element = is_sorted_until(eastl::end(intArray), eastl::end(intArray)); - /// vector<int>::iterator unsorted_element_with_user_compare = is_sorted_until(eastl::end(intArray), eastl::end(intArray), eastl::less<int>()); - /// - template<typename ForwardIterator> - ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last) - { - if(first != last) - { - ForwardIterator next = first; - - while(++next != last) - { - if(*next < *first) - return next; - - first = next; - } - } - - return last; - } - - template<typename ForwardIterator, typename Compare> - ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare compare) - { - if(first != last) - { - ForwardIterator next = first; - - while(++next != last) - { - if(compare(*next, *first)) - return next; - - first = next; - } - } - - return last; - } - - - - /// merge - /// - /// This function merges two sorted input sorted ranges into a result sorted range. - /// This merge is stable in that no element from the first range will be changed - /// in order relative to other elements from the first range. - /// - template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare> - OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare compare) - { - while((first1 != last1) && (first2 != last2)) - { - if(compare(*first2, *first1)) - { - EASTL_VALIDATE_COMPARE(!compare(*first1, *first2)); // Validate that the compare function is sane. - *result = *first2; - ++first2; - } - else - { - *result = *first1; - ++first1; - } - ++result; - } - - // Check which list is empty and explicitly copy remaining items from the other list. - // For performance reasons, only a single copy operation is invoked to avoid the potential overhead - // introduced by chaining two copy operations together. Even if a copy is of zero size there can - // be overhead from calling memmove with a zero size copy. - if (first1 == last1) - { - return eastl::copy(first2, last2, result); - } - else - { - return eastl::copy(first1, last1, result); - } - } - - template <typename InputIterator1, typename InputIterator2, typename OutputIterator> - inline OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) - { - typedef eastl::less<typename eastl::iterator_traits<InputIterator1>::value_type> Less; - - return eastl::merge<InputIterator1, InputIterator2, OutputIterator, Less> - (first1, last1, first2, last2, result, Less()); - } - - - ////////////////////////////////////////////////////////////////////////////// - /// insertion_sort - /// - /// insertion_sort is an O(n^2) stable sorting algorithm that starts at the - /// (k + 1) element and assumes the first (k) elements are sorted. - /// Then copy_backwards from (k + 1) to the begining any elements where the - /// (k + 1) element is less than [0, k] elements. The position of k when - /// (k + 1) element is not less than k is the sorted position of the (k + 1) element. - /// - /// Example With Intermediate Steps: - /// (k + 1) == 2 : [3, 2, 1] -> [3, 3, 1] -> [2, 3, 1] - /// (k + 1) == 1 : [2, 3, 1] -> [2, 3, 3] -> [2, 2, 3] -> [1, 2, 3] - /// : [1, 2, 3] - template <typename BidirectionalIterator, typename StrictWeakOrdering> - void insertion_sort(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering compare) - { - typedef typename eastl::iterator_traits<BidirectionalIterator>::value_type value_type; - - if (first != last) - { - BidirectionalIterator i = first; - - for (++i; i != last; ++i) - { - value_type insertValue(eastl::move(*i)); - BidirectionalIterator insertPosition = i; - - for (BidirectionalIterator movePosition = i; movePosition != first && compare(insertValue, *(--movePosition)); --insertPosition) - { - EASTL_VALIDATE_COMPARE(!compare(*movePosition, insertValue)); - *insertPosition = eastl::move(*movePosition); - } - - *insertPosition = eastl::move(insertValue); - } - } - } // insertion_sort - - - template <typename BidirectionalIterator> - void insertion_sort(BidirectionalIterator first, BidirectionalIterator last) - { - typedef eastl::less<typename eastl::iterator_traits<BidirectionalIterator>::value_type> Less; - - insertion_sort<BidirectionalIterator>(first, last, Less()); - - } // insertion_sort - - - /// shell_sort - /// - /// Implements the ShellSort algorithm. This algorithm is a serious algorithm for larger - /// data sets, as reported by Sedgewick in his discussions on QuickSort. Note that shell_sort - /// requires a random access iterator, which usually means an array (eg. vector, deque). - /// ShellSort has good performance with presorted sequences. - /// The term "shell" derives from the name of the inventor, David Shell. - /// - /// To consider: Allow the user to specify the "h-sequence" array. - /// - template <typename RandomAccessIterator, typename StrictWeakOrdering> - void shell_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering compare) - { - typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type; - - // We use the Knuth 'h' sequence below, as it is easy to calculate at runtime. - // However, possibly we are better off using a different sequence based on a table. - // One such sequence which averages slightly better than Knuth is: - // 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, - // 64769, 146305, 260609, 587521, 1045505, 2354689, 4188161, 9427969, 16764929 - - if(first != last) - { - RandomAccessIterator iCurrent, iBack, iSorted, iInsertFirst; - difference_type nSize = last - first; - difference_type nSpace = 1; // nSpace is the 'h' value of the ShellSort algorithm. - - while(nSpace < nSize) - nSpace = (nSpace * 3) + 1; // This is the Knuth 'h' sequence: 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, - - for(nSpace = (nSpace - 1) / 3; nSpace >= 1; nSpace = (nSpace - 1) / 3) // Integer division is less than ideal. - { - for(difference_type i = 0; i < nSpace; i++) - { - iInsertFirst = first + i; - - for(iSorted = iInsertFirst + nSpace; iSorted < last; iSorted += nSpace) - { - iBack = iCurrent = iSorted; - - for(; (iCurrent != iInsertFirst) && compare(*iCurrent, *(iBack -= nSpace)); iCurrent = iBack) - { - EASTL_VALIDATE_COMPARE(!compare(*iBack, *iCurrent)); // Validate that the compare function is sane. - eastl::iter_swap(iCurrent, iBack); - } - } - } - } - } - } // shell_sort - - template <typename RandomAccessIterator> - inline void shell_sort(RandomAccessIterator first, RandomAccessIterator last) - { - typedef eastl::less<typename eastl::iterator_traits<RandomAccessIterator>::value_type> Less; - - eastl::shell_sort<RandomAccessIterator, Less>(first, last, Less()); - } - - - - /// heap_sort - /// - /// Implements the HeapSort algorithm. - /// Note that heap_sort requires a random access iterator, which usually means - /// an array (eg. vector, deque). - /// - template <typename RandomAccessIterator, typename StrictWeakOrdering> - void heap_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering compare) - { - // We simply call our heap algorithms to do the work for us. - eastl::make_heap<RandomAccessIterator, StrictWeakOrdering>(first, last, compare); - eastl::sort_heap<RandomAccessIterator, StrictWeakOrdering>(first, last, compare); - } - - template <typename RandomAccessIterator> - inline void heap_sort(RandomAccessIterator first, RandomAccessIterator last) - { - typedef eastl::less<typename eastl::iterator_traits<RandomAccessIterator>::value_type> Less; - - eastl::heap_sort<RandomAccessIterator, Less>(first, last, Less()); - } - - - - namespace Internal - { - // Sorts a range whose initial (start - first) entries are already sorted. - // This function is a useful helper to the tim_sort function. - // This is the same as insertion_sort except that it has a start parameter which indicates - // where the start of the unsorted data is. - template <typename BidirectionalIterator, typename StrictWeakOrdering> - void insertion_sort_already_started(BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator start, StrictWeakOrdering compare) - { - typedef typename eastl::iterator_traits<BidirectionalIterator>::value_type value_type; - - if (first != last) // if the range is non-empty... - { - BidirectionalIterator iCurrent, iNext, iSorted = start - 1; - - for (++iSorted; iSorted != last; ++iSorted) - { - const value_type temp(*iSorted); - - iNext = iCurrent = iSorted; - - for (--iCurrent; (iNext != first) && compare(temp, *iCurrent); --iNext, --iCurrent) - { - EASTL_VALIDATE_COMPARE(!compare(*iCurrent, temp)); // Validate that the compare function is sane. - *iNext = *iCurrent; - } - - *iNext = temp; - } - } - } - } - - - - /// merge_sort_buffer - /// - /// Implements the MergeSort algorithm with a user-supplied buffer. - /// The input buffer must be able to hold a number of items equal to 'last - first'. - /// Note that merge_sort_buffer requires a random access iterator, which usually means - /// an array (eg. vector, deque). - /// - /// The algorithm used for merge sort is not the standard merge sort. It has been modified - /// to improve performance for data that is already partially sorted. In fact, if data - /// is completely sorted, then performance is O(n), but even data with partially sorted - /// regions can benefit from the modifications. - /// - /// 'InsertionSortLimit' specifies a size limit for which the algorithm will use insertion sort. - /// Due to the overhead of merge sort, it is often faster to use insertion sort once the size of a region - /// is fairly small. However, insertion sort is not as efficient (in terms of assignments orcomparisons) - /// so choosing a value that is too large will reduce performance. Generally a value of 16 to 32 is reasonable, - /// but the best choose will depend on the data being sorted. - template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering, typename difference_type, int InsertionSortLimit> - class MergeSorter - { - public: - static void sort(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer, StrictWeakOrdering compare) - { - if (sort_impl(first, last, pBuffer, difference_type(0), compare) == RL_Buffer) - { - const difference_type nCount = last - first; - eastl::copy<T*, RandomAccessIterator>(pBuffer, pBuffer + nCount, first); - } - EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare))); - } - - private: - static_assert(InsertionSortLimit > 1, "Sequences of length 1 are already sorted. Use a larger value for InsertionSortLimit"); - - enum ResultLocation - { - RL_SourceRange, // i.e. result is in the range defined by [first, last) - RL_Buffer, // i.e. result is in pBuffer - }; - - // sort_impl - // - // This sort routine sorts the data in [first, last) and places the result in pBuffer or in the original range of the input. The actual - // location of the data is indicated by the enum returned. - // - // lastSortedEnd is used to specify a that data in the range [first, first + lastSortedEnd] is already sorted. This information is used - // to avoid unnecessary merge sorting of already sorted data. lastSortedEnd is a hint, and can be an under estimate of the sorted elements - // (i.e. it is legal to pass 0). - static ResultLocation sort_impl(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer, difference_type lastSortedEnd, StrictWeakOrdering compare) - { - const difference_type nCount = last - first; - - if (lastSortedEnd < 1) - { - lastSortedEnd = eastl::is_sorted_until<RandomAccessIterator, StrictWeakOrdering>(first, last, compare) - first; - } - - // Sort the region unless lastSortedEnd indicates it is already sorted. - if (lastSortedEnd < nCount) - { - // If the size is less than or equal to InsertionSortLimit use insertion sort instead of recursing further. - if (nCount <= InsertionSortLimit) - { - eastl::Internal::insertion_sort_already_started<RandomAccessIterator, StrictWeakOrdering>(first, last, first + lastSortedEnd, compare); - return RL_SourceRange; - } - else - { - const difference_type nMid = nCount / 2; - - ResultLocation firstHalfLocation = RL_SourceRange; - // Don't sort the first half if it is already sorted. - if (lastSortedEnd < nMid) - { - firstHalfLocation = sort_impl(first, first + nMid, pBuffer, lastSortedEnd, compare); - } - - ResultLocation secondHalfLocation = sort_impl(first + nMid, last, pBuffer + nMid, lastSortedEnd - nMid, compare); - - return merge_halves(first, last, nMid, pBuffer, firstHalfLocation, secondHalfLocation, compare); - } - } - else - { - EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare))); - return RL_SourceRange; - } - } - - // merge_halves - // - // Merge two sorted regions of elements. - // The inputs to this method effectively define two large buffers. The variables 'firstHalfLocation' and 'secondHalfLocation' define where the data to be - // merged is located within the two buffers. It is entirely possible that the two areas to be merged could be entirely located in either of the larger buffers. - // Upon returning the merged results will be in one of the two buffers (indicated by the return result). - static ResultLocation merge_halves(RandomAccessIterator first, RandomAccessIterator last, difference_type nMid, T* pBuffer, ResultLocation firstHalfLocation, ResultLocation secondHalfLocation, StrictWeakOrdering compare) - { - const difference_type nCount = last - first; - if (firstHalfLocation == RL_SourceRange) - { - if (secondHalfLocation == RL_SourceRange) - { - eastl::merge<RandomAccessIterator, RandomAccessIterator, T*, StrictWeakOrdering>(first, first + nMid, first + nMid, last, pBuffer, compare); - EASTL_DEV_ASSERT((eastl::is_sorted<T*, StrictWeakOrdering>(pBuffer, pBuffer + nCount, compare))); - return RL_Buffer; - } - else - { - eastl::copy(first, first + nMid, pBuffer); - eastl::merge<T*, T*, RandomAccessIterator, StrictWeakOrdering>(pBuffer, pBuffer + nMid, pBuffer + nMid, pBuffer + nCount, first, compare); - EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare))); - return RL_SourceRange; - } - } - else - { - if (secondHalfLocation == RL_SourceRange) - { - eastl::copy(first + nMid, last, pBuffer + nMid); - eastl::merge<T*, T*, RandomAccessIterator, StrictWeakOrdering>(pBuffer, pBuffer + nMid, pBuffer + nMid, pBuffer + nCount, first, compare); - EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare))); - return RL_SourceRange; - } - else - { - eastl::merge<T*, T*, RandomAccessIterator, StrictWeakOrdering>(pBuffer, pBuffer + nMid, pBuffer + nMid, pBuffer + nCount, first, compare); - EASTL_DEV_ASSERT((eastl::is_sorted<RandomAccessIterator, StrictWeakOrdering>(first, last, compare))); - return RL_SourceRange; - } - } - } - - }; - - - template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering> - void merge_sort_buffer(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer, StrictWeakOrdering compare) - { - typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type; - MergeSorter<RandomAccessIterator, T, StrictWeakOrdering, difference_type, 16>::sort(first, last, pBuffer, compare); - } - - template <typename RandomAccessIterator, typename T> - inline void merge_sort_buffer(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer) - { - typedef eastl::less<typename eastl::iterator_traits<RandomAccessIterator>::value_type> Less; - - eastl::merge_sort_buffer<RandomAccessIterator, T, Less>(first, last, pBuffer, Less()); - } - - - - /// merge_sort - /// - /// Implements the MergeSort algorithm. - /// This algorithm allocates memory via the user-supplied allocator. Use merge_sort_buffer - /// function if you want a version which doesn't allocate memory. - /// Note that merge_sort requires a random access iterator, which usually means - /// an array (eg. vector, deque). - /// - template <typename RandomAccessIterator, typename Allocator, typename StrictWeakOrdering> - void merge_sort(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator, StrictWeakOrdering compare) - { - typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type; - typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type value_type; - - const difference_type nCount = last - first; - - if(nCount > 1) - { - // We need to allocate an array of nCount value_type objects as a temporary buffer. - value_type* const pBuffer = (value_type*)allocate_memory(allocator, nCount * sizeof(value_type), EASTL_ALIGN_OF(value_type), 0); - eastl::uninitialized_fill(pBuffer, pBuffer + nCount, value_type()); - - eastl::merge_sort_buffer<RandomAccessIterator, value_type, StrictWeakOrdering> - (first, last, pBuffer, compare); - - eastl::destruct(pBuffer, pBuffer + nCount); - EASTLFree(allocator, pBuffer, nCount * sizeof(value_type)); - } - } - - template <typename RandomAccessIterator, typename Allocator> - inline void merge_sort(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator) - { - typedef eastl::less<typename eastl::iterator_traits<RandomAccessIterator>::value_type> Less; - - eastl::merge_sort<RandomAccessIterator, Allocator, Less>(first, last, allocator, Less()); - } - - - - /// partition - /// - /// Implements the partition algorithm. - /// Rearranges the elements in the range [first, last), in such a way that all the elements - /// for which pred returns true precede all those for which it returns false. The iterator - /// returned points to the first element of the second group. - /// The relative ordering within each group is not necessarily the same as before the call. - /// See function stable_partition for a function with a similar behavior and stability in - /// the ordering. - /// - /// To do: Implement a version that uses a faster BidirectionalIterator algorithm for the - /// case that the iterator range is a bidirectional iterator instead of just an - /// input iterator (one direction). - /// - template<typename InputIterator, typename Predicate> - InputIterator partition(InputIterator begin, InputIterator end, Predicate predicate) - { - if(begin != end) - { - while(predicate(*begin)) - { - if(++begin == end) - return begin; - } - - InputIterator middle = begin; - - while(++middle != end) - { - if(predicate(*middle)) - { - eastl::swap(*begin, *middle); - ++begin; - } - } - } - - return begin; - } - - /// stable_partition - /// - /// Performs the same function as @p partition() with the additional - /// guarantee that the relative ordering of elements in each group is - /// preserved. - template <typename ForwardIterator, typename Predicate> - ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred) - { - first = eastl::find_if_not(first, last, pred); - - if (first == last) - return first; - - typedef typename iterator_traits<ForwardIterator>::value_type value_type; - - const auto requested_size = eastl::distance(first, last); - - auto allocator = *get_default_allocator(0); - value_type* const buffer = - (value_type*)allocate_memory(allocator, requested_size * sizeof(value_type), EASTL_ALIGN_OF(value_type), 0); - eastl::uninitialized_fill(buffer, buffer + requested_size, value_type()); - - ForwardIterator result1 = first; - value_type* result2 = buffer; - - *result2 = eastl::move(*first); - ++result2; - ++first; - for (; first != last; ++first) - { - if (pred(*first)) - { - *result1 = eastl::move(*first); - ++result1; - } - else - { - *result2 = eastl::move(*first); - ++result2; - } - } - - eastl::copy(buffer, result2, result1); - - eastl::destruct(buffer, buffer + requested_size); - EASTLFree(allocator, buffer, requested_size * sizeof(value_type)); - - return result1; - } - - ///////////////////////////////////////////////////////////////////// - // quick_sort - // - // We do the "introspection sort" variant of quick sort which is now - // well-known and understood. You can read about this algorithm in - // many articles on quick sort, but briefly what it does is a median- - // of-three quick sort whereby the recursion depth is limited to a - // some value (after which it gives up on quick sort and switches to - // a heap sort) and whereby after a certain amount of sorting the - // algorithm stops doing quick-sort and finishes the sorting via - // a simple insertion sort. - ///////////////////////////////////////////////////////////////////// - - #if (defined(EA_PROCESSOR_X86) || defined(EA_PROCESSOR_X86_64)) - static const int kQuickSortLimit = 28; // For sorts of random arrays over 100 items, 28 - 32 have been found to be good numbers on x86. - #else - static const int kQuickSortLimit = 16; // It seems that on other processors lower limits are more beneficial, as they result in fewer compares. - #endif - - namespace Internal - { - template <typename Size> - inline Size Log2(Size n) - { - int i; - for(i = 0; n; ++i) - n >>= 1; - return i - 1; - } - - // To do: Investigate the speed of this bit-trick version of Log2. - // It may work better on some platforms but not others. - // - // union FloatUnion { - // float f; - // uint32_t i; - // }; - // - // inline uint32_t Log2(uint32_t x) - // { - // const FloatInt32Union u = { x }; - // return (u.i >> 23) - 127; - // } - } - - template <typename RandomAccessIterator, typename T> - inline RandomAccessIterator get_partition_impl(RandomAccessIterator first, RandomAccessIterator last, T&& pivotValue) - { - using PureT = decay_t<T>; - - for(; ; ++first) - { - while(eastl::less<PureT>()(*first, pivotValue)) - { - EASTL_VALIDATE_COMPARE(!eastl::less<PureT>()(pivotValue, *first)); // Validate that the compare function is sane. - ++first; - } - --last; - - while(eastl::less<PureT>()(pivotValue, *last)) - { - EASTL_VALIDATE_COMPARE(!eastl::less<PureT>()(*last, pivotValue)); // Validate that the compare function is sane. - --last; - } - - if(first >= last) // Random access iterators allow operator >= - return first; - - eastl::iter_swap(first, last); - } - } - - /// get_partition - /// - /// This function takes const T& instead of T because T may have special alignment - /// requirements and some compilers (e.g. VC++) are don't respect alignment requirements - /// for function arguments. - /// - template <typename RandomAccessIterator, typename T> - inline RandomAccessIterator get_partition(RandomAccessIterator first, RandomAccessIterator last, const T& pivotValue) - { - const T pivotCopy(pivotValue); // Need to make a temporary because the sequence below is mutating. - return get_partition_impl<RandomAccessIterator, const T&>(first, last, pivotCopy); - } - - template <typename RandomAccessIterator, typename T> - inline RandomAccessIterator get_partition(RandomAccessIterator first, RandomAccessIterator last, T&& pivotValue) - { - // Note: unlike the copy-constructible variant of get_partition... we can't create a temporary const move-constructible object - return get_partition_impl<RandomAccessIterator, T&&>(first, last, eastl::move(pivotValue)); - } - - template <typename RandomAccessIterator, typename T, typename Compare> - inline RandomAccessIterator get_partition_impl(RandomAccessIterator first, RandomAccessIterator last, T&& pivotValue, Compare compare) - { - for(; ; ++first) - { - while(compare(*first, pivotValue)) - { - EASTL_VALIDATE_COMPARE(!compare(pivotValue, *first)); // Validate that the compare function is sane. - ++first; - } - --last; - - while(compare(pivotValue, *last)) - { - EASTL_VALIDATE_COMPARE(!compare(*last, pivotValue)); // Validate that the compare function is sane. - --last; - } - - if(first >= last) // Random access iterators allow operator >= - return first; - - eastl::iter_swap(first, last); - } - } - - template <typename RandomAccessIterator, typename T, typename Compare> - inline RandomAccessIterator get_partition(RandomAccessIterator first, RandomAccessIterator last, const T& pivotValue, Compare compare) - { - const T pivotCopy(pivotValue); // Need to make a temporary because the sequence below is mutating. - return get_partition_impl<RandomAccessIterator, const T&, Compare>(first, last, pivotCopy, compare); - } - - template <typename RandomAccessIterator, typename T, typename Compare> - inline RandomAccessIterator get_partition(RandomAccessIterator first, RandomAccessIterator last, T&& pivotValue, Compare compare) - { - // Note: unlike the copy-constructible variant of get_partition... we can't create a temporary const move-constructible object - return get_partition_impl<RandomAccessIterator, T&&, Compare>(first, last, eastl::forward<T>(pivotValue), compare); - } - - - namespace Internal - { - // This function is used by quick_sort and is not intended to be used by itself. - // This is because the implementation below makes an assumption about the input - // data that quick_sort satisfies but arbitrary data may not. - // There is a standalone insertion_sort function. - template <typename RandomAccessIterator> - inline void insertion_sort_simple(RandomAccessIterator first, RandomAccessIterator last) - { - for(RandomAccessIterator current = first; current != last; ++current) - { - typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type value_type; - - RandomAccessIterator end(current), prev(current); - value_type value(eastl::forward<value_type>(*current)); - - for(--prev; eastl::less<value_type>()(value, *prev); --end, --prev) // We skip checking for (prev >= first) because quick_sort (our caller) makes this unnecessary. - { - EASTL_VALIDATE_COMPARE(!eastl::less<value_type>()(*prev, value)); // Validate that the compare function is sane. - *end = eastl::forward<value_type>(*prev); - } - - *end = eastl::forward<value_type>(value); - } - } - - - // This function is used by quick_sort and is not intended to be used by itself. - // This is because the implementation below makes an assumption about the input - // data that quick_sort satisfies but arbitrary data may not. - // There is a standalone insertion_sort function. - template <typename RandomAccessIterator, typename Compare> - inline void insertion_sort_simple(RandomAccessIterator first, RandomAccessIterator last, Compare compare) - { - for(RandomAccessIterator current = first; current != last; ++current) - { - typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type value_type; - - RandomAccessIterator end(current), prev(current); - value_type value(eastl::forward<value_type>(*current)); - - for(--prev; compare(value, *prev); --end, --prev) // We skip checking for (prev >= first) because quick_sort (our caller) makes this unnecessary. - { - EASTL_VALIDATE_COMPARE(!compare(*prev, value)); // Validate that the compare function is sane. - *end = eastl::forward<value_type>(*prev); - } - - *end = eastl::forward<value_type>(value); - } - } - } // namespace Internal - - - template <typename RandomAccessIterator> - inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) - { - typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type; - typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type value_type; - - eastl::make_heap<RandomAccessIterator>(first, middle); - - for(RandomAccessIterator i = middle; i < last; ++i) - { - if(eastl::less<value_type>()(*i, *first)) - { - EASTL_VALIDATE_COMPARE(!eastl::less<value_type>()(*first, *i)); // Validate that the compare function is sane. - value_type temp(eastl::forward<value_type>(*i)); - *i = eastl::forward<value_type>(*first); - eastl::adjust_heap<RandomAccessIterator, difference_type, value_type> - (first, difference_type(0), difference_type(middle - first), difference_type(0), eastl::forward<value_type>(temp)); - } - } - - eastl::sort_heap<RandomAccessIterator>(first, middle); - } - - - template <typename RandomAccessIterator, typename Compare> - inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare compare) - { - typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type; - typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type value_type; - - eastl::make_heap<RandomAccessIterator, Compare>(first, middle, compare); - - for(RandomAccessIterator i = middle; i < last; ++i) - { - if(compare(*i, *first)) - { - EASTL_VALIDATE_COMPARE(!compare(*first, *i)); // Validate that the compare function is sane. - value_type temp(eastl::forward<value_type>(*i)); - *i = eastl::forward<value_type>(*first); - eastl::adjust_heap<RandomAccessIterator, difference_type, value_type, Compare> - (first, difference_type(0), difference_type(middle - first), difference_type(0), eastl::forward<value_type>(temp), compare); - } - } - - eastl::sort_heap<RandomAccessIterator, Compare>(first, middle, compare); - } - - - template<typename RandomAccessIterator> - inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last) - { - typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; - - while((last - first) > 5) - { - const value_type midValue(eastl::median<value_type>(*first, *(first + (last - first) / 2), *(last - 1))); - const RandomAccessIterator midPos(eastl::get_partition<RandomAccessIterator, value_type>(first, last, midValue)); - - if(midPos <= nth) - first = midPos; - else - last = midPos; - } - - eastl::insertion_sort<RandomAccessIterator>(first, last); - } - - - template<typename RandomAccessIterator, typename Compare> - inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare compare) - { - typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; - - while((last - first) > 5) - { - const value_type midValue(eastl::median<value_type, Compare>(*first, *(first + (last - first) / 2), *(last - 1), compare)); - const RandomAccessIterator midPos(eastl::get_partition<RandomAccessIterator, value_type, Compare>(first, last, midValue, compare)); - - if(midPos <= nth) - first = midPos; - else - last = midPos; - } - - eastl::insertion_sort<RandomAccessIterator, Compare>(first, last, compare); - } - - - namespace Internal - { - EA_DISABLE_VC_WARNING(4702) // unreachable code - template <typename RandomAccessIterator, typename Size, typename PivotValueType> - inline void quick_sort_impl_helper(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount) - { - typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; - - while(((last - first) > kQuickSortLimit) && (kRecursionCount > 0)) - { - const RandomAccessIterator position(eastl::get_partition<RandomAccessIterator, value_type>(first, last, - eastl::forward<PivotValueType>(eastl::median<value_type>(eastl::forward<value_type>(*first), eastl::forward<value_type>(*(first + (last - first) / 2)), eastl::forward<value_type>(*(last - 1)))))); - - eastl::Internal::quick_sort_impl_helper<RandomAccessIterator, Size, PivotValueType>(position, last, --kRecursionCount); - last = position; - } - - if(kRecursionCount == 0) - eastl::partial_sort<RandomAccessIterator>(first, last, last); - } - - template <typename RandomAccessIterator, typename Size, typename Compare, typename PivotValueType> - inline void quick_sort_impl_helper(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount, Compare compare) - { - typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; - - while(((last - first) > kQuickSortLimit) && (kRecursionCount > 0)) - { - const RandomAccessIterator position(eastl::get_partition<RandomAccessIterator, value_type, Compare>(first, last, - eastl::forward<PivotValueType>(eastl::median<value_type, Compare>(eastl::forward<value_type>(*first), eastl::forward<value_type>(*(first + (last - first) / 2)), eastl::forward<value_type>(*(last - 1)), compare)), compare)); - - eastl::Internal::quick_sort_impl_helper<RandomAccessIterator, Size, Compare, PivotValueType>(position, last, --kRecursionCount, compare); - last = position; - } - - if(kRecursionCount == 0) - eastl::partial_sort<RandomAccessIterator, Compare>(first, last, last, compare); - } - EA_RESTORE_VC_WARNING() - - template <typename RandomAccessIterator, typename Size> - inline void quick_sort_impl(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount, - typename eastl::enable_if<eastl::is_copy_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value>::type* = 0) - { - typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; - - // copy constructors require const value_type - quick_sort_impl_helper<RandomAccessIterator, Size, const value_type>(first, last, kRecursionCount); - } - - template <typename RandomAccessIterator, typename Size> - inline void quick_sort_impl(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount, - typename eastl::enable_if<eastl::is_move_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value - && !eastl::is_copy_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value>::type* = 0) - { - typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; - - // move constructors require non-const value_type - quick_sort_impl_helper<RandomAccessIterator, Size, value_type>(first, last, kRecursionCount); - } - - template <typename RandomAccessIterator, typename Size, typename Compare> - inline void quick_sort_impl(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount, Compare compare, - typename eastl::enable_if<eastl::is_copy_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value>::type* = 0) - { - typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; - - // copy constructors require const value_type - quick_sort_impl_helper<RandomAccessIterator, Size, Compare, const value_type>(first, last, kRecursionCount, compare); - } - - template <typename RandomAccessIterator, typename Size, typename Compare> - inline void quick_sort_impl(RandomAccessIterator first, RandomAccessIterator last, Size kRecursionCount, Compare compare, - typename eastl::enable_if<eastl::is_move_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value - && !eastl::is_copy_constructible<typename iterator_traits<RandomAccessIterator>::value_type>::value>::type* = 0) - { - typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; - - // move constructors require non-const value_type - quick_sort_impl_helper<RandomAccessIterator, Size, Compare, value_type>(first, last, kRecursionCount, compare); - } - } - - - /// quick_sort - /// - /// This is an unstable sort. - /// quick_sort sorts the elements in [first, last) into ascending order, - /// meaning that if i and j are any two valid iterators in [first, last) - /// such that i precedes j, then *j is not less than *i. quick_sort is not - /// guaranteed to be stable. That is, suppose that *i and *j are equivalent: - /// neither one is less than the other. It is not guaranteed that the - /// relative order of these two elements will be preserved by sort. - /// - /// We implement the "introspective" variation of quick-sort. This is - /// considered to be the best general-purpose variant, as it avoids - /// worst-case behaviour and optimizes the final sorting stage by - /// switching to an insertion sort. - /// - template <typename RandomAccessIterator> - void quick_sort(RandomAccessIterator first, RandomAccessIterator last) - { - typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type; - - if(first != last) - { - eastl::Internal::quick_sort_impl<RandomAccessIterator, difference_type>(first, last, 2 * Internal::Log2(last - first)); - - if((last - first) > (difference_type)kQuickSortLimit) - { - eastl::insertion_sort<RandomAccessIterator>(first, first + kQuickSortLimit); - eastl::Internal::insertion_sort_simple<RandomAccessIterator>(first + kQuickSortLimit, last); - } - else - eastl::insertion_sort<RandomAccessIterator>(first, last); - } - } - - - template <typename RandomAccessIterator, typename Compare> - void quick_sort(RandomAccessIterator first, RandomAccessIterator last, Compare compare) - { - typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type; - - if(first != last) - { - eastl::Internal::quick_sort_impl<RandomAccessIterator, difference_type, Compare>(first, last, 2 * Internal::Log2(last - first), compare); - - if((last - first) > (difference_type)kQuickSortLimit) - { - eastl::insertion_sort<RandomAccessIterator, Compare>(first, first + kQuickSortLimit, compare); - eastl::Internal::insertion_sort_simple<RandomAccessIterator, Compare>(first + kQuickSortLimit, last, compare); - } - else - eastl::insertion_sort<RandomAccessIterator, Compare>(first, last, compare); - } - } - - - - - namespace Internal - { - // Portions of the tim_sort code were originally written by Christopher Swenson. - // https://github.com/swenson/sort - // All code in this repository, unless otherwise specified, is hereby licensed under the - // MIT Public License: Copyright (c) 2010 Christopher Swenson - - const intptr_t kTimSortStackSize = 64; // Question: What's the upper-limit size requirement for this? - - struct tim_sort_run - { - intptr_t start; - intptr_t length; - }; - - - // EASTL_COUNT_LEADING_ZEROES - // - // Count leading zeroes in an integer. - // - #ifndef EASTL_COUNT_LEADING_ZEROES - #if defined(__GNUC__) - #if (EA_PLATFORM_PTR_SIZE == 8) - #define EASTL_COUNT_LEADING_ZEROES __builtin_clzll - #else - #define EASTL_COUNT_LEADING_ZEROES __builtin_clz - #endif - #endif - - #ifndef EASTL_COUNT_LEADING_ZEROES - static inline int eastl_count_leading_zeroes(uint64_t x) - { - if(x) - { - int n = 0; - if(x & UINT64_C(0xFFFFFFFF00000000)) { n += 32; x >>= 32; } - if(x & 0xFFFF0000) { n += 16; x >>= 16; } - if(x & 0xFFFFFF00) { n += 8; x >>= 8; } - if(x & 0xFFFFFFF0) { n += 4; x >>= 4; } - if(x & 0xFFFFFFFC) { n += 2; x >>= 2; } - if(x & 0xFFFFFFFE) { n += 1; } - return 63 - n; - } - return 64; - } - - static inline int eastl_count_leading_zeroes(uint32_t x) - { - if(x) - { - int n = 0; - if(x <= 0x0000FFFF) { n += 16; x <<= 16; } - if(x <= 0x00FFFFFF) { n += 8; x <<= 8; } - if(x <= 0x0FFFFFFF) { n += 4; x <<= 4; } - if(x <= 0x3FFFFFFF) { n += 2; x <<= 2; } - if(x <= 0x7FFFFFFF) { n += 1; } - return n; - } - return 32; - } - - #define EASTL_COUNT_LEADING_ZEROES eastl_count_leading_zeroes - #endif - #endif - - - // reverse_elements - // - // Reverses the range [first + start, first + start + size) - // To consider: Use void eastl::reverse(BidirectionalIterator first, BidirectionalIterator last); - // - template <typename RandomAccessIterator> - void reverse_elements(RandomAccessIterator first, intptr_t start, intptr_t end) - { - while(start < end) - { - eastl::swap(*(first + start), *(first + end)); - ++start; - --end; - } - } - - - // tim_sort_count_run - // - // Finds the length of a run which is already sorted (either up or down). - // If the run is in reverse order, this function puts it in regular order. - // - template <typename RandomAccessIterator, typename StrictWeakOrdering> - intptr_t tim_sort_count_run(const RandomAccessIterator first, const intptr_t start, const intptr_t size, StrictWeakOrdering compare) - { - if((size - start) > 1) // If there is anything in the set... - { - intptr_t curr = (start + 2); - - if(!compare(*(first + start + 1), *(first + start))) // If (first[start + 1] >= first[start]) (If the run is increasing) ... - { - for(;; ++curr) - { - if(curr >= (size - 1)) // If we are at the end of the data... this run is done. - break; - - if(compare(*(first + curr), *(first + curr - 1))) // If this item is not in order... this run is done. - break; - } - } - else // Else it is decreasing. - { - for(;; ++curr) - { - if(curr >= (size - 1)) // If we are at the end of the data... this run is done. - break; - - if(!compare(*(first + curr), *(first + curr - 1))) // If this item is not in order... this run is done. - break; // Note that we intentionally compare against <= 0 and not just < 0. This is because - } // The reverse_elements call below could reverse two equal elements and break our stability requirement. - - reverse_elements(first, start, curr - 1); - } - - return (curr - start); - } - - // Else we have just one item in the set. - return 1; - } - - - // Input Return - // -------------- - // 64 32 - // 65 33 - // 66 33 - // 67 34 - // 68 34 - // ... - // 125 63 - // 126 63 - // 127 64 - // 128 32 - // 129 33 - // 130 33 - // 131 33 - // 132 33 - // 133 34 - // 134 34 - // 135 34 - // 136 34 - // 137 35 - // ... - // - // This function will return a value that is always in the range of [32, 64]. - // - static inline intptr_t timsort_compute_minrun(intptr_t size) - { - const int32_t top_bit = (int32_t)((sizeof(intptr_t) * 8) - EASTL_COUNT_LEADING_ZEROES((uintptr_t)size)); - const int32_t shift = (top_bit > 6) ? (top_bit - 6) : 0; - const intptr_t mask = (intptr_t(1) << shift) - 1; - intptr_t minrun = (intptr_t)(size >> shift); - - if(mask & size) - ++minrun; - - return minrun; - } - - - template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering> - void tim_sort_merge(RandomAccessIterator first, const tim_sort_run* run_stack, const intptr_t stack_curr, - T* pBuffer, StrictWeakOrdering compare) - { - const intptr_t A = run_stack[stack_curr - 2].length; - const intptr_t B = run_stack[stack_curr - 1].length; - const intptr_t curr = run_stack[stack_curr - 2].start; - - EASTL_DEV_ASSERT((A < 10000000) && (B < 10000000) && (curr < 10000000)); // Sanity check. - - if(A < B) // If the first run is shorter than the second run... merge left. - { - // Copy to another location so we have room in the main array to put the sorted items. - eastl::copy(first + curr, first + curr + A, pBuffer); - - #if EASTL_DEV_DEBUG - typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type value_type; - - for(intptr_t i = 0; i < A; i++) - *(first + curr + i) = value_type(); - #endif - - intptr_t i = 0; - intptr_t j = curr + A; - - for(intptr_t k = curr; k < curr + A + B; k++) - { - if((i < A) && (j < (curr + A + B))) - { - if(!compare(*(first + j), *(pBuffer + i))) // If (first[j] >= pBuffer[i])... - *(first + k) = *(pBuffer + i++); - else - *(first + k) = *(first + j++); - } - else if(i < A) - *(first + k) = *(pBuffer + i++); - else - *(first + k) = *(first + j++); - } - } - else // Else the second run is equal or shorter... merge right. - { - eastl::copy(first + curr + A, first + curr + A + B, pBuffer); - - intptr_t i = B - 1; - intptr_t j = curr + A - 1; - - for(intptr_t k = curr + A + B - 1; k >= curr; k--) - { - if((i >= 0) && (j >= curr)) - { - if(compare(*(pBuffer + i), *(first + j))) // If (pBuffer[i] < first[j]) ... - *(first + k) = *(first + j--); - else - *(first + k) = *(pBuffer + i--); - } - else if(i >= 0) - *(first + k) = *(pBuffer + i--); - else - *(first + k) = *(first + j--); - } - } - } - - - // See the timsort.txt file for an explanation of this function. - // - // ------------------------------------------------------------------------ - // What turned out to be a good compromise maintains two invariants on the - // stack entries, where A, B and C are the lengths of the three righmost - // not-yet merged slices: - // 1. A > B+C - // 2. B > C - // ------------------------------------------------------------------------ - // - static inline bool timsort_check_invariant(tim_sort_run* run_stack, const intptr_t stack_curr) - { - // To do: Optimize this for the most common type of values. - if(stack_curr > 2) - { - const intptr_t A = run_stack[stack_curr - 3].length; - const intptr_t B = run_stack[stack_curr - 2].length; - const intptr_t C = run_stack[stack_curr - 1].length; - - EASTL_DEV_ASSERT((A < 10000000) && (B < 10000000) && (C < 10000000)); // Sanity check. - - if((A <= (B + C)) || (B <= C)) - return true; // Merge the right-most runs. - } - else if(stack_curr == 2) - { - const intptr_t A = run_stack[stack_curr - 2].length; - const intptr_t B = run_stack[stack_curr - 1].length; - - EASTL_DEV_ASSERT((A < 10000000) && (B < 10000000)); // Sanity check. - - if(A <= B) - return true; // Merge the right-most runs. - } - - return false; // Don't merge the right-most runs. - } - - - template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering> - intptr_t tim_sort_collapse(RandomAccessIterator first, tim_sort_run* run_stack, intptr_t stack_curr, - T* pBuffer, const intptr_t size, StrictWeakOrdering compare) - { - // If the run_stack only has one thing on it, we are done with the collapse. - while(stack_curr > 1) - { - // If this is the last merge, just do it. - if((stack_curr == 2) && ((run_stack[0].length + run_stack[1].length) == size)) - { - tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare); - run_stack[0].length += run_stack[1].length; - stack_curr--; - - #if EASTL_DEV_DEBUG - memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr])); - #endif - - break; - } - // Check if the invariant is off for a run_stack of 2 elements. - else if((stack_curr == 2) && (run_stack[0].length <= run_stack[1].length)) - { - tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare); - run_stack[0].length += run_stack[1].length; - stack_curr--; - - #if EASTL_DEV_DEBUG - memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr])); - #endif - - break; - } - else if (stack_curr == 2) - break; - - const intptr_t A = run_stack[stack_curr - 3].length; - const intptr_t B = run_stack[stack_curr - 2].length; - const intptr_t C = run_stack[stack_curr - 1].length; - - if(A <= (B + C)) // Check first invariant. - { - if(A < C) - { - tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr - 1, pBuffer, compare); - - stack_curr--; - run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; // Merge A and B. - run_stack[stack_curr - 1] = run_stack[stack_curr]; - - #if EASTL_DEV_DEBUG - EASTL_DEV_ASSERT((run_stack[stack_curr - 2].start + run_stack[stack_curr - 2].length) <= size); - EASTL_DEV_ASSERT((run_stack[stack_curr - 1].start + run_stack[stack_curr - 1].length) <= size); - memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr])); - #endif - } - else - { - tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare); // Merge B and C. - - stack_curr--; - run_stack[stack_curr - 1].length += run_stack[stack_curr].length; - - #if EASTL_DEV_DEBUG - EASTL_DEV_ASSERT((run_stack[stack_curr - 1].start + run_stack[stack_curr - 1].length) <= size); - memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr])); - #endif - } - } - else if(B <= C) // Check second invariant - { - tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare); - - stack_curr--; - run_stack[stack_curr - 1].length += run_stack[stack_curr].length; // Merge B and C. - - #if EASTL_DEV_DEBUG - EASTL_DEV_ASSERT((run_stack[stack_curr - 1].start + run_stack[stack_curr - 1].length) <= size); - memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr])); - #endif - } - else - break; - } - - return stack_curr; - } - - - // tim_sort_add_run - // - // Return true if the sort is done. - // - template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering> - bool tim_sort_add_run(tim_sort_run* run_stack, RandomAccessIterator first, T* pBuffer, const intptr_t size, const intptr_t minrun, - intptr_t& len, intptr_t& run, intptr_t& curr, intptr_t& stack_curr, StrictWeakOrdering compare) - { - len = tim_sort_count_run<RandomAccessIterator, StrictWeakOrdering>(first, curr, size, compare); // This will count the length of the run and reverse the run if it is backwards. - run = minrun; - - if(run < minrun) // Always make runs be of minrun length (we'll sort the additional data as needed below) - run = minrun; - - if(run > (size - curr)) // But if there isn't minrun data remaining, just sort what's remaining. - run = (size - curr); - - if(run > len) // If there is any additional data we want to sort to bring up the run length to minrun. - { - insertion_sort_already_started<RandomAccessIterator, StrictWeakOrdering>(first + curr, first + curr + run, first + curr + len, compare); - len = run; - } - - // At this point, run will be equal to minrun or will go to the end of our data. - // Add this run to our stack of runs. - EASTL_DEV_ASSERT(stack_curr < kTimSortStackSize); - EASTL_DEV_ASSERT((curr >= 0) && (curr < size) && ((curr + len) <= size)); - - run_stack[stack_curr].start = curr; - run_stack[stack_curr].length = len; - stack_curr++; - - // Move to the beginning of the next run in the data. - curr += len; - - if(curr == size) // If we have hit the end of the data... - { - while(stack_curr > 1) // If there is any more than one run... (else all the data is sorted) - { - tim_sort_merge<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, compare); - - run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; - stack_curr--; - - #if EASTL_DEV_DEBUG - EASTL_DEV_ASSERT((run_stack[stack_curr - 1].start + run_stack[stack_curr - 1].length) <= size); - memset(&run_stack[stack_curr], 0, sizeof(run_stack[stack_curr])); - #endif - } - - return true; // We are done with sorting. - } - - return false; - } - - } // namespace Internal - - - // tim_sort_buffer - // - /// This is a stable sort. - // Implements the tim-sort sorting algorithm with a user-provided scratch buffer. - // http://en.wikipedia.org/wiki/Timsort - // This sort is the fastest sort when sort stability (maintaining order of equal values) is required and - // data sets are non-trivial (size >= 15). It's also the fastest sort (e.g. faster than quick_sort) for - // the case that at at least half your data is already sorted. Otherwise, eastl::quick_sort is about 10% - // faster than tim_sort_buffer but is not a stable sort. There are some reports that tim_sort outperforms - // quick_sort but most of these aren't taking into account that optimal quick_sort implementations use - // a hybrid approach called "introsort" (http://en.wikipedia.org/wiki/Introsort) which improves quick_sort - // considerably in practice. - // - // Strengths: - // - Fastest stable sort for most sizes of data. - // - Fastest sort for containers of data already mostly sorted. - // - Simpler to understand than quick_sort. - // - // Weaknesses: - // - User must provide a scratch buffer, otherwise the buffer is dynamically allocated during runtime. - // - Not as fast as quick_sort for the general case of randomized data. - // - Requires a RandomAccessIterator; thus must be on an array container type and not a list container type. - // - Uses a lot of code to implement; thus it's not great when there is little room for more code. - // - // The pBuffer parameter must hold at least ((last-first)/2) elements (i.e. half the elements of the container). - // This minimum size is a worst-case size requirement, but handles all possible cases. pBuffer is just a scratch - // buffer and is not needed after the return of this function, and doesn't need to be seeded with any particular - // values upon entering this function. - // - // Example usage: - // int intArray[64]; - // int buffer[32]; - // ... - // tim_sort_buffer(intArray, intArray + 64, buffer); - // - template <typename RandomAccessIterator, typename T, typename StrictWeakOrdering> - void tim_sort_buffer(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer, StrictWeakOrdering compare) - { - using namespace Internal; - - // To consider: Convert the implementation to use first/last instead of first/size. - const intptr_t size = (intptr_t)(last - first); - - if(size < 64) - insertion_sort_already_started(first, first + size, first + 1, compare); - else - { - tim_sort_run run_stack[kTimSortStackSize]; - intptr_t stack_curr = 0; - intptr_t len, run; - intptr_t curr = 0; - const intptr_t minrun = timsort_compute_minrun(size); - - #if EASTL_DEV_DEBUG - memset(run_stack, 0, sizeof(run_stack)); - #endif - - if(tim_sort_add_run<RandomAccessIterator, T, StrictWeakOrdering>(run_stack, first, pBuffer, size, minrun, len, run, curr, stack_curr, compare)) - return; - if(tim_sort_add_run<RandomAccessIterator, T, StrictWeakOrdering>(run_stack, first, pBuffer, size, minrun, len, run, curr, stack_curr, compare)) - return; - if(tim_sort_add_run<RandomAccessIterator, T, StrictWeakOrdering>(run_stack, first, pBuffer, size, minrun, len, run, curr, stack_curr, compare)) - return; - - for(;;) - { - if(timsort_check_invariant(run_stack, stack_curr)) - stack_curr = tim_sort_collapse<RandomAccessIterator, T, StrictWeakOrdering>(first, run_stack, stack_curr, pBuffer, size, compare); - else - { - if(tim_sort_add_run<RandomAccessIterator, T, StrictWeakOrdering>(run_stack, first, pBuffer, size, minrun, len, run, curr, stack_curr, compare)) - break; - } - } - } - } - - - template <typename RandomAccessIterator, typename T> - inline void tim_sort_buffer(RandomAccessIterator first, RandomAccessIterator last, T* pBuffer) - { - typedef eastl::less<T> Less; - - eastl::tim_sort_buffer<RandomAccessIterator, T, Less>(first, last, pBuffer, Less()); - } - - - - - /// radix_sort - /// - /// Implements a classic LSD (least significant digit) radix sort. - /// See http://en.wikipedia.org/wiki/Radix_sort. - /// This sort requires that the sorted data be of a type that has a member - /// radix_type typedef and an mKey member of that type. The type must be - /// an integral type. This limits what can be sorted, but radix_sort is - /// very fast -- typically faster than any other sort. - /// For example: - /// struct Sortable { - /// typedef int radix_type; - /// radix_type mKey; - /// // User data goes here, or the user can inherit from Sortable. - /// }; - /// or, more generally: - /// template <typname Integer> - /// struct Sortable { - /// typedef Integer radix_type; - /// Integer mKey; - /// }; - /// - /// Example usage: - /// struct Element { - /// typedef uint16_t radix_type; - /// uint16_t mKey; - /// uint16_t mUserData; - /// }; - /// - /// Element elementArray[100]; - /// Element buffer[100]; - /// - /// radix_sort<Element*, extract_radix_key<Element> >(elementArray, elementArray + 100, buffer); - /// - /// To consider: A static linked-list implementation may be faster than the version here. - - namespace Internal - { - /// extract_radix_key - /// - /// Default radix sort integer value reader. It expects the sorted elements - /// to have an integer member of type radix_type and of name "mKey". - /// - template <typename Node> - struct extract_radix_key - { - typedef typename Node::radix_type radix_type; - - const radix_type operator()(const Node& x) const - { return x.mKey; } - }; - - // The radix_sort implementation uses two optimizations that are not part of a typical radix sort implementation. - // 1. Computing a histogram (i.e. finding the number of elements per bucket) for the next pass is done in parallel with the loop that "scatters" - // elements in the current pass. The advantage is that it avoids the memory traffic / cache pressure of reading keys in a separate operation. - // Note: It would also be possible to compute all histograms in a single pass. However, that would increase the amount of stack space used and - // also increase cache pressure slightly. However, it could still be faster under some situations. - // 2. If all elements are mapped to a single bucket, then there is no need to perform a scatter operation. Instead the elements are left in place - // and only copied if they need to be copied to the final output buffer. - template <typename RandomAccessIterator, typename ExtractKey, int DigitBits, typename IntegerType> - void radix_sort_impl(RandomAccessIterator first, - RandomAccessIterator last, - RandomAccessIterator buffer, - ExtractKey extractKey, - IntegerType) - { - RandomAccessIterator srcFirst = first; - EA_CONSTEXPR_OR_CONST size_t numBuckets = 1 << DigitBits; - EA_CONSTEXPR_OR_CONST IntegerType bucketMask = numBuckets - 1; - - // The alignment of this variable isn't required; it merely allows the code below to be faster on some platforms. - uint32_t EA_PREFIX_ALIGN(EASTL_PLATFORM_PREFERRED_ALIGNMENT) bucketSize[numBuckets]; - uint32_t EA_PREFIX_ALIGN(EASTL_PLATFORM_PREFERRED_ALIGNMENT) bucketPosition[numBuckets]; - - RandomAccessIterator temp; - uint32_t i; - - bool doSeparateHistogramCalculation = true; - uint32_t j; - for (j = 0; j < (8 * sizeof(IntegerType)); j += DigitBits) - { - if (doSeparateHistogramCalculation) - { - memset(bucketSize, 0, sizeof(bucketSize)); - // Calculate histogram for the first scatter operation - for (temp = srcFirst; temp != last; ++temp) - ++bucketSize[(extractKey(*temp) >> j) & bucketMask]; - } - - // If a single bucket contains all of the elements, then don't bother redistributing all elements to the - // same bucket. - if (bucketSize[((extractKey(*srcFirst) >> j) & bucketMask)] == uint32_t(last - srcFirst)) - { - // Set flag to ensure histogram is computed for next digit position. - doSeparateHistogramCalculation = true; - } - else - { - // The histogram is either not needed or it will be calculated in parallel with the scatter operation below for better cache efficiency. - doSeparateHistogramCalculation = false; - - // If this is the last digit position, then don't calculate a histogram - if (j == (8 * sizeof(IntegerType) - DigitBits)) - { - bucketPosition[0] = 0; - for (i = 0; i < numBuckets - 1; i++) - { - bucketPosition[i + 1] = bucketPosition[i] + bucketSize[i]; - } - - for (temp = srcFirst; temp != last; ++temp) - { - IntegerType key = extractKey(*temp); - const size_t digit = (key >> j) & bucketMask; - buffer[bucketPosition[digit]++] = *temp; - } - } - // Compute the histogram while performing the scatter operation - else - { - bucketPosition[0] = 0; - for (i = 0; i < numBuckets - 1; i++) - { - bucketPosition[i + 1] = bucketPosition[i] + bucketSize[i]; - bucketSize[i] = 0; // Clear the bucket for the next pass - } - bucketSize[numBuckets - 1] = 0; - - uint32_t jNext = j + DigitBits; - for (temp = srcFirst; temp != last; ++temp) - { - IntegerType key = extractKey(*temp); - const size_t digit = (key >> j) & bucketMask; - buffer[bucketPosition[digit]++] = *temp; - - // Update histogram for the next scatter operation - ++bucketSize[(extractKey(*temp) >> jNext) & bucketMask]; - } - } - - last = buffer + (last - srcFirst); - temp = srcFirst; - srcFirst = buffer; - buffer = temp; - } - } - - if (srcFirst != first) - { - // Copy values back into the expected buffer - for (temp = srcFirst; temp != last; ++temp) - *buffer++ = *temp; - } - } - } // namespace Internal - - template <typename RandomAccessIterator, typename ExtractKey, int DigitBits = 8> - void radix_sort(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator buffer) - { - static_assert(DigitBits > 0, "DigitBits must be > 0"); - static_assert(DigitBits <= (sizeof(typename ExtractKey::radix_type) * 8), "DigitBits must be <= the size of the key (in bits)"); - eastl::Internal::radix_sort_impl<RandomAccessIterator, ExtractKey, DigitBits>(first, last, buffer, ExtractKey(), typename ExtractKey::radix_type()); - } - - - - /// comb_sort - /// - /// This is an unstable sort. - /// Implements the CombSort algorithm; in particular, implements the CombSort11 variation - /// of the CombSort algorithm, based on the reference to '11' in the implementation. - /// - /// To consider: Use a comb sort table instead of the '((nSpace * 10) + 3) / 13' expression. - /// Ideal tables can be found on the Internet by looking up "comb sort table". - /// - template <typename ForwardIterator, typename StrictWeakOrdering> - void comb_sort(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare) - { - typedef typename eastl::iterator_traits<ForwardIterator>::difference_type difference_type; - - ForwardIterator iCurrent, iNext; - difference_type length = eastl::distance(first, last); - difference_type nSpace = length; - - for(bool bSwapped = false; (nSpace > 1) || bSwapped; ) - { - nSpace = ((nSpace * 10) + 3) / 13; // Integer division is less than ideal. - - if((nSpace == 9) || (nSpace == 10)) - nSpace = 11; - - iCurrent = iNext = first; - eastl::advance(iNext, nSpace); - - for(bSwapped = false; iNext != last; iCurrent++, iNext++) - { - if(compare(*iNext, *iCurrent)) - { - EASTL_VALIDATE_COMPARE(!compare(*iCurrent, *iNext)); // Validate that the compare function is sane. - eastl::iter_swap(iCurrent, iNext); - bSwapped = true; - } - } - } - } // comb_sort - - template <typename ForwardIterator> - inline void comb_sort(ForwardIterator first, ForwardIterator last) - { - typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less; - - eastl::comb_sort<ForwardIterator, Less>(first, last, Less()); - } - - - - - /// bubble_sort - /// - /// This is a stable sort. - /// Implements the BubbleSort algorithm. This algorithm is only useful for - /// small range sizes, such as 10 or less items. You may be better off using - /// insertion_sort for cases where bubble_sort works. - /// - namespace Internal - { - template <typename ForwardIterator, typename StrictWeakOrdering> - void bubble_sort_impl(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare, EASTL_ITC_NS::forward_iterator_tag) - { - ForwardIterator iCurrent, iNext; - - while(first != last) - { - iNext = iCurrent = first; - - for(++iNext; iNext != last; iCurrent = iNext, ++iNext) - { - if(compare(*iNext, *iCurrent)) - { - EASTL_VALIDATE_COMPARE(!compare(*iCurrent, *iNext)); // Validate that the compare function is sane. - eastl::iter_swap(iCurrent, iNext); - } - } - last = iCurrent; - } - } - - template <typename BidirectionalIterator, typename StrictWeakOrdering> - void bubble_sort_impl(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering compare, EASTL_ITC_NS::bidirectional_iterator_tag) - { - if(first != last) - { - BidirectionalIterator iCurrent, iNext, iLastModified; - - last--; - - while(first != last) - { - iLastModified = iNext = iCurrent = first; - - for(++iNext; iCurrent != last; iCurrent = iNext, ++iNext) - { - if(compare(*iNext, *iCurrent)) - { - EASTL_VALIDATE_COMPARE(!compare(*iCurrent, *iNext)); // Validate that the compare function is sane. - iLastModified = iCurrent; - eastl::iter_swap(iCurrent, iNext); - } - } - - last = iLastModified; - } - } - } - } // namespace Internal - - template <typename ForwardIterator, typename StrictWeakOrdering> - inline void bubble_sort(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare) - { - typedef typename eastl::iterator_traits<ForwardIterator>::iterator_category IC; - - eastl::Internal::bubble_sort_impl<ForwardIterator, StrictWeakOrdering>(first, last, compare, IC()); - } - - template <typename ForwardIterator> - inline void bubble_sort(ForwardIterator first, ForwardIterator last) - { - typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less; - typedef typename eastl::iterator_traits<ForwardIterator>::iterator_category IC; - - eastl::Internal::bubble_sort_impl<ForwardIterator, Less>(first, last, Less(), IC()); - } - - - - /// sort - /// - /// We use quick_sort by default. See quick_sort for details. - /// - /// EASTL_DEFAULT_SORT_FUNCTION - /// If a default sort function is specified then call it, otherwise use EASTL's default quick_sort. - /// EASTL_DEFAULT_SORT_FUNCTION must be namespace-qualified and include any necessary template - /// parameters (e.g. eastl::comb_sort instead of just comb_sort), and it must be visible to this code. - /// The EASTL_DEFAULT_SORT_FUNCTION must be provided in two versions: - /// template <typename RandomAccessIterator> - /// void EASTL_DEFAULT_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last); - /// - /// template <typename RandomAccessIterator, typename Compare> - /// void EASTL_DEFAULT_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last, Compare compare) - /// - template <typename RandomAccessIterator> - inline void sort(RandomAccessIterator first, RandomAccessIterator last) - { - #if defined(EASTL_DEFAULT_SORT_FUNCTION) - EASTL_DEFAULT_SORT_FUNCTION(first, last); - #else - eastl::quick_sort<RandomAccessIterator>(first, last); - #endif - } - - template <typename RandomAccessIterator, typename Compare> - inline void sort(RandomAccessIterator first, RandomAccessIterator last, Compare compare) - { - #if defined(EASTL_DEFAULT_SORT_FUNCTION) - EASTL_DEFAULT_SORT_FUNCTION(first, last, compare); - #else - eastl::quick_sort<RandomAccessIterator, Compare>(first, last, compare); - #endif - } - - - - /// stable_sort - /// - /// We use merge_sort by default. See merge_sort for details. - /// Beware that the used merge_sort -- and thus stable_sort -- allocates - /// memory during execution. Try using merge_sort_buffer if you want - /// to avoid memory allocation. - /// - /// EASTL_DEFAULT_STABLE_SORT_FUNCTION - /// If a default sort function is specified then call it, otherwise use EASTL's default merge_sort. - /// EASTL_DEFAULT_STABLE_SORT_FUNCTION must be namespace-qualified and include any necessary template - /// parameters (e.g. eastl::tim_sort instead of just tim_sort), and it must be visible to this code. - /// The EASTL_DEFAULT_STABLE_SORT_FUNCTION must be provided in three versions, though the third - /// allocation implementation may choose to ignore the allocator parameter: - /// template <typename RandomAccessIterator, typename StrictWeakOrdering> - /// void EASTL_DEFAULT_STABLE_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering compare); - /// - /// template <typename RandomAccessIterator> - /// void EASTL_DEFAULT_STABLE_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last); - /// - /// template <typename RandomAccessIterator, typename Allocator, typename StrictWeakOrdering> - /// void EASTL_DEFAULT_STABLE_SORT_FUNCTION(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator, StrictWeakOrdering compare); - /// - template <typename RandomAccessIterator, typename StrictWeakOrdering> - void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering compare) - { - #if defined(EASTL_DEFAULT_STABLE_SORT_FUNCTION) - EASTL_DEFAULT_STABLE_SORT_FUNCTION(first, last, *get_default_allocator(0), compare); - #else - eastl::merge_sort<RandomAccessIterator, EASTLAllocatorType, StrictWeakOrdering> - (first, last, *get_default_allocator(0), compare); - #endif - } - - template <typename RandomAccessIterator> - void stable_sort(RandomAccessIterator first, RandomAccessIterator last) - { - #if defined(EASTL_DEFAULT_STABLE_SORT_FUNCTION) - EASTL_DEFAULT_STABLE_SORT_FUNCTION(first, last, *get_default_allocator(0)); - #else - eastl::merge_sort<RandomAccessIterator, EASTLAllocatorType> - (first, last, *get_default_allocator(0)); - #endif - } - - template <typename RandomAccessIterator, typename Allocator, typename StrictWeakOrdering> - void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator, StrictWeakOrdering compare) - { - #if defined(EASTL_DEFAULT_STABLE_SORT_FUNCTION) - EASTL_DEFAULT_STABLE_SORT_FUNCTION(first, last, allocator, compare); - #else - eastl::merge_sort<RandomAccessIterator, Allocator, StrictWeakOrdering>(first, last, allocator, compare); - #endif - } - - // This is not defined because it would cause compiler errors due to conflicts with a version above. - //template <typename RandomAccessIterator, typename Allocator> - //void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Allocator& allocator) - //{ - // #if defined(EASTL_DEFAULT_STABLE_SORT_FUNCTION) - // EASTL_DEFAULT_STABLE_SORT_FUNCTION<RandomAccessIterator, Allocator>(first, last, allocator); - // #else - // eastl::merge_sort<RandomAccessIterator, Allocator>(first, last, allocator); - // #endif - //} - - - - - /* - // Something to consider adding: An eastl sort which uses qsort underneath. - // The primary purpose of this is to have an eastl interface for sorting which - // results in very little code generation, since all instances map to the - // C qsort function. - - template <typename T> - int small_footprint_sort_func(const void* a, const void* b) - { - if(*(const T*)a < *(const T*)b) - return -1; - if(*(const T*)a > *(const T*)b) - return +1; - return 0; - } - - template <typename ContiguousIterator> - void small_footprint_sort(ContiguousIterator first, ContiguousIterator last) - { - typedef typename eastl::iterator_traits<ContiguousIterator>::value_type value_type; - - qsort(first, (size_t)eastl::distance(first, last), sizeof(value_type), small_footprint_sort_func<value_type>); - } - */ - -} // namespace eastl - - -#endif // Header include guard - - - |