algorithm.cc

realview22.rar

    }
    __merge_adaptive (__first, __middle, __last,
                      _Distance (__middle - __first),
                     _Distance (__last - __middle), __buf, __buf_size,
                      (_TypeT*)0, __comp);
}


template <class _RandomAccessIter, class _TypeT, class _Compare>
void __partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle,
                     _RandomAccessIter __last, _TypeT*, _Compare __comp)
{
    _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);

    _STD::make_heap (__first, __middle, __comp);
    for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
        if (__comp (*__i, *__first))
            __pop_heap (__first, __middle, __i, *__i, __comp,
                        _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter));
    _STD::sort_heap (__first, __middle, __comp);
}


template <class _InputIter, class _RandomAccessIter, class _Compare,
          class _Distance, class _TypeT>
_RandomAccessIter __partial_sort_copy (_InputIter __first,
                                       _InputIter __last,
                                       _RandomAccessIter __first2,
                                       _RandomAccessIter __last2,
                                       _Compare __comp,
                                       _Distance*, _TypeT*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    if (__first2 == __last2) return __last2;
    _RandomAccessIter __res = __first2;
    for (; __first != __last && __res != __last2;
         ++__first, ++__res)
        *__res = *__first;
    _STD::make_heap (__first2, __res, __comp);
    for (; __first != __last; ++__first)
    {
        if (__comp (*__first, *__first2))
            __adjust_heap (__first2, _Distance (), _Distance (__res - __first2),
                           *__first, __comp);
    }
    _STD::sort_heap (__first2, __res, __comp);
    return __res;
}


// David R. Musser's Introspective Sorting algorithm
// O(N * log (N)) worst case complexity
template <class _RandomAccessIter, class _Distance, class _Compare>
void __introsort_loop (_RandomAccessIter __first, _RandomAccessIter __last,
                       _Distance __max_depth, _Compare __comp)
{
    for (; __last - __first > __stl_threshold; __max_depth /= 2) {
        if (0 == __max_depth) {
            __partial_sort (__first, __last, __last,
                            _RWSTD_VALUE_TYPE (_RandomAccessIter), __comp);
            break;
        }

        _RandomAccessIter __cut =
            __unguarded_partition (__first, __last,
                                   __median (*__first,
                                             *(__first + (__last - __first) /2),
                                             *(__last - 1), __comp), __comp);

        // limit the depth of the recursion tree to log2 (last - first)
        // where first and last are the initial values passed in from sort()
        __introsort_loop (__cut, __last, __max_depth, __comp);
        __last = __cut;
    }
}


template <class _RandomAccessIter, class _TypeT, class _Compare>
void __nth_element (_RandomAccessIter __first, _RandomAccessIter __nth,
                    _RandomAccessIter __last, _TypeT*, _Compare __comp)
{
    _RWSTD_ASSERT_IN_RANGE (__nth, __first, __last);

    while (__last - __first > 3)
    {
        _RandomAccessIter __cut =
            __unguarded_partition (__first, __last,
                                   _TypeT (__median (*__first,
                                                     * (__first +
                                                        (__last - __first)/2),
                                                     * (__last - 1),
                                                     __comp)),
             __comp);
        if (__cut <= __nth)
            __first = __cut;
        else
            __last = __cut;
    }
    __insertion_sort (__first, __last, __comp);
}

//
// Binary search.
//

template <class _FwdIter, class _TypeT, class _Compare, class _Distance>
_FwdIter __lower_bound (_FwdIter __first, _FwdIter __last,
                        const _TypeT& __val, _Compare __comp,
                        _Distance*, forward_iterator_tag)
{
    _RWSTD_ASSERT_RANGE (__first, __last);
    
    _Distance __dist = _DISTANCE (__first, __last, _Distance);
    _Distance __half;
    _FwdIter __middle;

    while (__dist > 0)
    {
        __half = __dist / 2;
        __middle = __first;
        _STD::advance (__middle, __half);
        if (__comp (*__middle, __val))
        {
            __first = __middle;
            ++__first;
            __dist = __dist - __half - 1;
        }
        else
            __dist = __half;
    }
    return __first;
}


template <class _RandomAccessIter, class _TypeT, class _Compare,
    class _Distance>
_RandomAccessIter __lower_bound (_RandomAccessIter __first,
                                 _RandomAccessIter __last,
                                 const _TypeT& __val,
                                 _Compare __comp,
                                 _Distance*,
                                 random_access_iterator_tag)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = __last - __first;
    _Distance __half;
    _RandomAccessIter __middle;

    while (__dist > 0)
    {
        __half = __dist / 2;
        __middle = __first + __half;
        if (__comp (*__middle, __val))
        {
            __first = __middle + 1;
            __dist = __dist - __half - 1;
        }
        else
            __dist = __half;
    }
    return __first;
}


template <class _FwdIter, class _TypeT, class _Compare, class _Distance>
_FwdIter __upper_bound (_FwdIter __first, _FwdIter __last,
                        const _TypeT& __val, _Compare __comp,
                        _Distance*, forward_iterator_tag)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = _DISTANCE (__first, __last, _Distance);
    _Distance __half;
    _FwdIter __middle;

    while (__dist > 0)
    {
        __half = __dist / 2;
        __middle = __first;
        _STD::advance (__middle, __half);
        if (__comp (__val, *__middle))
            __dist = __half;
        else {
            __first = __middle;
            ++__first;
            __dist = __dist - __half - 1;
        }
    }
    return __first;
}

template <class _RandomAccessIter, class _TypeT, class _Compare,
    class _Distance>
_RandomAccessIter __upper_bound (_RandomAccessIter __first,
                                 _RandomAccessIter __last,
                                 const _TypeT& __val,
                                 _Compare __comp, _Distance*,
                                 random_access_iterator_tag)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = __last - __first;
    _Distance __half;
    _RandomAccessIter __middle;

    while (__dist > 0)
    {
        __half = __dist / 2;
        __middle = __first + __half;
        if (__comp (__val, *__middle))
            __dist = __half;
        else {
            __first = __middle + 1;
            __dist = __dist - __half - 1;
        }
    }
    return __first;
}


template <class _FwdIter, class _TypeT, class _Compare, class _Distance>
pair<_FwdIter, _FwdIter>
__equal_range (_FwdIter __first, _FwdIter __last, const _TypeT& __val,
               _Compare __comp, _Distance*, forward_iterator_tag)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = _DISTANCE (__first, __last, _Distance);
    _Distance __half;
    _FwdIter __middle, __left, __right;

    while (__dist > 0)
    {
        __half = __dist / 2;
        __middle = __first;
        _STD::advance (__middle, __half);
        if (__comp (*__middle, __val))
        {
            __first = __middle;
            ++__first;
            __dist = __dist - __half - 1;
        }
        else if (__comp (__val, *__middle))
            __dist = __half;
        else
        {
            __left = _STD::lower_bound (__first, __middle, __val, __comp);
            _STD::advance (__first, __dist);
            __right = _STD::upper_bound (++__middle, __first, __val, __comp);
            pair<_FwdIter, _FwdIter> __tmp (__left, __right);
            return __tmp;
        }
    }
    pair<_FwdIter, _FwdIter> __tmp (__first, __first);
    return __tmp;
}

template <class _RandomAccessIter, class _TypeT, class _Compare,
    class _Distance>
pair<_RandomAccessIter, _RandomAccessIter>
__equal_range (_RandomAccessIter __first, _RandomAccessIter __last,
               const _TypeT& __val, _Compare __comp, _Distance*,
               random_access_iterator_tag)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = __last - __first;
    _Distance __half;
    _RandomAccessIter __middle, __left, __right;

    while (__dist > 0)
    {
        __half = __dist / 2;
        __middle = __first + __half;
        if (__comp (*__middle, __val))
        {
            __first = __middle + 1;
            __dist = __dist - __half - 1;
        }
        else if (__comp (__val, *__middle))
            __dist = __half;
        else
        {
            __left  = _STD::lower_bound (__first, __middle, __val, __comp);
            __right = _STD::upper_bound (++__middle, __first + __dist,
                                         __val, __comp);
            pair<_RandomAccessIter, _RandomAccessIter> __tmp(__left, __right);
            return __tmp;
        }
    }
    pair<_RandomAccessIter, _RandomAccessIter> __tmp (__first, __first);
    return __tmp;
}

//
// Merge
//

template <class _InputIter1, class _InputIter2, class _OutputIter,
    class _Compare>
_OutputIter merge (_InputIter1 __first1, _InputIter1 __last1,
                   _InputIter2 __first2, _InputIter2 __last2,
                   _OutputIter __res, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    for (; __first1 != __last1 && __first2 != __last2; ++__res)
    {
        if (__comp (*__first2, *__first1)) {
            *__res = *__first2;
            ++__first2;
        }
        else {
            *__res = *__first1;
            ++__first1;
        }
    }
    return _STD::copy (__first2, __last2, _STD::copy(__first1, __last1, __res));
}


template <class _BidirIter, class _Distance, class _Compare>
void __merge_without_buffer (_BidirIter __first,
                             _BidirIter __middle,
                             _BidirIter __last,
                             _Distance __dist1, _Distance __dist2,
                             _Compare __comp)
{
    _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);

    if (__dist1 == 0 || __dist2 == 0) return;
    if (__dist1 + __dist2 == 2)
    {
        if (__comp (*__middle, *__first))
            _STD::iter_swap (__first, __middle);
        return;
    }
    _BidirIter __first_cut = __first;
    _BidirIter __second_cut = __middle;
    _Distance __dist11;
    _Distance __dist22;

    if (__dist1 > __dist2) {
        __dist11 = __dist1 / 2;
        _STD::advance (__first_cut, __dist11);
        __second_cut = _STD::lower_bound (__middle, __last,
                                          *__first_cut, __comp);
        __dist22 = _DISTANCE (__middle, __second_cut, _Distance);
    }
    else {
        __dist22 = __dist2 / 2;
        _STD::advance (__second_cut, __dist22);
        __first_cut = _STD::upper_bound (__first, __middle,
                                            *__second_cut, __comp);
        __dist11 = _DISTANCE (__first, __first_cut, _Distance);
    }
    _STD::rotate (__first_cut, __middle, __second_cut);

    _BidirIter __middle2 = __first_cut;

    _STD::advance (__middle2, __dist22);

    __merge_without_buffer (__first, __first_cut, __middle2,
                            __dist11, __dist22, __comp);
    __merge_without_buffer (__middle2, __second_cut, __last,
                            __dist1 - __dist11, __dist2 - __dist22, __comp);
}

template <class _BidirIter1, class _BidirIter2, class _Distance>
_BidirIter1 __rotate_adaptive (_BidirIter1 __first,
                               _BidirIter1 __middle,
                               _BidirIter1 __last,
                               _Distance __dist1, _Distance __dist2,
                               _BidirIter2 __buf,
                               _Distance __buf_size)
{
    _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);

    _BidirIter2 __buf_end;
    if (__dist1 > __dist2 && __dist2 <= __buf_size)
    {
        __buf_end = _STD::copy (__middle, __last, __buf);
        _STD::copy_backward (__first, __middle, __last);
        return _STD::copy (__buf, __buf_end, __first);
    }
    else if (__dist1 <= __buf_size)
    {
        __buf_end = _STD::copy (__first, __middle, __buf);
        _STD::copy (__middle, __last, __first);
        return _STD::copy_backward (__buf, __buf_end, __last);
    }
    else
    {
        _STD::rotate (__first, __middle, __last);
        _STD::advance (__first, __dist2);
        return __first;
    }
}

template <class _BidirIter1, class _BidirIter2,
    class _BidirIter3>
_BidirIter3 __merge_backward (_BidirIter1 __first1,
                              _BidirIter1 __last1,
                              _BidirIter2 __first2,
                              _BidirIter2 __last2,
                              _BidirIter3 __res)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    if (__first1 == __last1)
        return _STD::copy_backward (__first2, __last2, __res);

    if (__first2 == __last2)
        return _STD::copy_backward (__first1, __last1, __res);

    --__last1;
    --__last2;
    while (true)
    {
        if (*__last2 < *__last1)
        {
            *--__res = *__last1;
            if (__first1 == __last1)
                return _STD::copy_backward (__first2, ++__last2, __res);
            --__last1;
        }
        else
        {
            *--__res = *__last2;
            if (__first2 == __last2)
                return _STD::copy_backward (__first1, ++__last1, __res);
            --__last2;
        }
    }
}