// NearestNeighborSearch.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <vector>
#include <ctime>
#include <random>
#include "Neighbours.h"
//
//const int N = 100;

using namespace std;
//default_random_engine eng(time(0));
//default_random_engine eng;

using Graph = vector<vector<double>>;
using Visit = vector <bool>;
using VisitedPoints = vector<int>;

Graph BNNSGraphGenerator() {
    Graph graph(N);
    for (int i = 0; i < graph.size(); i++) {
        graph[i].resize(N);
    }
    uniform_real_distribution<double> distr(1, 10);
    for (int i = 0; i < graph.size(); i++) {
        for (int j = 0; j <= i; j++) {
            if (i == j) {
                graph[i][j] = 0;
                graph[j][i] = 0;
                continue;
            }
            double dist = distr(eng);
            graph[i][j] = dist;
            graph[j][i] = graph[i][j];
        }
    }
    return graph;
}
Visit BNNSVisitGenerator() {
    Visit visit(N);
    for (int i = 0; i < N; i++)
        visit[i] = false;
    return visit;
}
void BNNSGraphPrinter(Graph graph) {
    for (int i = 0; i < graph.size(); i++) {
        for (int j = 0; j < graph.size(); j++)
            cout << graph[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}
void BNNSVisitPrinter(Visit visit) {
    for (int i = 0; i < visit.size(); i++)
        cout << visit[i] << " ";
    cout << endl;
}

int BNNSNearestWayFinder(Graph graph, int index, double& wayLength, Visit& visit) {
    double minimalWay = INFINITY;
    int minimalWayIndex = 0;
    for (int i = 0; i < N; i++)
        if (graph[index][i] < minimalWay && visit[i] == false) {
            minimalWay = graph[index][i];
            minimalWayIndex = i;
        }
    wayLength += minimalWay;
    return (minimalWayIndex);
}

double BNNSTravelingSalesmanNeighbour(Graph& graph, Visit& visit,int i, VisitedPoints &Visited) {

    int visitedCounter = 1;
    int nearestIndex = i;  double wayLength = 0;
    visit[i] = true; Visited.push_back(i);
    while (visitedCounter != N) {
        nearestIndex = BNNSNearestWayFinder(graph, nearestIndex, wayLength, visit);
        visitedCounter++;
        visit[nearestIndex] = true; Visited.push_back(nearestIndex);
    }
    wayLength += graph[i][nearestIndex];
    return wayLength;
}

double BNNSFinder(Graph& graph, Visit& visit) {

    vector< VisitedPoints> allVisitedPoints;
    double minWaylen = INFINITY;
    for (int i = 0; i < N; i++) {
        Visit visit = BNNSVisitGenerator();
        VisitedPoints Visited;
        double wayLen = BNNSTravelingSalesmanNeighbour(graph, visit, i, Visited);
        if (wayLen < minWaylen) {
            minWaylen = wayLen;
        }
        allVisitedPoints.push_back(Visited);
    }
    return minWaylen;
}

//int main() {
//  srand(time(0));
//  Graph graph = BNNSGraphGenerator();
//  Visit visit = BNNSVisitGenerator();
//  BNNSGraphPrinter(graph);
//  //VisitPrinter(visit);
//
//  Finder(graph,visit);
//
//}