Pileus Git - ~andy/gtk/blob - gtk/gtksequence.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 2002  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 "gtksequence.h"
  23
  24 typedef struct _GtkSequenceNode GtkSequenceNode;
  25
  26 struct _GtkSequence {
  27   GtkSequenceNode *node;        /* does not necessarily point to the root.
  28                                  * You can splay it if you want it to
  29                                  */
  30   GDestroyNotify data_destroy_notify;
  31 };
  32
  33 struct _GtkSequenceNode {
  34   guint is_end  : 1;
  35   gint  n_nodes : 31;           /* number of nodes below this node,
  36                                  * including this node
  37                                  */
  38   GtkSequenceNode *parent;
  39   GtkSequenceNode *left;
  40   GtkSequenceNode *right;
  41
  42   GtkSequence *sequence;
  43
  44   gpointer data;
  45 };
  46
  47 static GtkSequenceNode *_gtk_sequence_node_new          (gpointer          data);
  48 static GtkSequenceNode *_gtk_sequence_node_find_first   (GtkSequenceNode    *node);
  49 static GtkSequenceNode *_gtk_sequence_node_find_last    (GtkSequenceNode    *node);
  50 static GtkSequenceNode *_gtk_sequence_node_find_by_pos  (GtkSequenceNode    *node,
  51                                                          gint pos);
  52 static GtkSequenceNode *_gtk_sequence_node_prev         (GtkSequenceNode    *node);
  53 static GtkSequenceNode *_gtk_sequence_node_next         (GtkSequenceNode    *node);
  54 static gint           _gtk_sequence_node_get_pos (GtkSequenceNode    *node);
  55 static GtkSequence     *_gtk_sequence_node_get_sequence (GtkSequenceNode    *node);
  56 static GtkSequenceNode *_gtk_sequence_node_find_closest (GtkSequenceNode    *node,
  57                                                          GtkSequenceNode    *other,
  58                                                          GCompareDataFunc  cmp,
  59                                                          gpointer          data);
  60 static gint           _gtk_sequence_node_get_length   (GtkSequenceNode    *node);
  61 static void           _gtk_sequence_node_free         (GtkSequenceNode    *node,
  62                                                        GDestroyNotify    destroy);
  63 #if 0
  64 static gboolean       _gtk_sequence_node_is_singleton (GtkSequenceNode    *node);
  65 #endif
  66 static void           _gtk_sequence_node_split        (GtkSequenceNode    *node,
  67                                                        GtkSequenceNode   **left,
  68                                                        GtkSequenceNode   **right);
  69 static void           _gtk_sequence_node_insert_before (GtkSequenceNode *node,
  70                                                         GtkSequenceNode *new);
  71 static void           _gtk_sequence_node_remove        (GtkSequenceNode *node);
  72 static void           _gtk_sequence_node_insert_sorted (GtkSequenceNode *node,
  73                                                         GtkSequenceNode *new,
  74                                                         GCompareDataFunc cmp_func,
  75                                                         gpointer cmp_data);
  76
  77 /* GtkSequence */
  78 GtkSequence *
  79 _gtk_sequence_new                (GDestroyNotify           data_destroy)
  80 {
  81   GtkSequence *seq = g_new (GtkSequence, 1);
  82   seq->data_destroy_notify = data_destroy;
  83
  84   seq->node = _gtk_sequence_node_new (NULL);
  85   seq->node->is_end = TRUE;
  86   seq->node->sequence = seq;
  87
  88   return seq;
  89 }
  90
  91 void
  92 _gtk_sequence_foreach         (GtkSequence       *seq,
  93                                GFunc              func,
  94                                gpointer           data)
  95 {
  96   GtkSequencePtr ptr;
  97
  98   g_return_if_fail (seq != NULL);
  99   g_return_if_fail (func != NULL);
 100
 101   ptr = _gtk_sequence_get_begin_ptr (seq);
 102
 103   while (!_gtk_sequence_ptr_is_end (ptr))
 104     {
 105       GtkSequenceNode *node = ptr;
 106
 107       func (node->data, data);
 108
 109       ptr = _gtk_sequence_ptr_next (ptr);
 110     }
 111
 112 }
 113
 114 void
 115 _gtk_sequence_free               (GtkSequence               *seq)
 116 {
 117   g_return_if_fail (seq != NULL);
 118
 119   _gtk_sequence_node_free (seq->node, seq->data_destroy_notify);
 120
 121   g_free (seq);
 122 }
 123
 124 #if 0
 125 static void
 126 flatten_nodes (GtkSequenceNode *node, GList **list)
 127 {
 128   g_print ("flatten %p\n", node);
 129   if (!node)
 130     return;
 131   else if (_gtk_sequence_node_is_singleton (node))
 132     *list = g_list_prepend (*list, node);
 133   else
 134     {
 135       GtkSequenceNode *left;
 136       GtkSequenceNode *right;
 137
 138       _gtk_sequence_node_split (node, &left, &right);
 139
 140       flatten_nodes (left, list);
 141       flatten_nodes (right, list);
 142     }
 143 }
 144 #endif
 145
 146 typedef struct SortInfo SortInfo;
 147 struct SortInfo {
 148   GCompareDataFunc cmp;
 149   gpointer data;
 150 };
 151
 152 static gint
 153 node_compare (gconstpointer n1, gconstpointer n2, gpointer data)
 154 {
 155   const SortInfo *info = data;
 156   const GtkSequenceNode *node1 = n1;
 157   const GtkSequenceNode *node2 = n2;
 158   gint retval;
 159
 160   if (node1->is_end)
 161       return 1;
 162
 163   if (node2->is_end)
 164       return -1;
 165
 166   retval = (* info->cmp) (node1, node2, info->data);
 167
 168   /* If the nodes are different, but the user-supplied compare function
 169    * compares them equal, then force an arbitrary (but consistent) order
 170    * on them, so that our sorts will be stable
 171    */
 172   if (retval != 0 || n1 == n2)
 173     return retval;
 174
 175   if (n1 > n2)
 176     return 1;
 177   else
 178     return -1;
 179 }
 180
 181 void
 182 _gtk_sequence_append             (GtkSequence               *seq,
 183                                   gpointer                 data)
 184 {
 185   GtkSequenceNode *node, *last;
 186
 187   g_return_if_fail (seq != NULL);
 188
 189   node = _gtk_sequence_node_new (data);
 190   node->sequence = seq;
 191   last = _gtk_sequence_node_find_last (seq->node);
 192   _gtk_sequence_node_insert_before (last, node);
 193 }
 194 #if 0
 195
 196 void
 197 _gtk_sequence_prepend            (GtkSequence               *seq,
 198                                   gpointer                 data)
 199 {
 200   GtkSequenceNode *node, *second;
 201
 202   g_return_if_fail (seq != NULL);
 203
 204   node = _gtk_sequence_node_new (data);
 205   node->sequence = seq;
 206   second = _gtk_sequence_node_next (_gtk_sequence_node_find_first (seq->node));
 207
 208   _gtk_sequence_node_insert_before (second, node);
 209 }
 210 #endif
 211
 212 GtkSequencePtr
 213 _gtk_sequence_insert             (GtkSequencePtr             ptr,
 214                                   gpointer                 data)
 215 {
 216   GtkSequenceNode *node;
 217
 218   g_return_val_if_fail (ptr != NULL, NULL);
 219
 220   node = _gtk_sequence_node_new (data);
 221   node->sequence = ptr->sequence;
 222
 223   _gtk_sequence_node_insert_before (ptr, node);
 224
 225   return node;
 226 }
 227
 228 static void
 229 _gtk_sequence_unlink (GtkSequence *seq,
 230                       GtkSequenceNode *node)
 231 {
 232   g_assert (!node->is_end);
 233
 234   seq->node = _gtk_sequence_node_next (node);
 235
 236   g_assert (seq->node);
 237   g_assert (seq->node != node);
 238
 239   _gtk_sequence_node_remove (node);
 240 }
 241
 242 void
 243 _gtk_sequence_remove             (GtkSequencePtr             ptr)
 244 {
 245   GtkSequence *seq;
 246
 247   g_return_if_fail (ptr != NULL);
 248   g_return_if_fail (!ptr->is_end);
 249
 250   seq = _gtk_sequence_node_get_sequence (ptr);
 251   _gtk_sequence_unlink (seq, ptr);
 252   _gtk_sequence_node_free (ptr, seq->data_destroy_notify);
 253 }
 254
 255 void
 256 _gtk_sequence_sort               (GtkSequence               *seq,
 257                                   GCompareDataFunc         cmp_func,
 258                                   gpointer                 cmp_data)
 259 {
 260   GtkSequence *tmp;
 261   GtkSequenceNode *begin, *end;
 262
 263   g_return_if_fail (seq != NULL);
 264   g_return_if_fail (cmp_func != NULL);
 265
 266   begin = _gtk_sequence_get_begin_ptr (seq);
 267   end   = _gtk_sequence_get_end_ptr (seq);
 268
 269   _gtk_sequence_remove_range (begin, end, &tmp);
 270
 271   while (_gtk_sequence_get_length (tmp) > 0)
 272     {
 273       GtkSequenceNode *node = _gtk_sequence_get_begin_ptr (tmp);
 274       _gtk_sequence_unlink (tmp, node);
 275
 276       _gtk_sequence_node_insert_sorted (seq->node, node, cmp_func, cmp_data);
 277     }
 278
 279   _gtk_sequence_free (tmp);
 280 }
 281
 282 gpointer
 283 _gtk_sequence_ptr_get_data           (GtkSequencePtr             ptr)
 284 {
 285   g_return_val_if_fail (ptr != NULL, NULL);
 286   g_return_val_if_fail (!ptr->is_end, NULL);
 287
 288   return ptr->data;
 289 }
 290
 291 GtkSequencePtr
 292 _gtk_sequence_insert_sorted      (GtkSequence               *seq,
 293                                   gpointer                 data,
 294                                   GCompareDataFunc         cmp_func,
 295                                   gpointer                 cmp_data)
 296 {
 297   GtkSequenceNode *new_node = _gtk_sequence_node_new (data);
 298   new_node->sequence = seq;
 299   _gtk_sequence_node_insert_sorted (seq->node, new_node, cmp_func, cmp_data);
 300   return new_node;
 301 }
 302
 303 void
 304 _gtk_sequence_insert_sequence    (GtkSequencePtr             ptr,
 305                                   GtkSequence               *other_seq)
 306 {
 307   GtkSequenceNode *last;
 308
 309   g_return_if_fail (other_seq != NULL);
 310   g_return_if_fail (ptr != NULL);
 311
 312   last = _gtk_sequence_node_find_last (other_seq->node);
 313   _gtk_sequence_node_insert_before (ptr, last);
 314   _gtk_sequence_node_remove (last);
 315   _gtk_sequence_node_free (last, NULL);
 316   other_seq->node = NULL;
 317   _gtk_sequence_free (other_seq);
 318 }
 319
 320 void
 321 _gtk_sequence_concatenate        (GtkSequence               *seq1,
 322                                   GtkSequence               *seq2)
 323 {
 324   GtkSequenceNode *last;
 325
 326   g_return_if_fail (seq1 != NULL);
 327   g_return_if_fail (seq2 != NULL);
 328
 329   last = _gtk_sequence_node_find_last (seq1->node);
 330   _gtk_sequence_insert_sequence (last, seq2);
 331 }
 332
 333 /*
 334  * The new sequence inherits the destroy notify from the sequence that
 335  * beign and end comes from
 336  */
 337 void
 338 _gtk_sequence_remove_range       (GtkSequencePtr             begin,
 339                                   GtkSequencePtr             end,
 340                                   GtkSequence              **removed)
 341 {
 342   GtkSequence *seq;
 343   GtkSequenceNode *s1, *s2, *s3;
 344
 345   seq = _gtk_sequence_node_get_sequence (begin);
 346
 347   g_assert (end != NULL);
 348
 349   g_return_if_fail (seq == _gtk_sequence_node_get_sequence (end));
 350
 351   _gtk_sequence_node_split (begin, &s1, &s2);
 352   _gtk_sequence_node_split (end, NULL, &s3);
 353
 354   if (s1)
 355     _gtk_sequence_node_insert_before (s3, s1);
 356
 357   seq->node = s3;
 358
 359   if (removed)
 360     {
 361       *removed = _gtk_sequence_new (seq->data_destroy_notify);
 362       _gtk_sequence_node_insert_before ((*removed)->node, s2);
 363     }
 364   else
 365     {
 366       _gtk_sequence_node_free (s2, seq->data_destroy_notify);
 367     }
 368 }
 369
 370 gint
 371 _gtk_sequence_get_length         (GtkSequence               *seq)
 372 {
 373   return _gtk_sequence_node_get_length (seq->node) - 1;
 374 }
 375
 376 GtkSequencePtr
 377 _gtk_sequence_get_end_ptr        (GtkSequence               *seq)
 378 {
 379   g_return_val_if_fail (seq != NULL, NULL);
 380   return _gtk_sequence_node_find_last (seq->node);
 381 }
 382
 383 GtkSequencePtr
 384 _gtk_sequence_get_begin_ptr      (GtkSequence               *seq)
 385 {
 386   g_return_val_if_fail (seq != NULL, NULL);
 387   return _gtk_sequence_node_find_first (seq->node);
 388 }
 389
 390 /*
 391  * if pos > number of items or -1, will return end pointer
 392  */
 393 GtkSequencePtr
 394 _gtk_sequence_get_ptr_at_pos     (GtkSequence               *seq,
 395                                   gint                     pos)
 396 {
 397   gint len;
 398
 399   g_return_val_if_fail (seq != NULL, NULL);
 400
 401   len = _gtk_sequence_get_length (seq);
 402
 403   if (pos > len || pos == -1)
 404     pos = len;
 405
 406   return _gtk_sequence_node_find_by_pos (seq->node, pos);
 407 }
 408
 409
 410 /* GtkSequencePtr */
 411 gboolean
 412 _gtk_sequence_ptr_is_end         (GtkSequencePtr             ptr)
 413 {
 414   g_return_val_if_fail (ptr != NULL, FALSE);
 415   return ptr->is_end;
 416 }
 417
 418 gboolean
 419 _gtk_sequence_ptr_is_begin       (GtkSequencePtr             ptr)
 420 {
 421   return (_gtk_sequence_node_prev (ptr) == ptr);
 422 }
 423
 424 /* If you call this on an end pointer you'll get
 425  * the length of the sequence
 426  */
 427 gint
 428 _gtk_sequence_ptr_get_position   (GtkSequencePtr             ptr)
 429 {
 430   g_return_val_if_fail (ptr != NULL, -1);
 431
 432   return _gtk_sequence_node_get_pos (ptr);
 433 }
 434
 435 GtkSequencePtr
 436 _gtk_sequence_ptr_next           (GtkSequencePtr             ptr)
 437 {
 438   g_return_val_if_fail (ptr != NULL, NULL);
 439
 440   return _gtk_sequence_node_next (ptr);
 441 }
 442
 443 GtkSequencePtr
 444 _gtk_sequence_ptr_prev           (GtkSequencePtr             ptr)
 445 {
 446   g_return_val_if_fail (ptr != NULL, NULL);
 447
 448   return _gtk_sequence_node_prev (ptr);
 449 }
 450
 451 GtkSequencePtr
 452 _gtk_sequence_ptr_move           (GtkSequencePtr             ptr,
 453                                   guint                    delta)
 454 {
 455   gint new_pos;
 456
 457   g_return_val_if_fail (ptr != NULL, NULL);
 458
 459   new_pos = _gtk_sequence_node_get_pos (ptr) + delta;
 460
 461   return _gtk_sequence_node_find_by_pos (ptr, new_pos);
 462 }
 463
 464 void
 465 _gtk_sequence_sort_changed  (GtkSequencePtr          ptr,
 466                              GCompareDataFunc        cmp_func,
 467                              gpointer                cmp_data)
 468
 469 {
 470   GtkSequence *seq;
 471
 472   g_return_if_fail (ptr != NULL);
 473   g_return_if_fail (!ptr->is_end);
 474
 475   seq = _gtk_sequence_node_get_sequence (ptr);
 476   _gtk_sequence_unlink (seq, ptr);
 477   _gtk_sequence_node_insert_sorted (seq->node, ptr, cmp_func, cmp_data);
 478 }
 479
 480 /* search
 481  *
 482  * The only restriction on the search function is that it
 483  * must not delete any nodes. It is permitted to insert new nodes,
 484  * but the caller should "know what he is doing"
 485  */
 486 void
 487 _gtk_sequence_search             (GtkSequence               *seq,
 488                                   GtkSequenceSearchFunc      f,
 489                                   gpointer                 data)
 490 {
 491   GQueue *intervals = g_queue_new ();
 492
 493   g_queue_push_tail (intervals, _gtk_sequence_node_find_first (seq->node));
 494   g_queue_push_tail (intervals, _gtk_sequence_node_find_last (seq->node));
 495
 496   while (!g_queue_is_empty (intervals))
 497     {
 498       GtkSequenceNode *begin = g_queue_pop_head (intervals);
 499       GtkSequenceNode *end   = g_queue_pop_head (intervals);
 500
 501       if (f (begin, end, data))
 502         {
 503           gint begin_pos = _gtk_sequence_node_get_pos (begin);
 504           gint end_pos   = _gtk_sequence_node_get_pos (end);
 505
 506           if (end_pos - begin_pos > 1)
 507             {
 508               GtkSequenceNode *mid;
 509               gint mid_pos;
 510
 511               mid_pos = begin_pos + (end_pos - begin_pos) / 2;
 512               mid = _gtk_sequence_node_find_by_pos (begin, mid_pos);
 513
 514               g_queue_push_tail (intervals, begin);
 515               g_queue_push_tail (intervals, mid);
 516
 517               g_queue_push_tail (intervals, mid);
 518               g_queue_push_tail (intervals, end);
 519             }
 520         }
 521     }
 522
 523   g_queue_free (intervals);
 524 }
 525
 526 #if 0
 527 /* aggregates */
 528 void
 529 _gtk_sequence_add_aggregate      (GtkSequence               *seq,
 530                                   const gchar             *aggregate,
 531                                   GtkSequenceAggregateFunc   f,
 532                                   gpointer                 data,
 533                                   GDestroyNotify           destroy)
 534 {
 535   /* FIXME */
 536 }
 537
 538 void
 539 _gtk_sequence_remove_aggregate   (GtkSequence               *seq,
 540                                   const gchar              aggregate)
 541 {
 542   /* FIXME */
 543
 544 }
 545
 546 void
 547 _gtk_sequence_set_aggregate_data (GtkSequencePtr             ptr,
 548                                   const gchar             *aggregate,
 549                                   gpointer                 data)
 550 {
 551   /* FIXME */
 552
 553 }
 554
 555 gpointer
 556 _gtk_sequence_get_aggregate_data (GtkSequencePtr             begin,
 557                                   GtkSequencePtr             end,
 558                                   const gchar             *aggregate)
 559 {
 560   g_assert_not_reached();
 561   return NULL;
 562 }
 563 #endif
 564
 565
 566 /* Nodes
 567  */
 568 static void
 569 _gtk_sequence_node_update_fields (GtkSequenceNode *node)
 570 {
 571   g_assert (node != NULL);
 572
 573   node->n_nodes = 1;
 574
 575   if (node->left)
 576     node->n_nodes += node->left->n_nodes;
 577
 578   if (node->right)
 579     node->n_nodes += node->right->n_nodes;
 580
 581 #if 0
 582   if (node->left || node->right)
 583     g_assert (node->n_nodes > 1);
 584 #endif
 585 }
 586
 587 #define NODE_LEFT_CHILD(n)  (((n)->parent) && ((n)->parent->left) == (n))
 588 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
 589
 590 static void
 591 _gtk_sequence_node_rotate (GtkSequenceNode *node)
 592 {
 593   GtkSequenceNode *tmp, *old;
 594
 595   g_assert (node->parent);
 596   g_assert (node->parent != node);
 597
 598   if (NODE_LEFT_CHILD (node))
 599     {
 600       /* rotate right */
 601       tmp = node->right;
 602
 603       node->right = node->parent;
 604       node->parent = node->parent->parent;
 605       if (node->parent)
 606         {
 607           if (node->parent->left == node->right)
 608             node->parent->left = node;
 609           else
 610             node->parent->right = node;
 611         }
 612
 613       g_assert (node->right);
 614
 615       node->right->parent = node;
 616       node->right->left = tmp;
 617
 618       if (node->right->left)
 619         node->right->left->parent = node->right;
 620
 621       old = node->right;
 622     }
 623   else
 624     {
 625       /* rotate left */
 626       tmp = node->left;
 627
 628       node->left = node->parent;
 629       node->parent = node->parent->parent;
 630       if (node->parent)
 631         {
 632           if (node->parent->right == node->left)
 633             node->parent->right = node;
 634           else
 635             node->parent->left = node;
 636         }
 637
 638       g_assert (node->left);
 639
 640       node->left->parent = node;
 641       node->left->right = tmp;
 642
 643       if (node->left->right)
 644         node->left->right->parent = node->left;
 645
 646       old = node->left;
 647     }
 648
 649   _gtk_sequence_node_update_fields (old);
 650   _gtk_sequence_node_update_fields (node);
 651 }
 652
 653 static GtkSequenceNode *
 654 splay (GtkSequenceNode *node)
 655 {
 656   while (node->parent)
 657     {
 658       if (!node->parent->parent)
 659         {
 660           /* zig */
 661           _gtk_sequence_node_rotate (node);
 662         }
 663       else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) ||
 664                (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent)))
 665         {
 666           /* zig-zig */
 667           _gtk_sequence_node_rotate (node->parent);
 668           _gtk_sequence_node_rotate (node);
 669         }
 670       else
 671         {
 672           /* zig-zag */
 673           _gtk_sequence_node_rotate (node);
 674           _gtk_sequence_node_rotate (node);
 675         }
 676     }
 677
 678   return node;
 679 }
 680
 681 static GtkSequenceNode *
 682 _gtk_sequence_node_new (gpointer          data)
 683 {
 684   GtkSequenceNode *node = g_new0 (GtkSequenceNode, 1);
 685
 686   node->parent = NULL;
 687   node->left = NULL;
 688   node->right = NULL;
 689
 690   node->data = data;
 691   node->is_end = FALSE;
 692   node->n_nodes = 1;
 693
 694   return node;
 695 }
 696
 697 static GtkSequenceNode *
 698 find_min (GtkSequenceNode *node)
 699 {
 700   splay (node);
 701
 702   while (node->left)
 703     node = node->left;
 704
 705   return node;
 706 }
 707
 708 static GtkSequenceNode *
 709 find_max (GtkSequenceNode *node)
 710 {
 711   splay (node);
 712
 713   while (node->right)
 714     node = node->right;
 715
 716   return node;
 717 }
 718
 719 static GtkSequenceNode *
 720 _gtk_sequence_node_find_first   (GtkSequenceNode    *node)
 721 {
 722   return splay (find_min (node));
 723 }
 724
 725 static GtkSequenceNode *
 726 _gtk_sequence_node_find_last    (GtkSequenceNode    *node)
 727 {
 728   return splay (find_max (node));
 729 }
 730
 731 static gint
 732 get_n_nodes (GtkSequenceNode *node)
 733 {
 734   if (node)
 735     return node->n_nodes;
 736   else
 737     return 0;
 738 }
 739
 740 static GtkSequenceNode *
 741 _gtk_sequence_node_find_by_pos  (GtkSequenceNode    *node,
 742                                  gint              pos)
 743 {
 744   gint i;
 745
 746   g_assert (node != NULL);
 747
 748   splay (node);
 749
 750   while ((i = get_n_nodes (node->left)) != pos)
 751     {
 752       if (i < pos)
 753         {
 754           node = node->right;
 755           pos -= (i + 1);
 756         }
 757       else
 758         {
 759           node = node->left;
 760           g_assert (node->parent != NULL);
 761         }
 762     }
 763
 764   return splay (node);
 765 }
 766
 767 static GtkSequenceNode *
 768 _gtk_sequence_node_prev         (GtkSequenceNode    *node)
 769 {
 770   splay (node);
 771
 772   if (node->left)
 773     {
 774       node = node->left;
 775       while (node->right)
 776         node = node->right;
 777     }
 778
 779   return splay (node);
 780 }
 781
 782 static GtkSequenceNode *
 783 _gtk_sequence_node_next         (GtkSequenceNode    *node)
 784 {
 785   splay (node);
 786
 787   if (node->right)
 788     {
 789       node = node->right;
 790       while (node->left)
 791         node = node->left;
 792     }
 793
 794   return splay (node);
 795 }
 796
 797 static gint
 798 _gtk_sequence_node_get_pos (GtkSequenceNode    *node)
 799 {
 800   splay (node);
 801
 802   return get_n_nodes (node->left);
 803 }
 804
 805 static GtkSequence *
 806 _gtk_sequence_node_get_sequence (GtkSequenceNode    *node)
 807 {
 808   splay (node);
 809
 810   return node->sequence;
 811 }
 812
 813 static GtkSequenceNode *
 814 _gtk_sequence_node_find_closest (GtkSequenceNode    *node,
 815                                  GtkSequenceNode    *other,
 816                                  GCompareDataFunc  cmp,
 817                                  gpointer          data)
 818 {
 819   GtkSequenceNode *best;
 820   gint c;
 821
 822   splay (node);
 823
 824   do
 825     {
 826       best = node;
 827
 828       if ((c = cmp (node, other, data)) != 0)
 829         {
 830           if (c < 0)
 831             node = node->right;
 832           else
 833             node = node->left;
 834         }
 835     }
 836   while (c != 0 && node != NULL);
 837
 838   return best;
 839 }
 840
 841 static void
 842 _gtk_sequence_node_free         (GtkSequenceNode    *node,
 843                                  GDestroyNotify    destroy)
 844 {
 845   /* FIXME:
 846    *
 847    * This is to avoid excessively deep recursions. A splay tree is not necessarily
 848    * balanced at all.
 849    *
 850    * I _think_ this is still linear in the number of nodes, but I'd like to
 851    * do something more efficient.
 852    */
 853
 854   while (node)
 855     {
 856       GtkSequenceNode *next;
 857
 858       node = splay (find_min (node));
 859       next = node->right;
 860       if (next)
 861         next->parent = NULL;
 862
 863       if (destroy && !node->is_end)
 864         destroy (node->data);
 865       g_free (node);
 866
 867       node = next;
 868     }
 869 }
 870
 871 #if 0
 872 static gboolean
 873 _gtk_sequence_node_is_singleton (GtkSequenceNode    *node)
 874 {
 875   splay (node);
 876
 877   if (node->left || node->right)
 878     return FALSE;
 879
 880   return TRUE;
 881 }
 882 #endif
 883
 884 static void
 885 _gtk_sequence_node_split        (GtkSequenceNode    *node,
 886                                  GtkSequenceNode   **left,
 887                                  GtkSequenceNode   **right)
 888 {
 889   GtkSequenceNode *left_tree;
 890
 891   splay (node);
 892
 893   left_tree = node->left;
 894   if (left_tree)
 895     {
 896       left_tree->parent = NULL;
 897       _gtk_sequence_node_update_fields (left_tree);
 898     }
 899
 900   node->left = NULL;
 901   _gtk_sequence_node_update_fields (node);
 902
 903   if (left)
 904     *left = left_tree;
 905
 906   if (right)
 907     *right = node;
 908 }
 909
 910 static void
 911 _gtk_sequence_node_insert_before (GtkSequenceNode *node,
 912                                   GtkSequenceNode *new)
 913 {
 914   g_assert (node != NULL);
 915   g_assert (new != NULL);
 916
 917   splay (node);
 918
 919   new = splay (find_min (new));
 920   g_assert (new->left == NULL);
 921
 922   if (node->left)
 923     node->left->parent = new;
 924
 925   new->left = node->left;
 926   new->parent = node;
 927
 928   node->left = new;
 929
 930   _gtk_sequence_node_update_fields (new);
 931   _gtk_sequence_node_update_fields (node);
 932 }
 933
 934 static gint
 935 _gtk_sequence_node_get_length (GtkSequenceNode    *node)
 936 {
 937   g_assert (node != NULL);
 938
 939   splay (node);
 940   return node->n_nodes;
 941 }
 942
 943 static void
 944 _gtk_sequence_node_remove        (GtkSequenceNode *node)
 945 {
 946   GtkSequenceNode *right, *left;
 947
 948   splay (node);
 949
 950   left = node->left;
 951   right = node->right;
 952
 953   node->left = node->right = NULL;
 954
 955   if (right)
 956     {
 957       right->parent = NULL;
 958
 959       right = _gtk_sequence_node_find_first (right);
 960       g_assert (right->left == NULL);
 961
 962       right->left = left;
 963       if (left)
 964         {
 965           left->parent = right;
 966           _gtk_sequence_node_update_fields (right);
 967         }
 968     }
 969   else if (left)
 970     left->parent = NULL;
 971 }
 972
 973 #if 0
 974 /* debug func */
 975 static gint
 976 _gtk_sequence_node_calc_height (GtkSequenceNode *node)
 977 {
 978   /* breadth first traversal */
 979   gint height = 0;
 980   GQueue *nodes = g_queue_new ();
 981
 982   g_queue_push_tail (nodes, node);
 983
 984   while (!g_queue_is_empty (nodes))
 985     {
 986       GQueue *tmp = g_queue_new ();
 987
 988       height++;
 989       while (!g_queue_is_empty (nodes))
 990         {
 991           GtkSequenceNode *node = g_queue_pop_head (nodes);
 992           if (node->left)
 993             g_queue_push_tail (tmp, node->left);
 994           if (node->right)
 995             g_queue_push_tail (tmp, node->right);
 996         }
 997
 998       g_queue_free (nodes);
 999
1000       nodes = tmp;
1001     }
1002   g_queue_free (nodes);
1003
1004   return height;
1005 }
1006 #endif
1007
1008 static void
1009 _gtk_sequence_node_insert_sorted (GtkSequenceNode *node,
1010                                   GtkSequenceNode *new,
1011                                   GCompareDataFunc cmp_func,
1012                                   gpointer cmp_data)
1013 {
1014   SortInfo info;
1015   GtkSequenceNode *closest;
1016   info.cmp = cmp_func;
1017   info.data = cmp_data;
1018
1019   closest =
1020     _gtk_sequence_node_find_closest (node, new, node_compare, &info);
1021
1022   g_assert (closest != new);
1023
1024   if (node_compare (new, closest, &info) > 0)
1025     closest = _gtk_sequence_node_next (closest);
1026
1027   _gtk_sequence_node_insert_before (closest, new);
1028 }
1029
1030 static gint
1031 _gtk_sequence_node_calc_height (GtkSequenceNode *node)
1032 {
1033   gint left_height;
1034   gint right_height;
1035
1036   if (node)
1037     {
1038       left_height = 0;
1039       right_height = 0;
1040
1041       if (node->left)
1042         left_height = _gtk_sequence_node_calc_height (node->left);
1043
1044       if (node->right)
1045         right_height = _gtk_sequence_node_calc_height (node->right);
1046
1047       return MAX (left_height, right_height) + 1;
1048     }
1049
1050   return 0;
1051 }
1052
1053 gint
1054 _gtk_sequence_calc_tree_height   (GtkSequence               *seq)
1055 {
1056   GtkSequenceNode *node = seq->node;
1057   gint r, l;
1058   while (node->parent)
1059     node = node->parent;
1060
1061   if (node)
1062     {
1063       r = _gtk_sequence_node_calc_height (node->right);
1064       l = _gtk_sequence_node_calc_height (node->left);
1065
1066       return MAX (r, l) + 1;
1067     }
1068   else
1069     return 0;
1070 }
1071
1072 GtkSequence   *
1073 _gtk_sequence_ptr_get_sequence (GtkSequencePtr    ptr)
1074 {
1075   GtkSequenceNode *node = ptr;
1076
1077   return node->sequence;
1078 }
1079
1080 void
1081 _gtk_sequence_swap (GtkSequencePtr a,
1082                     GtkSequencePtr b)
1083 {
1084   GtkSequenceNode *leftmost, *rightmost, *rightmost_next;
1085   int a_pos, b_pos;
1086
1087   g_return_if_fail (!_gtk_sequence_ptr_is_end (a));
1088   g_return_if_fail (!_gtk_sequence_ptr_is_end (b));
1089
1090   if (a == b)
1091       return;
1092
1093   a_pos = _gtk_sequence_ptr_get_position (a);
1094   b_pos = _gtk_sequence_ptr_get_position (b);
1095
1096   if (a_pos > b_pos)
1097     {
1098       leftmost = b;
1099       rightmost = a;
1100     }
1101   else
1102     {
1103       leftmost = a;
1104       rightmost = b;
1105     }
1106
1107   rightmost_next = _gtk_sequence_node_next (rightmost);
1108
1109   /* Situation now:  ..., leftmost, ......., rightmost, rightmost_next, ... */
1110
1111   _gtk_sequence_move (rightmost, leftmost);
1112   _gtk_sequence_move (leftmost, rightmost_next);
1113 }
1114
1115 void
1116 _gtk_sequence_move (GtkSequencePtr ptr,
1117                     GtkSequencePtr new_pos)
1118 {
1119   g_return_if_fail (ptr != NULL);
1120   g_return_if_fail (new_pos != NULL);
1121
1122   if (ptr == new_pos)
1123     return;
1124
1125   _gtk_sequence_unlink (ptr->sequence, ptr);
1126   _gtk_sequence_node_insert_before (new_pos, ptr);
1127 }
1128
1129 /* Overwrites the existing pointer. */
1130 void
1131 _gtk_sequence_set             (GtkSequencePtr     ptr,
1132                                gpointer           data)
1133 {
1134   GtkSequence *seq;
1135
1136   g_return_if_fail (!_gtk_sequence_ptr_is_end (ptr));
1137
1138   seq = _gtk_sequence_node_get_sequence (ptr);
1139   if (seq->data_destroy_notify)
1140     seq->data_destroy_notify (ptr->data);
1141   ptr->data = data;
1142 }