match_score, mismatch_score, indel_score, gap_score, NULL, entry, align);  return; }  if  (max_col == 0 && t_half < t_hi) {   Complete_Align (s, 0, s_len, t, t_half, t_hi, max_row,
void  Overlap_Align_Save_Space    (const char * s, int s_len, const char * t, int t_lo, int t_hi,     int t_len, int match_score, int mismatch_score, int indel_score,     int gap_score, Alignment_t & align)//  Find the best alignment of a prefix of string  s  to a//  substring of  t  starting between postions  t_lo  and  t_hi ,//  where the alignment must extend to the end of one of the strings.//  The length of  s  is  s_len  and the length of  t  is  t_len .//  The resulting alignment is stored in  align ,//  where  s  is the  a  string and  t  is the  b  string.//   match_score  is the score for matching characters (positive);//   mismatch_score  the score for aligning different characters (negative);//   indel_score  the score for insertions/deletions (negative);//  and  gap_score  the extra penalty for starting a gap (negative).//  Do recursively keeping just a finite number of rows  {   Alignment_t  sub_ali_1, sub_ali_2;   vector <Augmented_Score_Entry_t> align_row;        //  row of alignment array   Augmented_Score_Entry_t  entry, last_entry;   int  t_half, t_slip;   int  max_row, max_col, max_score, mxs, max_ref;   unsigned int  max_from, mxf;   int  r, c;      if  (Verbose > 3)       fprintf (stderr, "Overlap_Align_Save_Space:\n");   // Build first row   entry . diag_score = entry . top_score = entry . left_score = 0;   entry . diag_from = entry . top_from = entry . left_from = FROM_NOWHERE;   entry . top_ref = entry . diag_ref = entry . left_ref = 0;   align_row . push_back (entry);   for  (c = 1;  c <= s_len;  c ++)     {      entry . top_score = NEG_INFTY_SCORE;      entry . top_from = FROM_NOWHERE;      entry . diag_score = NEG_INFTY_SCORE;      entry . diag_from = FROM_NOWHERE;      entry . left_score = align_row [c - 1] . left_score + indel_score;      if  (c == 1)          entry . left_score += gap_score;      entry . left_from = FROM_LEFT;      entry . left_ref = 0;      entry . top_ref = entry . diag_ref = -1;      align_row . push_back (entry);     }   entry . Get_Max (max_score, max_from);   max_row = t_lo;   max_col = s_len;   max_ref = 0;   // Do remaining rows   t_half = (t_lo + t_len) / 2;   for  (r = t_lo + 1;  r <= t_len;  r ++)     {      int  first_score;      if  (r < t_hi)          first_score = 0;      else if  (r == t_hi)          first_score = indel_score + gap_score;        else          first_score = indel_score;      Align_Row_Update (align_row, t [r - 1], s, s_len, match_score,           mismatch_score, indel_score, gap_score, first_score);      if  (r == t_half)          {  // set the ref entries to reference this row           align_row [0] . top_ref = 0;           for  (c = 1;  c <= s_len;  c ++)             {              align_row [c] . top_ref = align_row [c] . diag_ref = c;              align_row [c - 1] . Get_Max_Left (mxs, mxf, gap_score);              align_row [c] . left_ref = align_row [c - 1] . Get_Ref (mxf);             }          }      // Check last column entry for max      align_row [s_len] . Get_Max (mxs, mxf);      if  (mxs > max_score)          {           max_score = mxs;           max_from = mxf;           max_row = r;           max_col = s_len;           max_ref = align_row [s_len] . Get_Ref (mxf);          }     }   // Check entries in last row for max   for  (c = 0;  c <= s_len;  c ++)     {      align_row [c] . Get_Max (mxs, mxf);      if  (mxs > max_score)          {           max_score = mxs;           max_from = mxf;           max_row = t_len;           max_col = c;           max_ref = align_row [c] . Get_Ref (mxf);          }     }   t_slip = Min (t_hi, max_row);   if  (Verbose > 3)       fprintf (stderr,            "max_row/col = %d/%d  t_lo = %d  t_slip = %d  t_half = %d  t_hi = %d\n",            max_row, max_col, t_lo, t_slip, t_half, t_hi);   if  (max_row <= t_half)       {  // only need one recursive call        Complete_Align (s, 0, s_len, t, t_lo, t_slip, max_row,             match_score, mismatch_score, indel_score, gap_score, NULL,             entry, align);        return;       }   t_slip = Min (t_hi, t_half);   if  (Verbose > 3)       fprintf (stderr,            "max_ref = %d  t_lo = %d  t_slip = %d  t_half = %d  t_hi = %d\n",            max_ref, t_lo, t_slip, t_half, t_hi);   Complete_Align (s, 0, max_ref, t, t_lo, t_slip, t_half,        match_score, mismatch_score, indel_score, gap_score,        NULL, entry, sub_ali_1);   if  (max_ref == 0)       t_slip = Max (t_hi, t_half + 1);     else       t_slip = t_half + 1;   Complete_Align (s, max_ref, max_col, t, t_half, t_slip,        max_row, match_score, mismatch_score, indel_score, gap_score,        & entry, last_entry, sub_ali_2);   align . Combine (sub_ali_1, sub_ali_2);   return;  }