/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package io.gameoftrades.student32.Opdracht_3;

import io.gameoftrades.debug.Debuggable;
import io.gameoftrades.debug.Debugger;
import io.gameoftrades.debug.DummyDebugger;
import io.gameoftrades.model.algoritme.StedenTourAlgoritme;
import io.gameoftrades.model.kaart.Kaart;
import io.gameoftrades.model.kaart.Pad;
import io.gameoftrades.model.kaart.Stad;
import io.gameoftrades.student32.Opdracht_2.SnelstePadAlgoritmeImpl;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * references: https://archive.fo/JYDMs ,
 * https://en.wikipedia.org/wiki/Travelling_salesman_problem,
 * https://en.wikipedia.org/wiki/2-opt
 *
 * @author Groep32 :D
 *
 * Beschrijving klasse: De klasse StedenTourAlgoritme zoekt de snelste route in
 * een wereld van stad naar stad. Elke stad mag maar een keer bezocht worden en
 * uiteindelijk moet de route met de laagste kosten opgeslagen worden. Dat is
 * dan de meeste efficiënte route voor de handelaar. WIj hebben gebruik gemaakt
 * van de algortime: 2-Opt. Per iteratie wordt er een nieuwe route gegenereerd
 * door de methode: TwoOptSwap(); De huidige route wordt dan qua kosten
 * vergeleken met de volgende kosten van de route en als die beter is dan de
 * vorige wordt die opgeslagen als best_distance. Zo gaat de algoritme door
 * totdat het geen betere route meer vindt.
 */
public class StedenTourAlgoritmeImpl implements StedenTourAlgoritme, Debuggable {

    private Debugger debug;
    private final ArrayList<Stad> newRoute = new ArrayList<>();
    private ArrayList<Stad> route;
    private final SnelstePadAlgoritmeImpl snelstePad = new SnelstePadAlgoritmeImpl();
    private Kaart kaart;
    private Pad pad = null;
    private double new_distance;
    private double best_distance;
    private int improve = 0;
    private int size;
    HashMap<String, Double> bekendPad = new HashMap<>();

    public StedenTourAlgoritmeImpl() {
        this.debug = new DummyDebugger();
        this.size = 0;
        this.best_distance = 0;
        this.new_distance = Double.MAX_VALUE;
    }

    /**
     * Methode berekend meest efficiënte route
     *
     * @param kaart
     * @param steden
     * @return
     */
    @Override
    public List<Stad> bereken(Kaart kaart, List<Stad> steden) {
        reset();
        this.kaart = kaart;
        route = new ArrayList<>(steden);
        size = route.size();

        for (int i = 0; i < size; i++) {
            newRoute.add(route.get(i));
        }
        best_distance = iterateSteden(route);
        improveRoute();
        debug.debugSteden(kaart, route);
        return route;
    }

    /**
     * Methode checkt nog 100 keer of er een betere/snellere route is dan de
     * huidige gevonden route, door met de methode 2OptSwap() de steden posities
     * te veranderen en daarvan de best distances te berekenen.
     */
    public void improveRoute() {
        whileLoop:
        while (improve < 100) {
            for (int i = 1; i < size - 1; i++) {
                for (int k = i + 1; k < size; k++) {
                    TwoOptSwap(i, k);
                    new_distance = iterateSteden(newRoute);
                    compareNewToBest(new_distance, best_distance);
                    improve++;
                    debug.debugSteden(kaart, newRoute);
                    newRoute.clear();
                    if (improve == 100) {
                        System.out.println("\nBeste Route: " + Arrays.toString(route.toArray()));
                        System.out.println(best_distance + " punten..");
                        break whileLoop;
                    }
                }
            }
        }
    }

    /**
     * Methode vergelijkt de huidige routekosten met de nieuw gevonden route
     * kosten en geeft de goedkoopste routekosten terug.
     *
     * @param newDistance
     * @param bestDistance
     */
    public void compareNewToBest(double newDistance, double bestDistance) {

        if (new_distance < best_distance) {
            improve = 0;
            route.clear();
            for (int j = 0; j < size; j++) {
                route.add(j, newRoute.get(j));
            }

            System.out.println("New distance: " + new_distance);
            System.out.println(Arrays.toString(route.toArray()));
            best_distance = new_distance;
        }
    }

    /**
     * Methode loopt door alle steden en telt de kosten van stad naar stad op.
     * Ook worden de routes tussen de steden opgeslagen in een Hashmap, hierdoor
     * kunnen we met behulp van de klasse Node.java de afstanden cachen.
     * Hierdoor hoeft de algoritme bepaalde routes niet opnieuw te berekenen en
     * zal dit wat tijd besparen.
     *
     * @param listRoute
     * @return
     */
    public double iterateSteden(ArrayList<Stad> listRoute) {
        double distanceTotaal = 0;
        double distance = 0;
        for (int i = 0; i < listRoute.size(); i++) {
            Stad huidig = listRoute.get(i);
            Stad eind = listRoute.get(i + 1);
            CacheKosten n = new CacheKosten(huidig.getCoordinaat(), eind.getCoordinaat());

            if (bekendPad.containsKey(n.toString())) {
                for (Map.Entry<String, Double> entry : bekendPad.entrySet()) {
                    if (entry.getKey().equals(n.toString())) {
                        distanceTotaal += entry.getValue();
                        break;
                    }
                }
            } else {
                pad = snelstePad.bereken(kaart, huidig.getCoordinaat(), eind.getCoordinaat());
                distanceTotaal += pad.getTotaleTijd();
                distance = pad.getTotaleTijd();
                bekendPad.put(n.toString(), distance);
            }
            if (i == listRoute.size() - 2) {
                break;
            }
        }
        return distanceTotaal;
    }

    /**
     * Methode swapt op verschillende manieren de steden in een route List, om
     * verschillende route mogelijkheden te hebben.
     *
     * @param i
     * @param k
     */
    private void TwoOptSwap(int i, int k) {

        int size = route.size();

        // 1. Take route[0] to route[i-1] and add them in order to new_route
        for (int c = 0; c <= i - 1; ++c) {
            newRoute.add(c, route.get(c));
        }

        // 2. Take route[i] to route[k] and add them in reverse order to new_route
        int dec = 0;
        for (int c = i; c <= k; ++c) {
            newRoute.add(c, route.get(k - dec));
            dec++;
        }

        // 3. Take route k+1 to end and add them in order to new_route
        for (int c = k + 1; c < size; ++c) {
            newRoute.add(c, route.get(c));
        }
    }

    /**
     * Methode reset alle variabelen.
     */
    public void reset() {
        size = 0;
        best_distance = 0;
        new_distance = 0;
        improve = 0;
        pad = null;
    }

    /**
     * Toont algoritme naam bij keuzemenu
     *
     * @return
     */
    @Override
    public String toString() {
        return "Stedentour Algoritme  :D";
    }

    /**
     * Methode uit Debuggable interface
     *
     * @param debugger
     */
    @Override
    public void setDebugger(Debugger d) {
        this.debug = d;
    }
}