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