1 // Heap implementation -*- C++ -*-
3 // Copyright (C) 2001, 2004, 2005, 2006 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
33 * Hewlett-Packard Company
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
44 * Silicon Graphics Computer Systems, Inc.
46 * Permission to use, copy, modify, distribute and sell this software
47 * and its documentation for any purpose is hereby granted without fee,
48 * provided that the above copyright notice appear in all copies and
49 * that both that copyright notice and this permission notice appear
50 * in supporting documentation. Silicon Graphics makes no
51 * representations about the suitability of this software for any
52 * purpose. It is provided "as is" without express or implied warranty.
56 * This is an internal header file, included by other library headers.
57 * You should not attempt to use it directly.
63 #include <debug/debug.h>
65 _GLIBCXX_BEGIN_NAMESPACE(std)
67 // is_heap, a predicate testing whether or not a range is
68 // a heap. This function is an extension, not part of the C++
70 template<typename _RandomAccessIterator, typename _Distance>
72 __is_heap(_RandomAccessIterator __first, _Distance __n)
74 _Distance __parent = 0;
75 for (_Distance __child = 1; __child < __n; ++__child)
77 if (__first[__parent] < __first[__child])
79 if ((__child & 1) == 0)
85 template<typename _RandomAccessIterator, typename _Distance,
86 typename _StrictWeakOrdering>
88 __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
91 _Distance __parent = 0;
92 for (_Distance __child = 1; __child < __n; ++__child)
94 if (__comp(__first[__parent], __first[__child]))
96 if ((__child & 1) == 0)
102 template<typename _RandomAccessIterator>
104 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
105 { return std::__is_heap(__first, std::distance(__first, __last)); }
107 template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
109 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
110 _StrictWeakOrdering __comp)
111 { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
113 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
115 template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
117 __push_heap(_RandomAccessIterator __first,
118 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
120 _Distance __parent = (__holeIndex - 1) / 2;
121 while (__holeIndex > __topIndex && *(__first + __parent) < __value)
123 *(__first + __holeIndex) = *(__first + __parent);
124 __holeIndex = __parent;
125 __parent = (__holeIndex - 1) / 2;
127 *(__first + __holeIndex) = __value;
131 * @brief Push an element onto a heap.
132 * @param first Start of heap.
133 * @param last End of heap + element.
136 * This operation pushes the element at last-1 onto the valid heap over the
137 * range [first,last-1). After completion, [first,last) is a valid heap.
139 template<typename _RandomAccessIterator>
141 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
143 typedef typename iterator_traits<_RandomAccessIterator>::value_type
145 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
148 // concept requirements
149 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
150 _RandomAccessIterator>)
151 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
152 __glibcxx_requires_valid_range(__first, __last);
153 // __glibcxx_requires_heap(__first, __last - 1);
155 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
156 _DistanceType(0), _ValueType(*(__last - 1)));
159 template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
162 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
163 _Distance __topIndex, _Tp __value, _Compare __comp)
165 _Distance __parent = (__holeIndex - 1) / 2;
166 while (__holeIndex > __topIndex
167 && __comp(*(__first + __parent), __value))
169 *(__first + __holeIndex) = *(__first + __parent);
170 __holeIndex = __parent;
171 __parent = (__holeIndex - 1) / 2;
173 *(__first + __holeIndex) = __value;
177 * @brief Push an element onto a heap using comparison functor.
178 * @param first Start of heap.
179 * @param last End of heap + element.
180 * @param comp Comparison functor.
183 * This operation pushes the element at last-1 onto the valid heap over the
184 * range [first,last-1). After completion, [first,last) is a valid heap.
185 * Compare operations are performed using comp.
187 template<typename _RandomAccessIterator, typename _Compare>
189 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
192 typedef typename iterator_traits<_RandomAccessIterator>::value_type
194 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
197 // concept requirements
198 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
199 _RandomAccessIterator>)
200 __glibcxx_requires_valid_range(__first, __last);
201 __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
203 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
204 _DistanceType(0), _ValueType(*(__last - 1)), __comp);
207 template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
209 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
210 _Distance __len, _Tp __value)
212 const _Distance __topIndex = __holeIndex;
213 _Distance __secondChild = 2 * __holeIndex + 2;
214 while (__secondChild < __len)
216 if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
218 *(__first + __holeIndex) = *(__first + __secondChild);
219 __holeIndex = __secondChild;
220 __secondChild = 2 * (__secondChild + 1);
222 if (__secondChild == __len)
224 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
225 __holeIndex = __secondChild - 1;
227 std::__push_heap(__first, __holeIndex, __topIndex, __value);
230 template<typename _RandomAccessIterator, typename _Tp>
232 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
233 _RandomAccessIterator __result, _Tp __value)
235 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
237 *__result = *__first;
238 std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
243 * @brief Pop an element off a heap.
244 * @param first Start of heap.
245 * @param last End of heap.
248 * This operation pops the top of the heap. The elements first and last-1
249 * are swapped and [first,last-1) is made into a heap.
251 template<typename _RandomAccessIterator>
253 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
255 typedef typename iterator_traits<_RandomAccessIterator>::value_type
258 // concept requirements
259 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
260 _RandomAccessIterator>)
261 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
262 __glibcxx_requires_valid_range(__first, __last);
263 __glibcxx_requires_heap(__first, __last);
265 std::__pop_heap(__first, __last - 1, __last - 1,
266 _ValueType(*(__last - 1)));
269 template<typename _RandomAccessIterator, typename _Distance,
270 typename _Tp, typename _Compare>
272 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
273 _Distance __len, _Tp __value, _Compare __comp)
275 const _Distance __topIndex = __holeIndex;
276 _Distance __secondChild = 2 * __holeIndex + 2;
277 while (__secondChild < __len)
279 if (__comp(*(__first + __secondChild),
280 *(__first + (__secondChild - 1))))
282 *(__first + __holeIndex) = *(__first + __secondChild);
283 __holeIndex = __secondChild;
284 __secondChild = 2 * (__secondChild + 1);
286 if (__secondChild == __len)
288 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
289 __holeIndex = __secondChild - 1;
291 std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
294 template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
296 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
297 _RandomAccessIterator __result, _Tp __value, _Compare __comp)
299 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
301 *__result = *__first;
302 std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
307 * @brief Pop an element off a heap using comparison functor.
308 * @param first Start of heap.
309 * @param last End of heap.
310 * @param comp Comparison functor to use.
313 * This operation pops the top of the heap. The elements first and last-1
314 * are swapped and [first,last-1) is made into a heap. Comparisons are
317 template<typename _RandomAccessIterator, typename _Compare>
319 pop_heap(_RandomAccessIterator __first,
320 _RandomAccessIterator __last, _Compare __comp)
322 // concept requirements
323 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
324 _RandomAccessIterator>)
325 __glibcxx_requires_valid_range(__first, __last);
326 __glibcxx_requires_heap_pred(__first, __last, __comp);
328 typedef typename iterator_traits<_RandomAccessIterator>::value_type
330 std::__pop_heap(__first, __last - 1, __last - 1,
331 _ValueType(*(__last - 1)), __comp);
335 * @brief Construct a heap over a range.
336 * @param first Start of heap.
337 * @param last End of heap.
340 * This operation makes the elements in [first,last) into a heap.
342 template<typename _RandomAccessIterator>
344 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
346 typedef typename iterator_traits<_RandomAccessIterator>::value_type
348 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
351 // concept requirements
352 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
353 _RandomAccessIterator>)
354 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
355 __glibcxx_requires_valid_range(__first, __last);
357 if (__last - __first < 2)
360 const _DistanceType __len = __last - __first;
361 _DistanceType __parent = (__len - 2) / 2;
364 std::__adjust_heap(__first, __parent, __len,
365 _ValueType(*(__first + __parent)));
373 * @brief Construct a heap over a range using comparison functor.
374 * @param first Start of heap.
375 * @param last End of heap.
376 * @param comp Comparison functor to use.
379 * This operation makes the elements in [first,last) into a heap.
380 * Comparisons are made using comp.
382 template<typename _RandomAccessIterator, typename _Compare>
384 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
387 typedef typename iterator_traits<_RandomAccessIterator>::value_type
389 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
392 // concept requirements
393 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
394 _RandomAccessIterator>)
395 __glibcxx_requires_valid_range(__first, __last);
397 if (__last - __first < 2)
400 const _DistanceType __len = __last - __first;
401 _DistanceType __parent = (__len - 2) / 2;
404 std::__adjust_heap(__first, __parent, __len,
405 _ValueType(*(__first + __parent)), __comp);
413 * @brief Sort a heap.
414 * @param first Start of heap.
415 * @param last End of heap.
418 * This operation sorts the valid heap in the range [first,last).
420 template<typename _RandomAccessIterator>
422 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
424 // concept requirements
425 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
426 _RandomAccessIterator>)
427 __glibcxx_function_requires(_LessThanComparableConcept<
428 typename iterator_traits<_RandomAccessIterator>::value_type>)
429 __glibcxx_requires_valid_range(__first, __last);
430 // __glibcxx_requires_heap(__first, __last);
432 while (__last - __first > 1)
433 std::pop_heap(__first, _RandomAccessIterator(__last--));
437 * @brief Sort a heap using comparison functor.
438 * @param first Start of heap.
439 * @param last End of heap.
440 * @param comp Comparison functor to use.
443 * This operation sorts the valid heap in the range [first,last).
444 * Comparisons are made using comp.
446 template<typename _RandomAccessIterator, typename _Compare>
448 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
451 // concept requirements
452 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
453 _RandomAccessIterator>)
454 __glibcxx_requires_valid_range(__first, __last);
455 __glibcxx_requires_heap_pred(__first, __last, __comp);
457 while (__last - __first > 1)
458 std::pop_heap(__first, _RandomAccessIterator(__last--), __comp);
461 _GLIBCXX_END_NAMESPACE
463 #endif /* _STL_HEAP_H */