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

template <typename Object, typename Comparator>
void insertionSort( vector<Object> & arr, Comparator isLessThan )
{
    for( int p = 1; p < arr.size( ); p++ )
    {
        Object tmp = arr[ p ];

        int j;
        for( j = p; j > 0 && isLessThan( tmp, arr[ j - 1 ] ); j-- )
            arr[ j ] = arr[ j - 1 ];
        arr[ j ] = tmp;
    }
}

template <typename Comparable>
void insertionSort( vector<Comparable> & arr )
{
    insertionSort( arr, less<Comparable>( ) );
}

class Shape
{
  public:
    virtual ~Shape( ) { }
    virtual double area( ) const = 0;
    virtual void print( ostream & out = cout ) const = 0;
};

ostream & operator<< ( ostream & out, const Shape & s ) 
{
    s.print( out );
    return out;
}

class Circle : public Shape
{
  public:
    explicit Circle( double r = 0.0 ) : radius( r )
    {
    }

    double area( ) const
    {
        return 3.14 * radius * radius;
    }

    void print( ostream & out = cout ) const
    {
        out << "[Circle with radius " << radius << "]";
    }

    bool operator< ( const Circle & rhs ) const
    {
        return radius < rhs.radius;
    }

  private:
    double radius;
};

class Rectangle : public Shape
{
  public:
    explicit Rectangle( double len = 0.0, double wid = 0.0 ) : length( len ), width( wid )
    {
    }

    double area( ) const
    {
        return length * width;
    }

    void print( ostream & out = cout ) const
    {
        out << "[Rectangle " << length << "-by-" << width << "]";
    }

  private:
    double length;
    double width;
};

class OrderShapeByArea
{
  public:
    bool operator() ( const Shape & lhs, const Shape & rhs ) const
    { return lhs.area( ) < rhs.area( ); }
};

class OrderShapePtrByArea
{
  public:
    bool operator() ( const Shape * lhs, const Shape * rhs ) const
    { return lhs->area( ) < rhs->area( ); }
};


template <typename Object>
void printVector( const vector<Object> & s )
{
    for( int i = 0; i < s.size( ); i++ )
        cout << s[ i ] << " ";
    cout << endl;
}

template <typename Pointer>
void printVectorPtr( const vector<Pointer> & s )
{
    for( int i = 0; i < s.size( ); i++ )
        cout << *s[ i ] << " ";
    cout << endl;
}

int main( )
{
    vector<Circle> v1;
    v1.push_back( Circle( 3 ) );
    v1.push_back( Circle( 8 ) );
    v1.push_back( Circle( 4 ) );

    printVector( v1 );
    insertionSort( v1 );
    printVector( v1 );
    cout << endl;

    vector<Rectangle> v2;
    v2.push_back( Rectangle( 3, 5 ) );
    v2.push_back( Rectangle( 1, 10 ) );
    v2.push_back( Rectangle( 2, 7 ) );

    printVector( v2 );
    insertionSort( v2, OrderShapeByArea( ) );
    printVector( v2 );
    cout << endl;


    vector<Shape *> v3;
    v3.push_back( new Rectangle( 2, 3 ) );
    v3.push_back( new Circle( 1 ) );
    v3.push_back( new Rectangle( 1, 2 ) );
    printVectorPtr( v3 );
    insertionSort( v3, OrderShapePtrByArea( ) );
    printVectorPtr( v3 );
    cout << endl;

    for( int i = 0; i < v3.size( ); i++ )
        delete v3[ i ];

    return 0;
}