/*
 * searchPath.c
 * 
 * Copyright (c) 2011-2013 BGI-Shenzhen <soap at genomics dot org dot cn>. 
 *
 * This file is part of SOAPdenovo-Trans.
 *
 * SOAPdenovo-Trans is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * SOAPdenovo-Trans is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with SOAPdenovo-Trans.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
#include "stdinc.h"
#include "newhash.h"
#include "extfunc.h"
#include "extvab.h"

static int trace_limit = 5000;	//the times function is called in a search

/*
 search connection paths which were masked along related contigs
 start from one contig, end with another
 path length includes the length of the last contig
*/
void traceAlongMaskedCnt (unsigned int destE, unsigned int currE, int max_steps, int min, int max, int index, int len, int *num_route)
{
	num_trace++;

	if (num_trace > trace_limit || *num_route >= max_n_routes)
	{
		return;
	}

	unsigned int *array;
	int num, i, length;
	CONNECT *ite_cnt;

	if (index > 0)		// there're at most max_steps edges stored in this array including the destination edge
	{
		length = len + contig_array[currE].length;
	}
	else
	{
		length = 0;
	}

	if (index > max_steps || length > max)
	{
		return;
	}			// this is the only situation we stop

	if (index > 0)		// there're at most max_steps edges stored in this array including the destination edge
	{
		so_far[index - 1] = currE;
	}

	if (currE == destE && index == 0)
	{
		printf ("traceAlongMaskedCnt: start and destination are the same\n");
		return;
	}

	if (currE == destE && length >= min && length <= max)
	{
		num = *num_route;
		array = found_routes[num];

		for (i = 0; i < index; i++)
		{
			array[i] = so_far[i];
		}

		if (index < max_steps)
		{
			array[index] = 0;
		}		//indicate the end of the route

		*num_route = ++num;
	}			// one route is extrated, but we don't terminate searching

	ite_cnt = contig_array[currE].downwardConnect;

	while (ite_cnt)
	{
		if (!ite_cnt->mask || ite_cnt->deleted)
		{
			ite_cnt = ite_cnt->next;
			continue;
		}

		traceAlongMaskedCnt (destE, ite_cnt->contigID, max_steps, min, max, index + 1, length + ite_cnt->gapLen, num_route);
		ite_cnt = ite_cnt->next;
	}
}

// search connection paths from one connect to a contig
// path length includes the length of the last contig
void traceAlongConnect (unsigned int destE, CONNECT * currCNT, int max_steps, int min, int max, int index, int len, int *num_route)
{
	num_trace++;

	if (num_trace > trace_limit || *num_route >= max_n_routes)
	{
		return;
	}

	unsigned int *array, currE;
	int num, i, length;
	CONNECT *ite_cnt;

	currE = currCNT->contigID;
	length = len + currCNT->gapLen;
	length += contig_array[currE].length;

	if (index > max_steps || length > max)
	{
		return;
	}			// this is the only situation we stop

	/*
	   if(globalFlag)
	   printf("B: step %d, ctg %d, length %d\n",index,currCNT->contigID,length);
	 */
	if (currE == destE && index == 1)
	{
		printf ("traceAlongConnect: start and destination are the same\n");
		return;
	}

	so_far[index - 1] = currE;	// there're at most max_steps edges stored in this array including the destination edge

	if (currE == destE && length >= min && length <= max)
	{
		num = *num_route;
		array = found_routes[num];

		for (i = 0; i < index; i++)
		{
			array[i] = so_far[i];
		}

		if (index < max_steps)
		{
			array[index] = 0;
		}		//indicate the end of the route

		*num_route = ++num;
	}			// one route is extrated, but we don't terminate searching

	if (currCNT->nextInScaf)
	{
		traceAlongConnect (destE, currCNT->nextInScaf, max_steps, min, max, index + 1, length, num_route);
		return;
	}

	ite_cnt = contig_array[currE].downwardConnect;

	while (ite_cnt)
	{
		if (ite_cnt->mask || ite_cnt->deleted)
		{
			ite_cnt = ite_cnt->next;
			continue;
		}

		traceAlongConnect (destE, ite_cnt, max_steps, min, max, index + 1, length, num_route);
		ite_cnt = ite_cnt->next;
	}
}

//find paths in the graph from currE to destE, its length does not include length of both end contigs
void traceAlongArc (unsigned int destE, unsigned int currE, int max_steps, int min, int max, int index, int len, int *num_route)
{
	num_trace++;

	if (num_trace > trace_limit || *num_route >= 4)//max_n_routes-1)
	{
		return;
	}

	unsigned int *array, out_ed, vt;
	int num, i, pos, length;
	preARC *parc;

	pos = index;

	if (pos > max_steps || len > max)
	{
		return;
	}			// this is the only situation we stop

	if (currE == destE && pos == 0)
	{
		printf ("traceAlongArc: start and destination are the same\n");
		return;
	}

	if (pos > 0)		// pos starts with 0 for the starting edge
	{
		so_far[pos - 1] = currE;
	}			// there're at most max_steps edges stored in this array including the destination edge

	if (currE == destE && len >= min)
	{
		num = *num_route;
		array = found_routes[num];

		for (i = 0; i < pos; i++)
		{
			array[i] = so_far[i];
		}

		if (pos < max_steps)
		{
			array[pos] = 0;
		}		//indicate the end of the route

		*num_route = ++num;
	}			// one route is extrated, but we don't terminate searching

	if (pos == max_steps || len == max)
	{
		return;
	}

	if (pos++ > 0)		//not the starting edge
	{
		length = len + contig_array[currE].length;
	}
	else
	{
		length = len;
	}

	vt = contig_array[currE].to_vt;
	parc = contig_array[currE].arcs;

	while (parc)
	{
		out_ed = parc->to_ed;
		traceAlongArc (destE, out_ed, max_steps, min, max, pos, length, num_route);
		parc = parc->next;
	}
}