/* Practice #1. Genetic algorithm for commivojager problem.  */
/*    Roman V. ShapovAlov. CM&C-210. overrider@cmcspec.ru    */

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <cmath>

#define MAXINT 32767
#define _DEBUG_ 1

using namespace std;

/* CLASSES DECLARATION */

// exception type
struct Error {
	string errmsg;
	Error (string em){errmsg = em;}};

// graph read from file
class Graph{
	int **dist;
	int n;
public: Graph (int n) {  
	int i;  this->n = n;
			dist = new int*[n];
			for (i = 0; i < n; i++) dist[i] = new int[n];
	}
	Graph (const char*);  // constructor gets filename and builds a graph
	int*& operator[] (int i) {return dist[i];}
	int getN () { return n; }
};

// Individual abstract class
// you should implement its methods for using in GA
// access to Ingivid objects by pointer only!!!
class Individ{
public: 
	virtual ~Individ () {}
	
	virtual int fitness () const = 0;   // fitness function
	bool operator< (const Individ& ind2) { return this->fitness() > ind2.fitness(); }
	bool operator> (const Individ& ind2) { return this->fitness() < ind2.fitness(); }
	bool operator== (const Individ& ind2) { return this->fitness() == ind2.fitness(); }
	virtual string toString () const = 0;
	
	virtual void mutate () = 0;          // mutation operator
	virtual void crossover (Individ* spouse) = 0;  // crossover operator
};

// concret Individual type for particular problem solving 
// problrm is a famous Travelling Salesman Problem
class TravelIndivid: public Individ{
	int *chromo;     // chromosome is a sequense of nodes in path
	static Graph g;  // our graph 
	int numPts;      // number of nodes in graph
	
	void swap (int i, int j){
		if (i == j) return;
		chromo[i] = chromo[i]^chromo[j];
		chromo[j] = chromo[i]^chromo[j];
		chromo[i] = chromo[i]^chromo[j];
	}
	
public: 
	TravelIndivid  ();
	virtual ~TravelIndivid () { delete[] chromo; }
	
	int len() const {  // length of a path in its chromosome :)
		int res = 0, dr;
		for (int i = 0; i < numPts; i++) {
			dr = g[chromo[i]][chromo[(i+1)%numPts]];
			if (!dr) return MAXINT;
			res += dr;
		}
		return res;
	}
	
	int fitness () const { return -len(); }
	
	void mutate() { swap (rand()%numPts,rand()%numPts); }
	
	void crossover (Individ* spouse){ 	}
	
	friend ostream& operator<< (ostream& out, const TravelIndivid& list);
	
	// unused operator overloaded for fulfilling requirements
	const TravelIndivid& operator= (const TravelIndivid& ti){
		this->numPts = ti.numPts;
		for (int i = 0; i < numPts; i++) chromo[i] = ti.chromo[i];
		return *this;
	}
	
	string toString () const {
		stringstream str;
		//for (int i = 0; i<numPts; i++) str += string((char*)chromo[i]) + " ";
		for (int i = 0; i<numPts; i++) str << chromo[i] << " ";
		str<<"  lenght = "<<len();
		return str.str();
	}
};
Graph TravelIndivid::g("iLoveC++.grf");

// population is a set of Individuals
class Population {
	static int size;         // constant size of population
	vector<Individ*> staff;  // vector of individuals
public:
	Population () { // creates a population of Individuals
		staff = vector<Individ*>(size); 
		vector<Individ*>::iterator i; 
		for (i = staff.begin (); i != staff.end(); i++ ) 
			*i = new TravelIndivid();
	}
	
	// method for callig the overloaded sort method
	void sort() { 
		vector<Individ*>::iterator f = staff.begin();
		vector<Individ*>::iterator l = staff.end();
		sort (f,l); }
	
	// sorts the population wuith Hoar method. best Individuals come to beginning
	void sort (vector<Individ*>::iterator first,
		vector<Individ*>::iterator last);
		
	// kills bad individuals of population
	void selection (){
		sort();
		vector<Individ*>::iterator i = staff.begin(); 
		vector<Individ*>::iterator j = staff.end(); 
		for (j--; i < j; i++, j--) **j = **i;
	}
	
	void crossover () {
		vector<Individ*>::iterator i = staff.begin(); 
		vector<Individ*>::iterator j = staff.end(); 
		for (j--; i < j; i++, j--) (*i)->crossover(*j);
	}
	
	void mutation (){ 
		vector<Individ*>::iterator i; 
		for (i = staff.begin () + (staff.size() + 1) / 2; i != staff.end(); i++) 
			(*i)->mutate();
	}
	
	// returns the best individ of population
	Individ* getBest() { sort(); return staff[0]; }
	
	friend ostream& operator<< (ostream& out, const Population& pop);
};
int Population::size = 8;

// general genetic algorithm class
class GA {
	Population pop;
	
public: 
	static int maxIter;  // number of GA iterations

	Individ* go() {      // starts the evolution
		if (_DEBUG_) cout<<pop;
		for (int i = 0; i < maxIter; i++){
			pop.selection();
			pop.crossover();
			pop.mutation();
			if (_DEBUG_) cout<<pop;
		}
		return pop.getBest(); }
};
int GA::maxIter = 8;

/* IMPLEMENTATION */

Graph::Graph (const char* fname){
  try{  // try-block for file operations
	ifstream fin(fname);
    if(!fin.is_open()) {
		Error e("Unable to open file!");
		throw e;
	}
	int i, j;
	fin>>n;
	dist = new int*[n];
	for (i = 0; i < n; i++) dist[i] = new int[n];
	for (i = 0; i < n; i++) for (j = 0; j < n; j++) {
		if(fin.eof()) {Error e("Bad file structure!"); throw e;}
		fin>>(*this)[i][j];
	}
	fin.close();
  } catch (Error e) { cerr<<"File reading error: "<<e.errmsg; terminate(); }
}

TravelIndivid::TravelIndivid() {
	int i;
	chromo = new int [numPts = g.getN()];
	for (i = 0; i<numPts; i++) chromo [i] = i;
	for (i = 0; i<numPts*3; i++) swap (i%numPts,rand()%numPts);
}

void Population::sort (vector<Individ*>::iterator first,
		vector<Individ*>::iterator last) {
	if( first == last ) return;
    vector<Individ*>::iterator left  = first;
    vector<Individ*>::iterator right = last;
    vector<Individ*>::iterator pivot = left++;
	while( left != right ) {
		if (**left < **pivot) ++left;
        else {
           while ((left != --right)&& (**pivot < **right) );
           iter_swap( left, right );
      }
    }
	--left;
    iter_swap( first, left );
    sort(first, left);
    sort(right, last);
}

ostream& operator<< (ostream& out, const TravelIndivid& ti){
	for (int i = 0; i<ti.numPts; i++) out<<ti.chromo[i]<<" ";
	out<<"  lenght = "<<ti.len();
	return out;
}

ostream& operator<< (ostream& out, const Population& pop){
	out<<endl;
	for (vector<Individ*>::const_iterator i = pop.staff.begin (); i != pop.staff.end(); i++ ) 
		out<<(*i)->toString()<<endl;
	out<<endl;
	return out;
}

// it's just a main() method :)
int main (){ 
	srand(13);
	GA ga;
	TravelIndivid *ind = (TravelIndivid*)ga.go();
	cout<<"The best route is: "<<*ind<<endl;
	return 0;}