1951a39d68df598db08dfced8b4707755864a0492Ying Wang// Heap implementation -*- C++ -*- 2951a39d68df598db08dfced8b4707755864a0492Ying Wang 3951a39d68df598db08dfced8b4707755864a0492Ying Wang// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 51951a39d68df598db08dfced8b4707755864a0492Ying Wang/** @file stl_heap.h 52951a39d68df598db08dfced8b4707755864a0492Ying Wang * This is an internal header file, included by other library headers. 53951a39d68df598db08dfced8b4707755864a0492Ying Wang * You should not attempt to use it directly. 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 62951a39d68df598db08dfced8b4707755864a0492Ying Wang_GLIBCXX_BEGIN_NAMESPACE(std) 63951a39d68df598db08dfced8b4707755864a0492Ying Wang 64951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 65951a39d68df598db08dfced8b4707755864a0492Ying Wang * @defgroup heap_algorithms Heap Algorithms 66951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup sorting_algorithms 67951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 68951a39d68df598db08dfced8b4707755864a0492Ying Wang 69951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance> 70951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance 71951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap_until(_RandomAccessIterator __first, _Distance __n) 72951a39d68df598db08dfced8b4707755864a0492Ying Wang { 73951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __parent = 0; 74951a39d68df598db08dfced8b4707755864a0492Ying Wang for (_Distance __child = 1; __child < __n; ++__child) 75951a39d68df598db08dfced8b4707755864a0492Ying Wang { 76951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__first[__parent] < __first[__child]) 77951a39d68df598db08dfced8b4707755864a0492Ying Wang return __child; 78951a39d68df598db08dfced8b4707755864a0492Ying Wang if ((__child & 1) == 0) 79951a39d68df598db08dfced8b4707755864a0492Ying Wang ++__parent; 80951a39d68df598db08dfced8b4707755864a0492Ying Wang } 81951a39d68df598db08dfced8b4707755864a0492Ying Wang return __n; 82951a39d68df598db08dfced8b4707755864a0492Ying Wang } 83951a39d68df598db08dfced8b4707755864a0492Ying Wang 84951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, 85951a39d68df598db08dfced8b4707755864a0492Ying Wang typename _Compare> 86951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance 87951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap_until(_RandomAccessIterator __first, _Distance __n, 88951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 89951a39d68df598db08dfced8b4707755864a0492Ying Wang { 90951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __parent = 0; 91951a39d68df598db08dfced8b4707755864a0492Ying Wang for (_Distance __child = 1; __child < __n; ++__child) 92951a39d68df598db08dfced8b4707755864a0492Ying Wang { 93951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__comp(__first[__parent], __first[__child])) 94951a39d68df598db08dfced8b4707755864a0492Ying Wang return __child; 95951a39d68df598db08dfced8b4707755864a0492Ying Wang if ((__child & 1) == 0) 96951a39d68df598db08dfced8b4707755864a0492Ying Wang ++__parent; 97951a39d68df598db08dfced8b4707755864a0492Ying Wang } 98951a39d68df598db08dfced8b4707755864a0492Ying Wang return __n; 99951a39d68df598db08dfced8b4707755864a0492Ying Wang } 100951a39d68df598db08dfced8b4707755864a0492Ying Wang 101951a39d68df598db08dfced8b4707755864a0492Ying Wang // __is_heap, a predicate testing whether or not a range is a heap. 102951a39d68df598db08dfced8b4707755864a0492Ying Wang // This function is an extension, not part of the C++ standard. 103951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance> 104951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 105951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap(_RandomAccessIterator __first, _Distance __n) 106951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::__is_heap_until(__first, __n) == __n; } 107951a39d68df598db08dfced8b4707755864a0492Ying Wang 108951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare, 109951a39d68df598db08dfced8b4707755864a0492Ying Wang typename _Distance> 110951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 111951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) 112951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::__is_heap_until(__first, __n, __comp) == __n; } 113951a39d68df598db08dfced8b4707755864a0492Ying Wang 114951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 115951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 116951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 117951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::__is_heap(__first, std::distance(__first, __last)); } 118951a39d68df598db08dfced8b4707755864a0492Ying Wang 119951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 120951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 121951a39d68df598db08dfced8b4707755864a0492Ying Wang __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 122951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 123951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } 124951a39d68df598db08dfced8b4707755864a0492Ying Wang 125951a39d68df598db08dfced8b4707755864a0492Ying Wang // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap, 126951a39d68df598db08dfced8b4707755864a0492Ying Wang // + is_heap and is_heap_until in C++0x. 127951a39d68df598db08dfced8b4707755864a0492Ying Wang 128951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 129951a39d68df598db08dfced8b4707755864a0492Ying Wang void 130951a39d68df598db08dfced8b4707755864a0492Ying Wang __push_heap(_RandomAccessIterator __first, 131951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __holeIndex, _Distance __topIndex, _Tp __value) 132951a39d68df598db08dfced8b4707755864a0492Ying Wang { 133951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __parent = (__holeIndex - 1) / 2; 134951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__holeIndex > __topIndex && *(__first + __parent) < __value) 135951a39d68df598db08dfced8b4707755864a0492Ying Wang { 136951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 137951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __parent; 138951a39d68df598db08dfced8b4707755864a0492Ying Wang __parent = (__holeIndex - 1) / 2; 139951a39d68df598db08dfced8b4707755864a0492Ying Wang } 140951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 141951a39d68df598db08dfced8b4707755864a0492Ying Wang } 142951a39d68df598db08dfced8b4707755864a0492Ying Wang 143951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 144951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Push an element onto a heap. 145951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 146951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap + element. 147951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 148951a39d68df598db08dfced8b4707755864a0492Ying Wang * 149951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation pushes the element at last-1 onto the valid heap over the 150951a39d68df598db08dfced8b4707755864a0492Ying Wang * range [first,last-1). After completion, [first,last) is a valid heap. 151951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 152951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 153951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 154951a39d68df598db08dfced8b4707755864a0492Ying Wang push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 155951a39d68df598db08dfced8b4707755864a0492Ying Wang { 156951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 157951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 158951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 159951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 160951a39d68df598db08dfced8b4707755864a0492Ying Wang 161951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 162951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 163951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 164951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 165951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 166951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap(__first, __last - 1); 167951a39d68df598db08dfced8b4707755864a0492Ying Wang 168951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 169951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__push_heap(__first, _DistanceType((__last - __first) - 1), 170951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType(0), _GLIBCXX_MOVE(__value)); 171951a39d68df598db08dfced8b4707755864a0492Ying Wang } 172951a39d68df598db08dfced8b4707755864a0492Ying Wang 173951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 174951a39d68df598db08dfced8b4707755864a0492Ying Wang typename _Compare> 175951a39d68df598db08dfced8b4707755864a0492Ying Wang void 176951a39d68df598db08dfced8b4707755864a0492Ying Wang __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 177951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __topIndex, _Tp __value, _Compare __comp) 178951a39d68df598db08dfced8b4707755864a0492Ying Wang { 179951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __parent = (__holeIndex - 1) / 2; 180951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__holeIndex > __topIndex 181951a39d68df598db08dfced8b4707755864a0492Ying Wang && __comp(*(__first + __parent), __value)) 182951a39d68df598db08dfced8b4707755864a0492Ying Wang { 183951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 184951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __parent; 185951a39d68df598db08dfced8b4707755864a0492Ying Wang __parent = (__holeIndex - 1) / 2; 186951a39d68df598db08dfced8b4707755864a0492Ying Wang } 187951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 188951a39d68df598db08dfced8b4707755864a0492Ying Wang } 189951a39d68df598db08dfced8b4707755864a0492Ying Wang 190951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 191951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Push an element onto a heap using comparison functor. 192951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 193951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap + element. 194951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor. 195951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 196951a39d68df598db08dfced8b4707755864a0492Ying Wang * 197951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation pushes the element at last-1 onto the valid heap over the 198951a39d68df598db08dfced8b4707755864a0492Ying Wang * range [first,last-1). After completion, [first,last) is a valid heap. 199951a39d68df598db08dfced8b4707755864a0492Ying Wang * Compare operations are performed using comp. 200951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 201951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 202951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 203951a39d68df598db08dfced8b4707755864a0492Ying Wang push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 204951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 205951a39d68df598db08dfced8b4707755864a0492Ying Wang { 206951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 207951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 208951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 209951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 210951a39d68df598db08dfced8b4707755864a0492Ying Wang 211951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 212951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 213951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 214951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 215951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap_pred(__first, __last - 1, __comp); 216951a39d68df598db08dfced8b4707755864a0492Ying Wang 217951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 218951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__push_heap(__first, _DistanceType((__last - __first) - 1), 219951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); 220951a39d68df598db08dfced8b4707755864a0492Ying Wang } 221951a39d68df598db08dfced8b4707755864a0492Ying Wang 222951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 223951a39d68df598db08dfced8b4707755864a0492Ying Wang void 224951a39d68df598db08dfced8b4707755864a0492Ying Wang __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 225951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __len, _Tp __value) 226951a39d68df598db08dfced8b4707755864a0492Ying Wang { 227951a39d68df598db08dfced8b4707755864a0492Ying Wang const _Distance __topIndex = __holeIndex; 228951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __secondChild = __holeIndex; 229951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__secondChild < (__len - 1) / 2) 230951a39d68df598db08dfced8b4707755864a0492Ying Wang { 231951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild = 2 * (__secondChild + 1); 232951a39d68df598db08dfced8b4707755864a0492Ying Wang if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) 233951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild--; 234951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 235951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __secondChild; 236951a39d68df598db08dfced8b4707755864a0492Ying Wang } 237951a39d68df598db08dfced8b4707755864a0492Ying Wang if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 238951a39d68df598db08dfced8b4707755864a0492Ying Wang { 239951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild = 2 * (__secondChild + 1); 240951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 241951a39d68df598db08dfced8b4707755864a0492Ying Wang + (__secondChild - 1))); 242951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __secondChild - 1; 243951a39d68df598db08dfced8b4707755864a0492Ying Wang } 244951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__push_heap(__first, __holeIndex, __topIndex, 245951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_MOVE(__value)); 246951a39d68df598db08dfced8b4707755864a0492Ying Wang } 247951a39d68df598db08dfced8b4707755864a0492Ying Wang 248951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 249951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 250951a39d68df598db08dfced8b4707755864a0492Ying Wang __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 251951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator __result) 252951a39d68df598db08dfced8b4707755864a0492Ying Wang { 253951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 254951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 255951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 256951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 257951a39d68df598db08dfced8b4707755864a0492Ying Wang 258951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*__result); 259951a39d68df598db08dfced8b4707755864a0492Ying Wang *__result = _GLIBCXX_MOVE(*__first); 260951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__adjust_heap(__first, _DistanceType(0), 261951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType(__last - __first), 262951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_MOVE(__value)); 263951a39d68df598db08dfced8b4707755864a0492Ying Wang } 264951a39d68df598db08dfced8b4707755864a0492Ying Wang 265951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 266951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Pop an element off a heap. 267951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 268951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 269951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 270951a39d68df598db08dfced8b4707755864a0492Ying Wang * 271951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation pops the top of the heap. The elements first and last-1 272951a39d68df598db08dfced8b4707755864a0492Ying Wang * are swapped and [first,last-1) is made into a heap. 273951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 274951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 275951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 276951a39d68df598db08dfced8b4707755864a0492Ying Wang pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 277951a39d68df598db08dfced8b4707755864a0492Ying Wang { 278951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 279951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 280951a39d68df598db08dfced8b4707755864a0492Ying Wang 281951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 282951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 283951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 284951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 285951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 286951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap(__first, __last); 287951a39d68df598db08dfced8b4707755864a0492Ying Wang 288951a39d68df598db08dfced8b4707755864a0492Ying Wang --__last; 289951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__pop_heap(__first, __last, __last); 290951a39d68df598db08dfced8b4707755864a0492Ying Wang } 291951a39d68df598db08dfced8b4707755864a0492Ying Wang 292951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Distance, 293951a39d68df598db08dfced8b4707755864a0492Ying Wang typename _Tp, typename _Compare> 294951a39d68df598db08dfced8b4707755864a0492Ying Wang void 295951a39d68df598db08dfced8b4707755864a0492Ying Wang __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 296951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __len, _Tp __value, _Compare __comp) 297951a39d68df598db08dfced8b4707755864a0492Ying Wang { 298951a39d68df598db08dfced8b4707755864a0492Ying Wang const _Distance __topIndex = __holeIndex; 299951a39d68df598db08dfced8b4707755864a0492Ying Wang _Distance __secondChild = __holeIndex; 300951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__secondChild < (__len - 1) / 2) 301951a39d68df598db08dfced8b4707755864a0492Ying Wang { 302951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild = 2 * (__secondChild + 1); 303951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__comp(*(__first + __secondChild), 304951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + (__secondChild - 1)))) 305951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild--; 306951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 307951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __secondChild; 308951a39d68df598db08dfced8b4707755864a0492Ying Wang } 309951a39d68df598db08dfced8b4707755864a0492Ying Wang if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 310951a39d68df598db08dfced8b4707755864a0492Ying Wang { 311951a39d68df598db08dfced8b4707755864a0492Ying Wang __secondChild = 2 * (__secondChild + 1); 312951a39d68df598db08dfced8b4707755864a0492Ying Wang *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 313951a39d68df598db08dfced8b4707755864a0492Ying Wang + (__secondChild - 1))); 314951a39d68df598db08dfced8b4707755864a0492Ying Wang __holeIndex = __secondChild - 1; 315951a39d68df598db08dfced8b4707755864a0492Ying Wang } 316951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__push_heap(__first, __holeIndex, __topIndex, 317951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_MOVE(__value), __comp); 318951a39d68df598db08dfced8b4707755864a0492Ying Wang } 319951a39d68df598db08dfced8b4707755864a0492Ying Wang 320951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 321951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 322951a39d68df598db08dfced8b4707755864a0492Ying Wang __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 323951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator __result, _Compare __comp) 324951a39d68df598db08dfced8b4707755864a0492Ying Wang { 325951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 326951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 327951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 328951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 329951a39d68df598db08dfced8b4707755864a0492Ying Wang 330951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*__result); 331951a39d68df598db08dfced8b4707755864a0492Ying Wang *__result = _GLIBCXX_MOVE(*__first); 332951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__adjust_heap(__first, _DistanceType(0), 333951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType(__last - __first), 334951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_MOVE(__value), __comp); 335951a39d68df598db08dfced8b4707755864a0492Ying Wang } 336951a39d68df598db08dfced8b4707755864a0492Ying Wang 337951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 338951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Pop an element off a heap using comparison functor. 339951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 340951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 341951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 342951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 343951a39d68df598db08dfced8b4707755864a0492Ying Wang * 344951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation pops the top of the heap. The elements first and last-1 345951a39d68df598db08dfced8b4707755864a0492Ying Wang * are swapped and [first,last-1) is made into a heap. Comparisons are 346951a39d68df598db08dfced8b4707755864a0492Ying Wang * made using comp. 347951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 348951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 349951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 350951a39d68df598db08dfced8b4707755864a0492Ying Wang pop_heap(_RandomAccessIterator __first, 351951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator __last, _Compare __comp) 352951a39d68df598db08dfced8b4707755864a0492Ying Wang { 353951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 354951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 355951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 356951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 357951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap_pred(__first, __last, __comp); 358951a39d68df598db08dfced8b4707755864a0492Ying Wang 359951a39d68df598db08dfced8b4707755864a0492Ying Wang --__last; 360951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__pop_heap(__first, __last, __last, __comp); 361951a39d68df598db08dfced8b4707755864a0492Ying Wang } 362951a39d68df598db08dfced8b4707755864a0492Ying Wang 363951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 364951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Construct a heap over a range. 365951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 366951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 367951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 368951a39d68df598db08dfced8b4707755864a0492Ying Wang * 369951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation makes the elements in [first,last) into a heap. 370951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 371951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 372951a39d68df598db08dfced8b4707755864a0492Ying Wang void 373951a39d68df598db08dfced8b4707755864a0492Ying Wang make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 374951a39d68df598db08dfced8b4707755864a0492Ying Wang { 375951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 376951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 377951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 378951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 379951a39d68df598db08dfced8b4707755864a0492Ying Wang 380951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 381951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 382951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 383951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 384951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 385951a39d68df598db08dfced8b4707755864a0492Ying Wang 386951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__last - __first < 2) 387951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 388951a39d68df598db08dfced8b4707755864a0492Ying Wang 389951a39d68df598db08dfced8b4707755864a0492Ying Wang const _DistanceType __len = __last - __first; 390951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType __parent = (__len - 2) / 2; 391951a39d68df598db08dfced8b4707755864a0492Ying Wang while (true) 392951a39d68df598db08dfced8b4707755864a0492Ying Wang { 393951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 394951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value)); 395951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__parent == 0) 396951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 397951a39d68df598db08dfced8b4707755864a0492Ying Wang __parent--; 398951a39d68df598db08dfced8b4707755864a0492Ying Wang } 399951a39d68df598db08dfced8b4707755864a0492Ying Wang } 400951a39d68df598db08dfced8b4707755864a0492Ying Wang 401951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 402951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Construct a heap over a range using comparison functor. 403951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 404951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 405951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 406951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 407951a39d68df598db08dfced8b4707755864a0492Ying Wang * 408951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation makes the elements in [first,last) into a heap. 409951a39d68df598db08dfced8b4707755864a0492Ying Wang * Comparisons are made using comp. 410951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 411951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 412951a39d68df598db08dfced8b4707755864a0492Ying Wang void 413951a39d68df598db08dfced8b4707755864a0492Ying Wang make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 414951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 415951a39d68df598db08dfced8b4707755864a0492Ying Wang { 416951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::value_type 417951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType; 418951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename iterator_traits<_RandomAccessIterator>::difference_type 419951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType; 420951a39d68df598db08dfced8b4707755864a0492Ying Wang 421951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 422951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 423951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 424951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 425951a39d68df598db08dfced8b4707755864a0492Ying Wang 426951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__last - __first < 2) 427951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 428951a39d68df598db08dfced8b4707755864a0492Ying Wang 429951a39d68df598db08dfced8b4707755864a0492Ying Wang const _DistanceType __len = __last - __first; 430951a39d68df598db08dfced8b4707755864a0492Ying Wang _DistanceType __parent = (__len - 2) / 2; 431951a39d68df598db08dfced8b4707755864a0492Ying Wang while (true) 432951a39d68df598db08dfced8b4707755864a0492Ying Wang { 433951a39d68df598db08dfced8b4707755864a0492Ying Wang _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 434951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), 435951a39d68df598db08dfced8b4707755864a0492Ying Wang __comp); 436951a39d68df598db08dfced8b4707755864a0492Ying Wang if (__parent == 0) 437951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 438951a39d68df598db08dfced8b4707755864a0492Ying Wang __parent--; 439951a39d68df598db08dfced8b4707755864a0492Ying Wang } 440951a39d68df598db08dfced8b4707755864a0492Ying Wang } 441951a39d68df598db08dfced8b4707755864a0492Ying Wang 442951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 443951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Sort a heap. 444951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 445951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 446951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 447951a39d68df598db08dfced8b4707755864a0492Ying Wang * 448951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation sorts the valid heap in the range [first,last). 449951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 450951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 451951a39d68df598db08dfced8b4707755864a0492Ying Wang void 452951a39d68df598db08dfced8b4707755864a0492Ying Wang sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 453951a39d68df598db08dfced8b4707755864a0492Ying Wang { 454951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 455951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 456951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 457951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept< 458951a39d68df598db08dfced8b4707755864a0492Ying Wang typename iterator_traits<_RandomAccessIterator>::value_type>) 459951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 460951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap(__first, __last); 461951a39d68df598db08dfced8b4707755864a0492Ying Wang 462951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__last - __first > 1) 463951a39d68df598db08dfced8b4707755864a0492Ying Wang { 464951a39d68df598db08dfced8b4707755864a0492Ying Wang --__last; 465951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__pop_heap(__first, __last, __last); 466951a39d68df598db08dfced8b4707755864a0492Ying Wang } 467951a39d68df598db08dfced8b4707755864a0492Ying Wang } 468951a39d68df598db08dfced8b4707755864a0492Ying Wang 469951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 470951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Sort a heap using comparison functor. 471951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of heap. 472951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of heap. 473951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 474951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 475951a39d68df598db08dfced8b4707755864a0492Ying Wang * 476951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation sorts the valid heap in the range [first,last). 477951a39d68df598db08dfced8b4707755864a0492Ying Wang * Comparisons are made using comp. 478951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 479951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 480951a39d68df598db08dfced8b4707755864a0492Ying Wang void 481951a39d68df598db08dfced8b4707755864a0492Ying Wang sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 482951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 483951a39d68df598db08dfced8b4707755864a0492Ying Wang { 484951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 485951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 486951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 487951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 488951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_heap_pred(__first, __last, __comp); 489951a39d68df598db08dfced8b4707755864a0492Ying Wang 490951a39d68df598db08dfced8b4707755864a0492Ying Wang while (__last - __first > 1) 491951a39d68df598db08dfced8b4707755864a0492Ying Wang { 492951a39d68df598db08dfced8b4707755864a0492Ying Wang --__last; 493951a39d68df598db08dfced8b4707755864a0492Ying Wang std::__pop_heap(__first, __last, __last, __comp); 494951a39d68df598db08dfced8b4707755864a0492Ying Wang } 495951a39d68df598db08dfced8b4707755864a0492Ying Wang } 496951a39d68df598db08dfced8b4707755864a0492Ying Wang 497951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef __GXX_EXPERIMENTAL_CXX0X__ 498951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 499951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Search the end of a heap. 500951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of range. 501951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of range. 502951a39d68df598db08dfced8b4707755864a0492Ying Wang * @return An iterator pointing to the first element not in the heap. 503951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 504951a39d68df598db08dfced8b4707755864a0492Ying Wang * 505951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation returns the last iterator i in [first, last) for which 506951a39d68df598db08dfced8b4707755864a0492Ying Wang * the range [first, i) is a heap. 507951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 508951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 509951a39d68df598db08dfced8b4707755864a0492Ying Wang inline _RandomAccessIterator 510951a39d68df598db08dfced8b4707755864a0492Ying Wang is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 511951a39d68df598db08dfced8b4707755864a0492Ying Wang { 512951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 513951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_RandomAccessIteratorConcept< 514951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 515951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_LessThanComparableConcept< 516951a39d68df598db08dfced8b4707755864a0492Ying Wang typename iterator_traits<_RandomAccessIterator>::value_type>) 517951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 518951a39d68df598db08dfced8b4707755864a0492Ying Wang 519951a39d68df598db08dfced8b4707755864a0492Ying Wang return __first + std::__is_heap_until(__first, std::distance(__first, 520951a39d68df598db08dfced8b4707755864a0492Ying Wang __last)); 521951a39d68df598db08dfced8b4707755864a0492Ying Wang } 522951a39d68df598db08dfced8b4707755864a0492Ying Wang 523951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 524951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Search the end of a heap using comparison functor. 525951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of range. 526951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of range. 527951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 528951a39d68df598db08dfced8b4707755864a0492Ying Wang * @return An iterator pointing to the first element not in the heap. 529951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 530951a39d68df598db08dfced8b4707755864a0492Ying Wang * 531951a39d68df598db08dfced8b4707755864a0492Ying Wang * This operation returns the last iterator i in [first, last) for which 532951a39d68df598db08dfced8b4707755864a0492Ying Wang * the range [first, i) is a heap. Comparisons are made using comp. 533951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 534951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 535951a39d68df598db08dfced8b4707755864a0492Ying Wang inline _RandomAccessIterator 536951a39d68df598db08dfced8b4707755864a0492Ying Wang is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, 537951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 538951a39d68df598db08dfced8b4707755864a0492Ying Wang { 539951a39d68df598db08dfced8b4707755864a0492Ying Wang // concept requirements 540951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_function_requires(_RandomAccessIteratorConcept< 541951a39d68df598db08dfced8b4707755864a0492Ying Wang _RandomAccessIterator>) 542951a39d68df598db08dfced8b4707755864a0492Ying Wang __glibcxx_requires_valid_range(__first, __last); 543951a39d68df598db08dfced8b4707755864a0492Ying Wang 544951a39d68df598db08dfced8b4707755864a0492Ying Wang return __first + std::__is_heap_until(__first, std::distance(__first, 545951a39d68df598db08dfced8b4707755864a0492Ying Wang __last), 546951a39d68df598db08dfced8b4707755864a0492Ying Wang __comp); 547951a39d68df598db08dfced8b4707755864a0492Ying Wang } 548951a39d68df598db08dfced8b4707755864a0492Ying Wang 549951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 550951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Determines whether a range is a heap. 551951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of range. 552951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of range. 553951a39d68df598db08dfced8b4707755864a0492Ying Wang * @return True if range is a heap, false otherwise. 554951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 555951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 556951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator> 557951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 558951a39d68df598db08dfced8b4707755864a0492Ying Wang is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 559951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::is_heap_until(__first, __last) == __last; } 560951a39d68df598db08dfced8b4707755864a0492Ying Wang 561951a39d68df598db08dfced8b4707755864a0492Ying Wang /** 562951a39d68df598db08dfced8b4707755864a0492Ying Wang * @brief Determines whether a range is a heap using comparison functor. 563951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param first Start of range. 564951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param last End of range. 565951a39d68df598db08dfced8b4707755864a0492Ying Wang * @param comp Comparison functor to use. 566951a39d68df598db08dfced8b4707755864a0492Ying Wang * @return True if range is a heap, false otherwise. 567951a39d68df598db08dfced8b4707755864a0492Ying Wang * @ingroup heap_algorithms 568951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 569951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename _RandomAccessIterator, typename _Compare> 570951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 571951a39d68df598db08dfced8b4707755864a0492Ying Wang is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 572951a39d68df598db08dfced8b4707755864a0492Ying Wang _Compare __comp) 573951a39d68df598db08dfced8b4707755864a0492Ying Wang { return std::is_heap_until(__first, __last, __comp) == __last; } 574951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 575951a39d68df598db08dfced8b4707755864a0492Ying Wang 576951a39d68df598db08dfced8b4707755864a0492Ying Wang_GLIBCXX_END_NAMESPACE 577951a39d68df598db08dfced8b4707755864a0492Ying Wang 578951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif /* _STL_HEAP_H */ 579