/*
 * queue.c
 *
 * Sung-Eun Choi (sungeun@cs.washington.edu)
 * Autumn 1996
 *
 */

#include "queue.h"
#include "my_malloc.h"
#include <stdio.h>		/* for errors */

#define _Q_SUCCESS_ 0
#define _Q_ERROR_ -1
#define _Q_FAILURE_ -1

/* a queue element: data and a pointer to the next element */
typedef struct q_element {
  any_t data;
  struct q_element *next;
} q_element_t;

/* the REAL queue: pointer to the head (front) and tail (back) */
typedef struct realq {
  q_element_t *head;
  q_element_t *tail;
} realq_t;

/* Prototypes for other functions to be used internally */

/* Abstract the queue elements, too.  I may want to improve
   their implementation at a later time */
/* Return a new q_element. */
static q_element_t *q_element_new(any_t, q_element_t *);
/* Free the q_element. */
static int q_element_free(q_element_t *);
/* Get the data. */
static any_t q_element_data(q_element_t *);
/* Update the q_element's next pointer. */
static int q_element_set_next(q_element_t *, q_element_t *);
/* Return the q_element's next pointer. */
static q_element_t *q_element_get_next(q_element_t *);

/* Return an empty queue */
queue_t
queue_new()
{
  realq_t *rq;

  rq = (realq_t *) my_malloc(sizeof(realq_t));
  if (rq == NULL) {
    fprintf(stderr, "queue_new: calloc failed\n");
    exit(_Q_ERROR_);
  }

  rq->head = NULL;
  rq->tail = NULL;

  return (queue_t) rq;

}

/* Prepend an any_t to a queue (both specifed as parameters).  Return
   0 (success) or -1 (failure). */
int
queue_prepend(queue_t q, any_t d)
{
  q_element_t *e;
  realq_t *rq;

  rq = (realq_t *) q;
  if (rq == NULL) {                  /* if the q pointer itself if NULL */
    return _Q_FAILURE_;              /* return failure */
  }

  e = q_element_new(d, rq->head);    /* create a new queue element
					with d, whose next pointer is
					the current head of the queue */

  rq->head = e;                      /* prepend it to the queue */

  if (rq->tail == NULL) {            /* if the queue was empty */
    rq->tail = rq->head;             /* this element is the tail, too */
  }

  return _Q_SUCCESS_;
}

/* Appends an any_t to a queue (both specifed as parameters).  Return
   0 (success) or -1 (failure). */
int
queue_append(queue_t q, any_t d)
{
  realq_t *rq;
  q_element_t *e;

  rq = (realq_t *) q;
  if (rq == NULL) {                  /* if the q pointer itself if NULL */
    return _Q_FAILURE_;              /* return failure */
  }

  e = q_element_new(d, NULL);        /* create a new queue element
					with d, whose next pointer is
					NULL */

  if (rq->tail != NULL) {            /* if the queue is not empty */
    q_element_set_next(rq->tail, e); /* append it to the queue */
  }
  else {                             /* the queue was empty, so */
    rq->head = e;                    /* this element is the head, too */
  }
  rq->tail = e;

  return _Q_SUCCESS_;
}

/* Dequeue and return the first any_t from the queue or NULL if queue
   is empty.  Return 0 (success) or -1 (failure). */
int
queue_dequeue(queue_t q, any_t *d)
{
  realq_t *rq;
  q_element_t *e;

  rq = (realq_t *) q;
  if (rq == NULL) {                  /* if the q pointer itself if NULL */
    return _Q_FAILURE_;              /* return failure */
  }

  if (rq->head == NULL) {            /* if the queue is empty */
    *d = NULL;                       /* return a NULL data element */
  }
  else {
    e = rq->head;                    /* get the first element */
    rq->head = q_element_get_next(e);/* move up the head pointer */
    if (rq->head == NULL) {          /* if this was the last element */
      rq->tail = NULL;               /* reset the tail pointer, too */
    }
    *d = q_element_data(e);          /* return the data element */
    q_element_free(e);
  }

  return _Q_SUCCESS_;
}

/* Iterate the function parameter over each element in the queue.  The
   additional any_t argument is passed to the function as its first
   argument and the queue element is the second.  Return 0 (success)
   or -1 (failure). */
int
queue_iterate(queue_t q, PFany f, any_t a)
{
  realq_t *rq;
  any_t current;
  q_element_t *e;

  if (f == NULL) {                   /* if the function pointer is NULL */
    return _Q_FAILURE_;              /* return failure */
  }

  rq = (realq_t *) q;
  if (rq == NULL) {                  /* if the q pointer itself if NULL */
    return _Q_FAILURE_;              /* return failure */
  }

  if (rq->head != NULL) {            /* if the queue is not empty */
    e = rq->head;
    while (e != NULL) {              /* go through the queue */
      current = q_element_data(e);   /* get the data from this element */
      (void) (*f)(a, current);       /* call f with this element */
      e = q_element_get_next(e);     /* get the next element */
    }
  }

  return _Q_SUCCESS_;
}

/* Free the queue and return 0 (success) or -1 (failure). */
int
queue_free (queue_t q)
{
  realq_t *rq;
  any_t dummy;

  if (q == NULL) {                   /* if the q pointer itself if NULL */
    return _Q_FAILURE_;              /* return failure */
  }

  while (queue_dequeue(q, &dummy));  /* dequeue all the elements */

  rq = (realq_t *) q;
  my_free(rq);

  return _Q_SUCCESS_;
}

/* internal functions */

/* Return a new q_element. */
static q_element_t *
q_element_new(any_t d, q_element_t *n)
{
  q_element_t *e;

  e = (q_element_t *) my_malloc(sizeof(q_element_t));
  if (e == NULL) {
    fprintf(stderr, "INTERNAL ERROR: malloc failed\n");
    exit(_Q_ERROR_);
  }

  e->data = d;
  q_element_set_next(e, n);

  return e;

}

/* Free the q_element. */
static int
q_element_free(q_element_t *e)
{
  if (e == NULL) {                   /* if the element is NULL */
    return _Q_FAILURE_;              /* return failure */
  }

  my_free(e);
  return _Q_SUCCESS_;

}

/* Get the data. */
static any_t
q_element_data(q_element_t *e)
{
  if (e == NULL) {                   /* if the element is NULL */
    return NULL;                     /* return NULL */
  }

  return (e->data);

}

/* Update the q_element's next pointer. */
static int
q_element_set_next(q_element_t *e, q_element_t *n)
{
  if (e == NULL) {                   /* if the element is NULL */
    return _Q_FAILURE_;              /* return failure */
  }

  e->next = n;
  return _Q_SUCCESS_;

}

/* Return the q_element's next pointer. */
static q_element_t *
q_element_get_next(q_element_t *e)
{
  if (e == NULL) {                   /* if the element is NULL */
    return NULL;                     /* return NULL */
  }

  return (e->next);

}