stl_heap.h

来自「symbian上STL模板库的实现」· C头文件 代码 · 共 484 行 · 第 1/2 页

                    __value);
        }

    /**
     *  @brief  Pop an element off a heap.
     *  @param  first  Start of heap.
     *  @param  last   End of heap.
     *  @ingroup heap
     *
     *  This operation pops the top of the heap.  The elements first and last-1
     *  are swapped and [first,last-1) is made into a heap.
     */
    template<typename _RandomAccessIterator>
        inline void
        pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        {
            typedef typename iterator_traits<_RandomAccessIterator>::value_type
                _ValueType;

            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                    _RandomAccessIterator>)
                __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
#endif
                __glibcxx_requires_valid_range(__first, __last);
            __glibcxx_requires_heap(__first, __last);

            std::__pop_heap(__first, __last - 1, __last - 1,
                    _ValueType(*(__last - 1)));
        }

    template<typename _RandomAccessIterator, typename _Distance,
        typename _Tp, typename _Compare>
            void
            __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
                    _Distance __len, _Tp __value, _Compare __comp)
            {
                const _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;
                }
                std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
            }

    template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
        inline void
        __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
                _RandomAccessIterator __result, _Tp __value, _Compare __comp)
        {
            typedef typename iterator_traits<_RandomAccessIterator>::difference_type
                _Distance;
            *__result = *__first;
            std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
                    __value, __comp);
        }

    /**
     *  @brief  Pop an element off a heap using comparison functor.
     *  @param  first  Start of heap.
     *  @param  last   End of heap.
     *  @param  comp   Comparison functor to use.
     *  @ingroup heap
     *
     *  This operation pops the top of the heap.  The elements first and last-1
     *  are swapped and [first,last-1) is made into a heap.  Comparisons are
     *  made using comp.
     */
    template<typename _RandomAccessIterator, typename _Compare>
        inline void
        pop_heap(_RandomAccessIterator __first,
                _RandomAccessIterator __last, _Compare __comp)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                    _RandomAccessIterator>)
#endif
                __glibcxx_requires_valid_range(__first, __last);
            __glibcxx_requires_heap_pred(__first, __last, __comp);

            typedef typename iterator_traits<_RandomAccessIterator>::value_type
                _ValueType;
            std::__pop_heap(__first, __last - 1, __last - 1,
                    _ValueType(*(__last - 1)), __comp);
        }

    /**
     *  @brief  Construct a heap over a range.
     *  @param  first  Start of heap.
     *  @param  last   End of heap.
     *  @ingroup heap
     *
     *  This operation makes the elements in [first,last) into a heap.
     */
    template<typename _RandomAccessIterator>
        void
        make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        {
            typedef typename iterator_traits<_RandomAccessIterator>::value_type
                _ValueType;
            typedef typename iterator_traits<_RandomAccessIterator>::difference_type
                _DistanceType;

            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                    _RandomAccessIterator>)
                __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            if (__last - __first < 2)
                return;

            const _DistanceType __len = __last - __first;
            _DistanceType __parent = (__len - 2) / 2;
            while (true)
            {
                std::__adjust_heap(__first, __parent, __len,
                        _ValueType(*(__first + __parent)));
                if (__parent == 0)
                    return;
                __parent--;
            }
        }

    /**
     *  @brief  Construct a heap over a range using comparison functor.
     *  @param  first  Start of heap.
     *  @param  last   End of heap.
     *  @param  comp   Comparison functor to use.
     *  @ingroup heap
     *
     *  This operation makes the elements in [first,last) into a heap.
     *  Comparisons are made using comp.
     */
    template<typename _RandomAccessIterator, typename _Compare>
        inline void
        make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
                _Compare __comp)
        {
            typedef typename iterator_traits<_RandomAccessIterator>::value_type
                _ValueType;
            typedef typename iterator_traits<_RandomAccessIterator>::difference_type
                _DistanceType;

            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                    _RandomAccessIterator>)
#endif
                __glibcxx_requires_valid_range(__first, __last);

            if (__last - __first < 2)
                return;

            const _DistanceType __len = __last - __first;
            _DistanceType __parent = (__len - 2) / 2;
            while (true)
            {
                std::__adjust_heap(__first, __parent, __len,
                        _ValueType(*(__first + __parent)), __comp);
                if (__parent == 0)
                    return;
                __parent--;
            }
        }

    /**
     *  @brief  Sort a heap.
     *  @param  first  Start of heap.
     *  @param  last   End of heap.
     *  @ingroup heap
     *
     *  This operation sorts the valid heap in the range [first,last).
     */
    template<typename _RandomAccessIterator>
        void
        sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                    _RandomAccessIterator>)
                __glibcxx_function_requires(_LessThanComparableConcept<
                        typename iterator_traits<_RandomAccessIterator>::value_type>)
#endif
                __glibcxx_requires_valid_range(__first, __last);
            //      __glibcxx_requires_heap(__first, __last);

            while (__last - __first > 1)
                std::pop_heap(__first, __last--);
        }

    /**
     *  @brief  Sort a heap using comparison functor.
     *  @param  first  Start of heap.
     *  @param  last   End of heap.
     *  @param  comp   Comparison functor to use.
     *  @ingroup heap
     *
     *  This operation sorts the valid heap in the range [first,last).
     *  Comparisons are made using comp.
     */
    template<typename _RandomAccessIterator, typename _Compare>
        void
        sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
                _Compare __comp)
        {
            // concept requirements
#ifndef NO__GLIBCXX_FUNCTION_REQUIRES
            __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                    _RandomAccessIterator>)
#endif
                __glibcxx_requires_valid_range(__first, __last);
            __glibcxx_requires_heap_pred(__first, __last, __comp);

            while (__last - __first > 1)
                std::pop_heap(__first, __last--, __comp);
        }

} // namespace std

#endif /* _STL_HEAP_H */

// Local Variables:
// mode:C++
// End: