diff options
Diffstat (limited to 'include/EASTL/bonus/sort_extra.h')
| -rw-r--r-- | include/EASTL/bonus/sort_extra.h | 204 |
1 files changed, 0 insertions, 204 deletions
diff --git a/include/EASTL/bonus/sort_extra.h b/include/EASTL/bonus/sort_extra.h deleted file mode 100644 index 5f9a0c4..0000000 --- a/include/EASTL/bonus/sort_extra.h +++ /dev/null @@ -1,204 +0,0 @@ -///////////////////////////////////////////////////////////////////////////// -// Copyright (c) Electronic Arts Inc. All rights reserved. -///////////////////////////////////////////////////////////////////////////// - -////////////////////////////////////////////////////////////////////////////// -// This file implements additional sort algorithms beyond the basic set. -// Included here are: -// selection_sort -- Unstable. -// shaker_sort -- Stable. -// bucket_sort -- Stable. -// -////////////////////////////////////////////////////////////////////////////// - - -#ifndef EASTL_SORT_EXTRA_H -#define EASTL_SORT_EXTRA_H - - -#include <EASTL/internal/config.h> -#include <EASTL/iterator.h> -#include <EASTL/algorithm.h> -#include <EASTL/functional.h> -#include <EASTL/heap.h> -#include <EASTL/sort.h> // For backwards compatibility due to sorts moved from here to sort.h. -#include <EASTL/allocator.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 - - - -namespace eastl -{ - /// selection_sort - /// - /// Implements the SelectionSort algorithm. - /// - template <typename ForwardIterator, typename StrictWeakOrdering> - void selection_sort(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare) - { - ForwardIterator iCurrent, iMin; - - for(; first != last; ++first) - { - iCurrent = first; - iMin = iCurrent; - - for(++iCurrent; iCurrent != last; ++iCurrent) - { - if(compare(*iCurrent, *iMin)) - { - EASTL_VALIDATE_COMPARE(!compare(*iMin, *iCurrent)); // Validate that the compare function is sane. - iMin = iCurrent; - } - } - - if(first != iMin) - eastl::iter_swap(first, iMin); - } - } // selection_sort - - template <typename ForwardIterator> - inline void selection_sort(ForwardIterator first, ForwardIterator last) - { - typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less; - - eastl::selection_sort<ForwardIterator, Less>(first, last, Less()); - } - - - - /// shaker_sort - /// - /// Implements the ShakerSort algorithm, which is a sorting algorithm which - /// improves on bubble_sort by sweeping both from left to right and right - /// to left, resulting in less iteration. - /// - template <typename BidirectionalIterator, typename StrictWeakOrdering> - void shaker_sort(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering compare) - { - if(first != last) - { - BidirectionalIterator iCurrent, iNext, iLastModified; - - --last; - - while(first != last) - { - iLastModified = first; - - for(iCurrent = first; iCurrent != last; iCurrent = iNext) - { - iNext = iCurrent; - ++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; - - if(first != last) - { - for(iCurrent = last; iCurrent != first; iCurrent = iNext) - { - iNext = iCurrent; - --iNext; - - if(compare(*iCurrent, *iNext)) - { - EASTL_VALIDATE_COMPARE(!compare(*iNext, *iCurrent)); // Validate that the compare function is sane. - iLastModified = iCurrent; - eastl::iter_swap(iNext, iCurrent); - } - } - first = iLastModified; - } - } - } - } // shaker_sort - - template <typename BidirectionalIterator> - inline void shaker_sort(BidirectionalIterator first, BidirectionalIterator last) - { - typedef eastl::less<typename eastl::iterator_traits<BidirectionalIterator>::value_type> Less; - - eastl::shaker_sort<BidirectionalIterator, Less>(first, last, Less()); - } - - - - /// bucket_sort - /// - /// Implements the BucketSort algorithm. - /// - /// Example usage: - /// const size_t kElementRange = 32; - /// vector<int> intArray(1000); - /// - /// for(int i = 0; i < 1000; i++) - /// intArray[i] = rand() % kElementRange; - /// - /// vector< vector<int> > bucketArray(kElementRange); - /// bucket_sort(intArray.begin(), intArray.end(), bucketArray, eastl::hash_use_self<int>()); - /// - template <typename T> - struct hash_use_self - { - T operator()(const T& x) const - { return x; } - }; - - // Requires buckeyArray to be an array of arrays with a size equal to the range of values - // returned by the hash function. The hash function is required to return a unique value - // for each uniquely sorted element. Usually the way this is done is the elements are - // integers of a limited range (e.g. 0-64) and the hash function returns the element value - // itself. If you had a case where all elements were always even numbers (e.g. 0-128), - // you could use a custom hash function that returns (element value / 2). - // - // The user is required to provide an empty bucketArray to this function. This function returns - // with the bucketArray non-empty. This function doesn't clear the bucketArray because that takes - // time and the user might not need it to be cleared, at least at that time. - // - template <typename ForwardIterator, typename ContainerArray, typename HashFunction> - void bucket_sort(ForwardIterator first, ForwardIterator last, ContainerArray& bucketArray, HashFunction hash /*= hash_use_self*/) - { - for(ForwardIterator iInput = first; iInput != last; ++iInput) - bucketArray[hash(*iInput)].push_back(*iInput); - - for(typename ContainerArray::const_iterator iBucket = bucketArray.begin(); iBucket != bucketArray.end(); ++iBucket) - first = eastl::copy((*iBucket).begin(), (*iBucket).end(), first); - } - - - -} // namespace eastl - - -#endif // Header include guard - - - - - - - - - - - - - - - - - - - - |