#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 >= max_n_routes)
    {
      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;
    }

}