diff -r 2fe1408b6811 -r e1b950c65cb4 epoc32/include/stdapis/stlport/stl/_heap.c --- a/epoc32/include/stdapis/stlport/stl/_heap.c Tue Mar 16 16:12:26 2010 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,242 +0,0 @@ -/* - * - * - * Copyright (c) 1994 - * Hewlett-Packard Company - * - * Copyright (c) 1996,1997 - * Silicon Graphics Computer Systems, Inc. - * - * Copyright (c) 1997 - * Moscow Center for SPARC Technology - * - * Copyright (c) 1999 - * Boris Fomitchev - * - * This material is provided "as is", with absolutely no warranty expressed - * or implied. Any use is at your own risk. - * - * Permission to use or copy this software for any purpose is hereby granted - * without fee, provided the above notices are retained on all copies. - * Permission to modify the code and to distribute modified code is granted, - * provided the above notices are retained, and a notice that the code was - * modified is included with the above copyright notice. - * - */ -#ifndef _STLP_HEAP_C -#define _STLP_HEAP_C - -#ifndef _STLP_INTERNAL_HEAP_H -# include -#endif - -#ifndef _STLP_INTERNAL_ITERATOR_BASE_H -# include -#endif - -_STLP_BEGIN_NAMESPACE - -template -_STLP_INLINE_LOOP -void -__push_heap(_RandomAccessIterator __first, - _Distance __holeIndex, _Distance __topIndex, _Tp __val) -{ - _Distance __parent = (__holeIndex - 1) / 2; - while (__holeIndex > __topIndex && *(__first + __parent) < __val) { - *(__first + __holeIndex) = *(__first + __parent); - __holeIndex = __parent; - __parent = (__holeIndex - 1) / 2; - } - *(__first + __holeIndex) = __val; -} - -template -inline void -__push_heap_aux(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Distance*, _Tp*) -{ - __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), - _Tp(*(__last - 1))); -} - -template -void -push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - __push_heap_aux(__first, __last, - _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator)); -} - - -template -_STLP_INLINE_LOOP -void -__push_heap(_RandomAccessIterator __first, _Distance __holeIndex, - _Distance __topIndex, _Tp __val, _Compare __comp) -{ - _Distance __parent = (__holeIndex - 1) / 2; - while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) { - *(__first + __holeIndex) = *(__first + __parent); - __holeIndex = __parent; - __parent = (__holeIndex - 1) / 2; - } - *(__first + __holeIndex) = __val; -} - -template -inline void -__push_heap_aux(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Compare __comp, - _Distance*, _Tp*) -{ - __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), - _Tp(*(__last - 1)), __comp); -} - -template -void -push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Compare __comp) -{ - __push_heap_aux(__first, __last, __comp, - _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator)); -} - -template -void -__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, - _Distance __len, _Tp __val) { - _Distance __topIndex = __holeIndex; - _Distance __secondChild = 2 * __holeIndex + 2; - while (__secondChild < __len) { - if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) - __secondChild--; - *(__first + __holeIndex) = *(__first + __secondChild); - __holeIndex = __secondChild; - __secondChild = 2 * (__secondChild + 1); - } - if (__secondChild == __len) { - *(__first + __holeIndex) = *(__first + (__secondChild - 1)); - __holeIndex = __secondChild - 1; - } - __push_heap(__first, __holeIndex, __topIndex, __val); -} - - -template -inline void -__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) { - __pop_heap(__first, __last - 1, __last - 1, - _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator)); -} - -template -void pop_heap(_RandomAccessIterator __first, - _RandomAccessIterator __last) { - __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator)); -} - -template -void -__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, - _Distance __len, _Tp __val, _Compare __comp) -{ - _Distance __topIndex = __holeIndex; - _Distance __secondChild = 2 * __holeIndex + 2; - while (__secondChild < __len) { - if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) - __secondChild--; - *(__first + __holeIndex) = *(__first + __secondChild); - __holeIndex = __secondChild; - __secondChild = 2 * (__secondChild + 1); - } - if (__secondChild == __len) { - *(__first + __holeIndex) = *(__first + (__secondChild - 1)); - __holeIndex = __secondChild - 1; - } - __push_heap(__first, __holeIndex, __topIndex, __val, __comp); -} - - -template -inline void -__pop_heap_aux(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Tp*, _Compare __comp) -{ - __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp, - _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator)); -} - - -template -void -pop_heap(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Compare __comp) -{ - __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp); -} - -template -_STLP_INLINE_LOOP -void -__make_heap(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Tp*, _Distance*) -{ - if (__last - __first < 2) return; - _Distance __len = __last - __first; - _Distance __parent = (__len - 2)/2; - - while (true) { - __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent))); - if (__parent == 0) return; - __parent--; - } -} - -template -void -make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - __make_heap(__first, __last, - _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator)); -} - -template -_STLP_INLINE_LOOP -void -__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Compare __comp, _Tp*, _Distance*) -{ - if (__last - __first < 2) return; - _Distance __len = __last - __first; - _Distance __parent = (__len - 2)/2; - - while (true) { - __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)), - __comp); - if (__parent == 0) return; - __parent--; - } -} - -template -void -make_heap(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Compare __comp) -{ - __make_heap(__first, __last, __comp, - _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator)); -} - -_STLP_END_NAMESPACE - -#endif /* _STLP_HEAP_C */ - -// Local Variables: -// mode:C++ -// End: