Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(468)

Side by Side Diff: Source/wtf/NonCopyingSort.h

Issue 20300002: Fix trailing whitespace in .cpp, .h, and .idl files (ex. Source/core) (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Created 7 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « Source/wtf/MessageQueue.h ('k') | Source/wtf/OwnArrayPtr.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
OLDNEW
« no previous file with comments | « Source/wtf/MessageQueue.h ('k') | Source/wtf/OwnArrayPtr.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698