algorith.mh

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

///////////////////////////////////////////////////////////////////////////
// FILE: algorithm (Definitions of various algorithm templates)
//
:keep CPP_HDR
:include crwatcnt.sp
//
// Description: This header is part of the C++ standard library. It
//              defines a collection of useful algorithm templates.
///////////////////////////////////////////////////////////////////////////
#ifndef _ALGORITHM_INCLUDED
#define _ALGORITHM_INCLUDED
:include readonly.sp

#ifndef __cplusplus
#error The header algorithm requires C++
#endif

#if defined(max) || defined(min)
  #error The previously defined macro(s) max/min conflict with algorithm
:: We could #undef max/min here, but that seems a bit rude.
#endif

#ifndef _CSTDLIB_INCLUDED
  #include <cstdlib>
#endif

#ifndef _FUNCTIONAL_INCLUDED
  #include <function>
#endif

#ifndef _ITERATOR_INCLUDED
  #include <iterator>
#endif

#ifndef _STDEXCEPT_INCLUDED
  #include <stdexcep>
#endif

#ifndef _UTILITY_INCLUDED
  #include <utility>
#endif

namespace std {

// Non-modifying sequence operations
// =================================

// for_each( InputIterator, InputIterator, Function )
// **************************************************
template< class InputIterator, class Function >
Function for_each( InputIterator first, InputIterator last, Function f )
{
    while( first != last ) {
        f( *first );
        ++first;
    }
    return( f );
}

// find( InputIterator, InputIterator, const Type & )
// **************************************************
template< class InputIterator, class Type >
InputIterator find( InputIterator first, InputIterator last, const Type &value)
{
    while( first != last ) {
        if( *first == value ) return first;
        ++first;
    }
    return( first );
}

// find_if( InputIterator, InputIterator, Predicate )
// **************************************************
template< class InputIterator, class Predicate >
InputIterator find_if( InputIterator first, InputIterator last, Predicate pred)
{
    while( first != last ) {
        if( pred( *first ) != false ) return first;
        ++first;
    }
    return( first );
}

// find_end( Fwd1, Fwd1, Fwd2, Fwd2)
// *********************************
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator1 find_end( ForwardIterator1 first1,
                           ForwardIterator1 last1,
                           ForwardIterator2 first2,
                           ForwardIterator2 last2 )
{
    ForwardIterator1 a;
    ForwardIterator2 b;
    ForwardIterator1 ans = last1;
    while( first1 != last1 ) {
        //find first item that matches
        while( ! ( *first1 == *first2 ) ) {
            ++first1;
            if( first1 == last1 ) return( ans );
        }
        //see if other items match
        a = first1;
        b = first2;
        do {
            ++a;
            ++b;
            if( b == last2 ) {
                ans = first1;
                break;
            }
            if( a == last1 ) return( ans );
        } while( *a == *b );
        ++first1;
    }
    return( ans );
}

// find_end( Fwd1, Fwd1, Fwd2, Fwd2, BinaryPred )
// **********************************************
template< class ForwardIterator1,
          class ForwardIterator2,
          class BinaryPredictate >
ForwardIterator1 find_end( ForwardIterator1 first1,
                           ForwardIterator1 last1,
                           ForwardIterator2 first2,
                           ForwardIterator2 last2,
                           BinaryPredictate pred )
{
    ForwardIterator1 a;
    ForwardIterator2 b;
    ForwardIterator1 ans = last1;
    while( first1 != last1 ) {
        //find first item that matches
        while( ! ( pred( *first1, *first2 ) ) ) {
            ++first1;
            if( first1 == last1 ) return( ans );
        }
        //see if other items match
        a = first1;
        b = first2;
        do {
            ++a;
            ++b;
            if( b == last2 ) {
                ans = first1;
                break;
            }
            if( a == last1 ) return( ans );
        } while( pred( *a, *b ) );
        ++first1;
    }
    return( ans );
}

// find_first_of( Fwd1, Fwd1, Fwd2, Fwd2 )
// ***************************************
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator1 find_first_of( ForwardIterator1 first1,
                                ForwardIterator1 last1,
                                ForwardIterator2 first2,
                                ForwardIterator2 last2)
{
    ForwardIterator2 i;
    while( first1 != last1 ) {
        for( i = first2; i != last2; ++i ){
            if( *first1 == *i ) return first1;
        }
        ++first1;
    }
    return( last1 );
}

// find_first_of( Fwd1, Fwd1, Fwd2, Fwd2, Pred )
// *********************************************
template< class ForwardIterator1,
          class ForwardIterator2, 
          class BinaryPredictate >
ForwardIterator1 find_first_of( ForwardIterator1 first1,
                                ForwardIterator1 last1,
                                ForwardIterator2 first2,
                                ForwardIterator2 last2,
                                BinaryPredictate pred )
{
    ForwardIterator2 i;
    while( first1 != last1 ) {
        for( i = first2; i != last2; ++i ){
            if( pred( *first1, *i ) ) return first1;
        }
        ++first1;
    }
    return( last1 );
}

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

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

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

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

:: Commented out due to compiler bug.
#ifdef _NEVER
// count( InputIterator, InputIterator, const Type & )
// ***************************************************
template< class InputIterator, class Type >
typename iterator_traits< InputIterator >::difference_type
    count( InputIterator first,
           InputIterator last,
           const Type &value )
{
    typename iterator_traits< InputIterator >::difference_type number(0);
    while( first != last ) {
        if( *first == value ) ++number;
        ++first;
    }
    return( number );
}

// count_if( InputIterator, InputIterator, Predicate )
// ***************************************************
template< class InputIterator, class Predicate >
typename iterator_traits< InputIterator >::difference_type
    count_if( InputIterator first,
              InputIterator last,
              Predicate pred )
{
    typename iterator_traits< InputIterator >::difference_type number(0);
    while( first != last ) {
        if( pred( *first ) != false ) ++number;
        ++first;
    }
    return( number );
}
#endif

// mismatch( InputIterator1, InputIterator1, InputIterator2 )
//***********************************************************
template< class InputIterator1, class InputIterator2 >
pair< InputIterator1, InputIterator2 >
    mismatch( InputIterator1 first1,
              InputIterator1 last1,
              InputIterator2 first2 )
{
    while( first1 != last1 && *first1 == *first2 ) {
        ++first1; ++first2;
    }
    return( pair< InputIterator1, InputIterator2 >( first1, first2 ) );
} 

// mismatch( InputIterator1, InputIterator1, InputIterator2, BinaryPredicate )
//***************************************************************************
template< class InputIterator1, class InputIterator2, class BinaryPredicate >
pair< InputIterator1, InputIterator2 >
    mismatch( InputIterator1 first1,
              InputIterator1 last1,
              InputIterator2 first2,
              BinaryPredicate pred )
{
    while( first1 != last1 && pred( *first1, *first2 ) != false ) {
        ++first1; ++first2;
    }
    return( pair< InputIterator1, InputIterator2 >( first1, first2 ) );
} 

// equal( InputIterator1, InputIterator1, InputIterator2 )
// *******************************************************
template< class InputIterator1, class InputIterator2 >
bool equal( InputIterator1 first1,
            InputIterator1 last1,
            InputIterator2 first2)
{
    while( first1 != last1 ) {
        if( *first1 != *first2 ) return false;
        ++first1; ++first2;
    }
    return( true );
}

// equal( InputIterator1, InputIterator1, InputIterator2, BinaryPredicate )
// ************************************************************************
template< class InputIterator1, class InputIterator2, class BinaryPredicate >
bool equal( InputIterator1 first1,
            InputIterator1 last1,
            InputIterator2 first2,
            BinaryPredicate pred)
{
    while( first1 != last1 ) {
        if( pred( *first1, *first2 ) == false ) return false;
        ++first1; ++first2;
    }
    return( true );
}


// Mutating Sequence Operations
// ============================

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

// copy_backward( Bidirectional1, Bidirectional1, Bidirectional2 )
// ****************************************************************
template< class Bidirectional1, class Bidirectional2 >
Bidirectional2 copy_backward( Bidirectional1 first,
                              Bidirectional1 last,
                              Bidirectional2 result )
{
    if( first == last ) return( result );
    while( --last != first ) {
        *--result = *last;
    }
    *--result = *last;
    return( result );
}

// swap( Type &, Type & )
// **********************
template< class Type >
inline void swap( Type &x, Type &y )
    { Type tmp(x); x = y; y = tmp; }


// swap_ranges( ForwardIterator1, ForwardIterator1, ForwardIterator2 )
// *******************************************************************
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator2 swap_ranges( ForwardIterator1 first1,
                              ForwardIterator1 last1,
                              ForwardIterator2 first2 )
{
    while( first1 != last1 ) {