/* 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.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/>.

 */

#include "config.h"

#include "gsequence.h"

#include "gmem.h"

#include "gtestutils.h"

#include "gslice.h"

/**

 * SECTION:sequence

 * @title: Sequences

 * @short_description: scalable lists

 *

 * The #GSequence data structure has the API of a list, but is

 * implemented internally with a balanced binary tree. This means that

 * it is possible to maintain a sorted list of n elements in time O(n log n).

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

 * of the [Type Conversion Macros][glib-Type-Conversion-Macros], or simply

 * pointers to any type of data.

 *

 * A #GSequence is accessed through "iterators", represented by a

 * #GSequenceIter. An iterator represents a position between two

 * elements of the sequence. For example, the "begin" iterator

 * represents the gap immediately before the first element of the

 * sequence, and the "end" iterator represents the gap immediately

 * after the last element. In an empty sequence, the begin and end

 * iterators are the same.

 *

 * Some methods on #GSequence operate on ranges of items. For example

 * g_sequence_foreach_range() will call a user-specified function on

 * each element with the given range. The range is delimited by the

 * gaps represented by the passed-in iterators, so if you pass in the

 * begin and end iterators, the range in question is the entire

 * sequence.

 *

 * The function g_sequence_get() is used with an iterator to access the

 * element immediately following the gap that the iterator represents.

 * The iterator is said to "point" to that element.

 *

 * Iterators are stable across most operations on a #GSequence. For

 * example an iterator pointing to some element of a sequence will

 * continue to point to that element even after the sequence is sorted.

 * Even moving an element to another sequence using for example

 * g_sequence_move_range() will not invalidate the iterators pointing

 * to it. The only operation that will invalidate an iterator is when

 * the element it points to is removed from any sequence.

 *

 * To sort the data, either use g_sequence_insert_sorted() or

 * g_sequence_insert_sorted_iter() to add data to the #GSequence or, if

 * you want to add a large amount of data, it is more efficient to call

 * g_sequence_sort() or g_sequence_sort_iter() after doing unsorted

 * insertions.

 */

/**

 * GSequenceIter:

 *

 * The #GSequenceIter struct is an opaque data type representing an

 * iterator pointing into a #GSequence.

 */

/**

 * GSequenceIterCompareFunc:

 * @a: a #GSequenceIter

 * @b: a #GSequenceIter

 * @data: user data

 *

 * A #GSequenceIterCompareFunc is a function used to compare iterators.

 * It must return zero if the iterators compare equal, a negative value

 * if @a comes before @b, and a positive value if @b comes before @a.

 *

 * Returns: zero if the iterators are equal, a negative value if @a

 *     comes before @b, and a positive value if @b comes before @a.

 */

typedef struct _GSequenceNode GSequenceNode;

/**

 * GSequence:

 *

 * The #GSequence struct is an opaque data type representing a

 * [sequence][glib-Sequences] data type.

 */

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          (GSequenceNode            *haystack,

                                          GSequenceNode            *needle,

                                          GSequenceNode            *end,

                                          GSequenceIterCompareFunc  cmp,

                                          gpointer                  user_data);

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 gboolean

seq_is_end (GSequence     *seq,

            GSequenceIter *iter)

{

  return seq->end_node == iter;

}

static gboolean

is_end (GSequenceIter *iter)

{

  GSequenceIter *parent = iter->parent;

  if (iter->right)

    return FALSE;

  if (!parent)

    return TRUE;

  while (parent->right == iter)

    {

      iter = parent;

      parent = iter->parent;

      if (!parent)

        return TRUE;

    }

  return FALSE;

}

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: (nullable): 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.

 *

 * Returns: (transfer full): a new #GSequence

 *

 * Since: 2.14

 **/

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

 */

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. @func must not modify the sequence

 * itself.

 *

 * Since: 2.14

 */

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. @func must not modify the sequence itself.

 *

 * Since: 2.14

 */

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 exactly 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.

 *

 * Returns: (transfer none): a #GSequenceIter pointing somewhere in the

 *    (@begin, @end) range

 *

 * Since: 2.14

 */

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.

 *

 * Returns: 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

 */

gint

g_sequence_iter_compare (GSequenceIter *a,

                         GSequenceIter *b)

{

  gint a_pos, b_pos;

  GSequence *seq_a, *seq_b;

  g_return_val_if_fail (a != NULL, 0);

  g_return_val_if_fail (b != NULL, 0);

  seq_a = get_sequence (a);

  seq_b = get_sequence (b);

  g_return_val_if_fail (seq_a == seq_b, 0);

  check_seq_access (seq_a);

  check_seq_access (seq_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 #GSequence

 * @data: the data for the new item

 *

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

 *

 * Returns: (transfer none): an iterator pointing to the new item

 *

 * Since: 2.14

 */

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

 *

 * Returns: (transfer none): an iterator pointing to the new item

 *

 * Since: 2.14

 */

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.

 *

 * Returns: (transfer none): an iterator pointing to the new item

 *

 * Since: 2.14

 */

GSequenceIter *

g_sequence_insert_before (GSequenceIter *iter,

                          gpointer       data)

{

  GSequence *seq;

  GSequenceNode *node;

  g_return_val_if_fail (iter != NULL, NULL);

  seq = get_sequence (iter);

  check_seq_access (seq);

  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 sequence has a data destroy function associated with it, this

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

 *

 * Since: 2.14

 */

void

g_sequence_remove (GSequenceIter *iter)

{

  GSequence *seq;

  g_return_if_fail (iter != NULL);

  seq = get_sequence (iter);

  g_return_if_fail (!seq_is_end (seq, iter));

  check_seq_access (seq);

  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

 */

void

g_sequence_remove_range (GSequenceIter *begin,

                         GSequenceIter *end)

{

  GSequence *seq_begin, *seq_end;

  seq_begin = get_sequence (begin);

  seq_end = get_sequence (end);

  g_return_if_fail (seq_begin == seq_end);

  /* check_seq_access() calls are done by g_sequence_move_range() */

  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

 */

void

g_sequence_move_range (GSequenceIter *dest,

                       GSequenceIter *begin,

                       GSequenceIter *end)

{

  GSequence *src_seq, *end_seq, *dest_seq;

  GSequenceNode *first;

  g_return_if_fail (begin != NULL);

  g_return_if_fail (end != NULL);

  src_seq = get_sequence (begin);

  check_seq_access (src_seq);

  end_seq = get_sequence (end);

  check_seq_access (end_seq);

  if (dest)

    {

      dest_seq = get_sequence (dest);

      check_seq_access (dest_seq);

    }

  g_return_if_fail (src_seq == end_seq);

  /* Dest points to begin or end? */

  if (dest == begin || dest == end)

    return;

  /* begin comes after end? */

  if (g_sequence_iter_compare (begin, end) >= 0)

    return;

  /* dest points somewhere in the (begin, end) range? */

  if (dest && dest_seq == src_seq &&

      g_sequence_iter_compare (dest, begin) > 0 &&

      g_sequence_iter_compare (dest, end) < 0)

    {

      return;

    }

  first = node_get_first (begin);

  node_cut (begin);

  node_cut (end);

  if (first != begin)

    node_join (first, end);

  if (dest)

    {

      first = node_get_first (dest);

      node_cut (dest);

      node_join (begin, dest);

      if (dest != first)

        node_join (first, begin);

    }

  else

    {

      node_free (begin, src_seq);

    }

}

/**

 * g_sequence_sort:

 * @seq: a #GSequence

 * @cmp_func: the function used to sort the sequence

 * @cmp_data: user data passed to @cmp_func

 *

 * Sorts @seq using @cmp_func.

 *

 * @cmp_func is passed two items of @seq 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.

 *

 * Since: 2.14

 */

void

g_sequence_sort (GSequence        *seq,

                 GCompareDataFunc  cmp_func,

                 gpointer          cmp_data)

{

  SortInfo info;

  info.cmp_func = cmp_func;

  info.cmp_data = cmp_data;

  info.end_node = seq->end_node;

  check_seq_access (seq);

  g_sequence_sort_iter (seq, iter_compare, &info;;

}

/**

 * g_sequence_insert_sorted:

 * @seq: a #GSequence

 * @data: the data to insert

 * @cmp_func: the function used to compare items in the sequence

 * @cmp_data: user data passed to @cmp_func.

 *

 * Inserts @data into @sequence using @func to determine the new

 * position. The sequence must already be sorted according to @cmp_func;

 * otherwise the new position of @data is undefined.

 *

 * @cmp_func is called with two items of the @seq and @user_data.

 * It should return 0 if the items are equal, a negative value

 * if the first item comes before the second, and a positive value

 * if the second  item comes before the first.

 *

 * Note that when adding a large amount of data to a #GSequence,

 * it is more efficient to do unsorted insertions and then call

 * g_sequence_sort() or g_sequence_sort_iter().

 *

 * Returns: (transfer none): a #GSequenceIter pointing to the new item.

 *

 * Since: 2.14

 */

GSequenceIter *

g_sequence_insert_sorted (GSequence        *seq,

                          gpointer          data,

                          GCompareDataFunc  cmp_func,

                          gpointer          cmp_data)

{

  SortInfo info;

  g_return_val_if_fail (seq != NULL, NULL);

  g_return_val_if_fail (cmp_func != NULL, NULL);

  info.cmp_func = cmp_func;

  info.cmp_data = cmp_data;

  info.end_node = seq->end_node;

  check_seq_access (seq);

  return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info;;

}

/**

 * g_sequence_sort_changed:

 * @iter: A #GSequenceIter

 * @cmp_func: the function used to compare items in the sequence

 * @cmp_data: user data passed to @cmp_func.

 *

 * Moves the data pointed to a new position as indicated by @cmp_func. This

 * function should be called for items in a sequence already sorted according

 * to @cmp_func whenever some aspect of an item changes so that @cmp_func

 * may return different values for that item.

 *

 * @cmp_func is called with two items of the @seq and @user_data.

 * It should return 0 if the items are equal, a negative value if

 * the first item comes before the second, and a positive value if

 * the second item comes before the first.

 *

 * Since: 2.14

 */

void

g_sequence_sort_changed (GSequenceIter    *iter,

                         GCompareDataFunc  cmp_func,

                         gpointer          cmp_data)

{

  GSequence *seq;

  SortInfo info;

  g_return_if_fail (iter != NULL);

  seq = get_sequence (iter);

  /* check_seq_access() call is done by g_sequence_sort_changed_iter() */

  g_return_if_fail (!seq_is_end (seq, iter));

  info.cmp_func = cmp_func;

  info.cmp_data = cmp_data;

  info.end_node = seq->end_node;

  g_sequence_sort_changed_iter (iter, iter_compare, &info;;

}

/**

 * g_sequence_search:

 * @seq: a #GSequence

 * @data: data for the new item

 * @cmp_func: the function used to compare items in the sequence

 * @cmp_data: user data passed to @cmp_func

 *

 * Returns an iterator pointing to the position where @data would

 * be inserted according to @cmp_func and @cmp_data.

 *

 * @cmp_func is called with two items of the @seq and @user_data.

 * It should return 0 if the items are equal, a negative value if

 * the first item comes before the second, and a positive value if

 * the second item comes before the first.

 *

 * If you are simply searching for an existing element of the sequence,

 * consider using g_sequence_lookup().

 *

 * This function will fail if the data contained in the sequence is

 * unsorted.

 *

 * Returns: (transfer none): an #GSequenceIter pointing to the position where @data

 *     would have been inserted according to @cmp_func and @cmp_data

 *

 * Since: 2.14

 */

GSequenceIter *

g_sequence_search (GSequence        *seq,

                   gpointer          data,

                   GCompareDataFunc  cmp_func,

                   gpointer          cmp_data)

{

  SortInfo info;

  g_return_val_if_fail (seq != NULL, NULL);

  info.cmp_func = cmp_func;

  info.cmp_data = cmp_data;

  info.end_node = seq->end_node;

  check_seq_access (seq);

  return g_sequence_search_iter (seq, data, iter_compare, &info;;

}

/**

 * g_sequence_lookup:

 * @seq: a #GSequence

 * @data: data to lookup

 * @cmp_func: the function used to compare items in the sequence

 * @cmp_data: user data passed to @cmp_func

 *

 * Returns an iterator pointing to the position of the first item found

 * equal to @data according to @cmp_func and @cmp_data. If more than one

 * item is equal, it is not guaranteed that it is the first which is

 * returned. In that case, you can use g_sequence_iter_next() and

 * g_sequence_iter_prev() to get others.

 *

 * @cmp_func is called with two items of the @seq and @user_data.

 * It should return 0 if the items are equal, a negative value if

 * the first item comes before the second, and a positive value if

 * the second item comes before the first.

 *

 * This function will fail if the data contained in the sequence is

 * unsorted.

 *

 * Returns: (transfer none) (nullable): an #GSequenceIter pointing to the position of the

 *     first item found equal to @data according to @cmp_func and

 *     @cmp_data, or %NULL if no such item exists

 *

 * Since: 2.28

 */

GSequenceIter *

g_sequence_lookup (GSequence        *seq,

                   gpointer          data,

                   GCompareDataFunc  cmp_func,

                   gpointer          cmp_data)

{

  SortInfo info;

  g_return_val_if_fail (seq != NULL, NULL);

  info.cmp_func = cmp_func;

  info.cmp_data = cmp_data;

  info.end_node = seq->end_node;

  check_seq_access (seq);

  return g_sequence_lookup_iter (seq, data, iter_compare, &info;;

}

/**

 * g_sequence_sort_iter:

 * @seq: a #GSequence

 * @cmp_func: the function used to compare iterators in the sequence

 * @cmp_data: user data passed to @cmp_func

 *

 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead

 * of a GCompareDataFunc as the compare function

 *

 * @cmp_func is called with two iterators pointing into @seq. It should