//  resource.h

//{{NO_DEPENDENCIES}}
// Microsoft Visual C++ generated include file.
// Used by TSP_Dialog.rc

#define IDD_TSP_DIALOG                         101
#define IDC_INPUT                               1001
#define IDC_OUTPUT                              1002

// Next default values for new objects
//{{AFX_PREFIXED}}

#ifdef APSTUDIO_INVOKED
#ifndef APSTUDIO_READONLY_SYMBOLS
#define _APS_NEXT_RESOURCE_VALUE        102
#define _APS_NEXT_COMMAND_VALUE         40001
#define _APS_NEXT_CONTROL_VALUE         1003
#define _APS_NEXT_SYMED_VALUE           101
#endif
#endif


// TSP_Dialog RC Source, Version 1.0

#include "resource.h"

IDI_INPUT                             ICON  "TSP.ico"
IDI_OUTPUT                            ICON  "TSP.ico"

IDD_TSP_DIALOG DIALOGEX 0, 0, 329, 235
STYLE DS_MODALFRAME | WS_POPUP | WS_VISIBLE | WS_CAPTION
CAPTION "Traveling Salesman Dialog"
FONT 8, "MS Sans Serif"
BEGIN
    EDITTEXT "", IDC_INPUT, WS_TABSTOP | WS_BORDER | ES_CENTER, 20, 10, 280, 22
    PUSHBUTTON "&Berechnen", IDOK, 100, 180, 50, 14
    PUSHBUTTON "&Abbrechen", IDCANCEL, 150, 180, 50, 14
    EDITTEXT "", IDC_OUTPUT, ES_MULTILINE | WS_VSCROLL | WS_HSCROLL | ES_READONLY | WS_TABSTOP, 20, 40, 290, 120
END

// Next default values for new objects
//{{NO_DEPENDENCIES}}
// Microsoft Visual C++ generated include file.
// Used by TSP_Dialog.rc

// End


// --- TSP_Dialog.cpp - Win32 Traveling Salesman Dialog GUI ---
#include <windows.h>
#include <vector>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include "resource.h"

// --- Datenstruktur: Stadt ====> City Struct ====>---
struct City {
    double x;
    double y;
};

// --- Hilfsfunktion: Abstand zwischen zwei St&auml;dten (Python translate_distance) ---
double CalculateDistance(const City& city1, const City& city2) {
    return std::sqrt(std::pow(city1.x - city2.x, 2) + 
                     std::pow(city1.y - city2.y, 2));
}

// --- Haupt-Algorithmen-Funktion: Traveling Salesman Solver (Brute Force) ---
struct TSPResult {
    std::vector<City> route;
    double distance;
};

TSPResult SolveTravelingSalesman(const std::vector<City>& cities) {
    if (cities.size() < 2) {
        return { {}, -1.0 }; // Zu wenig St&auml;dte, Fehler
    }

    size_t n = cities.size();
    
    // Permutationen-Indizes initialisieren (0 bis N-1)
    std::vector<size_t> p(n);
    for(size_t i=0; i<n; ++i) p[i] = i;

    double shortest_dist = 1e20; // Unendlich als Startwert
    TSPResult best_result;
    best_result.route.reserve(n);
    
    // Permutations-Loop: Iteriert &uuml;ber alle N! Kombinationen
    for (size_t perm_id = 0; ; perm_id++) {
        double current_dist = 0.0;
        
        // Pfad berechnen: c1 -> c2 -> ... -> cN
        for (size_t i = 0; i < n - 1; ++i) {
            const City& c1 = cities[p[i]];
            const City& c2 = cities[p[i + 1]];
            current_dist += CalculateDistance(c1, c2);
        }
        // R&uuml;ckkehr zum Startpunkt (cN -> c0)
        current_dist += CalculateDistance(cities[p[n - 1]], cities[p[0]]);

        if (current_dist < shortest_dist) {
            shortest_dist = current_dist;
            best_result.distance = shortest_dist;
            
            // Indizes in City-Objekte konvertieren f&uuml;r Ausgabe
            best_result.route.resize(n);
            for (size_t i = 0; i < n; ++i) {
                best_result.route[i] = cities[p[i]];
            }
        }

        // Loop abbrechen wenn keine weiteren Permutationen m&ouml;glich sind
        if (!std::next_permutation(p.begin(), p.end())) {
            break; 
        }
    }

    return best_result;
}

// --- Dialog-Prozedur (Message Handler f&uuml;r Dialog-Fenster) ---
LRESULT CALLBACK DlgProc(HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam) {
    switch (msg) {
        case WM_INITDIALOG: {
            // Eingabefeld aktivieren f&uuml;r Bearbeitung
            SendMessage(hwnd, WM_SETFOCUS, 0, MAKELPARAM(IDC_INPUT));

            return TRUE; 
        }
        
        case WM_COMMAND: {
        
            INT_PTR iResult = -1;
            
            switch (LOWORD(wParam)) {
                case IDOK: // Berechnen Button wurde geklickt
                {
                    // Input holen
                    char buffer[512];
                    if (!GetWindowText(GetDlgItem(hwnd, IDC_INPUT), buffer, sizeof(buffer))) break;
                    std::string inputStr(buffer);

                    // Parsing der Koordinaten (Format: x,y;x,y;x,y)
                    std::vector<City> cities;
                    std::stringstream ss(inputStr);
                    std::string line;
                    
                    while (std::getline(ss, line, ';')) {
                        size_t comma = line.find(',');
                        if (comma == std::string::npos) continue;

                        try {
                            double x = 0.0, y = 0.0;
                            std::size_t endX; 
                            
                            // Trimmen: Entferne Leerzeichen um x und y herum
                            std::string sX = line.substr(0, comma);
                            while(sX.size() > 0 && (sX.back() == ' ' || sX.back() == '\t' || sX.back() == '\r' || sX.back() == '\n')) {
                                sX.pop_back();
                            }
                            
                            std::string sY = line.substr(comma + 1);
                            while(sY.size() > 0 && (sY.front() == ' ' || sY.front() == '\t' || sY.front() == '\r')) {
                                sY.erase(0, 1);
                            }

                            x = std::stod(sX, &endX);
                            y = std::stod(sY);
                            
                            cities.push_back({x, y});
                        } catch (...) {
                            // Fehlerhafte Zahl ignorieren
                            continue;
                        }
                    }

                    if (cities.empty()) {
                        MessageBoxA(hwnd, "Keine g&uuml;ltige Daten im Eingabefeld.", 
                                   "Fehler", MB_OK | MB_ICONWARNING);
                        break;
                    }

                    // Berechnung ausf&uuml;hren
                    TSPResult res = SolveTravelingSalesman(cities);

                    // Ergebnis-Text formatieren (mit stringstream f&uuml;r saubere Ausgabe)
                    std::ostringstream out;
                    
                    if (!res.route.empty()) {
                        out << "=== Beste Route ===\n";
                        for (size_t i = 0; i < res.route.size(); ++i) {
                            out << "(" << std::fixed << std::setprecision(1) 
                                << res.route[i].x << ", " 
                                << res.route[i].y << ")";
                            
                            if (i < res.route.size() - 1) {
                                out << "  →  "; // Pfeil statt "->'
                            }
                        }

                        out << "\n\n=== K&uuml;rzeste Gesamtstrecke ===\n"
                             << std::fixed << std::setprecision(2)
                             << res.distance << " (Einheiten)\n";
                        
                        // Hinweis: Start- und Endpunkt sind gleich
                        const City& start = res.route[0];
                        const City& end = res.route.back();
                        out << "\nStart: (" << start.x << ", " << start.y << ") -> ";
                        out << "Ende: (" << end.x << ", " << end.y << ")\n";
                    } else {
                        out << "Keine Route gefunden.";
                    }

                    // Text ins Ausgabe-Feld setzen
                    SetWindowText(GetDlgItem(hwnd, IDC_OUTPUT), out.str().c_str());
                    
                    // Input leeren
                    SetWindowText(GetDlgItem(hwnd, IDC_INPUT), "");
                    break;
                }
                
                case IDCANCEL: // Ende/Exit Button
                    EndDialog(hwnd, IDOK);
                    return TRUE;
            }
            
            return TRUE;
        }
        
        case WM_CLOSE: {
            EndDialog(hwnd, IDOK);
            return TRUE;
        }
        
     
    }
}

// --- Hauptfunktion f&uuml;r die Registrierung und Start ====>---
int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow) {
    UNREFERENCED_PARAMETER(hPrevInstance);
    UNREFERENCED_PARAMETER(lpCmdLine);

    DialogBox(NULL, MAKEINTRESOURCE(IDD_TSP_DIALOG), NULL, DlgProc);

    return 0;
}