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 |