/*****************************************************************************/
/* align.c
/* Scores a 200x200 matrix in 3 seconds */
/*****************************************************************************/

#include "align.h"
#include <stdio.h>
#include <string.h>
#include <assert.h>


static char *Unshift(char *pszSource, int c);


SW *New(char *pszA, char *pszB, Payoff payoff)
{
    int row, col;

    SW *psw = (SW *) malloc(sizeof (SW));

    fprintf(stderr, "New");
    psw->payoff = payoff;
    psw->pszA   = Unshift(pszA, ' ');
    psw->pszB   = Unshift(pszB, ' ');

    psw->nRows  = strlen(psw->pszA);
    psw->nCols  = strlen(psw->pszB);

    psw->ppCell = (Cell**) malloc(psw->nRows * sizeof (Cell *));

    for (row=0; row<psw->nRows; row++)
    {
	fprintf(stderr, ".");
	psw->ppCell[row] = (Cell *) malloc(psw->nCols * sizeof(Cell));

	for (col=0; col<psw->nCols; col++)
	{
	    Cell *pCell = &psw->ppCell[row][col];
	    pCell->row   = row;
	    pCell->col   = col;
	    pCell->score = 0;
	    pCell->prev  = 0;
	}
    }

    fprintf(stderr, "\n");
    return psw;
}


void Delete(SW *psw)
{
    int row;

    free(psw->pszA);
    free(psw->pszB);

    for (row=0; row<psw->nRows; row++)
	free(psw->ppCell[row]);

    free(psw);
}


void Score(SW *psw)
{
    int row, col;

    Payoff payoff = psw->payoff;
    fprintf(stderr, "Score");

    for (row=1; row<psw->nRows; row++)
    {
	int cA = psw->pszA[row];
	fprintf(stderr, ".");

	for (col=1; col<psw->nCols; col++)
	{
	    int   cB       = psw->pszB[col];
	    int   pay      = cA==cB ? payoff.match : payoff. mismatch;
	    int   ulScore  = psw->ppCell[row-1][col-1].score;

	    int   maxScore = ulScore + pay;
	    Cell* pCell    = &psw->ppCell[row-1][col-1];

	    int r, c;
	    for (r=0; r<row; r++)
	    {
		int uScore   = psw->ppCell[r][col].score;
		int gapScore = uScore + payoff.open + payoff.extend * (row-r);
		if (gapScore < maxScore) continue;

		maxScore = gapScore;
		pCell    = &psw->ppCell[r][col];		
	    }

	    for (c=0; c<col; c++)
	    {
		int lScore   = psw->ppCell[row][c].score;
		int gapScore = lScore + payoff.open + payoff.extend * (col-c);
		if (gapScore < maxScore) continue;

		maxScore = gapScore;
		pCell    = &psw->ppCell[row][c];		
	    }

	    psw->ppCell[row][col].score = maxScore;
	    psw->ppCell[row][col].prev  = pCell;
	}
    }
    fprintf(stderr, "\n");
}


void DumpScore(SW *psw)
{
    int row, col;

    printf("   ");
    for (col=1; col<psw->nCols; col++)
	printf("%3c", psw->pszB[col]);
    printf("\n");

    for (row=1; row<psw->nRows; row++)
    {
	printf("%3c", psw->pszA[row]);
	for (col=1; col<psw->nCols; col++)
	    printf("%3d", psw->ppCell[row][col].score);
	printf("\n");
    }
}


char *Unshift(char *pszSource, int c)
{
    int n = strlen(pszSource);
    char *pszDest = (char *) malloc(n+2);
    assert(pszDest);
    pszDest[0] = c;
    strcpy(pszDest+1, pszSource);
    return pszDest;
}