/*
 * 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 lapr.project.utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import lapr.project.model.Journey;
import lapr.project.model.Park;
import lapr.project.model.Point;
import lapr.project.model.TouristicPoint;
import lapr.project.model.User;

/**
 *
 * @author Vasco_Rodrigues
 */
public class GraphAlgorithms extends GraphHandler {

    public static final boolean ASCENDING = true;
    public static final boolean DESCENDING = false;

    public GraphAlgorithms(User user) {
        super(user);
    }

    public LinkedList<Point> getShortestPath(Point orig, Point dest, Attribute att) {

        int size = graph.numVertices();

        Point[] points = new Point[size];
        Iterator<Point> it = graph.vertices().iterator();
        for (int i = 0; i < size; i++) {
            points[i] = it.next();
        }

        LinkedList<Point> path = new LinkedList<>();
        for (Integer i : getSmallestRoute(orig, dest, att, points).track) {
            path.add(points[i]);
        }
        return path;
    }

    private Track getSmallestRoute(Point vOrig, Point vDest, Attribute att, Point[] points) {

        int size = graph.numVertices();

        boolean[] visited = new boolean[size];

        int[] pathKeys = new int[size];
        double[] dist = new double[size];

        for (int i = 0; i < size; i++) {
            dist[i] = Double.MAX_VALUE;
            pathKeys[i] = -1;
        }
        int ogIndex = indexOf(vOrig, points);
        dist[ogIndex] = 0;
        shortestRoute(ogIndex, points, visited, pathKeys, dist, vDest, att);
        Track sp = new Track();
        buildPath(vOrig, vDest, points, pathKeys, sp);
        sp = revPath(sp);
        sp.weight = dist[sp.getLastVert()];
        return sp;
    }

    /**
     * Computes shortest-path distance from a source vertex to all reachable
     * vertices of a graph g with nonnegative edge weights This implementation
     * uses Dijkstra's algorithm
     *
     * @param vOrig Vertex that will be the source of the path
     * @param vertices
     * @param visited set of discovered vertices
     * @param pathKeys minimum path vertices keys
     * @param dist minimum distances
     * @param verticeParagem
     */
    private void shortestRoute(int indexOrigin, Point[] vertices,
            boolean[] visited, int[] pathKeys, double[] dist, Point verticeParagem, Attribute att) {

        visited[indexOrigin] = true;

        if (vertices[indexOrigin].equals(verticeParagem)) {
            return;
        }

        int indexVert;
        for (Edge<Point, Path> edge : graph.outgoingEdges(vertices[indexOrigin])) {

            indexVert = indexOf(edge.getVDest(), vertices);
            Double addedWeight = 0.0;
            if (!visited[indexVert]) {
                if (att.equals(ENERGY)) {
                    //addedWeight = Journey.calculateEnergyBetweenTwoLocations(edge.getVOrig().getLocation(), edge.getVDest().getLocation(), user, user.getAverageSpeed(), BICYCLE, GraphHandler.PATH);
                } else {
                    addedWeight = getAttribute(edge, att);
                }
                if (addedWeight != null && addedWeight >= 0) {
                    double weight = dist[indexOrigin] + addedWeight;
                    if (dist[indexVert] > weight) {
                        dist[indexVert] = weight;
                        pathKeys[indexVert] = indexOrigin;
                    }
                }
            }
        }

        indexVert = getLowestDist(dist, visited);

        if (indexVert == -1) {
            return;
        }
        shortestRoute(indexVert, vertices, visited, pathKeys, dist, verticeParagem, att);
    }

    private static <V, E> int getLowestDist(double[] distancias, boolean[] visited) {
        double lowest = Double.MAX_VALUE;
        int index = -1;
        for (int i = 0; i < distancias.length; i++) {
            if (distancias[i] < lowest) {
                if (!visited[i]) {
                    lowest = distancias[i];
                    index = i;
                }
            }
        }
        return index;
    }

    private static <V, E> int indexOf(V vertice, V[] vertices) {
        for (int i = 0; i < vertices.length; i++) {
            if (vertices[i].equals(vertice)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Reverses the path
     *
     * @param path stack with path
     */
    private Track revPath(Track path) {

        Track pathrev = new Track();
        int size = path.track.size();
        for (int i = size - 1; i >= 0; i--) {
            pathrev.track.add(path.track.get(i));
        }

        return pathrev;
    }

    /**
     * Extracts from pathKeys the minimum path between voInf and vdInf The path
     * is constructed from the end to the beginning
     *
     * @param vOrig information of the Vertex origin
     * @param vDest information of the Vertex destination
     * @param verts
     * @param pathKeys minimum path vertices keys
     * @param path stack with the minimum path (correct order)
     */
    private static void buildPath(Point vOrig, Point vDest, Point[] verts, int[] pathKeys, Track path) {
        int index = indexOf(vDest, verts);
        int indexOG = indexOf(vOrig, verts);
        if (indexOG == -1 || index == -1) {
            return;
        }

        do {
            path.track.add(index);
            index = pathKeys[index];
        } while (index != -1);

    }
//-----------------------------------------------

    public List<LinkedList<Point>> shortestRouteWithCertainPoints(Point origin, Point dest, int minPoints, Set<Point> mustGoes, Attribute att, boolean ordering) {

        if (!graph.validVertex(origin) || !graph.validVertex(dest)) {
            return null;
        }

        if (!(origin instanceof Park) || !(dest instanceof Park)) {
            return null;
        }

        int size = graph.numVertices();
        Point[] points = new Point[size];
        Iterator<Point> it = graph.vertices().iterator();
        for (int i = 0; i < size; i++) {
            points[i] = it.next();
        }

        LinkedList<Track> allTracks = new LinkedList<>();
        Set<Track> finishedTracks = new HashSet<>();
        allTracks.add(new Track(indexOf(origin, points)));

        Set<Integer> mgInteger = new HashSet<>();
        for (Point p : mustGoes) {
            mgInteger.add(indexOf(p, points));
        }

        List<Track> tracks = new ArrayList<>();

        //This variable might be initialized by parameter in the future
        final int defautlNumberOfResults = 5;

        recursivePathFinder(tracks, defautlNumberOfResults, allTracks, dest, minPoints, mgInteger, finishedTracks, att, points);

        int mult;
        int index;
        if (ordering) {
            mult = 1;
            index = 0;
        } else {
            mult = -1;
            index = tracks.size() - 1;
        }

        List<LinkedList<Point>> orderedResult = new ArrayList<>();

        LinkedList<Point> path;
        for (int j = 0; j < tracks.size(); j++) {
            path = new LinkedList<>();
            Track track = tracks.get(index);

            for (Integer i : track.track) {
                path.add(points[i]);
            }
            orderedResult.add(path);
            index += mult;
        }

        return orderedResult;
    }

    private void recursivePathFinder(List<Track> result, int numResults, LinkedList<Track> allTracks, Point vertFim, int minPoints, Set<Integer> mustGoes, Set<Track> finished, Attribute att, Point[] vertices) {
        if (allTracks.isEmpty()) {
            return;
        }
        Collections.sort(allTracks);
        Track track = allTracks.remove();
        if (finished.contains(track)) {
            result.add(track);
            if (result.size() == numResults) {
                return;
            }
        } else {
            for (Edge<Point, Path> edge : graph.getVertex(track.getLastVert()).getAllOutEdges()) {
                if (track.validateEdge(edge, vertices)) {
                    Track sec = new Track(track);
                    sec.AddEdge(edge, att, vertices);
                    if (sec.track.containsAll(mustGoes) && sec.numPoints >= minPoints) {
                        sec.track.remove(sec.track.size() - 1);
                        Track temp = getSmallestRoute(edge.getVDest(), vertFim, att, vertices);
                        sec.addAll(temp.track, temp.weight, vertices);
                        finished.add(sec);
                    }
                    allTracks.add(sec);
                }
            }
        }
        recursivePathFinder(result, numResults, allTracks, vertFim, minPoints, mustGoes, finished, att, vertices);
    }

    /**
     * Inner class Track
     *
     */
    private class Track implements Comparable<Track> {

        private List<Integer> track;
        private double weight;
        private int numPoints;

        public Track() {
            weight = 0;
            numPoints = 0;
            track = new ArrayList<>();

        }

        public Track(Integer vertInicial) {
            weight = 0;
            numPoints = 0;
            track = new ArrayList<>();
            track.add(vertInicial);
        }

        /**
         * Construtor da classe caminho
         *
         * @param caminho_inicial
         * @param weight
         */
        private Track(Track that) {
            this.track = new ArrayList<>(that.track);
            this.weight = that.weight;
            this.numPoints = that.numPoints;
        }

        /**
         * Construtor da classe caminho
         *
         * @param caminho_inicial
         * @param weight
         */
        private Track(LinkedList<Integer> caminho, double weight) {
            this.track = new ArrayList<>(caminho);
            this.weight = weight;
        }

        public Integer getLastVert() {
            return track.get(track.size() - 1);
        }

        public boolean addAll(List<Integer> list, double weight, Point[] vertices) {
            this.weight += weight;
            for (Integer p : list) {
                if (vertices[p] instanceof TouristicPoint && !track.contains(p)) {
                    numPoints++;
                }
                track.add(p);
            }
            return true;
        }

        public boolean AddEdge(Edge<Point, Path> edge, Attribute att, Point[] vertices) {
            if (validateEdge(edge, vertices)) {
                double toAdd = getAttribute(edge, att);
                if (toAdd >= 0) {
                    Point p = (edge.getVDest());
                    weight += toAdd;
                    if (p instanceof TouristicPoint && !track.contains(indexOf(p, vertices))) {
                        numPoints++;
                    }
                    track.add(indexOf(p, vertices));
                    return true;
                }
                return false;
            }
            return false;
        }

        /**
         * Verifica se é possível adicionar um vértice à lista, as condições de
         * adição são: Um vértice V não pode ocupar duas posicões consecutivas V
         * != penúltimo vértice && último vértice!= penúltimo vértice ou seja, é
         * possível um caminho ser ABA, mas nunca AAB ou ABAB
         *
         * @param edge
         * @return
         */
        public boolean validateEdge(Edge<Point, Path> edge, Point[] vertices) {
            int size = track.size();
            if (size > 1) {
                if (vertices[track.get(size - 1)].equals(edge.getVDest())) {
                    return false;
                }
            }
            if (size > 2) {
                if (track.get(size - 1).equals(track.get(size - 3)) && vertices[track.get(size - 2)].equals(edge.getVDest())) {
                    return false;
                }
            }
            if (size > 4) {
                int index = track.indexOf(track.get(size - 1));
                if (index == size - 1) {
                    return true;
                }

                return !vertices[track.get(index + 1)].equals(edge.getVDest());
            }
            return true;
        }

        @Override
        public int compareTo(Track that) {
            if (this.weight > that.weight) {
                return 1;
            }
            if (this.weight < that.weight) {
                return -1;
            }
            return 0;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (!(obj instanceof Track)) {
                return false;
            }
            Track that = (Track) obj;
            if (Math.abs(this.weight - that.weight) > 0.0001) {
                return false;
            }
            return this.track.equals(that.track);
        }
    }
}