sim.c

开放源码的编译器open watcom 1.6.0版的源代码

	     FF[j] = j;
	     if ( nseq == 2 || j > mm )
		RR[j] = SS[j] = mm + 1;
	     else
		RR[j] = SS[j] = j;
	  }

	for ( i = mm; i >= m1; i-- )
	  {  c = p = 0;
	     f = - (q);
	     ci = fi = i;
	     pi = i + 1;
	     cj = fj = pj = nn + 1;
	     va = v[A[i]];
	     if ( nseq == 2 || n1 > i )
		limit = n1;
	     else
		limit = i + 1;
	     for ( j = nn; j >= limit ; j-- )  
		 {  f = f - r;
		  c = c - qr;
		  ORDER(f, fi, fj, c, ci, cj)
		  c = CC[j] - qr; 
		  ci = RR[j];
		  cj = EE[j];
		  d = DD[j] - r;
		  di = SS[j];
		  dj = FF[j];
		  ORDER(d, di, dj, c, ci, cj)
		  c = 0;
		  DIAG(i, j, c, p+va[B[j]])             /* diagonal */
		  if ( c <= 0 )
		    { c = 0; ci = i; cj = j; }
		  else
		    { ci = pi; cj = pj; }
		  ORDER(c, ci, cj, d, di, dj)
		  ORDER(c, ci, cj, f, fi, fj)
		  p = CC[j];
		  CC[j] = c;
		  pi = RR[j];
		  pj = EE[j];
		  RR[j] = ci;
		  EE[j] = cj;
		  DD[j] = d;
		  SS[j] = di;
		  FF[j] = dj;
		  if ( c > min )
		    flag = 1;
		}
	     if ( nseq == 2 || i < n1 )
		 { HH[i] = CC[n1];
		 II[i] = RR[n1];
		 JJ[i] = EE[n1];
		 WW[i] = DD[n1];
		 XX[i] = SS[n1];
		 YY[i] = FF[n1];
		 }
	  }
	
  for ( rl = m1, cl = n1; ; )
    { for ( rflag = cflag = 1; (rflag && m1 > 1) || ( cflag && n1 > 1);)
	{ if ( rflag && m1 > 1 )        /* Compute one row */
	    { rflag = 0;
		m1--;
		c = p = 0;
		f = - (q);
		ci = fi = m1;
		pi = m1 + 1;
		cj = fj = pj = nn + 1;
		va = v[A[m1]];
		for ( j = nn; j >= n1 ; j-- )  
		{ f = f - r;
		  c = c - qr;
		  ORDER(f, fi, fj, c, ci, cj)
		  c = CC[j] - qr; 
		  ci = RR[j];
		  cj = EE[j];
		  d = DD[j] - r;
		  di = SS[j];
		  dj = FF[j];
		  ORDER(d, di, dj, c, ci, cj)
		  c = 0;
		  DIAG(m1, j, c, p+va[B[j]])            /* diagonal */
		  if ( c <= 0 )
		    { c = 0; ci = m1; cj = j; }
		  else
		    { ci = pi; cj = pj; }
		  ORDER(c, ci, cj, d, di, dj)
		  ORDER(c, ci, cj, f, fi, fj)
		  p = CC[j];
		  CC[j] = c;
		  pi = RR[j];
		  pj = EE[j];
		  RR[j] = ci;
		  EE[j] = cj;
		  DD[j] = d;
		  SS[j] = di;
		  FF[j] = dj;
		  if ( c > min )
		     flag = 1;
		  if ( ! rflag && (ci > rl && cj > cl || di > rl && dj>cl
						  || fi > rl && fj > cl))
			rflag = 1;
		}
		HH[m1] = CC[n1];
		II[m1] = RR[n1];
		JJ[m1] = EE[n1];
		WW[m1] = DD[n1];
		XX[m1] = SS[n1];
		YY[m1] = FF[n1];
		if ( ! cflag && ( ci > rl && cj > cl || di > rl && dj > cl
			     || fi > rl && fj > cl ) )
		 cflag = 1;
	    }

	  if ( nseq == 1 && n1 == (m1 + 1) && ! rflag )
	     cflag = 0;
	  if ( cflag && n1 > 1 )        /* Compute one column */
	    { cflag = 0;
		n1--;
		c = 0;
		f = - (q);
		cj = fj = n1;
		va = v[B[n1]];
		if ( nseq == 2 || mm < n1 )
		{ p = 0;
		  ci = fi = pi = mm + 1;
		  pj = n1 + 1;
		  limit = mm;
		}
		else
		{ p = HH[n1];
		  pi = II[n1];
		  pj = JJ[n1];
		  ci = fi = n1;
		  limit = n1 - 1;
		}
		for ( i = limit; i >= m1 ; i-- )  
		{ f = f - r;
		  c = c - qr;
		  ORDER(f, fi, fj, c, ci, cj)
		  c = HH[i] - qr; 
		  ci = II[i];
		  cj = JJ[i];
		  d = WW[i] - r;
		  di = XX[i];
		  dj = YY[i];
		  ORDER(d, di, dj, c, ci, cj)
		  c = 0;
		  DIAG(i, n1, c, p+va[A[i]])
		  if ( c <= 0 )
		    { c = 0; ci = i; cj = n1; }
		  else
		    { ci = pi; cj = pj; }
		  ORDER(c, ci, cj, d, di, dj)
		  ORDER(c, ci, cj, f, fi, fj)
		  p = HH[i];
		  HH[i] = c;
		  pi = II[i];
		  pj = JJ[i];
		  II[i] = ci;
		  JJ[i] = cj;
		  WW[i] = d;
		  XX[i] = di;
		  YY[i] = dj;
		  if ( c > min )
		     flag = 1;
		  if (! cflag && (ci > rl && cj > cl || di > rl && dj >cl
				 || fi > rl && fj > cl ) )
		     cflag = 1;
		}
		CC[n1] = HH[m1];
		RR[n1] = II[m1];
		EE[n1] = JJ[m1];
		DD[n1] = WW[m1];
		SS[n1] = XX[m1];
		FF[n1] = YY[m1];
		if ( ! rflag && ( ci > rl && cj > cl || di > rl && dj > cl
						 || fi > rl && fj > cl ))
		 rflag = 1;
	    }
	}
	if ( m1 == 1 && n1 == 1 || no_cross() )
	 break;
   }
  m1--;
  n1--;
}

/* recompute the area on forward pass */
small_pass(A,B,count,nseq) char A[], B[]; long count, nseq;
{ register  long  i, j;             /* row and column indices */
  register  long  c;                /* best score at current point */
  register  long  f;                /* best score ending with insertion */
  register  long  d;                /* best score ending with deletion */
  register  long  p;                /* best score at (i-1, j-1) */
  register  long  ci, cj;           /* end-point associated with c */ 
  register  long  di, dj;           /* end-point associated with d */
  register  long  fi, fj;           /* end-point associated with f */
  register  long  pi, pj;           /* end-point associated with p */
  long  *va;                        /* pointer to v(A[i], B[j]) */
  long   addnode();                 /* function for inserting a node */
  long  limit;                      /* lower bound on j */

	for ( j = n1 + 1; j <= nn ; j++ )
	  {  CC[j] = 0;
	     RR[j] = m1;
	     EE[j] = j;
	     DD[j] = - (q);
	     SS[j] = m1;
	     FF[j] = j;
	  }
	for ( i = m1 + 1; i <= mm; i++) 
	  {  c = 0;                             /* Initialize column 0 */
	     f = - (q);
	     ci = fi = i;
	     va = v[A[i]];
	     if ( nseq == 2 || i <= n1 )
		 { p = 0;
		 pi = i - 1;
		 cj = fj = pj = n1;
		 limit = n1 + 1;
		 }
	     else
		 { p = CC[i];
		 pi = RR[i];
		 pj = EE[i];
		 cj = fj = i;
		 limit = i + 1;
		 }
	     for ( j = limit ; j <= nn ; j++ )  
		 {  f = f - r;
		  c = c - qr;
		  ORDER(f, fi, fj, c, ci, cj)
		  c = CC[j] - qr; 
		  ci = RR[j];
		  cj = EE[j];
		  d = DD[j] - r;
		  di = SS[j];
		  dj = FF[j];
		  ORDER(d, di, dj, c, ci, cj)
		  c = 0;
		  DIAG(i, j, c, p+va[B[j]])             /* diagonal */
		  if ( c <= 0 )
		    { c = 0; ci = i; cj = j; }
		  else
		    { ci = pi; cj = pj; }
		  ORDER(c, ci, cj, d, di, dj)
		  ORDER(c, ci, cj, f, fi, fj)
		  p = CC[j];
		  CC[j] = c;
		  pi = RR[j];
		  pj = EE[j];
		  RR[j] = ci;
		  EE[j] = cj;
		  DD[j] = d;
		  SS[j] = di;
		  FF[j] = dj;
		  if ( c > min )        /* add the score into list */
		    min = addnode(c, ci, cj, i, j, count, min);
		}
	  }
}

/* Add a new node into list.  */

long addnode(c, ci, cj, i, j, K, cost)  long c, ci, cj, i, j, K, cost;
{ short found;                          /* 1 if the node is in LIST */
  register long d;

  found = 0;
  if ( most != 0 && most->STARI == ci && most->STARJ == cj )
    found = 1;
  else
     for ( d = 0; d < numnode ; d++ )
	{ most = LIST[d];
	  if ( most->STARI == ci && most->STARJ == cj )
	    { found = 1;
		break;
	    }
	}
  if ( found )
    { if ( most->SCORE < c )
	{ most->SCORE = c;
	  most->ENDI = i;
	  most->ENDJ = j;
	}
	if ( most->TOP > i ) most->TOP = i;
	if ( most->BOT < i ) most->BOT = i;
	if ( most->LEFT > j ) most->LEFT = j;
	if ( most->RIGHT < j ) most->RIGHT = j;
    }
  else
    { if ( numnode == K )       /* list full */
	 most = low;
	else
	 most = LIST[numnode++];
	most->SCORE = c;
	most->STARI = ci;
	most->STARJ = cj;
	most->ENDI = i;
	most->ENDJ = j;
	most->TOP = most->BOT = i;
	most->LEFT = most->RIGHT = j;
    }
  if ( numnode == K )
    { if ( low == most || ! low ) 
	{ for ( low = LIST[0], d = 1; d < numnode ; d++ )
	    if ( LIST[d]->SCORE < low->SCORE )
		low = LIST[d];
	}
	return ( low->SCORE ) ;
    }
  else
    return cost;
}

/* Find and remove the largest score in list */

vertexptr findmax()
{ vertexptr  cur;
  register long i, j;

  for ( j = 0, i = 1; i < numnode ; i++ )
    if ( LIST[i]->SCORE > LIST[j]->SCORE )
	 j = i;
  cur = LIST[j];
  if ( j != --numnode )
    { LIST[j] = LIST[numnode];
	LIST[numnode] =  cur;
    }
  most = LIST[0];
  if ( low == cur ) low = LIST[0];
  return ( cur );
}

/* return 1 if no node in LIST share vertices with the area */

no_cross()
{ vertexptr  cur;
  register long i;

	for ( i = 0; i < numnode; i++ )
	{ cur = LIST[i];
	  if ( cur->STARI <= mm && cur->STARJ <= nn && cur->BOT >= m1-1 && 
		 cur->RIGHT >= n1-1 && (cur->STARI < rl || cur->STARJ < cl))
	     { if ( cur->STARI < rl ) rl = cur->STARI;
		 if ( cur->STARJ < cl ) cl = cur->STARJ;
		 flag = 1;
		 break;
	     }
	}
	if ( i == numnode )
	return 1;
	else
	return 0;
}

/* diff(A,B,M,N,tb,te) returns the score of an optimum conversion between
   A[1..M] and B[1..N] that begins(ends) with a delete if tb(te) is zero
   and appends such a conversion to the current script.                */

long diff(A,B,M,N,tb,te) char *A, *B; long M, N; long tb, te;

{ long   midi, midj, type;      /* Midpoint, type, and cost */
  long midc;

{ register long   i, j;
  register long c, e, d, s;
	   long t, *va;
	   char  *ckalloc();

/* Boundary cases: M <= 1 or N == 0 */

  if (N <= 0)
    { if (M > 0) DEL(M)
	return - gap(M);
    }
  if (M <= 1)
    { if (M <= 0)
	{ INS(N);
	  return - gap(N);
	}
	if (tb > te) tb = te;
	midc = - (tb + r + gap(N) );
	midj = 0;
	va = v[A[1]];
	for (j = 1; j <= N; j++)
	{  for ( tt = 1, z = row[I+1]; z != 0; z = z->NEXT )    
		if ( z->COL == j+J )                      
		 { tt = 0; break; }             
	   if ( tt )                    
	    { c = va[B[j]] - ( gap(j-1) + gap(N-j) );
		if (c > midc)
		 { midc = c;
		 midj = j;
		 }
	    }
	}
	if (midj == 0)
	{ INS(N) DEL(1) }
	else
	{ if (midj > 1) INS(midj-1)
	  REP
	  if ( A[1] == B[midj] )
	     no_mat += 1;
	  else
	     no_mis += 1;
	  /* mark (A[I],B[J]) as used: put J into list row[I] */        
	  I++; J++;
	  z = ( pairptr ) ckalloc( (long) sizeof(pair));
	  z->COL = J;                   
	  z->NEXT = row[I];                             
	  row[I] = z;
	  if (midj < N) INS(N-midj)
	}
	return midc;
    }

/* Divide: Find optimum midpoint (midi,midj) of cost midc */

  midi = M/2;             /* Forward phase:                          */
  CC[0] = 0;              /*   Compute C(M/2,k) & D(M/2,k) for all k */
  t = -q;
  for (j = 1; j <= N; j++)
    { CC[j] = t = t-r;
	DD[j] = t-q;
    }
  t = -tb;
  for (i = 1; i <= midi; i++)
    { s = CC[0];
	CC[0] = c = t = t-r;
	e = t-q;
	va = v[A[i]];
	for (j = 1; j <= N; j++)
	{ if ((c = c - qr) > (e = e - r)) e = c;
	  if ((c = CC[j] - qr) > (d = DD[j] - r)) d = c;
	  DIAG(i+I, j+J, c, s+va[B[j]])
	  if (c < d) c = d;
	  if (c < e) c = e;
	  s = CC[j];
	  CC[j] = c;
	  DD[j] = d;
	}
    }
  DD[0] = CC[0];

  RR[N] = 0;              /* Reverse phase:                          */
  t = -q;                 /*   Compute R(M/2,k) & S(M/2,k) for all k */
  for (j = N-1; j >= 0; j--)
    { RR[j] = t = t-r;
	SS[j] = t-q;
    }
  t = -te;
  for (i = M-1; i >= midi; i--)
    { s = RR[N];
	RR[N] = c = t = t-r;
	e = t-q;
	va = v[A[i+1]];
	for (j = N-1; j >= 0; j--)
	{ if ((c = c - qr) > (e = e - r)) e = c;
	  if ((c = RR[j] - qr) > (d = SS[j] - r)) d = c;
	  DIAG(i+1+I, j+1+J, c, s+va[B[j+1]])
	  if (c < d) c = d;
	  if (c < e) c = e;
	  s = RR[j];
	  RR[j] = c;
	  SS[j] = d;
	}
    }
  SS[N] = RR[N];

  midc = CC[0]+RR[0];           /* Find optimal midpoint */
  midj = 0;
  type = 1;
  for (j = 0; j <= N; j++)
    if ((c = CC[j] + RR[j]) >= midc)
	if (c > midc || CC[j] != DD[j] && RR[j] == SS[j])
	{ midc = c;
	  midj = j;
	}
  for (j = N; j >= 0; j--)
    if ((c = DD[j] + SS[j] + q) > midc)
	{ midc = c;
	midj = j;
	type = 2;
	}
}

/* Conquer: recursively around midpoint */

  if (type == 1)
    { diff(A,B,midi,midj,tb,q);
	diff(A+midi,B+midj,M-midi,N-midj,q,te);
    }
  else
    { diff(A,B,midi-1,midj,tb,zero);
	DEL(2);
	diff(A+midi+1,B+midj,M-midi-1,N-midj,zero,te);
    }
  return midc;
}

/* Alignment display routine */