/****************************************************
File Name: prog08_DAC183.cpp

Author: David Crowe
Date: 11/18/2015
Problem Number: 8
CS 1428 Fall 2015
Instructor: Priebe

Pulls locations of several cities and optimizes the route between them.
*****************************************************/

#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>

using namespace std;

struct City
{
    string name;
    double x;
    double y;
};

bool getData(string inputFile, City cities[], int &numCities);//checks to see if text file is readable and populates City array
double getDistance(City city1, City city2);//finds distance between two cities
double totalDistance(City cities[], int numCities);//finds total distance between all cities in a certain route
void greedyRouteImprove(City cities[], int numCities, const int MAX_CITIES);//finds an improved route based on getting nearest city
void hungarianMethodRouteImprove(City cities[], int numCities);//uses the hungarian method to find THE most optimal route

int main()
{
    const int MAX_CITIES = 99;
    int numCities = 0;
    City cities[MAX_CITIES];

    string inputFile = "route_data.txt";

    if (getData(inputFile, cities, numCities))
    {
        cout << "Current Route: \n";
        for (int i = 0; i < numCities; i++)
            cout << cities[i].name << endl;
            //setw(5) << " " << setw(4) << cities[i].x << ", " << cities[i].y << endl;

        cout << "\nDistance between cities: \n";
        for (int d = 0; d < numCities - 1; d++)
        cout << setw(10) << cities[d].name << setw(4) <<  " -> " << left << setw(8) << cities[d+1].name << ": "
             << setprecision(2) << fixed << setw(9) << getDistance(cities[d], cities[d+1]) << endl;

        cout << "\nTotal distance: " << totalDistance(cities, numCities) << endl;

        //greedyRouteImprove(cities, numCities, MAX_CITIES);
        hungarianMethodRouteImprove(cities, numCities);
    }
    return 0;
}

bool getData(string inputFile, City cities[], int &numCities)
{
    ifstream inFile;
    inFile.open("route_data.txt");
    if (inFile)
    {
        string name;
        while (inFile >> name)
        {
            cities[numCities].name = name;
            inFile >> cities[numCities].x;
            inFile >> cities[numCities].y;

            numCities++;
        }
        return true;
    }
    else
        return false;
}

double getDistance(City city1, City city2)
{
    return (sqrt(pow((city2.y - city1.y),2) + pow((city2.x - city1.x),2)));
}

double totalDistance(City cities[], int numCities)
{
    double distance = 0;

    for (int t = 0; t < numCities-1; t++)
        distance += getDistance(cities[t],cities[t+1]);

    return distance;
}

void greedyRouteImprove(City cities[], int numCities, const int MAX_CITIES)
{
    cout << "\n[----------------------]\n";
    cout << "\nImproved Route:\n";

    bool valid;

    City betterCities[MAX_CITIES];

    betterCities[0] = cities[0];
    double smallestDistance = 99;

    for (int a = 0; a < numCities; a++)//iterates through betterCities array
    {
        for (int b = 1; b < numCities; b++)//iterates through cities array
        {
             if (getDistance(betterCities[a], cities[b]) < smallestDistance)
            {
                valid = true;//determines if a city is valid based if it's already used
                for (int w = 0; w < numCities; w++)
                {
                    if (betterCities[w].name == cities[b].name)
                        valid = false;
                }
                if(valid)
                {
                    betterCities[a+1] = cities[b];
                    smallestDistance = getDistance(betterCities[a], cities[b]);
                }
            }
        }
        smallestDistance = 99;
    }

    for (int p = 0; p < numCities; p++)
        cout << betterCities[p].name << endl;

    cout << "\nDistance between cities: \n";
    for (int d = 0; d < numCities - 1; d++)
        cout << setw(10) << betterCities[d].name << setw(4) <<  " -> " << left << setw(8) << betterCities[d+1].name << ": "
             << setprecision(2) << fixed << setw(9) << getDistance(betterCities[d], betterCities[d+1]) << endl;

    cout << "\nTotal distance: " << totalDistance(betterCities, numCities) << endl << endl;

    cout << "\n\t\t >>> " << totalDistance(cities, numCities) / totalDistance(betterCities, numCities) << "x better <<<\n\n\n";
}

void hungarianMethodRouteImprove(City cities[], int numCities)
{
    double distancesArray[numCities][numCities];
    double cleanDistancesArray[numCities][numCities];

    for (int a = 0; a < numCities; a++)
        for (int b = 0; b < numCities; b++)
            distancesArray[a][b] = (getDistance(cities[a], cities[b]));

    for (int r = 0; r < numCities; r++)
    {
        for (int c = 0; c < numCities; c++)
        {
            if (distancesArray[r][c] == 0.00)
            {
                distancesArray[r][c] = -1.00;
            }
            //cout << distancesArray[r][c] << ", ";
        }
        //cout << endl;
    }

    std::copy(&distancesArray[0][0], &distancesArray[0][0]+numCities*numCities,&cleanDistancesArray[0][0]);//copies arrays to be used later

    const int BY = numCities;

    int round = 0;
    double totalDistance = 0;
    int pathArray [BY];

    while(round < BY)
    {
            cout << "Matrix: " << endl;
            for (int a = 0; a < BY; a++)
            {
                cout << setw(5);
                for (int b = 0; b < BY; b++)
                {
                    cout << setw(5) << distancesArray[a][b] <<  " | ";
                }
                cout << endl;
            }
            cout << endl;


        double minR = 99.0;
        double minC = 99.0;

        for (int r = 0; r < BY; r++) //row minimization
        {
            for (int c = 0; c < BY; c++)
                if (distancesArray[r][c] < minR && distancesArray[r][c] != -1)
                        minR = distancesArray[r][c];

            for (int iC = 0; iC < BY; iC++)
                if (distancesArray[r][iC] != -1)
                    distancesArray[r][iC] = (distancesArray[r][iC] - minR);
            minR = 99;
        }

            cout << "Row Reduced Matrix: " << endl;
            for (int a = 0; a < 5; a++)
            {
                cout << setw(5);
                for (int b = 0; b < BY; b++)
                    cout << setw(5) << distancesArray[a][b] << " | ";
                cout << endl;
            }
            cout << endl;

        for (int c = 0; c < BY; c++) //column minimization
        {
            for (int r = 0; r < BY; r++)
                if (distancesArray[r][c] < minC && distancesArray[r][c] != -1)
                        minC = distancesArray[r][c];

            for (int iR = 0; iR < BY; iR++)
                if (distancesArray[iR][c] != -1)
                    distancesArray[iR][c] = (distancesArray[iR][c] - minC);
            minC = 99;
        }

            cout << "Column Reduced Matrix: " << endl;
            for (int a = 0; a < BY; a++)
            {
                cout << setw(5);
                for (int b = 0; b < BY; b++)
                    cout << setw(5) << distancesArray[a][b] << " | ";
                cout << endl;
            }
            cout << endl;

        double penalty = 0;
        double penaltyArray[BY][BY];
        double minRow = 99.0;
        double minCol = 99.0;

        for (int x = 0; x < BY; x++)
            for (int y = 0; y < BY; y++)
                penaltyArray[y][x] = 0.00;

        for (int a = 0; a < BY; a++)//row
        {
            for (int b = 0; b < BY; b++)//column
            {
                 if (distancesArray[a][b] == 0)
                 {
                     distancesArray[a][b] = 100.0;
                     for (int c = 0; c < BY; c++)
                     {
                        if (distancesArray[a][c] < minRow && distancesArray[a][c] != -1)
                            minRow = distancesArray[a][c];
                     }
                    for (int r = 0; r < BY; r++)
                    {
                        if (distancesArray[r][b] < minCol && distancesArray[r][b] != -1)
                            minCol = distancesArray[r][b];
                    }
                    penaltyArray[a][b] = (minRow + minCol);
                    minRow = 99.0;
                    minCol = 99.0;
                    distancesArray[a][b] = 0;
                 }
            }
        }

        double greatestPenalty = 0.0;

        cout << "Penalty Matrix: " << endl;
        for (int a = 0; a < BY; a++)
        {
            cout << setw(5);
            for (int b = 0; b < BY; b++)
            {
                cout << setw(5) << penaltyArray[a][b] << " | ";
                if (penaltyArray[a][b] > greatestPenalty)
                    greatestPenalty = penaltyArray[a][b];
            }
            cout << endl;
        }

        int oneCount = 0;
        int scratchR = 0;
        int scratchC = 0;

        for (int a = 0; a < BY; a++)
            for (int b = 0; b < BY; b++)
                if (penaltyArray[a][b] == greatestPenalty)
                    while (oneCount < 1)
                    {
                        cout << "\t\t\tLocation: " << a << " -> " << b << endl;
                        pathArray[a] = b;
                        totalDistance += cleanDistancesArray[a][b];
                        scratchR = a;
                        scratchC = b;
                        oneCount++;
                    }
                    distancesArray[scratchC][scratchR] = -1;

        for (int r = 0; r < BY; r++)
            distancesArray[r][scratchC] = -1;
        for (int c = 0; c < BY; c++)
            distancesArray[scratchR][c] = -1;

        //cout << "\nReduced Matrix: " << endl;
        for (int a = 0; a < BY; a++)
        {
            for (int b = 0; b < BY; b++)
            {
                //cout << distancesArray[a][b] << " ";
                if (penaltyArray[a][b] > greatestPenalty)
                    greatestPenalty = penaltyArray[a][b];
            }
            //cout << endl;
        }
        round++;
    }

    int stop = 0;
    int city = 0;
    cout << "\nRoute: ";
    while (stop < BY -1)
    {
        //cout << city << " -> " << pathArray[city] << ", ";
        city = pathArray[city];
        stop++;
    }

    for (int i = 0; i < BY; i++)
        cout << i << "->" << pathArray[i] << ", ";
    cout << "\nTotal distance: " << totalDistance << endl;
}