1/*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation.  Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose.  It is provided "as is" without express or implied warranty.
13 *
14 * Copyright (c) 1997
15 * Silicon Graphics Computer Systems, Inc.
16 *
17 * Permission to use, copy, modify, distribute and sell this software
18 * and its documentation for any purpose is hereby granted without fee,
19 * provided that the above copyright notice appear in all copies and
20 * that both that copyright notice and this permission notice appear
21 * in supporting documentation.  Silicon Graphics makes no
22 * representations about the suitability of this software for any
23 * purpose.  It is provided "as is" without express or implied warranty.
24 */
25
26/* NOTE: This is an internal header file, included by other STL headers.
27 *   You should not attempt to use it directly.
28 */
29
30#ifndef _STLP_INTERNAL_HEAP_H
31#define _STLP_INTERNAL_HEAP_H
32
33_STLP_BEGIN_NAMESPACE
34
35// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
36
37template <class _RandomAccessIterator>
38void
39push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last);
40
41
42template <class _RandomAccessIterator, class _Compare>
43void
44push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
45          _Compare __comp);
46
47template <class _RandomAccessIterator, class _Distance, class _Tp>
48void
49__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
50              _Distance __len, _Tp __val);
51
52template <class _RandomAccessIterator, class _Tp, class _Distance>
53inline void
54__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
55           _RandomAccessIterator __result, _Tp __val, _Distance*)
56{
57  *__result = *__first;
58  __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __val);
59}
60
61template <class _RandomAccessIterator>
62void pop_heap(_RandomAccessIterator __first,
63        _RandomAccessIterator __last);
64
65template <class _RandomAccessIterator, class _Distance,
66          class _Tp, class _Compare>
67void
68__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
69              _Distance __len, _Tp __val, _Compare __comp);
70
71template <class _RandomAccessIterator, class _Tp, class _Compare,
72          class _Distance>
73inline void
74__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
75           _RandomAccessIterator __result, _Tp __val, _Compare __comp,
76           _Distance*)
77{
78  *__result = *__first;
79  __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
80                __val, __comp);
81}
82
83template <class _RandomAccessIterator, class _Compare>
84void
85pop_heap(_RandomAccessIterator __first,
86         _RandomAccessIterator __last, _Compare __comp);
87
88template <class _RandomAccessIterator>
89void
90make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last);
91
92template <class _RandomAccessIterator, class _Compare>
93void
94make_heap(_RandomAccessIterator __first,
95          _RandomAccessIterator __last, _Compare __comp);
96
97template <class _RandomAccessIterator>
98_STLP_INLINE_LOOP
99void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
100{
101  while (__last - __first > 1)
102    pop_heap(__first, __last--);
103}
104
105template <class _RandomAccessIterator, class _Compare>
106_STLP_INLINE_LOOP
107void
108sort_heap(_RandomAccessIterator __first,
109          _RandomAccessIterator __last, _Compare __comp)
110{
111  while (__last - __first > 1)
112    pop_heap(__first, __last--, __comp);
113}
114
115_STLP_END_NAMESPACE
116
117# if !defined (_STLP_LINK_TIME_INSTANTIATION)
118#  include <stl/_heap.c>
119# endif
120
121#endif /* _STLP_INTERNAL_HEAP_H */
122
123// Local Variables:
124// mode:C++
125// End:
126