algorithm.cc

realview22.rar

    {
        _STD::iter_swap (__first, __i);
        ++__first; ++__i;
        if (__first == __middle)
        {
            if (__i == __last) return;
            __middle = __i;
        }
        else if (__i == __last)
            __i = __middle;
    }
}

template <class _EuclideanRingElement>
_EuclideanRingElement __gcd (_EuclideanRingElement __m,
                            _EuclideanRingElement __n)
{
    while (__n != 0)
    {
        _EuclideanRingElement __r = __m % __n;
        __m = __n;
        __n = __r;
    }
    return __m;
}

template <class _RandomAccessIter, class _Distance, class _TypeT>
void __rotate_cycle (_RandomAccessIter __first, _RandomAccessIter __last,
                     _RandomAccessIter __initial, _Distance __shift, _TypeT*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _TypeT __val = *__initial;
    _RandomAccessIter __ptr1 = __initial;
    _RandomAccessIter __ptr2 = __ptr1 + __shift;
    while (__ptr2 != __initial)
    {
        *__ptr1 = *__ptr2;
        __ptr1 = __ptr2;
        if (__last - __ptr2 > __shift)
            __ptr2 += __shift;
        else
            __ptr2 = __first + (__shift - (__last - __ptr2));
    }
    *__ptr1 = __val;
}

template <class _RandomAccessIter, class _Distance>
void __rotate (_RandomAccessIter __first, _RandomAccessIter __middle,
               _RandomAccessIter __last, _Distance*,
               random_access_iterator_tag)
{
    _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last);
  
    _Distance __n = __gcd (__last - __first, __middle - __first);
    while (__n--)
        __rotate_cycle (__first, __last, __first + __n, __middle - __first,
                       _RWSTD_VALUE_TYPE (_RandomAccessIter));
}

template <class _RandomAccessIter, class _Distance>
void __random_shuffle (_RandomAccessIter __first, _RandomAccessIter __last,
		       _Distance*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__first != __last)
	for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
	    _STD::iter_swap (__i,
                             __first + _RW::__rw_random (__i - __first + 1));
}

template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle (_RandomAccessIter __first, _RandomAccessIter __last,
                     _RandomNumberGenerator& __rand)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (! (__first == __last))
        for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
            _STD::iter_swap (__i, __first + __rand ((__i - __first) + 1));
}

template <class _BidirIter, class _Predicate>
_BidirIter partition (_BidirIter __first, _BidirIter __last,
                      _Predicate __pred)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    while (true)
    {
        while (true)
        {
            if (__first == __last)
                return __first;
            else if (__pred (*__first))
                ++__first;
            else
                break;
        }
        --__last;
        while (true)
        {
            if (__first == __last)
                return __first;
            else if (!__pred (*__last))
                --__last;
            else
                break;
        }
        _STD::iter_swap (__first, __last);
        ++__first;
    }
}

template <class _BidirIter, class _Predicate, class _Distance>
_BidirIter __inplace_stable_partition (_BidirIter __first, _BidirIter __last,
                                       _Predicate __pred, _Distance __dist)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__dist == 1) return __pred (*__first) ? __last : __first;
    _BidirIter __middle = __first;
    _STD::advance (__middle, __dist / 2);
    _BidirIter
        __first_cut = __inplace_stable_partition (__first, __middle, __pred,
                                                  __dist / 2);
    _BidirIter
        __second_cut = __inplace_stable_partition (__middle, __last, __pred,
                                                 __dist - __dist / 2);
    _STD::rotate (__first_cut, __middle, __second_cut);
    __dist = _DISTANCE (__middle, __second_cut, _Distance);
    _STD::advance (__first_cut, __dist);
    return __first_cut;
}

template <class _BidirIter, class _Pointer, class _Predicate,
    class _Distance, class _TypeT>
_BidirIter __stable_partition_adaptive (_BidirIter __first, _BidirIter __last,
                                        _Predicate __pred, _Distance __dist,
                                        _Pointer __buf,
                                        _Distance __buf_size,
                                        _Distance& __fill_pointer, _TypeT*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__dist <= __buf_size)
    {
        __dist = 0;
        _BidirIter __res1 = __first;
        _Pointer __res2 = __buf;
        for (; __first != __last && __dist < __fill_pointer; ++__first)
        {
            if (__pred (*__first)) {
                *__res1 = *__first;
                ++__res1;
            }
            else {
                *__res2 = *__first;
                ++__res2;
                ++__dist;
            }
        }
        if (__first != __last)
        {
            raw_storage_iterator<_Pointer, _TypeT> __res3 (__res2);
            for (; __first != __last; ++__first)
            {
                if (__pred (*__first)) {
                    *__res1 = *__first;
                    ++__res1;
                }
                else {
                    *__res3 = *__first;
                    ++__res3;
                    ++__dist;
                }
            }
            __fill_pointer = __dist;
        }
        _STD::copy (__buf, __buf + __dist, __res1);
        return __res1;
    }
    _BidirIter __middle = __first;
    _STD::advance (__middle, __dist / 2);

    // (__dist / 2)'s type may not be the same as that of __dist,
    // hence the seemingly redundant casts below
    _BidirIter __first_cut =
        __stable_partition_adaptive (__first, __middle, __pred,
                                     _Distance (__dist / 2),
                                     __buf, __buf_size,
                                     __fill_pointer, (_TypeT*)0);
    _BidirIter __second_cut =
        __stable_partition_adaptive (__middle, __last, __pred,
                                     _Distance (__dist - __dist / 2),
                                     __buf, __buf_size,
                                     __fill_pointer, (_TypeT*)0);

    _STD::rotate (__first_cut, __middle, __second_cut);
    __dist = _DISTANCE (__middle, __second_cut, _Distance);
    _STD::advance (__first_cut, __dist);
    return __first_cut;
}


template <class _BidirIter, class _Predicate, class _TypeT, class _Distance>
_BidirIter __stable_partition (_BidirIter __first, _BidirIter __last,
                               _Predicate __pred, _TypeT*, _Distance*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = _DISTANCE (__first, __last, _Distance);

    if (!__dist)
        return __last;
    
    // 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 (__dist, (_TypeT*)0);

    if (__pair.first == 0)
        return __inplace_stable_partition (__first, __last, __pred, __dist);

    _Distance __fill_pointer = 0;
    _BidirIter __res =
        __stable_partition_adaptive (__first, __last, __pred, __dist,
                                     __pair.first, __pair.second,
                                     __fill_pointer, (_TypeT*)0);

    _RW::__rw_destroy (__pair.first, __pair.first + __fill_pointer);
    _STD::return_temporary_buffer (__pair.first);

    return __res;
}

//
// Sorting and related operations.
//

template <class _RandomAccessIter, class _TypeT, class _Compare>
_RandomAccessIter __unguarded_partition (_RandomAccessIter __first,
                                         _RandomAccessIter __last,
                                         _TypeT __pivot, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    while (true) {
        while (__comp (*__first, __pivot))
            ++__first;

        while (__comp (__pivot, *--__last))
            ;

        if (!(__first < __last))
            return __first;

        _STD::iter_swap (__first, __last);
        ++__first;
    }
}


template <class _TypeT, class _Compare>
inline const _TypeT& __median (const _TypeT& __a, const _TypeT& __b,
                               const _TypeT& __c, _Compare __comp)
{
    return __comp (__a, __b)
        ? __comp (__b, __c) ? __b : __comp (__a, __c) ? __c : __a
        : __comp (__a, __c) ? __a : __comp (__b, __c) ? __c : __b;
}


const int __stl_threshold = 16;

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

    while (__last - __first > __stl_threshold)
    {
        _RandomAccessIter __cut =
            __unguarded_partition (__first, __last,
                                   _TypeT (__median (*__first,
                                                     * (__first +
                                                        (__last - __first)/2),
                                                     * (__last - 1),
                                                     __comp)),
             __comp);
        if (__cut - __first >= __last - __cut) {
            __quick_sort_loop_aux (__cut, __last,
                                   _RWSTD_VALUE_TYPE (_RandomAccessIter),
                                   __comp);
            __last = __cut;
        }
        else {
            __quick_sort_loop_aux (__first, __cut,
                                   _RWSTD_VALUE_TYPE (_RandomAccessIter),
                                   __comp);
            __first = __cut;
        }
    }
}


template <class _RandomAccessIter, class _Compare>
void __insertion_sort (_RandomAccessIter __first,
                       _RandomAccessIter __last, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (! (__first == __last))
        for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
            __linear_insert (__first, __i,
                             _RWSTD_VALUE_TYPE (_RandomAccessIter), __comp);
}

template <class _RandomAccessIter, class _TypeT, class _Compare>
void __unguarded_linear_insert (_RandomAccessIter __last, _TypeT __val,
                                _Compare __comp)
{
    for (_RandomAccessIter __next = __last; __comp (__val, *--__next); ) {
        *__last = *__next;
        __last = __next;
    }
    *__last = __val;
}


template <class _RandomAccessIter, class _Compare>
void __final_insertion_sort (_RandomAccessIter __first,
                             _RandomAccessIter __last, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__last - __first > __stl_threshold)
    {
        __insertion_sort (__first, __first + __stl_threshold, __comp);
        __unguarded_insertion_sort (__first + __stl_threshold, __last,
                                    __comp);
    }
    else
        __insertion_sort (__first, __last, __comp);
}


template <class _RandomAccessIter1, class _RandomAccessIter2,
    class _Distance, class _Compare>
void __merge_sort_loop (_RandomAccessIter1 __first,
                        _RandomAccessIter1 __last,
                        _RandomAccessIter2 __res, _Distance __step,
                        _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __two_step = 2 * __step;

    while (__last - __first >= __two_step) {
        __res = _STD::merge (__first, __first + __step,
                             __first + __step, __first + __two_step, __res,
                             __comp);
        __first += __two_step;
    }
    __step = _STD::min (_Distance (__last - __first), __step);

    _STD::merge (__first, __first + __step, __first + __step, __last,
                 __res, __comp);
}


template <class _RandomAccessIter, class _Distance, class _Compare>
void __chunk_insertion_sort (_RandomAccessIter __first,
                             _RandomAccessIter __last,
                             _Distance __chunk_size, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    while (__last - __first >= __chunk_size)
    {
        __insertion_sort (__first, __first + __chunk_size, __comp);
        __first += __chunk_size;
    }
    __insertion_sort (__first, __last, __comp);
}


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

    _Distance __dist = __last - __first;
    _Pointer __buf_last = __buf + __dist;

    const int __stl_chunk_size = 7;

    _Distance __step = __stl_chunk_size;
    __chunk_insertion_sort (__first, __last, __step, __comp);

    while (__step < __dist)
    {
        __merge_sort_loop (__first, __last, __buf, __step, __comp);
        __step *= 2;
        __merge_sort_loop (__buf, __buf_last, __first, __step,
                           __comp);
        __step *= 2;
    }
}


template <class _RandomAccessIter, class _Pointer, class _Distance,
    class _TypeT, class _Compare>
void __stable_sort_adaptive (_RandomAccessIter __first,
                             _RandomAccessIter __last, _Pointer __buf,
                             _Distance __buf_size, _TypeT*,
                             _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = (__last - __first + 1) / 2;
    _RandomAccessIter __middle = __first + __dist;
    if (__dist > __buf_size)
    {
        __stable_sort_adaptive (__first, __middle, __buf, __buf_size,
                                (_TypeT*)0, __comp);
        __stable_sort_adaptive (__middle, __last, __buf, __buf_size,
                                (_TypeT*)0, __comp);
    }
    else
    {
        __merge_sort_with_buffer (__first, __middle, __buf,
                                 (_Distance*)0, (_TypeT*)0, __comp);
        __merge_sort_with_buffer (__middle, __last, __buf,
                                 (_Distance*)0, (_TypeT*)0, __comp);