rhythmdb/gsequence.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 2002  Soeren Sandmann (sandmann@daimi.au.dk)
   3  *
   4  * arch-tag: Implementation of GSequence - a fast ordered-sequence
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the
  17  * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
  18  * Boston, MA 02110-1301  USA.
  19  */
  20
  21 #include <glib.h>
  22
  23 #include "gsequence.h"
  24
  25 #ifndef g_slice_new0
  26 #define g_slice_new0(a) g_new0(a, 1)
  27 #define g_slice_free(a, b) g_free(b)
  28 #endif
  29
  30 typedef struct _GSequenceNode GSequenceNode;
  31
  32 struct _GSequence {
  33     GSequenceNode *node;        /* does not necessarily point to the root.
  34                                  * You can splay it if you want it to
  35                                  */
  36     GDestroyNotify data_destroy_notify;
  37 };
  38
  39 struct _GSequenceNode {
  40     guint is_end  : 1;
  41     gint  n_nodes : 31;         /* number of nodes below this node,
  42                                  * including this node
  43                                  */
  44     GSequenceNode *parent;
  45     GSequenceNode *left;
  46     GSequenceNode *right;
  47
  48     GSequence *sequence;
  49
  50     gpointer data;
  51 };
  52
  53 static GSequenceNode *g_sequence_node_new          (gpointer          data);
  54 static GSequenceNode *g_sequence_node_find_first   (GSequenceNode    *node);
  55 static GSequenceNode *g_sequence_node_find_last    (GSequenceNode    *node);
  56 static GSequenceNode *g_sequence_node_find_by_pos  (GSequenceNode    *node,
  57                                                     gint pos);
  58 static GSequenceNode *g_sequence_node_prev         (GSequenceNode    *node);
  59 static GSequenceNode *g_sequence_node_next         (GSequenceNode    *node);
  60 static gint           g_sequence_node_get_pos (GSequenceNode    *node);
  61 static GSequence     *g_sequence_node_get_sequence (GSequenceNode    *node);
  62 static GSequenceNode *g_sequence_node_find_closest (GSequenceNode    *node,
  63                                                     GSequenceNode    *other,
  64                                                     GCompareDataFunc  cmp,
  65                                                     gpointer          data);
  66 static gint           g_sequence_node_get_length   (GSequenceNode    *node);
  67 static void           g_sequence_node_free         (GSequenceNode    *node,
  68                                                     GDestroyNotify    destroy);
  69 #if 0
  70 static gboolean       g_sequence_node_is_singleton (GSequenceNode    *node);
  71 #endif
  72 static void           g_sequence_node_split        (GSequenceNode    *node,
  73                                                     GSequenceNode   **left,
  74                                                     GSequenceNode   **right);
  75 static void           g_sequence_node_insert_before (GSequenceNode *node,
  76                                                      GSequenceNode *new);
  77 static void           g_sequence_node_remove        (GSequenceNode *node);
  78 static void           g_sequence_node_insert_sorted (GSequenceNode *node,
  79                                                      GSequenceNode *new,
  80                                                      GCompareDataFunc cmp_func,
  81                                                      gpointer cmp_data);
  82
  83 /* GSequence */
  84 GSequence *
  85 g_sequence_new                (GDestroyNotify           data_destroy)
  86 {
  87     GSequence *seq = g_new (GSequence, 1);
  88     seq->data_destroy_notify = data_destroy;
  89
  90     seq->node = g_sequence_node_new (NULL);
  91     seq->node->is_end = TRUE;
  92     seq->node->sequence = seq;
  93
  94     return seq;
  95 }
  96
  97 void
  98 g_sequence_free               (GSequence               *seq)
  99 {
 100     g_return_if_fail (seq != NULL);
 101
 102     g_sequence_node_free (seq->node, seq->data_destroy_notify);
 103
 104     g_free (seq);
 105 }
 106
 107 #if 0
 108 static void
 109 flatten_nodes (GSequenceNode *node, GList **list)
 110 {
 111     g_print ("flatten %p\n", node);
 112     if (!node)
 113         return;
 114     else if (g_sequence_node_is_singleton (node))
 115         *list = g_list_prepend (*list, node);
 116     else
 117     {
 118         GSequenceNode *left;
 119         GSequenceNode *right;
 120
 121         g_sequence_node_split (node, &left, &right);
 122
 123         flatten_nodes (left, list);
 124         flatten_nodes (right, list);
 125     }
 126 }
 127 #endif
 128
 129 typedef struct SortInfo SortInfo;
 130 struct SortInfo {
 131     GCompareDataFunc cmp;
 132     gpointer data;
 133 };
 134
 135 static gint
 136 node_compare (gconstpointer n1, gconstpointer n2, gpointer data)
 137 {
 138     SortInfo *info = data;
 139     const GSequenceNode *node1 = n1;
 140     const GSequenceNode *node2 = n2;
 141
 142     if (node1->is_end)
 143         return 1;
 144     else if (node2->is_end)
 145         return -1;
 146     else
 147         return (* info->cmp) (node1->data, node2->data, info->data);
 148 }
 149
 150 void
 151 g_sequence_append             (GSequence               *seq,
 152                                gpointer                 data)
 153 {
 154     GSequenceNode *node, *last;
 155
 156     g_return_if_fail (seq != NULL);
 157
 158     node = g_sequence_node_new (data);
 159     node->sequence = seq;
 160     last = g_sequence_node_find_last (seq->node);
 161     g_sequence_node_insert_before (last, node);
 162 }
 163
 164 void
 165 g_sequence_prepend            (GSequence               *seq,
 166                                gpointer                 data)
 167 {
 168     GSequenceNode *node, *second;
 169
 170     g_return_if_fail (seq != NULL);
 171
 172     node = g_sequence_node_new (data);
 173     node->sequence = seq;
 174     second = g_sequence_node_next (g_sequence_node_find_first (seq->node));
 175
 176     g_sequence_node_insert_before (second, node);
 177 }
 178
 179 void
 180 g_sequence_insert             (GSequencePtr             ptr,
 181                                gpointer                 data)
 182 {
 183     GSequenceNode *node;
 184
 185     g_return_if_fail (ptr != NULL);
 186
 187     node = g_sequence_node_new (data);
 188     node->sequence = ptr->sequence;
 189
 190     g_sequence_node_insert_before (ptr, node);
 191 }
 192
 193 static void
 194 g_sequence_unlink (GSequence *seq,
 195                    GSequenceNode *node)
 196 {
 197     g_assert (!node->is_end);
 198
 199     seq->node = g_sequence_node_next (node);
 200
 201     g_assert (seq->node);
 202     g_assert (seq->node != node);
 203
 204     g_sequence_node_remove (node);
 205 }
 206
 207 void
 208 g_sequence_remove             (GSequencePtr             ptr)
 209 {
 210     GSequence *seq;
 211
 212     g_return_if_fail (ptr != NULL);
 213     g_return_if_fail (!ptr->is_end);
 214
 215     seq = g_sequence_node_get_sequence (ptr);
 216     g_sequence_unlink (seq, ptr);
 217     g_sequence_node_free (ptr, seq->data_destroy_notify);
 218 }
 219
 220 void
 221 g_sequence_sort               (GSequence               *seq,
 222                                GCompareDataFunc         cmp_func,
 223                                gpointer                 cmp_data)
 224 {
 225     GSequence *tmp;
 226     GSequenceNode *begin, *end;
 227
 228     g_return_if_fail (seq != NULL);
 229     g_return_if_fail (cmp_func != NULL);
 230
 231     begin = g_sequence_get_begin_ptr (seq);
 232     end   = g_sequence_get_end_ptr (seq);
 233
 234     g_sequence_remove_range (begin, end, &tmp);
 235
 236     while (g_sequence_get_length (tmp) > 0)
 237     {
 238         GSequenceNode *node = g_sequence_get_begin_ptr (tmp);
 239         g_sequence_unlink (tmp, node);
 240
 241         g_sequence_node_insert_sorted (seq->node, node, cmp_func, cmp_data);
 242     }
 243
 244     g_sequence_free (tmp);
 245 }
 246
 247 gpointer
 248 g_sequence_ptr_get_data           (GSequencePtr             ptr)
 249 {
 250     g_return_val_if_fail (ptr != NULL, NULL);
 251     g_return_val_if_fail (!ptr->is_end, NULL);
 252
 253     return ptr->data;
 254 }
 255
 256 GSequencePtr
 257 g_sequence_insert_sorted      (GSequence               *seq,
 258                                gpointer                 data,
 259                                GCompareDataFunc         cmp_func,
 260                                gpointer                 cmp_data)
 261 {
 262     GSequenceNode *new_node = g_sequence_node_new (data);
 263     new_node->sequence = seq;
 264     g_sequence_node_insert_sorted (seq->node, new_node, cmp_func, cmp_data);
 265     return new_node;
 266 }
 267
 268 void
 269 g_sequence_insert_sequence    (GSequencePtr             ptr,
 270                                GSequence               *other_seq)
 271 {
 272     GSequenceNode *last;
 273
 274     g_return_if_fail (other_seq != NULL);
 275     g_return_if_fail (ptr != NULL);
 276
 277     last = g_sequence_node_find_last (other_seq->node);
 278     g_sequence_node_insert_before (ptr, last);
 279     g_sequence_node_remove (last);
 280     g_sequence_node_free (last, NULL);
 281     other_seq->node = NULL;
 282     g_sequence_free (other_seq);
 283 }
 284
 285 void
 286 g_sequence_concatenate        (GSequence               *seq1,
 287                                GSequence               *seq2)
 288 {
 289     GSequenceNode *last;
 290
 291     g_return_if_fail (seq1 != NULL);
 292     g_return_if_fail (seq2 != NULL);
 293
 294     last = g_sequence_node_find_last (seq1->node);
 295     g_sequence_insert_sequence (last, seq2);
 296 }
 297
 298 /*
 299  * The new sequence inherits the destroy notify from the sequence that
 300  * beign and end comes from
 301  */
 302 void
 303 g_sequence_remove_range       (GSequencePtr             begin,
 304                                GSequencePtr             end,
 305                                GSequence              **removed)
 306 {
 307     GSequence *seq;
 308     GSequenceNode *s1, *s2, *s3;
 309
 310     seq = g_sequence_node_get_sequence (begin);
 311
 312     g_assert (end != NULL);
 313
 314     g_return_if_fail (seq == g_sequence_node_get_sequence (end));
 315
 316     g_sequence_node_split (begin, &s1, &s2);
 317     g_sequence_node_split (end, NULL, &s3);
 318
 319     if (s1)
 320         g_sequence_node_insert_before (s3, s1);
 321
 322     seq->node = s3;
 323
 324     if (removed)
 325     {
 326         *removed = g_sequence_new (seq->data_destroy_notify);
 327         g_sequence_node_insert_before ((*removed)->node, s2);
 328     }
 329     else
 330     {
 331         g_sequence_node_free (s2, seq->data_destroy_notify);
 332     }
 333 }
 334
 335 gint
 336 g_sequence_get_length         (GSequence               *seq)
 337 {
 338     return g_sequence_node_get_length (seq->node) - 1;
 339 }
 340
 341 GSequencePtr
 342 g_sequence_get_end_ptr        (GSequence               *seq)
 343 {
 344     g_return_val_if_fail (seq != NULL, NULL);
 345     return g_sequence_node_find_last (seq->node);
 346 }
 347
 348 GSequencePtr
 349 g_sequence_get_begin_ptr      (GSequence               *seq)
 350 {
 351     g_return_val_if_fail (seq != NULL, NULL);
 352     return g_sequence_node_find_first (seq->node);
 353 }
 354
 355 /*
 356  * if pos > number of items or -1, will return end pointer
 357  */
 358 GSequencePtr
 359 g_sequence_get_ptr_at_pos     (GSequence               *seq,
 360                                gint                     pos)
 361 {
 362     gint len;
 363
 364     g_return_val_if_fail (seq != NULL, NULL);
 365
 366     len = g_sequence_get_length (seq);
 367
 368     if (pos > len || pos == -1)
 369         pos = len;
 370
 371     return g_sequence_node_find_by_pos (seq->node, pos);
 372 }
 373
 374 /* GSequencePtr */
 375 gboolean
 376 g_sequence_ptr_is_end         (GSequencePtr             ptr)
 377 {
 378     g_return_val_if_fail (ptr != NULL, FALSE);
 379     return ptr->is_end;
 380 }
 381
 382 gboolean
 383 g_sequence_ptr_is_begin       (GSequencePtr             ptr)
 384 {
 385     return (g_sequence_node_prev (ptr) == ptr);
 386 }
 387
 388 gint
 389 g_sequence_ptr_get_position   (GSequencePtr             ptr)
 390 {
 391     g_return_val_if_fail (ptr != NULL, -1);
 392
 393     return g_sequence_node_get_pos (ptr);
 394 }
 395
 396 GSequencePtr
 397 g_sequence_ptr_next           (GSequencePtr             ptr)
 398 {
 399     g_return_val_if_fail (ptr != NULL, NULL);
 400
 401     return g_sequence_node_next (ptr);
 402 }
 403
 404 GSequencePtr
 405 g_sequence_ptr_prev           (GSequencePtr             ptr)
 406 {
 407     g_return_val_if_fail (ptr != NULL, NULL);
 408
 409     return g_sequence_node_prev (ptr);
 410 }
 411
 412 GSequencePtr
 413 g_sequence_ptr_move           (GSequencePtr             ptr,
 414                                guint                    delta)
 415 {
 416     gint new_pos;
 417
 418     g_return_val_if_fail (ptr != NULL, NULL);
 419
 420     new_pos = g_sequence_node_get_pos (ptr) + delta;
 421
 422     return g_sequence_node_find_by_pos (ptr, new_pos);
 423 }
 424
 425 void
 426 g_sequence_ptr_sort_changed  (GSequencePtr           ptr,
 427                               GCompareDataFunc       cmp_func,
 428                               gpointer               cmp_data)
 429 {
 430     GSequence *seq;
 431
 432     g_return_if_fail (!ptr->is_end);
 433
 434     seq = g_sequence_node_get_sequence (ptr);
 435     g_sequence_unlink (seq, ptr);
 436     g_sequence_node_insert_sorted (seq->node, ptr, cmp_func, cmp_data);
 437 }
 438
 439 /* search
 440  *
 441  * The only restriction on the search function is that it
 442  * must not delete any nodes. It is permitted to insert new nodes,
 443  * but the caller should "know what he is doing"
 444  */
 445 void
 446 g_sequence_search             (GSequence               *seq,
 447                                GSequenceSearchFunc      f,
 448                                gpointer                 data)
 449 {
 450     GQueue *intervals = g_queue_new ();
 451
 452     g_queue_push_tail (intervals, g_sequence_node_find_first (seq->node));
 453     g_queue_push_tail (intervals, g_sequence_node_find_last (seq->node));
 454
 455     while (!g_queue_is_empty (intervals))
 456     {
 457         GSequenceNode *begin = g_queue_pop_head (intervals);
 458         GSequenceNode *end   = g_queue_pop_head (intervals);
 459
 460         if (f (begin, end, data))
 461         {
 462             gint begin_pos = g_sequence_node_get_pos (begin);
 463             gint end_pos   = g_sequence_node_get_pos (end);
 464
 465             if (end_pos - begin_pos > 1)
 466             {
 467                 GSequenceNode *mid;
 468                 gint mid_pos;
 469
 470                 mid_pos = begin_pos + (end_pos - begin_pos) / 2;
 471                 mid = g_sequence_node_find_by_pos (begin, mid_pos);
 472
 473                 g_queue_push_tail (intervals, begin);
 474                 g_queue_push_tail (intervals, mid);
 475
 476                 g_queue_push_tail (intervals, mid);
 477                 g_queue_push_tail (intervals, end);
 478             }
 479         }
 480     }
 481
 482     g_queue_free (intervals);
 483 }
 484
 485 #if 0
 486 /* aggregates */
 487 void
 488 g_sequence_add_aggregate      (GSequence               *seq,
 489                                const gchar             *aggregate,
 490                                GSequenceAggregateFunc   f,
 491                                gpointer                 data,
 492                                GDestroyNotify           destroy)
 493 {
 494     /* FIXME */
 495 }
 496
 497 void
 498 g_sequence_remove_aggregate   (GSequence               *seq,
 499                                const gchar              aggregate)
 500 {
 501     /* FIXME */
 502
 503 }
 504
 505 void
 506 g_sequence_set_aggregate_data (GSequencePtr             ptr,
 507                                const gchar             *aggregate,
 508                                gpointer                 data)
 509 {
 510     /* FIXME */
 511
 512 }
 513
 514 gpointer
 515 g_sequence_get_aggregate_data (GSequencePtr             begin,
 516                                GSequencePtr             end,
 517                                const gchar             *aggregate)
 518 {
 519     g_assert_not_reached();
 520     return NULL;
 521 }
 522 #endif
 523
 524 /* Nodes
 525  */
 526 static void
 527 g_sequence_node_update_fields (GSequenceNode *node)
 528 {
 529     g_assert (node != NULL);
 530
 531     node->n_nodes = 1;
 532
 533     if (node->left)
 534         node->n_nodes += node->left->n_nodes;
 535
 536     if (node->right)
 537         node->n_nodes += node->right->n_nodes;
 538
 539 #if 0
 540     if (node->left || node->right)
 541         g_assert (node->n_nodes > 1);
 542 #endif
 543 }
 544
 545 #define NODE_LEFT_CHILD(n)  (((n)->parent) && ((n)->parent->left) == (n))
 546 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
 547
 548 static void
 549 g_sequence_node_rotate (GSequenceNode *node)
 550 {
 551     GSequenceNode *tmp, *old;
 552
 553     g_assert (node->parent);
 554     g_assert (node->parent != node);
 555
 556     if (NODE_LEFT_CHILD (node))
 557     {
 558         /* rotate right */
 559         tmp = node->right;
 560
 561         node->right = node->parent;
 562         node->parent = node->parent->parent;
 563         if (node->parent)
 564         {
 565             if (node->parent->left == node->right)
 566                 node->parent->left = node;
 567             else
 568                 node->parent->right = node;
 569         }
 570
 571         g_assert (node->right);
 572
 573         node->right->parent = node;
 574         node->right->left = tmp;
 575
 576         if (node->right->left)
 577             node->right->left->parent = node->right;
 578
 579         old = node->right;
 580     }
 581     else
 582     {
 583         /* rotate left */
 584         tmp = node->left;
 585
 586         node->left = node->parent;
 587         node->parent = node->parent->parent;
 588         if (node->parent)
 589         {
 590             if (node->parent->right == node->left)
 591                 node->parent->right = node;
 592             else
 593                 node->parent->left = node;
 594         }
 595
 596         g_assert (node->left);
 597
 598         node->left->parent = node;
 599         node->left->right = tmp;
 600
 601         if (node->left->right)
 602             node->left->right->parent = node->left;
 603
 604         old = node->left;
 605     }
 606
 607     g_sequence_node_update_fields (old);
 608     g_sequence_node_update_fields (node);
 609 }
 610
 611 static GSequenceNode *
 612 splay (GSequenceNode *node)
 613 {
 614     while (node->parent)
 615     {
 616         if (!node->parent->parent)
 617         {
 618             /* zig */
 619             g_sequence_node_rotate (node);
 620         }
 621         else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) ||
 622                  (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent)))
 623         {
 624             /* zig-zig */
 625             g_sequence_node_rotate (node->parent);
 626             g_sequence_node_rotate (node);
 627         }
 628         else
 629         {
 630             /* zig-zag */
 631             g_sequence_node_rotate (node);
 632             g_sequence_node_rotate (node);
 633         }
 634     }
 635
 636     return node;
 637 }
 638
 639 static GSequenceNode *
 640 g_sequence_node_new (gpointer          data)
 641 {
 642     GSequenceNode *node = g_slice_new0 (GSequenceNode);
 643
 644     node->parent = NULL;
 645     node->left = NULL;
 646     node->right = NULL;
 647
 648     node->data = data;
 649     node->is_end = FALSE;
 650     node->n_nodes = 1;
 651
 652     return node;
 653 }
 654
 655 static GSequenceNode *
 656 find_min (GSequenceNode *node)
 657 {
 658     splay (node);
 659
 660     while (node->left)
 661         node = node->left;
 662
 663     return node;
 664 }
 665
 666 static GSequenceNode *
 667 find_max (GSequenceNode *node)
 668 {
 669     splay (node);
 670
 671     while (node->right)
 672         node = node->right;
 673
 674     return node;
 675 }
 676
 677 static GSequenceNode *
 678 g_sequence_node_find_first   (GSequenceNode    *node)
 679 {
 680     return splay (find_min (node));
 681 }
 682
 683 static GSequenceNode *
 684 g_sequence_node_find_last    (GSequenceNode    *node)
 685 {
 686     return splay (find_max (node));
 687 }
 688
 689 static gint
 690 get_n_nodes (GSequenceNode *node)
 691 {
 692     if (node)
 693         return node->n_nodes;
 694     else
 695         return 0;
 696 }
 697
 698 static GSequenceNode *
 699 g_sequence_node_find_by_pos  (GSequenceNode    *node,
 700                               gint              pos)
 701 {
 702     gint i;
 703
 704     g_assert (node != NULL);
 705
 706     splay (node);
 707
 708     while ((i = get_n_nodes (node->left)) != pos)
 709     {
 710         if (i < pos)
 711         {
 712             node = node->right;
 713             pos -= (i + 1);
 714         }
 715         else
 716         {
 717             node = node->left;
 718             g_assert (node->parent != NULL);
 719         }
 720     }
 721
 722     return splay (node);
 723 }
 724
 725 static GSequenceNode *
 726 g_sequence_node_prev         (GSequenceNode    *node)
 727 {
 728     splay (node);
 729
 730     if (node->left)
 731     {
 732         node = node->left;
 733         while (node->right)
 734             node = node->right;
 735     }
 736
 737     return splay (node);
 738 }
 739
 740 static GSequenceNode *
 741 g_sequence_node_next         (GSequenceNode    *node)
 742 {
 743     splay (node);
 744
 745     if (node->right)
 746     {
 747         node = node->right;
 748         while (node->left)
 749             node = node->left;
 750     }
 751
 752     return splay (node);
 753 }
 754
 755 static gint
 756 g_sequence_node_get_pos (GSequenceNode    *node)
 757 {
 758     splay (node);
 759
 760     return get_n_nodes (node->left);
 761 }
 762
 763 static GSequence *
 764 g_sequence_node_get_sequence (GSequenceNode    *node)
 765 {
 766     splay (node);
 767
 768     return node->sequence;
 769 }
 770
 771 static GSequenceNode *
 772 g_sequence_node_find_closest (GSequenceNode    *node,
 773                               GSequenceNode    *other,
 774                               GCompareDataFunc  cmp,
 775                               gpointer          data)
 776 {
 777     GSequenceNode *best;
 778     gint c;
 779
 780     splay (node);
 781
 782     do
 783     {
 784         best = node;
 785
 786         if ((c = cmp (node, other, data)) != 0)
 787         {
 788             if (c < 0)
 789                 node = node->right;
 790             else
 791                 node = node->left;
 792         }
 793     }
 794     while (c != 0 && node != NULL);
 795
 796     return best;
 797 }
 798
 799 static void
 800 g_sequence_node_free         (GSequenceNode    *node,
 801                               GDestroyNotify    destroy)
 802 {
 803     /* FIXME:
 804      *
 805      * This is to avoid excessively deep recursions. A splay tree is not necessarily
 806      * balanced at all.
 807      *
 808      * I _think_ this is still linear in the number of nodes, but I'd like to
 809      * do something more efficient.
 810      */
 811
 812     while (node)
 813     {
 814         GSequenceNode *next;
 815
 816         node = splay (find_min (node));
 817         next = node->right;
 818         if (next)
 819             next->parent = NULL;
 820
 821         if (destroy && !node->is_end)
 822             destroy (node->data);
 823         g_slice_free (GSequenceNode, node);
 824
 825         node = next;
 826     }
 827 }
 828
 829 #if 0
 830 static gboolean
 831 g_sequence_node_is_singleton (GSequenceNode    *node)
 832 {
 833     splay (node);
 834
 835     if (node->left || node->right)
 836         return FALSE;
 837
 838     return TRUE;
 839 }
 840 #endif
 841
 842 static void
 843 g_sequence_node_split        (GSequenceNode    *node,
 844                               GSequenceNode   **left,
 845                               GSequenceNode   **right)
 846 {
 847     GSequenceNode *left_tree;
 848
 849     splay (node);
 850
 851     left_tree = node->left;
 852     if (left_tree)
 853     {
 854         left_tree->parent = NULL;
 855         g_sequence_node_update_fields (left_tree);
 856     }
 857
 858     node->left = NULL;
 859     g_sequence_node_update_fields (node);
 860
 861     if (left)
 862         *left = left_tree;
 863
 864     if (right)
 865         *right = node;
 866 }
 867
 868 static void
 869 g_sequence_node_insert_before (GSequenceNode *node,
 870                                GSequenceNode *new)
 871 {
 872     g_assert (node != NULL);
 873     g_assert (new != NULL);
 874
 875     splay (node);
 876
 877     new = splay (find_min (new));
 878     g_assert (new->left == NULL);
 879
 880     if (node->left)
 881         node->left->parent = new;
 882
 883     new->left = node->left;
 884     new->parent = node;
 885
 886     node->left = new;
 887
 888     g_sequence_node_update_fields (new);
 889     g_sequence_node_update_fields (node);
 890 }
 891
 892 static gint
 893 g_sequence_node_get_length (GSequenceNode    *node)
 894 {
 895     g_assert (node != NULL);
 896
 897     splay (node);
 898     return node->n_nodes;
 899 }
 900
 901 static void
 902 g_sequence_node_remove        (GSequenceNode *node)
 903 {
 904     GSequenceNode *right, *left;
 905
 906     splay (node);
 907
 908     left = node->left;
 909     right = node->right;
 910
 911     node->left = node->right = NULL;
 912
 913     if (right)
 914     {
 915         right->parent = NULL;
 916
 917         right = g_sequence_node_find_first (right);
 918         g_assert (right->left == NULL);
 919
 920         right->left = left;
 921         if (left)
 922         {
 923             left->parent = right;
 924             g_sequence_node_update_fields (right);
 925         }
 926     }
 927     else if (left)
 928         left->parent = NULL;
 929 }
 930
 931 #if 0
 932 /* debug func */
 933 static gint
 934 g_sequence_node_calc_height (GSequenceNode *node)
 935 {
 936     /* breadth first traversal */
 937     gint height = 0;
 938     GQueue *nodes = g_queue_new ();
 939
 940     g_queue_push_tail (nodes, node);
 941
 942     while (!g_queue_is_empty (nodes))
 943     {
 944         GQueue *tmp = g_queue_new ();
 945
 946         height++;
 947         while (!g_queue_is_empty (nodes))
 948         {
 949             GSequenceNode *node = g_queue_pop_head (nodes);
 950             if (node->left)
 951                 g_queue_push_tail (tmp, node->left);
 952             if (node->right)
 953                 g_queue_push_tail (tmp, node->right);
 954         }
 955
 956         g_queue_free (nodes);
 957
 958         nodes = tmp;
 959     }
 960     g_queue_free (nodes);
 961
 962     return height;
 963 }
 964 #endif
 965
 966 static void
 967 g_sequence_node_insert_sorted (GSequenceNode *node,
 968                                GSequenceNode *new,
 969                                GCompareDataFunc cmp_func,
 970                                gpointer cmp_data)
 971 {
 972     SortInfo info;
 973     GSequenceNode *closest;
 974     info.cmp = cmp_func;
 975     info.data = cmp_data;
 976
 977     closest =
 978         g_sequence_node_find_closest (node, new, node_compare, &info);
 979
 980     if (node_compare (new, closest, &info) > 0)
 981         closest = g_sequence_node_next (closest);
 982
 983     /* this can never fail since we have a bigger-than-everything
 984      * end-node
 985      */
 986     g_assert (node_compare (new, closest, &info) <= 0);
 987     g_sequence_node_insert_before (closest, new);
 988 }
 989
 990 static gint
 991 g_sequence_node_calc_height (GSequenceNode *node)
 992 {
 993   gint left_height;
 994   gint right_height;
 995
 996   if (node)
 997   {
 998       left_height = 0;
 999       right_height = 0;
1000
1001       if (node->left)
1002         left_height = g_sequence_node_calc_height (node->left);
1003
1004       if (node->right)
1005         right_height = g_sequence_node_calc_height (node->right);
1006
1007       return MAX (left_height, right_height) + 1;
1008   }
1009
1010   return 0;
1011 }
1012
1013 gint
1014 g_sequence_calc_tree_height   (GSequence               *seq)
1015 {
1016     GSequenceNode *node = seq->node;
1017     gint r, l;
1018     while (node->parent)
1019         node = node->parent;
1020
1021     if (node)
1022     {
1023         r = g_sequence_node_calc_height (node->right);
1024         l = g_sequence_node_calc_height (node->left);
1025
1026         return MAX (r, l) + 1;
1027     }
1028     else
1029         return 0;
1030 }