// ==========================================================================
// $Id: stl_sort.cpp,v 1.2 2011/09/10 01:08:19 jlang Exp $
// CSI2372 example Code for lecture 11
// ==========================================================================
// (C)opyright:
//
//   Jochen Lang
//   SITE, University of Ottawa
//   800 King Edward Ave.
//   Ottawa, On., K1N 6N5
//   Canada. 
//   http://www.site.uottawa.ca
// 
// Creator: jlang (Jochen Lang)
// Email:   jlang@site.uottawa.ca
// ==========================================================================
// $Log: stl_sort.cpp,v $
// Revision 1.2  2011/09/10 01:08:19  jlang
// Updates F10
//
// Revision 1.1  2006/11/08 01:41:35  jlang
// added stl code for lecture 11
//
//
// ==========================================================================
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using std::cout;
using std::endl;
using std::vector;
using std::sort;
using std::stable_sort;

template <class T, const int NUM>
class Point;

template <class T, const int NUM>
bool lessThan(const Point<T,NUM>& ptA, const Point<T,NUM>& ptB );


template <class T, const int NUM>
class Point{
  T d_components[NUM];
public:
  Point();
  Point( T* _components );
  bool operator<( const Point<T,NUM>& oPoint ) const;
  void print() const;

  friend bool lessThan<T,NUM>(const Point<T,NUM>& ptA, 
			      const Point<T,NUM>& ptB );
};

template <class T, const int NUM>
Point<T,NUM>::Point() 
{}

template <class T, const int NUM>
Point<T,NUM>::Point( T* _components ) 
{
  for ( int i=0; i<NUM; i++ ) {
    d_components[i] = _components[i];
  }
}

template <class T, const int NUM>
bool Point<T,NUM>::operator<( const Point<T,NUM>& oPoint ) const {
  return d_components[0] < oPoint.d_components[0];
}

template <class T, const int NUM>
void Point<T,NUM>::print() const
{
  cout << "( ";
  for ( int i=0; i<NUM; i++ ) {
    if (i!=0) cout  << ", ";
    cout << d_components[i];
  }  
  cout << " )" << endl;
}

template <class T, const int NUM>
bool lessThan(const Point<T,NUM>& ptA, const Point<T,NUM>& ptB ) {
  assert( NUM > 1 );
  return ptA.d_components[1] < ptB.d_components[1];
}


template <class T, const int NUM>
void printVector( vector<Point<T,NUM> >& pVec ) {
  // loop over the elements and print
  for ( typename vector<Point<T,NUM> >::iterator iter = pVec.begin();
	iter != pVec.end();
	++iter ) {
    iter->print();
  }
  cout << endl;
  return;
}


int main() {
  int initA[] = {3,15};
  int initB[] = {3,13};
  int initC[] = {3,8};
  int initD[] = {1,12};
  Point<int,2> iPt1(initA), iPt2(initB), iPt3(initC), iPt4(initD);

  vector<Point<int,2> > pVec;
  pVec.push_back( iPt1 );
  pVec.push_back( iPt2 );
  pVec.push_back( iPt3 );
  pVec.push_back( iPt4 );


  // Print unsorted
  printVector( pVec );
  // Sort the points
  sort( pVec.begin(), pVec.end(), lessThan<int,2> );
  // Print sorted
  printVector( pVec );
  // Stable Sort on 1st coordinate
  stable_sort( pVec.begin(), pVec.end() );
  // Print sorted
  printVector( pVec );

  return 0;
}