const Graph    = require('./graph-data-structure');

type NodeLabel   = string;
type VisitedNode = {
    label : NodeLabel;
    visited : boolean;
}
type DFSComponents = {
    component : NodeLabel[];
    visited   : { [label : string]:boolean };
}

class GraphComponents {

        Graph;

        constructor() {
            this.Graph = new Graph();
        }

        remaining( visitedList : {[label : string]: boolean } ): NodeLabel[] 
        {
            const resultList:  NodeLabel[] = [];
            Object.keys( visitedList ).forEach( (element : NodeLabel) => {
                if ( !visitedList[element] ) {
                    resultList.push( element );
                }
            });
            return resultList;
        }

        depthFirstSearch( sourceNode : NodeLabel ) : DFSComponents
        {
            const nodesVisited  : { [label : string]: boolean } = {};
            const nodeList      : NodeLabel[]          = [];

            function DFSVisit( node: NodeLabel ) {
                if (!nodesVisited[node]) {
                    nodesVisited[node] = true;
                    this.Graph.adjacent(node).forEach(DFSVisit);
                    nodeList.push(node);
                }
            }
            nodesVisited[sourceNode] = true;
            this.Graph.adjacent(sourceNode).forEach( DFSVisit );
            return {component : nodeList, visited : nodesVisited};
        }

        connectedComponents()
        {
            let graphNodes: NodeLabel[] = this.Graph.nodes();
            if (graphNodes == []) { throw new Error(`The list of nodes in the Graph is empty.`) };

            let   remaining: NodeLabel[] = graphNodes;
            const Components = [];

            while ( !(remaining == []) ) {
                let currentNode  = remaining[0];
                let results     = this.depthFirstSearch( currentNode );
                Components.push( results.component );
                remaining       = this.remaining( results.visited );
            }

            return Components;
        }
}