/*!
 * Copyright (C) 2017 AT&T Intellectual Property. All rights reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing
 * permissions and limitations under the License.
 */

import DirectedGraph from 'nfvo-utils/DirectedGraph.js';

function findCycles(graph, node, id, visited = {}, visitedConnections = {}, recursionStack = {}, connectionsWithCycle = {}) {
	visited[node] = true;
	recursionStack[node] = true;
	if (id) {
		visitedConnections[id] = true;
	}
	for (let edge of graph.getEdges(node)) {
		if (!visited[edge.target]) {
			findCycles(graph, edge.target, edge.id, visited, visitedConnections, recursionStack, connectionsWithCycle);
		} else if (recursionStack[edge.target]) {
			visitedConnections[edge.id] = true;
			for (let connection in visitedConnections) {
				connectionsWithCycle[connection] = true;
			}
		}
	}
	recursionStack[node] = false;
	return {visitedNodes: visited, connectionsWithCycle: connectionsWithCycle};
}

export function checkCyclesAndMarkDependencies(dependenciesList) {
	let overallVisitedNodes = {};
	let overallConnectionsWithCycles = {};

	let g = new DirectedGraph();
	for (let dependency of dependenciesList) {
		if (dependency.sourceId !== null && dependency.targetId !== null) {
			g.addEdge(dependency.sourceId, dependency.targetId, {id: dependency.id});
		}
	}

	for (let node in g.nodes) {
		if (!overallVisitedNodes.node) {
			let {visitedNodes, connectionsWithCycle} = findCycles(g, node, undefined);
			overallVisitedNodes = {...overallVisitedNodes, ...visitedNodes};
			overallConnectionsWithCycles = {...overallConnectionsWithCycles, ...connectionsWithCycle};
		}
	}
	return dependenciesList.map(dependency => (
		{
			...dependency,
			 hasCycle: dependency.sourceId && dependency.targetId ? 
			 	overallConnectionsWithCycles.hasOwnProperty(dependency.id) 
				 : undefined
		}));
}