// Insertion sort with iterators. Provides both a two-parameter
// and a three-parameter version. To force expansions, we wind up
// writing extra versions, but these should
// not be called by general users and are considered private helpers.

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

// This is the guts of the generic insertion sort routine.
// It is logically a private routine.
// It requires a beginning and ending iterator,
// a comparison function object,
// and a dummy parameter that is used to establish
// the type of objects that are in the container.
template <class RandomIterator, class Comparator, class Object>
void insertionSort( const RandomIterator & begin,
                    const RandomIterator & end,
                    Comparator lessThan,
                    const Object & obj )
{
    RandomIterator j;

    for( RandomIterator p = begin+1; p != end; ++p )
    {
        Object tmp = *p;
        for( j = p; j != begin && lessThan( tmp, *( j-1 ) ); --j )
            *j = *(j-1);
        *j = tmp;
    }
}

// This is the more public version of insertion sort.
// It requires a pair of iterators and a comparison
// function object. It calls the four parameter version
// by sending *begin as the additional parameter.
// The template expansion will allow the routine
// above to then deduce Object, on the basis of *begin.
template <class RandomIterator, class Comparator>
void insertionSort( const RandomIterator & begin,
                    const RandomIterator & end,
                    Comparator lessThan )
{
    if( begin != end )
        insertionSort( begin, end, lessThan, *begin );
}

// The two-parameter version logically would call
// the three parameter version, and send in a
// default function object. The function object
// would be less<Object>, but what is Object?
// We don't know, so we pass *begin to another
// version of insertionSort to deduce it.
template <class RandomIterator>
void insertionSort( const RandomIterator & begin,
                    const RandomIterator & end )
{
    if( begin != end )
        insertionSortHelp( begin, end, *begin );
}

// The three-parameter helper
// uses Object to construct less<Object>, and
// calls the three-parameter version of insertionSort.
template <class RandomIterator, class Object>
void insertionSortHelp( const RandomIterator & begin,
                        const RandomIterator & end,
                        const Object & obj )
{
    insertionSort( begin, end, less<Object>( ) );
}

// A test program.
int main( )
{
    vector<double> v;

    v.push_back( 4.7 );
    v.push_back( 6.7 );
    v.push_back( 2.2 );
    v.push_back( 1.9 );
    v.push_back( 8.6 );
    v.push_back( 3.4 );

    insertionSort( v.begin( ), v.end( ) );

    for( int i = 0; i < v.size( ); i++ )
        cout << v[ i ] << endl;

    return 0;
}