/* movstat/deque.c
 *
 * Double-ended queue based on a circular buffer
 * 
 * Copyright (C) 2018 Patrick Alken
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */

typedef int deque_type_t;

typedef struct
{
  int head;
  int tail;
  int size;       /* total elements allocated */
  deque_type_t *array;
} deque;

static size_t deque_size(const size_t n);
static int deque_init(const size_t n, deque * d);
static int deque_empty(deque * d);
static int deque_is_empty(const deque * d);
static int deque_is_full(const deque * d);
static int deque_push_front(const deque_type_t x, deque * d);
static int deque_push_back(const deque_type_t x, deque * d);
static int deque_pop_front(deque * d);
static int deque_pop_back(deque * d);
static deque_type_t deque_peek_front(const deque * d);
static deque_type_t deque_peek_back(const deque * d);

static size_t
deque_size(const size_t n)
{
  size_t size = 0;

  size += sizeof(deque);
  size += n * sizeof(deque_type_t); /* array */

  return size;
}

static int
deque_init(const size_t n, deque * d)
{
  d->head = -1;
  d->tail = 0;
  d->size = (int) n;
  d->array = (deque_type_t *) ((unsigned char *) d + sizeof(deque));

  return GSL_SUCCESS;
}

/* empty the queue */
static int
deque_empty(deque * d)
{
  d->head = -1;
  d->tail = 0;
  return GSL_SUCCESS;
}

/* check if queue is empty */
static int
deque_is_empty(const deque * d)
{
  return (d->head == -1);
}

/* check if queue is full */
static int
deque_is_full(const deque * d)
{
  return ((d->head == 0 && d->tail == d->size - 1) ||
          (d->head == d->tail + 1));
}

static int
deque_push_front(const deque_type_t x, deque * d)
{
  if (deque_is_full(d))
    {
      GSL_ERROR("deque is full", GSL_EOVRFLW);
    }
  else
    {
      if (d->head == -1)     /* queue is empty */
        {
          d->head = 0;
          d->tail = 0;
        }
      else if (d->head == 0) /* head is in first position, wrap to end */
        {
          d->head = d->size - 1;
        }
      else                   /* decrement head */
        {
          --(d->head);
        }

      /* insert element */
      d->array[d->head] = x;

      return GSL_SUCCESS;
    }
}

static int
deque_push_back(const deque_type_t x, deque * d)
{
  if (deque_is_full(d))
    {
      GSL_ERROR("deque is full", GSL_EOVRFLW);
    }
  else
    {
      if (d->head == -1)               /* queue is empty */
        {
          d->head = 0;
          d->tail = 0;
        }
      else if (d->tail == d->size - 1) /* tail is in last position, wrap to 0 */
        {
          d->tail = 0;
        }
      else                             /* increment tail */
        {
          ++(d->tail);
        }

      /* insert element */
      d->array[d->tail] = x;

      return GSL_SUCCESS;
    }
}

static int
deque_pop_front(deque * d)
{
  if (deque_is_empty(d))
    {
      GSL_ERROR("cannot pop element from empty queue", GSL_EOVRFLW);
    }
  else
    {
      if (d->head == d->tail)          /* queue has only one element */
        {
          d->head = -1;
          d->tail = -1;
        }
      else if (d->head == d->size - 1) /* head is in last position, wrap to 0 */
        {
          d->head = 0;
        }
      else                             /* increment head */
        {
          ++(d->head);
        }

      return GSL_SUCCESS;
    }
}

static int
deque_pop_back(deque * d)
{
  if (deque_is_empty(d))
    {
      GSL_ERROR("cannot pop element from empty queue", GSL_EOVRFLW);
    }
  else
    {
      if (d->head == d->tail)    /* queue has only one element */
        {
          d->head = -1;
          d->tail = -1;
        }
      else if (d->tail == 0)     /* tail is in first position, wrap to end */
        {
          d->tail = d->size - 1;
        }
      else                       /* decrement tail */
        {
          --(d->tail);
        }

      return GSL_SUCCESS;
    }
}

static deque_type_t
deque_peek_front(const deque * d)
{
  if (deque_is_empty(d))
    {
      GSL_ERROR("queue is empty", GSL_EBADLEN);
    }
  else
    {
      return d->array[d->head];
    }
}

static deque_type_t
deque_peek_back(const deque * d)
{
  if (deque_is_empty(d) || d->tail < 0)
    {
      GSL_ERROR("queue is empty", GSL_EBADLEN);
    }
  else
    {
      return d->array[d->tail];
    }
}