- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_heap.h

    00001 /*
    00002  *
    00003  * Copyright (c) 1994
    00004  * Hewlett-Packard Company
    00005  *
    00006  * Permission to use, copy, modify, distribute and sell this software
    00007  * and its documentation for any purpose is hereby granted without fee,
    00008  * provided that the above copyright notice appear in all copies and
    00009  * that both that copyright notice and this permission notice appear
    00010  * in supporting documentation.  Hewlett-Packard Company makes no
    00011  * representations about the suitability of this software for any
    00012  * purpose.  It is provided "as is" without express or implied warranty.
    00013  *
    00014  * Copyright (c) 1997
    00015  * Silicon Graphics Computer Systems, Inc.
    00016  *
    00017  * Permission to use, copy, modify, distribute and sell this software
    00018  * and its documentation for any purpose is hereby granted without fee,
    00019  * provided that the above copyright notice appear in all copies and
    00020  * that both that copyright notice and this permission notice appear
    00021  * in supporting documentation.  Silicon Graphics makes no
    00022  * representations about the suitability of this software for any
    00023  * purpose.  It is provided "as is" without express or implied warranty.
    00024  */
    00025
    00026 /* NOTE: This is an internal header file, included by other STL headers.
    00027  *   You should not attempt to use it directly.
    00028  */
    00029
    00030 #ifndef __SGI_STL_INTERNAL_HEAP_H
    00031 #define __SGI_STL_INTERNAL_HEAP_H
    00032
    00033 __STL_BEGIN_NAMESPACE
    00034
    00035 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00036 #pragma set woff 1209
    00037 #endif
    00038
    00039 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
    00040
    00041 template <class _RandomAccessIterator, class _Distance, class _Tp>
    00042 void
    00043 __push_heap(_RandomAccessIterator __first,
    00044             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
    00045 {
    00046   _Distance __parent = (__holeIndex - 1) / 2;
    00047   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
    00048     *(__first + __holeIndex) = *(__first + __parent);
    00049     __holeIndex = __parent;
    00050     __parent = (__holeIndex - 1) / 2;
    00051   }
    00052   *(__first + __holeIndex) = __value;
    00053 }
    00054
    00055 template <class _RandomAccessIterator, class _Distance, class _Tp>
    00056 inline void
    00057 __push_heap_aux(_RandomAccessIterator __first,
    00058                 _RandomAccessIterator __last, _Distance*, _Tp*)
    00059 {
    00060   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
    00061               _Tp(*(__last - 1)));
    00062 }
    00063
    00064 template <class _RandomAccessIterator>
    00065 inline void
    00066 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    00067 {
    00068   __push_heap_aux(__first, __last,
    00069                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
    00070 }
    00071
    00072 template <class _RandomAccessIterator, class _Distance, class _Tp,
    00073           class _Compare>
    00074 void
    00075 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
    00076             _Distance __topIndex, _Tp __value, _Compare __comp)
    00077 {
    00078   _Distance __parent = (__holeIndex - 1) / 2;
    00079   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
    00080     *(__first + __holeIndex) = *(__first + __parent);
    00081     __holeIndex = __parent;
    00082     __parent = (__holeIndex - 1) / 2;
    00083   }
    00084   *(__first + __holeIndex) = __value;
    00085 }
    00086
    00087 template <class _RandomAccessIterator, class _Compare,
    00088           class _Distance, class _Tp>
    00089 inline void
    00090 __push_heap_aux(_RandomAccessIterator __first,
    00091                 _RandomAccessIterator __last, _Compare __comp,
    00092                 _Distance*, _Tp*)
    00093 {
    00094   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
    00095               _Tp(*(__last - 1)), __comp);
    00096 }
    00097
    00098 template <class _RandomAccessIterator, class _Compare>
    00099 inline void
    00100 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00101           _Compare __comp)
    00102 {
    00103   __push_heap_aux(__first, __last, __comp,
    00104                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
    00105 }
    00106
    00107 template <class _RandomAccessIterator, class _Distance, class _Tp>
    00108 void
    00109 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
    00110               _Distance __len, _Tp __value)
    00111 {
    00112   _Distance __topIndex = __holeIndex;
    00113   _Distance __secondChild = 2 * __holeIndex + 2;
    00114   while (__secondChild < __len) {
    00115     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
    00116       __secondChild--;
    00117     *(__first + __holeIndex) = *(__first + __secondChild);
    00118     __holeIndex = __secondChild;
    00119     __secondChild = 2 * (__secondChild + 1);
    00120   }
    00121   if (__secondChild == __len) {
    00122     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    00123     __holeIndex = __secondChild - 1;
    00124   }
    00125   __push_heap(__first, __holeIndex, __topIndex, __value);
    00126 }
    00127
    00128 template <class _RandomAccessIterator, class _Tp, class _Distance>
    00129 inline void
    00130 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00131            _RandomAccessIterator __result, _Tp __value, _Distance*)
    00132 {
    00133   *__result = *__first;
    00134   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
    00135 }
    00136
    00137 template <class _RandomAccessIterator, class _Tp>
    00138 inline void
    00139 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00140                _Tp*)
    00141 {
    00142   __pop_heap(__first, __last - 1, __last - 1,
    00143              _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
    00144 }
    00145
    00146 template <class _RandomAccessIterator>
    00147 inline void pop_heap(_RandomAccessIterator __first,
    00148                      _RandomAccessIterator __last)
    00149 {
    00150   __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
    00151 }
    00152
    00153 template <class _RandomAccessIterator, class _Distance,
    00154           class _Tp, class _Compare>
    00155 void
    00156 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
    00157               _Distance __len, _Tp __value, _Compare __comp)
    00158 {
    00159   _Distance __topIndex = __holeIndex;
    00160   _Distance __secondChild = 2 * __holeIndex + 2;
    00161   while (__secondChild < __len) {
    00162     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
    00163       __secondChild--;
    00164     *(__first + __holeIndex) = *(__first + __secondChild);
    00165     __holeIndex = __secondChild;
    00166     __secondChild = 2 * (__secondChild + 1);
    00167   }
    00168   if (__secondChild == __len) {
    00169     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    00170     __holeIndex = __secondChild - 1;
    00171   }
    00172   __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
    00173 }
    00174
    00175 template <class _RandomAccessIterator, class _Tp, class _Compare,
    00176           class _Distance>
    00177 inline void
    00178 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00179            _RandomAccessIterator __result, _Tp __value, _Compare __comp,
    00180            _Distance*)
    00181 {
    00182   *__result = *__first;
    00183   __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
    00184                 __value, __comp);
    00185 }
    00186
    00187 template <class _RandomAccessIterator, class _Tp, class _Compare>
    00188 inline void
    00189 __pop_heap_aux(_RandomAccessIterator __first,
    00190                _RandomAccessIterator __last, _Tp*, _Compare __comp)
    00191 {
    00192   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
    00193              __DISTANCE_TYPE(__first));
    00194 }
    00195
    00196 template <class _RandomAccessIterator, class _Compare>
    00197 inline void
    00198 pop_heap(_RandomAccessIterator __first,
    00199          _RandomAccessIterator __last, _Compare __comp)
    00200 {
    00201     __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
    00202 }
    00203
    00204 template <class _RandomAccessIterator, class _Tp, class _Distance>
    00205 void
    00206 __make_heap(_RandomAccessIterator __first,
    00207             _RandomAccessIterator __last, _Tp*, _Distance*)
    00208 {
    00209   if (__last - __first < 2) return;
    00210   _Distance __len = __last - __first;
    00211   _Distance __parent = (__len - 2)/2;
    00212
    00213   while (true) {
    00214     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
    00215     if (__parent == 0) return;
    00216     __parent--;
    00217   }
    00218 }
    00219
    00220 template <class _RandomAccessIterator>
    00221 inline void
    00222 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    00223 {
    00224   __make_heap(__first, __last,
    00225               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
    00226 }
    00227
    00228 template <class _RandomAccessIterator, class _Compare,
    00229           class _Tp, class _Distance>
    00230 void
    00231 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00232             _Compare __comp, _Tp*, _Distance*)
    00233 {
    00234   if (__last - __first < 2) return;
    00235   _Distance __len = __last - __first;
    00236   _Distance __parent = (__len - 2)/2;
    00237
    00238   while (true) {
    00239     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
    00240                   __comp);
    00241     if (__parent == 0) return;
    00242     __parent--;
    00243   }
    00244 }
    00245
    00246 template <class _RandomAccessIterator, class _Compare>
    00247 inline void
    00248 make_heap(_RandomAccessIterator __first,
    00249           _RandomAccessIterator __last, _Compare __comp)
    00250 {
    00251   __make_heap(__first, __last, __comp,
    00252               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
    00253 }
    00254
    00255 template <class _RandomAccessIterator>
    00256 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    00257 {
    00258   while (__last - __first > 1)
    00259     pop_heap(__first, __last--);
    00260 }
    00261
    00262 template <class _RandomAccessIterator, class _Compare>
    00263 void
    00264 sort_heap(_RandomAccessIterator __first,
    00265           _RandomAccessIterator __last, _Compare __comp)
    00266 {
    00267   while (__last - __first > 1)
    00268     pop_heap(__first, __last--, __comp);
    00269 }
    00270
    00271 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00272 #pragma reset woff 1209
    00273 #endif
    00274
    00275 __STL_END_NAMESPACE
    00276
    00277 #endif /* __SGI_STL_INTERNAL_HEAP_H */
    00278
    00279 // Local Variables:
    00280 // mode:C++
    00281 // End: