/*-------------------------------------------------------------

Copyright (C) 2000 Peter Clote, Sebastian Will.
All Rights Reserved.

written by Peter Clote
modified by Sebastian Will

Permission to use, copy, modify, and distribute this
software and its documentation for NON-COMMERCIAL purposes
and without fee is hereby granted provided that this
copyright notice appears in all copies.


THE AUTHOR AND PUBLISHER MAKE NO REPRESENTATIONS OR
WARRANTIES ABOUT THE SUITABILITY OF THE SOFTWARE, EITHER
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHORS
AND PUBLISHER SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED
BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
THIS SOFTWARE OR ITS DERIVATIVES.

-------------------------------------------------------------*/

/*************************************************
   dotter.c
   
Outputs a dot plot for 2 sequences. This is the original
approach made by biologists towards identifying local
and global alignments between 2 sequences.

*************************************************/

#define MARK_DIAGONALS /* mark diagonals by DOT2 */

/* try define TAB 3 with MARK_DIAGONALS,
 without MARK_DIAGONALS TAB=2 may be more suitable*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SPACE ' '
#define DOT '*'
#define DOT2 '+'
#define N 1000
#define M 1000 /* N,M upper bounds on length of sequences a,b resp. */
#define TAB 3


/* Function prototypes */
void error ( char *s );   

void error ( char *s ) {
   fprintf(stderr,"%s\n",s);
   exit(1);
}



void display ( char *a, char *b, char s[N][M]){

   int i,j,k,n,m;

   n=strlen(a);
   m=strlen(b);


   /****************** print letters of string b ***********/
   printf("%c",SPACE);
   for (j=0;j<m;j++) { 
      for (k=0;k<TAB;k++) printf(" ");
      printf("%c",b[j]);
      }
   printf("\n");


   /********************* print dot array ************/
   for (i=0;i<n;i++) {
      printf("%c",a[i]);
      for (j=0;j<m;j++) {
         for (k=0;k<TAB;k++) printf(" ");
         printf("%c",s[i][j]);
         }
      printf("\n");

#ifdef MARK_DIAGONALS
      if (i<n-1) {
	for (k=0;k<=TAB/2+1;k++) printf(" ");
	for (j=0;j<m-1;j++) {
	  for (k=0;k<TAB;k++) printf(" ");
	  if (s[i][j]==DOT && s[i+1][j+1]==DOT) printf("%c",DOT2); else printf("%c",SPACE);
	}
	printf("\n");
      }
#endif
   }
}




main(int argc, char *argv[]) {
   char *a, *b;
   int n,m,i,j;
   char s[N][M];
   if ( argc != 3 )
      error("Usage: dotter sequence1 sequence2\n");

   a = argv[1];
   b = argv[2];
   n = strlen(a);
   m = strlen(b);

   /*************************** fill dot array *******/
   for (i=0;i<n;i++)
      for (j=0;j<m;j++)
         if (a[i] == b[j])
            s[i][j] = DOT;
         else
            s[i][j] = SPACE;
   
   display(a,b,s); 
}


/*------------------------------------------------------------------
Sample run:
  where
  #undef MARK_DIAGONALS
  #define TAB 2

% a.out GCGGGGGTCGCCAAGCCAG CGCGGGGTACCGGGCTTGG


   C  G  C  G  G  G  G  T  A  C  C  G  G  G  C  T  T  G  G
G     .     .  .  .  .              .  .  .           .  .
C  .     .                    .  .           .
G     .     .  .  .  .              .  .  .           .  .
G     .     .  .  .  .              .  .  .           .  .
G     .     .  .  .  .              .  .  .           .  .
G     .     .  .  .  .              .  .  .           .  .
G     .     .  .  .  .              .  .  .           .  .
T                       .                       .  .
C  .     .                    .  .           .
G     .     .  .  .  .              .  .  .           .  .
C  .     .                    .  .           .
C  .     .                    .  .           .
A                          .
A                          .
G     .     .  .  .  .              .  .  .           .  .
C  .     .                    .  .           .
C  .     .                    .  .           .
A                          .
G     .     .  .  .  .              .  .  .           .  .

------------------------------------------------------------------*/