15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2010 Apple Inc. All Rights Reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met: 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer in the 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * documentation and/or other materials provided with the distribution. 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef WTF_NonCopyingSort_h 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define WTF_NonCopyingSort_h 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using std::swap; 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<typename RandomAccessIterator, typename Predicate> 3502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdochinline void siftDown(RandomAccessIterator array, ptrdiff_t start, ptrdiff_t end, Predicate compareLess) 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ptrdiff_t root = start; 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (root * 2 + 1 <= end) { 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ptrdiff_t child = root * 2 + 1; 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (child < end && compareLess(array[child], array[child + 1])) 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) child++; 4302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (compareLess(array[root], array[child])) { 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) swap(array[root], array[child]); 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) root = child; 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<typename RandomAccessIterator, typename Predicate> 5302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdochinline void heapify(RandomAccessIterator array, ptrdiff_t count, Predicate compareLess) 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ptrdiff_t start = (count - 2) / 2; 5602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (start >= 0) { 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) siftDown(array, start, count - 1, compareLess); 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) start--; 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<typename RandomAccessIterator, typename Predicate> 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void heapSort(RandomAccessIterator start, RandomAccessIterator end, Predicate compareLess) 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ptrdiff_t count = end - start; 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) heapify(start, count, compareLess); 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ptrdiff_t endIndex = count - 1; 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (endIndex > 0) { 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) swap(start[endIndex], start[0]); 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) siftDown(start, 0, endIndex - 1, compareLess); 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) endIndex--; 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<typename RandomAccessIterator, typename Predicate> 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)inline void nonCopyingSort(RandomAccessIterator start, RandomAccessIterator end, Predicate compareLess) 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // heapsort happens to use only swaps, not copies, but the essential thing about 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // this function is the fact that it does not copy, not the specific algorithm 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) heapSort(start, end, compareLess); 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using WTF::nonCopyingSort; 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // WTF_NonCopyingSort_h 90