19720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 29720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 39720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 49720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1994 59720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Hewlett-Packard Company 69720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 79720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1996,1997 89720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Silicon Graphics Computer Systems, Inc. 99720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1997 119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Moscow Center for SPARC Technology 129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1999 149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Boris Fomitchev 159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This material is provided "as is", with absolutely no warranty expressed 179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or implied. Any use is at your own risk. 189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to use or copy this software for any purpose is hereby granted 209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * without fee, provided the above notices are retained on all copies. 219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to modify the code and to distribute modified code is granted, 229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * provided the above notices are retained, and a notice that the code was 239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * modified is included with the above copyright notice. 249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_HEAP_C 279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_HEAP_C 289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_HEAP_H 309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_heap.h> 319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ITERATOR_BASE_H 349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_iterator_base.h> 359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Distance, class _Tp> 409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP 419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__push_heap(_RandomAccessIterator __first, 439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __holeIndex, _Distance __topIndex, _Tp __val) 449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __parent = (__holeIndex - 1) / 2; 469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__holeIndex > __topIndex && *(__first + __parent) < __val) { 479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + __holeIndex) = *(__first + __parent); 489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __holeIndex = __parent; 499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __parent = (__holeIndex - 1) / 2; 509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + __holeIndex) = __val; 529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Distance, class _Tp> 559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void 569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__push_heap_aux(_RandomAccessIterator __first, 579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIterator __last, _Distance*, _Tp*) 589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp(*(__last - 1))); 619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator> 649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpush_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __push_heap_aux(__first, __last, 689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator)); 699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Distance, class _Tp, 739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP 759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __topIndex, _Tp __val, _Compare __comp) 789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __parent = (__holeIndex - 1) / 2; 809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) { 819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(__val, *(__first + __parent)), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + __holeIndex) = *(__first + __parent); 839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __holeIndex = __parent; 849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __parent = (__holeIndex - 1) / 2; 859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + __holeIndex) = __val; 879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Compare, 909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Distance, class _Tp> 919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void 929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__push_heap_aux(_RandomAccessIterator __first, 939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIterator __last, _Compare __comp, 949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance*, _Tp*) 959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp(*(__last - 1)), __comp); 989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Compare> 1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpush_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) 1049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 1059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __push_heap_aux(__first, __last, __comp, 1069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator)); 1079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Distance, class _Tp> 1109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 1119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 1129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len, _Tp __val) { 1139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __topIndex = __holeIndex; 1149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __secondChild = 2 * __holeIndex + 2; 1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__secondChild < __len) { 1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) 1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __secondChild--; 1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + __holeIndex) = *(__first + __secondChild); 1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __holeIndex = __secondChild; 1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __secondChild = 2 * (__secondChild + 1); 1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__secondChild == __len) { 1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __holeIndex = __secondChild - 1; 1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __push_heap(__first, __holeIndex, __topIndex, __val); 1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Tp> 1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void 1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) { 1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __pop_heap(__first, __last - 1, __last - 1, 1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator)); 1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator> 1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid pop_heap(_RandomAccessIterator __first, 1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIterator __last) { 1409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator)); 1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Distance, 1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Tp, class _Compare> 1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len, _Tp __val, _Compare __comp) 1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __topIndex = __holeIndex; 1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __secondChild = 2 * __holeIndex + 2; 1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__secondChild < __len) { 1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) { 1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*(__first + (__secondChild - 1)), *(__first + __secondChild)), 1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __secondChild--; 1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + __holeIndex) = *(__first + __secondChild); 1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __holeIndex = __secondChild; 1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __secondChild = 2 * (__secondChild + 1); 1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__secondChild == __len) { 1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __holeIndex = __secondChild - 1; 1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __push_heap(__first, __holeIndex, __topIndex, __val, __comp); 1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Tp, class _Compare> 1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void 1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__pop_heap_aux(_RandomAccessIterator __first, 1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIterator __last, _Tp*, _Compare __comp) 1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp, 1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator)); 1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Compare> 1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpop_heap(_RandomAccessIterator __first, 1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIterator __last, _Compare __comp) 1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp); 1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Tp, class _Distance> 1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP 1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__make_heap(_RandomAccessIterator __first, 1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIterator __last, _Tp*, _Distance*) 1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__last - __first < 2) return; 1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len = __last - __first; 1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __parent = (__len - 2)/2; 1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;;) { 1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent))); 1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__parent == 0) return; 2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __parent--; 2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator> 2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockmake_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __make_heap(__first, __last, 2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator)); 2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Compare, 2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Tp, class _Distance> 2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP 2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp, _Tp*, _Distance*) 2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__last - __first < 2) return; 2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len = __last - __first; 2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __parent = (__len - 2)/2; 2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;;) { 2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)), 2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__parent == 0) return; 2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __parent--; 2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIterator, class _Compare> 2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockmake_heap(_RandomAccessIterator __first, 2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIterator __last, _Compare __comp) 2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __make_heap(__first, __last, __comp, 2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator)); 2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_HEAP_C */ 2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables: 2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++ 2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End: 247