478 lines
14 KiB
C
478 lines
14 KiB
C
|
///////////////////////////////////////////////////////////////////////////
|
||
|
|
// FILE: _algsort.h (Definitions of sorting and related operations)
|
||
|
|
//
|
||
|
|
// =========================================================================
|
||
|
|
//
|
||
|
|
// Open Watcom Project
|
||
|
|
//
|
||
|
|
// Copyright (c) 2004-2010 The Open Watcom Contributors. All Rights Reserved.
|
||
|
|
//
|
||
|
|
// This file is automatically generated. Do not edit directly.
|
||
|
|
//
|
||
|
|
// =========================================================================
|
||
|
|
//
|
||
|
|
// Description: This header is part of the <algorithm> header.
|
||
|
|
///////////////////////////////////////////////////////////////////////////
|
||
|
|
#ifndef __ALGSORT_H_INCLUDED
|
||
|
|
#define __ALGSORT_H_INCLUDED
|
||
|
|
|
||
|
|
#ifndef _ENABLE_AUTODEPEND
|
||
|
|
#pragma read_only_file;
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#ifndef _ALGORITHM_INCLUDED
|
||
|
|
#error The header _algsort.h requires algorithm.
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#ifndef _FUNCTIONAL_INCLUDED
|
||
|
|
#include <function>
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#ifndef _ITERATOR_INCLUDED
|
||
|
|
#include <iterator>
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#ifndef _STDEXCEPT_INCLUDED
|
||
|
|
#include <stdexcep>
|
||
|
|
#endif
|
||
|
|
|
||
|
|
namespace std {
|
||
|
|
|
||
|
|
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 ); }
|
||
|
|
|
||
|
|
template< class RandomAccess >
|
||
|
|
void heapify( RandomAccess first,
|
||
|
|
RandomAccess last,
|
||
|
|
typename
|
||
|
|
iterator_traits< RandomAccess >::difference_type 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;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
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)
|
||
|
|
{
|
||
|
|
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);
|
||
|
|
}
|
||
|
|
|
||
|
|
// 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 >
|
||
|
|
void quick_sort( RandomAccess seq,
|
||
|
|
typename std::iterator_traits< RandomAccess >::difference_type left,
|
||
|
|
typename std::iterator_traits< RandomAccess >::difference_type right,
|
||
|
|
Compare comp)
|
||
|
|
{
|
||
|
|
using std::swap;
|
||
|
|
typedef typename std::iterator_traits< RandomAccess >::difference_type
|
||
|
|
difference_type;
|
||
|
|
|
||
|
|
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 );
|
||
|
|
|
||
|
|
difference_type i = left;
|
||
|
|
difference_type 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 >
|
||
|
|
inline
|
||
|
|
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 >
|
||
|
|
inline
|
||
|
|
void sort( RandomAccess first, RandomAccess last )
|
||
|
|
{
|
||
|
|
if( first == last ) return;
|
||
|
|
_ow::quick_sort(first, 0, (last - first) - 1,
|
||
|
|
std::less< typename iterator_traits< RandomAccess >::value_type >( )
|
||
|
|
);
|
||
|
|
}
|
||
|
|
|
||
|
|
// binary_search( ForwardIterator, ForwardIterator, const Type &, Compare )
|
||
|
|
// ************************************************************************
|
||
|
|
template< class ForwardIterator, class Type, class Compare >
|
||
|
|
inline
|
||
|
|
bool binary_search( ForwardIterator first, ForwardIterator last,
|
||
|
|
const Type &value,
|
||
|
|
Compare comp )
|
||
|
|
{
|
||
|
|
typedef typename
|
||
|
|
iterator_traits< ForwardIterator >::difference_type length_type;
|
||
|
|
|
||
|
|
ForwardIterator p1( first );
|
||
|
|
length_type len = last - first; // This should really use distance( ).
|
||
|
|
length_type mid = len/2;
|
||
|
|
ForwardIterator p2( p1 );
|
||
|
|
advance( p2, mid );
|
||
|
|
|
||
|
|
while( len > 0 ) {
|
||
|
|
if( comp( value, *p2 ) ) {
|
||
|
|
len = mid;
|
||
|
|
mid = len/2;
|
||
|
|
p2 = p1;
|
||
|
|
advance( p2, mid );
|
||
|
|
}
|
||
|
|
else if( comp( *p2, value ) ) {
|
||
|
|
len = mid + ((len % 2) == 0 ? 0 : 1 ) - 1;
|
||
|
|
mid = len/2;
|
||
|
|
p1 = ++p2;
|
||
|
|
advance( p2, mid );
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
return( true );
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return( false );
|
||
|
|
}
|
||
|
|
|
||
|
|
// binary_search( ForwardIterator, ForwardIterator, const Type & )
|
||
|
|
// ***************************************************************
|
||
|
|
template< class ForwardIterator, class Type >
|
||
|
|
inline
|
||
|
|
bool binary_search( ForwardIterator first, ForwardIterator last,
|
||
|
|
const Type &value )
|
||
|
|
{
|
||
|
|
return( binary_search( first, last, value,
|
||
|
|
std::less< typename iterator_traits< ForwardIterator >::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 );
|
||
|
|
}
|
||
|
|
|
||
|
|
// next_permutation( Bidirectional, Bidirectional, Compare )
|
||
|
|
// *********************************************************
|
||
|
|
template< typename Bidirectional, typename Compare >
|
||
|
|
bool next_permutation( Bidirectional first, Bidirectional last, Compare comp )
|
||
|
|
{
|
||
|
|
if( first == last ) return false;
|
||
|
|
Bidirectional i = first;
|
||
|
|
++i;
|
||
|
|
if( i == last ) return false;
|
||
|
|
i = last;
|
||
|
|
--i;
|
||
|
|
|
||
|
|
for( ;; ) {
|
||
|
|
Bidirectional ii = i;
|
||
|
|
--i;
|
||
|
|
if( comp( *i, *ii ) ) {
|
||
|
|
Bidirectional j = last;
|
||
|
|
while( !comp( *i, *--j ) ) /* null */ ;
|
||
|
|
swap( *i, *j );
|
||
|
|
reverse( ii, last );
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
if( i == first ) {
|
||
|
|
reverse( first, last );
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// next_permutation( Bidirectional, Bidirectional )
|
||
|
|
// ************************************************
|
||
|
|
template< typename Bidirectional >
|
||
|
|
bool next_permutation( Bidirectional first, Bidirectional last )
|
||
|
|
{
|
||
|
|
return ( next_permutation( first, last,
|
||
|
|
std::less< typename iterator_traits< Bidirectional >::value_type >( )
|
||
|
|
) );
|
||
|
|
}
|
||
|
|
|
||
|
|
// prev_permutation( Bidirectional, Bidirectional, Compare )
|
||
|
|
// *********************************************************
|
||
|
|
template< class Bidirectional, class Compare >
|
||
|
|
bool prev_permutation( Bidirectional first, Bidirectional last, Compare comp )
|
||
|
|
{
|
||
|
|
if( first == last ) return false;
|
||
|
|
Bidirectional i = first;
|
||
|
|
++i;
|
||
|
|
if( i == last ) return false;
|
||
|
|
i = last;
|
||
|
|
--i;
|
||
|
|
|
||
|
|
for( ;; ) {
|
||
|
|
Bidirectional ii = i;
|
||
|
|
--i;
|
||
|
|
if( comp( *ii, *i ) ) {
|
||
|
|
Bidirectional j = last;
|
||
|
|
while( !comp( *--j, *i ) ) /* null */ ;
|
||
|
|
swap( *i, *j );
|
||
|
|
reverse( ii, last );
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
if( i == first ) {
|
||
|
|
reverse( first, last );
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// prev_permutation( Bidirectional, Bidirectional )
|
||
|
|
// ************************************************
|
||
|
|
template< typename Bidirectional >
|
||
|
|
bool prev_permutation( Bidirectional first, Bidirectional last )
|
||
|
|
{
|
||
|
|
return ( prev_permutation( first, last,
|
||
|
|
std::less< typename iterator_traits< Bidirectional >::value_type >( )
|
||
|
|
) );
|
||
|
|
}
|
||
|
|
|
||
|
|
} // namespace std
|
||
|
|
|
||
|
|
#endif
|