/**
 * This source code is from https://github.com/jriecken/dependency-graph
 * Just added "any" types here, wrapper everything into exported class.
 * We cant use a package itself because we want to package "everything-in-it" for the frontend users of TypeORM.
 */

/**
 * A simple dependency graph
 */

import { TypeORMError } from "../error"

/**
 * Helper for creating a Depth-First-Search on
 * a set of edges.
 *
 * Detects cycles and throws an Error if one is detected.
 *
 * @param edges The set of edges to DFS through
 * @param leavesOnly Whether to only return "leaf" nodes (ones who have no edges)
 * @param result An array in which the results will be populated
 */
function createDFS(edges: any, leavesOnly: any, result: any) {
    let currentPath: any[] = []
    let visited: any = {}
    return function DFS(currentNode: any) {
        visited[currentNode] = true
        currentPath.push(currentNode)
        edges[currentNode].forEach(function (node: any) {
            if (!visited[node]) {
                DFS(node)
            } else if (currentPath.indexOf(node) >= 0) {
                currentPath.push(node)
                throw new TypeORMError(
                    `Dependency Cycle Found: ${currentPath.join(" -> ")}`,
                )
            }
        })
        currentPath.pop()
        if (
            (!leavesOnly || edges[currentNode].length === 0) &&
            result.indexOf(currentNode) === -1
        ) {
            result.push(currentNode)
        }
    }
}

export class DepGraph {
    nodes: any = {}
    outgoingEdges: any = {} // Node -> [Dependency Node]
    incomingEdges: any = {} // Node -> [Dependant Node]

    /**
     * Add a node to the dependency graph. If a node already exists, this method will do nothing.
     */
    addNode(node: any, data?: any) {
        if (!this.hasNode(node)) {
            // Checking the arguments length allows the user to add a node with undefined data
            if (arguments.length === 2) {
                this.nodes[node] = data
            } else {
                this.nodes[node] = node
            }
            this.outgoingEdges[node] = []
            this.incomingEdges[node] = []
        }
    }

    /**
     * Remove a node from the dependency graph. If a node does not exist, this method will do nothing.
     */
    removeNode(node: any) {
        if (this.hasNode(node)) {
            delete this.nodes[node]
            delete this.outgoingEdges[node]
            delete this.incomingEdges[node]
            ;[this.incomingEdges, this.outgoingEdges].forEach(function (
                edgeList,
            ) {
                Object.keys(edgeList).forEach(function (key: any) {
                    let idx = edgeList[key].indexOf(node)
                    if (idx >= 0) {
                        edgeList[key].splice(idx, 1)
                    }
                }, this)
            })
        }
    }

    /**
     * Check if a node exists in the graph
     */
    hasNode(node: any) {
        return this.nodes.hasOwnProperty(node)
    }

    /**
     * Get the data associated with a node name
     */
    getNodeData(node: any) {
        if (this.hasNode(node)) {
            return this.nodes[node]
        } else {
            throw new TypeORMError(`Node does not exist: ${node}`)
        }
    }

    /**
     * Set the associated data for a given node name. If the node does not exist, this method will throw an error
     */
    setNodeData(node: any, data: any) {
        if (this.hasNode(node)) {
            this.nodes[node] = data
        } else {
            throw new TypeORMError(`Node does not exist: ${node}`)
        }
    }

    /**
     * Add a dependency between two nodes. If either of the nodes does not exist,
     * an Error will be thrown.
     */
    addDependency(from: any, to: any) {
        if (!this.hasNode(from)) {
            throw new TypeORMError(`Node does not exist: ${from}`)
        }
        if (!this.hasNode(to)) {
            throw new TypeORMError(`Node does not exist: ${to}`)
        }
        if (this.outgoingEdges[from].indexOf(to) === -1) {
            this.outgoingEdges[from].push(to)
        }
        if (this.incomingEdges[to].indexOf(from) === -1) {
            this.incomingEdges[to].push(from)
        }
        return true
    }

    /**
     * Remove a dependency between two nodes.
     */
    removeDependency(from: any, to: any) {
        let idx: any
        if (this.hasNode(from)) {
            idx = this.outgoingEdges[from].indexOf(to)
            if (idx >= 0) {
                this.outgoingEdges[from].splice(idx, 1)
            }
        }

        if (this.hasNode(to)) {
            idx = this.incomingEdges[to].indexOf(from)
            if (idx >= 0) {
                this.incomingEdges[to].splice(idx, 1)
            }
        }
    }

    /**
     * Get an array containing the nodes that the specified node depends on (transitively).
     *
     * Throws an Error if the graph has a cycle, or the specified node does not exist.
     *
     * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned
     * in the array.
     */
    dependenciesOf(node: any, leavesOnly: any) {
        if (this.hasNode(node)) {
            let result: any[] = []
            let DFS = createDFS(this.outgoingEdges, leavesOnly, result)
            DFS(node)
            let idx = result.indexOf(node)
            if (idx >= 0) {
                result.splice(idx, 1)
            }
            return result
        } else {
            throw new TypeORMError(`Node does not exist: ${node}`)
        }
    }

    /**
     * get an array containing the nodes that depend on the specified node (transitively).
     *
     * Throws an Error if the graph has a cycle, or the specified node does not exist.
     *
     * If `leavesOnly` is true, only nodes that do not have any dependants will be returned in the array.
     */
    dependantsOf(node: any, leavesOnly: any) {
        if (this.hasNode(node)) {
            let result: any[] = []
            let DFS = createDFS(this.incomingEdges, leavesOnly, result)
            DFS(node)
            let idx = result.indexOf(node)
            if (idx >= 0) {
                result.splice(idx, 1)
            }
            return result
        } else {
            throw new TypeORMError(`Node does not exist: ${node}`)
        }
    }

    /**
     * Construct the overall processing order for the dependency graph.
     *
     * Throws an Error if the graph has a cycle.
     *
     * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned.
     */
    overallOrder(leavesOnly?: any) {
        let self = this
        let result: any[] = []
        let keys = Object.keys(this.nodes)
        if (keys.length === 0) {
            return result // Empty graph
        } else {
            // Look for cycles - we run the DFS starting at all the nodes in case there
            // are several disconnected subgraphs inside this dependency graph.
            let CycleDFS = createDFS(this.outgoingEdges, false, [])
            keys.forEach(function (n: any) {
                CycleDFS(n)
            })

            let DFS = createDFS(this.outgoingEdges, leavesOnly, result)
            // Find all potential starting points (nodes with nothing depending on them) an
            // run a DFS starting at these points to get the order
            keys.filter(function (node) {
                return self.incomingEdges[node].length === 0
            }).forEach(function (n) {
                DFS(n)
            })

            return result
        }
    }
}