import GraphVertex from "./GraphVertex";

export default class Graph {
    constructor(isDirected = true) {
        this.vertices = new Map();
        this.isDirected = isDirected;
    }

    addEdge(start, end) {
        const startVertex = this.addVertex(start);
        const endVertex = this.addVertex(end);

        startVertex.addAdjacent(endVertex);

        if (!this.isDirected) {
            endVertex.addAdjacent(startVertex);
        }
    }

    removeEdge(start, end) {
        const startVertex = this.getVertex(start);
        const endVertex = this.getVertex(end);

        if (startVertex && endVertex) {
            startVertex.removeAdjacent(endVertex);

            if (!this.isDirected) {
                endVertex.removeAdjacent(startVertex);
            }
        }
    }

    addVertex(value) {
        if (this.vertices.has(value)) {
            return this.getVertex(value);
        }

        const vertex = new GraphVertex(value);
        this.vertices.set(value, vertex);
        return vertex;
    }

    removeVertex(value) {
        const vertexToRemove = this.getVertex(value);

        if (vertexToRemove) {
            for (const vertex of vertexToRemove.getAdjacents()) {
                vertex.removeAdjacent(vertexToRemove);
            }
        }

        return this.vertices.delete(value);
    }

    getVertex(value) {
        return this.vertices.get(value);
    }

    getVertexValues() {
        return [...this.vertices.keys()];
    }

    print() {
        for (const vertex of this.vertices.values()) {
            console.log(vertex.getValue(), " => ", vertex.adjacents);
        }
    }

    // TODO: enhance adjacency matrix to not create unnecessary array from 0 -> minVertexValue
    getAdjacencyMatrix() {
        const maxVal = Math.max(...this.getVertexValues());
        const adjacencyMatrix = [];

        for (let i = 0; i <= maxVal; i++) {
            adjacencyMatrix.push(new Array(maxVal + 1).fill(0));
        }

        for (const [key, vertex] of this.vertices.entries()) {
            const fromVertex = vertex;
            for (const toVertex of vertex.getAdjacents()) {
                adjacencyMatrix[fromVertex.getValue()][toVertex.getValue()] = 1;
            }
        }

        return adjacencyMatrix;
    }

    depthFirstSearch(startVertex, targetValue) {
        const visited = new Set();
        const stack = [startVertex];

        while (stack.length) {
            const current = stack.pop();

            if (current.getValue() === targetValue) {
                console.log("Found vertex with value of " + targetValue);
                return true;
            }

            if (visited.has(current)) {
                continue;
            }

            console.log("Searching vertex with value of " + current.getValue());
            visited.add(current);
            for (const adjacentVertex of current.getAdjacents()) {
                stack.push(adjacentVertex);
            }
        }

        console.log("Did not find vertex with value of " + targetValue);
        return false;
    }

    breadthFirstSearch(startVertex, targetValue) {
        const visited = new Set();
        const queue = [startVertex];

        while (queue.length) {
            const current = queue.shift();

            if (current.getValue() === targetValue) {
                console.log("Found vertex with value of " + targetValue);
                return true;
            }

            if (visited.has(current)) {
                continue;
            }

            console.log("Searching vertex with value of " + current.getValue());
            visited.add(current);
            for (const adjacentVertex of current.getAdjacents()) {
                queue.push(adjacentVertex);
            }
        }

        console.log("Did not find vertex with value of " + targetValue);
        return false;
    }
}
