123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246 |
- /*
- *
- *
- * 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 <stl/_heap.h>
- #endif
- #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
- # include <stl/_iterator_base.h>
- #endif
- _STLP_BEGIN_NAMESPACE
- template <class _RandomAccessIterator, class _Distance, class _Tp>
- _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 <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>
- void
- push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
- {
- __push_heap_aux(__first, __last,
- _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
- }
- template <class _RandomAccessIterator, class _Distance, class _Tp,
- class _Compare>
- _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)) {
- _STLP_VERBOSE_ASSERT(!__comp(__val, *(__first + __parent)), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
- *(__first + __holeIndex) = *(__first + __parent);
- __holeIndex = __parent;
- __parent = (__holeIndex - 1) / 2;
- }
- *(__first + __holeIndex) = __val;
- }
- 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>
- 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 <class _RandomAccessIterator, class _Distance, class _Tp>
- 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 <class _RandomAccessIterator, class _Tp>
- 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 <class _RandomAccessIterator>
- void pop_heap(_RandomAccessIterator __first,
- _RandomAccessIterator __last) {
- __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
- }
- template <class _RandomAccessIterator, class _Distance,
- class _Tp, class _Compare>
- 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)))) {
- _STLP_VERBOSE_ASSERT(!__comp(*(__first + (__secondChild - 1)), *(__first + __secondChild)),
- _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
- __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 <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,
- _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
- }
- template <class _RandomAccessIterator, class _Compare>
- void
- pop_heap(_RandomAccessIterator __first,
- _RandomAccessIterator __last, _Compare __comp)
- {
- __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
- }
- template <class _RandomAccessIterator, class _Tp, class _Distance>
- _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;
- for (;;) {
- __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
- if (__parent == 0) return;
- __parent--;
- }
- }
- template <class _RandomAccessIterator>
- void
- make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
- {
- __make_heap(__first, __last,
- _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
- }
- template <class _RandomAccessIterator, class _Compare,
- class _Tp, class _Distance>
- _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;
- for (;;) {
- __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
- __comp);
- if (__parent == 0) return;
- __parent--;
- }
- }
- template <class _RandomAccessIterator, class _Compare>
- 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:
|