/* GLIB - Library of useful routines for C programming

 * Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007

 * Soeren Sandmann (sandmann@daimi.au.dk)

 *

 * 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 "config.h"

#include "glib.h"

#include "galias.h"

typedef struct _GSequenceNode GSequenceNode;

struct _GSequence

{

  GSequenceNode *       end_node;

  GDestroyNotify        data_destroy_notify;

  gboolean              access_prohibited;

  /* The 'real_sequence' is used when temporary sequences are created

   * to hold nodes that are being rearranged. The 'real_sequence' of such

   * a temporary sequence points to the sequence that is actually being

   * manipulated. The only reason we need this is so that when the

   * sort/sort_changed/search_iter() functions call out to the application

   * g_sequence_iter_get_sequence() will return the correct sequence.

   */

  GSequence *		real_sequence;

};

struct _GSequenceNode

{

  gint                  n_nodes;

  GSequenceNode *       parent;    

  GSequenceNode *       left;

  GSequenceNode *       right;

  gpointer              data;   /* For the end node, this field points

                                 * to the sequence

                                 */

};

/*

 * Declaration of GSequenceNode methods

 */

static GSequenceNode *node_new           (gpointer                  data);

static GSequenceNode *node_get_first     (GSequenceNode            *node);

static GSequenceNode *node_get_last      (GSequenceNode            *node);

static GSequenceNode *node_get_prev      (GSequenceNode            *node);

static GSequenceNode *node_get_next      (GSequenceNode            *node);

static gint           node_get_pos       (GSequenceNode            *node);

static GSequenceNode *node_get_by_pos    (GSequenceNode            *node,

                                          gint                      pos);

static GSequenceNode *node_find_closest  (GSequenceNode            *haystack,

                                          GSequenceNode            *needle,

                                          GSequenceNode            *end,

                                          GSequenceIterCompareFunc  cmp,

                                          gpointer                  user_data);

static gint           node_get_length    (GSequenceNode            *node);

static void           node_free          (GSequenceNode            *node,

                                          GSequence                *seq);

static void           node_cut           (GSequenceNode            *split);

static void           node_insert_before (GSequenceNode            *node,

                                          GSequenceNode            *new);

static void           node_unlink        (GSequenceNode            *node);

static void           node_join          (GSequenceNode            *left,

					  GSequenceNode            *right);

static void           node_insert_sorted (GSequenceNode            *node,

                                          GSequenceNode            *new,

                                          GSequenceNode            *end,

                                          GSequenceIterCompareFunc  cmp_func,

                                          gpointer                  cmp_data);

/*

 * Various helper functions

 */

static void

check_seq_access (GSequence *seq)

{

  if (G_UNLIKELY (seq->access_prohibited))

    {

      g_warning ("Accessing a sequence while it is "

                 "being sorted or searched is not allowed");

    }

}

static GSequence *

get_sequence (GSequenceNode *node)

{

  return (GSequence *)node_get_last (node)->data;

}

static void

check_iter_access (GSequenceIter *iter)

{

  check_seq_access (get_sequence (iter));

}

static gboolean

is_end (GSequenceIter *iter)

{

  GSequence *seq;

  if (iter->right)

    return FALSE;

  if (!iter->parent)

    return TRUE;

  if (iter->parent->right != iter)

    return FALSE;

  seq = get_sequence (iter);

  return seq->end_node == iter;

}

typedef struct

{

  GCompareDataFunc  cmp_func;

  gpointer          cmp_data;

  GSequenceNode    *end_node;

} SortInfo;

/* This function compares two iters using a normal compare

 * function and user_data passed in in a SortInfo struct

 */

static gint

iter_compare (GSequenceIter *node1,

              GSequenceIter *node2,

              gpointer       data)

{

  const SortInfo *info = data;

  gint retval;

  if (node1 == info->end_node)

    return 1;

  if (node2 == info->end_node)

    return -1;

  retval = info->cmp_func (node1->data, node2->data, info->cmp_data);

  return retval;

}

/*

 * Public API

 */

/**

 * g_sequence_new:

 * @data_destroy: a #GDestroyNotify function, or %NULL

 * 

 * Creates a new GSequence. The @data_destroy function, if non-%NULL will

 * be called on all items when the sequence is destroyed and on items that

 * are removed from the sequence.

 * 

 * Return value: a new #GSequence

 * 

 * Since: 2.14

 **/

EXPORT_C GSequence *

g_sequence_new (GDestroyNotify data_destroy)

{

  GSequence *seq = g_new (GSequence, 1);

  seq->data_destroy_notify = data_destroy;

  seq->end_node = node_new (seq);

  seq->access_prohibited = FALSE;

  seq->real_sequence = seq;

  return seq;

}

/**

 * g_sequence_free:

 * @seq: a #GSequence

 * 

 * Frees the memory allocated for @seq. If @seq has a data destroy 

 * function associated with it, that function is called on all items in

 * @seq.

 * 

 * Since: 2.14

 **/

EXPORT_C void

g_sequence_free (GSequence *seq)

{

  g_return_if_fail (seq != NULL);

  check_seq_access (seq);

  node_free (seq->end_node, seq);

  g_free (seq);

}

/**

 * g_sequence_foreach_range:

 * @begin: a #GSequenceIter

 * @end: a #GSequenceIter

 * @func: a #GFunc

 * @user_data: user data passed to @func

 * 

 * Calls @func for each item in the range (@begin, @end) passing

 * @user_data to the function.

 * 

 * Since: 2.14

 **/

EXPORT_C void

g_sequence_foreach_range (GSequenceIter *begin,

                          GSequenceIter *end,

                          GFunc          func,

                          gpointer       user_data)

{

  GSequence *seq;

  GSequenceIter *iter;

  g_return_if_fail (func != NULL);

  g_return_if_fail (begin != NULL);

  g_return_if_fail (end != NULL);

  seq = get_sequence (begin);

  seq->access_prohibited = TRUE;

  iter = begin;

  while (iter != end)

    {

      GSequenceIter *next = node_get_next (iter);

      func (iter->data, user_data);

      iter = next;

    }

  seq->access_prohibited = FALSE;

}

/**

 * g_sequence_foreach:

 * @seq: a #GSequence

 * @func: the function to call for each item in @seq

 * @user_data: user data passed to @func

 * 

 * Calls @func for each item in the sequence passing @user_data

 * to the function.

 * 

 * Since: 2.14

 **/

EXPORT_C void

g_sequence_foreach (GSequence *seq,

                    GFunc      func,

                    gpointer   user_data)

{

  GSequenceIter *begin, *end;

  check_seq_access (seq);

  begin = g_sequence_get_begin_iter (seq);

  end   = g_sequence_get_end_iter (seq);

  g_sequence_foreach_range (begin, end, func, user_data);

}

/**

 * g_sequence_range_get_midpoint:

 * @begin: a #GSequenceIter

 * @end: a #GSequenceIter

 * 

 * Finds an iterator somewhere in the range (@begin, @end). This

 * iterator will be close to the middle of the range, but is not

 * guaranteed to be <emphasis>exactly</emphasis> in the middle.

 *

 * The @begin and @end iterators must both point to the same sequence and

 * @begin must come before or be equal to @end in the sequence.

 * 

 * Return value: A #GSequenceIter pointing somewhere in the

 * (@begin, @end) range.

 * 

 * Since: 2.14

 **/

EXPORT_C GSequenceIter *

g_sequence_range_get_midpoint (GSequenceIter *begin,

                               GSequenceIter *end)

{

  int begin_pos, end_pos, mid_pos;

  g_return_val_if_fail (begin != NULL, NULL);

  g_return_val_if_fail (end != NULL, NULL);

  g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);

  begin_pos = node_get_pos (begin);

  end_pos = node_get_pos (end);

  g_return_val_if_fail (end_pos >= begin_pos, NULL);

  mid_pos = begin_pos + (end_pos - begin_pos) / 2;

  return node_get_by_pos (begin, mid_pos);

}

/**

 * g_sequence_iter_compare:

 * @a: a #GSequenceIter

 * @b: a #GSequenceIter

 * 

 * Returns a negative number if @a comes before @b, 0 if they are equal,

 * and a positive number if @a comes after @b.

 *

 * The @a and @b iterators must point into the same sequence.

 * 

 * Return value: A negative number if @a comes before @b, 0 if they are

 * equal, and a positive number if @a comes after @b.

 * 

 * Since: 2.14

 **/

EXPORT_C gint

g_sequence_iter_compare (GSequenceIter *a,

                         GSequenceIter *b)

{

  gint a_pos, b_pos;

  g_return_val_if_fail (a != NULL, 0);

  g_return_val_if_fail (b != NULL, 0);

  g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0);

  check_iter_access (a);

  check_iter_access (b);

  a_pos = node_get_pos (a);

  b_pos = node_get_pos (b);

  if (a_pos == b_pos)

    return 0;

  else if (a_pos > b_pos)

    return 1;

  else

    return -1;

}

/**

 * g_sequence_append:

 * @seq: a #GSequencePointer

 * @data: the data for the new item

 * 

 * Adds a new item to the end of @seq.

 * 

 * Return value: an iterator pointing to the new item

 * 

 * Since: 2.14

 **/

EXPORT_C GSequenceIter *

g_sequence_append (GSequence *seq,

                   gpointer   data)

{

  GSequenceNode *node;

  g_return_val_if_fail (seq != NULL, NULL);

  check_seq_access (seq);

  node = node_new (data);

  node_insert_before (seq->end_node, node);

  return node;

}

/**

 * g_sequence_prepend:

 * @seq: a #GSequence

 * @data: the data for the new item

 * 

 * Adds a new item to the front of @seq

 * 

 * Return value: an iterator pointing to the new item

 * 

 * Since: 2.14

 **/

EXPORT_C GSequenceIter *

g_sequence_prepend (GSequence *seq,

                    gpointer   data)

{

  GSequenceNode *node, *first;

  g_return_val_if_fail (seq != NULL, NULL);

  check_seq_access (seq);

  node = node_new (data);

  first = node_get_first (seq->end_node);

  node_insert_before (first, node);

  return node;

}

/**

 * g_sequence_insert_before:

 * @iter: a #GSequenceIter

 * @data: the data for the new item

 * 

 * Inserts a new item just before the item pointed to by @iter.

 * 

 * Return value: an iterator pointing to the new item

 * 

 * Since: 2.14

 **/

EXPORT_C GSequenceIter *

g_sequence_insert_before (GSequenceIter *iter,

                          gpointer       data)

{

  GSequenceNode *node;

  g_return_val_if_fail (iter != NULL, NULL);

  check_iter_access (iter);

  node = node_new (data);

  node_insert_before (iter, node);

  return node;

}

/**

 * g_sequence_remove:

 * @iter: a #GSequenceIter

 * 

 * Removes the item pointed to by @iter. It is an error to pass the

 * end iterator to this function.

 *

 * If the sequnce has a data destroy function associated with it, this

 * function is called on the data for the removed item.

 * 

 * Since: 2.14

 **/

EXPORT_C void

g_sequence_remove (GSequenceIter *iter)

{

  GSequence *seq;

  g_return_if_fail (iter != NULL);

  g_return_if_fail (!is_end (iter));

  check_iter_access (iter);

  seq = get_sequence (iter); 

  node_unlink (iter);

  node_free (iter, seq);

}

/**

 * g_sequence_remove_range:

 * @begin: a #GSequenceIter

 * @end: a #GSequenceIter

 * 

 * Removes all items in the (@begin, @end) range.

 *

 * If the sequence has a data destroy function associated with it, this

 * function is called on the data for the removed items.

 * 

 * Since: 2.14

 **/

EXPORT_C void

g_sequence_remove_range (GSequenceIter *begin,

                         GSequenceIter *end)

{

  g_return_if_fail (get_sequence (begin) == get_sequence (end));

  check_iter_access (begin);

  check_iter_access (end);

  g_sequence_move_range (NULL, begin, end);

}

/**

 * g_sequence_move_range:

 * @dest: a #GSequenceIter

 * @begin: a #GSequenceIter

 * @end: a #GSequenceIter

 * 

 * Inserts the (@begin, @end) range at the destination pointed to by ptr.

 * The @begin and @end iters must point into the same sequence. It is

 * allowed for @dest to point to a different sequence than the one pointed

 * into by @begin and @end.

 * 

 * If @dest is NULL, the range indicated by @begin and @end is

 * removed from the sequence. If @dest iter points to a place within

 * the (@begin, @end) range, the range does not move.

 * 

 * Since: 2.14

 **/

EXPORT_C void

g_sequence_move_range (GSequenceIter *dest,

                       GSequenceIter *begin,

                       GSequenceIter *end)

{

  GSequence *src_seq;

  GSequenceNode *first;

  g_return_if_fail (begin != NULL);

  g_return_if_fail (end != NULL);

  check_iter_access (begin);

  check_iter_access (end);

  if (dest)

    check_iter_access (dest);

  src_seq = get_sequence (begin);

  g_return_if_fail (src_seq == get_sequence (end));