algorithm

realview22.rar

inline void
__stable_sort (_RandomAccessIter __first, _RandomAccessIter __last,
               _TypeT*, _Distance*, _Compare __comp)
{
    // call an extension of get_temporary_buffer<>() in case partial class
    // specialization (and iterator_traits<>) isn't supported by compiler
    pair<_TypeT*, _Distance> __p =
        _STD::get_temporary_buffer (_Distance (__last - __first), (_TypeT*)0);

    if (__p.first == 0)
        __inplace_stable_sort (__first, __last, __comp);
    else {
        _Distance __len = min (_Distance (__p.second),
                               _Distance (__last - __first));
        _STD::copy (__first, __first + __len,
                       raw_storage_iterator<_TypeT*, _TypeT>(__p.first));

        __stable_sort_adaptive (__first, __last, __p.first, __p.second,
                                (_TypeT*)0, __comp);

        _RW::__rw_destroy (__p.first, __p.first + __len);

        _STD::return_temporary_buffer (__p.first);
    }
}


// 25.3.1.2
template <class _RandomAccessIter, class _Compare>
inline void stable_sort (_RandomAccessIter __first, _RandomAccessIter __last,
                         _Compare __comp)
{
    if (!(__first == __last))
        __stable_sort (__first, __last,
                       _RWSTD_VALUE_TYPE (_RandomAccessIter),
                       _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter), __comp);
}


template <class _RandomAccessIter>
inline void stable_sort (_RandomAccessIter __first, _RandomAccessIter __last)
{
    _STD::stable_sort (__first, __last, _RWSTD_LESS (_RandomAccessIter));
}


// helper to work around the lack of iterator_traits
template <class _RandomAccessIter, class _TypeT, class _Compare>
void __partial_sort (_RandomAccessIter, _RandomAccessIter,
                     _RandomAccessIter, _TypeT*, _Compare);

// 25.3.1.3
template <class _RandomAccessIter, class _Compare>
inline void partial_sort (_RandomAccessIter __first,
                          _RandomAccessIter __middle,
                          _RandomAccessIter __last, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);
    _RWSTD_ASSERT_RANGE (__first, __middle);

    if (!(__first == __middle))
        __partial_sort (__first, __middle, __last,
                        _RWSTD_VALUE_TYPE(_RandomAccessIter),
                        __comp);
}

template <class _RandomAccessIter>
inline void
partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle,
              _RandomAccessIter __last)
{
    _STD::partial_sort (__first, __middle, __last,
                        _RWSTD_LESS (_RandomAccessIter));
}


// helper to work around the lack of iterator_traits
template <class _InputIter, class _RandomAccessIter, class _Compare,
          class _Distance, class _TypeT>
_RandomAccessIter
__partial_sort_copy (_InputIter, _InputIter,
                     _RandomAccessIter, _RandomAccessIter,
                     _Compare, _Distance*, _TypeT*);


// 25.3.1.4
template <class _InputIter, class _RandomAccessIter, class _Compare>
inline _RandomAccessIter
partial_sort_copy (_InputIter __first, _InputIter __last,
                   _RandomAccessIter __res_first,
                   _RandomAccessIter __res_last, _Compare __comp)
{
    return __first == __last ? __res_first :
        __partial_sort_copy (__first, __last, __res_first, __res_last, __comp,
                             _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter),
                             _RWSTD_VALUE_TYPE (_RandomAccessIter));
}


template <class _InputIter, class _RandomAccessIter>
inline _RandomAccessIter
partial_sort_copy (_InputIter __first1, _InputIter __last1,
                   _RandomAccessIter __first2, _RandomAccessIter __last2)
{
    return _STD::partial_sort_copy (__first1, __last1, __first2, __last2,
                                    _RWSTD_LESS (_InputIter));
}


template <class _RandomAccessIter, class _TypeT, class _Compare>
void __nth_element (_RandomAccessIter, _RandomAccessIter,
                    _RandomAccessIter, _TypeT*, _Compare);

// 25.3.2 - Nth element [lib.alg.nth.element]

template <class _RandomAccessIter, class _Compare>
inline void nth_element (_RandomAccessIter __first, _RandomAccessIter __nth,
                         _RandomAccessIter __last, _Compare __comp)
{
    if (!(__first == __last))
        __nth_element (__first, __nth, __last,
                       _RWSTD_VALUE_TYPE (_RandomAccessIter), __comp);
}

template <class _RandomAccessIter>
inline void nth_element (_RandomAccessIter __first, _RandomAccessIter __nth,
                         _RandomAccessIter __last)
{
    _STD::nth_element (__first, __nth, __last, _RWSTD_LESS (_RandomAccessIter));
}


// 25.3.3 - Binary search [lib.alg.binary.search]

template <class _FwdIter, class _TypeT, class _Compare, class _Distance>
_FwdIter __lower_bound (_FwdIter, _FwdIter, const _TypeT&, _Compare,
                        _Distance*, forward_iterator_tag);


template <class _FwdIter, class _TypeT, class _Compare, class _Distance>
inline _FwdIter
__lower_bound (_FwdIter __first, _FwdIter __last,
               const _TypeT& __value, _Compare __comp, _Distance*,
               bidirectional_iterator_tag)
{
    return __lower_bound (__first, __last, __value, __comp,
                          (_Distance*)0, forward_iterator_tag ());
}

template <class _RandomAccessIter, class _TypeT, class _Compare,
          class _Distance>
_RandomAccessIter __lower_bound (_RandomAccessIter, _RandomAccessIter,
                                 const _TypeT&, _Compare, _Distance*,
                                 random_access_iterator_tag);

// 25.3.3.1
template <class _FwdIter, class _TypeT, class _Compare>
inline _FwdIter lower_bound (_FwdIter __first,_FwdIter __last,
                             const _TypeT& __value, _Compare __comp)
{
    return __lower_bound (__first, __last, __value, __comp,
                          _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                          _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first));
}


template <class _FwdIter, class _TypeT>
inline _FwdIter
lower_bound (_FwdIter __first, _FwdIter __last, const _TypeT& __value)
{
    return _STD::lower_bound (__first, __last, __value,
                              _RWSTD_LESS (_FwdIter));
}


template <class _FwdIter, class _TypeT, class _Compare, class _Distance>
_FwdIter __upper_bound (_FwdIter, _FwdIter, const _TypeT&, _Compare,
                        _Distance*, forward_iterator_tag);


template <class _FwdIter, class _TypeT, class _Compare, class _Distance>
inline _FwdIter
__upper_bound (_FwdIter __first, _FwdIter __last, const _TypeT& __value,
               _Compare __comp, _Distance*, bidirectional_iterator_tag)
{
    return __upper_bound (__first, __last, __value, __comp,
                          (_Distance*)0, forward_iterator_tag ());
}


template <class _RandomAccessIter, class _TypeT, class _Compare,
          class _Distance>
_RandomAccessIter __upper_bound (_RandomAccessIter, _RandomAccessIter,
                                 const _TypeT&, _Compare, _Distance*,
                                 random_access_iterator_tag);

// 25.3.3.2
template <class _FwdIter, class _TypeT, class _Compare>
inline _FwdIter
upper_bound (_FwdIter __first,_FwdIter __last,
             const _TypeT& __value, _Compare __comp)
{
    return __upper_bound (__first, __last, __value, __comp,
                          _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                          _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first));
}


template <class _FwdIter, class _TypeT>
inline _FwdIter
upper_bound (_FwdIter __first, _FwdIter __last, const _TypeT& __value)
{
    return _STD::upper_bound (__first, __last, __value,
                              _RWSTD_LESS (_FwdIter));
}


template <class _FwdIter, class _TypeT, class _Compare, class _Distance>
pair<_FwdIter, _FwdIter>
__equal_range (_FwdIter, _FwdIter, const _TypeT&,
               _Compare, _Distance*, forward_iterator_tag);


template <class _FwdIter, class _TypeT, class _Compare, class _Distance>
inline pair<_FwdIter, _FwdIter>
__equal_range (_FwdIter __first, _FwdIter __last, const _TypeT& __value,
               _Compare __comp, _Distance*, bidirectional_iterator_tag)
{
    return __equal_range (__first, __last, __value, __comp,
                          (_Distance*)0, forward_iterator_tag());
}


template <class _RandomAccessIter, class _TypeT, class _Compare,
          class _Distance>
pair<_RandomAccessIter, _RandomAccessIter>
__equal_range (_RandomAccessIter, _RandomAccessIter,
               const _TypeT&, _Compare, _Distance*, random_access_iterator_tag);


// 25.3.3.3
template <class _FwdIter, class _TypeT, class _Compare>
inline pair<_FwdIter, _FwdIter>
equal_range (_FwdIter __first, _FwdIter __last,
             const _TypeT& __value, _Compare __comp)
{
    return __equal_range (__first, __last, __value, __comp,
                          _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                          _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first));
}

template <class _FwdIter, class _TypeT>
inline pair<_FwdIter, _FwdIter>
equal_range (_FwdIter __first, _FwdIter __last, const _TypeT& __value)
{
    return _STD::equal_range (__first, __last, __value,
                              _RWSTD_LESS (_FwdIter));
}


// 25.3.3.4
template <class _FwdIter, class _TypeT, class _Compare>
inline bool binary_search (_FwdIter __first, _FwdIter __last,
                           const _TypeT& __value, _Compare __comp)
{
    _FwdIter __i = _STD::lower_bound (__first, __last, __value, __comp);
    return __i != __last && !__comp(__value, *__i);
}


template <class _FwdIter, class _TypeT>
inline bool
binary_search (_FwdIter __first, _FwdIter __last, const _TypeT& __value)
{
    return _STD::binary_search (__first, __last, __value,
                                _RWSTD_LESS (_FwdIter));
}


// 25.3.4 - Merge [lib.alg.merge]

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

template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter merge (_InputIter1 __first1, _InputIter1 __last1,
                   _InputIter2 __first2, _InputIter2 __last2,
                   _OutputIter __res)
{
    return _STD::merge (__first1, __last1, __first2, __last2, __res,
                        _RWSTD_LESS (_InputIter1));
}


template <class _BidirIter1, class _BidirIter2, class _BidirIter3,
          class _Compare>
_BidirIter3
__merge_backward (_BidirIter1, _BidirIter1, _BidirIter2, _BidirIter2,
                  _BidirIter3, _Compare);

template <class _BidirIter, class _Distance, class _Pointer, class _TypeT,
          class _Compare>
void __merge_adaptive (_BidirIter, _BidirIter, _BidirIter,
                       _Distance, _Distance, _Pointer, _Distance, _TypeT*,
                       _Compare);

template <class _BidirIter, class _Distance, class _TypeT, class _Compare>
void __inplace_merge (_BidirIter, _BidirIter, _BidirIter,
                      _Distance*, _TypeT*, _Compare);

// 25.3.4, p6
template <class _BidirIter, class _Compare>
inline void
inplace_merge (_BidirIter __first, _BidirIter __middle, _BidirIter __last,
               _Compare __comp)
{
    if (!(__first == __middle || __middle == __last))
        __inplace_merge (__first, __middle, __last,
                         _RWSTD_DIFFERENCE_TYPE (_BidirIter),
                         _RWSTD_VALUE_TYPE (_BidirIter), __comp);
}



// 25.3.4, p6
template <class _BidirIter>
inline void
inplace_merge (_BidirIter __first, _BidirIter __middle, _BidirIter __last)
{
    _STD::inplace_merge (__first, __middle, __last, _RWSTD_LESS (_BidirIter));
}

// 25.3.5 - Set operations on sorted structures

// 25.3.5.1
template <class _InputIter1, class _InputIter2, class _Compare>
bool includes (_InputIter1, _InputIter1, _InputIter2, _InputIter2, _Compare);

template <class _InputIter1, class _InputIter2>
inline bool includes (_InputIter1 __first1, _InputIter1 __last1,
                      _InputIter2 __first2, _InputIter2 __last2)
{
    return _STD::includes (__first1, __last1, __first2, __last2,
                           _RWSTD_LESS (_InputIter1));
}


// 25.3.5.2
template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter
set_union (_InputIter1, _InputIter1, _InputIter2, _InputIter2,
           _OutputIter, _Compare);

template <class _InputIter1, class _InputIter2, class _OutputIter>
inline _OutputIter
set_union (_InputIter1 __first1, _InputIter1 __last1,
           _InputIter2 __first2, _InputIter2 __last2, _OutputIter __res)
{
    return _STD::set_union (__first1, __last1, __first2, __last2, __res,
                            _RWSTD_LESS (_InputIter1));
}


// 25.3.5.3
template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter
set_intersection (_InputIter1, _InputIter1, _InputIter2, _InputIter2,