/*
 * searchPath.c
 *
 * Copyright (c) 2008-2016 Ruibang Luo <aquaskyline.com>.
 *
 * This file is part of SOAPdenovo.
 *
 * SOAPdenovo 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 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.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include "stdinc.h"
#include "newhash.h"
#include "kmerhash.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 )
    {
      fprintf ( stderr, "The 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 )
    {
      fprintf ( stderr, "The 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 )
    {
      fprintf ( stderr, "The 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;
    }
}