'use strict';

// Copyright 2016 Fetch Robotics, Inc.
// Author(s): Andrey Filenko

/**
 * findSubGraphs() searches for sub-graphs for a given lane.
 *
 * @param {Object} node - currently checked node. If current sub-graph does not contain this node yet,
 * it's added to sub-graph nodes, and algorithm checks all nodes connected to the checked one.
 *
 * @param {Object} lane - contains nodes and edges arrays.
 *
 * @param {Object} recursion - stores results and params needed to exit from recursion.
 *
 * @return {Array} List of all sub-graphs: [[nodes...], [nodes...]]
 */
const findSubGraphs = (node, lane, recursion) => {
    recursion.callsCount++;

    const { currentSubGraph, passedNodes, subGraphs } = recursion;
    const { nodes, edges, nodesMap } = lane;
    const nodeEdges = edges.filter((edge) => edge.start === node.id || edge.end === node.id);

    // mark current sub-graph nodes and all nodes passed during search
    if (passedNodes.indexOf(node) < 0) {
        if (currentSubGraph.indexOf(node) < 0) {
            currentSubGraph.push(node);
        }
        passedNodes.push(node);
    }
    // continue walking through current sub-graph if checked node has references to other nodes
    if (nodeEdges.length) {
        const nextCheckedEdges = nodeEdges.filter((edge) => {
            return currentSubGraph.indexOf(nodesMap[edge.end]) < 0
                || currentSubGraph.indexOf(nodesMap[edge.start]) < 0;
        });
        nextCheckedEdges.forEach((edge) => {
            if (node.id !== edge.end) {
                return findSubGraphs(nodesMap[edge.end], lane, recursion);
            } else if (node.id !== edge.start) {
                return findSubGraphs(nodesMap[edge.start], lane, recursion);
            }
        });
    }

    recursion.callsCount--;

    // if no more calls were made, then current sub-graph search is completed
    if (recursion.callsCount === 0) {
        if (currentSubGraph.length) {
            subGraphs.push(currentSubGraph);
        }

        // if all nodes were passed, exiting recursion
        if (passedNodes.length === nodes.length) {
            return subGraphs;
        }

        // determine the next node which was not passed yet
        while (
            (recursion.startNodeIndex < nodes.length - 1)
            && (passedNodes.indexOf(nodes[recursion.startNodeIndex]) >= 0)
        ) {
            recursion.startNodeIndex++;
        }
        const nextNode = nodes[recursion.startNodeIndex];

        // start search for next sub-graph
        recursion.currentSubGraph = [];
        return findSubGraphs(nextNode, lane, recursion);
    }
};

export default function getLaneParts(nodes, edges) {
    if (!(nodes && nodes.length)) {
        return [];
    }

    // build nodes map for faster access to node by id during sub-graphs search
    const nodesMap = nodes.reduce((result, node) => {
        result[node.id] = node;
        return result;
    }, {});

    return findSubGraphs(
        nodes[0],
        {
            nodes,
            edges: edges || [],
            nodesMap,
        },
        {
            subGraphs: [],
            currentSubGraph: [],
            startNodeIndex: 0,
            passedNodes: [],
            callsCount: 0
        }
    );
}