import it.uniupo.algoTools.MinHeap;
import it.uniupo.graphLib.DirectedGraph;
import it.uniupo.graphLib.Edge;
import it.uniupo.graphLib.GraphInterface;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Voli {

    private DirectedGraph myCollegamenti;
    private boolean[] founded;


    public Voli(DirectedGraph collegamenti) {
        this.myCollegamenti = collegamenti;
        this.founded = new boolean[myCollegamenti.getOrder()];
    }

    private int[] dijkstra(int sorg) {
        int[] distance = new int[myCollegamenti.getOrder()];
        Arrays.fill(distance, -1);

        founded[sorg] = true;
        distance[sorg] = 0;
        MinHeap<Edge, Integer> heap = new MinHeap<Edge, Integer>();

        for (Edge e : myCollegamenti.getOutEdges(sorg)) {
            heap.add(e, distance[sorg] + e.getWeight());
        }

        while (!heap.isEmpty()) {
            Edge heapReturnedEdge = heap.extractMin(); //arco (u,w), u alla prima iterazione è uguale a sorg
            int nodeU = heapReturnedEdge.getTail();
            int nodeW = heapReturnedEdge.getHead();
            if (!founded[nodeW]) {
                founded[nodeW] = true;
                distance[nodeW] = distance[nodeU] + heapReturnedEdge.getWeight();
                for (Edge e : myCollegamenti.getOutEdges(nodeW)) {
                    heap.add(e, distance[nodeW] + e.getWeight());
                }
            }
        }
        return distance;
    }

    private boolean dijkstraTrattaVeloce(int sorg, int dest, ArrayList<Edge> returnArray) {
        int[] distance = new int[myCollegamenti.getOrder()];
        //ArrayList<Edge> returnArray = new ArrayList<>();
        Arrays.fill(distance, -1);

        founded[sorg] = true;
        distance[sorg] = 0;
        MinHeap<Edge, Integer> heap = new MinHeap<Edge, Integer>();

        for (Edge e : myCollegamenti.getOutEdges(sorg)) {
            heap.add(e, distance[sorg] + e.getWeight());
        }

        while (!heap.isEmpty()) {
            Edge heapReturnedEdge = heap.extractMin(); //arco (u,w), u alla prima iterazione è uguale a sorg
            int nodeU = heapReturnedEdge.getTail();
            int nodeW = heapReturnedEdge.getHead();
            if (!returnArray.isEmpty() && nodeU == returnArray.getLast().getTail()) {
                returnArray.removeLast();
            }
            if (!founded[nodeW]) {
                returnArray.add(heapReturnedEdge);
                if (nodeW == dest) {
                    return true;
                }
                founded[nodeW] = true;
                distance[nodeW] = distance[nodeU] + heapReturnedEdge.getWeight();
                for (Edge e : myCollegamenti.getOutEdges(nodeW)) {
                    heap.add(e, distance[nodeW] + e.getWeight());
                }
            }
        }
        return false;
    }

    private int[] bfs(int sorg) {
        if (sorg >= this.myCollegamenti.getOrder()) {
            throw new IllegalArgumentException("Sorgente errata");
        }
        founded[sorg] = true;
        int[] bfsDistance = new int[myCollegamenti.getOrder()];
        Arrays.fill(bfsDistance, -1);
        bfsDistance[sorg] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(sorg);
        while (!q.isEmpty()) {
            int u = q.remove();
            for (int v : myCollegamenti.getNeighbors(u)) {
                if (!founded[v]) {
                    founded[v] = true;
                    q.add(v);
                    bfsDistance[v] = bfsDistance[u] + 1;
                }
            }
        }
        return bfsDistance;
    }

    private int[] bfsTime(int sorg) {
        if (sorg >= this.myCollegamenti.getOrder()) {
            throw new IllegalArgumentException("Sorgente errata");
        }
        founded[sorg] = true;
        int[] bfsDistanceWeigth = new int[myCollegamenti.getOrder()];
        Arrays.fill(bfsDistanceWeigth, -1);
        bfsDistanceWeigth[sorg] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(sorg);
        while (!q.isEmpty()) {
            int u = q.remove();
            for (Edge uv : myCollegamenti.getOutEdges(u)) {
                int v = uv.getHead();
                if (!founded[v]) {
                    founded[v] = true;
                    q.add(v);
                    bfsDistanceWeigth[v] = bfsDistanceWeigth[u] + uv.getWeight();
                }
            }
        }
        return bfsDistanceWeigth;
    }

    private ArrayList<Integer> bfsMinScali(int sorg, int dest) {
        if (sorg >= this.myCollegamenti.getOrder()) {
            throw new IllegalArgumentException("Sorgente errata");
        }
        ArrayList<Integer> returnArray = new ArrayList<>();
        founded[sorg] = true;
        Queue<Integer> q = new LinkedList<>();
        q.add(sorg);
        while (!q.isEmpty()) {
            int u = q.remove();
            if (u != sorg) {
                returnArray.add(u);
            }
            boolean noNewNodes = true;
            for (int v : myCollegamenti.getNeighbors(u)) {
                if (!founded[v]) {
                    founded[v] = true;
                    noNewNodes = false;
                    q.add(v);
                    //returnArray.add(v);
                }
                if (v == dest) {
                    return returnArray;
                }
            }
            if (!returnArray.isEmpty() && noNewNodes) {
                returnArray.removeLast();
            }
        }
        return null;
    }

    private void checkAirport(int partenza, int destinazione) {
        if (partenza < 0 || destinazione < 0 || partenza >= myCollegamenti.getOrder() || destinazione >= myCollegamenti.getOrder()) {
            throw new IllegalArgumentException("Aeroporto di partenza o di destinazione non esite");
        }
    }

    public int tempoMinimo(int partenza, int destinazione) {
        checkAirport(partenza, destinazione);
        Arrays.fill(founded, false);
        int[] d = dijkstra(partenza);
        return d[destinazione];
    }

    public int scali(int partenza, int destinazione) {
        checkAirport(partenza, destinazione);
        if (partenza == destinazione) return 0;
        int[] res = bfs(partenza);

        if (res[destinazione] != -1) return --res[destinazione];
        else return res[destinazione];
    }

    public int tempo(int partenza, int destinazione) {
        checkAirport(partenza, destinazione);
        Arrays.fill(founded, false);
        return bfsTime(partenza)[destinazione];
    }

    public ArrayList<Edge> trattaVeloce(int partenza, int destinazione) {
        checkAirport(partenza, destinazione);
        Arrays.fill(founded, false);
        ArrayList<Edge> resultArray = new ArrayList<>();
        return dijkstraTrattaVeloce(partenza, destinazione, resultArray) ? resultArray : null;
    }

    public ArrayList<Integer> elencoScali(int partenza, int destinazione) {
        checkAirport(partenza, destinazione);
        if (partenza == destinazione) return new ArrayList<>(); //Serve solo per ritornare un ArrayList vuota
        Arrays.fill(founded, false);
        return bfsMinScali(partenza, destinazione);
    }
}