williamr@2: /*
williamr@2:  *
williamr@2:  * Copyright (c) 1994
williamr@2:  * Hewlett-Packard Company
williamr@2:  *
williamr@2:  * Permission to use, copy, modify, distribute and sell this software
williamr@2:  * and its documentation for any purpose is hereby granted without fee,
williamr@2:  * provided that the above copyright notice appear in all copies and
williamr@2:  * that both that copyright notice and this permission notice appear
williamr@2:  * in supporting documentation.  Hewlett-Packard Company makes no
williamr@2:  * representations about the suitability of this software for any
williamr@2:  * purpose.  It is provided "as is" without express or implied warranty.
williamr@2:  *
williamr@2:  * Copyright (c) 1997
williamr@2:  * Silicon Graphics Computer Systems, Inc.
williamr@2:  *
williamr@2:  * Permission to use, copy, modify, distribute and sell this software
williamr@2:  * and its documentation for any purpose is hereby granted without fee,
williamr@2:  * provided that the above copyright notice appear in all copies and
williamr@2:  * that both that copyright notice and this permission notice appear
williamr@2:  * in supporting documentation.  Silicon Graphics makes no
williamr@2:  * representations about the suitability of this software for any
williamr@2:  * purpose.  It is provided "as is" without express or implied warranty.
williamr@2:  */
williamr@2: 
williamr@2: /* NOTE: This is an internal header file, included by other STL headers.
williamr@2:  *   You should not attempt to use it directly.
williamr@2:  */
williamr@2: 
williamr@2: #ifndef _STLP_INTERNAL_HEAP_H
williamr@2: #define _STLP_INTERNAL_HEAP_H
williamr@2: 
williamr@2: #ifndef _STLP_CONFIG_H
williamr@2: #include <stl/_config.h>
williamr@2: #endif
williamr@2: 
williamr@2: _STLP_BEGIN_NAMESPACE
williamr@2: 
williamr@2: // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
williamr@2: 
williamr@2: template <class _RandomAccessIterator>
williamr@2: void 
williamr@2: push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last);
williamr@2: 
williamr@2: 
williamr@2: template <class _RandomAccessIterator, class _Compare>
williamr@2: void 
williamr@2: push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
williamr@2:           _Compare __comp);
williamr@2: 
williamr@2: template <class _RandomAccessIterator, class _Distance, class _Tp>
williamr@2: void 
williamr@2: __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
williamr@2:               _Distance __len, _Tp __val);
williamr@2: 
williamr@2: template <class _RandomAccessIterator, class _Tp, class _Distance>
williamr@2: inline void 
williamr@2: __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
williamr@2:            _RandomAccessIterator __result, _Tp __val, _Distance*)
williamr@2: {
williamr@2:   *__result = *__first;
williamr@2:   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __val);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIterator>
williamr@2: void pop_heap(_RandomAccessIterator __first, 
williamr@2: 	      _RandomAccessIterator __last);
williamr@2: 
williamr@2: template <class _RandomAccessIterator, class _Distance,
williamr@2:           class _Tp, class _Compare>
williamr@2: void
williamr@2: __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
williamr@2:               _Distance __len, _Tp __val, _Compare __comp);
williamr@2: 
williamr@2: template <class _RandomAccessIterator, class _Tp, class _Compare, 
williamr@2:           class _Distance>
williamr@2: inline void 
williamr@2: __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
williamr@2:            _RandomAccessIterator __result, _Tp __val, _Compare __comp,
williamr@2:            _Distance*)
williamr@2: {
williamr@2:   *__result = *__first;
williamr@2:   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
williamr@2:                 __val, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIterator, class _Compare>
williamr@2: void 
williamr@2: pop_heap(_RandomAccessIterator __first,
williamr@2:          _RandomAccessIterator __last, _Compare __comp);
williamr@2: 
williamr@2: template <class _RandomAccessIterator>
williamr@2: void 
williamr@2: make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last);
williamr@2: 
williamr@2: template <class _RandomAccessIterator, class _Compare>
williamr@2: void 
williamr@2: make_heap(_RandomAccessIterator __first, 
williamr@2:           _RandomAccessIterator __last, _Compare __comp);
williamr@2: 
williamr@2: template <class _RandomAccessIterator>
williamr@2: _STLP_INLINE_LOOP
williamr@2: void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
williamr@2: {
williamr@2:   while (__last - __first > 1)
williamr@2:     pop_heap(__first, __last--);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIterator, class _Compare>
williamr@2: _STLP_INLINE_LOOP
williamr@2: void 
williamr@2: sort_heap(_RandomAccessIterator __first,
williamr@2:           _RandomAccessIterator __last, _Compare __comp)
williamr@2: {
williamr@2:   while (__last - __first > 1)
williamr@2:     pop_heap(__first, __last--, __comp);
williamr@2: }
williamr@2: 
williamr@2: _STLP_END_NAMESPACE
williamr@2: 
williamr@2: # if !defined (_STLP_LINK_TIME_INSTANTIATION)
williamr@2: #  include <stl/_heap.c>
williamr@2: # endif
williamr@2: 
williamr@2: #endif /* _STLP_INTERNAL_HEAP_H */
williamr@2: 
williamr@2: // Local Variables:
williamr@2: // mode:C++
williamr@2: // End: