/home/ntakagi/work/STLport-5.1.5/stlport/stl/_heap.c Source File

00001 /*
00002  *
00003  *
00004  * Copyright (c) 1994
00005  * Hewlett-Packard Company
00006  *
00007  * Copyright (c) 1996,1997
00008  * Silicon Graphics Computer Systems, Inc.
00009  *
00010  * Copyright (c) 1997
00011  * Moscow Center for SPARC Technology
00012  *
00013  * Copyright (c) 1999
00014  * Boris Fomitchev
00015  *
00016  * This material is provided "as is", with absolutely no warranty expressed
00017  * or implied. Any use is at your own risk.
00018  *
00019  * Permission to use or copy this software for any purpose is hereby granted
00020  * without fee, provided the above notices are retained on all copies.
00021  * Permission to modify the code and to distribute modified code is granted,
00022  * provided the above notices are retained, and a notice that the code was
00023  * modified is included with the above copyright notice.
00024  *
00025  */
00026 #ifndef _STLP_HEAP_C
00027 #define _STLP_HEAP_C
00028 
00029 #ifndef _STLP_INTERNAL_HEAP_H
00030 # include <stl/_heap.h>
00031 #endif
00032 
00033 #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
00034 # include <stl/_iterator_base.h>
00035 #endif
00036 
00037 _STLP_BEGIN_NAMESPACE
00038 
00039 template <class _RandomAccessIterator, class _Distance, class _Tp>
00040 _STLP_INLINE_LOOP
00041 void
00042 __push_heap(_RandomAccessIterator __first,
00043             _Distance __holeIndex, _Distance __topIndex, _Tp __val)
00044 {
00045   _Distance __parent = (__holeIndex - 1) / 2;
00046   while (__holeIndex > __topIndex && *(__first + __parent) < __val) {
00047     *(__first + __holeIndex) = *(__first + __parent);
00048     __holeIndex = __parent;
00049     __parent = (__holeIndex - 1) / 2;
00050   }
00051   *(__first + __holeIndex) = __val;
00052 }
00053 
00054 template <class _RandomAccessIterator, class _Distance, class _Tp>
00055 inline void
00056 __push_heap_aux(_RandomAccessIterator __first,
00057                 _RandomAccessIterator __last, _Distance*, _Tp*)
00058 {
00059   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
00060               _Tp(*(__last - 1)));
00061 }
00062 
00063 template <class _RandomAccessIterator>
00064 void
00065 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00066 {
00067   __push_heap_aux(__first, __last,
00068                   _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
00069 }
00070 
00071 
00072 template <class _RandomAccessIterator, class _Distance, class _Tp,
00073           class _Compare>
00074 _STLP_INLINE_LOOP
00075 void
00076 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00077             _Distance __topIndex, _Tp __val, _Compare __comp)
00078 {
00079   _Distance __parent = (__holeIndex - 1) / 2;
00080   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) {
00081     _STLP_VERBOSE_ASSERT(!__comp(__val, *(__first + __parent)), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00082     *(__first + __holeIndex) = *(__first + __parent);
00083     __holeIndex = __parent;
00084     __parent = (__holeIndex - 1) / 2;
00085   }
00086   *(__first + __holeIndex) = __val;
00087 }
00088 
00089 template <class _RandomAccessIterator, class _Compare,
00090           class _Distance, class _Tp>
00091 inline void
00092 __push_heap_aux(_RandomAccessIterator __first,
00093                 _RandomAccessIterator __last, _Compare __comp,
00094                 _Distance*, _Tp*)
00095 {
00096   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
00097               _Tp(*(__last - 1)), __comp);
00098 }
00099 
00100 template <class _RandomAccessIterator, class _Compare>
00101 void
00102 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00103           _Compare __comp)
00104 {
00105   __push_heap_aux(__first, __last, __comp,
00106                   _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
00107 }
00108 
00109 template <class _RandomAccessIterator, class _Distance, class _Tp>
00110 void
00111 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00112               _Distance __len, _Tp __val) {
00113   _Distance __topIndex = __holeIndex;
00114   _Distance __secondChild = 2 * __holeIndex + 2;
00115   while (__secondChild < __len) {
00116     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
00117       __secondChild--;
00118     *(__first + __holeIndex) = *(__first + __secondChild);
00119     __holeIndex = __secondChild;
00120     __secondChild = 2 * (__secondChild + 1);
00121   }
00122   if (__secondChild == __len) {
00123     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00124     __holeIndex = __secondChild - 1;
00125   }
00126   __push_heap(__first, __holeIndex, __topIndex, __val);
00127 }
00128 
00129 
00130 template <class _RandomAccessIterator, class _Tp>
00131 inline void
00132 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) {
00133   __pop_heap(__first, __last - 1, __last - 1,
00134              _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
00135 }
00136 
00137 template <class _RandomAccessIterator>
00138 void pop_heap(_RandomAccessIterator __first,
00139         _RandomAccessIterator __last) {
00140   __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
00141 }
00142 
00143 template <class _RandomAccessIterator, class _Distance,
00144           class _Tp, class _Compare>
00145 void
00146 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00147               _Distance __len, _Tp __val, _Compare __comp)
00148 {
00149   _Distance __topIndex = __holeIndex;
00150   _Distance __secondChild = 2 * __holeIndex + 2;
00151   while (__secondChild < __len) {
00152     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) {
00153       _STLP_VERBOSE_ASSERT(!__comp(*(__first + (__secondChild - 1)), *(__first + __secondChild)),
00154                            _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00155       __secondChild--;
00156     }
00157     *(__first + __holeIndex) = *(__first + __secondChild);
00158     __holeIndex = __secondChild;
00159     __secondChild = 2 * (__secondChild + 1);
00160   }
00161   if (__secondChild == __len) {
00162     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00163     __holeIndex = __secondChild - 1;
00164   }
00165   __push_heap(__first, __holeIndex, __topIndex, __val, __comp);
00166 }
00167 
00168 
00169 template <class _RandomAccessIterator, class _Tp, class _Compare>
00170 inline void
00171 __pop_heap_aux(_RandomAccessIterator __first,
00172                _RandomAccessIterator __last, _Tp*, _Compare __comp)
00173 {
00174   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
00175              _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
00176 }
00177 
00178 
00179 template <class _RandomAccessIterator, class _Compare>
00180 void
00181 pop_heap(_RandomAccessIterator __first,
00182          _RandomAccessIterator __last, _Compare __comp)
00183 {
00184     __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
00185 }
00186 
00187 template <class _RandomAccessIterator, class _Tp, class _Distance>
00188 _STLP_INLINE_LOOP
00189 void
00190 __make_heap(_RandomAccessIterator __first,
00191             _RandomAccessIterator __last, _Tp*, _Distance*)
00192 {
00193   if (__last - __first < 2) return;
00194   _Distance __len = __last - __first;
00195   _Distance __parent = (__len - 2)/2;
00196 
00197   for (;;) {
00198     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
00199     if (__parent == 0) return;
00200     __parent--;
00201   }
00202 }
00203 
00204 template <class _RandomAccessIterator>
00205 void
00206 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00207 {
00208   __make_heap(__first, __last,
00209               _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
00210 }
00211 
00212 template <class _RandomAccessIterator, class _Compare,
00213           class _Tp, class _Distance>
00214 _STLP_INLINE_LOOP
00215 void
00216 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00217             _Compare __comp, _Tp*, _Distance*)
00218 {
00219   if (__last - __first < 2) return;
00220   _Distance __len = __last - __first;
00221   _Distance __parent = (__len - 2)/2;
00222 
00223   for (;;) {
00224     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
00225                   __comp);
00226     if (__parent == 0) return;
00227     __parent--;
00228   }
00229 }
00230 
00231 template <class _RandomAccessIterator, class _Compare>
00232 void
00233 make_heap(_RandomAccessIterator __first,
00234           _RandomAccessIterator __last, _Compare __comp)
00235 {
00236   __make_heap(__first, __last, __comp,
00237               _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
00238 }
00239 
00240 _STLP_END_NAMESPACE
00241 
00242 #endif /*  _STLP_HEAP_C */
00243 
00244 // Local Variables:
00245 // mode:C++
00246 // End: