algorith.mh

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

    return( ++result );
}

// random_shuffle( RandomAccess, RandomAccess )
// ********************************************
template< class RandomAccess >
void random_shuffle( RandomAccess first, RandomAccess last )
{
    typedef typename iterator_traits< RandomAccess >::difference_type Int;
    Int length = last - first;
    Int i = 1;

    while( i < length ) {
        swap( first[i], first[ rand( ) % ( i + 1 ) ] );
        ++i;
    }
}

// random_shuffle( RandomAccess, RandomAccess, RandomGenerator >
// *************************************************************
template< class RandomAccess, class RandomGenerator >
void random_shuffle( RandomAccess first,
                     RandomAccess last,
                     RandomGenerator rgen )
{
    typedef typename iterator_traits< RandomAccess >::difference_type Int;
    Int length = last - first;
    Int i = 1;

    while( i < length ) {
        swap( first[i], first[ rgen( i + 1 ) ] );
        ++i;
    }
}


// Sorting and related operations
// ==============================

namespace _ow {

    template< class Int >
    inline Int heap_parent( Int index )
        { return ( ( index - 1 )/2 ); }

    template< class Int >
    inline Int heap_left( Int index )
        { return ( 2*index + 1 ); }

    template< class Int >
    inline Int heap_right( Int index )
        { return ( 2*index + 2 ); }

:: The proper declaration doesn't work because of a compiler bug.
#ifdef _NEVER
    template< class RandomAccess >
    void heapify( RandomAccess first,
                  RandomAccess last,
                  typename
                    iterator_traits< RandomAccess >::difference_type index)
#endif
    template< class RandomAccess, class DifferenceType >
    void heapify( RandomAccess first,
                  RandomAccess last,
                  DifferenceType index)
    {
        using std::swap;
        typedef typename iterator_traits< RandomAccess >::difference_type Int;

        Int size = last - first;
        Int L    = heap_left( index );   // Index of left child.
        Int R    = heap_right( index );  // Index of right child.
        Int largest = index;             // Index of largest child.

        if( L < size && first[largest] < first[L] ) largest = L;
        if( R < size && first[largest] < first[R] ) largest = R;
        if( largest != index ) {
            swap( first[index], first[largest] );
            heapify( first, last, largest );
        }
    }

} // namespace _ow

// push_heap( RandomAccess, RandomAccess )
// ***************************************
template< class RandomAccess >
void push_heap( RandomAccess first, RandomAccess last )
{
    typedef typename iterator_traits< RandomAccess >::difference_type Int;
    using std::swap;
    using _ow::heap_parent;

    if( first == last )
        throw std::domain_error( "heap underflow" );

    Int index = (last - first) - 1;
    while( index > 0 && first[heap_parent( index )] < first[index] ) {
        swap( first[heap_parent( index )], first[index] );
        index = heap_parent( index );
    }
}

// pop_heap( RandomAccess, RandomAccess )
// **************************************
template< class RandomAccess >
void pop_heap( RandomAccess first, RandomAccess last )
{
    using std::swap;

    if( first == last )
        throw std::domain_error( "heap underflow" );

    --last;
    if( first != last ) {
        swap( *first, *last );
        _ow::heapify( first, last, 0 );
    }
}

// make_heap( RandomAccess, RandomAccess )
// ***************************************
template< class RandomAccess >
void make_heap( RandomAccess first, RandomAccess last )
{
    typedef typename iterator_traits< RandomAccess >::difference_type Int;

    Int size = last - first;
    Int index;

    if( size <= 1 ) return;
    for( index = size/2 - 1; index >= 0; --index ) {
        _ow::heapify( first, last, index );
    }
}

// sort_heap( RandomAccess, RandomAccess )
// ***************************************
template< class RandomAccess >
void sort_heap( RandomAccess first, RandomAccess last )
{
    typedef typename iterator_traits< RandomAccess >::difference_type Int;
    using std::swap;

    Int size = last - first;
    Int index;

    if( size <= 1 ) return;
    for( index = size - 1; index > 0; --index ) {
        swap( first[0], first[index] );
        --last;
        _ow::heapify( first, last, 0 );
    }
}

namespace _ow {

    // Used for small subsequences when doing a QuickSort.
    template< class Bidirectional, class Compare>
    void insertion_sort( Bidirectional first,
                         Bidirectional last,
                         Compare comp)
    {
        if( first == last ) return;

        Bidirectional current = first;
        ++current;
        while( current != last ) {
            typename std::iterator_traits< Bidirectional >::value_type
            temp = *current;
            Bidirectional p1 = current;
            Bidirectional p2 = current;
            --p2;

            while( comp( temp, *p2 ) ) {
                *p1 = *p2;
                if( p2 == first ) {
                    --p1;
                    break;
                }
                --p1; --p2;
            }
            *p1 = temp;
            ++current;
        }
    }

#ifdef _NEVER
    template< class RandomAccess, class Compare >
    RandomAccess
    med3( RandomAccess seq,
          typename std::iterator_traits< RandomAccess >::difference_type left,
          typename std::iterator_traits< RandomAccess >::difference_type right,
          Compare comp)
#endif
    template< class RandomAccess, class Compare, class DifferenceType >
    RandomAccess
    med3( RandomAccess seq,
          DifferenceType left,
          DifferenceType right,
          Compare comp)
    {
        using std::swap;
        typename std::iterator_traits< RandomAccess >::difference_type middle;

        middle = (left + right) / 2;
        if( comp( seq[middle], seq[left] ) ) swap( seq[left], seq[middle] );
        if( comp( seq[right], seq[left] ) ) swap( seq[left], seq[right] );
        if( comp( seq[right], seq[middle] ) ) swap( seq[middle], seq[right] );

        swap( seq[middle], seq[right - 1] );
        return seq + (right - 1);
    }

#ifdef _NEVER
    template< class RandomAccess, class Compare >
    void quick_sort( RandomAccess seq,
          typename std::iterator_traits< RandomAccess >::difference_type left,
          typename std::iterator_traits< RandomAccess >::difference_type right,
                     Compare comp)
#endif
    // Based on the QuickSort algorithm in Mark Allen Weiss's "Data
    // Structures and Algorithm Analysis in C++" third edition; Addison
    // Wesley; ISBN=0-321-44146-X.
    //
    template< class RandomAccess, class Compare, class DifferenceType >
    void quick_sort( RandomAccess seq,
                     DifferenceType left,
                     DifferenceType right,
                     Compare comp)
    {
        using std::swap;

        if( right - left < 10 )
            insertion_sort( seq + left, seq + right + 1, comp );
        else {
            typename std::iterator_traits< RandomAccess >::value_type
            pivot = *med3( seq, left, right, comp );

            DifferenceType i = left;
            DifferenceType j = right - 1;
            for( ; ; ) {
                while( comp( seq[++i], pivot ) ) ;
                while( comp( pivot, seq[--j] ) ) ;
                if( i >= j ) break;
                swap( seq[i], seq[j] );
            }

            swap( seq[i], seq[right-1] );
            quick_sort( seq, left, i - 1, comp );
            quick_sort( seq, i + 1, right, comp );
        }
    }

} // namespace _ow


// sort( RandomAccess, RandomAccess, Compare )
// *******************************************
template< class RandomAccess, class Compare >
void sort( RandomAccess first, RandomAccess last, Compare comp )
{
    if( first == last ) return;
    _ow::quick_sort( first, 0, (last - first) - 1, comp );
}

// sort( RandomAccess, RandomAccess )
// **********************************
template< class RandomAccess >
void sort( RandomAccess first, RandomAccess last )
{
    if( first == last ) return;
    _ow::quick_sort(
      first, 0, (last - first) - 1,
      std::less< typename std::iterator_traits< RandomAccess >::value_type >( )
    );
}    

// min( const Type &, const Type & )
// *********************************
template< class Type >
inline const Type &min( const Type &x, const Type &y )
    { return( (y < x) ? y : x ); }

// max( const Type &, const Type & )
// *********************************
template< class Type >
inline const Type &max( const Type &x, const Type &y )
    { return( (x < y) ? y : x ); }

// min( const Type &, const Type &, Compare )
// ******************************************
template< class Type, class Compare >
inline const Type &min( const Type &x, const Type &y, Compare comp )
    { return( comp( y, x ) ? y : x ); }

// max( const Type &, const Type &, Compare )
// ******************************************
template< class Type, class Compare >
inline const Type &max( const Type &x, const Type &y, Compare comp )
    { return( comp( x, y ) ? y : x ); }

// min_element( ForwardIterator, ForwardIterator )
// ***********************************************
template< class ForwardIterator >
ForwardIterator min_element( ForwardIterator first, ForwardIterator last )
{
    if( first == last ) return( last );
    ForwardIterator tmp( first );
    ++first;
    while( first != last ) {
        if( *first < *tmp ) tmp = first;
        ++first;
    }
    return( tmp );
}

// min_element( ForwardIterator, ForwardIterator, Compare )
// ********************************************************
template< class ForwardIterator, class Compare >
ForwardIterator min_element( ForwardIterator first,
                             ForwardIterator last,
                             Compare comp )
{
    if( first == last ) return( last );
    ForwardIterator tmp( first );
    ++first;
    while( first != last ) {
        if( comp( *first, *tmp ) ) tmp = first;
        ++first;
    }
    return( tmp );
}

// max_element( ForwardIterator, ForwardIterator )
// ***********************************************
template< class ForwardIterator >
ForwardIterator max_element( ForwardIterator first, ForwardIterator last )
{
    if( first == last ) return( last );
    ForwardIterator tmp( first );
    ++first;
    while( first != last ) {
        if( *tmp < *first ) tmp = first;
        ++first;
    }
    return( tmp );
}

// max_element( ForwardIterator, ForwardIterator, Compare )
// ********************************************************
template< class ForwardIterator, class Compare >
ForwardIterator max_element( ForwardIterator first,
                             ForwardIterator last,
                             Compare comp )
{
    if( first == last ) return( last );
    ForwardIterator tmp( first );
    ++first;
    while( first != last ) {
        if( comp( *tmp, *first ) ) tmp = first;
        ++first;
    }
    return( tmp );
}

} // namespace std

#endif