/* GLIB - Library of useful routines for C programming
 * Copyright (C) 2001 Joshua Nathaniel Pritikin and 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 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, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include "gring.h"

/* Description

The #GRing structure is a doubly-linked list data structure,
very similar to #GList.

Each element in the ring contains a piece of data, together with
pointers which link to the previous and next elements in the ring.
Using these pointers it is possible to move through the ring in both
directions (unlike the Singly-Linked Lists which only allows movement
through the list in the forward direction).

Ring elements are allocated in blocks by sharing GListAllocator with #GList.
This is more efficient than allocating elements individually.

Note that most of the #GRing functions expect to be passed a pointer
to the first element of the ring. The functions which insert elements
return the new start of the ring, which may have changed.

There is no function to create a GRing. NULL is considered to be an
empty ring so you simply initialize a GRing* to NULL.

In generally, the #GRing API mimics the #GList API.  You can almost
s/list/ring/g and your code will continue to work.  Some exceptions
are g_ring_find_custom and g_ring_foreach, which take slightly
different parameters.  You must also be sure to use the g_ring_next /
g_ring_prev macros for ring traversal.

#GRing also supplies the necessary functions to replace #GQueue, which
is now deprecated.  Both g_ring_append and g_ring_prepend are O(1),
and g_ring_pop_(head|tail) offer data removal matching the style of
queues.

*/

/**
 * g_ring_free:
 * @ring: a #GRing.
 *
 * Frees all the memory used by a #GRing.
 *
 * Note: If list elements contain dynamically-allocated memory, they
 * should be freed first.
 **/
void
g_ring_free (GRing *ring)
{
  if (!ring)
    return;

  ring->prev->next = 0;   /* finesse g_list_free [HACK] */

  g_list_free ((GList*) ring);
}

/**
 * g_ring_free_1:
 * @ring: a #GRing element.
 *
 * Frees one #GRing element.  It is usually used after g_ring_remove_link().
 **/
void
g_ring_free_1 (GRing *ring)
{
  ring->next->prev = ring->prev;
  ring->prev->next = ring->next;

  g_list_free_1 ((GList*) ring);
}

static inline GRing *
_g_ring_insert (GRing *    head,
		gpointer   data)
{
  GRing *ring = g_ring_alloc ();

  ring->data = data;

  if (!head)
    {
      ring->next = ring;
      ring->prev = ring;
    }
  else
    {
      ring->next = head;
      ring->prev = head->prev;
      ring->next->prev = ring;
      ring->prev->next = ring;
    }

  return ring;
}

/**
 * g_ring_append:
 * @head: a #GRing.
 * @data: the data for the new element.
 *
 * Adds a new element on to the end of the ring.
 *
 * Return value: the new head of the #GRing.
 **/
GRing *
g_ring_append (GRing *  head,
	       gpointer data)
{
  GRing *ring;

  ring = _g_ring_insert (head, data);

  return head? head : ring;
}

/**
 * g_ring_prepend:
 * @head: a #GRing.
 * @data: the data for the new element.
 *
 * Adds a new element on to the beginning of the ring.
 *
 * Return value: the new head of the #GRing.
 **/
GRing *
g_ring_prepend (GRing *  head,
		gpointer data)
{
  return _g_ring_insert (head, data);
}

/**
 * g_ring_insert
 * @head: a #GRing.
 * @data: the data for the new element.
 * @position: the position to insert the element.  If negative or larger than
 * the length of the list then the new element is added on to the end of the
 * list.
 *
 * Inserts a new element into the list at the given position.
 *
 * Return value: the new head of the #GRing.
 **/
GRing *
g_ring_insert (GRing *  head,
	       gpointer data,
	       gint     position)
{
  GRing *ring;
  GRing *ready;

  if (position < 0)
    return g_ring_append (head, data);
  else if (position == 0)
    return g_ring_prepend (head, data);

  ring = g_ring_nth (head, position);
  if (!ring)
    return g_ring_append (head, data);

  ready = _g_ring_insert (ring, data);

  return head == ring? ready : head;
}

/**
 * g_ring_insert_sorted:
 * @head: a #GRing
 * @data: the data for the new element.
 * @func: the function to compare elements in the list.  It's return value should follow the same protocol as strcmp().
 * @user_data: user data passed to the function.
 *
 * Inserts a new element into the list using the given comparison function to
 * determine the appropriate position.
 *
 * Return value: the new head of the #GRing
 **/
GRing *
g_ring_insert_sorted (GRing *head,
		      gpointer data,
		      GCompareDataFunc func,
		      gpointer user_data)
{
  GRing *ring;
  gint cmp;

  g_return_val_if_fail (func, head);

  if (!head)
    {
      ring = g_ring_alloc ();

      ring->data = data;
      ring->next = ring;
      ring->prev = ring;

      return ring;
    }

  cmp = (*func) (data, head->data, user_data);

  if (cmp < 0)
    return _g_ring_insert (head, data);

  ring = head;

  while (ring->next != head && cmp > 0)
    {
      ring = ring->next;
      cmp = (*func) (data, ring->data, user_data);
    }

  if (cmp > 0)
    _g_ring_insert (ring->next, data);
  else
    _g_ring_insert (ring, data);

  return head;
}

/**
 * g_ring_concat:
 * @ring1: a #GRing
 * @ring2: the #GRing to add to the end of the first #GRing.
 *
 * Adds the second #GRing onto the end of the first #GRing.  The elements of
 * the second #GRing are not copied. They are used directly.
 *
 * Return value: the new head of the #GRing
 **/
GRing *
g_ring_concat (GRing *head1,
	       GRing *head2)
{
  GRing *tail1, *tail2;
 
  if (!head1)
    return head2;
  if (!head2)
    return head1;

  tail1 = head1->prev;
  tail2 = head2->prev;
  head1->prev = tail2;
  tail2->next = head1;
  head2->prev = tail1;
  tail1->next = head2;
 
  return head1;
}

GRing *
g_ring_remove (GRing *       head,
	       gconstpointer data)
{
  GRing *ring;

  if (!head)
    return NULL;

  for (ring = head; ring; ring = g_ring_next (head, ring))
    {
      if (ring->data != data)
	continue;

      if (ring == head)
	head = (ring == ring->next)? NULL : ring->next;

      g_ring_free_1 (ring);
      
      break;
    }
  
  return head;
}

GRing *
g_ring_remove_all (GRing *       head,
		   gconstpointer data)
{
  GRing *ring;

  if (!head)
    return NULL;

  ring = head;

  do {
    GRing *next = ring->next;

    if (ring->data == data)
      {
	if (ring == head)
	  head = (ring == ring->next)? NULL : ring->next;
	
	g_ring_free_1 (ring);
      }

    ring = next;

  } while (ring != head);
  
  return head;
}

// head == NULL is OK
//
GRing *
g_ring_remove_link (GRing *head,
		    GRing *ring)
{
  if (!ring)
    return head;

  if (ring == head)
    head = ring == ring->next? NULL : ring->next;

  ring->next->prev = ring->prev;
  ring->prev->next = ring->next;

  ring->next = ring->prev = ring;

  return head;
}

GRing *
g_ring_delete_link (GRing *head,
		    GRing *ring)
{
  head = g_ring_remove_link (head, ring);
  g_list_free_1 ((GList*) ring);
  return head;
}

GRing *
g_ring_reverse (GRing *head)
{
  GRing *last, *ring;

  if (!head || head == head->next)
    return head;

  last = head;

  do
    {
      ring = head;
      head = ring->next;
      ring->next = ring->prev;
      ring->prev = head;
    }
  while (ring->prev != last);

  return last->next;
}

GRing *
g_ring_copy (GRing *head)
{
  GRing *copy;
  GRing *ring;
  
  if (!head)
    return 0;

  copy = NULL;
  for (ring = head; ring; ring = g_ring_next (head, ring))
    {
      copy = g_ring_append (copy, ring->data);
    }

  return copy;
}

GRing *
g_ring_nth (GRing *ring,
	    guint  n)
{
  GRing *head;

  head = ring;

  while ((n-- > 0))
    {
      ring = ring->next;

      if (ring == head)
	return NULL;
    }
  
  return ring;
}

GRing *
g_ring_nth_prev (GRing *ring,
		 guint  n)
{
  GRing *head;

  head = ring;

  while ((n-- > 0))
    {
      ring = ring->prev;

      if (ring == head)
	return NULL;
    }
  
  return ring;
}

GRing *
g_ring_find (GRing *       head,
	     gconstpointer data)
{
  GRing *ring;

  for (ring = head; ring; ring = g_ring_next (head, ring))
    {
      if (ring->data == data)
	return ring;
    }

  return NULL;
}

GRing *
g_ring_find_nearby (GRing *       head,
		    gconstpointer data)
{
  GRing *fwd, *bck;

  if (!head)
    return NULL;

  if (head->data == data)
    return head;

  if (head->next == head)
    return NULL;

  fwd = head->next;
  bck = head->prev;

  while (1)
    {
      if (fwd->data == data)
	return fwd;

      if (fwd == bck)
	return NULL;
      
      if (bck->data == data)
	return bck;
      
      fwd = fwd->next;
      
      if (fwd == bck)
	return NULL;
      
      bck = bck->prev;
    }

  return NULL;
}

/**
 * g_ring_find_custom:
 * @head: a #GRing
 * @func: the function to call for each link.  It should return 0 when the desired link is found.
 * @user_data: user data passed to the function.
 *
 * Finds an link in a #GRing using a supplied function to test for the desired element.
 * It iterates over the list, calling the given function which should return 0 when the
 * desired element is found. The function takes two gpointer arguments, the #GRing
 * link's data and the given user data.
 *
 * Return value: the found #GRing or NULL
 **/
GRing *
g_ring_find_custom (GRing *      head,
		    GCompareFunc func,
		    gpointer     user_data)
{
  GRing *ring;

  g_return_val_if_fail (func != NULL, NULL);

  if (!head)
    return NULL;

  for (ring = head; ring; ring = g_ring_next (head, ring))
    {
      if (! (*func) (ring->data, user_data))
	return ring;
    }
  
  return NULL;
}

GRing *
g_ring_find_nearby_custom (GRing *       head,
			   GCompareFunc  func,
			   gpointer      user_data)
{
  GRing *fwd, *bck;

  g_return_val_if_fail (func != NULL, NULL);

  if (!head)
    return NULL;

  if (! (*func) (head->data, user_data))
    return head;

  if (head->next == head)
    return NULL;

  fwd = head->next;
  bck = head->prev;

  while (1)
    {
      if (! (*func) (fwd->data, user_data))
	return fwd;

      if (fwd == bck)
	return NULL;
      
      if (! (*func) (bck->data, user_data))
	return bck;
      
      fwd = fwd->next;
      
      if (fwd == bck)
	return NULL;
      
      bck = bck->prev;
    }

  return NULL;
}

/**
 * g_ring_position:
 * @head: a #GRing.
 * @ring: an element in the #GRing.
 *
 * Gets the position of the given element in the #GRing (starting from 0).
 *
 * Return value: the position of the element in the #GRing or
 * -1 if the element is not found.
 **/
gint
g_ring_position (GRing *head,
		 GRing *ring)
{
  GRing *iter;
  gint ix=0;

  for (iter = head; iter; iter = g_ring_next (head, iter))
    {
      if (iter == ring) return ix;
      ++ix;
    }

  return -1;
}

/**
 * g_ring_index:
 * @head: a #GRing.
 * @data: the data to find.
 *
 * Gets the position of the element containing the given data (starting from 0).
 *
 * Return value: the index of the element containing the data or
 * -1 if the data is not found.
 **/
gint
g_ring_index (GRing *       head,
	      gconstpointer data)
{
  GRing *iter;
  gint ix=0;

  for (iter = head; iter; iter = g_ring_next (head, iter))
    {
      if (iter->data == data) return ix;
      ++ix;
    }

  return -1;
}

/**
 * g_ring_length:
 * @head: a #GRing
 *
 * Gets the number of links in the ring by traversing the whole ring.
 *
 * Return value: the number of links in the ring
 **/
guint
g_ring_length (GRing *head)
{
  GRing *ring;
  guint length;
 
  if (!head)
    return 0;

  ring = head;
  length = 0;

  do
    {
      ++length;
      ring = ring->next;
    }
  while (ring != head);
 
  return length;
}

/**
 * g_ring_foreach:
 * @head: a pointer to a #GRing.
 * @func: the function to call with each ring's data
 * @user_data: user data to pass to the function
 *
 * Calls a function for each element of a #GRing.
 *
 * It is permissible to modify the ring during traversal.  However, you
 * must carefully check your code against the implementation of g_ring_foreach.
 * Modifications may cause elements to be skipped or visited twice.
 * The safest approach is to do any modifications outside of the
 * g_ring_foreach callback.
 *
 **/
void
g_ring_foreach (GRing ** head,
		GFunc    func,
		gpointer user_data)
{
  GRing *ring = *head;

  if (!ring)
    return;

  do
    {
      GRing *next = ring->next;
      (*func) (ring->data, user_data);
      ring = next;
    }
  while (ring != *head);
}

GRing     *g_ring_sort             (GRing *head, GCompareFunc compare_func)
{
  g_error("not implemented");
}

GRing     *g_ring_sort_with_data   (GRing           *head,
				    GCompareDataFunc compare_func,
				    gpointer         user_data)
{
  g_error ("not implemented");
}

/**
 * g_ring_nth_data:
 * @head: a #GRing.
 * @n: the position of the element.
 *
 * Gets the data of the element at the given position.
 *
 * Return value: the element's data or NULL if the position is off the end
 * of the #GRing.
 **/
gpointer
g_ring_nth_data (GRing *head,
		 guint  n)
{
  GRing *ring;

  ring = head;

  while ((n-- > 0))
    {
      ring = ring->next;

      if (ring == head)
	return NULL;
    }
  
  return ring->data;
}

gpointer
g_ring_pop_head (GRing **head)
{
  gpointer data;
 
  g_return_val_if_fail (head != NULL, NULL);
 
  if (!*head)
    return NULL;

  data = (*head)->data;
  *head = g_ring_delete_link (*head, *head);
 
  return data;
}

gpointer
g_ring_pop_tail (GRing **head)
{
  gpointer data;
 
  g_return_val_if_fail (head != NULL, NULL);
 
  if (!*head)
    return NULL;

  data = (*head)->prev->data;
  *head = g_ring_delete_link (*head, (*head)->prev);
 
  return data;
}