attic/fluttr/src/eggsequence.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007  Soeren Sandmann (sandmann@daimi.au.dk)
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include <glib.h>
  21
  22 #include "eggsequence.h"
  23
  24 typedef struct _EggSequenceNode EggSequenceNode;
  25
  26 struct _EggSequence
  27 {
  28     EggSequenceNode *    end_node;
  29     GDestroyNotify       data_destroy_notify;
  30     gboolean             access_prohibited;
  31 };
  32
  33 struct _EggSequenceNode
  34 {
  35     gint n_nodes;
  36     EggSequenceNode *parent;
  37     EggSequenceNode *left;
  38     EggSequenceNode *right;
  39     gpointer data;              /* For the end node, this field points
  40                                  * to the sequence
  41                                  */
  42 };
  43
  44 static EggSequenceNode *node_new           (gpointer           data);
  45 static EggSequenceNode *node_get_first     (EggSequenceNode   *node);
  46 static EggSequenceNode *node_get_last      (EggSequenceNode   *node);
  47 static EggSequenceNode *node_get_prev      (EggSequenceNode   *node);
  48 static EggSequenceNode *node_get_next      (EggSequenceNode   *node);
  49 static gint             node_get_pos       (EggSequenceNode   *node);
  50 static EggSequenceNode *node_get_by_pos    (EggSequenceNode   *node,
  51                                             gint               pos);
  52 static EggSequenceNode *node_find_closest  (EggSequenceNode   *haystack,
  53                                             EggSequenceNode   *needle,
  54                                             EggSequenceNode   *end,
  55                                             EggSequenceIterCompareFunc cmp,
  56                                             gpointer           user_data);
  57 static gint             node_get_length    (EggSequenceNode   *node);
  58 static void             node_free          (EggSequenceNode   *node,
  59                                             EggSequence       *seq);
  60 static void             node_cut           (EggSequenceNode   *split);
  61 static void             node_insert_after  (EggSequenceNode   *node,
  62                                             EggSequenceNode   *second);
  63 static void             node_insert_before (EggSequenceNode   *node,
  64                                             EggSequenceNode   *new);
  65 static void             node_unlink        (EggSequenceNode   *node);
  66 static void             node_insert_sorted (EggSequenceNode   *node,
  67                                             EggSequenceNode   *new,
  68                                             EggSequenceNode   *end,
  69                                             EggSequenceIterCompareFunc cmp_func,
  70                                             gpointer           cmp_data);
  71
  72 static EggSequence *
  73 get_sequence (EggSequenceNode *node)
  74 {
  75     return (EggSequence *)node_get_last (node)->data;
  76 }
  77
  78 static void
  79 check_seq_access (EggSequence *seq)
  80 {
  81     if (G_UNLIKELY (seq->access_prohibited))
  82     {
  83         g_warning ("Accessing a sequence while it is "
  84                    "being sorted or searched is not allowed");
  85     }
  86 }
  87
  88 static void
  89 check_iter_access (EggSequenceIter *iter)
  90 {
  91     check_seq_access (get_sequence (iter));
  92 }
  93
  94 static gboolean
  95 is_end (EggSequenceIter *iter)
  96 {
  97     EggSequence *seq = get_sequence (iter);
  98
  99     return seq->end_node == iter;
 100 }
 101
 102 /*
 103  * Public API
 104  */
 105
 106 /**
 107  * egg_sequence_new:
 108  * @data_destroy: A #GDestroyNotify function, or %NULL
 109  *
 110  * Creates a new EggSequence. The @data_destroy function will be called
 111  * on all items when the sequence is destroyed and on items that are
 112  * removed from the sequence.
 113  *
 114  * Return value: A new #EggSequence
 115  *
 116  * Since: 2.14
 117  **/
 118 EggSequence *
 119 egg_sequence_new (GDestroyNotify data_destroy)
 120 {
 121     EggSequence *seq = g_new (EggSequence, 1);
 122     seq->data_destroy_notify = data_destroy;
 123
 124     seq->end_node = node_new (seq);
 125
 126     seq->access_prohibited = FALSE;
 127
 128     return seq;
 129 }
 130
 131 /**
 132  * egg_sequence_free:
 133  * @seq: a #EggSequence
 134  *
 135  * Frees the memory allocated for @seq. If @seq has a destroy notify
 136  * function associated with it, that function is called on all items in
 137  * @seq.
 138  *
 139  * Since: 2.14
 140  **/
 141 void
 142 egg_sequence_free (EggSequence *seq)
 143 {
 144     g_return_if_fail (seq != NULL);
 145
 146     check_seq_access (seq);
 147
 148     node_free (seq->end_node, seq);
 149
 150     g_free (seq);
 151 }
 152
 153 /**
 154  * egg_sequence_foreach_range:
 155  * @begin: a #EggSequenceIter
 156  * @end: a #EggSequenceIter
 157  * @func: a #GFunc
 158  * @user_data: user data passed to @func
 159  *
 160  * Calls @func for each item in the range (@begin, @end) passing
 161  * @user_data to the function.
 162  *
 163  * Since: 2.14
 164  **/
 165 void
 166 egg_sequence_foreach_range (EggSequenceIter *begin,
 167                             EggSequenceIter *end,
 168                             GFunc            func,
 169                             gpointer         user_data)
 170 {
 171     EggSequence *seq;
 172     EggSequenceIter *iter;
 173
 174     g_return_if_fail (func != NULL);
 175     g_return_if_fail (begin != NULL);
 176     g_return_if_fail (end != NULL);
 177
 178     seq = get_sequence (begin);
 179
 180     seq->access_prohibited = TRUE;
 181
 182     iter = begin;
 183     while (iter != end)
 184     {
 185         EggSequenceIter *next = node_get_next (iter);
 186
 187         func (iter->data, user_data);
 188
 189         iter = next;
 190     }
 191
 192     seq->access_prohibited = FALSE;
 193 }
 194
 195 /**
 196  * egg_sequence_foreach:
 197  * @seq: a #EggSequence
 198  * @func: the function to call for each item in @seq
 199  * @data: user data passed to @func
 200  *
 201  * Calls @func for each item in the sequence passing @user_data
 202  * to the function.
 203  *
 204  * Since: 2.14
 205  **/
 206 void
 207 egg_sequence_foreach (EggSequence *seq,
 208                       GFunc        func,
 209                       gpointer     data)
 210 {
 211     EggSequenceIter *begin, *end;
 212
 213     check_seq_access (seq);
 214
 215     begin = egg_sequence_get_begin_iter (seq);
 216     end   = egg_sequence_get_end_iter (seq);
 217
 218     egg_sequence_foreach_range (begin, end, func, data);
 219 }
 220
 221 /**
 222  * egg_sequence_range_get_midpoint:
 223  * @begin: a #EggSequenceIter
 224  * @end: a #EggSequenceIter
 225  *
 226  * Finds an iterator somewhere in the range (@begin, @end). This
 227  * iterator will be close to the middle of the range, but is not
 228  * guaranteed to be <emphasize>exactly</emphasize> in the middle.
 229  *
 230  * The @begin and @end iterators must both point to the same sequence and
 231  * @begin must come before or be equal to @end in the sequence.
 232  *
 233  * Return value: A #EggSequenceIter which is close to the middle of
 234  * the (@begin, @end) range.
 235  *
 236  * Since: 2.14
 237  **/
 238 EggSequenceIter *
 239 egg_sequence_range_get_midpoint (EggSequenceIter *begin,
 240                                  EggSequenceIter *end)
 241 {
 242     int begin_pos, end_pos, mid_pos;
 243
 244     g_return_val_if_fail (begin != NULL, NULL);
 245     g_return_val_if_fail (end != NULL, NULL);
 246     g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
 247
 248     begin_pos = node_get_pos (begin);
 249     end_pos = node_get_pos (end);
 250
 251     g_return_val_if_fail (end_pos >= begin_pos, NULL);
 252
 253     mid_pos = begin_pos + (end_pos - begin_pos) / 2;
 254
 255     return node_get_by_pos (begin, mid_pos);
 256 }
 257
 258 /**
 259  * egg_sequence_iter_compare:
 260  * @a: a #EggSequenceIter
 261  * @b: a #EggSequenceIter
 262  *
 263  * Returns a negative number if @a comes before @b, 0 if they are equal,
 264  * and a positive number if @a comes after @b.
 265  *
 266  * The @a and @b iterators must point into the same sequence.
 267  *
 268  * Return value: A negative number if @a comes before @b, 0 if they are
 269  * equal, and a positive number if @a comes after @b.
 270  *
 271  * Since: 2.14
 272  **/
 273 gint
 274 egg_sequence_iter_compare (EggSequenceIter *a,
 275                            EggSequenceIter *b)
 276 {
 277     gint a_pos, b_pos;
 278
 279     g_return_val_if_fail (a != NULL, 0);
 280     g_return_val_if_fail (b != NULL, 0);
 281     g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0);
 282
 283     check_iter_access (a);
 284     check_iter_access (b);
 285
 286     a_pos = node_get_pos (a);
 287     b_pos = node_get_pos (b);
 288
 289     if (a_pos == b_pos)
 290         return 0;
 291     else if (a_pos > b_pos)
 292         return 1;
 293     else
 294         return -1;
 295 }
 296
 297 /**
 298  * egg_sequence_append:
 299  * @seq: a #EggSequencePointer
 300  * @data: the data for the new item
 301  *
 302  * Adds a new item to the end of @seq.
 303  *
 304  * Return value: An iterator pointing to the new item
 305  *
 306  * Since: 2.14
 307  **/
 308 EggSequenceIter *
 309 egg_sequence_append (EggSequence *seq,
 310                      gpointer     data)
 311 {
 312     EggSequenceNode *node;
 313
 314     g_return_val_if_fail (seq != NULL, NULL);
 315
 316     check_seq_access (seq);
 317
 318     node = node_new (data);
 319     node_insert_before (seq->end_node, node);
 320
 321     return node;
 322 }
 323
 324 /**
 325  * egg_sequence_prepend:
 326  * @seq: a #EggSequence
 327  * @data: the data for the new item
 328  *
 329  * Adds a new item to the front of @seq
 330  *
 331  * Return value: An iterator pointing to the new item
 332  *
 333  * Since: 2.14
 334  **/
 335 EggSequenceIter *
 336 egg_sequence_prepend (EggSequence *seq,
 337                       gpointer     data)
 338 {
 339     EggSequenceNode *node, *first;
 340
 341     g_return_val_if_fail (seq != NULL, NULL);
 342
 343     check_seq_access (seq);
 344
 345     node = node_new (data);
 346     first = node_get_first (seq->end_node);
 347
 348     node_insert_before (first, node);
 349
 350     return node;
 351 }
 352
 353 /**
 354  * egg_sequence_insert_before:
 355  * @iter: a #EggSequenceIter
 356  * @data: the data for the new item
 357  *
 358  * Inserts a new item just before the item pointed to by @iter.
 359  *
 360  * Return value: An iterator pointing to the new item
 361  *
 362  * Since: 2.14
 363  **/
 364 EggSequenceIter *
 365 egg_sequence_insert_before (EggSequenceIter *iter,
 366                             gpointer         data)
 367 {
 368     EggSequenceNode *node;
 369
 370     g_return_val_if_fail (iter != NULL, NULL);
 371
 372     check_iter_access (iter);
 373
 374     node = node_new (data);
 375
 376     node_insert_before (iter, node);
 377
 378     return node;
 379 }
 380
 381 /**
 382  * egg_sequence_remove:
 383  * @iter: a #EggSequenceIter
 384  *
 385  * Removes the item pointed to by @iter. It is an error to pass the
 386  * end iterator to this function.
 387  *
 388  * If the sequnce has a data destroy function associated with it, this
 389  * function is called on the data for the removed item.
 390  *
 391  * Since: 2.14
 392  **/
 393 void
 394 egg_sequence_remove (EggSequenceIter *iter)
 395 {
 396     EggSequence *seq;
 397
 398     g_return_if_fail (iter != NULL);
 399     g_return_if_fail (!is_end (iter));
 400
 401     check_iter_access (iter);
 402
 403     seq = get_sequence (iter);
 404
 405     node_unlink (iter);
 406     node_free (iter, seq);
 407 }
 408
 409 /**
 410  * egg_sequence_remove_range:
 411  * @begin: a #EggSequenceIter
 412  * @end: a #EggSequenceIter
 413  *
 414  * Removes all items in the (@begin, @end) range.
 415  *
 416  * If the sequence has a data destroy function associated with it, this
 417  * function is called on the data for the removed items.
 418  *
 419  * Since: 2.14
 420  **/
 421 void
 422 egg_sequence_remove_range (EggSequenceIter *begin,
 423                            EggSequenceIter *end)
 424 {
 425     g_return_if_fail (get_sequence (begin) == get_sequence (end));
 426
 427     check_iter_access (begin);
 428     check_iter_access (end);
 429
 430     egg_sequence_move_range (NULL, begin, end);
 431 }
 432
 433 /**
 434  * egg_sequence_move_range:
 435  * @dest: a #EggSequenceIter
 436  * @begin: a #EggSequenceIter
 437  * @end: a #EggSequenceIter
 438  *
 439  * Inserts the (@begin, @end) range at the destination pointed to by ptr.
 440  * The @begin and @end iters must point into the same sequence. It is
 441  * allowed for @dest to point to a different sequence than the one pointed
 442  * into by @begin and @end.
 443  *
 444  * If @dest is NULL, the range indicated by @begin and @end is
 445  * removed from the sequence. If @dest iter points to a place within
 446  * the (@begin, @end) range, the range does not move.
 447  *
 448  * Since: 2.14
 449  **/
 450 void
 451 egg_sequence_move_range (EggSequenceIter *dest,
 452                          EggSequenceIter *begin,
 453                          EggSequenceIter *end)
 454 {
 455     EggSequence *src_seq;
 456     EggSequenceNode *first;
 457
 458     g_return_if_fail (begin != NULL);
 459     g_return_if_fail (end != NULL);
 460
 461     check_iter_access (begin);
 462     check_iter_access (end);
 463     if (dest)
 464         check_iter_access (dest);
 465
 466     src_seq = get_sequence (begin);
 467
 468     g_return_if_fail (src_seq == get_sequence (end));
 469
 470     /* Dest points to begin or end? */
 471     if (dest == begin || dest == end)
 472         return;
 473
 474     /* begin comes after end? */
 475     if (egg_sequence_iter_compare (begin, end) >= 0)
 476         return;
 477
 478     /* dest points somewhere in the (begin, end) range? */
 479     if (dest && get_sequence (dest) == src_seq &&
 480         egg_sequence_iter_compare (dest, begin) > 0 &&
 481         egg_sequence_iter_compare (dest, end) < 0)
 482     {
 483         return;
 484     }
 485
 486     src_seq = get_sequence (begin);
 487
 488     first = node_get_first (begin);
 489
 490     node_cut (begin);
 491
 492     node_cut (end);
 493
 494     if (first != begin)
 495         node_insert_after (node_get_last (first), end);
 496
 497     if (dest)
 498         node_insert_before (dest, begin);
 499     else
 500         node_free (begin, src_seq);
 501 }
 502
 503 typedef struct
 504 {
 505     GCompareDataFunc    cmp_func;
 506     gpointer            cmp_data;
 507     EggSequenceNode     *end_node;
 508 } SortInfo;
 509
 510 /* This function compares two iters using a normal compare
 511  * function and user_data passed in in a SortInfo struct
 512  */
 513 static gint
 514 iter_compare (EggSequenceIter *node1,
 515               EggSequenceIter *node2,
 516               gpointer data)
 517 {
 518     const SortInfo *info = data;
 519     gint retval;
 520
 521     if (node1 == info->end_node)
 522         return 1;
 523
 524     if (node2 == info->end_node)
 525         return -1;
 526
 527     retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
 528
 529     return retval;
 530 }
 531
 532 /**
 533  * egg_sequence_sort:
 534  * @seq: a #EggSequence
 535  * @cmp_func: the #GCompareDataFunc used to sort @seq. This function is
 536  *       passed two items of @seq and should return 0 if they are equal,
 537  *       a negative value fi the first comes before the second, and a
 538  *       positive value if the second comes before the first.
 539  * @cmp_data: user data passed to @cmp_func
 540  *
 541  * Sorts @seq using @cmp_func.
 542  *
 543  * Since: 2.14
 544  **/
 545 void
 546 egg_sequence_sort (EggSequence      *seq,
 547                    GCompareDataFunc  cmp_func,
 548                    gpointer          cmp_data)
 549 {
 550     SortInfo info = { cmp_func, cmp_data, seq->end_node };
 551
 552     check_seq_access (seq);
 553
 554     egg_sequence_sort_iter (seq, iter_compare, &info);
 555 }
 556
 557 /**
 558  * egg_sequence_insert_sorted:
 559  * @seq: a #EggSequence
 560  * @data: the data to insert
 561  * @cmp_func: the #GCompareDataFunc used to compare items in the queue. It
 562  *     is called with two items of the @seq and @user_data. It should
 563  *     return 0 if the items are equal, a negative value if the first
 564  *     item comes before the second, and a positive value if the second
 565  *     item comes before the first.
 566  * @cmp_data: user data passed to @cmp_func.
 567  *
 568  * Inserts @data into @queue using @func to determine the new position.
 569  * @seq must already be sorted according to @cmp_func; otherwise the
 570  * new position of is undefined.
 571  *
 572  * Return value: A #EggSequenceIter pointing to the new item.
 573  *
 574  * Since: 2.14
 575  **/
 576 EggSequenceIter *
 577 egg_sequence_insert_sorted (EggSequence       *seq,
 578                             gpointer           data,
 579                             GCompareDataFunc   cmp_func,
 580                             gpointer           cmp_data)
 581 {
 582     SortInfo info = { cmp_func, cmp_data, NULL };
 583
 584     g_return_val_if_fail (seq != NULL, NULL);
 585     g_return_val_if_fail (cmp_func != NULL, NULL);
 586
 587     info.end_node = seq->end_node;
 588     check_seq_access (seq);
 589
 590     return egg_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
 591 }
 592
 593 /**
 594  * egg_sequence_sort_changed:
 595  * @iter: A #EggSequenceIter
 596  * @cmp_func: the #GCompareDataFunc used to compare items in the queue. It
 597  *     is called with two items of the @seq and @user_data. It should
 598  *     return 0 if the items are equal, a negative value if the first
 599  *     item comes before the second, and a positive value if the second
 600  *     item comes before the first.
 601  * @cmp_data: user data passed to @cmp_func.
 602  *
 603  * Moves the data pointed to a new position as indicated by @cmp_func. This
 604  * function should be called for items in a sequence already sorted according
 605  * to @cmp_func whenever some aspect of an item changes so that @cmp_func
 606  * may return different values for that item.
 607  *
 608  * Since: 2.14
 609  **/
 610 void
 611 egg_sequence_sort_changed (EggSequenceIter  *iter,
 612                            GCompareDataFunc  cmp_func,
 613                            gpointer          cmp_data)
 614 {
 615     SortInfo info = { cmp_func, cmp_data, NULL };
 616
 617     g_return_if_fail (!is_end (iter));
 618
 619     info.end_node = get_sequence (iter)->end_node;
 620     check_iter_access (iter);
 621
 622     egg_sequence_sort_changed_iter (iter, iter_compare, &info);
 623 }
 624
 625 /**
 626  * egg_sequence_search:
 627  * @seq: a #EggSequence
 628  * @data: data for the new item
 629  * @cmp_func: the #GCompareDataFunc used to compare items in the queue. It
 630  *     is called with two items of the @seq and @user_data. It should
 631  *     return 0 if the items are equal, a negative value if the first
 632  *     item comes before the second, and a positive value if the second
 633  *     item comes before the first.
 634  * @cmp_data: user data passed to @cmp_func.
 635  *
 636  * Returns an iterator pointing to the position where @data would
 637  * be inserted according to @cmp_func and @cmp_data.
 638  *
 639  * Return value: An #EggSequenceIter pointing to the position where @data
 640  * would have been inserted according to @cmp_func and @cmp_data.
 641  *
 642  * Since: 2.14
 643  **/
 644 EggSequenceIter *
 645 egg_sequence_search (EggSequence      *seq,
 646                      gpointer          data,
 647                      GCompareDataFunc  cmp_func,
 648                      gpointer          cmp_data)
 649 {
 650     SortInfo info = { cmp_func, cmp_data, NULL };
 651
 652     g_return_val_if_fail (seq != NULL, NULL);
 653
 654     info.end_node = seq->end_node;
 655     check_seq_access (seq);
 656
 657     return egg_sequence_search_iter (seq, data, iter_compare, &info);
 658 }
 659
 660 /**
 661  * egg_sequence_sort_iter:
 662  * @seq: a #EggSequence
 663  * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
 664  *     sequence. It is called with two iterators pointing into @seq. It should
 665  *     return 0 if the iterators are equal, a negative value if the first
 666  *     iterator comes before the second, and a positive value if the second
 667  *     iterator comes before the first.
 668  * @cmp_data: user data passed to @cmp_func
 669  *
 670  * Like egg_sequence_sort(), but uses a #EggSequenceIterCompareFunc instead
 671  * of a GCompareDataFunc as the compare function
 672  *
 673  * Since: 2.14
 674  **/
 675 void
 676 egg_sequence_sort_iter (EggSequence                *seq,
 677                         EggSequenceIterCompareFunc  cmp_func,
 678                         gpointer                    cmp_data)
 679 {
 680     EggSequence *tmp;
 681     EggSequenceNode *begin, *end;
 682
 683     g_return_if_fail (seq != NULL);
 684     g_return_if_fail (cmp_func != NULL);
 685
 686     check_seq_access (seq);
 687
 688     begin = egg_sequence_get_begin_iter (seq);
 689     end   = egg_sequence_get_end_iter (seq);
 690
 691     tmp = egg_sequence_new (NULL);
 692
 693     egg_sequence_move_range (egg_sequence_get_begin_iter (tmp), begin, end);
 694
 695     tmp->access_prohibited = TRUE;
 696     seq->access_prohibited = TRUE;
 697
 698     while (egg_sequence_get_length (tmp) > 0)
 699     {
 700         EggSequenceNode *node = egg_sequence_get_begin_iter (tmp);
 701
 702         node_unlink (node);
 703
 704         node_insert_sorted (seq->end_node, node, seq->end_node, cmp_func, cmp_data);
 705     }
 706
 707     tmp->access_prohibited = FALSE;
 708     seq->access_prohibited = FALSE;
 709
 710     egg_sequence_free (tmp);
 711 }
 712
 713 /**
 714  * egg_sequence_sort_changed_iter:
 715  * @iter: a #EggSequenceIter
 716  * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
 717  *     sequence. It is called with two iterators pointing into @seq. It should
 718  *     return 0 if the iterators are equal, a negative value if the first
 719  *     iterator comes before the second, and a positive value if the second
 720  *     iterator comes before the first.
 721  * @cmp_data: user data passed to @cmp_func
 722  *
 723  * Like egg_sequence_sort_changed(), but uses
 724  * a #EggSequenceIterCompareFunc instead of a #GCompareDataFunc as
 725  * the compare function.
 726  *
 727  * Since: 2.14
 728  **/
 729 void
 730 egg_sequence_sort_changed_iter (EggSequenceIter            *iter,
 731                                 EggSequenceIterCompareFunc  iter_cmp,
 732                                 gpointer                    cmp_data)
 733 {
 734     EggSequence *seq;
 735     EggSequenceIter *next, *prev;
 736
 737     g_return_if_fail (!is_end (iter));
 738
 739     check_iter_access (iter);
 740
 741     /* If one of the neighbours is equal to iter, then
 742      * don't move it. This ensures that sort_changed() is
 743      * a stable operation.
 744      */
 745
 746     next = node_get_next (iter);
 747     prev = node_get_prev (iter);
 748
 749     if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
 750         return;
 751
 752     if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
 753         return;
 754
 755     seq = get_sequence (iter);
 756
 757     seq->access_prohibited = TRUE;
 758
 759     node_unlink (iter);
 760     node_insert_sorted (seq->end_node, iter, seq->end_node, iter_cmp, cmp_data);
 761
 762     seq->access_prohibited = FALSE;
 763 }
 764
 765 /**
 766  * egg_sequence_insert_sorted_iter:
 767  * @seq: a #EggSequence
 768  * @data: data for the new item
 769  * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
 770  *     sequence. It is called with two iterators pointing into @seq. It should
 771  *     return 0 if the iterators are equal, a negative value if the first
 772  *     iterator comes before the second, and a positive value if the second
 773  *     iterator comes before the first.
 774  * @cmp_data: user data passed to @cmp_func
 775  *
 776  * Like egg_sequence_insert_sorted(), but uses
 777  * a #EggSequenceIterCompareFunc instead of a #GCompareDataFunc as
 778  * the compare function.
 779  *
 780  * Return value: A #EggSequenceIter pointing to the new item
 781  *
 782  * Since: 2.14
 783  **/
 784 EggSequenceIter *
 785 egg_sequence_insert_sorted_iter   (EggSequence                *seq,
 786                                    gpointer                    data,
 787                                    EggSequenceIterCompareFunc  iter_cmp,
 788                                    gpointer                    cmp_data)
 789 {
 790     EggSequenceNode *new_node;
 791     EggSequence *tmp_seq;
 792
 793     check_seq_access (seq);
 794
 795     /* Create a new temporary sequence and put the new node into
 796      * that. The reason for this is that the user compare function
 797      * will be called with the new node, and if it dereferences,
 798      * "is_end" will be called on it. But that will crash if the
 799      * node is not actually in a sequence.
 800      *
 801      * node_insert_sorted() makes sure the node is unlinked before
 802      * is is inserted.
 803      *
 804      * The reason we need the "iter" versions at all is that that
 805      * is the only kind of compare functions GtkTreeView can use.
 806      */
 807     tmp_seq = egg_sequence_new (NULL);
 808     new_node = egg_sequence_append (tmp_seq, data);
 809
 810     node_insert_sorted (seq->end_node, new_node,
 811                         seq->end_node, iter_cmp, cmp_data);
 812
 813     egg_sequence_free (tmp_seq);
 814
 815     return new_node;
 816 }
 817
 818 /**
 819  * egg_sequence_search_iter:
 820  * @seq: a #EggSequence
 821  * @data: data for the new item
 822  * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
 823  *     sequence. It is called with two iterators pointing into @seq. It should
 824  *     return 0 if the iterators are equal, a negative value if the first
 825  *     iterator comes before the second, and a positive value if the second
 826  *     iterator comes before the first.
 827  * @cmp_data: user data passed to @cmp_func
 828  *
 829  * Like egg_sequence_search(), but uses
 830  * a #EggSequenceIterCompareFunc instead of a #GCompareDataFunc as
 831  * the compare function.
 832  *
 833  * Return value: A #EggSequenceIter pointing to the position in @seq
 834  * where @data would have been inserted according to @cmp_func and @cmp_data.
 835  *
 836  * Since: 2.14
 837  **/
 838 EggSequenceIter *
 839 egg_sequence_search_iter (EggSequence                *seq,
 840                           gpointer                    data,
 841                           EggSequenceIterCompareFunc  cmp_func,
 842                           gpointer                    cmp_data)
 843 {
 844     EggSequenceNode *node;
 845     EggSequenceNode *dummy;
 846
 847     g_return_val_if_fail (seq != NULL, NULL);
 848
 849     check_seq_access (seq);
 850
 851     seq->access_prohibited = TRUE;
 852
 853     dummy = node_new (data);
 854
 855     node = node_find_closest (seq->end_node, dummy,
 856                               seq->end_node, cmp_func, cmp_data);
 857
 858     node_free (dummy, NULL);
 859
 860     seq->access_prohibited = FALSE;
 861
 862     return node;
 863 }
 864
 865 /**
 866  * egg_sequence_iter_get_sequence:
 867  * @iter: a #EggSequenceIter
 868  *
 869  * Returns the #EggSequence that @iter points into.
 870  *
 871  * Return value: The #EggSequence that @iter points into.
 872  *
 873  * Since: 2.14
 874  **/
 875 EggSequence *
 876 egg_sequence_iter_get_sequence (EggSequenceIter *iter)
 877 {
 878     g_return_val_if_fail (iter != NULL, NULL);
 879
 880     return get_sequence (iter);
 881 }
 882
 883 /**
 884  * egg_sequence_get:
 885  * @iter: a #EggSequenceIter
 886  *
 887  * Returns the data that @iter points to.
 888  *
 889  * Return value: The data that @iter points to
 890  *
 891  * Since: 2.14
 892  **/
 893 gpointer
 894 egg_sequence_get (EggSequenceIter *iter)
 895 {
 896     g_return_val_if_fail (iter != NULL, NULL);
 897     g_return_val_if_fail (!is_end (iter), NULL);
 898
 899     return iter->data;
 900 }
 901
 902 /**
 903  * egg_sequence_set:
 904  * @iter: a #EggSequenceIter
 905  * @data: new data for the item
 906  *
 907  * Changes the data for the item pointed to by @iter to be @data. If
 908  * the sequence has a data destroy function associated with it, that
 909  * function is called on the existing data that @iter pointed to.
 910  *
 911  * Since: 2.14
 912  **/
 913 void
 914 egg_sequence_set (EggSequenceIter *iter,
 915                   gpointer         data)
 916 {
 917     EggSequence *seq;
 918
 919     g_return_if_fail (iter != NULL);
 920     g_return_if_fail (!is_end (iter));
 921
 922     seq = get_sequence (iter);
 923
 924     /* If @data is identical to iter->data, it is destroyed
 925      * here. This will work right in case of ref-counted objects. Also
 926      * it is similar to what ghashtables do.
 927      *
 928      * For non-refcounted data it's a little less convenient, but
 929      * code relying on self-setting not destroying would be
 930      * pretty dubious anyway ...
 931      */
 932
 933     if (seq->data_destroy_notify)
 934         seq->data_destroy_notify (iter->data);
 935
 936     iter->data = data;
 937 }
 938
 939 /**
 940  * egg_sequence_get_length:
 941  * @seq: a #EggSequence
 942  *
 943  * Returns the length of @seq
 944  *
 945  * Return value: The length of @seq
 946  *
 947  * Since: 2.14
 948  **/
 949 gint
 950 egg_sequence_get_length (EggSequence *seq)
 951 {
 952     return node_get_length (seq->end_node) - 1;
 953 }
 954
 955 /**
 956  * egg_sequence_get_end_iter:
 957  * @seq: a #EggSequence
 958  *
 959  * Returns the end iterator for @seg
 960  *
 961  * Return value: The end iterator for @seq
 962  *
 963  * Since: 2.14
 964  **/
 965 EggSequenceIter *
 966 egg_sequence_get_end_iter (EggSequence *seq)
 967 {
 968     g_return_val_if_fail (seq != NULL, NULL);
 969
 970     g_assert (is_end (seq->end_node));
 971
 972     return seq->end_node;
 973 }
 974
 975 /**
 976  * egg_sequence_get_begin_iter:
 977  * @seq: a #EggSequence
 978  *
 979  * Returns the begin iterator for @seq.
 980  *
 981  * Return value: The begin iterator for @seq.
 982  *
 983  * Since: 2.14
 984  **/
 985 EggSequenceIter *
 986 egg_sequence_get_begin_iter (EggSequence *seq)
 987 {
 988     g_return_val_if_fail (seq != NULL, NULL);
 989     return node_get_first (seq->end_node);
 990 }
 991
 992 static int
 993 clamp_position (EggSequence *seq,
 994                 int          pos)
 995 {
 996     gint len = egg_sequence_get_length (seq);
 997
 998     if (pos > len || pos < 0)
 999         pos = len;
1000
1001     return pos;
1002 }
1003
1004 /*
1005  * if pos > number of items or -1, will return end pointer
1006  */
1007 /**
1008  * egg_sequence_get_iter_at_pos:
1009  * @seq: a #EggSequence
1010  * @pos: a position in @seq, or -1 for the end.
1011  *
1012  * Returns the iterator as position @pos. If @pos is negative or larger
1013  * than the number of items in @seq, the end iterator is returned.
1014  *
1015  * Return value: The #EggSequenceIter at position @pos
1016  *
1017  * Since: 2.14
1018  **/
1019 EggSequenceIter *
1020 egg_sequence_get_iter_at_pos (EggSequence *seq,
1021                               gint         pos)
1022 {
1023     g_return_val_if_fail (seq != NULL, NULL);
1024
1025     pos = clamp_position (seq, pos);
1026
1027     return node_get_by_pos (seq->end_node, pos);
1028 }
1029
1030 /**
1031  * egg_sequence_move:
1032  * @src: a #EggSequenceIter pointing to the item to move
1033  * @dest: a #EggSequenceIter pointing to the position to which
1034  *        the item is moved.
1035  *
1036  * Move the item pointed to by @src to the position indicated by @dest.
1037  * After calling this function @dest will point to the position immediately
1038  * after @src.
1039  *
1040  * Since: 2.14
1041  **/
1042 void
1043 egg_sequence_move (EggSequenceIter *src,
1044                    EggSequenceIter *dest)
1045 {
1046     g_return_if_fail (src != NULL);
1047     g_return_if_fail (dest != NULL);
1048     g_return_if_fail (!is_end (src));
1049
1050     if (src == dest)
1051         return;
1052
1053     node_unlink (src);
1054     node_insert_before (dest, src);
1055 }
1056
1057 /* EggSequenceIter */
1058
1059 /**
1060  * egg_sequence_iter_is_end:
1061  * @iter: a #EggSequenceIter
1062  *
1063  * Returns whether @iter is the end iterator
1064  *
1065  * Return value: Whether @iter is the end iterator.
1066  *
1067  * Since: 2.14
1068  **/
1069 gboolean
1070 egg_sequence_iter_is_end (EggSequenceIter *iter)
1071 {
1072     g_return_val_if_fail (iter != NULL, FALSE);
1073
1074     return is_end (iter);
1075 }
1076
1077 /**
1078  * egg_sequence_iter_is_begin:
1079  * @iter: a #EggSequenceIter
1080  *
1081  * Returns whether @iter is the begin iterator
1082  *
1083  * Return value: Whether @iter is the begin iterator
1084  *
1085  * Since: 2.14
1086  **/
1087 gboolean
1088 egg_sequence_iter_is_begin (EggSequenceIter *iter)
1089 {
1090     g_return_val_if_fail (iter != NULL, FALSE);
1091
1092     return (node_get_prev (iter) == iter);
1093 }
1094
1095 /**
1096  * egg_sequence_iter_get_position:
1097  * @iter: a #EggSequenceIter
1098  *
1099  * Returns the position of @iter
1100  *
1101  * Return value: The position of @iter
1102  *
1103  * Since: 2.14
1104  **/
1105 gint
1106 egg_sequence_iter_get_position (EggSequenceIter *iter)
1107 {
1108     g_return_val_if_fail (iter != NULL, -1);
1109
1110     return node_get_pos (iter);
1111 }
1112
1113 /**
1114  * egg_sequence_iter_next:
1115  * @iter: a #EggSequenceIter
1116  *
1117  * Returns an iterator pointing to the next position after @iter. If
1118  * @iter is the end iterator, the end iterator is returned.
1119  *
1120  * Return value: A #EggSequenceIter pointing to the next position after @iter.
1121  *
1122  * Since: 2.14
1123  **/
1124 EggSequenceIter *
1125 egg_sequence_iter_next (EggSequenceIter *iter)
1126 {
1127     g_return_val_if_fail (iter != NULL, NULL);
1128
1129     return node_get_next (iter);
1130 }
1131
1132 /**
1133  * egg_sequence_iter_prev:
1134  * @iter: a #EggSequenceIter
1135  *
1136  * Returns an iterator pointing to the previous position before @iter. If
1137  * @iter is the begin iterator, the begin iterator is returned.
1138  *
1139  * Return value: A #EggSequenceIter pointing to the previous position before
1140  * @iter.
1141  *
1142  * Since: 2.14
1143  **/
1144 EggSequenceIter *
1145 egg_sequence_iter_prev (EggSequenceIter *iter)
1146 {
1147     g_return_val_if_fail (iter != NULL, NULL);
1148
1149     return node_get_prev (iter);
1150 }
1151
1152 /**
1153  * egg_sequence_iter_move:
1154  * @iter: a #EggSequenceIter
1155  * @delta: A positive or negative number indicating how many positions away
1156  *    from @iter the returned #EggSequenceIter will be.
1157  *
1158  * Returns the #EggSequenceIter which is @delta positions away from @iter.
1159  * If @iter is closer than -@delta positions to the beginning of the sequence,
1160  * the begin iterator is returned. If @iter is closer than @delta positions
1161  * to the end of the queue, the end iterator is returned.
1162  *
1163  * Return value: a #EggSequenceIter which is @delta positions away from @iter.
1164  *
1165  * Since: 2.14
1166  **/
1167 EggSequenceIter *
1168 egg_sequence_iter_move (EggSequenceIter *iter,
1169                         gint             delta)
1170 {
1171     gint new_pos;
1172
1173     g_return_val_if_fail (iter != NULL, NULL);
1174
1175     new_pos = node_get_pos (iter) + delta;
1176
1177     new_pos = clamp_position (get_sequence (iter), new_pos);
1178
1179     return node_get_by_pos (iter, new_pos);
1180 }
1181
1182 /**
1183  * egg_sequence_swap:
1184  * @a: a #EggSequenceIter
1185  * @b: a #EggSequenceIter
1186  *
1187  * Swaps the items pointed to by @a and @b
1188  *
1189  * Since: 2.14
1190  **/
1191 void
1192 egg_sequence_swap (EggSequenceIter *a,
1193                    EggSequenceIter *b)
1194 {
1195     EggSequenceNode *leftmost, *rightmost, *rightmost_next;
1196     int a_pos, b_pos;
1197
1198     g_return_if_fail (!egg_sequence_iter_is_end (a));
1199     g_return_if_fail (!egg_sequence_iter_is_end (b));
1200
1201     if (a == b)
1202         return;
1203
1204     a_pos = egg_sequence_iter_get_position (a);
1205     b_pos = egg_sequence_iter_get_position (b);
1206
1207     if (a_pos > b_pos)
1208     {
1209         leftmost = b;
1210         rightmost = a;
1211     }
1212     else
1213     {
1214         leftmost = a;
1215         rightmost = b;
1216     }
1217
1218     rightmost_next = node_get_next (rightmost);
1219
1220     /* Situation is now like this:
1221      *
1222      *     ..., leftmost, ......., rightmost, rightmost_next, ...
1223      *
1224      */
1225     egg_sequence_move (rightmost, leftmost);
1226     egg_sequence_move (leftmost, rightmost_next);
1227 }
1228
1229 /*
1230  * Implementation of the node_* methods
1231  */
1232 static void
1233 node_update_fields (EggSequenceNode *node)
1234 {
1235     g_assert (node != NULL);
1236
1237     node->n_nodes = 1;
1238
1239     if (node->left)
1240         node->n_nodes += node->left->n_nodes;
1241
1242     if (node->right)
1243         node->n_nodes += node->right->n_nodes;
1244 }
1245
1246 #define NODE_LEFT_CHILD(n)  (((n)->parent) && ((n)->parent->left) == (n))
1247 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1248
1249 static void
1250 node_rotate (EggSequenceNode *node)
1251 {
1252     EggSequenceNode *tmp, *old;
1253
1254     g_assert (node->parent);
1255     g_assert (node->parent != node);
1256
1257     if (NODE_LEFT_CHILD (node))
1258     {
1259         /* rotate right */
1260         tmp = node->right;
1261
1262         node->right = node->parent;
1263         node->parent = node->parent->parent;
1264         if (node->parent)
1265         {
1266             if (node->parent->left == node->right)
1267                 node->parent->left = node;
1268             else
1269                 node->parent->right = node;
1270         }
1271
1272         g_assert (node->right);
1273
1274         node->right->parent = node;
1275         node->right->left = tmp;
1276
1277         if (node->right->left)
1278             node->right->left->parent = node->right;
1279
1280         old = node->right;
1281     }
1282     else
1283     {
1284         /* rotate left */
1285         tmp = node->left;
1286
1287         node->left = node->parent;
1288         node->parent = node->parent->parent;
1289         if (node->parent)
1290         {
1291             if (node->parent->right == node->left)
1292                 node->parent->right = node;
1293             else
1294                 node->parent->left = node;
1295         }
1296
1297         g_assert (node->left);
1298
1299         node->left->parent = node;
1300         node->left->right = tmp;
1301
1302         if (node->left->right)
1303             node->left->right->parent = node->left;
1304
1305         old = node->left;
1306     }
1307
1308     node_update_fields (old);
1309     node_update_fields (node);
1310 }
1311
1312 static EggSequenceNode *
1313 splay (EggSequenceNode *node)
1314 {
1315     while (node->parent)
1316     {
1317         if (!node->parent->parent)
1318         {
1319             /* zig */
1320             node_rotate (node);
1321         }
1322         else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) ||
1323                  (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent)))
1324         {
1325             /* zig-zig */
1326             node_rotate (node->parent);
1327             node_rotate (node);
1328         }
1329         else
1330         {
1331             /* zig-zag */
1332             node_rotate (node);
1333             node_rotate (node);
1334         }
1335     }
1336
1337     return node;
1338 }
1339
1340 static EggSequenceNode *
1341 node_new (gpointer data)
1342 {
1343     EggSequenceNode *node = g_slice_new0 (EggSequenceNode);
1344
1345     node->parent = NULL;
1346     node->parent = NULL;
1347     node->left = NULL;
1348     node->right = NULL;
1349
1350     node->data = data;
1351     node->n_nodes = 1;
1352
1353     return node;
1354 }
1355
1356 static EggSequenceNode *
1357 find_min (EggSequenceNode *node)
1358 {
1359     splay (node);
1360
1361     while (node->left)
1362         node = node->left;
1363
1364     return node;
1365 }
1366
1367 static EggSequenceNode *
1368 find_max (EggSequenceNode *node)
1369 {
1370     splay (node);
1371
1372     while (node->right)
1373         node = node->right;
1374
1375     return node;
1376 }
1377
1378 static EggSequenceNode *
1379 node_get_first   (EggSequenceNode    *node)
1380 {
1381     return splay (find_min (node));
1382 }
1383
1384 static EggSequenceNode *
1385 node_get_last    (EggSequenceNode    *node)
1386 {
1387     return splay (find_max (node));
1388 }
1389
1390 static gint
1391 get_n_nodes (EggSequenceNode *node)
1392 {
1393     if (node)
1394         return node->n_nodes;
1395     else
1396         return 0;
1397 }
1398
1399 static EggSequenceNode *
1400 node_get_by_pos  (EggSequenceNode *node,
1401                   gint             pos)
1402 {
1403     gint i;
1404
1405     g_assert (node != NULL);
1406
1407     splay (node);
1408
1409     while ((i = get_n_nodes (node->left)) != pos)
1410     {
1411         if (i < pos)
1412         {
1413             node = node->right;
1414             pos -= (i + 1);
1415         }
1416         else
1417         {
1418             node = node->left;
1419             g_assert (node->parent != NULL);
1420         }
1421     }
1422
1423     return splay (node);
1424 }
1425
1426 static EggSequenceNode *
1427 node_get_prev  (EggSequenceNode    *node)
1428 {
1429     splay (node);
1430
1431     if (node->left)
1432     {
1433         node = node->left;
1434         while (node->right)
1435             node = node->right;
1436     }
1437
1438     return splay (node);
1439 }
1440
1441 static EggSequenceNode *
1442 node_get_next         (EggSequenceNode    *node)
1443 {
1444     splay (node);
1445
1446     if (node->right)
1447     {
1448         node = node->right;
1449         while (node->left)
1450             node = node->left;
1451     }
1452
1453     return splay (node);
1454 }
1455
1456 static gint
1457 node_get_pos (EggSequenceNode    *node)
1458 {
1459     splay (node);
1460
1461     return get_n_nodes (node->left);
1462 }
1463
1464 /* Return closest node _strictly_ bigger than @needle (does always exist because
1465  * there is an end_node)
1466  */
1467 static EggSequenceNode *
1468 node_find_closest (EggSequenceNode            *haystack,
1469                    EggSequenceNode            *needle,
1470                    EggSequenceNode            *end,
1471                    EggSequenceIterCompareFunc  cmp_func,
1472                    gpointer                    cmp_data)
1473 {
1474     EggSequenceNode *best;
1475     gint c;
1476
1477     g_assert (haystack);
1478
1479     haystack = splay (haystack);
1480
1481     do
1482     {
1483         best = haystack;
1484
1485         /* cmp_func can't be called with the end node (it may be user-supplied) */
1486         if (haystack == end)
1487             c = 1;
1488         else
1489             c = cmp_func (haystack, needle, cmp_data);
1490
1491         /* In the following we don't break even if c == 0. Instaed we go on searching
1492          * along the 'bigger' nodes, so that we find the last one that is equal
1493          * to the needle.
1494          */
1495         if (c > 0)
1496             haystack = haystack->left;
1497         else
1498             haystack = haystack->right;
1499     }
1500     while (haystack != NULL);
1501
1502      /* If the best node is smaller or equal to the data, then move one step
1503      * to the right to make sure the best one is strictly bigger than the data
1504      */
1505     if (best != end && c <= 0)
1506         best = node_get_next (best);
1507
1508     return best;
1509 }
1510
1511 static void
1512 node_free (EggSequenceNode *node,
1513            EggSequence     *seq)
1514 {
1515     GQueue *stack = g_queue_new ();
1516
1517     splay (node);
1518
1519     g_queue_push_head (stack, node);
1520
1521     while (!g_queue_is_empty (stack))
1522     {
1523         node = g_queue_pop_head (stack);
1524
1525         if (node)
1526         {
1527             g_queue_push_head (stack, node->right);
1528             g_queue_push_head (stack, node->left);
1529
1530             if (seq && seq->data_destroy_notify && node != seq->end_node)
1531                 seq->data_destroy_notify (node->data);
1532
1533             g_slice_free (EggSequenceNode, node);
1534         }
1535     }
1536
1537     g_queue_free (stack);
1538 }
1539
1540 /* Splits into two trees, left and right.
1541  * @node will be part of the right tree
1542  */
1543
1544 static void
1545 node_cut (EggSequenceNode *node)
1546 {
1547     splay (node);
1548
1549     g_assert (node->parent == NULL);
1550
1551     if (node->left)
1552         node->left->parent = NULL;
1553
1554     node->left = NULL;
1555     node_update_fields (node);
1556 }
1557
1558 static void
1559 node_insert_before (EggSequenceNode *node,
1560                     EggSequenceNode *new)
1561 {
1562     g_assert (node != NULL);
1563     g_assert (new != NULL);
1564
1565     splay (node);
1566
1567     new = splay (find_min (new));
1568     g_assert (new->left == NULL);
1569
1570     if (node->left)
1571         node->left->parent = new;
1572
1573     new->left = node->left;
1574     new->parent = node;
1575
1576     node->left = new;
1577
1578     node_update_fields (new);
1579     node_update_fields (node);
1580 }
1581
1582 static void
1583 node_insert_after (EggSequenceNode *node,
1584                    EggSequenceNode *new)
1585 {
1586     g_assert (node != NULL);
1587     g_assert (new != NULL);
1588
1589     splay (node);
1590
1591     new = splay (find_max (new));
1592     g_assert (new->right == NULL);
1593     g_assert (node->parent == NULL);
1594
1595     if (node->right)
1596         node->right->parent = new;
1597
1598     new->right = node->right;
1599     new->parent = node;
1600
1601     node->right = new;
1602
1603     node_update_fields (new);
1604     node_update_fields (node);
1605 }
1606
1607 static gint
1608 node_get_length (EggSequenceNode    *node)
1609 {
1610     g_assert (node != NULL);
1611
1612     splay (node);
1613     return node->n_nodes;
1614 }
1615
1616 static void
1617 node_unlink (EggSequenceNode *node)
1618 {
1619     EggSequenceNode *right, *left;
1620
1621     splay (node);
1622
1623     left = node->left;
1624     right = node->right;
1625
1626     node->parent = node->left = node->right = NULL;
1627     node_update_fields (node);
1628
1629     if (right)
1630     {
1631         right->parent = NULL;
1632
1633         right = node_get_first (right);
1634         g_assert (right->left == NULL);
1635
1636         right->left = left;
1637         if (left)
1638         {
1639             left->parent = right;
1640             node_update_fields (right);
1641         }
1642     }
1643     else if (left)
1644     {
1645         left->parent = NULL;
1646     }
1647 }
1648
1649 static void
1650 node_insert_sorted (EggSequenceNode *node,
1651                     EggSequenceNode *new,
1652                     EggSequenceNode *end,
1653                     EggSequenceIterCompareFunc cmp_func,
1654                     gpointer cmp_data)
1655 {
1656     EggSequenceNode *closest;
1657
1658     closest = node_find_closest (node, new, end, cmp_func, cmp_data);
1659
1660     node_unlink (new);
1661
1662     node_insert_before (closest, new);
1663 }
1664
1665 static gint
1666 node_calc_height (EggSequenceNode *node)
1667 {
1668     gint left_height;
1669     gint right_height;
1670
1671     if (node)
1672     {
1673         left_height = 0;
1674         right_height = 0;
1675
1676         if (node->left)
1677             left_height = node_calc_height (node->left);
1678
1679         if (node->right)
1680             right_height = node_calc_height (node->right);
1681
1682         return MAX (left_height, right_height) + 1;
1683     }
1684
1685     return 0;
1686 }
1687
1688 /* Self test functions */
1689
1690 static void
1691 check_node (EggSequenceNode *node)
1692 {
1693     if (node)
1694     {
1695         g_assert (node->parent != node);
1696         g_assert (node->n_nodes ==
1697                   1 + get_n_nodes (node->left) + get_n_nodes (node->right));
1698         check_node (node->left);
1699         check_node (node->right);
1700     }
1701 }
1702
1703 void
1704 egg_sequence_self_test (EggSequence *seq)
1705 {
1706     EggSequenceNode *node = splay (seq->end_node);
1707
1708     check_node (node);
1709 }