#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
#include<math.h>
#include<time.h>


struct TwoSequence
{
    char *sequence1[200];
    char *sequence2[200];
};


typedef struct
{
     int match;
     int mismatch;
     int open;
     int extend;
} Payoff;


Payoff gPayoff = { 1, -1, -1, -1 };


typedef struct Cell
{
     int          row;
     int          col;
     int          score;
     struct Cell *prev;
} Cell;


typedef struct
{
     Payoff   payoff;
     char    *sequence1;
     char    *sequence2;
     int      nRows;
     int      nCols;
     Cell   **ppCell;
} SW;


extern SW   *New      (char *sequence1, char *sequence2, Payoff payoff);
extern void  Delete   (SW *psw);
extern void  Score    (SW *psw);
extern void  DumpScore(SW *psw);

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

static void  AlignString(char *sequence1, char *sequence2, Payoff payoff);
static void  TimeTest();
static char *RandString (int n);


main()
{
        struct TwoSequence twosequence;

        int i;

            printf("\nEnter sequence 1 : ");
            gets(twosequence.sequence1);

            printf("\nEnter sequence 2 : ");
            gets(twosequence.sequence2);

            for (i=0; i<2; i++)
                AlignString(twosequence[i].sequence1, twosequence[i].sequence2, gPayoff);

            TimeTest();

            printf("\nThank You");

        return 0;
}


void AlignString(char *sequence1, char *sequence2, Payoff payoff)
{
     SW *psw = New(sequence1, sequence2, payoff);
     Score(psw);
     DumpScore(psw);
     Delete(psw);
}

*SW *New(char *sequence1, char *sequence2, Payoff payoff)
{
     int row, col;

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

     fprintf(stderr, "New");
     psw->payoff = payoff;
     psw->sequence1   = Unshift(sequence1, ' ');
     psw->sequence2   = Unshift(sequence2, ' ');

     psw->nRows  = strlen(psw->*sequence1);
     psw->nCols  = strlen(psw->*sequence2);

     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->sequence1);
     free(psw->sequence2);

     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->sequence1[row];
    fprintf(stderr, ".");

    for (col=1; col<psw->nCols; col++)
    {
         int   cB       = psw->sequence2[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->sequence2[col]);
     printf("\n");

     for (row=1; row<psw->nRows; row++)
     {
    printf("%3c", psw->sequence1[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;
}

void TimeTest()
{
     char *sequence1 = RandString(200);
     char *sequence2 = RandString(200);

     int start, end;
     SW *psw;

     start = time(0);

     psw = New(sequence1, sequence2, gPayoff);
     Score(psw);
     Delete(psw);

     end = time(0);
     printf("%d seconds\n", end-start);
}

char *RandString(int n)
{
     char *psz = (char *) malloc(n+1);
     int i;

     for (i=0; i<n; i++)
    psz[i] = ' ' + (rand() & 0x3f);

     psz[n] = 0;

     return psz;
}

main()
{
        //................

        return 0;
}

int main()
{
        //................

        return 0;
}

main()
{
        //................

        return 0;
}

int main()
{
        //................

        return 0;
}

#include <iostream>

main ()
{
    std::cout << "It doesn't compile\n";

    return 0;
}

#include <iostream.h>

main ()
{
    cout << "It doesn't compile\n";

    return 0;
}

struct TwoSequence
{
     char sequence1[200];
     char sequence2[200];
};

                
AlignString(twosequence.sequence1, twosequence.sequence2, gPayoff);

*SW *New(char *sequence1, char *sequence2, Payoff payoff)