Logo Search packages:      
Sourcecode: matchbox-desktop version File versions  Download package

eggsequence.c

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

#include "eggsequence.h"

typedef struct _EggSequenceNode EggSequenceNode;

00026 struct _EggSequence
{
    EggSequenceNode *    end_node;
    GDestroyNotify       data_destroy_notify;
    gboolean             access_prohibited;
};

00033 struct _EggSequenceNode
{
    gint n_nodes;
    EggSequenceNode *parent;    
    EggSequenceNode *left;
    EggSequenceNode *right;
    gpointer data;            /* For the end node, this field points
                         * to the sequence
                         */
};

static EggSequenceNode *node_new           (gpointer           data);
static EggSequenceNode *node_get_first     (EggSequenceNode   *node);
static EggSequenceNode *node_get_last      (EggSequenceNode   *node);
static EggSequenceNode *node_get_prev      (EggSequenceNode   *node);
static EggSequenceNode *node_get_next      (EggSequenceNode   *node);
static gint             node_get_pos       (EggSequenceNode   *node);
static EggSequenceNode *node_get_by_pos    (EggSequenceNode   *node,
                                  gint               pos);
static EggSequenceNode *node_find_closest  (EggSequenceNode   *haystack,
                                  EggSequenceNode   *needle,
                                  EggSequenceNode   *end,
                                  EggSequenceIterCompareFunc cmp,
                                  gpointer           user_data);
static gint             node_get_length    (EggSequenceNode   *node);
static void             node_free          (EggSequenceNode   *node,
                                  EggSequence       *seq);
static void             node_cut           (EggSequenceNode   *split);
static void             node_insert_after  (EggSequenceNode   *node,
                                  EggSequenceNode   *second);
static void             node_insert_before (EggSequenceNode   *node,
                                  EggSequenceNode   *new);
static void             node_unlink        (EggSequenceNode   *node);
static void             node_insert_sorted (EggSequenceNode   *node,
                                  EggSequenceNode   *new,
                                  EggSequenceNode   *end,
                                  EggSequenceIterCompareFunc cmp_func,
                                  gpointer           cmp_data);

static EggSequence *
get_sequence (EggSequenceNode *node)
{
    return (EggSequence *)node_get_last (node)->data;
}

static void
check_seq_access (EggSequence *seq)
{
    if (G_UNLIKELY (seq->access_prohibited))
    {
      g_warning ("Accessing a sequence while it is "
               "being sorted or searched is not allowed");
    }
}

static void
check_iter_access (EggSequenceIter *iter)
{
    check_seq_access (get_sequence (iter));
}

static gboolean
is_end (EggSequenceIter *iter)
{
    EggSequence *seq = get_sequence (iter);
    
    return seq->end_node == iter;
}

/*
 * Public API
 */

/**
 * egg_sequence_new:
 * @data_destroy: A #GDestroyNotify function, or %NULL
 * 
 * Creates a new EggSequence. The @data_destroy function will be called
 * on all items when the sequence is destroyed and on items that are
 * removed from the sequence.
 * 
 * Return value: A new #EggSequence
 * 
 * Since: 2.14
 **/
EggSequence *
egg_sequence_new (GDestroyNotify data_destroy)
{
    EggSequence *seq = g_new (EggSequence, 1);
    seq->data_destroy_notify = data_destroy;
    
    seq->end_node = node_new (seq);
    
    seq->access_prohibited = FALSE;
    
    return seq;
}

/**
 * egg_sequence_free:
 * @seq: a #EggSequence
 * 
 * Frees the memory allocated for @seq. If @seq has a destroy notify
 * function associated with it, that function is called on all items in
 * @seq.
 * 
 * Since: 2.14
 **/
void
egg_sequence_free (EggSequence *seq)
{
    g_return_if_fail (seq != NULL);
    
    check_seq_access (seq);
    
    node_free (seq->end_node, seq);
    
    g_free (seq);
}

/**
 * egg_sequence_foreach_range:
 * @begin: a #EggSequenceIter
 * @end: a #EggSequenceIter
 * @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
 **/
void
egg_sequence_foreach_range (EggSequenceIter *begin,
                      EggSequenceIter *end,
                      GFunc        func,
                      gpointer           user_data)
{
    EggSequence *seq;
    EggSequenceIter *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)
    {
      EggSequenceIter *next = node_get_next (iter);
      
      func (iter->data, user_data);
      
      iter = next;
    }
    
    seq->access_prohibited = FALSE;
}

/**
 * egg_sequence_foreach:
 * @seq: a #EggSequence
 * @func: the function to call for each item in @seq
 * @data: user data passed to @func
 * 
 * Calls @func for each item in the sequence passing @user_data
 * to the function.
 * 
 * Since: 2.14
 **/
void
egg_sequence_foreach (EggSequence *seq,
                  GFunc        func,
                  gpointer     data)
{
    EggSequenceIter *begin, *end;
    
    check_seq_access (seq);
    
    begin = egg_sequence_get_begin_iter (seq);
    end   = egg_sequence_get_end_iter (seq);
    
    egg_sequence_foreach_range (begin, end, func, data);
}

/**
 * egg_sequence_range_get_midpoint:
 * @begin: a #EggSequenceIter
 * @end: a #EggSequenceIter
 * 
 * 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 <emphasize>exactly</emphasize> 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 #EggSequenceIter which is close to the middle of
 * the (@begin, @end) range.
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_range_get_midpoint (EggSequenceIter *begin,
                         EggSequenceIter *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);
}

/**
 * egg_sequence_iter_compare:
 * @a: a #EggSequenceIter
 * @b: a #EggSequenceIter
 * 
 * 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
 **/
gint
egg_sequence_iter_compare (EggSequenceIter *a,
                     EggSequenceIter *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;
}

/**
 * egg_sequence_append:
 * @seq: a #EggSequencePointer
 * @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
 **/
EggSequenceIter *
egg_sequence_append (EggSequence *seq,
                 gpointer     data)
{
    EggSequenceNode *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;
}

/**
 * egg_sequence_prepend:
 * @seq: a #EggSequence
 * @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
 **/
EggSequenceIter *
egg_sequence_prepend (EggSequence *seq,
                  gpointer     data)
{
    EggSequenceNode *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;
}

/**
 * egg_sequence_insert_before:
 * @iter: a #EggSequenceIter
 * @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
 **/
EggSequenceIter *
egg_sequence_insert_before (EggSequenceIter *iter,
                      gpointer         data)
{
    EggSequenceNode *node;
    
    g_return_val_if_fail (iter != NULL, NULL);
    
    check_iter_access (iter);
    
    node = node_new (data);
    
    node_insert_before (iter, node);
    
    return node;
}

/**
 * egg_sequence_remove:
 * @iter: a #EggSequenceIter
 * 
 * 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
 **/
void
egg_sequence_remove (EggSequenceIter *iter)
{
    EggSequence *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);
}

/**
 * egg_sequence_remove_range:
 * @begin: a #EggSequenceIter
 * @end: a #EggSequenceIter
 * 
 * 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
egg_sequence_remove_range (EggSequenceIter *begin,
                     EggSequenceIter *end)
{
    g_return_if_fail (get_sequence (begin) == get_sequence (end));

    check_iter_access (begin);
    check_iter_access (end);
    
    egg_sequence_move_range (NULL, begin, end);
}

/**
 * egg_sequence_move_range:
 * @dest: a #EggSequenceIter
 * @begin: a #EggSequenceIter
 * @end: a #EggSequenceIter
 * 
 * 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
egg_sequence_move_range (EggSequenceIter *dest,
                   EggSequenceIter *begin,
                   EggSequenceIter *end)
{
    EggSequence *src_seq;
    EggSequenceNode *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));

    /* Dest points to begin or end? */
    if (dest == begin || dest == end)
      return;

    /* begin comes after end? */
    if (egg_sequence_iter_compare (begin, end) >= 0)
      return;

    /* dest points somewhere in the (begin, end) range? */
    if (dest && get_sequence (dest) == src_seq &&
      egg_sequence_iter_compare (dest, begin) > 0 &&
      egg_sequence_iter_compare (dest, end) < 0)
    {
      return;
    }
    
    src_seq = get_sequence (begin);

    first = node_get_first (begin);

    node_cut (begin);

    node_cut (end);

    if (first != begin)
      node_insert_after (node_get_last (first), end);

    if (dest)
      node_insert_before (dest, begin);
    else
      node_free (begin, src_seq);
}

00503 typedef struct
{
    GCompareDataFunc    cmp_func;
    gpointer            cmp_data;
    EggSequenceNode     *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 (EggSequenceIter *node1,
            EggSequenceIter *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;
}

/**
 * egg_sequence_sort:
 * @seq: a #EggSequence
 * @cmp_func: the #GCompareDataFunc used to sort @seq. This function is
 *       passed two items of @seq and should return 0 if they are equal,
 *       a negative value fi the first comes before the second, and a
 *       positive value if the second comes before the first.
 * @cmp_data: user data passed to @cmp_func
 * 
 * Sorts @seq using @cmp_func.
 * 
 * Since: 2.14
 **/
void
egg_sequence_sort (EggSequence      *seq,
               GCompareDataFunc  cmp_func,
               gpointer          cmp_data)
{
    SortInfo info = { cmp_func, cmp_data, seq->end_node };
    
    check_seq_access (seq);
    
    egg_sequence_sort_iter (seq, iter_compare, &info);
}

/**
 * egg_sequence_insert_sorted:
 * @seq: a #EggSequence
 * @data: the data to insert
 * @cmp_func: the #GCompareDataFunc used to compare items in the queue. It
 *     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.
 * @cmp_data: user data passed to @cmp_func.
 *
 * Inserts @data into @queue using @func to determine the new position.
 * @seq must already be sorted according to @cmp_func; otherwise the
 * new position of is undefined.
 *
 * Return value: A #EggSequenceIter pointing to the new item.
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_insert_sorted (EggSequence       *seq,
                      gpointer           data,
                      GCompareDataFunc   cmp_func,
                      gpointer           cmp_data)
{
    SortInfo info = { cmp_func, cmp_data, NULL };
    
    g_return_val_if_fail (seq != NULL, NULL);
    g_return_val_if_fail (cmp_func != NULL, NULL);
    
    info.end_node = seq->end_node;
    check_seq_access (seq);
    
    return egg_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
}

/**
 * egg_sequence_sort_changed:
 * @iter: A #EggSequenceIter
 * @cmp_func: the #GCompareDataFunc used to compare items in the queue. It
 *     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.
 * @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.
 * 
 * Since: 2.14
 **/
void
egg_sequence_sort_changed (EggSequenceIter  *iter,
                     GCompareDataFunc  cmp_func,
                     gpointer          cmp_data)
{
    SortInfo info = { cmp_func, cmp_data, NULL };
    
    g_return_if_fail (!is_end (iter));
    
    info.end_node = get_sequence (iter)->end_node;
    check_iter_access (iter);
    
    egg_sequence_sort_changed_iter (iter, iter_compare, &info);
}

/**
 * egg_sequence_search:
 * @seq: a #EggSequence
 * @data: data for the new item
 * @cmp_func: the #GCompareDataFunc used to compare items in the queue. It
 *     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.
 * @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.
 * 
 * Return value: An #EggSequenceIter pointing to the position where @data
 * would have been inserted according to @cmp_func and @cmp_data.
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_search (EggSequence      *seq,
                 gpointer          data,
                 GCompareDataFunc  cmp_func,
                 gpointer          cmp_data)
{
    SortInfo info = { cmp_func, cmp_data, NULL };
    
    g_return_val_if_fail (seq != NULL, NULL);
    
    info.end_node = seq->end_node;
    check_seq_access (seq);
    
    return egg_sequence_search_iter (seq, data, iter_compare, &info);
}

/**
 * egg_sequence_sort_iter:
 * @seq: a #EggSequence
 * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
 *     sequence. It is called with two iterators pointing into @seq. It should
 *     return 0 if the iterators are equal, a negative value if the first
 *     iterator comes before the second, and a positive value if the second
 *     iterator comes before the first.
 * @cmp_data: user data passed to @cmp_func
 *
 * Like egg_sequence_sort(), but uses a #EggSequenceIterCompareFunc instead
 * of a GCompareDataFunc as the compare function
 * 
 * Since: 2.14
 **/
void
egg_sequence_sort_iter (EggSequence                *seq,
                  EggSequenceIterCompareFunc  cmp_func,
                  gpointer              cmp_data)
{
    EggSequence *tmp;
    EggSequenceNode *begin, *end;
    
    g_return_if_fail (seq != NULL);
    g_return_if_fail (cmp_func != NULL);
    
    check_seq_access (seq);
    
    begin = egg_sequence_get_begin_iter (seq);
    end   = egg_sequence_get_end_iter (seq);
    
    tmp = egg_sequence_new (NULL);
    
    egg_sequence_move_range (egg_sequence_get_begin_iter (tmp), begin, end);
    
    tmp->access_prohibited = TRUE;
    seq->access_prohibited = TRUE;
    
    while (egg_sequence_get_length (tmp) > 0)
    {
      EggSequenceNode *node = egg_sequence_get_begin_iter (tmp);
      
      node_unlink (node);
      
      node_insert_sorted (seq->end_node, node, seq->end_node, cmp_func, cmp_data);
    }
    
    tmp->access_prohibited = FALSE;
    seq->access_prohibited = FALSE;
    
    egg_sequence_free (tmp);
}

/**
 * egg_sequence_sort_changed_iter:
 * @iter: a #EggSequenceIter
 * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
 *     sequence. It is called with two iterators pointing into @seq. It should
 *     return 0 if the iterators are equal, a negative value if the first
 *     iterator comes before the second, and a positive value if the second
 *     iterator comes before the first.
 * @cmp_data: user data passed to @cmp_func
 *
 * Like egg_sequence_sort_changed(), but uses
 * a #EggSequenceIterCompareFunc instead of a #GCompareDataFunc as
 * the compare function.
 * 
 * Since: 2.14
 **/
void
egg_sequence_sort_changed_iter (EggSequenceIter            *iter,
                        EggSequenceIterCompareFunc  iter_cmp,
                        gpointer              cmp_data)
{
    EggSequence *seq;
    EggSequenceIter *next, *prev;
    
    g_return_if_fail (!is_end (iter));
    
    check_iter_access (iter);

    /* If one of the neighbours is equal to iter, then
     * don't move it. This ensures that sort_changed() is
     * a stable operation.
     */

    next = node_get_next (iter);
    prev = node_get_prev (iter);

    if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
      return;

    if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
      return;
    
    seq = get_sequence (iter);
    
    seq->access_prohibited = TRUE;
    
    node_unlink (iter);
    node_insert_sorted (seq->end_node, iter, seq->end_node, iter_cmp, cmp_data);
    
    seq->access_prohibited = FALSE;
}

/**
 * egg_sequence_insert_sorted_iter:
 * @seq: a #EggSequence
 * @data: data for the new item
 * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
 *     sequence. It is called with two iterators pointing into @seq. It should
 *     return 0 if the iterators are equal, a negative value if the first
 *     iterator comes before the second, and a positive value if the second
 *     iterator comes before the first.
 * @cmp_data: user data passed to @cmp_func
 * 
 * Like egg_sequence_insert_sorted(), but uses
 * a #EggSequenceIterCompareFunc instead of a #GCompareDataFunc as
 * the compare function.
 * 
 * Return value: A #EggSequenceIter pointing to the new item
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_insert_sorted_iter   (EggSequence                *seq,
                           gpointer                    data,
                           EggSequenceIterCompareFunc  iter_cmp,
                           gpointer              cmp_data)
{
    EggSequenceNode *new_node;
    EggSequence *tmp_seq;
    
    check_seq_access (seq);

    /* Create a new temporary sequence and put the new node into
     * that. The reason for this is that the user compare function
     * will be called with the new node, and if it dereferences, 
     * "is_end" will be called on it. But that will crash if the
     * node is not actually in a sequence.
     *
     * node_insert_sorted() makes sure the node is unlinked before
     * is is inserted.
     *
     * The reason we need the "iter" versions at all is that that
     * is the only kind of compare functions GtkTreeView can use.
     */
    tmp_seq = egg_sequence_new (NULL);
    new_node = egg_sequence_append (tmp_seq, data);

    node_insert_sorted (seq->end_node, new_node,
                  seq->end_node, iter_cmp, cmp_data);

    egg_sequence_free (tmp_seq);
    
    return new_node;
}

/**
 * egg_sequence_search_iter:
 * @seq: a #EggSequence
 * @data: data for the new item
 * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
 *     sequence. It is called with two iterators pointing into @seq. It should
 *     return 0 if the iterators are equal, a negative value if the first
 *     iterator comes before the second, and a positive value if the second
 *     iterator comes before the first.
 * @cmp_data: user data passed to @cmp_func
 *
 * Like egg_sequence_search(), but uses
 * a #EggSequenceIterCompareFunc instead of a #GCompareDataFunc as
 * the compare function.
 * 
 * Return value: A #EggSequenceIter pointing to the position in @seq
 * where @data would have been inserted according to @cmp_func and @cmp_data.
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_search_iter (EggSequence                *seq,
                    gpointer                    data,
                    EggSequenceIterCompareFunc  cmp_func,
                    gpointer                    cmp_data)
{
    EggSequenceNode *node;
    EggSequenceNode *dummy;
    
    g_return_val_if_fail (seq != NULL, NULL);
    
    check_seq_access (seq);
    
    seq->access_prohibited = TRUE;

    dummy = node_new (data);
    
    node = node_find_closest (seq->end_node, dummy,
                        seq->end_node, cmp_func, cmp_data);

    node_free (dummy, NULL);
    
    seq->access_prohibited = FALSE;
    
    return node;
}

/**
 * egg_sequence_iter_get_sequence:
 * @iter: a #EggSequenceIter
 * 
 * Returns the #EggSequence that @iter points into.
 * 
 * Return value: The #EggSequence that @iter points into.
 * 
 * Since: 2.14
 **/
EggSequence *
egg_sequence_iter_get_sequence (EggSequenceIter *iter)
{
    g_return_val_if_fail (iter != NULL, NULL);
    
    return get_sequence (iter);
}

/**
 * egg_sequence_get:
 * @iter: a #EggSequenceIter
 * 
 * Returns the data that @iter points to.
 * 
 * Return value: The data that @iter points to
 * 
 * Since: 2.14
 **/
gpointer
egg_sequence_get (EggSequenceIter *iter)
{
    g_return_val_if_fail (iter != NULL, NULL);
    g_return_val_if_fail (!is_end (iter), NULL);
    
    return iter->data;
}

/**
 * egg_sequence_set:
 * @iter: a #EggSequenceIter
 * @data: new data for the item
 * 
 * Changes the data for the item pointed to by @iter to be @data. If
 * the sequence has a data destroy function associated with it, that
 * function is called on the existing data that @iter pointed to.
 * 
 * Since: 2.14
 **/
void
egg_sequence_set (EggSequenceIter *iter,
              gpointer         data)
{
    EggSequence *seq;
    
    g_return_if_fail (iter != NULL);
    g_return_if_fail (!is_end (iter));
    
    seq = get_sequence (iter);

    /* If @data is identical to iter->data, it is destroyed
     * here. This will work right in case of ref-counted objects. Also
     * it is similar to what ghashtables do.
     *
     * For non-refcounted data it's a little less convenient, but
     * code relying on self-setting not destroying would be
     * pretty dubious anyway ...
     */
    
    if (seq->data_destroy_notify)
      seq->data_destroy_notify (iter->data);
    
    iter->data = data;
}

/**
 * egg_sequence_get_length:
 * @seq: a #EggSequence
 * 
 * Returns the length of @seq
 * 
 * Return value: The length of @seq
 * 
 * Since: 2.14
 **/
gint
egg_sequence_get_length (EggSequence *seq)
{
    return node_get_length (seq->end_node) - 1;
}

/**
 * egg_sequence_get_end_iter:
 * @seq: a #EggSequence 
 * 
 * Returns the end iterator for @seg
 * 
 * Return value: The end iterator for @seq
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_get_end_iter (EggSequence *seq)
{
    g_return_val_if_fail (seq != NULL, NULL);
    
    g_assert (is_end (seq->end_node));
    
    return seq->end_node;
}

/**
 * egg_sequence_get_begin_iter:
 * @seq: a #EggSequence
 * 
 * Returns the begin iterator for @seq.
 * 
 * Return value: The begin iterator for @seq.
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_get_begin_iter (EggSequence *seq)
{
    g_return_val_if_fail (seq != NULL, NULL);
    return node_get_first (seq->end_node);
}

static int
clamp_position (EggSequence *seq,
            int          pos)
{
    gint len = egg_sequence_get_length (seq);
    
    if (pos > len || pos < 0)
      pos = len;
    
    return pos;
}

/*
 * if pos > number of items or -1, will return end pointer
 */
/**
 * egg_sequence_get_iter_at_pos:
 * @seq: a #EggSequence
 * @pos: a position in @seq, or -1 for the end.
 * 
 * Returns the iterator as position @pos. If @pos is negative or larger
 * than the number of items in @seq, the end iterator is returned.
 * 
 * Return value: The #EggSequenceIter at position @pos
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_get_iter_at_pos (EggSequence *seq,
                        gint         pos)
{
    g_return_val_if_fail (seq != NULL, NULL);
    
    pos = clamp_position (seq, pos);
    
    return node_get_by_pos (seq->end_node, pos);
}

/**
 * egg_sequence_move:
 * @src: a #EggSequenceIter pointing to the item to move
 * @dest: a #EggSequenceIter pointing to the position to which
 *        the item is moved.
 *
 * Move the item pointed to by @src to the position indicated by @dest.
 * After calling this function @dest will point to the position immediately
 * after @src.
 * 
 * Since: 2.14
 **/
void
egg_sequence_move (EggSequenceIter *src,
               EggSequenceIter *dest)
{
    g_return_if_fail (src != NULL);
    g_return_if_fail (dest != NULL);
    g_return_if_fail (!is_end (src));
    
    if (src == dest)
      return;
    
    node_unlink (src);
    node_insert_before (dest, src);
}

/* EggSequenceIter */

/**
 * egg_sequence_iter_is_end:
 * @iter: a #EggSequenceIter
 * 
 * Returns whether @iter is the end iterator
 * 
 * Return value: Whether @iter is the end iterator.
 * 
 * Since: 2.14
 **/
gboolean
egg_sequence_iter_is_end (EggSequenceIter *iter)
{
    g_return_val_if_fail (iter != NULL, FALSE);
    
    return is_end (iter);
}

/**
 * egg_sequence_iter_is_begin:
 * @iter: a #EggSequenceIter
 * 
 * Returns whether @iter is the begin iterator
 * 
 * Return value: Whether @iter is the begin iterator
 * 
 * Since: 2.14
 **/
gboolean
egg_sequence_iter_is_begin (EggSequenceIter *iter)
{
    g_return_val_if_fail (iter != NULL, FALSE);
    
    return (node_get_prev (iter) == iter);
}

/**
 * egg_sequence_iter_get_position:
 * @iter: a #EggSequenceIter
 * 
 * Returns the position of @iter
 * 
 * Return value: The position of @iter
 * 
 * Since: 2.14
 **/
gint
egg_sequence_iter_get_position (EggSequenceIter *iter)
{
    g_return_val_if_fail (iter != NULL, -1);
    
    return node_get_pos (iter);
}

/**
 * egg_sequence_iter_next:
 * @iter: a #EggSequenceIter
 * 
 * Returns an iterator pointing to the next position after @iter. If
 * @iter is the end iterator, the end iterator is returned.
 * 
 * Return value: A #EggSequenceIter pointing to the next position after @iter.
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_iter_next (EggSequenceIter *iter)
{
    g_return_val_if_fail (iter != NULL, NULL);
    
    return node_get_next (iter);
}

/**
 * egg_sequence_iter_prev:
 * @iter: a #EggSequenceIter
 * 
 * Returns an iterator pointing to the previous position before @iter. If
 * @iter is the begin iterator, the begin iterator is returned.
 * 
 * Return value: A #EggSequenceIter pointing to the previous position before
 * @iter.
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_iter_prev (EggSequenceIter *iter)
{
    g_return_val_if_fail (iter != NULL, NULL);
    
    return node_get_prev (iter);
}

/**
 * egg_sequence_iter_move:
 * @iter: a #EggSequenceIter
 * @delta: A positive or negative number indicating how many positions away
 *    from @iter the returned #EggSequenceIter will be.
 *
 * Returns the #EggSequenceIter which is @delta positions away from @iter.
 * If @iter is closer than -@delta positions to the beginning of the sequence,
 * the begin iterator is returned. If @iter is closer than @delta positions
 * to the end of the queue, the end iterator is returned.
 *
 * Return value: a #EggSequenceIter which is @delta positions away from @iter.
 * 
 * Since: 2.14
 **/
EggSequenceIter *
egg_sequence_iter_move (EggSequenceIter *iter,
                  gint             delta)
{
    gint new_pos;
    
    g_return_val_if_fail (iter != NULL, NULL);
    
    new_pos = node_get_pos (iter) + delta;
    
    new_pos = clamp_position (get_sequence (iter), new_pos);
    
    return node_get_by_pos (iter, new_pos);
}

/**
 * egg_sequence_swap:
 * @a: a #EggSequenceIter
 * @b: a #EggSequenceIter
 * 
 * Swaps the items pointed to by @a and @b
 * 
 * Since: 2.14
 **/
void
egg_sequence_swap (EggSequenceIter *a,
               EggSequenceIter *b)
{
    EggSequenceNode *leftmost, *rightmost, *rightmost_next;
    int a_pos, b_pos;
    
    g_return_if_fail (!egg_sequence_iter_is_end (a));
    g_return_if_fail (!egg_sequence_iter_is_end (b));
    
    if (a == b)
      return;
    
    a_pos = egg_sequence_iter_get_position (a);
    b_pos = egg_sequence_iter_get_position (b);
    
    if (a_pos > b_pos)
    {
      leftmost = b;
      rightmost = a;
    }
    else
    {
      leftmost = a;
      rightmost = b;
    }
    
    rightmost_next = node_get_next (rightmost);
    
    /* Situation is now like this:
     *
     *     ..., leftmost, ......., rightmost, rightmost_next, ...
     *
     */
    egg_sequence_move (rightmost, leftmost);
    egg_sequence_move (leftmost, rightmost_next);
}

/*
 * Implementation of the node_* methods
 */
static void
node_update_fields (EggSequenceNode *node)
{
    g_assert (node != NULL);
    
    node->n_nodes = 1;
    
    if (node->left)
      node->n_nodes += node->left->n_nodes;
    
    if (node->right)
      node->n_nodes += node->right->n_nodes;
}

#define NODE_LEFT_CHILD(n)  (((n)->parent) && ((n)->parent->left) == (n))
#define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))

static void
node_rotate (EggSequenceNode *node)
{
    EggSequenceNode *tmp, *old;
    
    g_assert (node->parent);
    g_assert (node->parent != node);
    
    if (NODE_LEFT_CHILD (node))
    {
      /* rotate right */
      tmp = node->right;
      
      node->right = node->parent;
      node->parent = node->parent->parent;
      if (node->parent)
      {
          if (node->parent->left == node->right)
            node->parent->left = node;
          else
            node->parent->right = node;
      }
      
      g_assert (node->right);
      
      node->right->parent = node;
      node->right->left = tmp;
      
      if (node->right->left)
          node->right->left->parent = node->right;
      
      old = node->right;
    }
    else
    {
      /* rotate left */
      tmp = node->left;
      
      node->left = node->parent;
      node->parent = node->parent->parent;
      if (node->parent)
      {
          if (node->parent->right == node->left)
            node->parent->right = node;
          else
            node->parent->left = node;
      }
      
      g_assert (node->left);
      
      node->left->parent = node;
      node->left->right = tmp;
      
      if (node->left->right)
          node->left->right->parent = node->left;
      
      old = node->left;
    }
    
    node_update_fields (old);
    node_update_fields (node);
}

static EggSequenceNode *
splay (EggSequenceNode *node)
{
    while (node->parent)
    {
      if (!node->parent->parent)
      {
          /* zig */
          node_rotate (node);
      }
      else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) ||
             (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent)))
      {
          /* zig-zig */
          node_rotate (node->parent);
          node_rotate (node);
      }
      else
      {
          /* zig-zag */
          node_rotate (node);
          node_rotate (node);
      }
    }
    
    return node;
}

static EggSequenceNode *
node_new (gpointer data)
{
    EggSequenceNode *node = g_slice_new0 (EggSequenceNode);

    node->parent = NULL;
    node->parent = NULL;
    node->left = NULL;
    node->right = NULL;
    
    node->data = data;
    node->n_nodes = 1;
    
    return node;
}

static EggSequenceNode *
find_min (EggSequenceNode *node)
{
    splay (node);
    
    while (node->left)
      node = node->left;
    
    return node;
}

static EggSequenceNode *
find_max (EggSequenceNode *node)
{
    splay (node);
    
    while (node->right)
      node = node->right;
    
    return node;
}

static EggSequenceNode *
node_get_first   (EggSequenceNode    *node)
{
    return splay (find_min (node));
}

static EggSequenceNode *
node_get_last    (EggSequenceNode    *node)
{
    return splay (find_max (node));
}

static gint
get_n_nodes (EggSequenceNode *node)
{
    if (node)
      return node->n_nodes;
    else
      return 0;
}

static EggSequenceNode *
node_get_by_pos  (EggSequenceNode *node,
              gint             pos)
{
    gint i;
    
    g_assert (node != NULL);
    
    splay (node);
    
    while ((i = get_n_nodes (node->left)) != pos)
    {
      if (i < pos)
      {
          node = node->right;
          pos -= (i + 1);
      }
      else
      {
          node = node->left;
          g_assert (node->parent != NULL);
      }
    }
    
    return splay (node);
}

static EggSequenceNode *
node_get_prev  (EggSequenceNode    *node)
{
    splay (node);
    
    if (node->left)
    {
      node = node->left;
      while (node->right)
          node = node->right;
    }
    
    return splay (node);
}

static EggSequenceNode *
node_get_next         (EggSequenceNode    *node)
{
    splay (node);
    
    if (node->right)
    {
      node = node->right;
      while (node->left)
          node = node->left;
    }
    
    return splay (node);
}

static gint
node_get_pos (EggSequenceNode    *node)
{
    splay (node);
    
    return get_n_nodes (node->left);
}

/* Return closest node _strictly_ bigger than @needle (does always exist because
 * there is an end_node)
 */
static EggSequenceNode *
node_find_closest (EggSequenceNode        *haystack,
               EggSequenceNode            *needle,
               EggSequenceNode            *end,
               EggSequenceIterCompareFunc  cmp_func,
               gpointer              cmp_data)
{
    EggSequenceNode *best;
    gint c;
    
    g_assert (haystack);
    
    haystack = splay (haystack);
    
    do
    {
      best = haystack;

      /* cmp_func can't be called with the end node (it may be user-supplied) */
      if (haystack == end)
          c = 1;
      else
          c = cmp_func (haystack, needle, cmp_data);

      /* In the following we don't break even if c == 0. Instaed we go on searching
       * along the 'bigger' nodes, so that we find the last one that is equal
       * to the needle.
       */
      if (c > 0)
          haystack = haystack->left;
      else
          haystack = haystack->right;
    }
    while (haystack != NULL);
    
     /* If the best node is smaller or equal to the data, then move one step
     * to the right to make sure the best one is strictly bigger than the data
     */
    if (best != end && c <= 0)
      best = node_get_next (best);
    
    return best;
}

static void
node_free (EggSequenceNode *node,
         EggSequence     *seq)
{
    GQueue *stack = g_queue_new ();

    splay (node);
    
    g_queue_push_head (stack, node);
    
    while (!g_queue_is_empty (stack))
    {
      node = g_queue_pop_head (stack);
      
      if (node)
      {
          g_queue_push_head (stack, node->right);
          g_queue_push_head (stack, node->left);
          
          if (seq && seq->data_destroy_notify && node != seq->end_node)
            seq->data_destroy_notify (node->data);
          
          g_slice_free (EggSequenceNode, node);
      }
    }
    
    g_queue_free (stack);
}

/* Splits into two trees, left and right. 
 * @node will be part of the right tree
 */

static void
node_cut (EggSequenceNode *node)
{
    splay (node);

    g_assert (node->parent == NULL);
    
    if (node->left)
      node->left->parent = NULL;
    
    node->left = NULL;
    node_update_fields (node);
}

static void
node_insert_before (EggSequenceNode *node,
                EggSequenceNode *new)
{
    g_assert (node != NULL);
    g_assert (new != NULL);
    
    splay (node);
    
    new = splay (find_min (new));
    g_assert (new->left == NULL);
    
    if (node->left)
      node->left->parent = new;
    
    new->left = node->left;
    new->parent = node;
    
    node->left = new;
    
    node_update_fields (new);
    node_update_fields (node);
}

static void
node_insert_after (EggSequenceNode *node,
               EggSequenceNode *new)
{
    g_assert (node != NULL);
    g_assert (new != NULL);
    
    splay (node);
    
    new = splay (find_max (new));
    g_assert (new->right == NULL);
    g_assert (node->parent == NULL);
    
    if (node->right)
      node->right->parent = new;
    
    new->right = node->right;
    new->parent = node;
    
    node->right = new;
    
    node_update_fields (new);
    node_update_fields (node);
}

static gint
node_get_length (EggSequenceNode    *node)
{
    g_assert (node != NULL);
    
    splay (node);
    return node->n_nodes;
}

static void
node_unlink (EggSequenceNode *node)
{
    EggSequenceNode *right, *left;
    
    splay (node);
    
    left = node->left;
    right = node->right;
    
    node->parent = node->left = node->right = NULL;
    node_update_fields (node);
    
    if (right)
    {
      right->parent = NULL;
      
      right = node_get_first (right);
      g_assert (right->left == NULL);
      
      right->left = left;
      if (left)
      {
          left->parent = right;
          node_update_fields (right);
      }
    }
    else if (left)
    {
      left->parent = NULL;
    }
}

static void
node_insert_sorted (EggSequenceNode *node,
                EggSequenceNode *new,
                EggSequenceNode *end,
                EggSequenceIterCompareFunc cmp_func,
                gpointer cmp_data)
{
    EggSequenceNode *closest;
    
    closest = node_find_closest (node, new, end, cmp_func, cmp_data);

    node_unlink (new);
    
    node_insert_before (closest, new);
}

static gint
node_calc_height (EggSequenceNode *node)
{
    gint left_height;
    gint right_height;
    
    if (node)
    {
      left_height = 0;
      right_height = 0;
      
      if (node->left)
          left_height = node_calc_height (node->left);
      
      if (node->right)
          right_height = node_calc_height (node->right);
      
      return MAX (left_height, right_height) + 1;
    }
    
    return 0;
}

/* Self test functions */

static void
check_node (EggSequenceNode *node)
{
    if (node)
    {
      g_assert (node->parent != node);
      g_assert (node->n_nodes ==
              1 + get_n_nodes (node->left) + get_n_nodes (node->right));
      check_node (node->left);
      check_node (node->right);
    }
}

void
egg_sequence_self_test (EggSequence *seq)
{
    EggSequenceNode *node = splay (seq->end_node);
    
    check_node (node);
}

Generated by  Doxygen 1.6.0   Back to index