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

const double PI = 3.14;
class Shape
{
public:
    virtual ~Shape( ) { }

    virtual void print( ostream & out = cout ) const = 0;
    virtual double getArea( ) const = 0;
    virtual double getPerimeter( ) const = 0;
};


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

    double getArea( ) const
    { return  PI * radius * radius; }

    double getPerimeter( ) const
    { return 2 * PI * 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:
    Rectangle( double len, double wid ) : length( len ), width( wid )
    { }

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

    double getPerimeter( ) const
    { return 2 * ( length + width ); }

    void print( ostream & out = cout ) const
    { out << "Rectangle with sides: " << length << " and " << width; }

private:
    double length;
    double width;
};

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

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

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


class CompareRectangleByPerimeter
{
public:
    bool operator() ( const Rectangle & lhs, const Rectangle & rhs )
    { return lhs.getPerimeter( ) < rhs.getPerimeter( ); }
};

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

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

template <typename AnyType, typename Comparator>
void mysort( vector<AnyType> & arr, Comparator lessThan )
{
    for( int p = 1; p < arr.size( ); p++ )
    {
        AnyType x = arr[ p ];

        int j = p - 1;

        while( j >= 0 && lessThan( x, arr[ j ] ) )
        {
            arr[ j + 1 ] = arr[ j ];
            j--;
        }

        arr[ j + 1 ] = x;
    }
}

template <typename AnyType>
class DefaultLessThan
{
public:
    bool operator() ( const AnyType & lhs, const AnyType & rhs ) const
    {
        return lhs < rhs;
    }

};

template <typename AnyType>
void mysort( vector<AnyType> & arr )
{
    mysort( arr, DefaultLessThan<AnyType>( ) );
}

class Foo
{
};

int main( )
{
    vector<Circle> v2;
    v2.push_back( Circle( 3.0 ) );
    v2.push_back( Circle( 5.0 ) );
    v2.push_back( Circle( 2.0 ) );
    printVector( v2 );
    mysort( v2 );
    cout << endl;
    printVector( v2 );


    vector<Rectangle> v3;
    v3.push_back( Rectangle( 5.0, 5.0 ) );
    v3.push_back( Rectangle( 3.0, 9.0 ) );
    v3.push_back( Rectangle( 2.0, 12.0 ) );
    printVector( v3 );
    mysort( v3, CompareShapeByArea( ) );
    cout << endl;
    printVector( v3 );

    vector<Shape *> v1;
    v1.push_back( new Circle( 1.0 ) );
    v1.push_back( new Rectangle( 2.0, 3.0 ) );
    v1.push_back( new Circle( 3.0 ) );
    v1.push_back( new Rectangle( 1.0, 1.0 ) );

    printVectorPtr( v1 );
    mysort( v1, ComparePtrToShapeByArea( ) );
    cout << endl;
    printVectorPtr( v1 );

    return 0;
}