var GA = function(options) {
    this.id = options.id;
    this.pause = false;
    this.drawing = false;
    this.nodes = options.nodes;
    this.size = options.size;
    this.n = options.nodes.length;
    this.k = 5;
    this.sigma = options.sigma;
    this.init = options.init;
    this.crosstype = options.crosstype;
    this.crossrate = options.crossrate;
    this.muttype = options.muttype;
    this.mutrate = options.mutrate;
    this.genDelay = options.genDelay;
    this.showGraph = options.showGraph;
    this.showProgress = options.showProgress;
    this.showConvergence = options.showConvergence;
    this.best = 0;
    this.repeats = 0;
    this.edgeDistr = null;
    this.initEdgePcts();
};

GA.prototype.edgeCosts = function() {
    this.constant = 0;
    this.costMatrix = []
    for(var i=0; i<this.n; i++) {
        this.costMatrix.push([]);
        for(var j=0; j<this.n; j++) {
            var dist = distance(this.nodes[i], this.nodes[j])
            this.constant += dist;
            this.costMatrix[i].push(dist);
        }
    }
    this.constant /= this.n;
};

GA.prototype.cost = function(path) {
    var sum = 0;
    for(var i=0; i<path.length-1; i++) {
        sum += this.costMatrix[path[i]][path[i+1]];
    }
    return sum;
};

GA.prototype.fitness = function(path) {
    return this.constant/this.cost(path);
};

GA.prototype.prob = function() {
    if(this.edgeDistr == null) {
        this.edgeDistr = this.edgeDistribution();
    }
    var cities = [];
    for(var i=0; i<this.n; i++) {
        cities.push(i);
    }
    var ind = [];
    var ridx = -1;
    for(var i=0; i<this.n; i++) {
        if(ridx == -1) {
            ridx = randint(0, cities.length);
        }
        var last = cities.splice(ridx, 1)[0];
        ind.push(last);
        var city = pdistr(this.edgeDistr[last]);
        ridx = cities.indexOf(city);
        /*
        var rp = Math.random();
        for(var j=0; j<this.edgeDistr[last].length; j++) {
            if(rp <= this.edgeDistr[last][j]) {
                if(cities.indexOf(j) != -1) {
                    ridx = cities.indexOf(j)
                } else {
                    ridx = -1
                }
                break;
            }
        }
        */
    }
    ind.push(ind[0]);
    return ind;
}

GA.prototype.rand = function() {
    var path = [];
    for(var j=0; j<this.n; j++) {
        path.push(j);
    }
    shuffle(path);
    path.push(path[0]);
    return path;
}

GA.prototype.createPool = function() {
    this.pool = []
    for(var i=0; i<this.size; i++) {
        var path = this[this.init]();
        var individual = {}
        individual.path = path;
        individual.fitness = this.fitness(path);
        this.pool.push(individual);
    }
    this.pool.sort(function(a, b) {
        return b.fitness - a.fitness;
    });
};

GA.prototype.tournamentSelect = function(k) {
    var bestFitness = 0;
    for(var i=0; i<k; i++) {
        var r = randint(0, this.size);
        if(this.pool[r].fitness > bestFitness) {
            bestFitness = this.pool[r].fitness;
            padre = r;
        }
    }
    return this.pool[padre];
};

GA.prototype.hasConverged = function() {
    var edges = [];
    for(var i=0; i<this.n; i++) {
        edges.push([]);
        for(var j=0; j<this.n; j++) {
            edges[i].push(0);
        }
    }
    $(this.pool).each(function() {
        for(var i=0; i<this.path.length; i++) {
            j = (i+1)%this.path.length;
            edges[this.path[i]][this.path[j]] += 1;
        }
    });
    this.converge = [];
    for(var i=0; i<this.n; i++) {
        var sorted = edges[i].sort(function(a, b) {
            return b - a;
        });
        this.converge.push((sorted[0]+sorted[1])/this.size);
    }
    var percConv = avg(this.converge);
    console.log("Percent converged: " + percConv);
    return Math.min.apply(null, this.converge) > 0.95;
}

GA.prototype.runGeneration = function(options) {
    if(this.drawing || (options.delay <= 0 && !options.waited)) {
        var that = this;
        var delay = this.drawing ? ('waited' in options && options.waited ? options.delay : that.n*options.delay) : this.genDelay;
        setTimeout(function() {
            options.waited = true;
            that.runGeneration(options);
        }, delay);
    } else {
        if(!this.pause) {
            options.waited = false;
            this.avgEdgePercentile();
            this.crossover();
            this.mutate();
            this.pool.sort(function(a, b) {
                return b.fitness - a.fitness;
            });
            var changed = this.pool[0].fitness > this.best;

            console.log(this.generation);
            this.best = Math.max(this.pool[0].fitness, this.best);
            console.log(this.best);

            this.generation++;
            if(changed) {
                this.top10 = 0;
                this.avg = 0;
                for(var i=0; i<this.size; i++) {
                    if(i < this.size/10) {
                        this.top10 += this.pool[i].fitness;
                    }
                    this.avg += this.pool[i].fitness;
                }
                this.top10 /= (this.size/10);
                this.avg /= this.size;
                if(this.showGraph) {
                    this.removeEdges();
                    this.sigma.refresh();
                    this.drawEdges(this.sigma, this.pool[0].path.slice(), options.delay);
                }
            }
            var converged = this.hasConverged();
            this.updateCharts();
            if(('times' in options && this.generation < options.times) || 
                    ('maxtimes' in options && this.generation < options.maxtimes && !converged)) {
                this.runGeneration(options);
            } else {
                $('.fa', this.progress.renderTo.parentNode.parentNode).removeClass('fa-play').removeClass('fa-pause').addClass('fa-repeat').css('transform', 'translate(-50%, -50%)');
                this.done = true;
            }
        } else {
            var that = this;
            setTimeout(function() {
                that.runGeneration(options);
            }, 1000);
        }
    }
};

GA.prototype.run = function(options) {
    this.pause = options['pause'];
    if(this.pause) {
        options.pause = false;
        $('.fa', $('#tsp-pause-' + this.id).parent()).removeClass('fa-pause').addClass('fa-play').css('transform', 'translate(-40%, -50%)');
    }
    this.runOptions = clone(options);

    for(var i=0; i<this.progress.series.length; i++) {
        this.progress.series[i].setData([]);
    }
    this.best = 0;
    this.top10 = 0;
    this.avg = 0;

    this.edgeCosts();
    this.createPool();
    this.done = false;
    this.generation = 0;
    this.runGeneration(options);
};