/**
 * Interfaccia che rappresenta un arco pesato.
 */
export interface Edge<E> {
    node: E;
    weight: number;
}

/**
 * Implementazione di un grafo generico pesato e non orientato.
 * @typeParam E - Tipo dei vertici
 */
export class NotOrientedGraph<E> {
    private adjacencyList: Record<string, Edge<E>[]>;

    constructor() {
        this.adjacencyList = {};
    }

    /**
     * Aggiunge un vertice al grafo.
     * Se il vertice è già presente, non fa nulla.
     * @param vertex - Il vertice da aggiungere
     */
    aggiungiVertice(vertex: E): void {
        const key = String(vertex);
        if (!this.adjacencyList[key]) {
            this.adjacencyList[key] = [];
        }
    }

    /**
     * Aggiunge un arco pesato non orientato tra due vertici.
     * Se i vertici non esistono, vengono creati automaticamente.
     * @param vertex1 - Primo vertice
     * @param vertex2 - Secondo vertice
     * @param weight - Peso dell'arco
     */
    aggiungiArco(vertex1: E, vertex2: E, weight: number): void {
        const v1 = String(vertex1);
        const v2 = String(vertex2);

        if (!this.adjacencyList[v1]) {
            this.aggiungiVertice(vertex1);
        }
        if (!this.adjacencyList[v2]) {
            this.aggiungiVertice(vertex2);
        }

        this.adjacencyList[v1].push({
            node: vertex2, weight
        });
        this.adjacencyList[v2].push({
            node: vertex1, weight
        });
    }

    /**
     * Rimuove un arco tra due vertici, se esiste.
     * @param vertex1 - Primo vertice
     * @param vertex2 - Secondo vertice
     */
    rimuoviArco(vertex1: E, vertex2: E): void {
        const v1 = String(vertex1);
        const v2 = String(vertex2);

        this.adjacencyList[v1] = this.adjacencyList[v1]?.filter(edge => edge.node !== vertex2) || [];
        this.adjacencyList[v2] = this.adjacencyList[v2]?.filter(edge => edge.node !== vertex1) || [];
    }

    /**
     * Rimuove un vertice e tutti i relativi archi.
     * @param vertex - Il vertice da rimuovere
     */
    rimuoviVertice(vertex: E): void {
        const v = String(vertex);
        while (this.adjacencyList[v]?.length) {
            const adjacentEdge = this.adjacencyList[v].pop() as Edge<E>;
            this.rimuoviArco(vertex, adjacentEdge.node);
        }
        delete this.adjacencyList[v];
    }

    /**
     * Visualizza il grafo in console.
     */
    display(): void {
        for (const vertex in this.adjacencyList) {
            const edges = this.adjacencyList[vertex];
            const rappresentazione = edges.length > 0
                ? edges.map(e => `${e.node}(${e.weight})`).join(", ")
                : "NULL";
            console.log(`${vertex} -> ${rappresentazione}`);
        }
    }

    /**
     * Verifica se il grafo è connesso.
     * @returns true se il grafo è connesso, false altrimenti
     */
    verificaConnesso(): boolean {
        const visitati = new Set<string>();
        const vertices = Object.keys(this.adjacencyList);

        if (vertices.length === 0) return true; // grafo vuoto = connesso

        const dfs = (vertex: string) => {
            visitati.add(vertex);
            for (const edge of this.adjacencyList[vertex]) {
                const key = String(edge.node);
                if (!visitati.has(key)) {
                    dfs(key);
                }
            }
        };

        dfs(vertices[0]);

        return vertices.length === visitati.size;
    }

    /**
     * Visita in ampiezza (BFS) a partire da un vertice.
     * @param start - Vertice di partenza
     * @returns Lista dei vertici visitati in ordine BFS
     */
    visitaAmpiezza(start: E): E[] {
        const result: E[] = [];
        const visitati = new Set<string>();
        const queue: E[] = [start];

        visitati.add(String(start));

        while (queue.length > 0) {
            const nodo = queue.shift() as E;
            result.push(nodo);

            for (const edge of this.adjacencyList[String(nodo)]) {
                const key = String(edge.node);
                if (!visitati.has(key)) {
                    visitati.add(key);
                    queue.push(edge.node);
                }
            }
        }

        return result;
    }

    /**
     * Visita in profondità (DFS) a partire da un vertice.
     * @param start - Vertice di partenza
     * @returns Lista dei vertici visitati in ordine DFS
     */
    visitaProfondita(start: E): E[] {
        const result: E[] = [];
        const visitati = new Set<string>();

        const dfs = (vertex: E) => {
            visitati.add(String(vertex));
            result.push(vertex);

            for (const edge of this.adjacencyList[String(vertex)]) {
                if (!visitati.has(String(edge.node))) {
                    dfs(edge.node);
                }
            }
        };

        dfs(start);
        return result;
    }

    /**
     * Restituisce tutti i vertici del grafo
     * @returns tutti i vertici del grafo
     */
    getVertices(): E[] {
        const verticesSet = new Set<E>();
        for (const key in this.adjacencyList) {
            verticesSet.add(key as unknown as E);
            for (const edge of this.adjacencyList[key]) {
                verticesSet.add(edge.node);
            }
        }
        return Array.from(verticesSet);
    }
    
    /**
     * Restituisce tutti gli archi senza duplicati
     * @returns tutti gli archi senza duplicati
     */
    getEdges(): { from: E; to: E; weight: number }[] {
        const edges: { from: E; to: E; weight: number }[] = [];
        const visited = new Set<string>();

        for (const key in this.adjacencyList) {
            for (const edge of this.adjacencyList[key]) {
                // Crea un id unico indipendente dall'ordine dei nodi
                const id = [String(key), String(edge.node)].sort().join('-');
                if (!visited.has(id)) {
                    edges.push({ from: key as unknown as E, to: edge.node, weight: edge.weight });
                    visited.add(id);
                }
            }
        }

        return edges;
    }

    /**
     * Fornisce la lista di adiacenza dei nodi del grafo 
     * @returns lista di adiacenza
     */
    getAdjacencyList(){
      return this.adjacencyList;
    }
}

// =============================
// Test della struttura dati
// =============================

const graph = new NotOrientedGraph<string>();

graph.aggiungiVertice("A");
graph.aggiungiVertice("B");
graph.aggiungiVertice("C");

graph.aggiungiArco("A", "B", 5);
graph.aggiungiArco("A", "C", 2);
graph.aggiungiArco("B", "C", 3);

graph.display();

console.log("\nGrafo connesso:", graph.verificaConnesso());
console.log("Visita in ampiezza da A:", graph.visitaAmpiezza("A"));
console.log("Visita in profondità da A:", graph.visitaProfondita("A"));

graph.rimuoviArco("A", "C");
console.log("\nDopo aver rimosso l'arco A-C:");
graph.display();

graph.rimuoviVertice("B");
console.log("\nDopo aver rimosso il vertice B:");
graph.display();

console.log("\nGrafo connesso:", graph.verificaConnesso());
console.log("Visita in ampiezza da A:", graph.visitaAmpiezza("A"));
console.log("Visita in profondità da A:", graph.visitaProfondita("A"));