1951a39d68df598db08dfced8b4707755864a0492Ying Wang// Heap implementation -*- C++ -*- 2951a39d68df598db08dfced8b4707755864a0492Ying Wang 343f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 4951a39d68df598db08dfced8b4707755864a0492Ying Wang// Free Software Foundation, Inc. 5951a39d68df598db08dfced8b4707755864a0492Ying Wang// 6951a39d68df598db08dfced8b4707755864a0492Ying Wang// This file is part of the GNU ISO C++ Library. This library is free 7951a39d68df598db08dfced8b4707755864a0492Ying Wang// software; you can redistribute it and/or modify it under the 8951a39d68df598db08dfced8b4707755864a0492Ying Wang// terms of the GNU General Public License as published by the 9951a39d68df598db08dfced8b4707755864a0492Ying Wang// Free Software Foundation; either version 3, or (at your option) 10951a39d68df598db08dfced8b4707755864a0492Ying Wang// any later version. 11951a39d68df598db08dfced8b4707755864a0492Ying Wang 12951a39d68df598db08dfced8b4707755864a0492Ying Wang// This library is distributed in the hope that it will be useful, 13951a39d68df598db08dfced8b4707755864a0492Ying Wang// but WITHOUT ANY WARRANTY; without even the implied warranty of 14951a39d68df598db08dfced8b4707755864a0492Ying Wang// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15951a39d68df598db08dfced8b4707755864a0492Ying Wang// GNU General Public License for more details. 16951a39d68df598db08dfced8b4707755864a0492Ying Wang 17951a39d68df598db08dfced8b4707755864a0492Ying Wang// Under Section 7 of GPL version 3, you are granted additional 18951a39d68df598db08dfced8b4707755864a0492Ying Wang// permissions described in the GCC Runtime Library Exception, version 19951a39d68df598db08dfced8b4707755864a0492Ying Wang// 3.1, as published by the Free Software Foundation. 20951a39d68df598db08dfced8b4707755864a0492Ying Wang 21951a39d68df598db08dfced8b4707755864a0492Ying Wang// You should have received a copy of the GNU General Public License and 22951a39d68df598db08dfced8b4707755864a0492Ying Wang// a copy of the GCC Runtime Library Exception along with this program; 23951a39d68df598db08dfced8b4707755864a0492Ying Wang// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24951a39d68df598db08dfced8b4707755864a0492Ying Wang// <http://www.gnu.org/licenses/>. 25951a39d68df598db08dfced8b4707755864a0492Ying Wang 26951a39d68df598db08dfced8b4707755864a0492Ying Wang/* 27951a39d68df598db08dfced8b4707755864a0492Ying Wang * 28951a39d68df598db08dfced8b4707755864a0492Ying Wang * Copyright (c) 1994 29951a39d68df598db08dfced8b4707755864a0492Ying Wang * Hewlett-Packard Company 30951a39d68df598db08dfced8b4707755864a0492Ying Wang * 31951a39d68df598db08dfced8b4707755864a0492Ying Wang * Permission to use, copy, modify, distribute and sell this software 32951a39d68df598db08dfced8b4707755864a0492Ying Wang * and its documentation for any purpose is hereby granted without fee, 33951a39d68df598db08dfced8b4707755864a0492Ying Wang * provided that the above copyright notice appear in all copies and 34951a39d68df598db08dfced8b4707755864a0492Ying Wang * that both that copyright notice and this permission notice appear 35951a39d68df598db08dfced8b4707755864a0492Ying Wang * in supporting documentation. Hewlett-Packard Company makes no 36951a39d68df598db08dfced8b4707755864a0492Ying Wang * representations about the suitability of this software for any 37951a39d68df598db08dfced8b4707755864a0492Ying Wang * purpose. It is provided "as is" without express or implied warranty. 38951a39d68df598db08dfced8b4707755864a0492Ying Wang * 39951a39d68df598db08dfced8b4707755864a0492Ying Wang * Copyright (c) 1997 40951a39d68df598db08dfced8b4707755864a0492Ying Wang * Silicon Graphics Computer Systems, Inc. 41951a39d68df598db08dfced8b4707755864a0492Ying Wang * 42951a39d68df598db08dfced8b4707755864a0492Ying Wang * Permission to use, copy, modify, distribute and sell this software 43951a39d68df598db08dfced8b4707755864a0492Ying Wang * and its documentation for any purpose is hereby granted without fee, 44951a39d68df598db08dfced8b4707755864a0492Ying Wang * provided that the above copyright notice appear in all copies and 45951a39d68df598db08dfced8b4707755864a0492Ying Wang * that both that copyright notice and this permission notice appear 46951a39d68df598db08dfced8b4707755864a0492Ying Wang * in supporting documentation. Silicon Graphics makes no 47951a39d68df598db08dfced8b4707755864a0492Ying Wang * representations about the suitability of this software for any 48951a39d68df598db08dfced8b4707755864a0492Ying Wang * purpose. It is provided "as is" without express or implied warranty. 49951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 50951a39d68df598db08dfced8b4707755864a0492Ying Wang 5143f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh/** @file bits/stl_heap.h 52951a39d68df598db08dfced8b4707755864a0492Ying Wang * This is an internal header file, included by other library headers. 5343f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh * Do not attempt to use it directly. @headername{queue} 54951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 55951a39d68df598db08dfced8b4707755864a0492Ying Wang 56951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifndef _STL_HEAP_H 57951a39d68df598db08dfced8b4707755864a0492Ying Wang#define _STL_HEAP_H 1 58951a39d68df598db08dfced8b4707755864a0492Ying Wang 59951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <debug/debug.h> 60951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <bits/move.h> 61951a39d68df598db08dfced8b4707755864a0492Ying Wang 6243f272afd56a57640c62c952f9266478bacf0244Andrew Hsiehnamespace std _GLIBCXX_VISIBILITY(default) 6343f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh{ 6443f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh_GLIBCXX_BEGIN_NAMESPACE_VERSION 65951a39d68df598db08dfced8b4707755864a0492Ying Wang 66951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 6743f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh * @defgroup heap_algorithms Heap 68951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup sorting_algorithms 69951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 70951a39d68df598db08dfced8b4707755864a0492Ying Wang 71951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance> 72951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance 73951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap_until(_RandomAccessIterator __first, _Distance __n) 74951a39d68df598db08dfced8b4707755864a0492Ying Wang { 75951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __parent = 0; 76951a39d68df598db08dfced8b4707755864a0492Ying Wang for (_Distance __child = 1; __child < __n; ++__child) 77951a39d68df598db08dfced8b4707755864a0492Ying Wang { 78951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__first[__parent] < __first[__child]) 79951a39d68df598db08dfced8b4707755864a0492Ying Wang return __child; 80951a39d68df598db08dfced8b4707755864a0492Ying Wang if ((__child & 1) == 0) 81951a39d68df598db08dfced8b4707755864a0492Ying Wang ++__parent; 82951a39d68df598db08dfced8b4707755864a0492Ying Wang } 83951a39d68df598db08dfced8b4707755864a0492Ying Wang return __n; 84951a39d68df598db08dfced8b4707755864a0492Ying Wang } 85951a39d68df598db08dfced8b4707755864a0492Ying Wang 86951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, 87951a39d68df598db08dfced8b4707755864a0492Ying Wang typename _Compare> 88951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance 89951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap_until(_RandomAccessIterator __first, _Distance __n, 90951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 91951a39d68df598db08dfced8b4707755864a0492Ying Wang { 92951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __parent = 0; 93951a39d68df598db08dfced8b4707755864a0492Ying Wang for (_Distance __child = 1; __child < __n; ++__child) 94951a39d68df598db08dfced8b4707755864a0492Ying Wang { 95951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__comp(__first[__parent], __first[__child])) 96951a39d68df598db08dfced8b4707755864a0492Ying Wang return __child; 97951a39d68df598db08dfced8b4707755864a0492Ying Wang if ((__child & 1) == 0) 98951a39d68df598db08dfced8b4707755864a0492Ying Wang ++__parent; 99951a39d68df598db08dfced8b4707755864a0492Ying Wang } 100951a39d68df598db08dfced8b4707755864a0492Ying Wang return __n; 101951a39d68df598db08dfced8b4707755864a0492Ying Wang } 102951a39d68df598db08dfced8b4707755864a0492Ying Wang 103951a39d68df598db08dfced8b4707755864a0492Ying Wang // __is_heap, a predicate testing whether or not a range is a heap. 104951a39d68df598db08dfced8b4707755864a0492Ying Wang // This function is an extension, not part of the C++ standard. 105951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance> 106951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 107951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap(_RandomAccessIterator __first, _Distance __n) 108951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::__is_heap_until(__first, __n) == __n; } 109951a39d68df598db08dfced8b4707755864a0492Ying Wang 110951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare, 111951a39d68df598db08dfced8b4707755864a0492Ying Wang typename _Distance> 112951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 113951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) 114951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::__is_heap_until(__first, __n, __comp) == __n; } 115951a39d68df598db08dfced8b4707755864a0492Ying Wang 116951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 117951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 118951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 119951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::__is_heap(__first, std::distance(__first, __last)); } 120951a39d68df598db08dfced8b4707755864a0492Ying Wang 121951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 122951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 123951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 124951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 125951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } 126951a39d68df598db08dfced8b4707755864a0492Ying Wang 127951a39d68df598db08dfced8b4707755864a0492Ying Wang // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap, 128951a39d68df598db08dfced8b4707755864a0492Ying Wang // + is_heap and is_heap_until in C++0x. 129951a39d68df598db08dfced8b4707755864a0492Ying Wang 130951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 131951a39d68df598db08dfced8b4707755864a0492Ying Wang void 132951a39d68df598db08dfced8b4707755864a0492Ying Wang __push_heap(_RandomAccessIterator __first, 133951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __holeIndex, _Distance __topIndex, _Tp __value) 134951a39d68df598db08dfced8b4707755864a0492Ying Wang { 135951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __parent = (__holeIndex - 1) / 2; 136951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__holeIndex > __topIndex && *(__first + __parent) < __value) 137951a39d68df598db08dfced8b4707755864a0492Ying Wang { 138951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 139951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __parent; 140951a39d68df598db08dfced8b4707755864a0492Ying Wang __parent = (__holeIndex - 1) / 2; 141951a39d68df598db08dfced8b4707755864a0492Ying Wang } 142951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 143951a39d68df598db08dfced8b4707755864a0492Ying Wang } 144951a39d68df598db08dfced8b4707755864a0492Ying Wang 145951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 146951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Push an element onto a heap. 147951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 148951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap + element. 149951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 150951a39d68df598db08dfced8b4707755864a0492Ying Wang * 151951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation pushes the element at last-1 onto the valid heap over the 152951a39d68df598db08dfced8b4707755864a0492Ying Wang * range [first,last-1). After completion, [first,last) is a valid heap. 153951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 154951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 155951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 156951a39d68df598db08dfced8b4707755864a0492Ying Wang push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 157951a39d68df598db08dfced8b4707755864a0492Ying Wang { 158951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 159951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 160951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 161951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 162951a39d68df598db08dfced8b4707755864a0492Ying Wang 163951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 164951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 165951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 166951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 167951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 168951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap(__first, __last - 1); 169951a39d68df598db08dfced8b4707755864a0492Ying Wang 170951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 171951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__push_heap(__first, _DistanceType((__last - __first) - 1), 172951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType(0), _GLIBCXX_MOVE(__value)); 173951a39d68df598db08dfced8b4707755864a0492Ying Wang } 174951a39d68df598db08dfced8b4707755864a0492Ying Wang 175951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 176951a39d68df598db08dfced8b4707755864a0492Ying Wang typename _Compare> 177951a39d68df598db08dfced8b4707755864a0492Ying Wang void 178951a39d68df598db08dfced8b4707755864a0492Ying Wang __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 179951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __topIndex, _Tp __value, _Compare __comp) 180951a39d68df598db08dfced8b4707755864a0492Ying Wang { 181951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __parent = (__holeIndex - 1) / 2; 182951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__holeIndex > __topIndex 183951a39d68df598db08dfced8b4707755864a0492Ying Wang && __comp(*(__first + __parent), __value)) 184951a39d68df598db08dfced8b4707755864a0492Ying Wang { 185951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 186951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __parent; 187951a39d68df598db08dfced8b4707755864a0492Ying Wang __parent = (__holeIndex - 1) / 2; 188951a39d68df598db08dfced8b4707755864a0492Ying Wang } 189951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 190951a39d68df598db08dfced8b4707755864a0492Ying Wang } 191951a39d68df598db08dfced8b4707755864a0492Ying Wang 192951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 193951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Push an element onto a heap using comparison functor. 194951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 195951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap + element. 196951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor. 197951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 198951a39d68df598db08dfced8b4707755864a0492Ying Wang * 199951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation pushes the element at last-1 onto the valid heap over the 200951a39d68df598db08dfced8b4707755864a0492Ying Wang * range [first,last-1). After completion, [first,last) is a valid heap. 201951a39d68df598db08dfced8b4707755864a0492Ying Wang * Compare operations are performed using comp. 202951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 203951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 204951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 205951a39d68df598db08dfced8b4707755864a0492Ying Wang push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 206951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 207951a39d68df598db08dfced8b4707755864a0492Ying Wang { 208951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 209951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 210951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 211951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 212951a39d68df598db08dfced8b4707755864a0492Ying Wang 213951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 214951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 215951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 216951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 217951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap_pred(__first, __last - 1, __comp); 218951a39d68df598db08dfced8b4707755864a0492Ying Wang 219951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 220951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__push_heap(__first, _DistanceType((__last - __first) - 1), 221951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); 222951a39d68df598db08dfced8b4707755864a0492Ying Wang } 223951a39d68df598db08dfced8b4707755864a0492Ying Wang 224951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 225951a39d68df598db08dfced8b4707755864a0492Ying Wang void 226951a39d68df598db08dfced8b4707755864a0492Ying Wang __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 227951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __len, _Tp __value) 228951a39d68df598db08dfced8b4707755864a0492Ying Wang { 229951a39d68df598db08dfced8b4707755864a0492Ying Wang const _Distance __topIndex = __holeIndex; 230951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __secondChild = __holeIndex; 231951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__secondChild < (__len - 1) / 2) 232951a39d68df598db08dfced8b4707755864a0492Ying Wang { 233951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild = 2 * (__secondChild + 1); 234951a39d68df598db08dfced8b4707755864a0492Ying Wang if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) 235951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild--; 236951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 237951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __secondChild; 238951a39d68df598db08dfced8b4707755864a0492Ying Wang } 239951a39d68df598db08dfced8b4707755864a0492Ying Wang if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 240951a39d68df598db08dfced8b4707755864a0492Ying Wang { 241951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild = 2 * (__secondChild + 1); 242951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 243951a39d68df598db08dfced8b4707755864a0492Ying Wang + (__secondChild - 1))); 244951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __secondChild - 1; 245951a39d68df598db08dfced8b4707755864a0492Ying Wang } 246951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__push_heap(__first, __holeIndex, __topIndex, 247951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_MOVE(__value)); 248951a39d68df598db08dfced8b4707755864a0492Ying Wang } 249951a39d68df598db08dfced8b4707755864a0492Ying Wang 250951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 251951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 252951a39d68df598db08dfced8b4707755864a0492Ying Wang __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 253951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator __result) 254951a39d68df598db08dfced8b4707755864a0492Ying Wang { 255951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 256951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 257951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 258951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 259951a39d68df598db08dfced8b4707755864a0492Ying Wang 260951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*__result); 261951a39d68df598db08dfced8b4707755864a0492Ying Wang *__result = _GLIBCXX_MOVE(*__first); 262951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__adjust_heap(__first, _DistanceType(0), 263951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType(__last - __first), 264951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_MOVE(__value)); 265951a39d68df598db08dfced8b4707755864a0492Ying Wang } 266951a39d68df598db08dfced8b4707755864a0492Ying Wang 267951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 268951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Pop an element off a heap. 269951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 270951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 271951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 272951a39d68df598db08dfced8b4707755864a0492Ying Wang * 273951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation pops the top of the heap. The elements first and last-1 274951a39d68df598db08dfced8b4707755864a0492Ying Wang * are swapped and [first,last-1) is made into a heap. 275951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 276951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 277951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 278951a39d68df598db08dfced8b4707755864a0492Ying Wang pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 279951a39d68df598db08dfced8b4707755864a0492Ying Wang { 280951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 281951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 282951a39d68df598db08dfced8b4707755864a0492Ying Wang 283951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 284951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 285951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 286951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 287951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 288951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap(__first, __last); 289951a39d68df598db08dfced8b4707755864a0492Ying Wang 290951a39d68df598db08dfced8b4707755864a0492Ying Wang --__last; 291951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__pop_heap(__first, __last, __last); 292951a39d68df598db08dfced8b4707755864a0492Ying Wang } 293951a39d68df598db08dfced8b4707755864a0492Ying Wang 294951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, 295951a39d68df598db08dfced8b4707755864a0492Ying Wang typename _Tp, typename _Compare> 296951a39d68df598db08dfced8b4707755864a0492Ying Wang void 297951a39d68df598db08dfced8b4707755864a0492Ying Wang __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 298951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __len, _Tp __value, _Compare __comp) 299951a39d68df598db08dfced8b4707755864a0492Ying Wang { 300951a39d68df598db08dfced8b4707755864a0492Ying Wang const _Distance __topIndex = __holeIndex; 301951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __secondChild = __holeIndex; 302951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__secondChild < (__len - 1) / 2) 303951a39d68df598db08dfced8b4707755864a0492Ying Wang { 304951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild = 2 * (__secondChild + 1); 305951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__comp(*(__first + __secondChild), 306951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + (__secondChild - 1)))) 307951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild--; 308951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 309951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __secondChild; 310951a39d68df598db08dfced8b4707755864a0492Ying Wang } 311951a39d68df598db08dfced8b4707755864a0492Ying Wang if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 312951a39d68df598db08dfced8b4707755864a0492Ying Wang { 313951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild = 2 * (__secondChild + 1); 314951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 315951a39d68df598db08dfced8b4707755864a0492Ying Wang + (__secondChild - 1))); 316951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __secondChild - 1; 317951a39d68df598db08dfced8b4707755864a0492Ying Wang } 318951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__push_heap(__first, __holeIndex, __topIndex, 319951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_MOVE(__value), __comp); 320951a39d68df598db08dfced8b4707755864a0492Ying Wang } 321951a39d68df598db08dfced8b4707755864a0492Ying Wang 322951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 323951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 324951a39d68df598db08dfced8b4707755864a0492Ying Wang __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 325951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator __result, _Compare __comp) 326951a39d68df598db08dfced8b4707755864a0492Ying Wang { 327951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 328951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 329951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 330951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 331951a39d68df598db08dfced8b4707755864a0492Ying Wang 332951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*__result); 333951a39d68df598db08dfced8b4707755864a0492Ying Wang *__result = _GLIBCXX_MOVE(*__first); 334951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__adjust_heap(__first, _DistanceType(0), 335951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType(__last - __first), 336951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_MOVE(__value), __comp); 337951a39d68df598db08dfced8b4707755864a0492Ying Wang } 338951a39d68df598db08dfced8b4707755864a0492Ying Wang 339951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 340951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Pop an element off a heap using comparison functor. 341951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 342951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 343951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 344951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 345951a39d68df598db08dfced8b4707755864a0492Ying Wang * 346951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation pops the top of the heap. The elements first and last-1 347951a39d68df598db08dfced8b4707755864a0492Ying Wang * are swapped and [first,last-1) is made into a heap. Comparisons are 348951a39d68df598db08dfced8b4707755864a0492Ying Wang * made using comp. 349951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 350951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 351951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 352951a39d68df598db08dfced8b4707755864a0492Ying Wang pop_heap(_RandomAccessIterator __first, 353951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator __last, _Compare __comp) 354951a39d68df598db08dfced8b4707755864a0492Ying Wang { 355951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 356951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 357951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 358951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 359951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap_pred(__first, __last, __comp); 360951a39d68df598db08dfced8b4707755864a0492Ying Wang 361951a39d68df598db08dfced8b4707755864a0492Ying Wang --__last; 362951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__pop_heap(__first, __last, __last, __comp); 363951a39d68df598db08dfced8b4707755864a0492Ying Wang } 364951a39d68df598db08dfced8b4707755864a0492Ying Wang 365951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 366951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Construct a heap over a range. 367951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 368951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 369951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 370951a39d68df598db08dfced8b4707755864a0492Ying Wang * 371951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation makes the elements in [first,last) into a heap. 372951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 373951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 374951a39d68df598db08dfced8b4707755864a0492Ying Wang void 375951a39d68df598db08dfced8b4707755864a0492Ying Wang make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 376951a39d68df598db08dfced8b4707755864a0492Ying Wang { 377951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 378951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 379951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 380951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 381951a39d68df598db08dfced8b4707755864a0492Ying Wang 382951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 383951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 384951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 385951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 386951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 387951a39d68df598db08dfced8b4707755864a0492Ying Wang 388951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__last - __first < 2) 389951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 390951a39d68df598db08dfced8b4707755864a0492Ying Wang 391951a39d68df598db08dfced8b4707755864a0492Ying Wang const _DistanceType __len = __last - __first; 392951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType __parent = (__len - 2) / 2; 393951a39d68df598db08dfced8b4707755864a0492Ying Wang while (true) 394951a39d68df598db08dfced8b4707755864a0492Ying Wang { 395951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 396951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value)); 397951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__parent == 0) 398951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 399951a39d68df598db08dfced8b4707755864a0492Ying Wang __parent--; 400951a39d68df598db08dfced8b4707755864a0492Ying Wang } 401951a39d68df598db08dfced8b4707755864a0492Ying Wang } 402951a39d68df598db08dfced8b4707755864a0492Ying Wang 403951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 404951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Construct a heap over a range using comparison functor. 405951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 406951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 407951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 408951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 409951a39d68df598db08dfced8b4707755864a0492Ying Wang * 410951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation makes the elements in [first,last) into a heap. 411951a39d68df598db08dfced8b4707755864a0492Ying Wang * Comparisons are made using comp. 412951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 413951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 414951a39d68df598db08dfced8b4707755864a0492Ying Wang void 415951a39d68df598db08dfced8b4707755864a0492Ying Wang make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 416951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 417951a39d68df598db08dfced8b4707755864a0492Ying Wang { 418951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 419951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 420951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 421951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 422951a39d68df598db08dfced8b4707755864a0492Ying Wang 423951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 424951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 425951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 426951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 427951a39d68df598db08dfced8b4707755864a0492Ying Wang 428951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__last - __first < 2) 429951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 430951a39d68df598db08dfced8b4707755864a0492Ying Wang 431951a39d68df598db08dfced8b4707755864a0492Ying Wang const _DistanceType __len = __last - __first; 432951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType __parent = (__len - 2) / 2; 433951a39d68df598db08dfced8b4707755864a0492Ying Wang while (true) 434951a39d68df598db08dfced8b4707755864a0492Ying Wang { 435951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 436951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), 437951a39d68df598db08dfced8b4707755864a0492Ying Wang __comp); 438951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__parent == 0) 439951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 440951a39d68df598db08dfced8b4707755864a0492Ying Wang __parent--; 441951a39d68df598db08dfced8b4707755864a0492Ying Wang } 442951a39d68df598db08dfced8b4707755864a0492Ying Wang } 443951a39d68df598db08dfced8b4707755864a0492Ying Wang 444951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 445951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Sort a heap. 446951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 447951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 448951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 449951a39d68df598db08dfced8b4707755864a0492Ying Wang * 450951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation sorts the valid heap in the range [first,last). 451951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 452951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 453951a39d68df598db08dfced8b4707755864a0492Ying Wang void 454951a39d68df598db08dfced8b4707755864a0492Ying Wang sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 455951a39d68df598db08dfced8b4707755864a0492Ying Wang { 456951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 457951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 458951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 459951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept< 460951a39d68df598db08dfced8b4707755864a0492Ying Wang typename iterator_traits<_RandomAccessIterator>::value_type>) 461951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 462951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap(__first, __last); 463951a39d68df598db08dfced8b4707755864a0492Ying Wang 464951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__last - __first > 1) 465951a39d68df598db08dfced8b4707755864a0492Ying Wang { 466951a39d68df598db08dfced8b4707755864a0492Ying Wang --__last; 467951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__pop_heap(__first, __last, __last); 468951a39d68df598db08dfced8b4707755864a0492Ying Wang } 469951a39d68df598db08dfced8b4707755864a0492Ying Wang } 470951a39d68df598db08dfced8b4707755864a0492Ying Wang 471951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 472951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Sort a heap using comparison functor. 473951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 474951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 475951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 476951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 477951a39d68df598db08dfced8b4707755864a0492Ying Wang * 478951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation sorts the valid heap in the range [first,last). 479951a39d68df598db08dfced8b4707755864a0492Ying Wang * Comparisons are made using comp. 480951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 481951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 482951a39d68df598db08dfced8b4707755864a0492Ying Wang void 483951a39d68df598db08dfced8b4707755864a0492Ying Wang sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 484951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 485951a39d68df598db08dfced8b4707755864a0492Ying Wang { 486951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 487951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 488951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 489951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 490951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap_pred(__first, __last, __comp); 491951a39d68df598db08dfced8b4707755864a0492Ying Wang 492951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__last - __first > 1) 493951a39d68df598db08dfced8b4707755864a0492Ying Wang { 494951a39d68df598db08dfced8b4707755864a0492Ying Wang --__last; 495951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__pop_heap(__first, __last, __last, __comp); 496951a39d68df598db08dfced8b4707755864a0492Ying Wang } 497951a39d68df598db08dfced8b4707755864a0492Ying Wang } 498951a39d68df598db08dfced8b4707755864a0492Ying Wang 499951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef __GXX_EXPERIMENTAL_CXX0X__ 500951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 501951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Search the end of a heap. 502951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of range. 503951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of range. 504951a39d68df598db08dfced8b4707755864a0492Ying Wang * @return An iterator pointing to the first element not in the heap. 505951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 506951a39d68df598db08dfced8b4707755864a0492Ying Wang * 507951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation returns the last iterator i in [first, last) for which 508951a39d68df598db08dfced8b4707755864a0492Ying Wang * the range [first, i) is a heap. 509951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 510951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 511951a39d68df598db08dfced8b4707755864a0492Ying Wang inline _RandomAccessIterator 512951a39d68df598db08dfced8b4707755864a0492Ying Wang is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 513951a39d68df598db08dfced8b4707755864a0492Ying Wang { 514951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 515951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_RandomAccessIteratorConcept< 516951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 517951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept< 518951a39d68df598db08dfced8b4707755864a0492Ying Wang typename iterator_traits<_RandomAccessIterator>::value_type>) 519951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 520951a39d68df598db08dfced8b4707755864a0492Ying Wang 521951a39d68df598db08dfced8b4707755864a0492Ying Wang return __first + std::__is_heap_until(__first, std::distance(__first, 522951a39d68df598db08dfced8b4707755864a0492Ying Wang __last)); 523951a39d68df598db08dfced8b4707755864a0492Ying Wang } 524951a39d68df598db08dfced8b4707755864a0492Ying Wang 525951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 526951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Search the end of a heap using comparison functor. 527951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of range. 528951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of range. 529951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 530951a39d68df598db08dfced8b4707755864a0492Ying Wang * @return An iterator pointing to the first element not in the heap. 531951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 532951a39d68df598db08dfced8b4707755864a0492Ying Wang * 533951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation returns the last iterator i in [first, last) for which 534951a39d68df598db08dfced8b4707755864a0492Ying Wang * the range [first, i) is a heap. Comparisons are made using comp. 535951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 536951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 537951a39d68df598db08dfced8b4707755864a0492Ying Wang inline _RandomAccessIterator 538951a39d68df598db08dfced8b4707755864a0492Ying Wang is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, 539951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 540951a39d68df598db08dfced8b4707755864a0492Ying Wang { 541951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 542951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_RandomAccessIteratorConcept< 543951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 544951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 545951a39d68df598db08dfced8b4707755864a0492Ying Wang 546951a39d68df598db08dfced8b4707755864a0492Ying Wang return __first + std::__is_heap_until(__first, std::distance(__first, 547951a39d68df598db08dfced8b4707755864a0492Ying Wang __last), 548951a39d68df598db08dfced8b4707755864a0492Ying Wang __comp); 549951a39d68df598db08dfced8b4707755864a0492Ying Wang } 550951a39d68df598db08dfced8b4707755864a0492Ying Wang 551951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 552951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Determines whether a range is a heap. 553951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of range. 554951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of range. 555951a39d68df598db08dfced8b4707755864a0492Ying Wang * @return True if range is a heap, false otherwise. 556951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 557951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 558951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 559951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 560951a39d68df598db08dfced8b4707755864a0492Ying Wang is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 561951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::is_heap_until(__first, __last) == __last; } 562951a39d68df598db08dfced8b4707755864a0492Ying Wang 563951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 564951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Determines whether a range is a heap using comparison functor. 565951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of range. 566951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of range. 567951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 568951a39d68df598db08dfced8b4707755864a0492Ying Wang * @return True if range is a heap, false otherwise. 569951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 570951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 571951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 572951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 573951a39d68df598db08dfced8b4707755864a0492Ying Wang is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 574951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 575951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::is_heap_until(__first, __last, __comp) == __last; } 576951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 577951a39d68df598db08dfced8b4707755864a0492Ying Wang 57843f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh_GLIBCXX_END_NAMESPACE_VERSION 57943f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh} // namespace 580951a39d68df598db08dfced8b4707755864a0492Ying Wang 581951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif /* _STL_HEAP_H */ 582