Home | History | Annotate | Download | only in stl 
      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:
    126