diff options
author | Iain Merrick <husky@google.com> | 2010-09-13 16:35:48 +0100 |
---|---|---|
committer | Iain Merrick <husky@google.com> | 2010-09-16 12:10:42 +0100 |
commit | 5abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306 (patch) | |
tree | ddce1aa5e3b6967a69691892e500897558ff8ab6 /JavaScriptCore/wtf/NonCopyingSort.h | |
parent | 12bec63ec71e46baba27f0bd9bd9d8067683690a (diff) | |
download | external_webkit-5abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306.zip external_webkit-5abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306.tar.gz external_webkit-5abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306.tar.bz2 |
Merge WebKit at r67178 : Initial merge by git.
Change-Id: I57e01163b6866cb029cdadf405a0394a3918bc18
Diffstat (limited to 'JavaScriptCore/wtf/NonCopyingSort.h')
-rw-r--r-- | JavaScriptCore/wtf/NonCopyingSort.h | 89 |
1 files changed, 89 insertions, 0 deletions
diff --git a/JavaScriptCore/wtf/NonCopyingSort.h b/JavaScriptCore/wtf/NonCopyingSort.h new file mode 100644 index 0000000..fd611bd --- /dev/null +++ b/JavaScriptCore/wtf/NonCopyingSort.h @@ -0,0 +1,89 @@ +/* + * Copyright (C) 2010 Apple Inc. All Rights Reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + */ + +#ifndef WTF_NonCopyingSort_h +#define WTF_NonCopyingSort_h + +namespace WTF { + +using std::swap; + +template<typename RandomAccessIterator, typename Predicate> +inline void siftDown(RandomAccessIterator array, ptrdiff_t start, ptrdiff_t end, Predicate compareLess) +{ + ptrdiff_t root = start; + + while (root * 2 + 1 <= end) { + ptrdiff_t child = root * 2 + 1; + if (child < end && compareLess(array[child], array[child + 1])) + child++; + + if (compareLess(array[root], array[child])) { + swap(array[root], array[child]); + root = child; + } else + return; + } +} + +template<typename RandomAccessIterator, typename Predicate> +inline void heapify(RandomAccessIterator array, ptrdiff_t count, Predicate compareLess) +{ + ptrdiff_t start = (count - 2) / 2; + + while (start >= 0) { + siftDown(array, start, count - 1, compareLess); + start--; + } +} + +template<typename RandomAccessIterator, typename Predicate> +void heapSort(RandomAccessIterator start, RandomAccessIterator end, Predicate compareLess) +{ + ptrdiff_t count = end - start; + heapify(start, count, compareLess); + + ptrdiff_t endIndex = count - 1; + while (endIndex > 0) { + swap(start[endIndex], start[0]); + siftDown(start, 0, endIndex - 1, compareLess); + endIndex--; + } +} + +template<typename RandomAccessIterator, typename Predicate> +inline void nonCopyingSort(RandomAccessIterator start, RandomAccessIterator end, Predicate compareLess) +{ + // heapsort happens to use only swaps, not copies, but the essential thing about + // this function is the fact that it does not copy, not the specific algorithm + heapSort(start, end, compareLess); +} + +} // namespace WTF + +using WTF::nonCopyingSort; + +#endif // WTF_NonCopyingSort_h |