/*
 * Simple minded guitar chords
 *
 *  4 Mar 97  Erich Rickheit KSC     Created
 * 18 Apr 97  Erich Rickheit KSC     More chords; recursive descent parser
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <ctype.h>

char notenames[12][4] = {
  "c--", "c#-", "d--", "d#-", "e--", "f--",
  "f#-", "g--", "g#-", "a--", "a#-", "b--",
};

               /*    A  B   C  D  E  F  G  */
int notebyname[] = { 9, 11, 0, 2, 4, 5, 7, };
int intervals[][24] = {
                /*      1  2  3  4  5  6    7   8   9  10  11  12  13  14 */
     /* major */ { -1,  0, 2, 4, 5, 7, 9,  11, 12, 14, 16, 17, 19, 21, 23, 24 },
     /* minor */ { -1,  0, 1, 3, 4, 6, 8,  10, 12, 13, 14, 16, 19, 20, 22, 24 },
 /* augmented */ { -1,  1, 3, 5, 6, 8, 10, 12, 13, 15, 17, 18, 20, 22, 24, 25 },
/* diminished */ { -1, -1, 0, 2, 4, 6, 7,   9, 11, 12, 14, 16, 18, 19, 21, 23 },
};

struct note { int interval, type, val; };
#define TPERFECT    0
#define TMAJOR      0
#define TMINOR      1
#define TAUGMENTED  2
#define TDIMINISHED 3

/* attributes of the instrument - can be command line arguments */
#define MAXSTR 64
int   fingerct = 4;
int   fretreach = 3;
int   ignorestring = 2;
int   stringct = 6;
int   stringbase[MAXSTR] = { 4,   11,  7,   2,   9,   4 };
char *stringname[MAXSTR] = {"E", "B", "G", "D", "A", "E" };
int   rootonlow = 0;

char chordname[64];

char *ords(i)
{
  if (i > 3 && i < 21) return "th";
  i%=10;
  if (i==1) return "st";
  if (i==2) return "nd";
  if (i==3) return "rd";
  return "th";
}

struct note notes[128];
int notect = 0;
int basenote = -1;
char basename[4];
int rootnote = -1;
int rootchar = 'C';
int fretted[64];
void draw_chord();
int do_string(int);
int printstyle = 1;

char *nn(n)
  struct note *n;
{ int c, v;
  static char buf[10];
  char *p = buf;

  /* first, the note */
  *p = rootchar + n->interval -1;
  while (*p > 'G') *p-=7;

  /* base value for that note */
  c = notebyname[*p - 'A'];

  /* how far is the value from the base value for that note? */
  v = rootnote + intervals[n->type][n->interval];
  while (v<0)  v += 12;
  while (v>11) v -= 12;

  /* put in the appropriate flats, sharps */
    switch (v -c)
    {
      case -2: case 10:
        p[1] = 'b'; p[2] = 'b';
        p += 2;
        break;
      case -1: case 11:
        p[1] = 'b';
        p++;
        break;
      case  0:
        break;
      case  1: case -11:
        p[1] = '#';
        p++;
        break;
      case  2: case -10:
        p[1] = '#';
        p[2] = '#';
        p += 2;
        break;
      default:
        fprintf(stderr, "Shit, _I_ dunno\n");
        return "?";
    }
    p++; *p =0;


  return buf;
}

char err[1024];
char *inp;

int main(int argc, char *argv[])
{ char buf[1024];
  int  c;

  /* parse command line here */
  while ((c = getopt(argc, argv, "bf:i:p:r:t:")) != EOF)
    switch (c)
    {
      case 'b':
	rootonlow = 1;
	break;
      case 'f':
	if (!(c = atoi(optarg))) usage();
	fingerct = c;
	break;
      case 'i':
	if (!(c = atoi(optarg))) c = 10000;
	ignorestring = c;
	break;
      case 'p':
	if (!(c = atoi(optarg))) usage();
	printstyle = c;
	break;
      case 'r':
	if (!(c = atoi(optarg))) usage();
	fretreach = c;
	break;
      case 't':
	/* a list of strings, lowest to highest */
	stringct = 0;
	while (stringct < MAXSTR)
	{
	  inp = optarg;
	  if ((c = Pnote()) < 0) usage();

	  /* push the others along... */
	  memmove(stringbase+1, stringbase, stringct*sizeof(int));
	  memmove(stringname+1, stringname, stringct*sizeof(char *));

	  /* so we can fit this at the beginning */
	  stringbase[0] = c;
	  stringname[0] = optarg;
	  stringct++;

	  /* get the next one */
	  if (optind >= argc) break;
	  optarg = argv[optind++];
	  if (!optarg || !isalpha(*optarg)) break;
	}
	break;
      case '?': default: usage();
    }

  /* fix the sense of ignorestring; we label strings backwards, here */
  ignorestring = stringct - ignorestring;

  if (optind < argc)
  {
    buf[0] = 0;
    while (optind<argc) strcat(buf, argv[optind++]);
    dochord(buf);
  }
  else
  { int prompt = 0;

    if (isatty(0))
    {
      printf("-> ");
      prompt = 1;
    }
    while (fgets(buf, 1023, stdin))
    {
      dochord(buf);
      if (prompt) printf("\n-> ");
    }
  }
  return 0;
}

dochord(char *buf)
{ char *s, *d, *p;
  int i;

  /* save the original */
  p = chordname;

  /* trim out ws & normalize case */
  for (s=d=buf; *s; s++)
  {
    if (isspace(*s)) continue;
    *p++ = *s;
    if (isupper(*s)) *d = tolower(*s);
    else *d = *s;
    d++;
  }
  *d = 0; *p = 0;

  if (!*buf) return; /* just ignore blank lines */

  if (!Pchord(buf))
    fprintf(stderr, "Error parsing chord %s: %s\n", buf, err);

  /*
  printf("root = %d base = %d\n", rootnote, basenote);
  for (i=0; i<notect; i++)
    printf("i: %d; t: %d; v: %d (%s)\n", notes[i].interval, notes[i].type,
      rootnote + intervals[notes[i].type][notes[i].interval], nn(notes+i));
  */

  /* normalize the base note */
  while (basenote < 0)  basenote += 12;
  while (basenote > 11) basenote -= 12;

  /* now figure values for each of those notes */
  for (i=0; i<notect; i++)
  {
    notes[i].val = rootnote + intervals[notes[i].type][notes[i].interval];
    while (notes[i].val < 0)  notes[i].val += 12;
    while (notes[i].val > 11) notes[i].val -= 12;

    /* and set the notename for that */
    d = nn(notes+i);
    strncpy(notenames[notes[i].val], d, strlen(d));

    /* do we have the base note? */
    if (notes[i].val == basenote) basename[0] = 0;
  }

  /* found the base note yet? */
  if (basename[0])
  {
    notes[notect].val = basenote;
    strncpy(notenames[basenote], basename, strlen(basename));
    notect++;
  }

  /* go find that chord on the instrument */
  for (i=0; i<stringct; i++) fretted[i] = -1;
  do_string(0);
  flush_print();
}

/* a recursive-descent parser for chord names */

int Pchord(char *s)
{ int note, res;
  char *p;

  /* start at the beginning of the string */
  inp = s;
  notect = 0;
  basenote = rootnote = -1;

  if ((note = Pnote()) < 0) return 0;
  rootchar = toupper(*s);

  /* use that note to build the major triad */
  notect = 3;
  rootnote = note;
  notes[0].interval = 1; notes[0].type = TPERFECT;
  notes[1].interval = 3; notes[1].type = TMAJOR;
  notes[2].interval = 5; notes[2].type = TPERFECT;

  if (Pminor() < 0) return 0;
  if (!Pmods()) return 0;
  p = inp;
  if ((res = Pbase()) < 0) return 0;
  if (res)
  {
    memcpy(basename, p+1, inp-p);
    for (p=basename; *p; p++)
      if (islower(*p)) *p = toupper(*p);
  }
  if (*inp)
  {
    sprintf(err, "String not parsed: %s", inp);
    return 0;
  }

  if (basenote <0) basenote = rootnote;
  return 1;
}

/* looks for a note; returns its numeric value or -1 */
int Pnote()
{ int note;

  if (*inp >= 'A' && *inp <='G') *inp += 'a'-'A';
  if (*inp < 'a' || *inp >'g')
  {
    sprintf(err, "%c is not a valid note name", *inp);
    return -1;
  }

  note = notebyname[*inp - 'a'];
  inp++;

  /* look for an optional group of sharps or flats */
  if (*inp == 'b' || *inp == '!')
  {
    while (*inp == 'b' || *inp == '!')
      { inp++; note--; if (note<0) note += 12; }
  }
  else if (*inp == '#')
  {
    while (*inp == '#')
      { inp++; note++; if (note>11) note -= 12; }
  }

  return note;
}

/* look for a minor key for the chord */
int Pminor()
{ int i;

  if (*inp != 'm') return 0;

  /* don't be fooled by a 'maj' */
  if (inp[1] == 'a' && inp[2] == 'j') return 0;

  /* but accept 'min' */
  inp++;
  if (inp[0] == 'i' && inp[1] == 'n') inp += 2;

  /* and turn a major third into a minor third */
  for (i=0; i<notect; i++)
    if (notes[i].interval == 3)
      { notes[i].type = TMINOR; break; }

  return 1;
}

/* just a list of zero or more mods; give up if one returns an error */
int Pmods()
{ int res;
  while (res = Pmod())
    if (res < 0) return 0;
  return 1;
}

int Pmod()
{ int n,i;

  switch (*inp)
  {
    case 'a':
      if (!strncmp(inp, "add", 3))
      {
        inp+=3;
        if (!(n = Pnum()))
          { sprintf(err, "No interval to add"); return -1; }

        for (i=0; i<notect; i++)
          if (notes[i].interval == n)
          {
            sprintf(err, "%d%s interval already in chord", n, ords(n));
            return -1;
          }
        notes[notect].interval = n; notes[notect].type = TMAJOR;
        notect++;
        return 1;
      }

      if (strncmp(inp, "aug", 3)) return 0;
      inp += 2;  /* same as the two cases below */
    case '+':
    case '#':  /* augmented interval */
      inp++;
      if (!(n = Pnum())) n=5;
      if (n > 15)
        { sprintf(err, "interval out of range: %d", n); return -1; }

      /* see if that interval is already in the chord */
      for (i=0; i<notect; i++)
      {
        if (notes[i].interval == n)
          { notes[i].type = TAUGMENTED; return 1; }  /* so augment it */
      }
      /* nope, gotta add it */
      notes[notect].interval = n; notes[notect].type = TAUGMENTED;
      notect++;
      break;

    case '-':
    case 'b': /* diminished interval */
      inp++;
      if (!(n = Pnum())) n=5;
      if (n > 15)
        { sprintf(err, "interval out of range: %d", n); return -1; }

      /* see if that interval is already in the chord */
      for (i=0; i<notect; i++)
      {
        if (notes[i].interval == n)
          { notes[i].type = TMINOR; return 1; }  /* so diminish it */
      }
      /* nope, gotta add it */
      notes[notect].interval = n; notes[notect].type = TMINOR;
      notect++;
      break;

    case 'd':

      if (!strncmp(inp, "dim", 3)) /* diminished, as above... */
      {
        inp+=3;
        if (!(n = Pnum())) /* no number means a dimished chord */
        {
          /* minor third */
          for (i=0; i<notect; i++)
          {
            if (notes[i].interval == 3)
              { notes[i].type = TMINOR; break; }
          }

          /* diminished 5th */
          for (i=0; i<notect; i++)
          {
            if (notes[i].interval == 5)
              { notes[i].type = TDIMINISHED; break; }
          }

          /* diminished 7th */
          for (i=0; i<notect; i++)
          {
            if (notes[i].interval == 7)
              { notes[i].type = TDIMINISHED; return 0; }
          }
          /* nope, gotta add it */
          notes[notect].interval = 7; notes[notect].type = TDIMINISHED;
          notect++;

          return 0;
        }

        if (n > 15)
          { sprintf(err, "interval out of range: %d", n); return -1; }

        /* see if that interval is already in the chord */
        for (i=0; i<notect; i++)
        {
          if (notes[i].interval == n)
            { notes[i].type = TDIMINISHED; return 1; }  /* so diminish it */
        }
        /* nope, gotta add it */
        notes[notect].interval = n; notes[notect].type = TDIMINISHED;
        notect++;
        break;
      }

      return 0;
    case '1': case '2': case '3': case '4': case '5':
    case '6': case '7': case '8': case '9':
      n = Pnum();

      if (n>=7) /* me must have a (minor) 7th */
      {
        for (i=0; i<notect; i++)
          if (notes[i].interval == 7) break;
        if (i >= notect)
        {
          notes[notect].interval = 7; notes[notect].type = TMINOR;
          notect++;
        }
      }

      /* make sure that interval is in the chord */
      for (i=0; i<notect; i++)
        if (notes[i].interval == n) return 1;
      /* not there; add it */
      notes[notect].interval = n; notes[notect].type = TMAJOR;
      notect++;

      /* special case: 6/9 chords */
      if (n==6 && !strncmp(inp, "/9", 2))
      {
        inp += 2;
        /* add a ninth */
        for (i=0; i<notect; i++)
          if (notes[i].interval == 9) return 1;
        /* not there; add it */
        notes[notect].interval = 9; notes[notect].type = TMAJOR;
        notect++;
      }

      break;
    case 'm':

      if (!strncmp(inp, "maj", 3)) /* major interval */
      {
        inp+=3;
        if (!(n = Pnum())) n=7;
        if (n > 15)
          { sprintf(err, "interval out of range: %d", n); return -1; }

        /* see if that interval is already in the chord */
        for (i=0; i<notect; i++)
        {
          if (notes[i].interval == n)
            { notes[i].type = TMAJOR; return 1; }
        }
        /* nope, gotta add it */
        notes[notect].interval = n; notes[notect].type = TMAJOR;
        notect++;
        break;
      }

      return 0;
    case 's':
      if (!strncmp(inp, "sus", 3))
      {
        inp+=3;
        if (*inp == 'p') inp++; /* some write 'susp' */
        if (!(n = Pnum())) n=4;

        /* replace the third with the new interval */
        for (i=0; i<notect; i++)
          if (notes[i].interval == 3)
            { notes[i].interval = n; return 1;}
        sprintf(err, "No third to suspend");
        return -1;
      }

      return 0;
    case '/':
      /* might not be a mod, but a base note */
      if (inp[1] >= 'a' && inp[1]<='g') return 0;
      inp++;
      return Pmod();
    case '(':
      inp++;
      if (!Pmods()) return -1;
      if (*inp != ')')
        { sprintf(err, "Unbalanced paren"); return -1; }
      inp++;
      break;

    default: return 0;
  }

  return 1;
}

/* see if we've specified a root note */
int Pbase()
{ int i;

  if (*inp != '/') return 0;
  inp++;

  /* only one is allowed */
  if (basenote>=0)
  {
    sprintf(err, "base note is already set: %d", basenote);
    return -1;
  }

  /* get the note in question */
  if ((basenote = Pnote()) < 0) return -1;

  return 1;
}

int Pnum()
{ int val = 0;
  if (*inp < '1' || *inp > '9') return 0;

  while (isdigit(*inp))
  {
    val = 10*val + (*inp -'0');
    inp++;
  }

  return val;
}

int do_string(int string)
{ int note, pos, i;
  int success = 0;

  if (string < stringct)
  {
    for (note=0; note<notect; note++)
    {
      /* find the note on this string */
      pos = notes[note].val - stringbase[string];

      /* normalize to the first octave */
      while (pos < 0)  pos += 12;
      while (pos > 11) pos -= 12;

      /* check through a couple octaves */
      for (; pos < 11; pos+=12)
      {
        /* fail if more than three other strings are fretted */
        if (pos)
        { int count;

          for (i=count=0; i<string; i++)
            if (fretted[i]) count++;
          if (count > fingerct-1)
          { /* fails for an open chord--how about a barre chord? */
            int failure = 0, mn=pos;

            /* find the lowest non-open string; that's the barre */
            for (i=0; i<string; i++)
            {
              if (!fretted[i])  /* but can't have any open strings */
                { failure = 1; break; }
              if (fretted[i] < mn) mn = fretted[i];
            }
            if (failure || !mn) continue;

            /* now count frets above the barre */
            for (i=count=0; i<string; i++)
              if (fretted[i] > mn) count++;
            if (pos>mn) count++;
            /* fail if that's too many fingers */
            if (count > fingerct-1) continue;
          }
        }

        /* fail if reach of frets is too great */
        if (pos)
        { int mx, mn;

          mx = mn = pos;
          for (i=0; i<string; i++)
          {
            if (fretted[i] && fretted[i]>mx) mx=fretted[i];
            if (fretted[i] && fretted[i]<mn) mn=fretted[i];
          }
          if (mx -mn >= fretreach) continue;
        }

        /* seems to be successful */
        fretted[string] = pos;
        success = do_string(string+1);
        fretted[string] = -1;
      }
    }
    if (success) return 1;
    if (string >= ignorestring)
    {
      for (i=string; i<stringct; i++)
        fretted[i] = -1;
    }
    else return 0;
  }

  /* this may be a good chord; see if every note in the chord is played */
  for (note=0; note<notect; note++)
  {
    success = 0;
    for (i=0; i<string; i++)
    {
      pos = stringbase[i] + fretted[i];
      if ((pos%12) == (notes[note].val%12))
        { success=1; break; }
    }
    if (!success) return 0;
  }

  /* see if this string (the lowest) is the base note */
  if (rootonlow)
  {
    pos = (stringbase[string-1] + fretted[string-1])%12;
    if (pos != basenote) return 0;
  }

  /* looks good! draw the chord */
  draw_chord();
  return 1;
}


void draw_reg_chord()
{ int   i, j, min, max, pos;

  /* find the range of frets */
  min = 1000; max = 0;
  for (i=0; i<stringct; i++)
  {
    if (fretted[i]>0 && fretted[i]>max) max=fretted[i];
    if (fretted[i]>0 && fretted[i]<min) min=fretted[i];
  }
  if (min <= 2) min = 1;

  if (min >1) printf("     %d", min);
  putchar('\n');
  for (i=0; i<stringct; i++)
  {
    printf("%-2.2s", stringname[i]);
    if (fretted[i] <0)   putchar('X');
    else if (fretted[i]) putchar('|');
    else                 putchar('0');
    for (j=min; j<=max; j++)
    {
      putchar('-');
      if (j==fretted[i])
      {
        pos = (stringbase[i] + fretted[i])%12;
        fputs(notenames[pos], stdout);
      }
      else fputs("---", stdout);
      putchar('|');
    }
    putchar('\n');
  }
  putchar('\n');
}

void draw_tab_chord(int flush)
{ static char **out = 0;
  static int    len = 2;
  int           i, td=0;
  
  /* allocate space for the output */
  if (!out)
  {
    if (!(out = (char **)malloc(stringct *sizeof(char *)))) return;
    for (i=0; i<stringct; i++)
    {
      if (!(out[i] = (char *)malloc(80))) return;
      out[i][0] = '-'; out[i][1] = '-'; out[i][2] = 0;
    }
  }

  /* just flush the output? */
  if (flush || len > 75)
  {
    for (i=0; i<stringct; i++)
    {
      puts(out[i]);
      out[i][0] = '-'; out[i][1] = '-'; out[i][2] = 0;
    }
    len = 2;
    if (flush) return;
    putchar('\n');
  }

  /* see if any strings will need two digits;
    we just won't work for instruments with 100+ frets, sorry. */
  for (i=0; i<stringct; i++) if (fretted[i] >=10) td++;
  if (td) len++;

  /* and add the frets to the end of the string */
  for (i=0; i<stringct; i++)
  {
    if (td)
    {
      if (fretted[i] < 10) out[i][len-1] = '-';
      else out[i][len-1] = '0' + (fretted[i]/10);
    }
    if (fretted[i] < 0) out[i][len] = '-';
    else out[i][len] = '0' + (fretted[i]%10);
    out[i][len+1] = '-';
    out[i][len+2] = '-';
    out[i][len+3] = 0;
  }
  len += 3;

}

void draw_shp_chord()
{ int i;

  for (i=stringct-1; i>=0; i--)
  {
    if (fretted[i] < 0) printf("  X");
    else printf("%3d", fretted[i]);
  }
  printf("\n");
}

void draw_chp_chord()
{ int   i, min, max;

  /* find the range of frets */
  min = 1000; max = 0;
  for (i=0; i<stringct; i++)
  {
    if (fretted[i]>0 && fretted[i]>max) max=fretted[i];
    if (fretted[i]>0 && fretted[i]<min) min=fretted[i];
  }
  if (max <= 4) min = 1;

  fputs(chordname, stdout);
  for (i=stringct-1; i>=0; i--)
  {
    if (fretted[i] <0)   fputs(" x", stdout);
    else if (fretted[i]) printf(" %d", fretted[i]-min+1);
    else                 fputs(" 0", stdout);
  }
  printf(" %d\n", min);
}

usage()
{
  fputs(
"usage: ch [-b] [-f #] [-i #] [-p #] [-r #] [-t str str str.] [chord]\n"
  , stderr);
  exit(1);
}

void draw_chord()
{
  switch (printstyle)
  {
    case 1: draw_reg_chord();  break;
    case 2: draw_tab_chord(0); break;
    case 3: draw_shp_chord();  break;
    case 4: draw_chp_chord();  break;
    default:
      fprintf(stderr, "Unknown print style; using default...\n");
      printstyle = 1;
      draw_chord();
  }
}

flush_print()
{
  switch (printstyle)
  {
    case 2: draw_tab_chord(1); break;
    default: break;
  }
}