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