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

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


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


/*****************************************************************************
 * PAYOFF
 *****************************************************************************/
Payoff *payoff_new(int match, int mismatch, int open, int extend)
{
    Payoff *pPayoff = (Payoff *) malloc(sizeof (Payoff));

    pPayoff->match    = match;
    pPayoff->mismatch = mismatch;
    pPayoff->open     = open;
    pPayoff->extend   = extend;

    return pPayoff;
}


void payoff_DESTROY(Payoff *pPayoff)
{
    free(pPayoff);
}


/*****************************************************************************
 * CELL
 *****************************************************************************/
int   cell_row  (Cell *pCell) { return pCell->row;   }
int   cell_col  (Cell *pCell) { return pCell->col;   }
int   cell_score(Cell *pCell) { return pCell->score; }
Cell *cell_prev (Cell *pCell) { return pCell->prev;  }


/*****************************************************************************
 * MATRIX
 *****************************************************************************/
Matrix *matrix_new(char *pszA, char *pszB, Payoff *pPayoff)
{
    int row, col;

    Matrix *pMatrix = (Matrix *) malloc(sizeof (Matrix));

    /* fprintf(stderr, "New"); */

    pMatrix->payoff = *pPayoff;
    pMatrix->pszA   = Unshift(pszA, ' ');
    pMatrix->pszB   = Unshift(pszB, ' ');

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

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

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

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

    /* fprintf(stderr, "\n"); */
    return pMatrix;
}


void matrix_DESTROY(Matrix *pMatrix)
{
    int row;

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

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

    free(pMatrix);
}


void matrix_score(Matrix *pMatrix)
{
    int row, col;

    Payoff payoff = pMatrix->payoff;
    /* fprintf(stderr, "Score"); */

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

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

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

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

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

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

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

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


void matrix_dump(Matrix *pMatrix)
{
    int row, col;

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

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


extern Cell *matrix_cell(Matrix *pMatrix, int nRow, int nCol)
{
    return &pMatrix->ppCell[nRow][nCol];
}


/*****************************************************************************
 * STATIC FUNCTIONS
 *****************************************************************************/
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;
}