algorithm.cc

realview22.rar

template <class _BidirIter1, class _BidirIter2,
    class _BidirIter3, class _Compare>
_BidirIter3 __merge_backward (_BidirIter1 __first1,
                              _BidirIter1 __last1,
                              _BidirIter2 __first2,
                              _BidirIter2 __last2,
                              _BidirIter3 __res,
                              _Compare __comp)
{
    _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 (__comp (*__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;
        }
    }
}


template <class _BidirIter, class _Distance, class _Pointer, class _TypeT,
          class _Compare>
void __merge_adaptive (_BidirIter __first, _BidirIter __middle,
                       _BidirIter __last,
                       _Distance __dist1, _Distance __dist2,
                       _Pointer __buf, _Distance __buf_size, _TypeT*,
                       _Compare __comp)
{
    _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);
    
    if (__dist1 <= __dist2 && __dist1 <= __buf_size)
    {
        _Pointer __buf_end = _STD::copy (__first, __middle, __buf);
        _STD::merge (__buf, __buf_end, __middle, __last, __first, __comp);
    }
    else if (__dist2 <= __buf_size)
    {
        _Pointer __buf_end = _STD::copy (__middle, __last, __buf);
        __merge_backward (__first, __middle, __buf, __buf_end, __last,
                          __comp);
    }
    else
    {
        _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);
        }
        _BidirIter __middle2 =
            __rotate_adaptive (__first_cut, __middle, __second_cut,
                               __dist1 - __dist11, __dist22,
                               __buf, __buf_size);
        __merge_adaptive (__first, __first_cut, __middle2,
                          __dist11, __dist22,
                          __buf,
                          __buf_size, (_TypeT*)0,
                          __comp);
        __merge_adaptive (__middle2, __second_cut, __last,
                          __dist1 - __dist11, __dist2 - __dist22,
                          __buf, __buf_size, (_TypeT*)0, __comp);
    }
}


template <class _BidirIter, class _Distance, class _TypeT, class _Compare>
void __inplace_merge (_BidirIter __first, _BidirIter __middle,
                      _BidirIter __last, _Distance*, _TypeT*, _Compare __comp)
{
    _Distance __dist1 = _DISTANCE (__first, __middle, _Distance);
    _Distance __dist2 = _DISTANCE (__middle, __last, _Distance);
 
    // call an extension of get_temporary_buffer<>() in case partial class
    // specialization (and iterator_traits<>) isn't supported by compiler
    pair<_TypeT*, _Distance> __pair =
        _STD::get_temporary_buffer (__dist1 + __dist2, (_TypeT*)0);

    if (__pair.first == 0) {
        __merge_without_buffer (__first, __middle, __last, __dist1, __dist2,
                                __comp);
    }
    else {
        _Distance __dist = _STD::min (__pair.second, __dist1 + __dist2);
        
        _STD::fill_n (raw_storage_iterator<_TypeT*, _TypeT> (__pair.first),
                      __dist, *__first);
        __merge_adaptive (__first, __middle, __last, __dist1, __dist2,
                          __pair.first, __pair.second,
                          (_TypeT*)0, __comp);
        _RW::__rw_destroy (__pair.first, __pair.first + __dist);
        _STD::return_temporary_buffer (__pair.first);
    }
}

//
// Set operations. Assume sorted sequences.
//


// 25.3.5.1 - returns true iff every (not necessarily distinct) element
// in [first2, last2) occurs (at least as many times) in [first1, last1)
template <class _InputIter1, class _InputIter2, class _Compare>
bool includes (_InputIter1 __first1, _InputIter1 __last1,
               _InputIter2 __first2, _InputIter2 __last2,
               _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    while (__first1 != __last1 && __first2 != __last2) {
        if (__comp (*__first2, *__first1))
            return false;

        if (!__comp (*__first1, *__first2))
            ++__first2;

        ++__first1;
    }
    return __first2 == __last2;
}


template <class _InputIter1, class _InputIter2, class _OutputIter,
    class _Compare>
_OutputIter set_union (_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 (*__first1, *__first2)) {
            *__res = *__first1;
            ++__first1;
        }
        else if (__comp (*__first2, *__first1)) {
            *__res = *__first2;
            ++__first2;
        }
        else {
            *__res = *__first1;
            ++__first1;
            ++__first2;
        }
    }
    return _STD::copy (__first2, __last2,
                       _STD::copy (__first1, __last1, __res));
}


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

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


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

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


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

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

//
// Heap operations.
//

template <class _RandomAccessIter, class _Distance, class _TypeT,
          class _Compare>
void __push_heap (_RandomAccessIter __first, _Distance __holeIndex,
                  _Distance __topIndex, _TypeT __val, _Compare __comp)
{
    for (_Distance __parent = (__holeIndex - 1) / 2; 
         __holeIndex > __topIndex && __comp (* (__first + __parent), __val);
         __parent = ((__holeIndex = __parent) - 1) / 2) {
        *(__first + __holeIndex) = *(__first + __parent);
    }
    *(__first + __holeIndex) = __val;
}


template <class _RandomAccessIter, class _Distance, class _TypeT,
    class _Compare>
void __adjust_heap (_RandomAccessIter __first, _Distance __holeIndex,
                    _Distance __dist, _TypeT __val, _Compare __comp)
{
    _Distance __topIndex = __holeIndex;
    _Distance __2ndChild;

    while ((__2ndChild = 2 * __holeIndex + 2) < __dist) {
        if (__comp (*(__first + __2ndChild), *(__first + (__2ndChild - 1))))
            __2ndChild--;
        *(__first + __holeIndex) = *(__first + __2ndChild);
        __holeIndex = __2ndChild;
    }
    if (__2ndChild == __dist) {
        *(__first + __holeIndex) = *(__first + (__2ndChild - 1));
        __holeIndex = __2ndChild - 1;
    }
    __push_heap (__first, __holeIndex, __topIndex, __val, __comp);
}


template <class _RandomAccessIter, class _Compare, class _TypeT,
    class _Distance>
void __make_heap (_RandomAccessIter __first, _RandomAccessIter __last,
                  _Compare __comp, _TypeT*, _Distance*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = __last - __first;
    _Distance __parent = (__dist - 2)/2;
    while (true)
    {
        __adjust_heap (__first, __parent, __dist, * (__first + __parent),
                       __comp);
        if (__parent == 0)
            return;
        __parent--;
    }
}


//
// Minimum and maximum.
//


template <class _FwdIter, class _Compare>
_FwdIter min_element (_FwdIter __first, _FwdIter __last, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__first == __last)
        return __first;

    _FwdIter __res = __first;
    while (++__first != __last)
        if (__comp (*__first, *__res))
            __res = __first;

    return __res;
}


template <class _FwdIter, class _Compare>
_FwdIter max_element (_FwdIter __first, _FwdIter __last, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__first == __last)
        return __first;

    _FwdIter __res = __first;
    while (++__first != __last)
        if (__comp (*__res, *__first))
            __res = __first;

    return __res;
}

//
// Permutations.
//

template <class _BidirIter, class _Compare>
bool next_permutation (_BidirIter __first, _BidirIter __last, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__first == __last) return false;
    _BidirIter __i = __first;
    ++__i;
    if (__i == __last) return false;
    __i = __last;
    --__i;

    for (; ; )
    {
        _BidirIter __ii = __i--;
        if (__comp (*__i, *__ii))
        {
            _BidirIter __j = __last;
            while (!__comp (*__i, *--__j))
                ;
            _STD::iter_swap (__i, __j);
            _STD::reverse (__ii, __last);
            return true;
        }
        if (__i == __first)
        {
            _STD::reverse (__first, __last);
            return false;
        }
    }
}


template <class _BidirIter, class _Compare>
bool prev_permutation (_BidirIter __first, _BidirIter __last, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__first == __last) return false;
    _BidirIter __i = __first;
    ++__i;
    if (__i == __last) return false;
    __i = __last;
    --__i;

    for (; ; )
    {
        _BidirIter __ii = __i--;
        if (__comp (*__ii, *__i))
        {
            _BidirIter __j = __last;
            while (!__comp (*--__j, *__i))
                ;
            _STD::iter_swap (__i, __j);
            _STD::reverse (__ii, __last);
            return true;
        }
        if (__i == __first)
        {
            _STD::reverse (__first, __last);
            return false;
        }
    }
}


_RWSTD_NAMESPACE_END   // std