/* GLIB - Library of useful routines for C programming

 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

 *

 * GQueue: Double ended queue implementation, piggy backed on GList.

 * Copyright (C) 1998 Tim Janik

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * This library 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

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, see <http://www.gnu.org/licenses/>.

 */

/*

 * MT safe

 */

/**

 * SECTION:queue

 * @Title: Double-ended Queues

 * @Short_description: double-ended queue data structure

 *

 * The #GQueue structure and its associated functions provide a standard

 * queue data structure. Internally, GQueue uses the same data structure

 * as #GList to store elements.

 *

 * The data contained in each element can be either integer values, by

 * using one of the [Type Conversion Macros][glib-Type-Conversion-Macros],

 * or simply pointers to any type of data.

 *

 * To create a new GQueue, use g_queue_new().

 *

 * To initialize a statically-allocated GQueue, use #G_QUEUE_INIT or

 * g_queue_init().

 *

 * To add elements, use g_queue_push_head(), g_queue_push_head_link(),

 * g_queue_push_tail() and g_queue_push_tail_link().

 *

 * To remove elements, use g_queue_pop_head() and g_queue_pop_tail().

 *

 * To free the entire queue, use g_queue_free().

 */

#include "config.h"

#include "gqueue.h"

#include "gtestutils.h"

#include "gslice.h"

/**

 * g_queue_new:

 *

 * Creates a new #GQueue.

 *

 * Returns: a newly allocated #GQueue

 **/

GQueue *

g_queue_new (void)

{

  return g_slice_new0 (GQueue);

}

/**

 * g_queue_free:

 * @queue: a #GQueue

 *

 * Frees the memory allocated for the #GQueue. Only call this function

 * if @queue was created with g_queue_new(). If queue elements contain

 * dynamically-allocated memory, they should be freed first.

 *

 * If queue elements contain dynamically-allocated memory, you should

 * either use g_queue_free_full() or free them manually first.

 **/

void

g_queue_free (GQueue *queue)

{

  g_return_if_fail (queue != NULL);

  g_list_free (queue->head);

  g_slice_free (GQueue, queue);

}

/**

 * g_queue_free_full:

 * @queue: a pointer to a #GQueue

 * @free_func: the function to be called to free each element's data

 *

 * Convenience method, which frees all the memory used by a #GQueue,

 * and calls the specified destroy function on every element's data.

 *

 * @free_func should not modify the queue (eg, by removing the freed

 * element from it).

 *

 * Since: 2.32

 */

void

g_queue_free_full (GQueue        *queue,

                  GDestroyNotify  free_func)

{

  g_queue_foreach (queue, (GFunc) free_func, NULL);

  g_queue_free (queue);

}

/**

 * g_queue_init:

 * @queue: an uninitialized #GQueue

 *

 * A statically-allocated #GQueue must be initialized with this function

 * before it can be used. Alternatively you can initialize it with

 * #G_QUEUE_INIT. It is not necessary to initialize queues created with

 * g_queue_new().

 *

 * Since: 2.14

 */

void

g_queue_init (GQueue *queue)

{

  g_return_if_fail (queue != NULL);

  queue->head = queue->tail = NULL;

  queue->length = 0;

}

/**

 * g_queue_clear:

 * @queue: a #GQueue

 *

 * Removes all the elements in @queue. If queue elements contain

 * dynamically-allocated memory, they should be freed first.

 *

 * Since: 2.14

 */

void

g_queue_clear (GQueue *queue)

{

  g_return_if_fail (queue != NULL);

  g_list_free (queue->head);

  g_queue_init (queue);

}

/**

 * g_queue_is_empty:

 * @queue: a #GQueue.

 *

 * Returns %TRUE if the queue is empty.

 *

 * Returns: %TRUE if the queue is empty

 */

gboolean

g_queue_is_empty (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, TRUE);

  return queue->head == NULL;

}

/**

 * g_queue_get_length:

 * @queue: a #GQueue

 * 

 * Returns the number of items in @queue.

 * 

 * Returns: the number of items in @queue

 * 

 * Since: 2.4

 */

guint

g_queue_get_length (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, 0);

  return queue->length;

}

/**

 * g_queue_reverse:

 * @queue: a #GQueue

 * 

 * Reverses the order of the items in @queue.

 * 

 * Since: 2.4

 */

void

g_queue_reverse (GQueue *queue)

{

  g_return_if_fail (queue != NULL);

  queue->tail = queue->head;

  queue->head = g_list_reverse (queue->head);

}

/**

 * g_queue_copy:

 * @queue: a #GQueue

 * 

 * Copies a @queue. Note that is a shallow copy. If the elements in the

 * queue consist of pointers to data, the pointers are copied, but the

 * actual data is not.

 * 

 * Returns: a copy of @queue

 * 

 * Since: 2.4

 */

GQueue *

g_queue_copy (GQueue *queue)

{

  GQueue *result;

  GList *list;

  g_return_val_if_fail (queue != NULL, NULL);

  result = g_queue_new ();

  for (list = queue->head; list != NULL; list = list->next)

    g_queue_push_tail (result, list->data);

  return result;

}

/**

 * g_queue_foreach:

 * @queue: a #GQueue

 * @func: the function to call for each element's data

 * @user_data: user data to pass to @func

 * 

 * Calls @func for each element in the queue passing @user_data to the

 * function.

 * 

 * It is safe for @func to remove the element from @queue, but it must

 * not modify any part of the queue after that element.

 *

 * Since: 2.4

 */

void

g_queue_foreach (GQueue   *queue,

                 GFunc     func,

                 gpointer  user_data)

{

  GList *list;

  g_return_if_fail (queue != NULL);

  g_return_if_fail (func != NULL);

  list = queue->head;

  while (list)

    {

      GList *next = list->next;

      func (list->data, user_data);

      list = next;

    }

}

/**

 * g_queue_find:

 * @queue: a #GQueue

 * @data: data to find

 * 

 * Finds the first link in @queue which contains @data.

 * 

 * Returns: the first link in @queue which contains @data

 * 

 * Since: 2.4

 */

GList *

g_queue_find (GQueue        *queue,

              gconstpointer  data)

{

  g_return_val_if_fail (queue != NULL, NULL);

  return g_list_find (queue->head, data);

}

/**

 * g_queue_find_custom:

 * @queue: a #GQueue

 * @data: user data passed to @func

 * @func: a #GCompareFunc to call for each element. It should return 0

 *     when the desired element is found

 *

 * Finds an element in a #GQueue, using a supplied function to find the

 * desired element. It iterates over the queue, calling the given function

 * which should return 0 when the desired element is found. The function

 * takes two gconstpointer arguments, the #GQueue element's data as the

 * first argument and the given user data as the second argument.

 * 

 * Returns: the found link, or %NULL if it wasn't found

 * 

 * Since: 2.4

 */

GList *

g_queue_find_custom (GQueue        *queue,

                     gconstpointer  data,

                     GCompareFunc   func)

{

  g_return_val_if_fail (queue != NULL, NULL);

  g_return_val_if_fail (func != NULL, NULL);

  return g_list_find_custom (queue->head, data, func);

}

/**

 * g_queue_sort:

 * @queue: a #GQueue

 * @compare_func: the #GCompareDataFunc used to sort @queue. This function

 *     is passed two elements of the queue and should return 0 if they are

 *     equal, a negative value if the first comes before the second, and

 *     a positive value if the second comes before the first.

 * @user_data: user data passed to @compare_func

 * 

 * Sorts @queue using @compare_func. 

 * 

 * Since: 2.4

 */

void

g_queue_sort (GQueue           *queue,

              GCompareDataFunc  compare_func,

              gpointer          user_data)

{

  g_return_if_fail (queue != NULL);

  g_return_if_fail (compare_func != NULL);

  queue->head = g_list_sort_with_data (queue->head, compare_func, user_data);

  queue->tail = g_list_last (queue->head);

}

/**

 * g_queue_push_head:

 * @queue: a #GQueue.

 * @data: the data for the new element.

 *

 * Adds a new element at the head of the queue.

 */

void

g_queue_push_head (GQueue   *queue,

                   gpointer  data)

{

  g_return_if_fail (queue != NULL);

  queue->head = g_list_prepend (queue->head, data);

  if (!queue->tail)

    queue->tail = queue->head;

  queue->length++;

}

/**

 * g_queue_push_nth:

 * @queue: a #GQueue

 * @data: the data for the new element

 * @n: the position to insert the new element. If @n is negative or

 *     larger than the number of elements in the @queue, the element is

 *     added to the end of the queue.

 * 

 * Inserts a new element into @queue at the given position.

 * 

 * Since: 2.4

 */

void

g_queue_push_nth (GQueue   *queue,

                  gpointer  data,

                  gint      n)

{

  g_return_if_fail (queue != NULL);

  if (n < 0 || n >= queue->length)

    {

      g_queue_push_tail (queue, data);

      return;

    }

  g_queue_insert_before (queue, g_queue_peek_nth_link (queue, n), data);

}

/**

 * g_queue_push_head_link:

 * @queue: a #GQueue

 * @link_: a single #GList element, not a list with more than one element

 *

 * Adds a new element at the head of the queue.

 */

void

g_queue_push_head_link (GQueue *queue,

                        GList  *link)

{

  g_return_if_fail (queue != NULL);

  g_return_if_fail (link != NULL);

  g_return_if_fail (link->prev == NULL);

  g_return_if_fail (link->next == NULL);

  link->next = queue->head;

  if (queue->head)

    queue->head->prev = link;

  else

    queue->tail = link;

  queue->head = link;

  queue->length++;

}

/**

 * g_queue_push_tail:

 * @queue: a #GQueue

 * @data: the data for the new element

 *

 * Adds a new element at the tail of the queue.

 */

void

g_queue_push_tail (GQueue   *queue,

                   gpointer  data)

{

  g_return_if_fail (queue != NULL);

  queue->tail = g_list_append (queue->tail, data);

  if (queue->tail->next)

    queue->tail = queue->tail->next;

  else

    queue->head = queue->tail;

  queue->length++;

}

/**

 * g_queue_push_tail_link:

 * @queue: a #GQueue

 * @link_: a single #GList element, not a list with more than one element

 *

 * Adds a new element at the tail of the queue.

 */

void

g_queue_push_tail_link (GQueue *queue,

                        GList  *link)

{

  g_return_if_fail (queue != NULL);

  g_return_if_fail (link != NULL);

  g_return_if_fail (link->prev == NULL);

  g_return_if_fail (link->next == NULL);

  link->prev = queue->tail;

  if (queue->tail)

    queue->tail->next = link;

  else

    queue->head = link;

  queue->tail = link;

  queue->length++;

}

/**

 * g_queue_push_nth_link:

 * @queue: a #GQueue

 * @n: the position to insert the link. If this is negative or larger than

 *     the number of elements in @queue, the link is added to the end of

 *     @queue.

 * @link_: the link to add to @queue

 * 

 * Inserts @link into @queue at the given position.

 * 

 * Since: 2.4

 */

void

g_queue_push_nth_link (GQueue *queue,

                       gint    n,

                       GList  *link_)

{

  GList *next;

  GList *prev;

  g_return_if_fail (queue != NULL);

  g_return_if_fail (link_ != NULL);

  if (n < 0 || n >= queue->length)

    {

      g_queue_push_tail_link (queue, link_);

      return;

    }

  g_assert (queue->head);

  g_assert (queue->tail);

  next = g_queue_peek_nth_link (queue, n);

  prev = next->prev;

  if (prev)

    prev->next = link_;

  next->prev = link_;

  link_->next = next;

  link_->prev = prev;

  if (queue->head->prev)

    queue->head = queue->head->prev;

  if (queue->tail->next)

    queue->tail = queue->tail->next;

  queue->length++;

}

/**

 * g_queue_pop_head:

 * @queue: a #GQueue

 *

 * Removes the first element of the queue and returns its data.

 *

 * Returns: the data of the first element in the queue, or %NULL

 *     if the queue is empty

 */

gpointer

g_queue_pop_head (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, NULL);

  if (queue->head)

    {

      GList *node = queue->head;

      gpointer data = node->data;

      queue->head = node->next;

      if (queue->head)

        queue->head->prev = NULL;

      else

        queue->tail = NULL;

      g_list_free_1 (node);

      queue->length--;

      return data;

    }

  return NULL;

}

/**

 * g_queue_pop_head_link:

 * @queue: a #GQueue

 *

 * Removes and returns the first element of the queue.

 *

 * Returns: the #GList element at the head of the queue, or %NULL

 *     if the queue is empty

 */

GList *

g_queue_pop_head_link (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, NULL);

  if (queue->head)

    {

      GList *node = queue->head;

      queue->head = node->next;

      if (queue->head)

        {

          queue->head->prev = NULL;

          node->next = NULL;

        }

      else

        queue->tail = NULL;

      queue->length--;

      return node;

    }

  return NULL;

}

/**

 * g_queue_peek_head_link:

 * @queue: a #GQueue

 * 

 * Returns the first link in @queue.

 * 

 * Returns: the first link in @queue, or %NULL if @queue is empty

 * 

 * Since: 2.4

 */

GList *

g_queue_peek_head_link (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, NULL);

  return queue->head;

}

/**

 * g_queue_peek_tail_link:

 * @queue: a #GQueue

 * 

 * Returns the last link in @queue.

 * 

 * Returns: the last link in @queue, or %NULL if @queue is empty

 * 

 * Since: 2.4

 */

GList *

g_queue_peek_tail_link (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, NULL);

  return queue->tail;

}

/**

 * g_queue_pop_tail:

 * @queue: a #GQueue

 *

 * Removes the last element of the queue and returns its data.

 *

 * Returns: the data of the last element in the queue, or %NULL

 *     if the queue is empty

 */

gpointer

g_queue_pop_tail (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, NULL);

  if (queue->tail)

    {

      GList *node = queue->tail;

      gpointer data = node->data;

      queue->tail = node->prev;

      if (queue->tail)

        queue->tail->next = NULL;

      else

        queue->head = NULL;

      queue->length--;

      g_list_free_1 (node);

      return data;

    }

  return NULL;

}

/**

 * g_queue_pop_nth:

 * @queue: a #GQueue

 * @n: the position of the element

 * 

 * Removes the @n'th element of @queue and returns its data.

 * 

 * Returns: the element's data, or %NULL if @n is off the end of @queue

 * 

 * Since: 2.4

 */

gpointer

g_queue_pop_nth (GQueue *queue,

                 guint   n)

{

  GList *nth_link;

  gpointer result;

  g_return_val_if_fail (queue != NULL, NULL);

  if (n >= queue->length)

    return NULL;

  nth_link = g_queue_peek_nth_link (queue, n);

  result = nth_link->data;

  g_queue_delete_link (queue, nth_link);

  return result;

}

/**

 * g_queue_pop_tail_link:

 * @queue: a #GQueue

 *

 * Removes and returns the last element of the queue.

 *

 * Returns: the #GList element at the tail of the queue, or %NULL

 *     if the queue is empty

 */

GList *

g_queue_pop_tail_link (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, NULL);

  if (queue->tail)

    {

      GList *node = queue->tail;

      queue->tail = node->prev;

      if (queue->tail)

        {

          queue->tail->next = NULL;

          node->prev = NULL;

        }

      else

        queue->head = NULL;

      queue->length--;

      return node;

    }

  return NULL;

}

/**

 * g_queue_pop_nth_link:

 * @queue: a #GQueue

 * @n: the link's position

 * 

 * Removes and returns the link at the given position.

 * 

 * Returns: the @n'th link, or %NULL if @n is off the end of @queue

 * 

 * Since: 2.4

 */

GList*

g_queue_pop_nth_link (GQueue *queue,

                      guint   n)

{

  GList *link;

  g_return_val_if_fail (queue != NULL, NULL);

  if (n >= queue->length)

    return NULL;

  link = g_queue_peek_nth_link (queue, n);

  g_queue_unlink (queue, link);

  return link;

}

/**

 * g_queue_peek_nth_link:

 * @queue: a #GQueue

 * @n: the position of the link

 * 

 * Returns the link at the given position

 * 

 * Returns: the link at the @n'th position, or %NULL

 *     if @n is off the end of the list

 * 

 * Since: 2.4

 */

GList *

g_queue_peek_nth_link (GQueue *queue,

                       guint   n)

{

  GList *link;

  gint i;

  g_return_val_if_fail (queue != NULL, NULL);

  if (n >= queue->length)

    return NULL;

  if (n > queue->length / 2)

    {

      n = queue->length - n - 1;

      link = queue->tail;

      for (i = 0; i < n; ++i)

        link = link->prev;

    }

  else

    {

      link = queue->head;

      for (i = 0; i < n; ++i)

        link = link->next;

    }

  return link;

}

/**

 * g_queue_link_index:

 * @queue: a #GQueue

 * @link_: a #GList link

 * 

 * Returns the position of @link_ in @queue.

 * 

 * Returns: the position of @link_, or -1 if the link is

 *     not part of @queue

 * 

 * Since: 2.4

 */

gint

g_queue_link_index (GQueue *queue,

                    GList  *link_)

{

  g_return_val_if_fail (queue != NULL, -1);

  return g_list_position (queue->head, link_);

}

/**

 * g_queue_unlink:

 * @queue: a #GQueue

 * @link_: a #GList link that must be part of @queue

 *

 * Unlinks @link_ so that it will no longer be part of @queue.

 * The link is not freed.

 *

 * @link_ must be part of @queue.

 * 

 * Since: 2.4

 */

void

g_queue_unlink (GQueue *queue,

                GList  *link_)

{

  g_return_if_fail (queue != NULL);

  g_return_if_fail (link_ != NULL);

  if (link_ == queue->tail)

    queue->tail = queue->tail->prev;

  queue->head = g_list_remove_link (queue->head, link_);

  queue->length--;

}

/**

 * g_queue_delete_link:

 * @queue: a #GQueue

 * @link_: a #GList link that must be part of @queue

 *

 * Removes @link_ from @queue and frees it.

 *

 * @link_ must be part of @queue.

 * 

 * Since: 2.4

 */

void

g_queue_delete_link (GQueue *queue,

                     GList  *link_)

{

  g_return_if_fail (queue != NULL);

  g_return_if_fail (link_ != NULL);

  g_queue_unlink (queue, link_);

  g_list_free (link_);

}

/**

 * g_queue_peek_head:

 * @queue: a #GQueue

 *

 * Returns the first element of the queue.

 *

 * Returns: the data of the first element in the queue, or %NULL

 *     if the queue is empty

 */

gpointer

g_queue_peek_head (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, NULL);

  return queue->head ? queue->head->data : NULL;

}

/**

 * g_queue_peek_tail:

 * @queue: a #GQueue

 *

 * Returns the last element of the queue.

 *

 * Returns: the data of the last element in the queue, or %NULL

 *     if the queue is empty

 */

gpointer

g_queue_peek_tail (GQueue *queue)

{

  g_return_val_if_fail (queue != NULL, NULL);

  return queue->tail ? queue->tail->data : NULL;

}

/**

 * g_queue_peek_nth:

 * @queue: a #GQueue

 * @n: the position of the element