/* queues.c
 * This file is part of the code for abc2midi.
 * Notes due to finish in the future are held in a queue (linked list)
 * in time order. Qhead points to the head of the list and addtoQ() 
 * adds a note to the list. The unused elements of array Q are held
 * in another linked list pointed to by freehead. The tail is pointed
 * to by freetail. removefromQ() removes an element (always from the
 * head of the list) and adds it to the free list. Qinit() initializes
 * the queue and clearQ() outputs all the remaining notes at the end
 * of a track.
 * Qcheck() and PrintQ() are diagnostic routines.
 */

/* queue for notes waiting to end */
/* allows us to do general polyphony */
#define QSIZE 50
struct Qitem {
  int delay;
  int pitch;
  int chan;
  int next;
};
struct Qitem Q[QSIZE+1];
int Qhead, freehead, freetail;
extern long delta_time, tracklen;
extern int div_factor;

/* routines to handle note queue */

addtoQ(num, denom, pitch, chan, d)
int num, denom, pitch, chan, d;
{
  int i, done;
  int wait;
  int *ptr;

  wait = ((div_factor*num)/denom) + d;
  /* find free space */
  if (freehead == -1) {
    printQ();
    event_fatal_error("Note off queue overflow");
  } else {
    i = freehead;
    freehead = Q[freehead].next;
  };
  Q[i].pitch = pitch;
  Q[i].chan = chan;
  /* find place in queue */
  ptr = &Qhead;
  done = 0;
  while (!done) {
    if (*ptr == -1) {
      *ptr = i;
      Q[i].next = -1;
      Q[i].delay = wait;
      done = 1;
    } else {
      if (Q[*ptr].delay > wait) {
        Q[*ptr].delay = Q[*ptr].delay - wait;
        Q[i].next = *ptr;
        Q[i].delay = wait;
        *ptr = i;
        done = 1;
      } else {
        wait = wait - Q[*ptr].delay;
        ptr = &Q[*ptr].next;
      };
    };
  };
}

removefromQ(i)
int i;
{
  if (i == -1) {
    printQ();
    event_fatal_error("Internal error - nothing to remove from queue");
  } else {
    if (Q[Qhead].delay != 0) {
    printQ();
      event_fatal_error("Internal error - queue head has non-zero time");
    };
    Qhead = Q[i].next;
    Q[i].next = freehead;
    freehead = i;
  };
}

clearQ()
{
  int time;
  int i;

  /* remove gchord requests */
  time = 0;
  while ((Qhead != -1) && (Q[Qhead].pitch == -1)) {
    time = time + Q[Qhead].delay;
    i = Qhead;
    Qhead = Q[i].next;
    Q[i].next = freehead;
    freehead = i;
  };
  if (Qhead != -1) {
    timestep(time, 1);
  };
  /* do any remaining note offs, but don't do chord request */
  while (Qhead != -1) {
    event_error("Sustained notes beyond end of track");
    timestep(Q[Qhead].delay+1, 1);
  };
}

printQ()
{
  int t;

  printf("Qhead = %d freehead = %d freetail = %d\n", 
         Qhead, freehead, freetail);
  t = Qhead;
  printf("Q:");
  while (t != -1) {
    printf("p(%d)-%d->", Q[t].pitch, Q[t].delay);
    t = Q[t].next;
  };
  printf("\n");
}

advanceQ(t)
int t;
{
  if (Qhead == -1) {
    event_error("Internal error - empty queue");
  } else {
    Q[Qhead].delay = Q[Qhead].delay - t;
  };
}

Qinit()
{
  int i;

  /* initialize queue of notes waiting to finish */
  Qhead = -1;
  freehead = 0;
  for (i=0; i<QSIZE-1; i++) {
    Q[i].next = i + 1;
  };
  Q[QSIZE-1].next = -1;
  freetail = QSIZE-1;
}

Qcheck()
{
  int qfree, qused;
  int nextitem;
  int used[QSIZE];
  int i;
  int failed;

  failed = 0;
  for (i=0; i<QSIZE; i++) {
    used[i] = 0;
  };
  qused = 0;
  nextitem = Qhead;
  while (nextitem != -1) {
    qused = qused + 1;
    used[nextitem] = 1;
    nextitem = Q[nextitem].next;
    if ((nextitem < -1) || (nextitem >= QSIZE)) {
      failed = 1;
      printf("Queue corrupted Q[].next = %d\n", nextitem);
    };
  };
  qfree = 0;
  nextitem = freehead;
  while (nextitem != -1) {
    qfree = qfree + 1;
    used[nextitem] = 1;
    nextitem = Q[nextitem].next;
    if ((nextitem < -1) || (nextitem >= QSIZE)) {
      failed = 1;
      printf("Free Queue corrupted Q[].next = %d\n", nextitem);
    };
  };
  if (qfree + qused < QSIZE) {
    failed = 1;
    printf("qfree = %d qused = %d\n", qused, qfree);
  };
  for (i=0; i<QSIZE; i++) {
    if (used[i] == 0) {
      printf("Not used element %d\n", i);
      failed = 1;
    };
  };
  if (Q[freetail].next != -1) {
    printf("freetail = %d, Q[freetail].next = %d\n", freetail, 
           Q[freetail].next);
  };
  if (failed == 1) {
    printQ();
    event_fatal_error("Qcheck failed");
  };
}

timestep(t, atend)
int t;
int atend;
{
  int time;
  int headtime;

  time = t;
  /* process any notes waiting to finish */
  while ((Qhead != -1) && (Q[Qhead].delay < time)) {
    headtime = Q[Qhead].delay;
    delta_time = delta_time + (long) headtime;
    time = time - headtime;
    advanceQ(headtime);
    if (Q[Qhead].pitch == -1) {
      if (!atend) {
        dogchords(Q[Qhead].chan);
      };
    } else {
      midi_noteoff(delta_time, Q[Qhead].pitch, Q[Qhead].chan);
      tracklen = tracklen + delta_time;
      delta_time = 0L;
    };
    removefromQ(Qhead);
  };
  if (Qhead != -1) {
    advanceQ(time);
  };
  delta_time = delta_time + (long)time;
}