diff options
Diffstat (limited to 'rep/usr/include/c++/4.3/bits/stl_heap.h.gcov.html')
| -rw-r--r-- | rep/usr/include/c++/4.3/bits/stl_heap.h.gcov.html | 637 |
1 files changed, 0 insertions, 637 deletions
diff --git a/rep/usr/include/c++/4.3/bits/stl_heap.h.gcov.html b/rep/usr/include/c++/4.3/bits/stl_heap.h.gcov.html deleted file mode 100644 index c9d582a..0000000 --- a/rep/usr/include/c++/4.3/bits/stl_heap.h.gcov.html +++ /dev/null @@ -1,637 +0,0 @@ -<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> - -<html lang="en"> - -<head> - <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> - <title>LCOV - lcov.info - /usr/include/c++/4.3/bits/stl_heap.h</title> - <link rel="stylesheet" type="text/css" href="../../../../../gcov.css"> -</head> - -<body> - - <table width="100%" border=0 cellspacing=0 cellpadding=0> - <tr><td class="title">LTP GCOV extension - code coverage report</td></tr> - <tr><td class="ruler"><img src="../../../../../glass.png" width=3 height=3 alt=""></td></tr> - - <tr> - <td width="100%"> - <table cellpadding=1 border=0 width="100%"> - <tr> - <td class="headerItem" width="20%">Current view:</td> - <td class="headerValue" width="80%" colspan=4><a href="../../../../../index.html">directory</a> - <a href="index.html">usr/include/c++/4.3/bits</a> - stl_heap.h</td> - </tr> - <tr> - <td class="headerItem" width="20%">Test:</td> - <td class="headerValue" width="80%" colspan=4>lcov.info</td> - </tr> - <tr> - <td class="headerItem" width="20%">Date:</td> - <td class="headerValue" width="20%">2008-08-14</td> - <td width="20%"></td> - <td class="headerItem" width="20%">Instrumented lines:</td> - <td class="headerValue" width="20%">92</td> - </tr> - <tr> - <td class="headerItem" width="20%">Code covered:</td> - <td class="headerValue" width="20%">0.0 %</td> - <td width="20%"></td> - <td class="headerItem" width="20%">Executed lines:</td> - <td class="headerValue" width="20%">0</td> - </tr> - </table> - </td> - </tr> - <tr><td class="ruler"><img src="../../../../../glass.png" width=3 height=3 alt=""></td></tr> - </table> - - <table cellpadding=0 cellspacing=0 border=0> - <tr> - <td><br></td> - </tr> - <tr> - <td><pre class="source"> -<span class="lineNum"> 1 </span> : // Heap implementation -*- C++ -*- -<span class="lineNum"> 2 </span> : -<span class="lineNum"> 3 </span> : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 -<span class="lineNum"> 4 </span> : // Free Software Foundation, Inc. -<span class="lineNum"> 5 </span> : // -<span class="lineNum"> 6 </span> : // This file is part of the GNU ISO C++ Library. This library is free -<span class="lineNum"> 7 </span> : // software; you can redistribute it and/or modify it under the -<span class="lineNum"> 8 </span> : // terms of the GNU General Public License as published by the -<span class="lineNum"> 9 </span> : // Free Software Foundation; either version 2, or (at your option) -<span class="lineNum"> 10 </span> : // any later version. -<span class="lineNum"> 11 </span> : -<span class="lineNum"> 12 </span> : // This library is distributed in the hope that it will be useful, -<span class="lineNum"> 13 </span> : // but WITHOUT ANY WARRANTY; without even the implied warranty of -<span class="lineNum"> 14 </span> : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -<span class="lineNum"> 15 </span> : // GNU General Public License for more details. -<span class="lineNum"> 16 </span> : -<span class="lineNum"> 17 </span> : // You should have received a copy of the GNU General Public License along -<span class="lineNum"> 18 </span> : // with this library; see the file COPYING. If not, write to the Free -<span class="lineNum"> 19 </span> : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -<span class="lineNum"> 20 </span> : // USA. -<span class="lineNum"> 21 </span> : -<span class="lineNum"> 22 </span> : // As a special exception, you may use this file as part of a free software -<span class="lineNum"> 23 </span> : // library without restriction. Specifically, if other files instantiate -<span class="lineNum"> 24 </span> : // templates or use macros or inline functions from this file, or you compile -<span class="lineNum"> 25 </span> : // this file and link it with other files to produce an executable, this -<span class="lineNum"> 26 </span> : // file does not by itself cause the resulting executable to be covered by -<span class="lineNum"> 27 </span> : // the GNU General Public License. This exception does not however -<span class="lineNum"> 28 </span> : // invalidate any other reasons why the executable file might be covered by -<span class="lineNum"> 29 </span> : // the GNU General Public License. -<span class="lineNum"> 30 </span> : -<span class="lineNum"> 31 </span> : /* -<span class="lineNum"> 32 </span> : * -<span class="lineNum"> 33 </span> : * Copyright (c) 1994 -<span class="lineNum"> 34 </span> : * Hewlett-Packard Company -<span class="lineNum"> 35 </span> : * -<span class="lineNum"> 36 </span> : * Permission to use, copy, modify, distribute and sell this software -<span class="lineNum"> 37 </span> : * and its documentation for any purpose is hereby granted without fee, -<span class="lineNum"> 38 </span> : * provided that the above copyright notice appear in all copies and -<span class="lineNum"> 39 </span> : * that both that copyright notice and this permission notice appear -<span class="lineNum"> 40 </span> : * in supporting documentation. Hewlett-Packard Company makes no -<span class="lineNum"> 41 </span> : * representations about the suitability of this software for any -<span class="lineNum"> 42 </span> : * purpose. It is provided "as is" without express or implied warranty. -<span class="lineNum"> 43 </span> : * -<span class="lineNum"> 44 </span> : * Copyright (c) 1997 -<span class="lineNum"> 45 </span> : * Silicon Graphics Computer Systems, Inc. -<span class="lineNum"> 46 </span> : * -<span class="lineNum"> 47 </span> : * Permission to use, copy, modify, distribute and sell this software -<span class="lineNum"> 48 </span> : * and its documentation for any purpose is hereby granted without fee, -<span class="lineNum"> 49 </span> : * provided that the above copyright notice appear in all copies and -<span class="lineNum"> 50 </span> : * that both that copyright notice and this permission notice appear -<span class="lineNum"> 51 </span> : * in supporting documentation. Silicon Graphics makes no -<span class="lineNum"> 52 </span> : * representations about the suitability of this software for any -<span class="lineNum"> 53 </span> : * purpose. It is provided "as is" without express or implied warranty. -<span class="lineNum"> 54 </span> : */ -<span class="lineNum"> 55 </span> : -<span class="lineNum"> 56 </span> : /** @file stl_heap.h -<span class="lineNum"> 57 </span> : * This is an internal header file, included by other library headers. -<span class="lineNum"> 58 </span> : * You should not attempt to use it directly. -<span class="lineNum"> 59 </span> : */ -<span class="lineNum"> 60 </span> : -<span class="lineNum"> 61 </span> : #ifndef _STL_HEAP_H -<span class="lineNum"> 62 </span> : #define _STL_HEAP_H 1 -<span class="lineNum"> 63 </span> : -<span class="lineNum"> 64 </span> : #include <debug/debug.h> -<span class="lineNum"> 65 </span> : #include <bits/stl_move.h> -<span class="lineNum"> 66 </span> : -<span class="lineNum"> 67 </span> : _GLIBCXX_BEGIN_NAMESPACE(std) -<span class="lineNum"> 68 </span> : -<span class="lineNum"> 69 </span> : template<typename _RandomAccessIterator, typename _Distance> -<span class="lineNum"> 70 </span> : _Distance -<span class="lineNum"> 71 </span> : __is_heap_until(_RandomAccessIterator __first, _Distance __n) -<span class="lineNum"> 72 </span> : { -<span class="lineNum"> 73 </span> : _Distance __parent = 0; -<span class="lineNum"> 74 </span> : for (_Distance __child = 1; __child < __n; ++__child) -<span class="lineNum"> 75 </span> : { -<span class="lineNum"> 76 </span> : if (__first[__parent] < __first[__child]) -<span class="lineNum"> 77 </span> : return __child; -<span class="lineNum"> 78 </span> : if ((__child & 1) == 0) -<span class="lineNum"> 79 </span> : ++__parent; -<span class="lineNum"> 80 </span> : } -<span class="lineNum"> 81 </span> : return __n; -<span class="lineNum"> 82 </span> : } -<span class="lineNum"> 83 </span> : -<span class="lineNum"> 84 </span> : template<typename _RandomAccessIterator, typename _Distance, -<span class="lineNum"> 85 </span> : typename _Compare> -<span class="lineNum"> 86 </span> : _Distance -<span class="lineNum"> 87 </span> : __is_heap_until(_RandomAccessIterator __first, _Distance __n, -<span class="lineNum"> 88 </span> : _Compare __comp) -<span class="lineNum"> 89 </span> : { -<span class="lineNum"> 90 </span> : _Distance __parent = 0; -<span class="lineNum"> 91 </span> : for (_Distance __child = 1; __child < __n; ++__child) -<span class="lineNum"> 92 </span> : { -<span class="lineNum"> 93 </span> : if (__comp(__first[__parent], __first[__child])) -<span class="lineNum"> 94 </span> : return __child; -<span class="lineNum"> 95 </span> : if ((__child & 1) == 0) -<span class="lineNum"> 96 </span> : ++__parent; -<span class="lineNum"> 97 </span> : } -<span class="lineNum"> 98 </span> : return __n; -<span class="lineNum"> 99 </span> : } -<span class="lineNum"> 100 </span> : -<span class="lineNum"> 101 </span> : // __is_heap, a predicate testing whether or not a range is a heap. -<span class="lineNum"> 102 </span> : // This function is an extension, not part of the C++ standard. -<span class="lineNum"> 103 </span> : template<typename _RandomAccessIterator, typename _Distance> -<span class="lineNum"> 104 </span> : inline bool -<span class="lineNum"> 105 </span> : __is_heap(_RandomAccessIterator __first, _Distance __n) -<span class="lineNum"> 106 </span> : { return std::__is_heap_until(__first, __n) == __n; } -<span class="lineNum"> 107 </span> : -<span class="lineNum"> 108 </span> : template<typename _RandomAccessIterator, typename _Compare, -<span class="lineNum"> 109 </span> : typename _Distance> -<span class="lineNum"> 110 </span> : inline bool -<span class="lineNum"> 111 </span> : __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) -<span class="lineNum"> 112 </span> : { return std::__is_heap_until(__first, __n, __comp) == __n; } -<span class="lineNum"> 113 </span> : -<span class="lineNum"> 114 </span> : template<typename _RandomAccessIterator> -<span class="lineNum"> 115 </span> : inline bool -<span class="lineNum"> 116 </span> : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -<span class="lineNum"> 117 </span> : { return std::__is_heap(__first, std::distance(__first, __last)); } -<span class="lineNum"> 118 </span> : -<span class="lineNum"> 119 </span> : template<typename _RandomAccessIterator, typename _Compare> -<span class="lineNum"> 120 </span> : inline bool -<span class="lineNum"> 121 </span> : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, -<span class="lineNum"> 122 </span> : _Compare __comp) -<span class="lineNum"> 123 </span> : { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } -<span class="lineNum"> 124 </span> : -<span class="lineNum"> 125 </span> : // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap, -<span class="lineNum"> 126 </span> : // + is_heap and is_heap_until in C++0x. -<span class="lineNum"> 127 </span> : -<span class="lineNum"> 128 </span> : template<typename _RandomAccessIterator, typename _Distance, typename _Tp> -<span class="lineNum"> 129 </span> : void -<span class="lineNum"> 130 </span> : __push_heap(_RandomAccessIterator __first, -<span class="lineNum"> 131 </span><span class="lineNoCov"> 0 : _Distance __holeIndex, _Distance __topIndex, _Tp __value)</span> -<span class="lineNum"> 132 </span> : { -<span class="lineNum"> 133 </span><span class="lineNoCov"> 0 : _Distance __parent = (__holeIndex - 1) / 2;</span> -<span class="lineNum"> 134 </span><span class="lineNoCov"> 0 : while (__holeIndex > __topIndex && *(__first + __parent) < __value)</span> -<span class="lineNum"> 135 </span> : { -<span class="lineNum"> 136 </span><span class="lineNoCov"> 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));</span> -<span class="lineNum"> 137 </span><span class="lineNoCov"> 0 : __holeIndex = __parent;</span> -<span class="lineNum"> 138 </span><span class="lineNoCov"> 0 : __parent = (__holeIndex - 1) / 2;</span> -<span class="lineNum"> 139 </span> : } -<span class="lineNum"> 140 </span><span class="lineNoCov"> 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);</span> -<span class="lineNum"> 141 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 142 </span> : -<span class="lineNum"> 143 </span> : /** -<span class="lineNum"> 144 </span> : * @brief Push an element onto a heap. -<span class="lineNum"> 145 </span> : * @param first Start of heap. -<span class="lineNum"> 146 </span> : * @param last End of heap + element. -<span class="lineNum"> 147 </span> : * @ingroup heap -<span class="lineNum"> 148 </span> : * -<span class="lineNum"> 149 </span> : * This operation pushes the element at last-1 onto the valid heap over the -<span class="lineNum"> 150 </span> : * range [first,last-1). After completion, [first,last) is a valid heap. -<span class="lineNum"> 151 </span> : */ -<span class="lineNum"> 152 </span> : template<typename _RandomAccessIterator> -<span class="lineNum"> 153 </span> : inline void -<span class="lineNum"> 154 </span> : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -<span class="lineNum"> 155 </span> : { -<span class="lineNum"> 156 </span> : typedef typename iterator_traits<_RandomAccessIterator>::value_type -<span class="lineNum"> 157 </span> : _ValueType; -<span class="lineNum"> 158 </span> : typedef typename iterator_traits<_RandomAccessIterator>::difference_type -<span class="lineNum"> 159 </span> : _DistanceType; -<span class="lineNum"> 160 </span> : -<span class="lineNum"> 161 </span> : // concept requirements -<span class="lineNum"> 162 </span> : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< -<span class="lineNum"> 163 </span> : _RandomAccessIterator>) -<span class="lineNum"> 164 </span> : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) -<span class="lineNum"> 165 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 166 </span> : __glibcxx_requires_heap(__first, __last - 1); -<span class="lineNum"> 167 </span> : -<span class="lineNum"> 168 </span> : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); -<span class="lineNum"> 169 </span> : std::__push_heap(__first, _DistanceType((__last - __first) - 1), -<span class="lineNum"> 170 </span> : _DistanceType(0), _GLIBCXX_MOVE(__value)); -<span class="lineNum"> 171 </span> : } -<span class="lineNum"> 172 </span> : -<span class="lineNum"> 173 </span> : template<typename _RandomAccessIterator, typename _Distance, typename _Tp, -<span class="lineNum"> 174 </span> : typename _Compare> -<span class="lineNum"> 175 </span> : void -<span class="lineNum"> 176 </span> : __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, -<span class="lineNum"> 177 </span><span class="lineNoCov"> 0 : _Distance __topIndex, _Tp __value, _Compare __comp)</span> -<span class="lineNum"> 178 </span> : { -<span class="lineNum"> 179 </span><span class="lineNoCov"> 0 : _Distance __parent = (__holeIndex - 1) / 2;</span> -<span class="lineNum"> 180 </span><span class="lineNoCov"> 0 : while (__holeIndex > __topIndex</span> -<span class="lineNum"> 181 </span> : && __comp(*(__first + __parent), __value)) -<span class="lineNum"> 182 </span> : { -<span class="lineNum"> 183 </span><span class="lineNoCov"> 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));</span> -<span class="lineNum"> 184 </span><span class="lineNoCov"> 0 : __holeIndex = __parent;</span> -<span class="lineNum"> 185 </span><span class="lineNoCov"> 0 : __parent = (__holeIndex - 1) / 2;</span> -<span class="lineNum"> 186 </span> : } -<span class="lineNum"> 187 </span><span class="lineNoCov"> 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);</span> -<span class="lineNum"> 188 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 189 </span> : -<span class="lineNum"> 190 </span> : /** -<span class="lineNum"> 191 </span> : * @brief Push an element onto a heap using comparison functor. -<span class="lineNum"> 192 </span> : * @param first Start of heap. -<span class="lineNum"> 193 </span> : * @param last End of heap + element. -<span class="lineNum"> 194 </span> : * @param comp Comparison functor. -<span class="lineNum"> 195 </span> : * @ingroup heap -<span class="lineNum"> 196 </span> : * -<span class="lineNum"> 197 </span> : * This operation pushes the element at last-1 onto the valid heap over the -<span class="lineNum"> 198 </span> : * range [first,last-1). After completion, [first,last) is a valid heap. -<span class="lineNum"> 199 </span> : * Compare operations are performed using comp. -<span class="lineNum"> 200 </span> : */ -<span class="lineNum"> 201 </span> : template<typename _RandomAccessIterator, typename _Compare> -<span class="lineNum"> 202 </span> : inline void -<span class="lineNum"> 203 </span> : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, -<span class="lineNum"> 204 </span> : _Compare __comp) -<span class="lineNum"> 205 </span> : { -<span class="lineNum"> 206 </span> : typedef typename iterator_traits<_RandomAccessIterator>::value_type -<span class="lineNum"> 207 </span> : _ValueType; -<span class="lineNum"> 208 </span> : typedef typename iterator_traits<_RandomAccessIterator>::difference_type -<span class="lineNum"> 209 </span> : _DistanceType; -<span class="lineNum"> 210 </span> : -<span class="lineNum"> 211 </span> : // concept requirements -<span class="lineNum"> 212 </span> : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< -<span class="lineNum"> 213 </span> : _RandomAccessIterator>) -<span class="lineNum"> 214 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 215 </span> : __glibcxx_requires_heap_pred(__first, __last - 1, __comp); -<span class="lineNum"> 216 </span> : -<span class="lineNum"> 217 </span> : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); -<span class="lineNum"> 218 </span> : std::__push_heap(__first, _DistanceType((__last - __first) - 1), -<span class="lineNum"> 219 </span> : _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); -<span class="lineNum"> 220 </span> : } -<span class="lineNum"> 221 </span> : -<span class="lineNum"> 222 </span> : template<typename _RandomAccessIterator, typename _Distance, typename _Tp> -<span class="lineNum"> 223 </span> : void -<span class="lineNum"> 224 </span> : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, -<span class="lineNum"> 225 </span><span class="lineNoCov"> 0 : _Distance __len, _Tp __value)</span> -<span class="lineNum"> 226 </span> : { -<span class="lineNum"> 227 </span><span class="lineNoCov"> 0 : const _Distance __topIndex = __holeIndex;</span> -<span class="lineNum"> 228 </span><span class="lineNoCov"> 0 : _Distance __secondChild = __holeIndex;</span> -<span class="lineNum"> 229 </span><span class="lineNoCov"> 0 : while (__secondChild < (__len - 1) / 2)</span> -<span class="lineNum"> 230 </span> : { -<span class="lineNum"> 231 </span><span class="lineNoCov"> 0 : __secondChild = 2 * (__secondChild + 1);</span> -<span class="lineNum"> 232 </span><span class="lineNoCov"> 0 : if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))</span> -<span class="lineNum"> 233 </span><span class="lineNoCov"> 0 : __secondChild--;</span> -<span class="lineNum"> 234 </span><span class="lineNoCov"> 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));</span> -<span class="lineNum"> 235 </span><span class="lineNoCov"> 0 : __holeIndex = __secondChild;</span> -<span class="lineNum"> 236 </span> : } -<span class="lineNum"> 237 </span><span class="lineNoCov"> 0 : if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)</span> -<span class="lineNum"> 238 </span> : { -<span class="lineNum"> 239 </span><span class="lineNoCov"> 0 : __secondChild = 2 * (__secondChild + 1);</span> -<span class="lineNum"> 240 </span><span class="lineNoCov"> 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first</span> -<span class="lineNum"> 241 </span> : + (__secondChild - 1))); -<span class="lineNum"> 242 </span><span class="lineNoCov"> 0 : __holeIndex = __secondChild - 1;</span> -<span class="lineNum"> 243 </span> : } -<span class="lineNum"> 244 </span><span class="lineNoCov"> 0 : std::__push_heap(__first, __holeIndex, __topIndex,</span> -<span class="lineNum"> 245 </span> : _GLIBCXX_MOVE(__value)); -<span class="lineNum"> 246 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 247 </span> : -<span class="lineNum"> 248 </span> : template<typename _RandomAccessIterator> -<span class="lineNum"> 249 </span> : inline void -<span class="lineNum"> 250 </span> : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, -<span class="lineNum"> 251 </span><span class="lineNoCov"> 0 : _RandomAccessIterator __result)</span> -<span class="lineNum"> 252 </span> : { -<span class="lineNum"> 253 </span> : typedef typename iterator_traits<_RandomAccessIterator>::value_type -<span class="lineNum"> 254 </span> : _ValueType; -<span class="lineNum"> 255 </span> : typedef typename iterator_traits<_RandomAccessIterator>::difference_type -<span class="lineNum"> 256 </span> : _DistanceType; -<span class="lineNum"> 257 </span> : -<span class="lineNum"> 258 </span><span class="lineNoCov"> 0 : _ValueType __value = _GLIBCXX_MOVE(*__result);</span> -<span class="lineNum"> 259 </span><span class="lineNoCov"> 0 : *__result = _GLIBCXX_MOVE(*__first);</span> -<span class="lineNum"> 260 </span><span class="lineNoCov"> 0 : std::__adjust_heap(__first, _DistanceType(0),</span> -<span class="lineNum"> 261 </span> : _DistanceType(__last - __first), -<span class="lineNum"> 262 </span> : _GLIBCXX_MOVE(__value)); -<span class="lineNum"> 263 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 264 </span> : -<span class="lineNum"> 265 </span> : /** -<span class="lineNum"> 266 </span> : * @brief Pop an element off a heap. -<span class="lineNum"> 267 </span> : * @param first Start of heap. -<span class="lineNum"> 268 </span> : * @param last End of heap. -<span class="lineNum"> 269 </span> : * @ingroup heap -<span class="lineNum"> 270 </span> : * -<span class="lineNum"> 271 </span> : * This operation pops the top of the heap. The elements first and last-1 -<span class="lineNum"> 272 </span> : * are swapped and [first,last-1) is made into a heap. -<span class="lineNum"> 273 </span> : */ -<span class="lineNum"> 274 </span> : template<typename _RandomAccessIterator> -<span class="lineNum"> 275 </span> : inline void -<span class="lineNum"> 276 </span><span class="lineNoCov"> 0 : pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)</span> -<span class="lineNum"> 277 </span> : { -<span class="lineNum"> 278 </span> : typedef typename iterator_traits<_RandomAccessIterator>::value_type -<span class="lineNum"> 279 </span> : _ValueType; -<span class="lineNum"> 280 </span> : -<span class="lineNum"> 281 </span> : // concept requirements -<span class="lineNum"> 282 </span> : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< -<span class="lineNum"> 283 </span> : _RandomAccessIterator>) -<span class="lineNum"> 284 </span> : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) -<span class="lineNum"> 285 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 286 </span> : __glibcxx_requires_heap(__first, __last); -<span class="lineNum"> 287 </span> : -<span class="lineNum"> 288 </span><span class="lineNoCov"> 0 : std::__pop_heap(__first, __last - 1, __last - 1);</span> -<span class="lineNum"> 289 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 290 </span> : -<span class="lineNum"> 291 </span> : template<typename _RandomAccessIterator, typename _Distance, -<span class="lineNum"> 292 </span> : typename _Tp, typename _Compare> -<span class="lineNum"> 293 </span> : void -<span class="lineNum"> 294 </span> : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, -<span class="lineNum"> 295 </span><span class="lineNoCov"> 0 : _Distance __len, _Tp __value, _Compare __comp)</span> -<span class="lineNum"> 296 </span> : { -<span class="lineNum"> 297 </span><span class="lineNoCov"> 0 : const _Distance __topIndex = __holeIndex;</span> -<span class="lineNum"> 298 </span><span class="lineNoCov"> 0 : _Distance __secondChild = __holeIndex;</span> -<span class="lineNum"> 299 </span><span class="lineNoCov"> 0 : while (__secondChild < (__len - 1) / 2)</span> -<span class="lineNum"> 300 </span> : { -<span class="lineNum"> 301 </span><span class="lineNoCov"> 0 : __secondChild = 2 * (__secondChild + 1);</span> -<span class="lineNum"> 302 </span><span class="lineNoCov"> 0 : if (__comp(*(__first + __secondChild),</span> -<span class="lineNum"> 303 </span> : *(__first + (__secondChild - 1)))) -<span class="lineNum"> 304 </span><span class="lineNoCov"> 0 : __secondChild--;</span> -<span class="lineNum"> 305 </span><span class="lineNoCov"> 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));</span> -<span class="lineNum"> 306 </span><span class="lineNoCov"> 0 : __holeIndex = __secondChild;</span> -<span class="lineNum"> 307 </span> : } -<span class="lineNum"> 308 </span><span class="lineNoCov"> 0 : if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)</span> -<span class="lineNum"> 309 </span> : { -<span class="lineNum"> 310 </span><span class="lineNoCov"> 0 : __secondChild = 2 * (__secondChild + 1);</span> -<span class="lineNum"> 311 </span><span class="lineNoCov"> 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first</span> -<span class="lineNum"> 312 </span> : + (__secondChild - 1))); -<span class="lineNum"> 313 </span><span class="lineNoCov"> 0 : __holeIndex = __secondChild - 1;</span> -<span class="lineNum"> 314 </span> : } -<span class="lineNum"> 315 </span><span class="lineNoCov"> 0 : std::__push_heap(__first, __holeIndex, __topIndex, </span> -<span class="lineNum"> 316 </span> : _GLIBCXX_MOVE(__value), __comp); -<span class="lineNum"> 317 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 318 </span> : -<span class="lineNum"> 319 </span> : template<typename _RandomAccessIterator, typename _Compare> -<span class="lineNum"> 320 </span> : inline void -<span class="lineNum"> 321 </span> : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, -<span class="lineNum"> 322 </span><span class="lineNoCov"> 0 : _RandomAccessIterator __result, _Compare __comp)</span> -<span class="lineNum"> 323 </span> : { -<span class="lineNum"> 324 </span> : typedef typename iterator_traits<_RandomAccessIterator>::value_type -<span class="lineNum"> 325 </span> : _ValueType; -<span class="lineNum"> 326 </span> : typedef typename iterator_traits<_RandomAccessIterator>::difference_type -<span class="lineNum"> 327 </span> : _DistanceType; -<span class="lineNum"> 328 </span> : -<span class="lineNum"> 329 </span><span class="lineNoCov"> 0 : _ValueType __value = _GLIBCXX_MOVE(*__result);</span> -<span class="lineNum"> 330 </span><span class="lineNoCov"> 0 : *__result = _GLIBCXX_MOVE(*__first);</span> -<span class="lineNum"> 331 </span><span class="lineNoCov"> 0 : std::__adjust_heap(__first, _DistanceType(0),</span> -<span class="lineNum"> 332 </span> : _DistanceType(__last - __first), -<span class="lineNum"> 333 </span> : _GLIBCXX_MOVE(__value), __comp); -<span class="lineNum"> 334 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 335 </span> : -<span class="lineNum"> 336 </span> : /** -<span class="lineNum"> 337 </span> : * @brief Pop an element off a heap using comparison functor. -<span class="lineNum"> 338 </span> : * @param first Start of heap. -<span class="lineNum"> 339 </span> : * @param last End of heap. -<span class="lineNum"> 340 </span> : * @param comp Comparison functor to use. -<span class="lineNum"> 341 </span> : * @ingroup heap -<span class="lineNum"> 342 </span> : * -<span class="lineNum"> 343 </span> : * This operation pops the top of the heap. The elements first and last-1 -<span class="lineNum"> 344 </span> : * are swapped and [first,last-1) is made into a heap. Comparisons are -<span class="lineNum"> 345 </span> : * made using comp. -<span class="lineNum"> 346 </span> : */ -<span class="lineNum"> 347 </span> : template<typename _RandomAccessIterator, typename _Compare> -<span class="lineNum"> 348 </span> : inline void -<span class="lineNum"> 349 </span> : pop_heap(_RandomAccessIterator __first, -<span class="lineNum"> 350 </span><span class="lineNoCov"> 0 : _RandomAccessIterator __last, _Compare __comp)</span> -<span class="lineNum"> 351 </span> : { -<span class="lineNum"> 352 </span> : // concept requirements -<span class="lineNum"> 353 </span> : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< -<span class="lineNum"> 354 </span> : _RandomAccessIterator>) -<span class="lineNum"> 355 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 356 </span> : __glibcxx_requires_heap_pred(__first, __last, __comp); -<span class="lineNum"> 357 </span> : -<span class="lineNum"> 358 </span><span class="lineNoCov"> 0 : std::__pop_heap(__first, __last - 1, __last - 1, __comp);</span> -<span class="lineNum"> 359 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 360 </span> : -<span class="lineNum"> 361 </span> : /** -<span class="lineNum"> 362 </span> : * @brief Construct a heap over a range. -<span class="lineNum"> 363 </span> : * @param first Start of heap. -<span class="lineNum"> 364 </span> : * @param last End of heap. -<span class="lineNum"> 365 </span> : * @ingroup heap -<span class="lineNum"> 366 </span> : * -<span class="lineNum"> 367 </span> : * This operation makes the elements in [first,last) into a heap. -<span class="lineNum"> 368 </span> : */ -<span class="lineNum"> 369 </span> : template<typename _RandomAccessIterator> -<span class="lineNum"> 370 </span> : void -<span class="lineNum"> 371 </span><span class="lineNoCov"> 0 : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)</span> -<span class="lineNum"> 372 </span> : { -<span class="lineNum"> 373 </span> : typedef typename iterator_traits<_RandomAccessIterator>::value_type -<span class="lineNum"> 374 </span> : _ValueType; -<span class="lineNum"> 375 </span> : typedef typename iterator_traits<_RandomAccessIterator>::difference_type -<span class="lineNum"> 376 </span> : _DistanceType; -<span class="lineNum"> 377 </span> : -<span class="lineNum"> 378 </span> : // concept requirements -<span class="lineNum"> 379 </span> : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< -<span class="lineNum"> 380 </span> : _RandomAccessIterator>) -<span class="lineNum"> 381 </span> : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) -<span class="lineNum"> 382 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 383 </span> : -<span class="lineNum"> 384 </span><span class="lineNoCov"> 0 : if (__last - __first < 2)</span> -<span class="lineNum"> 385 </span><span class="lineNoCov"> 0 : return;</span> -<span class="lineNum"> 386 </span> : -<span class="lineNum"> 387 </span><span class="lineNoCov"> 0 : const _DistanceType __len = __last - __first;</span> -<span class="lineNum"> 388 </span><span class="lineNoCov"> 0 : _DistanceType __parent = (__len - 2) / 2;</span> -<span class="lineNum"> 389 </span><span class="lineNoCov"> 0 : while (true)</span> -<span class="lineNum"> 390 </span> : { -<span class="lineNum"> 391 </span><span class="lineNoCov"> 0 : _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));</span> -<span class="lineNum"> 392 </span><span class="lineNoCov"> 0 : std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));</span> -<span class="lineNum"> 393 </span><span class="lineNoCov"> 0 : if (__parent == 0)</span> -<span class="lineNum"> 394 </span><span class="lineNoCov"> 0 : return;</span> -<span class="lineNum"> 395 </span><span class="lineNoCov"> 0 : __parent--;</span> -<span class="lineNum"> 396 </span> : } -<span class="lineNum"> 397 </span> : } -<span class="lineNum"> 398 </span> : -<span class="lineNum"> 399 </span> : /** -<span class="lineNum"> 400 </span> : * @brief Construct a heap over a range using comparison functor. -<span class="lineNum"> 401 </span> : * @param first Start of heap. -<span class="lineNum"> 402 </span> : * @param last End of heap. -<span class="lineNum"> 403 </span> : * @param comp Comparison functor to use. -<span class="lineNum"> 404 </span> : * @ingroup heap -<span class="lineNum"> 405 </span> : * -<span class="lineNum"> 406 </span> : * This operation makes the elements in [first,last) into a heap. -<span class="lineNum"> 407 </span> : * Comparisons are made using comp. -<span class="lineNum"> 408 </span> : */ -<span class="lineNum"> 409 </span> : template<typename _RandomAccessIterator, typename _Compare> -<span class="lineNum"> 410 </span> : void -<span class="lineNum"> 411 </span> : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, -<span class="lineNum"> 412 </span><span class="lineNoCov"> 0 : _Compare __comp)</span> -<span class="lineNum"> 413 </span> : { -<span class="lineNum"> 414 </span> : typedef typename iterator_traits<_RandomAccessIterator>::value_type -<span class="lineNum"> 415 </span> : _ValueType; -<span class="lineNum"> 416 </span> : typedef typename iterator_traits<_RandomAccessIterator>::difference_type -<span class="lineNum"> 417 </span> : _DistanceType; -<span class="lineNum"> 418 </span> : -<span class="lineNum"> 419 </span> : // concept requirements -<span class="lineNum"> 420 </span> : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< -<span class="lineNum"> 421 </span> : _RandomAccessIterator>) -<span class="lineNum"> 422 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 423 </span> : -<span class="lineNum"> 424 </span><span class="lineNoCov"> 0 : if (__last - __first < 2)</span> -<span class="lineNum"> 425 </span><span class="lineNoCov"> 0 : return;</span> -<span class="lineNum"> 426 </span> : -<span class="lineNum"> 427 </span><span class="lineNoCov"> 0 : const _DistanceType __len = __last - __first;</span> -<span class="lineNum"> 428 </span><span class="lineNoCov"> 0 : _DistanceType __parent = (__len - 2) / 2;</span> -<span class="lineNum"> 429 </span><span class="lineNoCov"> 0 : while (true)</span> -<span class="lineNum"> 430 </span> : { -<span class="lineNum"> 431 </span><span class="lineNoCov"> 0 : _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));</span> -<span class="lineNum"> 432 </span><span class="lineNoCov"> 0 : std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),</span> -<span class="lineNum"> 433 </span> : __comp); -<span class="lineNum"> 434 </span><span class="lineNoCov"> 0 : if (__parent == 0)</span> -<span class="lineNum"> 435 </span><span class="lineNoCov"> 0 : return;</span> -<span class="lineNum"> 436 </span><span class="lineNoCov"> 0 : __parent--;</span> -<span class="lineNum"> 437 </span> : } -<span class="lineNum"> 438 </span> : } -<span class="lineNum"> 439 </span> : -<span class="lineNum"> 440 </span> : /** -<span class="lineNum"> 441 </span> : * @brief Sort a heap. -<span class="lineNum"> 442 </span> : * @param first Start of heap. -<span class="lineNum"> 443 </span> : * @param last End of heap. -<span class="lineNum"> 444 </span> : * @ingroup heap -<span class="lineNum"> 445 </span> : * -<span class="lineNum"> 446 </span> : * This operation sorts the valid heap in the range [first,last). -<span class="lineNum"> 447 </span> : */ -<span class="lineNum"> 448 </span> : template<typename _RandomAccessIterator> -<span class="lineNum"> 449 </span> : void -<span class="lineNum"> 450 </span><span class="lineNoCov"> 0 : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)</span> -<span class="lineNum"> 451 </span> : { -<span class="lineNum"> 452 </span> : // concept requirements -<span class="lineNum"> 453 </span> : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< -<span class="lineNum"> 454 </span> : _RandomAccessIterator>) -<span class="lineNum"> 455 </span> : __glibcxx_function_requires(_LessThanComparableConcept< -<span class="lineNum"> 456 </span> : typename iterator_traits<_RandomAccessIterator>::value_type>) -<span class="lineNum"> 457 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 458 </span> : __glibcxx_requires_heap(__first, __last); -<span class="lineNum"> 459 </span> : -<span class="lineNum"> 460 </span><span class="lineNoCov"> 0 : while (__last - __first > 1)</span> -<span class="lineNum"> 461 </span><span class="lineNoCov"> 0 : std::pop_heap(__first, _RandomAccessIterator(__last--));</span> -<span class="lineNum"> 462 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 463 </span> : -<span class="lineNum"> 464 </span> : /** -<span class="lineNum"> 465 </span> : * @brief Sort a heap using comparison functor. -<span class="lineNum"> 466 </span> : * @param first Start of heap. -<span class="lineNum"> 467 </span> : * @param last End of heap. -<span class="lineNum"> 468 </span> : * @param comp Comparison functor to use. -<span class="lineNum"> 469 </span> : * @ingroup heap -<span class="lineNum"> 470 </span> : * -<span class="lineNum"> 471 </span> : * This operation sorts the valid heap in the range [first,last). -<span class="lineNum"> 472 </span> : * Comparisons are made using comp. -<span class="lineNum"> 473 </span> : */ -<span class="lineNum"> 474 </span> : template<typename _RandomAccessIterator, typename _Compare> -<span class="lineNum"> 475 </span> : void -<span class="lineNum"> 476 </span> : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, -<span class="lineNum"> 477 </span><span class="lineNoCov"> 0 : _Compare __comp)</span> -<span class="lineNum"> 478 </span> : { -<span class="lineNum"> 479 </span> : // concept requirements -<span class="lineNum"> 480 </span> : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< -<span class="lineNum"> 481 </span> : _RandomAccessIterator>) -<span class="lineNum"> 482 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 483 </span> : __glibcxx_requires_heap_pred(__first, __last, __comp); -<span class="lineNum"> 484 </span> : -<span class="lineNum"> 485 </span><span class="lineNoCov"> 0 : while (__last - __first > 1)</span> -<span class="lineNum"> 486 </span><span class="lineNoCov"> 0 : std::pop_heap(__first, _RandomAccessIterator(__last--), __comp);</span> -<span class="lineNum"> 487 </span><span class="lineNoCov"> 0 : }</span> -<span class="lineNum"> 488 </span> : -<span class="lineNum"> 489 </span> : #ifdef __GXX_EXPERIMENTAL_CXX0X__ -<span class="lineNum"> 490 </span> : /** -<span class="lineNum"> 491 </span> : * @brief Search the end of a heap. -<span class="lineNum"> 492 </span> : * @param first Start of range. -<span class="lineNum"> 493 </span> : * @param last End of range. -<span class="lineNum"> 494 </span> : * @return An iterator pointing to the first element not in the heap. -<span class="lineNum"> 495 </span> : * @ingroup heap -<span class="lineNum"> 496 </span> : * -<span class="lineNum"> 497 </span> : * This operation returns the last iterator i in [first, last) for which -<span class="lineNum"> 498 </span> : * the range [first, i) is a heap. -<span class="lineNum"> 499 </span> : */ -<span class="lineNum"> 500 </span> : template<typename _RandomAccessIterator> -<span class="lineNum"> 501 </span> : inline _RandomAccessIterator -<span class="lineNum"> 502 </span> : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) -<span class="lineNum"> 503 </span> : { -<span class="lineNum"> 504 </span> : // concept requirements -<span class="lineNum"> 505 </span> : __glibcxx_function_requires(_RandomAccessIteratorConcept< -<span class="lineNum"> 506 </span> : _RandomAccessIterator>) -<span class="lineNum"> 507 </span> : __glibcxx_function_requires(_LessThanComparableConcept< -<span class="lineNum"> 508 </span> : typename iterator_traits<_RandomAccessIterator>::value_type>) -<span class="lineNum"> 509 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 510 </span> : -<span class="lineNum"> 511 </span> : return __first + std::__is_heap_until(__first, std::distance(__first, -<span class="lineNum"> 512 </span> : __last)); -<span class="lineNum"> 513 </span> : } -<span class="lineNum"> 514 </span> : -<span class="lineNum"> 515 </span> : /** -<span class="lineNum"> 516 </span> : * @brief Search the end of a heap using comparison functor. -<span class="lineNum"> 517 </span> : * @param first Start of range. -<span class="lineNum"> 518 </span> : * @param last End of range. -<span class="lineNum"> 519 </span> : * @param comp Comparison functor to use. -<span class="lineNum"> 520 </span> : * @return An iterator pointing to the first element not in the heap. -<span class="lineNum"> 521 </span> : * @ingroup heap -<span class="lineNum"> 522 </span> : * -<span class="lineNum"> 523 </span> : * This operation returns the last iterator i in [first, last) for which -<span class="lineNum"> 524 </span> : * the range [first, i) is a heap. Comparisons are made using comp. -<span class="lineNum"> 525 </span> : */ -<span class="lineNum"> 526 </span> : template<typename _RandomAccessIterator, typename _Compare> -<span class="lineNum"> 527 </span> : inline _RandomAccessIterator -<span class="lineNum"> 528 </span> : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, -<span class="lineNum"> 529 </span> : _Compare __comp) -<span class="lineNum"> 530 </span> : { -<span class="lineNum"> 531 </span> : // concept requirements -<span class="lineNum"> 532 </span> : __glibcxx_function_requires(_RandomAccessIteratorConcept< -<span class="lineNum"> 533 </span> : _RandomAccessIterator>) -<span class="lineNum"> 534 </span> : __glibcxx_requires_valid_range(__first, __last); -<span class="lineNum"> 535 </span> : -<span class="lineNum"> 536 </span> : return __first + std::__is_heap_until(__first, std::distance(__first, -<span class="lineNum"> 537 </span> : __last), -<span class="lineNum"> 538 </span> : __comp); -<span class="lineNum"> 539 </span> : } -<span class="lineNum"> 540 </span> : -<span class="lineNum"> 541 </span> : /** -<span class="lineNum"> 542 </span> : * @brief Determines whether a range is a heap. -<span class="lineNum"> 543 </span> : * @param first Start of range. -<span class="lineNum"> 544 </span> : * @param last End of range. -<span class="lineNum"> 545 </span> : * @return True if range is a heap, false otherwise. -<span class="lineNum"> 546 </span> : * @ingroup heap -<span class="lineNum"> 547 </span> : */ -<span class="lineNum"> 548 </span> : template<typename _RandomAccessIterator> -<span class="lineNum"> 549 </span> : inline bool -<span class="lineNum"> 550 </span> : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -<span class="lineNum"> 551 </span> : { return std::is_heap_until(__first, __last) == __last; } -<span class="lineNum"> 552 </span> : -<span class="lineNum"> 553 </span> : /** -<span class="lineNum"> 554 </span> : * @brief Determines whether a range is a heap using comparison functor. -<span class="lineNum"> 555 </span> : * @param first Start of range. -<span class="lineNum"> 556 </span> : * @param last End of range. -<span class="lineNum"> 557 </span> : * @param comp Comparison functor to use. -<span class="lineNum"> 558 </span> : * @return True if range is a heap, false otherwise. -<span class="lineNum"> 559 </span> : * @ingroup heap -<span class="lineNum"> 560 </span> : */ -<span class="lineNum"> 561 </span> : template<typename _RandomAccessIterator, typename _Compare> -<span class="lineNum"> 562 </span> : inline bool -<span class="lineNum"> 563 </span> : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, -<span class="lineNum"> 564 </span> : _Compare __comp) -<span class="lineNum"> 565 </span> : { return std::is_heap_until(__first, __last, __comp) == __last; } -<span class="lineNum"> 566 </span> : #endif -<span class="lineNum"> 567 </span> : -<span class="lineNum"> 568 </span> : _GLIBCXX_END_NAMESPACE -<span class="lineNum"> 569 </span> : -<span class="lineNum"> 570 </span> : #endif /* _STL_HEAP_H */ -</pre> - </td> - </tr> - </table> - <br> - - <table width="100%" border=0 cellspacing=0 cellpadding=0> - <tr><td class="ruler"><img src="../../../../../glass.png" width=3 height=3 alt=""></td></tr> - <tr><td class="versionInfo">Generated by: <a href="http://ltp.sourceforge.net/coverage/lcov.php" target="_parent">LTP GCOV extension version 1.6</a></td></tr> - </table> - <br> - -</body> -</html> |