diff options
Diffstat (limited to 'contrib/libstdc++/stl/stl_heap.h')
| -rw-r--r-- | contrib/libstdc++/stl/stl_heap.h | 281 |
1 files changed, 0 insertions, 281 deletions
diff --git a/contrib/libstdc++/stl/stl_heap.h b/contrib/libstdc++/stl/stl_heap.h deleted file mode 100644 index 62f142e..0000000 --- a/contrib/libstdc++/stl/stl_heap.h +++ /dev/null @@ -1,281 +0,0 @@ -/* - * - * Copyright (c) 1994 - * Hewlett-Packard Company - * - * Permission to use, copy, modify, distribute and sell this software - * and its documentation for any purpose is hereby granted without fee, - * provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear - * in supporting documentation. Hewlett-Packard Company makes no - * representations about the suitability of this software for any - * purpose. It is provided "as is" without express or implied warranty. - * - * Copyright (c) 1997 - * Silicon Graphics Computer Systems, Inc. - * - * Permission to use, copy, modify, distribute and sell this software - * and its documentation for any purpose is hereby granted without fee, - * provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear - * in supporting documentation. Silicon Graphics makes no - * representations about the suitability of this software for any - * purpose. It is provided "as is" without express or implied warranty. - */ - -/* NOTE: This is an internal header file, included by other STL headers. - * You should not attempt to use it directly. - */ - -#ifndef __SGI_STL_INTERNAL_HEAP_H -#define __SGI_STL_INTERNAL_HEAP_H - -__STL_BEGIN_NAMESPACE - -#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) -#pragma set woff 1209 -#endif - -// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap. - -template <class _RandomAccessIterator, class _Distance, class _Tp> -void -__push_heap(_RandomAccessIterator __first, - _Distance __holeIndex, _Distance __topIndex, _Tp __value) -{ - _Distance __parent = (__holeIndex - 1) / 2; - while (__holeIndex > __topIndex && *(__first + __parent) < __value) { - *(__first + __holeIndex) = *(__first + __parent); - __holeIndex = __parent; - __parent = (__holeIndex - 1) / 2; - } - *(__first + __holeIndex) = __value; -} - -template <class _RandomAccessIterator, class _Distance, class _Tp> -inline void -__push_heap_aux(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Distance*, _Tp*) -{ - __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), - _Tp(*(__last - 1))); -} - -template <class _RandomAccessIterator> -inline void -push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - __push_heap_aux(__first, __last, - __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); -} - -template <class _RandomAccessIterator, class _Distance, class _Tp, - class _Compare> -void -__push_heap(_RandomAccessIterator __first, _Distance __holeIndex, - _Distance __topIndex, _Tp __value, _Compare __comp) -{ - _Distance __parent = (__holeIndex - 1) / 2; - while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) { - *(__first + __holeIndex) = *(__first + __parent); - __holeIndex = __parent; - __parent = (__holeIndex - 1) / 2; - } - *(__first + __holeIndex) = __value; -} - -template <class _RandomAccessIterator, class _Compare, - class _Distance, class _Tp> -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 <class _RandomAccessIterator, class _Compare> -inline void -push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Compare __comp) -{ - __push_heap_aux(__first, __last, __comp, - __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); -} - -template <class _RandomAccessIterator, class _Distance, class _Tp> -void -__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, - _Distance __len, _Tp __value) -{ - _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, __value); -} - -template <class _RandomAccessIterator, class _Tp, class _Distance> -inline void -__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, - _RandomAccessIterator __result, _Tp __value, _Distance*) -{ - *__result = *__first; - __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value); -} - -template <class _RandomAccessIterator, class _Tp> -inline void -__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Tp*) -{ - __pop_heap(__first, __last - 1, __last - 1, - _Tp(*(__last - 1)), __DISTANCE_TYPE(__first)); -} - -template <class _RandomAccessIterator> -inline void pop_heap(_RandomAccessIterator __first, - _RandomAccessIterator __last) -{ - __pop_heap_aux(__first, __last, __VALUE_TYPE(__first)); -} - -template <class _RandomAccessIterator, class _Distance, - class _Tp, class _Compare> -void -__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, - _Distance __len, _Tp __value, _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, __value, __comp); -} - -template <class _RandomAccessIterator, class _Tp, class _Compare, - class _Distance> -inline void -__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, - _RandomAccessIterator __result, _Tp __value, _Compare __comp, - _Distance*) -{ - *__result = *__first; - __adjust_heap(__first, _Distance(0), _Distance(__last - __first), - __value, __comp); -} - -template <class _RandomAccessIterator, class _Tp, class _Compare> -inline void -__pop_heap_aux(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Tp*, _Compare __comp) -{ - __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp, - __DISTANCE_TYPE(__first)); -} - -template <class _RandomAccessIterator, class _Compare> -inline void -pop_heap(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Compare __comp) -{ - __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp); -} - -template <class _RandomAccessIterator, class _Tp, class _Distance> -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 <class _RandomAccessIterator> -inline void -make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - __make_heap(__first, __last, - __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); -} - -template <class _RandomAccessIterator, class _Compare, - class _Tp, class _Distance> -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 <class _RandomAccessIterator, class _Compare> -inline void -make_heap(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Compare __comp) -{ - __make_heap(__first, __last, __comp, - __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); -} - -template <class _RandomAccessIterator> -void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - while (__last - __first > 1) - pop_heap(__first, __last--); -} - -template <class _RandomAccessIterator, class _Compare> -void -sort_heap(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Compare __comp) -{ - while (__last - __first > 1) - pop_heap(__first, __last--, __comp); -} - -#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) -#pragma reset woff 1209 -#endif - -__STL_END_NAMESPACE - -#endif /* __SGI_STL_INTERNAL_HEAP_H */ - -// Local Variables: -// mode:C++ -// End: |
