/* 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];

    }

}