#ifndef _ALIGN_STANDARD_UTIL_H_
#define _ALIGN_STANDARD_UTIL_H_

#ifndef MAX
#define MAX(X, Y)   (((X) > (Y))? (X): (Y))
#endif

#ifndef MIN
#define MIN(X, Y)   (((X) < (Y))? (X): (Y))
#endif

typedef struct {
        int pos[2];
} ALN;

typedef struct {
        int  AlignLength;
        ALN  *aln;
} ALIGN;

typedef struct llist {
        int tm, tn;
        struct llist *next;
} LIST;

typedef struct {
        int  m,  n;
        int  pp;
} SAVE;

typedef struct {
        float val;
        int   ptr;
} RECD;

static int   Size_dr = 0;
static SAVE  *dr = NULL;
static int   i_record = -1;

static char AA[22] = "ARNDCQEGHILKMFPSTWYVX";

static float matrix[21][21] = {
   {  4, -1, -2, -2,  0, -1, -1,  0, -2, -1, -1, -1, -1, -2, -1,  1,  0, -3, -2,  0,  0 },
   { -1,  5,  0, -2, -3,  1,  0, -2,  0, -3, -2,  2, -1, -3, -2, -1, -1, -3, -2, -3, -1 },
   { -2,  0,  6,  1, -3,  0,  0,  0,  1, -3, -3,  0, -2, -3, -2,  1,  0, -4, -2, -3, -1 },
   { -2, -2,  1,  6, -3,  0,  2, -1, -1, -3, -4, -1, -3, -3, -1,  0, -1, -4, -3, -3, -1 },
   {  0, -3, -3, -3,  9, -3, -4, -3, -3, -1, -1, -3, -1, -2, -3, -1, -1, -2, -2, -1, -2 },
   { -1,  1,  0,  0, -3,  5,  2, -2,  0, -3, -2,  1,  0, -3, -1,  0, -1, -2, -1, -2, -1 },
   { -1,  0,  0,  2, -4,  2,  5, -2,  0, -3, -3,  1, -2, -3, -1,  0, -1, -3, -2, -2, -1 },
   {  0, -2,  0, -1, -3, -2, -2,  6, -2, -4, -4, -2, -3, -3, -2,  0, -2, -2, -3, -3, -1 },
   { -2,  0,  1, -1, -3,  0,  0, -2,  8, -3, -3, -1, -2, -1, -2, -1, -2, -2,  2, -3, -1 },
   { -1, -3, -3, -3, -1, -3, -3, -4, -3,  4,  2, -3,  1,  0, -3, -2, -1, -3, -1,  3, -1 },
   { -1, -2, -3, -4, -1, -2, -3, -4, -3,  2,  4, -2,  2,  0, -3, -2, -1, -2, -1,  1, -1 },
   { -1,  2,  0, -1, -3,  1,  1, -2, -1, -3, -2,  5, -1, -3, -1,  0, -1, -3, -2, -2, -1 },
   { -1, -1, -2, -3, -1,  0, -2, -3, -2,  1,  2, -1,  5,  0, -2, -1, -1, -1, -1,  1, -1 },
   { -2, -3, -3, -3, -2, -3, -3, -3, -1,  0,  0, -3,  0,  6, -4, -2, -2,  1,  3, -1, -1 },
   { -1, -2, -2, -1, -3, -1, -1, -2, -2, -3, -3, -1, -2, -4,  7, -1, -1, -4, -3, -2, -2 },
   {  1, -1,  1,  0, -1,  0,  0,  0, -1, -2, -2,  0, -1, -2, -1,  4,  1, -3, -2, -2,  0 },
   {  0, -1,  0, -1, -1, -1, -1, -2, -2, -1, -1, -1, -1, -2, -1,  1,  5, -2, -2,  0,  0 },
   { -3, -3, -4, -4, -2, -2, -3, -2, -2, -3, -2, -3, -1,  1, -4, -3, -2, 11,  2, -3, -2 },
   { -2, -2, -2, -3, -2, -1, -2, -3,  2, -1, -1, -2, -1,  3, -3, -2, -2,  2,  7, -1, -1 },
   {  0, -3, -3, -3, -1, -2, -2, -3, -3,  3,  1, -2,  1, -1, -2, -2,  0, -3, -1,  4, -1 },
   {  0, -1, -1, -1, -2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -2,  0,  0, -2, -1, -1, -1 }
};

static int  *_indexa = NULL, *_indexb = NULL;

static void print_alignment(FILE *fp, ALIGN *ss, const char *_seqa, const char *_seqb);
static float score(const int k, const int l);
static int find_index(char aa);
static ALIGN *alignment_standard(ALIGN *sa, ALIGN *sb, const float vv, const float uu,
		          float (*score)(const int, const int));
static int dynamic(ALIGN *sa, ALIGN *sb, const float vv, const float uu,
               float (*score)(const int, const int));
static ALIGN *mu_trcback(const int origin, ALIGN *a, ALIGN *b);
static int adr(int m, int n, int pp);
static void track(ALIGN *aa, LIST *top, ALIGN *sa, ALIGN *sb);
static LIST *mid_insert(LIST *top, LIST *insert, LIST *last);
static void delete_list(LIST *node);

#endif