[thirdparty/gcc.git] / libstdc++-v3 / include / bits / stl_heap.h

// Heap implementation -*- C++ -*-

// Copyright (C) 2001 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 * Copyright (c) 1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file stl_heap.h
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#ifndef _STL_HEAP_H
#define _STL_HEAP_H 1

#include <debug/debug.h>

namespace std
{
  // is_heap, a predicate testing whether or not a range is
  // a heap.  This function is an extension, not part of the C++
  // standard.
  template<typename _RandomAccessIterator, typename _Distance>
    bool
    __is_heap(_RandomAccessIterator __first, _Distance __n)
    {
      _Distance __parent = 0;
      for (_Distance __child = 1; __child < __n; ++__child) {
	if (__first[__parent] < __first[__child]) 
	  return false;
	if ((__child & 1) == 0)
	  ++__parent;
      }
      return true;
    }

  template<typename _RandomAccessIterator, typename _Distance,
           typename _StrictWeakOrdering>
    bool
    __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
	      _Distance __n)
    {
      _Distance __parent = 0;
      for (_Distance __child = 1; __child < __n; ++__child) {
	if (__comp(__first[__parent], __first[__child]))
	  return false;
	if ((__child & 1) == 0)
	  ++__parent;
      }
      return true;
    }

  template<typename _RandomAccessIterator>
    bool
    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    { return std::__is_heap(__first, std::distance(__first, __last)); }

  template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
    bool
    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	    _StrictWeakOrdering __comp)
    { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }

  // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.

  template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
    void 
    __push_heap(_RandomAccessIterator __first,
		_Distance __holeIndex, _Distance __topIndex, _Tp __value)
    {
      _Distance __parent = (__holeIndex - 1) / 2;
      while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
	*(__first + __holeIndex) = *(__first + __parent);
	__holeIndex = __parent;
	__parent = (__holeIndex - 1) / 2;
      }    
      *(__first + __holeIndex) = __value;
    }

  /**
   *  @brief  Push an element onto a heap.
   *  @param  first  Start of heap.
   *  @param  last   End of heap + element.
   *  @ingroup heap
   *
   *  This operation pushes the element at last-1 onto the valid heap over the
   *  range [first,last-1).  After completion, [first,last) is a valid heap.
  */
  template<typename _RandomAccessIterator>
    inline void 
    push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	  _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	  _DistanceType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
      __glibcxx_requires_valid_range(__first, __last);
      //      __glibcxx_requires_heap(__first, __last - 1);

      std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
		       _ValueType(*(__last - 1)));
    }

  template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 
	    typename _Compare>
    void
    __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
		_Distance __topIndex, _Tp __value, _Compare __comp)
    {
      _Distance __parent = (__holeIndex - 1) / 2;
      while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
	*(__first + __holeIndex) = *(__first + __parent);
	__holeIndex = __parent;
	__parent = (__holeIndex - 1) / 2;
      }
      *(__first + __holeIndex) = __value;
    }

  /**
   *  @brief  Push an element onto a heap using comparison functor.
   *  @param  first  Start of heap.
   *  @param  last   End of heap + element.
   *  @param  comp   Comparison functor.
   *  @ingroup heap
   *
   *  This operation pushes the element at last-1 onto the valid heap over the
   *  range [first,last-1).  After completion, [first,last) is a valid heap.
   *  Compare operations are performed using comp.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    inline void 
    push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	      _Compare __comp)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	  _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	  _DistanceType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_heap_pred(__first, __last - 1, __comp);

      std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
		       _ValueType(*(__last - 1)), __comp);
    }

  template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
    void 
    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
		  _Distance __len, _Tp __value)
    {
      _Distance __topIndex = __holeIndex;
      _Distance __secondChild = 2 * __holeIndex + 2;
      while (__secondChild < __len) {
	if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
	  __secondChild--;
	*(__first + __holeIndex) = *(__first + __secondChild);
	__holeIndex = __secondChild;
	__secondChild = 2 * (__secondChild + 1);
      }
      if (__secondChild == __len) {
	*(__first + __holeIndex) = *(__first + (__secondChild - 1));
	__holeIndex = __secondChild - 1;
      }
      std::__push_heap(__first, __holeIndex, __topIndex, __value);
    }

  template<typename _RandomAccessIterator, typename _Tp>
    inline void 
    __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	       _RandomAccessIterator __result, _Tp __value)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
      *__result = *__first;
      std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
    }

  /**
   *  @brief  Pop an element off a heap.
   *  @param  first  Start of heap.
   *  @param  last   End of heap.
   *  @ingroup heap
   *
   *  This operation pops the top of the heap.  The elements first and last-1
   *  are swapped and [first,last-1) is made into a heap.
  */
  template<typename _RandomAccessIterator>
    inline void
    pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_heap(__first, __last);

      std::__pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)));
    }

  template<typename _RandomAccessIterator, typename _Distance,
	   typename _Tp, typename _Compare>
    void
    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
		  _Distance __len, _Tp __value, _Compare __comp)
    {
      _Distance __topIndex = __holeIndex;
      _Distance __secondChild = 2 * __holeIndex + 2;
      while (__secondChild < __len) {
	if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
	  __secondChild--;
	*(__first + __holeIndex) = *(__first + __secondChild);
	__holeIndex = __secondChild;
	__secondChild = 2 * (__secondChild + 1);
      }
      if (__secondChild == __len) {
	*(__first + __holeIndex) = *(__first + (__secondChild - 1));
	__holeIndex = __secondChild - 1;
      }
      std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
    }

  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
    inline void 
    __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	       _RandomAccessIterator __result, _Tp __value, _Compare __comp)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
      *__result = *__first;
      std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
			 __value, __comp);
    }

  /**
   *  @brief  Pop an element off a heap using comparison functor.
   *  @param  first  Start of heap.
   *  @param  last   End of heap.
   *  @param  comp   Comparison functor to use.
   *  @ingroup heap
   *
   *  This operation pops the top of the heap.  The elements first and last-1
   *  are swapped and [first,last-1) is made into a heap.  Comparisons are
   *  made using comp.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    inline void 
    pop_heap(_RandomAccessIterator __first,
	     _RandomAccessIterator __last, _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_heap_pred(__first, __last, __comp);

      typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
      std::__pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
    }

  /**
   *  @brief  Construct a heap over a range.
   *  @param  first  Start of heap.
   *  @param  last   End of heap.
   *  @ingroup heap
   *
   *  This operation makes the elements in [first,last) into a heap.
  */
  template<typename _RandomAccessIterator>
    void 
    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	  _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	  _DistanceType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__last - __first < 2) return;
      _DistanceType __len = __last - __first;
      _DistanceType __parent = (__len - 2)/2;
	
      while (true) {
	std::__adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent)));
	if (__parent == 0) return;
	__parent--;
      }
    }

  /**
   *  @brief  Construct a heap over a range using comparison functor.
   *  @param  first  Start of heap.
   *  @param  last   End of heap.
   *  @param  comp   Comparison functor to use.
   *  @ingroup heap
   *
   *  This operation makes the elements in [first,last) into a heap.
   *  Comparisons are made using comp.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    inline void 
    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	      _Compare __comp)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	  _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	  _DistanceType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      
      if (__last - __first < 2) return;
      _DistanceType __len = __last - __first;
      _DistanceType __parent = (__len - 2)/2;
	
      while (true) {
	std::__adjust_heap(__first, __parent, __len,
			   _ValueType(*(__first + __parent)), __comp);
	if (__parent == 0) return;
	__parent--;
      }
    }

  /**
   *  @brief  Sort a heap.
   *  @param  first  Start of heap.
   *  @param  last   End of heap.
   *  @ingroup heap
   *
   *  This operation sorts the valid heap in the range [first,last).
  */
  template<typename _RandomAccessIterator>
    void
    sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
	    typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
      //      __glibcxx_requires_heap(__first, __last);

      while (__last - __first > 1)
	std::pop_heap(__first, __last--);
    }

  /**
   *  @brief  Sort a heap using comparison functor.
   *  @param  first  Start of heap.
   *  @param  last   End of heap.
   *  @param  comp   Comparison functor to use.
   *  @ingroup heap
   *
   *  This operation sorts the valid heap in the range [first,last).
   *  Comparisons are made using comp.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    void 
    sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	      _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_heap_pred(__first, __last, __comp);

      while (__last - __first > 1)
	std::pop_heap(__first, __last--, __comp);
    }

} // namespace std

#endif /* _STL_HEAP_H */

// Local Variables:
// mode:C++
// End:
Commit	Line	Data
42526146 PE	1	// Heap implementation -- C++ --
	2
	3	// Copyright (C) 2001 Free Software Foundation, Inc.
	4	//
	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)
	9	// any later version.
	10
	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.
	15
	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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
	19	// USA.
	20
	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.
	29
725dc051 BK	30	/*
	31	*
	32	* Copyright (c) 1994
	33	* Hewlett-Packard Company
	34	*
	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.
	42	*
	43	* Copyright (c) 1997
	44	* Silicon Graphics Computer Systems, Inc.
	45	*
	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.
	53	*/
	54
729e3d3f PE	55	/** @file stl_heap.h
	56	* This is an internal header file, included by other library headers.
	57	* You should not attempt to use it directly.
725dc051 BK	58	*/
725dc051 BK	59
3d7c150e BK	60	#ifndef _STL_HEAP_H
3d7c150e BK	61	#define _STL_HEAP_H 1
725dc051	62
285b36d6 BK	63	#include <debug/debug.h>
285b36d6 BK	64
d53d7f6e PE	65	namespace std
d53d7f6e PE	66	{
285b36d6 BK	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++
	69	// standard.
	70	template<typename _RandomAccessIterator, typename _Distance>
	71	bool
	72	__is_heap(_RandomAccessIterator __first, _Distance __n)
	73	{
	74	_Distance __parent = 0;
	75	for (_Distance __child = 1; __child < __n; ++__child) {
	76	if (__first[__parent] < __first[__child])
	77	return false;
	78	if ((__child & 1) == 0)
	79	++__parent;
	80	}
	81	return true;
	82	}
	83
	84	template<typename _RandomAccessIterator, typename _Distance,
	85	typename _StrictWeakOrdering>
	86	bool
	87	__is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
	88	_Distance __n)
	89	{
	90	_Distance __parent = 0;
	91	for (_Distance __child = 1; __child < __n; ++__child) {
	92	if (__comp(__first[__parent], __first[__child]))
	93	return false;
	94	if ((__child & 1) == 0)
	95	++__parent;
	96	}
	97	return true;
	98	}
	99
	100	template<typename _RandomAccessIterator>
	101	bool
	102	__is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
	103	{ return std::__is_heap(__first, std::distance(__first, __last)); }
	104
	105	template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
	106	bool
	107	__is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	108	_StrictWeakOrdering __comp)
	109	{ return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
725dc051	110
02d92e3b SW	111	// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
	112
	113	template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
	114	void
	115	__push_heap(_RandomAccessIterator __first,
	116	_Distance __holeIndex, _Distance __topIndex, _Tp __value)
	117	{
	118	_Distance __parent = (__holeIndex - 1) / 2;
	119	while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
	120	(__first + __holeIndex) = (__first + __parent);
	121	__holeIndex = __parent;
	122	__parent = (__holeIndex - 1) / 2;
	123	}
	124	*(__first + __holeIndex) = __value;
	125	}
	126
119dbb1f JQ	127	/**
	128	* @brief Push an element onto a heap.
	129	* @param first Start of heap.
	130	* @param last End of heap + element.
	131	* @ingroup heap
	132	*
	133	* This operation pushes the element at last-1 onto the valid heap over the
	134	* range [first,last-1). After completion, [first,last) is a valid heap.
	135	*/
02d92e3b SW	136	template<typename _RandomAccessIterator>
	137	inline void
	138	push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
	139	{
	140	typedef typename iterator_traits<_RandomAccessIterator>::value_type
	141	_ValueType;
	142	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	143	_DistanceType;
	144
	145	// concept requirements
3d7c150e	146	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4d16bdbb	147	_RandomAccessIterator>)
3d7c150e	148	__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
285b36d6 BK	149	__glibcxx_requires_valid_range(__first, __last);
285b36d6 BK	150	// __glibcxx_requires_heap(__first, __last - 1);
02d92e3b	151
369b78b0 PC	152	std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0),
369b78b0 PC	153	_ValueType(*(__last - 1)));
02d92e3b SW	154	}
	155
	156	template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
	157	typename _Compare>
	158	void
	159	__push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
	160	_Distance __topIndex, _Tp __value, _Compare __comp)
	161	{
	162	_Distance __parent = (__holeIndex - 1) / 2;
	163	while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
	164	(__first + __holeIndex) = (__first + __parent);
	165	__holeIndex = __parent;
	166	__parent = (__holeIndex - 1) / 2;
	167	}
	168	*(__first + __holeIndex) = __value;
	169	}
	170
119dbb1f JQ	171	/**
	172	* @brief Push an element onto a heap using comparison functor.
	173	* @param first Start of heap.
	174	* @param last End of heap + element.
	175	* @param comp Comparison functor.
	176	* @ingroup heap
	177	*
	178	* This operation pushes the element at last-1 onto the valid heap over the
	179	* range [first,last-1). After completion, [first,last) is a valid heap.
	180	* Compare operations are performed using comp.
	181	*/
02d92e3b SW	182	template<typename _RandomAccessIterator, typename _Compare>
	183	inline void
	184	push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	185	_Compare __comp)
	186	{
	187	typedef typename iterator_traits<_RandomAccessIterator>::value_type
	188	_ValueType;
	189	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	190	_DistanceType;
	191
	192	// concept requirements
3d7c150e	193	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4d16bdbb	194	_RandomAccessIterator>)
285b36d6 BK	195	__glibcxx_requires_valid_range(__first, __last);
285b36d6 BK	196	__glibcxx_requires_heap_pred(__first, __last - 1, __comp);
02d92e3b	197
369b78b0 PC	198	std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0),
369b78b0 PC	199	_ValueType(*(__last - 1)), __comp);
02d92e3b SW	200	}
	201
	202	template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
	203	void
	204	__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
	205	_Distance __len, _Tp __value)
	206	{
	207	_Distance __topIndex = __holeIndex;
	208	_Distance __secondChild = 2 * __holeIndex + 2;
	209	while (__secondChild < __len) {
	210	if ((__first + __secondChild) < (__first + (__secondChild - 1)))
	211	__secondChild--;
	212	(__first + __holeIndex) = (__first + __secondChild);
	213	__holeIndex = __secondChild;
	214	__secondChild = 2 * (__secondChild + 1);
	215	}
	216	if (__secondChild == __len) {
	217	(__first + __holeIndex) = (__first + (__secondChild - 1));
	218	__holeIndex = __secondChild - 1;
	219	}
369b78b0	220	std::__push_heap(__first, __holeIndex, __topIndex, __value);
02d92e3b SW	221	}
	222
	223	template<typename _RandomAccessIterator, typename _Tp>
	224	inline void
	225	__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	226	_RandomAccessIterator __result, _Tp __value)
	227	{
	228	typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
	229	__result = __first;
369b78b0	230	std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
02d92e3b SW	231	}
02d92e3b SW	232
119dbb1f JQ	233	/**
	234	* @brief Pop an element off a heap.
	235	* @param first Start of heap.
	236	* @param last End of heap.
	237	* @ingroup heap
	238	*
	239	* This operation pops the top of the heap. The elements first and last-1
	240	* are swapped and [first,last-1) is made into a heap.
	241	*/
02d92e3b SW	242	template<typename _RandomAccessIterator>
	243	inline void
	244	pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
	245	{
	246	typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
	247
	248	// concept requirements
3d7c150e	249	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4d16bdbb	250	_RandomAccessIterator>)
3d7c150e	251	__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
285b36d6 BK	252	__glibcxx_requires_valid_range(__first, __last);
285b36d6 BK	253	__glibcxx_requires_heap(__first, __last);
02d92e3b	254
369b78b0	255	std::__pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)));
02d92e3b SW	256	}
	257
	258	template<typename _RandomAccessIterator, typename _Distance,
	259	typename _Tp, typename _Compare>
	260	void
	261	__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
	262	_Distance __len, _Tp __value, _Compare __comp)
	263	{
	264	_Distance __topIndex = __holeIndex;
	265	_Distance __secondChild = 2 * __holeIndex + 2;
	266	while (__secondChild < __len) {
	267	if (__comp((__first + __secondChild), (__first + (__secondChild - 1))))
	268	__secondChild--;
	269	(__first + __holeIndex) = (__first + __secondChild);
	270	__holeIndex = __secondChild;
	271	__secondChild = 2 * (__secondChild + 1);
	272	}
	273	if (__secondChild == __len) {
	274	(__first + __holeIndex) = (__first + (__secondChild - 1));
	275	__holeIndex = __secondChild - 1;
	276	}
369b78b0	277	std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
02d92e3b SW	278	}
	279
	280	template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
	281	inline void
	282	__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	283	_RandomAccessIterator __result, _Tp __value, _Compare __comp)
	284	{
	285	typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
	286	__result = __first;
369b78b0 PC	287	std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
369b78b0 PC	288	__value, __comp);
02d92e3b SW	289	}
02d92e3b SW	290
119dbb1f JQ	291	/**
	292	* @brief Pop an element off a heap using comparison functor.
	293	* @param first Start of heap.
	294	* @param last End of heap.
	295	* @param comp Comparison functor to use.
	296	* @ingroup heap
	297	*
	298	* This operation pops the top of the heap. The elements first and last-1
	299	* are swapped and [first,last-1) is made into a heap. Comparisons are
	300	* made using comp.
	301	*/
02d92e3b SW	302	template<typename _RandomAccessIterator, typename _Compare>
	303	inline void
	304	pop_heap(_RandomAccessIterator __first,
	305	_RandomAccessIterator __last, _Compare __comp)
	306	{
	307	// concept requirements
3d7c150e	308	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4d16bdbb	309	_RandomAccessIterator>)
285b36d6 BK	310	__glibcxx_requires_valid_range(__first, __last);
285b36d6 BK	311	__glibcxx_requires_heap_pred(__first, __last, __comp);
02d92e3b SW	312
02d92e3b SW	313	typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
369b78b0	314	std::__pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
02d92e3b SW	315	}
02d92e3b SW	316
119dbb1f JQ	317	/**
	318	* @brief Construct a heap over a range.
	319	* @param first Start of heap.
	320	* @param last End of heap.
	321	* @ingroup heap
	322	*
	323	* This operation makes the elements in [first,last) into a heap.
	324	*/
02d92e3b SW	325	template<typename _RandomAccessIterator>
	326	void
	327	make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
	328	{
	329	typedef typename iterator_traits<_RandomAccessIterator>::value_type
	330	_ValueType;
	331	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	332	_DistanceType;
	333
	334	// concept requirements
3d7c150e	335	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4d16bdbb	336	_RandomAccessIterator>)
3d7c150e	337	__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
285b36d6	338	__glibcxx_requires_valid_range(__first, __last);
02d92e3b SW	339
	340	if (__last - __first < 2) return;
	341	_DistanceType __len = __last - __first;
	342	_DistanceType __parent = (__len - 2)/2;
	343
	344	while (true) {
369b78b0	345	std::__adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent)));
02d92e3b SW	346	if (__parent == 0) return;
	347	__parent--;
	348	}
	349	}
	350
119dbb1f JQ	351	/**
	352	* @brief Construct a heap over a range using comparison functor.
	353	* @param first Start of heap.
	354	* @param last End of heap.
	355	* @param comp Comparison functor to use.
	356	* @ingroup heap
	357	*
	358	* This operation makes the elements in [first,last) into a heap.
	359	* Comparisons are made using comp.
	360	*/
02d92e3b SW	361	template<typename _RandomAccessIterator, typename _Compare>
	362	inline void
	363	make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	364	_Compare __comp)
	365	{
	366	typedef typename iterator_traits<_RandomAccessIterator>::value_type
	367	_ValueType;
	368	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	369	_DistanceType;
	370
	371	// concept requirements
3d7c150e	372	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4d16bdbb	373	_RandomAccessIterator>)
285b36d6 BK	374	__glibcxx_requires_valid_range(__first, __last);
285b36d6 BK	375
02d92e3b SW	376	if (__last - __first < 2) return;
	377	_DistanceType __len = __last - __first;
	378	_DistanceType __parent = (__len - 2)/2;
	379
	380	while (true) {
369b78b0 PC	381	std::__adjust_heap(__first, __parent, __len,
369b78b0 PC	382	_ValueType(*(__first + __parent)), __comp);
02d92e3b SW	383	if (__parent == 0) return;
	384	__parent--;
	385	}
	386	}
	387
119dbb1f JQ	388	/**
	389	* @brief Sort a heap.
	390	* @param first Start of heap.
	391	* @param last End of heap.
	392	* @ingroup heap
	393	*
	394	* This operation sorts the valid heap in the range [first,last).
	395	*/
02d92e3b SW	396	template<typename _RandomAccessIterator>
	397	void
	398	sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
	399	{
	400	// concept requirements
3d7c150e	401	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4d16bdbb	402	_RandomAccessIterator>)
3d7c150e	403	__glibcxx_function_requires(_LessThanComparableConcept<
4d16bdbb	404	typename iterator_traits<_RandomAccessIterator>::value_type>)
285b36d6 BK	405	__glibcxx_requires_valid_range(__first, __last);
285b36d6 BK	406	// __glibcxx_requires_heap(__first, __last);
02d92e3b SW	407
02d92e3b SW	408	while (__last - __first > 1)
369b78b0	409	std::pop_heap(__first, __last--);
02d92e3b SW	410	}
02d92e3b SW	411
119dbb1f JQ	412	/**
	413	* @brief Sort a heap using comparison functor.
	414	* @param first Start of heap.
	415	* @param last End of heap.
	416	* @param comp Comparison functor to use.
	417	* @ingroup heap
	418	*
	419	* This operation sorts the valid heap in the range [first,last).
	420	* Comparisons are made using comp.
	421	*/
02d92e3b SW	422	template<typename _RandomAccessIterator, typename _Compare>
	423	void
	424	sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	425	_Compare __comp)
	426	{
	427	// concept requirements
3d7c150e	428	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4d16bdbb	429	_RandomAccessIterator>)
285b36d6 BK	430	__glibcxx_requires_valid_range(__first, __last);
285b36d6 BK	431	__glibcxx_requires_heap_pred(__first, __last, __comp);
02d92e3b SW	432
02d92e3b SW	433	while (__last - __first > 1)
369b78b0	434	std::pop_heap(__first, __last--, __comp);
02d92e3b	435	}
725dc051	436
d53d7f6e	437	} // namespace std
725dc051	438
3d7c150e	439	#endif /* _STL_HEAP_H */
725dc051 BK	440
	441	// Local Variables:
	442	// mode:C++
	443	// End: