| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2010 Apple Inc. All Rights Reserved. | 2 * Copyright (C) 2010 Apple Inc. All Rights Reserved. |
| 3 * | 3 * |
| 4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
| 5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
| 6 * are met: | 6 * are met: |
| 7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
| 8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
| 9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
| 10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
| 11 * documentation and/or other materials provided with the distribution. | 11 * documentation and/or other materials provided with the distribution. |
| 12 * | 12 * |
| 13 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY | 13 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY |
| 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR | 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR |
| 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 24 * | 24 * |
| 25 */ | 25 */ |
| 26 | 26 |
| 27 #ifndef WTF_NonCopyingSort_h | 27 #ifndef WTF_NonCopyingSort_h |
| 28 #define WTF_NonCopyingSort_h | 28 #define WTF_NonCopyingSort_h |
| 29 | 29 |
| 30 namespace WTF { | 30 namespace WTF { |
| 31 | 31 |
| 32 using std::swap; | 32 using std::swap; |
| 33 | 33 |
| 34 template<typename RandomAccessIterator, typename Predicate> | 34 template<typename RandomAccessIterator, typename Predicate> |
| 35 inline void siftDown(RandomAccessIterator array, ptrdiff_t start, ptrdiff_t end,
Predicate compareLess) | 35 inline void siftDown(RandomAccessIterator array, ptrdiff_t start, ptrdiff_t end,
Predicate compareLess) |
| 36 { | 36 { |
| 37 ptrdiff_t root = start; | 37 ptrdiff_t root = start; |
| 38 | 38 |
| 39 while (root * 2 + 1 <= end) { | 39 while (root * 2 + 1 <= end) { |
| 40 ptrdiff_t child = root * 2 + 1; | 40 ptrdiff_t child = root * 2 + 1; |
| 41 if (child < end && compareLess(array[child], array[child + 1])) | 41 if (child < end && compareLess(array[child], array[child + 1])) |
| 42 child++; | 42 child++; |
| 43 | 43 |
| 44 if (compareLess(array[root], array[child])) { | 44 if (compareLess(array[root], array[child])) { |
| 45 swap(array[root], array[child]); | 45 swap(array[root], array[child]); |
| 46 root = child; | 46 root = child; |
| 47 } else | 47 } else |
| 48 return; | 48 return; |
| 49 } | 49 } |
| 50 } | 50 } |
| 51 | 51 |
| 52 template<typename RandomAccessIterator, typename Predicate> | 52 template<typename RandomAccessIterator, typename Predicate> |
| 53 inline void heapify(RandomAccessIterator array, ptrdiff_t count, Predicate compa
reLess) | 53 inline void heapify(RandomAccessIterator array, ptrdiff_t count, Predicate compa
reLess) |
| 54 { | 54 { |
| 55 ptrdiff_t start = (count - 2) / 2; | 55 ptrdiff_t start = (count - 2) / 2; |
| 56 | 56 |
| 57 while (start >= 0) { | 57 while (start >= 0) { |
| 58 siftDown(array, start, count - 1, compareLess); | 58 siftDown(array, start, count - 1, compareLess); |
| 59 start--; | 59 start--; |
| 60 } | 60 } |
| 61 } | 61 } |
| 62 | 62 |
| 63 template<typename RandomAccessIterator, typename Predicate> | 63 template<typename RandomAccessIterator, typename Predicate> |
| 64 void heapSort(RandomAccessIterator start, RandomAccessIterator end, Predicate co
mpareLess) | 64 void heapSort(RandomAccessIterator start, RandomAccessIterator end, Predicate co
mpareLess) |
| 65 { | 65 { |
| 66 ptrdiff_t count = end - start; | 66 ptrdiff_t count = end - start; |
| (...skipping 13 matching lines...) Expand all Loading... |
| 80 // heapsort happens to use only swaps, not copies, but the essential thing a
bout | 80 // heapsort happens to use only swaps, not copies, but the essential thing a
bout |
| 81 // this function is the fact that it does not copy, not the specific algorit
hm | 81 // this function is the fact that it does not copy, not the specific algorit
hm |
| 82 heapSort(start, end, compareLess); | 82 heapSort(start, end, compareLess); |
| 83 } | 83 } |
| 84 | 84 |
| 85 } // namespace WTF | 85 } // namespace WTF |
| 86 | 86 |
| 87 using WTF::nonCopyingSort; | 87 using WTF::nonCopyingSort; |
| 88 | 88 |
| 89 #endif // WTF_NonCopyingSort_h | 89 #endif // WTF_NonCopyingSort_h |
| OLD | NEW |