algorith.mh

来自「开放源码的编译器open watcom 1.6.0版的源代码」· MH 代码 · 共 1,114 行 · 第 1/3 页

        swap( *first1, *first2 ); // iter_swap? See 25.2.2p3
        ++first1;
        ++first2;
    }
    return( first2 );
}

// iter_swap( ForwardIterator1, ForwardIterator2 )
// ***********************************************
template< class ForwardIterator1, class ForwardIterator2 >
inline void iter_swap( ForwardIterator1 x, ForwardIterator2 y )
{
    iterator_traits< ForwardIterator1 >::value_type tmp(*x);
    *x = *y;
    *y = tmp;
}

// transform( InputIterator, InputIterator, OutputIterator, UnaryOperation )
// *************************************************************************
template< class InputIterator, class OutputIterator, class UnaryOperation >
OutputIterator transform( InputIterator first,
                          InputIterator last,
                          OutputIterator result,
                          UnaryOperation op )
{
    while( first != last ) {
        *result = op( *first );
        ++first;
        ++result;
    }
    return( result );
}

// transform( Input1, Input1, Input2, Output, BinaryOperation )
// ************************************************************
template< class InputIterator1,
          class InputIterator2,
          class OutputIterator,
          class BinaryOperation >
OutputIterator transform( InputIterator1 first1,
                          InputIterator1 last1,
                          InputIterator2 first2,
                          OutputIterator result,
                          BinaryOperation bop )
{
    while( first1 != last1 ) {
        *result = bop( *first1, *first2 );
        ++first1;
        ++first2;
        ++result;
    }
    return( result );
}

// replace( ForwardIterator, ForwardIterator, const Type &, const Type & )
// ***********************************************************************
template< class ForwardIterator, class Type >
void replace( ForwardIterator first,
              ForwardIterator last,
              const Type &old_value,
              const Type &new_value )
{
    while( first != last ) {
        if( *first == old_value ) *first = new_value;
        ++first;
    }
}

// replace_if( ForwardIterator, ForwardIterator, Predicate, const Type & )
// ***********************************************************************
template< class ForwardIterator, class Predicate, class Type >
void replace_if( ForwardIterator first,
                 ForwardIterator last,
                 Predicate pred,
                 const Type &new_value )
{
    while( first != last ) {
        if ( pred( *first ) != false ) *first = new_value;
       ++first;
    }
}

// replace_copy( Input, Input, Output, const Type &, const Type & )
// ****************************************************************
template< class InputIterator, class OutputIterator, class Type >
OutputIterator replace_copy( InputIterator first,
                             InputIterator last,
                             OutputIterator result,
                             const Type &old_value,
                             const Type &new_value )
{
    while( first != last ) {
        *result = ( *first == old_value ) ? new_value : *first;
        ++first;
        ++result;
    }
    return( result );
}

// replace_copy_if( Input, Input, Output, Predicate, const Type & )
// ****************************************************************
template< class InputIterator,
          class OutputIterator,
          class Predicate,
          class Type >
OutputIterator replace_copy_if( InputIterator first,
                                InputIterator last,
                                OutputIterator result,
                                Predicate pred,
                                const Type &new_value )
{
    while( first != last ) {
        *result = ( pred( *first ) ) ? new_value : *first;
        ++first;
        ++result;
    }
    return( result );
}

// fill( ForwardIterator, ForwardIterator, const Type & )
// ******************************************************
template< class ForwardIterator, class Type >
void fill( ForwardIterator first, ForwardIterator last, const Type &value )
{
    while( first != last ) {
        *first = value;
        ++first;
    }
}

// fill_n( OutputIterator, Size, const Type & )
// ********************************************
template< class OutputIterator, class Size, class Type >
void fill_n( OutputIterator first, Size n, const Type &value )
{
    unsigned long long i = 0ULL, max(n);
    while( i < max ) {
        *first = value;
        ++first;
        ++i;
    }
}

// generate( ForwardIterator, ForwardIterator, Generator )
// *******************************************************
template< class ForwardIterator, class Generator >
void generate( ForwardIterator first, ForwardIterator last, Generator gen )
{
    while( first != last ) {
        *first = gen( );
        ++first;
    }
}

// generate_n( OutputIterator, Size, Generator )
// *********************************************
template< class OutputIterator, class Size, class Generator >
void generate_n( OutputIterator first, Size n, Generator gen )
{
    unsigned long long i = 0ULL, max(n);
    while( i < max ) {
        *first = gen( );
        ++first;
        ++i;
    }
}

// remove_copy( InpIterator, InpIterator, OutIterator, Type const & )
// ******************************************************************
template< class InputIterator, class OutputIterator, class Type >
OutputIterator remove_copy( InputIterator first,
                            InputIterator last,
                            OutputIterator out,
                            Type const & value)
{
    while( first != last){
        if( *first == value ) {
            ++first;
        } else {
            *out = *first;
            ++first;
            ++out;
      }
    }
    return( out );
}

// remove_copy_if( InpIterator, InpIterator, OutIterator, Predictate )
// *******************************************************************
template< class InputIterator, class OutputIterator, class Predictate >
OutputIterator remove_copy_if( InputIterator first,
                               InputIterator last,
                               OutputIterator out,
                               Predictate pred )
{
    while( first != last) {
        if( pred( *first ) != false ) {
            ++first;
        } else {
            *out = *first;
            ++first;
            ++out;
        }
    }
    return( out );
}

// remove( ForwardIterator, ForwardIterator, Type const & )
// ********************************************************
template< class ForwardIterator, class Type >
ForwardIterator remove( ForwardIterator first, 
                        ForwardIterator last,
                        Type const & value)
{
    ForwardIterator out = first;
    bool copy = false;
    while( first != last) {
        if( *first == value ) {
            ++first;
            copy = true;
        } else {
            if( copy ) {
                //avoid unecessary copies
                *out = *first;
            }
            ++first;
            ++out;
        }
    }
    return( out );
}

// remove_if( ForwardIterator, ForwardIterator, Predictate )
// *********************************************************
template< class ForwardIterator, class Predictate >
ForwardIterator remove_if( ForwardIterator first,
                           ForwardIterator last,
                           Predictate pred )
{
    ForwardIterator out = first;
    bool copy = false;
    while( first != last) {
        if( pred( *first ) != false ) {
            ++first;
            copy = true;
        } else {
            if( copy ){
                //avoid unecessary copies
                *out = *first;
            }
            ++first;
            ++out;
        }
    }
    return( out );
}

// unique( ForwardIterator, ForwardIterator )
// ******************************************
template< class ForwardIterator >
ForwardIterator unique( ForwardIterator first, ForwardIterator last )
{
    if( first == last ) return last;
    ForwardIterator probe( first );
    ++probe;

    while( probe != last ) {
        if( !( *first == *probe ) ) {
            ++first;
            if( first != probe ) *first = *probe;
        }
        ++probe;
    }
    ++first;
    return( first );
}

// unique( ForwardIterator, ForwardIterator, BinaryPredicate )
// ***********************************************************
template< class ForwardIterator, class BinaryPredicate >
ForwardIterator unique( ForwardIterator first,
                        ForwardIterator last,
                        BinaryPredicate pred )
{
    if( first == last ) return last;
    ForwardIterator probe( first );
    ++probe;

    while( probe != last ) {
        if( !pred( *first, *probe ) ) {
            ++first;
            if( first != probe ) *first = *probe;
        }
        ++probe;
    }
    ++first;
    return( first );
}

// unique_copy( InputIterator, InputIterator, OutputIterator )
// ***********************************************************
template< class InputIterator, class OutputIterator >
OutputIterator unique_copy( InputIterator first,
                            InputIterator last,
                            OutputIterator result )
{
    if( first == last ) return result;
    iterator_traits< InputIterator >::value_type temp( *first );
    ++first;
    *result++ = temp;

    while( first != last ) {
        if( !( temp == *first ) ) {
            temp = *first;
            *result++ = temp;
        }
        ++first;
    }
    return( result );
}

// unique_copy(InputIterator, InputIterator, OutputIterator, BinaryPredicate )
// ***************************************************************************
template< class InputIterator, class OutputIterator, class BinaryPredicate >
OutputIterator unique_copy( InputIterator first,
                            InputIterator last,
                            OutputIterator result,
                            BinaryPredicate pred )
{
    if( first == last ) return result;
    iterator_traits< InputIterator >::value_type temp( *first );
    ++first;
    *result++ = temp;

    while( first != last ) {
        if( !pred( temp, *first ) ) {
            temp = *first;
            *result++ = temp;
        }
        ++first;
    }
    return( result );
}

// reverse( Bidirectional, Bidirectional )
// ***************************************
template< class Bidirectional >
void reverse( Bidirectional first, Bidirectional last )
{
    if( first == last ) return;
    --last;
    while( first != last ) {
        swap( *first, *last );
        ++first;
        if( first == last ) break;
        --last;
    }
}

// reverse_copy( Bidirectional, Bidirectional, OutputIterator )
// ************************************************************
template< class Bidirectional, class OutputIterator >
OutputIterator reverse_copy( Bidirectional first,
                             Bidirectional last,
                             OutputIterator result )
{
    if( first == last ) return( result );
    while( --last != first ) {
        *result = *last;
        ++result;
    }
    *result = *last;