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

/* Double-ended queue implemented as circular list pointing to tail.

     empty queue is a ptr to NULL.
     queue with one item points to itself.
     queue with two or more items: queue points to last item,
                                   tail of last item points to head.

   Accessing the first or last item in the list is cheap.

   Prepending to (pushing on) or Appending to a list is cheap.

   Removing the head of a list (popping off) is cheap.

   Removing the last item from the list is expensive.

   Butfirst would be cheap if implemented.

   Butlast would be expensive.

   With the exception of an expensive 'butlast', this data structure is
   ideal for implementing lists in LOGO
   Commands needed:
     first butfirst last butlast member item setitem fput lput join
     count arraytolist listtoarray reverse combine

   These options efficiently support both stacks (LIFOs)
   and queues (FIFOs) with the same data structure.

   For a summary of different kinds of queues,
   see http://www.cis.upenn.edu/~matuszek/cit594-2005/Lectures/23-stacks-queues-deques.ppt

   Using a circular list avoids the cost of backpointers.

   At some point in the future there's a coding trick that can
   be added whereby the 'next' pointer is the exclusive-or of
   itself and the backpointer which somehow lets you store
   the backpointers without any extra space.  To be honest I
   don't remember the details and will have to sit down some time
   and work it out from first principles.  It's very hacky and
   unless removing the last item from a list is a frequent
   occurance in an application, it's not worth the increase in
   complexity of the code when this implementation is simple
   and works.

   (See http://en.wikipedia.org/wiki/XOR_linked_list )

   OK, the downside is that a list variable is no longer just
   one pointer, it has to be two pointers containing (in this case)
   the address of both the tail and the head of the list.

   It's too messy, I don't think I'll implement it.

 */

#ifndef USERTYPE
/* If usertype is anything other than a scalar the code will need
   tweaking wherever the data field is referenced. */
#define USERTYPE int
#endif

typedef struct QQ {
  struct QQ *tail;
  USERTYPE atom; /* more generically, a void *, but int is OK for testing */
} QQ;

static QQ *new_QQ(USERTYPE atom) /* returns a cell.  Used INTERNALLY only */
{
  QQ *p = malloc(sizeof(QQ));
  assert(p != NULL);
  p->atom = atom;
  p->tail = NULL;
  return p;
}

void append_QQ(QQ **pp, USERTYPE atom)
{
  QQ *head;
#define p (*pp)
  if (p == NULL) {
    p = head = new_QQ(atom);
  } else {
    /* p points to the tail. */
    head = p->tail;
    p = p->tail = new_QQ(atom);
  }
  p->tail = head;
#undef p
}
#define appendq(q, i) append_QQ(&q, i)

void push_QQ(QQ **pp, USERTYPE atom)
{
  QQ *head;
#define p (*pp)
  if (p == NULL) {
    p = new_QQ(atom);
    p->tail = p;
  } else {
    /* p points to the tail. */
    head = p->tail;
    p->tail = new_QQ(atom);
    p->tail->tail = head;
  }
#undef p
}
#define pushq(q, i) push_QQ(&q, i)

void show_QQ(QQ *list, const char *name)
{
  fprintf(stdout, "%s:", name);
  if (list == NULL) {
    fprintf(stdout, " NULL");
  } else {
    QQ *loop_breaker = list;
    for (;;) {
      list = list->tail;
      fprintf(stdout, " %d", list->atom);
      if (list == loop_breaker) break;
    }
  }
  fprintf(stdout, "\n");
}
#define showq(name) show_QQ(name, #name)

int firstq(QQ *q)
{
  assert(q != NULL); /* user bug */
  assert(q->tail != NULL); /* package bug */
  return q->tail->atom;
}

int lastq(QQ *q)
{
  assert(q != NULL);
  return q->atom;
}

void popfirst_QQ(QQ **qq)
{
  QQ *head;
#define q (*qq)
  assert(qq != NULL);
  assert(q != NULL);
  head = q->tail;
  if (q == head) { /* last atom */
    q = NULL;
  } else {
    q->tail = q->tail->tail;
  }
  free(head);
#undef q
}
#define popfirstq(q) popfirst_QQ(&q)

void poplast_QQ(QQ **qq)
{
  QQ *tail = NULL;
#define q (*qq)
  assert(qq != NULL);
  assert(q != NULL);

  if (q->tail != q) {
    /* EXPENSIVE */
    tail = q->tail;
    for (;;) {
      if (tail->tail == q) break;
      tail = tail->tail;
    }
    tail->tail = q->tail;
  }
  free(q); q = tail;
#undef q
}
#define poplastq(q) poplast_QQ(&q)

/* Unsafe join (aka 'cons') of two lists */
QQ *destructive_join_QQ(QQ **lleft, QQ **rright)
{
  QQ *tmp = NULL;
#define left (*lleft)
#define right (*rright)
  /* join two lists.  Use their space.  Set the lists to NULL. */
  tmp = right->tail;
  right->tail = left->tail;
  left->tail = tmp;
  tmp = right;
  left = NULL; right = NULL;
  return tmp;
#undef left
#undef right
}
#define destructive_joinq(left, right) destructive_join_QQ(&left, &right)

/* duplicate (copy) a list */
QQ *dupq(QQ *list)
{
  QQ *new = NULL, *old = list;
  USERTYPE atom;
  if (list != NULL) {
    for (;;) {
      atom = firstq(list); // list->tail->atom
      appendq(new, atom); // is a 3-liner in-line better than appendq?
      list = list->tail;
      if (list == old) break;
    }
  }
  return new;
}

/* reverse a copy of a list */
QQ *reversedupq(QQ *list)
{
  QQ *new = NULL, *old = list;
  USERTYPE atom;
  if (list != NULL) {
    for (;;) {
      atom = firstq(list); // list->tail->atom
      pushq(new, atom); // is a 3-liner in-line better than pushq?
      list = list->tail;
      if (list == old) break;
    }
  }
  return new;
}

/* reverse a copy of a list */
int countq(QQ *list)
{
  QQ *start = list;
  int count = 0;

  if (list != NULL) {
    for (;;) {
      list = list->tail; count += 1;
      if (list == start) break;
    }
  }
  return count;
}

/* return an indexed member of a list (based at 1) */
int memberq(QQ *list, int member)
{
  QQ *start = list;
  int count = 0;

  assert(member > 0);
  assert(list != NULL);
  list = list->tail;
  for (count = 1; count < member; count++) {
    assert(list != start); // not enough members
    list = list->tail;
  }

  return list->atom;
}

/* non-destructive join.  Uses copies of the lists. */
QQ *joinq(QQ *left, QQ *right)
{
  QQ *temp1 = dupq(left), *temp2 = dupq(right);
  return destructive_joinq(temp1, temp2);
}

/* use this to avoid heap lossage */
void make_QQ(QQ **ddest, QQ **ssource)
{
#define dest (*ddest)
#define source (*ssource)
  assert(ddest != NULL);
  while (dest != NULL) (void)popfirstq(dest); // 1-liner, no need for delq()  
  dest = source;
  source = NULL; /* Ensures we don't have two pointers to the one area. */
#undef dest
#undef source
}
#define makeq(dest, source) make_QQ(&dest, &source)

/* Unit test of double-ended queue list handling */
int main(int argc, char **argv)
{
  QQ *list1 = NULL, *list2 = NULL, *joined = NULL, *copied = NULL, *reversed = NULL;

  showq(list1);
  appendq(list1, 21);
  showq(list1);
  appendq(list1, 42);
  showq(list1);
  appendq(list1, 84);
  showq(list1);
  fprintf(stdout, "first(list1) = %d\n", firstq(list1));
  fprintf(stdout, "last(list1) = %d\n", lastq(list1));
  fprintf(stdout, "popfirstq "); popfirstq(list1); showq(list1);
  fprintf(stdout, "popfirstq "); popfirstq(list1); showq(list1);
  fprintf(stdout, "popfirstq "); popfirstq(list1); showq(list1);

  showq(list2);
  pushq(list2, 17);
  showq(list2);
  pushq(list2, 34);
  showq(list2);
  pushq(list2, 51);
  showq(list2);
  fprintf(stdout, "first(list2) = %d\n", firstq(list2));
  fprintf(stdout, "last(list2) = %d\n", lastq(list2));
  fprintf(stdout, "poplastq "); poplastq(list2); showq(list2);
  fprintf(stdout, "poplastq "); poplastq(list2); showq(list2);
  fprintf(stdout, "poplastq "); poplastq(list2); showq(list2);

  // rebuild
  appendq(list1, 21);
  appendq(list1, 42);
  appendq(list1, 84);
  showq(list1);
  pushq(list2, 17);
  pushq(list2, 34);
  pushq(list2, 51);
  showq(list2);
  joined = destructive_joinq(list1, list2);
  showq(joined);
  showq(list1); showq(list2);

  copied = dupq(joined);
  showq(copied);

  while (copied != NULL) (void)popfirstq(copied); // 1-liner, no need for delq()
  showq(copied);

  while (copied != NULL) (void)popfirstq(copied); 
  showq(copied);

  showq(joined);
  makeq(copied, joined);
  showq(copied);
  showq(joined);
  joined = joinq(copied, copied);
  showq(copied);
  showq(joined);

  reversed = reversedupq(joined);
  showq(reversed);
  fprintf(stdout, "countq reversed: %d\n", countq(reversed));

  //fprintf(stdout, "member 0 of reversed: %d\n", memberq(reversed, 0));
  fprintf(stdout, "member 1 of reversed: %d\n", memberq(reversed, 1));
  fprintf(stdout, "member 2 of reversed: %d\n", memberq(reversed, 2));
  fprintf(stdout, "member 11 of reversed: %d\n", memberq(reversed, 11));
  fprintf(stdout, "member 12 of reversed: %d\n", memberq(reversed, 12));
  //fprintf(stdout, "member 13 of reversed: %d\n", memberq(reversed, 13));

  exit(EXIT_SUCCESS);
  return EXIT_FAILURE;
  /*  Compare the output to the baseline:
list1: NULL
list1: 21
list1: 21 42
list1: 21 42 84
first(list1) = 21
last(list1) = 84
popfirstq list1: 42 84
popfirstq list1: 84
popfirstq list1: NULL
list2: NULL
list2: 17
list2: 34 17
list2: 51 34 17
first(list2) = 51
last(list2) = 17
poplastq list2: 51 34
poplastq list2: 51
poplastq list2: NULL
list1: 21 42 84
list2: 51 34 17
joined: 21 42 84 51 34 17
list1: NULL
list2: NULL
copied: 21 42 84 51 34 17
copied: NULL
copied: NULL
joined: 21 42 84 51 34 17
copied: 21 42 84 51 34 17
joined: NULL
copied: 21 42 84 51 34 17
joined: 21 42 84 51 34 17 21 42 84 51 34 17
reversed: 17 34 51 84 42 21 17 34 51 84 42 21
countq reversed: 12
member 1 of reversed: 17
member 2 of reversed: 34
member 11 of reversed: 42
member 12 of reversed: 21
   */
}