/**
 * Estructuras de Datos
 * Práctica 9 - Orden topológico en digrafos (sin clonar el grafo)
 *
 * APELLIDOS :                         NOMBRE:
 */

package topoSort;

import dataStructures.dictionary.Dictionary;
import dataStructures.dictionary.HashDictionary;
import dataStructures.graph.DiGraph;
import dataStructures.list.ArrayList;
import dataStructures.list.List;
import dataStructures.set.HashSet;
import dataStructures.set.Set;
import dataStructures.tuple.Tuple2;

public class TopologicalSortingDicPar<V> {

    private List<Set<V>> topSort;
    private boolean hasCycle;

    /*
     * Agrega los predecesores de cada vértice.
     */
    private Dictionary<V, Integer> PendingPredecessors(DiGraph<V> graph) {
        Dictionary<V, Integer> pendingPredecessors = new HashDictionary<>();
        for(V v : graph.vertices()) {
            pendingPredecessors.insert(v, graph.inDegree(v));
        }
        return pendingPredecessors;
    }

    /**
     * Para los que tiene como predecesor a V, los decremente en 1 el grado de entrada.
     * @param graph Digrafo.
     * @param pendingPredecessors Predecesorse pendientes.
     */
    private void DecrementInDegree(DiGraph<V> graph, Dictionary<V, Integer> pendingPredecessors, V vertex) {
        for(V v : graph.vertices()) {
            if(pendingPredecessors.isDefinedAt(v) && graph.predecessors(v).isElem(vertex)) {
                pendingPredecessors.insert(
                        v,
                        pendingPredecessors.valueOf(v) - 1);
            }
        }
    }

    public TopologicalSortingDicPar(DiGraph<V> graph) {
        topSort = new ArrayList<>();
        // dictionary: vertex -> # of pending predecessors
        Dictionary<V, Integer> pendingPredecessors;
        Set<V> sources = new HashSet<>();
        // Añadir predecesores.
        pendingPredecessors = PendingPredecessors(graph);
        // Flags de estados.
        boolean finished = false;
        while(!finished && !hasCycle) {
            // Actualizar las fuentes.
            for(Tuple2<V, Integer> t : pendingPredecessors.keysValues()) {
                if(t._2() == 0) {
                    sources.insert(t._1());
                    // Eliminar del diccionario.
                    pendingPredecessors.delete(t._1());
                }
            }
            // Una vez eliminado los predecesores de la lista, si no hay más, esta es la última iteración.
            if(pendingPredecessors.isEmpty()) {
                finished = true;
            }
            // Si no hay fuentes pero aún no hemos terminado, es porque hay ciclo.
            if(sources.isEmpty()) {
                hasCycle = true;
            } else {
                // Añadir todas las fuentes al conjunto.
                topSort.append(sources);
                // Decrementar el grado de los vértices que tienen como predecesor a alguna fuente añadida.
                for(V v : sources)
                    DecrementInDegree(graph, pendingPredecessors, v);
                // Limpiar las fuentes.
                sources = new HashSet<>();
            }
        }
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public List<Set<V>> order() {
        return hasCycle ? null : topSort;
    }

}