// ==========================================================================
// $Id: bubblesort.cpp,v 1.4 2014/10/22 20:26:06 jlang Exp $
// CSI2372 example Code for lecture 10
// ==========================================================================
// (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: bubblesort.cpp,v $
// Revision 1.4  2014/10/22 20:26:06  jlang
// Update for use of array and forward_list.
//
// Revision 1.3  2011/09/10 01:08:19  jlang
// Updates F10
//
// Revision 1.2  2009/11/16 02:59:02  jlang
// Added bubbble sort instead of selection sort
//
// Revision 1.1  2006/11/05 18:17:03  jlang
// Initial check-in for lecture 10
//
//
// ==========================================================================
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <array>
#include <forward_list>
#include <cstdlib> // because of rand

using std::cout;
using std::endl;
using std::vector;
using std::list;
using std::deque;
using std::array;
using std::forward_list;

template <class T>
void selectionSort( T& container ) {
  // loop over the elements
  for ( typename T::iterator iterA = container.begin();
				iterA != container.end();
				++iterA ) {
    for ( typename T::iterator iterB = iterA;
	  			iterB != container.end();
	  			++iterB ) {
      if ( *iterA > *iterB ) {
				// swap
				typename T::value_type tmp(*iterA);
				*iterA = *iterB;
				*iterB = tmp;
      }
    }
  }
  return;
}

template <class T>
void bubbleSort( T& container ) {
  // place the elements
  int noSwaps = 1;
  typename T::iterator lastEle = container.end();
  --lastEle;
  for ( typename T::iterator iterA = lastEle;
				iterA != container.begin() && noSwaps;
				--iterA ) {
    // count swaps for early out
    noSwaps = 0;
    for ( typename T::iterator iterB = container.begin();
	  			iterB != iterA;
	  			++iterB ) {
      typename T::iterator iterC = iterB;
      if ( *iterB > *(++iterC) ) {
				// swap
				typename T::value_type tmp(*iterB);
				*iterB = *iterC;
				*iterC = tmp;
				++noSwaps;
      }
    }
  }
  return;
}

template <class T>
void printInOrder( T& container ) {
  // loop over the elements
  for ( auto element:container ) { 
	  cout << element << ' ';
  }
  cout << endl;
  return;
}

int main( int argc, char* argv[] ) {
  const int sz=10;
  // Default construction
  vector<int> iVec;
  // add 10 random integers
  for ( int i=0; i<sz; ++i ) {
    iVec.push_back( static_cast<int>(static_cast<double>(rand())/
				     RAND_MAX*sz));
  }
  // Copy the elements into a list
  list<int> iList( iVec.begin(), iVec.end());
  // Copy the elements into a deque
  deque<int> iDeque( iVec.begin(), iVec.end());
	// Copy the elements into a array
	// array is just a wrapper class around a low-level array
	// it does not have the same constructors - just initialization
	array<int,sz> iArray;
	auto iterVec = iVec.cbegin();
	for ( auto &element:iArray) {
		element = *iterVec++;
	}
	// Copy the elements into a forward_list
	forward_list<int> ifList( iVec.begin(), iVec.end());
	
  cout << "Original Vector: " << endl;
  printInOrder( iVec ); 
  cout << endl;
  bubbleSort( iVec );
  cout << "Sorted Vector: " << endl;
  printInOrder( iVec );
  cout << endl;

  cout << "Original List: " << endl;
  printInOrder( iList ); 
  cout << endl;
  bubbleSort( iList );
  cout << "Sorted List: " << endl;
  printInOrder( iList );
  cout << endl;

  cout << "Original Deque: " << endl;
  printInOrder( iDeque ); 
  cout << endl;
  bubbleSort( iDeque );
  cout << "Sorted Deque: " << endl;
  printInOrder( iDeque );
  cout << endl;
  
  cout << "Original Array: " << endl;
  printInOrder( iArray ); 
  cout << endl;
  bubbleSort( iArray );
  cout << "Sorted Array: " << endl;
  printInOrder( iArray );
  cout << endl;

  cout << "Original Forward List: " << endl;
  printInOrder( ifList ); 
  cout << endl;
  // bubbleSort uses -- which is not available in forward_list
  selectionSort( ifList );
  cout << "Sorted Forward List: " << endl;
  printInOrder( ifList );
  cout << endl;

  return 0;
}