include/c++/stl/stl/_heap.h

   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
  37 template <class _RandomAccessIterator>
  38 void
  39 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last);
  40
  41
  42 template <class _RandomAccessIterator, class _Compare>
  43 void
  44 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  45           _Compare __comp);
  46
  47 template <class _RandomAccessIterator, class _Distance, class _Tp>
  48 void
  49 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  50               _Distance __len, _Tp __val);
  51
  52 template <class _RandomAccessIterator, class _Tp, class _Distance>
  53 inline 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
  61 template <class _RandomAccessIterator>
  62 void pop_heap(_RandomAccessIterator __first,
  63         _RandomAccessIterator __last);
  64
  65 template <class _RandomAccessIterator, class _Distance,
  66           class _Tp, class _Compare>
  67 void
  68 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  69               _Distance __len, _Tp __val, _Compare __comp);
  70
  71 template <class _RandomAccessIterator, class _Tp, class _Compare,
  72           class _Distance>
  73 inline 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
  83 template <class _RandomAccessIterator, class _Compare>
  84 void
  85 pop_heap(_RandomAccessIterator __first,
  86          _RandomAccessIterator __last, _Compare __comp);
  87
  88 template <class _RandomAccessIterator>
  89 void
  90 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last);
  91
  92 template <class _RandomAccessIterator, class _Compare>
  93 void
  94 make_heap(_RandomAccessIterator __first,
  95           _RandomAccessIterator __last, _Compare __comp);
  96
  97 template <class _RandomAccessIterator>
  98 _STLP_INLINE_LOOP
  99 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 100 {
 101   while (__last - __first > 1)
 102     pop_heap(__first, __last--);
 103 }
 104
 105 template <class _RandomAccessIterator, class _Compare>
 106 _STLP_INLINE_LOOP
 107 void
 108 sort_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: