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

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

#define MAXINT 32767

using namespace std;

struct Error {
	string errmsg;
	Error (string em){errmsg = em;}};

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*);
	int*& operator[] (int i) {return dist[i];}
	int getN () { return n; }
};

class Individ{
public: 
	virtual ~Individ () {}
	
	virtual int fitness () const = 0;
	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;
};

class TravelIndivid: public Individ{
	int *chromo;
	static Graph g;
	int numPts;
	
	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 {
		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(); }
	friend ostream& operator<< (ostream& out, const TravelIndivid& list);
	string toString () const {
		string str = "";
		for (int i = 0; i<numPts; i++) str += string((char*)chromo[i]) + " ";
		return str;
	}
};
Graph TravelIndivid::g("iLoveC++.grf");

class Population {
	//const int size = 128;
	vector<Individ*> staff;
public: static int size;
	Population () { 
		staff = vector<Individ*>(size); 
		vector<Individ*>::iterator i; 
		for (i = staff.begin (); i != staff.end(); i++ ) 
			*i = new TravelIndivid();
		sort();
	}
	
	void sort() { 
		vector<Individ*>::iterator f = staff.begin();
		vector<Individ*>::iterator l = staff.end();
		sort (f,--l); }
	void sort (vector<Individ*>::iterator first,
		vector<Individ*>::iterator last);
	Individ* getBest() { return staff[0]; }
};
int Population::size = 8;

class GA {
	Population oldpop, pop;
	
public: static double eps;
	static int maxIter;
	static int numInd;

	//GA() { }
	Individ* go() { return pop.getBest(); }
};
double GA::eps = 0.001;
int GA::maxIter = 256;

Graph::Graph (const char* fname){
	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();
}

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

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<<ti.len();
	return out;
}

int main (){
	GA ga;
	TravelIndivid *ind = (TravelIndivid*)ga.go();
	
	cout<<*ind<<endl;
	return 0;
}