////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	# Copyright 2022 Centre Tecnològic de Telecomunicacions de Catalunya (CTTC/CERCA) www.cttc.es
 *
 * 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.

 * Author: CTTC/CERCA PONS RU Ricardo Martínez (ricardo.martinez@cttc.es)
 */
 ////////////////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h> 
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <string.h>
#include <unistd.h>
#include <netdb.h>
#include <glib.h>
#include <sys/time.h>
#include <ctype.h>
#include <strings.h>
#include <time.h>
#include <math.h>
#include <fcntl.h>

#include "pathComp_log.h"
#include "pathComp_tools.h"
#include "pathComp_ksp.h"

// Global Variables
struct map_nodes_t *mapNodes;
struct graph_t *graph;
struct contextSet_t* contextSet;

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_ksp.c
 * 	@brief Dijkstra algorithm
 *
 *  @param srcMapIndex
 *  @param dstMapIndex
 *	@param g
 *	@param s
 *	@param SN
 *	@param RP
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void sp_comp(gint srcMapIndex, gint dstMapIndex, struct graph_t* g, struct service_t* s,
	struct nodes_t* SN, struct compRouteOutputItem_t* RP) {
	g_assert(s);
	g_assert(g);

	// Set params into mapNodes related to the source nodes of the request
	mapNodes->map[srcMapIndex].distance = 0.0;
	mapNodes->map[srcMapIndex].latency = 0.0;
	mapNodes->map[srcMapIndex].avaiBandwidth = 0.0;

	// Initialize the set Q and S
	GList* S = NULL, * Q = NULL;
	gint indexVertice = -1;

	//  Add the source into the Q
	struct nodeItem_t* nodeItem = g_malloc0(sizeof(struct nodeItem_t));
	if (nodeItem == NULL) {
		DEBUG_PC("memory allocation failed\n");
		exit(-1);
	}
	// initialize some nodeItem attributes
	nodeItem->distance = 0.0;
	nodeItem->latency = 0.0;
	duplicate_node_id(&mapNodes->map[srcMapIndex].verticeId, &nodeItem->node);
	Q = g_list_insert_sorted(Q, nodeItem, sort_by_distance);

	// Check whether there is spurNode (SN) and rootPath (RP)
	if (SN != NULL && RP != NULL) {
		struct routeElement_t* re;
		for (gint j = 0; j < RP->numRouteElements; j++)
		{
			// Get the source and target Nodes of the routeElement within the rootPath
			re = &RP->routeElement[j];
			DEBUG_PC ("root Link: aNodeId: %s (%s) --> zNodeiId: %s (%s)", re->aNodeId.nodeId, re->aEndPointId, re->zNodeId.nodeId, re->zEndPointId);

			// if ingress of the root link (aNodeId) is the spurNode, then stops
			if (compare_node_id(&re->aNodeId, SN) == 0)
			{
				DEBUG_PC ("root Link: aNodeId: %s and spurNode: %s -- stop exploring the rootPath (RP)", re->aNodeId.nodeId, SN->nodeId);
				break;
			}
			// Extract from Q
			GList* listnode = g_list_first(Q);
			struct nodeItem_t* node = (struct nodeItem_t*)(listnode->data);
			Q = g_list_remove(Q, node);

			//DEBUG_RL_RA ("Exploring node %s", node->node.nodeId);
			indexVertice = graph_vertice_lookup(node->node.nodeId, g);
			g_assert(indexVertice >= 0);

			// Get the indexTargetedVertice
			gint indexTVertice = -1;
			indexTVertice = graph_targeted_vertice_lookup(indexVertice, re->zNodeId.nodeId, g);
			gint done = check_link(node, indexVertice, indexTVertice, g, s, &S, &Q, mapNodes);
			(void)done;

			// Add to the S list
			S = g_list_append(S, node);    
		}

		// Check that the first node in Q set is SpurNode, otherwise something went wrong ...
		if (compare_node_id(&re->aNodeId, SN) != 0) {
			//DEBUG_PC ("root Link: aNodeId: %s is NOT the spurNode: %s -- something wrong", re->aNodeId.nodeId, SN->nodeId);
			g_list_free_full(S, g_free);
			g_list_free_full(Q, g_free);
			return;
		}
	}		
	while (g_list_length(Q) > 0) {
		//Extract from Q set
		GList* listnode = g_list_first(Q);
		struct nodeItem_t* node = (struct nodeItem_t*)(listnode->data);
		Q = g_list_remove(Q, node);
		DEBUG_PC ("Q length: %d", g_list_length (Q)); 
		DEBUG_PC ("DeviceId: %s", node->node.nodeId);            

		// visit all the links from u within the graph
		indexVertice = graph_vertice_lookup(node->node.nodeId, g);
		g_assert(indexVertice >= 0);

		// Check the targeted vertices from u
		for (gint i = 0; i < g->vertices[indexVertice].numTargetedVertices; i++)  {                
			gint done = check_link(node, indexVertice, i, g, s, &S, &Q, mapNodes);
			(void)done;
		}
		// Add node into the S Set
		S = g_list_append(S, node);
		//DEBUG_PC ("S length: %d", g_list_length (S));              
	}
	g_list_free_full(S, g_free);
	g_list_free_full(Q, g_free);
	return;
}

///////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_ksp.c
 * 	@brief KSP computation using Dijkstra algorithm
 *
 *  @param pred
 *  @param g
 *	@param s
  *	@param SN
 *	@param RP
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
gint ksp_comp(struct pred_t* pred, struct graph_t* g, struct service_t* s, 
				struct nodes_t *SN, struct compRouteOutputItem_t *RP) {
	g_assert(pred);
	g_assert(g);
	g_assert(s);

	// Check the both ingress src and dst endpoints are in the graph
	gint srcMapIndex = get_map_index_by_nodeId(s->service_endpoints_id[0].device_uuid, mapNodes);
	if (srcMapIndex == -1) {
		DEBUG_PC("ingress DeviceId: %s NOT in the graph", s->service_endpoints_id[0].device_uuid);
		return -1;
	}

	gint dstMapIndex = get_map_index_by_nodeId(s->service_endpoints_id[1].device_uuid, mapNodes);
	if (dstMapIndex == -1) {
		DEBUG_PC("egress DeviceId: %s NOT in the graph", s->service_endpoints_id[1].device_uuid);
		return -1;
	}

	// Compute the shortest path route
	sp_comp(srcMapIndex, dstMapIndex, g, s, SN, RP);
		
	// Check that a feasible solution in term of latency and bandwidth is found
	gint map_dstIndex = get_map_index_by_nodeId(s->service_endpoints_id[1].device_uuid, mapNodes);
	struct map_t* dest_map = &mapNodes->map[map_dstIndex];
	if (!(dest_map->distance < INFINITY_COST)) 	{
		DEBUG_PC("destination: %s NOT reachable", s->service_endpoints_id[1].device_uuid);
		return -1;
	}

	DEBUG_PC("AvailBw @ %s is %f", dest_map->verticeId.nodeId, dest_map->avaiBandwidth);
	// Check that the computed available bandwidth is larger than 0.0
	if (dest_map->avaiBandwidth <= (gfloat)0.0) {
		DEBUG_PC("dst: %s NOT REACHABLE", s->service_endpoints_id[1].device_uuid);
		return -1;
	}
	DEBUG_PC("dst: %s REACHABLE", s->service_endpoints_id[1].device_uuid);
	// Handle predecessors
	build_predecessors(pred, s, mapNodes);
	return 1;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_ksp.c
 * 	@brief K-CSPF algorithm execution (YEN algorithm)
 *
 *  @param s
 *  @param path
 *  @param g
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void alg_comp(struct service_t* s, struct compRouteOutput_t* path, struct graph_t *g) {
	g_assert(s);
	g_assert(path);
	g_assert(g);

	// create map of devices/nodes to handle the path computation using the context
	mapNodes = create_map_node();
	build_map_node(mapNodes, g);

	// predecessors to store the computed path    
	struct pred_t* predecessors = create_predecessors();

	struct service_endpoints_id_t* iEp = &(s->service_endpoints_id[0]);
	struct service_endpoints_id_t* eEp = &(s->service_endpoints_id[1]);

	// Compute the 1st KSP path
	gint done = ksp_comp (predecessors, g, s, NULL, NULL);
	if (done == -1) {
		DEBUG_PC("NO PATH FOUND %s[%s] ---> %s[%s]", iEp->device_uuid, iEp->endpoint_uuid, eEp->device_uuid, eEp->endpoint_uuid);
		comp_route_connection_issue_handler(path, s);
		g_free(mapNodes); g_free(predecessors);
		return;
	}

	// Construct the path from the computed predecessors
	struct compRouteOutputItem_t* p = create_path_item();
	//print_predecessors(predecessors);
	build_path(p, predecessors, s);
	//DEBUG_PC ("Path is constructed");

	gint indexDest = get_map_index_by_nodeId(eEp->device_uuid, mapNodes);
	struct map_t* dst_map = &mapNodes->map[indexDest];
	// Get the delay and cost
	memcpy(&p->cost, &dst_map->distance, sizeof(gdouble));
	memcpy(&p->availCap, &dst_map->avaiBandwidth, sizeof(dst_map->avaiBandwidth));
	memcpy(&p->delay, &dst_map->latency, sizeof(mapNodes->map[indexDest].latency));
	DEBUG_PC ("Computed Path Avail Bw: %f, Path Cost: %f, latency: %f", p->availCap, p->cost, p->delay);
	print_path(p);

	// If 1st SP satisfies the requirements from the req, STOP
	gboolean feasibleRoute = check_computed_path_feasability(s, p);
	if (feasibleRoute == TRUE) 	{
		DEBUG_PC("1st K-CSPF FEASIBLE, STOP!");
		print_path (p);		
		path->numPaths++;

		// Copy the serviceId
		DEBUG_PC("contextId: %s", s->serviceId.contextId);
		copy_service_id(&path->serviceId, &s->serviceId);

		// copy the service endpoints, in general, there will be 2 (point-to-point network connectivity services)
		for (gint i = 0; i < s->num_service_endpoints_id; i++) {
			struct service_endpoints_id_t* iEp = &(s->service_endpoints_id[i]);
			struct service_endpoints_id_t* oEp = &(path->service_endpoints_id[i]);
			copy_service_endpoint_id(oEp, iEp);
		}
		path->num_service_endpoints_id = s->num_service_endpoints_id;

		// Copy the computed path
		struct path_t* targetedPath = &(path->paths[path->numPaths - 1]);
		duplicate_path_t(p, targetedPath);		
		print_path_t (targetedPath);
		g_free(predecessors);
		g_free(p);
		g_free(mapNodes);
		return;
	}

	DEBUG_PC("1st CSPF COMPUTATION IS NOT FEASIBLE --> TRIGGER K COMPUTATIONS");
	// Create A and B sets of paths to handle the YEN algorithm
	struct path_set_t* A = create_path_set();
	struct path_set_t* B = create_path_set();

	// Add the previously computed path into A->paths[0]	
	duplicate_path(p, &A->paths[0]);

	A->numPaths++;
	g_free(predecessors);
	g_free(p);
	for (gint k = 1; k < MAX_KSP_VALUE; k++) {
		DEBUG_PC("------------ kth (%d) ---------------------", k);
		struct compRouteOutputItem_t* p = create_path_item();
		duplicate_path(&A->paths[k - 1], p);
		// The spurNode ranges from near-end node of the first link to the near-end of the last link forming the kth path
		gint i = 0;
		struct compRouteOutputItem_t* rootPath = create_path_item();
		for (i = 0; i < p->numRouteElements; i++) {
			struct nodes_t* spurNode = create_node();
			struct nodes_t* nextSpurNode = create_node();
			struct routeElement_t* re = &(p->routeElement[i]);
			// Create predecessors to store the computed path
			struct pred_t* predecessors = create_predecessors();
			// Clear previous mapNodes, i.e. create it again
			g_free(mapNodes);
			mapNodes = create_map_node();
			build_map_node(mapNodes, g);
			struct nodes_t* n = &re->aNodeId;
			duplicate_node_id(n, spurNode);
			n = &re->zNodeId;
			duplicate_node_id(n, nextSpurNode);
			DEBUG_PC("spurNode: %s --> nextSpurNode: %s", spurNode->nodeId, nextSpurNode->nodeId);

			// rootPath contains a set of links of A[k-1] from the source Node till the SpurNode -> NextSpurNode
			// Example: A[k-1] = {L1, L2, L3, L4}, i.e. " Node_a -- L1 --> Node_b -- L2 --> Node_c -- L3 --> Node_d -- L4 --> Node_e "
			// E.g., for the ith iteration if the spurNode = Node_c and NextSpurNode = Node_d; then rootPath = {L1, L2, L3}			
			add_routeElement_path_back(re, rootPath);
			DEBUG_PC("rootPath:");
			print_path(rootPath);

			// For all existing and computed paths p in A check if from the source to the NextSpurNode
			// the set of links matches with those contained in the rootPath
			// If YES, remove from the auxiliary graph the next link in p from NextSpurNode
			// Otherwise do nothing 
			struct graph_t* gAux = create_graph();
			// Baseline graph 
			//build_graph (gAux);
			duplicate_graph(g, gAux);
			// Modified graph
			modify_targeted_graph(gAux, A, rootPath, spurNode);

			// Trigger the computation of the path from src to dst constrained to traverse all the links from src 
			// to spurNode contained into rootPath over the resulting graph			
			if (ksp_comp(predecessors, gAux, s, spurNode, rootPath) == -1) {
				DEBUG_PC("FAILED SP from %s via spurNode: %s to %s", iEp->device_uuid, spurNode->nodeId, eEp->device_uuid);
				g_free(nextSpurNode);
				g_free(spurNode);
				g_free(gAux);
				g_free(predecessors);
				continue;
			}
			DEBUG_PC("SUCCESFUL SP from %s via spurNode: %s to %s", iEp->device_uuid, spurNode->nodeId, eEp->device_uuid);
			// Create the node list from the predecessors
			struct compRouteOutputItem_t* newKpath = create_path_item();
			build_path(newKpath, predecessors, s);
			DEBUG_PC("new K (for k: %d) Path is built", k);
			gint indexDest = get_map_index_by_nodeId(eEp->device_uuid, mapNodes);
			struct map_t* dst_map = &mapNodes->map[indexDest];

			memcpy(&newKpath->cost, &dst_map->distance, sizeof(gdouble));
			memcpy(&newKpath->availCap, &dst_map->avaiBandwidth, sizeof(dst_map->avaiBandwidth));
			memcpy(&newKpath->delay, &dst_map->latency, sizeof(mapNodes->map[indexDest].latency));			
			DEBUG_PC("New PATH (@ kth: %d) ADDED to B[%d] - {Path Cost: %f, e2e latency: %f, bw: %f ", k, B->numPaths, newKpath->cost, newKpath->delay, newKpath->availCap);
			// Add the computed kth SP to the heap B
			duplicate_path(newKpath, &B->paths[B->numPaths]);
			B->numPaths++;
			DEBUG_PC("Number of B paths: %d", B->numPaths);

			g_free(newKpath);
			g_free(nextSpurNode);
			g_free(spurNode);
			g_free(gAux);
			g_free(predecessors);
		}

		// If B is empty then stops
		if (B->numPaths == 0) {
			DEBUG_PC("B does not have any path ... the stops kth computation");
			break;
		}

		// Sort the potential paths contained in B by cost and latency and available bandwidth
		sort_path_set(B);

		// Add the lowest path into A[k]		
		DEBUG_PC("-------------------------------------------------------------");
		DEBUG_PC("To Add SP from B[0] to A[%d] --- Path Cost: %f, e2e Latency: %f", A->numPaths, B->paths[0].cost, B->paths[0].delay);
		duplicate_path(&B->paths[0], &A->paths[A->numPaths]);
		A->numPaths++;
		DEBUG_PC("A Set size: %d", A->numPaths);
		DEBUG_PC("-------------------------------------------------------------");

		// Remove/pòp front element from the path set B (i.e. remove B[0])
		pop_front_path_set(B);
		DEBUG_PC("B Set Size: %d", B->numPaths);
	}

	// Copy the serviceId
	copy_service_id(&path->serviceId, &s->serviceId);
	// copy the service endpoints, in general, there will be 2 (point-to-point network connectivity services)
	for (gint m = 0; m < s->num_service_endpoints_id; m++) {
		struct service_endpoints_id_t* iEp = &(s->service_endpoints_id[m]);
		struct service_endpoints_id_t* oEp = &(path->service_endpoints_id[m]);
		copy_service_endpoint_id(oEp, iEp);
	}

	for (gint ksp = 1; ksp < A->numPaths; ksp++){
		if (ksp >= MAX_KSP_VALUE) {
			DEBUG_PC("Number Requested paths (%d) REACHED - STOP", ksp);
			break;
		}
		gdouble feasibleRoute = check_computed_path_feasability(s, &A->paths[ksp]);
		if (feasibleRoute == TRUE) {
			DEBUG_PC("A[k-th%d] available: %f, pathCost: %f; latency: %f", ksp, A->paths[ksp].availCap, A->paths[ksp].cost, A->paths[ksp].delay);
			struct compRouteOutputItem_t* pathaux = &A->paths[ksp];
			path->numPaths++;
			struct path_t* targetedPath = &path->paths[path->numPaths - 1];
			duplicate_path_t(pathaux, targetedPath);		
			print_path_t(targetedPath);
			remove_path_set(A);
			remove_path_set(B);
			return;
		}
	}
	remove_path_set(A);
	remove_path_set(B);
	// No paths found --> Issue	
	DEBUG_PC("K-SP failed!!!");
	comp_route_connection_issue_handler(path, s);

	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_ksp.c
 * 	@brief Iterates over the list of network connectivity service requests 
 * to compute their own paths fulfilling the constraints
 *
 *  @param outputList
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
 /////////////////////////////////////////////////////////////////////////////////////////
void ksp_alg_execution_services(struct compRouteOutputList_t* outputList) {
	g_assert(outputList);
	g_assert(contextSet);
	g_assert(serviceList);

	DEBUG_PC("----- Starting the KSP Computation ------");

	// Iterate over the list of requested network connectivity services
	for (gint i = 0; i < serviceList->numServiceList; i++) {
		struct service_t* service = &(serviceList->services[i]);

		DEBUG_PC("Starting the Computation for ServiceId: %s [ContextId: %s]", service->serviceId.service_uuid, service->serviceId.contextId);
		struct compRouteOutput_t* pathService = &(outputList->compRouteConnection[i]);
		// check endpoints of the service are different (PE devices/nodes are different)
		if (same_src_dst_pe_nodeid(service) == 0) {
			DEBUG_PC("PEs are the same... no path computation");
			comp_route_connection_issue_handler(pathService, service);
			outputList->numCompRouteConnList++;
			continue;
		}
		// get the graph associated to the contextId in the contextSet, if no then error
		struct graph_t* g = get_graph_by_contextId(contextSet, service->serviceId.contextId);
		if (g == NULL) {
			DEBUG_PC("The targeted contextId is NOT in the ContextSet ... then NO graph");
			comp_route_connection_issue_handler(pathService, service);
			outputList->numCompRouteConnList++;
			continue;
		}
		alg_comp(service, pathService, g);
		outputList->numCompRouteConnList++;

		// for each network connectivity service, a single computed path (out of the KCSP) is retuned
		// If path is found, then the selected resources must be pre-assigned into the context information
		if (pathService->noPathIssue == NO_PATH_CONS_ISSUE)
		{
			continue;
		}
		struct path_t* path = &(pathService->paths[pathService->numPaths - 1]);
		allocate_graph_resources(path, service, g);
		allocate_graph_reverse_resources(path, service, g);
		print_graph(g);
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////////////
/**
 * 	@file pathComp_ksp.c
 * 	@brief handles the path computation triggering k-cspf algorithm
 *
 *  @param compRouteOutput
 *
 *	@author Ricardo Martínez <ricardo.martinez@cttc.es>
 *	@date 2022
 */
/////////////////////////////////////////////////////////////////////////////////////////
gint pathComp_ksp_alg(struct compRouteOutputList_t * routeConnList)
{   	
	g_assert(routeConnList);
	gint numSuccesPathComp = 0, numPathCompIntents = 0;
	
	DEBUG_PC ("================================================================");
	DEBUG_PC ("===========================   KSP   =========================");
	DEBUG_PC ("================================================================");
	// increase the number of Path Comp. Intents
	numPathCompIntents++;
	gint http_code = HTTP_CODE_OK;

	// timestamp t0
	struct timeval t0;
	gettimeofday(&t0, NULL);	
	
	// Allocate memory for the context
	contextSet = create_contextSet();
	// Build up the contextSet (>= 1)
	build_contextSet(contextSet);
	print_contextSet(contextSet);	
#if 1	
	//Triggering the path computation for each specific network connectivity service
	ksp_alg_execution_services (routeConnList);

	// -- timestamp t1
	struct timeval t1, delta;
	gettimeofday(&t1, NULL);
	delta.tv_sec = t1.tv_sec - t0.tv_sec;
	delta.tv_usec = t1.tv_usec - t0.tv_usec;
	delta = tv_adjust(delta);

	numSuccesPathComp++;
	update_stats_path_comp(routeConnList, delta, numSuccesPathComp, numPathCompIntents);
	print_path_connection_list(routeConnList);
#endif

	g_free(contextSet);
	return http_code;
}