src/gtksctree.c

   1 /*
   2  * This program is based on gtkflist.c
   3  */
   4
   5 #include <stdlib.h>
   6
   7 #include "gtksctree.h"
   8
   9
  10 enum {
  11         ROW_POPUP_MENU,
  12         EMPTY_POPUP_MENU,
  13         OPEN_ROW,
  14         START_DRAG,
  15         LAST_SIGNAL
  16 };
  17
  18
  19 static void gtk_sctree_class_init (GtkSCTreeClass *class);
  20 static void gtk_sctree_init (GtkSCTree *sctree);
  21
  22 static gint gtk_sctree_button_press (GtkWidget *widget, GdkEventButton *event);
  23 static gint gtk_sctree_button_release (GtkWidget *widget, GdkEventButton *event);
  24 static gint gtk_sctree_motion (GtkWidget *widget, GdkEventMotion *event);
  25 static void gtk_sctree_drag_begin (GtkWidget *widget, GdkDragContext *context);
  26 static void gtk_sctree_drag_end (GtkWidget *widget, GdkDragContext *context);
  27 static void gtk_sctree_drag_data_get (GtkWidget *widget, GdkDragContext *context,
  28                                      GtkSelectionData *data, guint info, guint time);
  29 static void gtk_sctree_drag_leave (GtkWidget *widget, GdkDragContext *context, guint time);
  30 static gboolean gtk_sctree_drag_motion (GtkWidget *widget, GdkDragContext *context,
  31                                        gint x, gint y, guint time);
  32 static gboolean gtk_sctree_drag_drop (GtkWidget *widget, GdkDragContext *context,
  33                                      gint x, gint y, guint time);
  34 static void gtk_sctree_drag_data_received (GtkWidget *widget, GdkDragContext *context,
  35                                           gint x, gint y, GtkSelectionData *data,
  36                                           guint info, guint time);
  37
  38 static void gtk_sctree_clear (GtkCList *clist);
  39 static void gtk_sctree_collapse (GtkCTree *ctree, GtkCTreeNode *node);
  40
  41 static void tree_sort (GtkCTree *ctree, GtkCTreeNode  *node, gpointer data);
  42 void gtk_sctree_sort_node (GtkCTree *ctree, GtkCTreeNode *node);
  43 static void real_sort_list (GtkCList *clist);
  44 void gtk_sctree_sort_recursive (GtkCTree *ctree, GtkCTreeNode *node);
  45
  46 static void gtk_ctree_link (GtkCTree *ctree,
  47                         GtkCTreeNode  *node,
  48                         GtkCTreeNode  *parent,
  49                         GtkCTreeNode  *sibling,
  50                         gboolean       update_focus_row);
  51
  52 static void gtk_ctree_unlink (GtkCTree      *ctree,
  53                         GtkCTreeNode  *node,
  54                         gboolean       update_focus_row);
  55
  56 static void tree_update_level (GtkCTree      *ctree,
  57                         GtkCTreeNode  *node,
  58                         gpointer       data);
  59
  60 static GtkCTreeNode * gtk_ctree_last_visible (GtkCTree     *ctree,
  61                                               GtkCTreeNode *node);
  62
  63 static GtkCTreeClass *parent_class;
  64
  65 static guint sctree_signals[LAST_SIGNAL];
  66
  67
  68 #define GTK_CLIST_CLASS_FW(_widget_) GTK_CLIST_CLASS (((GtkObject*) (_widget_))->klass)
  69
  70 /**
  71  * gtk_sctree_get_type:
  72  * @void:
  73  *
  74  * Creates the GtkSCTree class and its type information
  75  *
  76  * Return value: The type ID for GtkSCTreeClass
  77  **/
  78 GtkType
  79 gtk_sctree_get_type (void)
  80 {
  81         static GtkType sctree_type = 0;
  82
  83         if (!sctree_type) {
  84                 GtkTypeInfo sctree_info = {
  85                         "GtkSCTree",
  86                         sizeof (GtkSCTree),
  87                         sizeof (GtkSCTreeClass),
  88                         (GtkClassInitFunc) gtk_sctree_class_init,
  89                         (GtkObjectInitFunc) gtk_sctree_init,
  90                         NULL, /* reserved_1 */
  91                         NULL, /* reserved_2 */
  92                         (GtkClassInitFunc) NULL
  93                 };
  94
  95                 sctree_type = gtk_type_unique (gtk_ctree_get_type (), &sctree_info);
  96         }
  97
  98         return sctree_type;
  99 }
 100
 101 /* Standard class initialization function */
 102 static void
 103 gtk_sctree_class_init (GtkSCTreeClass *klass)
 104 {
 105         GtkObjectClass *object_class;
 106         GtkWidgetClass *widget_class;
 107         GtkCListClass *clist_class;
 108         GtkCTreeClass *ctree_class;
 109
 110         object_class = (GtkObjectClass *) klass;
 111         widget_class = (GtkWidgetClass *) klass;
 112         clist_class = (GtkCListClass *) klass;
 113         ctree_class = (GtkCTreeClass *) klass;
 114
 115         parent_class = gtk_type_class (gtk_ctree_get_type ());
 116
 117         sctree_signals[ROW_POPUP_MENU] =
 118                 gtk_signal_new ("row_popup_menu",
 119                                 GTK_RUN_FIRST,
 120                                 object_class->type,
 121                                 GTK_SIGNAL_OFFSET (GtkSCTreeClass, row_popup_menu),
 122                                 gtk_marshal_NONE__POINTER,
 123                                 GTK_TYPE_NONE, 1,
 124                                 GTK_TYPE_GDK_EVENT);
 125         sctree_signals[EMPTY_POPUP_MENU] =
 126                 gtk_signal_new ("empty_popup_menu",
 127                                 GTK_RUN_FIRST,
 128                                 object_class->type,
 129                                 GTK_SIGNAL_OFFSET (GtkSCTreeClass, empty_popup_menu),
 130                                 gtk_marshal_NONE__POINTER,
 131                                 GTK_TYPE_NONE, 1,
 132                                 GTK_TYPE_GDK_EVENT);
 133         sctree_signals[OPEN_ROW] =
 134                 gtk_signal_new ("open_row",
 135                                 GTK_RUN_FIRST,
 136                                 object_class->type,
 137                                 GTK_SIGNAL_OFFSET (GtkSCTreeClass, open_row),
 138                                 gtk_marshal_NONE__NONE,
 139                                 GTK_TYPE_NONE, 0);
 140         sctree_signals[START_DRAG] =
 141                 gtk_signal_new ("start_drag",
 142                                 GTK_RUN_FIRST,
 143                                 object_class->type,
 144                                 GTK_SIGNAL_OFFSET (GtkSCTreeClass, start_drag),
 145                                 gtk_marshal_NONE__INT_POINTER,
 146                                 GTK_TYPE_NONE, 2,
 147                                 GTK_TYPE_INT,
 148                                 GTK_TYPE_GDK_EVENT);
 149
 150         gtk_object_class_add_signals (object_class, sctree_signals, LAST_SIGNAL);
 151
 152         clist_class->clear = gtk_sctree_clear;
 153         ctree_class->tree_collapse = gtk_sctree_collapse;
 154
 155         widget_class->button_press_event = gtk_sctree_button_press;
 156         widget_class->button_release_event = gtk_sctree_button_release;
 157         widget_class->motion_notify_event = gtk_sctree_motion;
 158         widget_class->drag_begin = gtk_sctree_drag_begin;
 159         widget_class->drag_end = gtk_sctree_drag_end;
 160         widget_class->drag_data_get = gtk_sctree_drag_data_get;
 161         widget_class->drag_leave = gtk_sctree_drag_leave;
 162         widget_class->drag_motion = gtk_sctree_drag_motion;
 163         widget_class->drag_drop = gtk_sctree_drag_drop;
 164         widget_class->drag_data_received = gtk_sctree_drag_data_received;
 165 }
 166
 167 /* Standard object initialization function */
 168 static void
 169 gtk_sctree_init (GtkSCTree *sctree)
 170 {
 171         sctree->anchor_row = NULL;
 172
 173         /* GtkCTree does not specify pointer motion by default */
 174         gtk_widget_add_events (GTK_WIDGET (sctree), GDK_POINTER_MOTION_MASK);
 175         gtk_widget_add_events (GTK_WIDGET (sctree), GDK_POINTER_MOTION_MASK);
 176 }
 177
 178 /* Get information the specified row is selected. */
 179
 180 static gboolean
 181 row_is_selected(GtkSCTree *sctree, gint row)
 182 {
 183         GtkCListRow *clist_row;
 184         clist_row =  g_list_nth (GTK_CLIST(sctree)->row_list, row)->data;
 185         return clist_row ? clist_row->state == GTK_STATE_SELECTED : FALSE;
 186 }
 187
 188 /* Selects the rows between the anchor to the specified row, inclusive.  */
 189 static void
 190 select_range (GtkSCTree *sctree, gint row)
 191 {
 192         gint prev_row;
 193         gint min, max;
 194         gint i;
 195
 196         if (sctree->anchor_row == NULL) {
 197                 prev_row = row;
 198                 sctree->anchor_row = gtk_ctree_node_nth(GTK_CTREE(sctree), row);
 199         } else
 200                 prev_row = g_list_position(GTK_CLIST(sctree)->row_list,
 201                                            (GList *)sctree->anchor_row);
 202
 203         if (row < prev_row) {
 204                 min = row;
 205                 max = prev_row;
 206         } else {
 207                 min = prev_row;
 208                 max = row;
 209         }
 210         for (i = min; i <= max; i++)
 211                 gtk_clist_select_row (GTK_CLIST (sctree), i, -1);
 212 }
 213
 214 /* Handles row selection according to the specified modifier state */
 215 static void
 216 select_row (GtkSCTree *sctree, gint row, gint col, guint state)
 217 {
 218         gboolean range, additive;
 219         g_return_if_fail (sctree != NULL);
 220         g_return_if_fail (GTK_IS_SCTREE (sctree));
 221
 222         range = ((state & GDK_SHIFT_MASK) != 0) &&
 223                 (GTK_CLIST(sctree)->selection_mode != GTK_SELECTION_SINGLE) &&
 224                 (GTK_CLIST(sctree)->selection_mode != GTK_SELECTION_BROWSE);
 225         additive = ((state & GDK_CONTROL_MASK) != 0) &&
 226                    (GTK_CLIST(sctree)->selection_mode != GTK_SELECTION_SINGLE) &&
 227                    (GTK_CLIST(sctree)->selection_mode != GTK_SELECTION_BROWSE);
 228
 229         gtk_clist_freeze (GTK_CLIST (sctree));
 230         GTK_CLIST(sctree)->focus_row = row;
 231         GTK_CLIST_CLASS(GTK_OBJECT(sctree)->klass)->refresh(GTK_CLIST(sctree));
 232         if (!additive)
 233                 gtk_clist_unselect_all (GTK_CLIST (sctree));
 234
 235         if (!range) {
 236                 GtkCTreeNode *node;
 237
 238                 node = gtk_ctree_node_nth (GTK_CTREE(sctree), row);
 239
 240                 /*No need to manage overlapped list*/
 241                 if (additive) {
 242                         if (row_is_selected(sctree, row))
 243                                 gtk_clist_unselect_row (GTK_CLIST (sctree), row, col);
 244                         else
 245                                 gtk_signal_emit_by_name
 246                                         (GTK_OBJECT (sctree),
 247                                          "tree_select_row", node, col);
 248                 } else {
 249                         gtk_signal_emit_by_name
 250                                 (GTK_OBJECT (sctree),
 251                                  "tree_select_row", node, col);
 252                 }
 253                 sctree->anchor_row = node;
 254         } else
 255                 select_range (sctree, row);
 256         gtk_clist_thaw (GTK_CLIST (sctree));
 257 }
 258
 259 /* Our handler for button_press events.  We override all of GtkCList's broken
 260  * behavior.
 261  */
 262 static gint
 263 gtk_sctree_button_press (GtkWidget *widget, GdkEventButton *event)
 264 {
 265         GtkSCTree *sctree;
 266         GtkCList *clist;
 267         gboolean on_row;
 268         gint row;
 269         gint col;
 270         gint retval;
 271
 272         g_return_val_if_fail (widget != NULL, FALSE);
 273         g_return_val_if_fail (GTK_IS_SCTREE (widget), FALSE);
 274         g_return_val_if_fail (event != NULL, FALSE);
 275
 276         sctree = GTK_SCTREE (widget);
 277         clist = GTK_CLIST (widget);
 278         retval = FALSE;
 279
 280         if (event->window != clist->clist_window)
 281                 return (* GTK_WIDGET_CLASS (parent_class)->button_press_event) (widget, event);
 282
 283         on_row = gtk_clist_get_selection_info (clist, event->x, event->y, &row, &col);
 284
 285         if (on_row && !GTK_WIDGET_HAS_FOCUS(widget))
 286                 gtk_widget_grab_focus (widget);
 287
 288         if (gtk_ctree_is_hot_spot (GTK_CTREE(sctree), event->x, event->y)) {
 289                 gtk_ctree_toggle_expansion
 290                         (GTK_CTREE(sctree),
 291                          gtk_ctree_node_nth(GTK_CTREE(sctree), row));
 292                 return TRUE;
 293         }
 294
 295         switch (event->type) {
 296         case GDK_BUTTON_PRESS:
 297                 if (event->button == 1 || event->button == 2) {
 298                         if (event->button == 2)
 299                                 event->state &= ~(GDK_SHIFT_MASK | GDK_CONTROL_MASK);
 300                         if (on_row) {
 301                                 /* Save the mouse info for DnD */
 302                                 sctree->dnd_press_button = event->button;
 303                                 sctree->dnd_press_x = event->x;
 304                                 sctree->dnd_press_y = event->y;
 305
 306                                 /* Handle selection */
 307                                 if ((row_is_selected (sctree, row)
 308                                      && !(event->state & (GDK_CONTROL_MASK | GDK_SHIFT_MASK)))
 309                                     || ((event->state & GDK_CONTROL_MASK)
 310                                         && !(event->state & GDK_SHIFT_MASK))) {
 311                                         sctree->dnd_select_pending = TRUE;
 312                                         sctree->dnd_select_pending_state = event->state;
 313                                         sctree->dnd_select_pending_row = row;
 314                                 } else
 315                                         select_row (sctree, row, col, event->state);
 316                         } else
 317                                 gtk_clist_unselect_all (clist);
 318
 319                         retval = TRUE;
 320                 } else if (event->button == 3) {
 321                         /* Emit *_popup_menu signal*/
 322                         if (on_row) {
 323                                 if (!row_is_selected(sctree,row))
 324                                         select_row (sctree, row, col, 0);
 325                                 gtk_signal_emit (GTK_OBJECT (sctree),
 326                                                  sctree_signals[ROW_POPUP_MENU],
 327                                                  event);
 328                         } else {
 329                                 gtk_clist_unselect_all(clist);
 330                                 gtk_signal_emit (GTK_OBJECT (sctree),
 331                                                  sctree_signals[EMPTY_POPUP_MENU],
 332                                                  event);
 333                         }
 334                         retval = TRUE;
 335                 }
 336
 337                 break;
 338
 339         case GDK_2BUTTON_PRESS:
 340                 if (event->button != 1)
 341                         break;
 342
 343                 sctree->dnd_select_pending = FALSE;
 344                 sctree->dnd_select_pending_state = 0;
 345
 346                 if (on_row)
 347                         gtk_signal_emit (GTK_OBJECT (sctree),
 348                                          sctree_signals[OPEN_ROW]);
 349
 350                 retval = TRUE;
 351                 break;
 352
 353         default:
 354                 break;
 355         }
 356
 357         return retval;
 358 }
 359
 360 /* Our handler for button_release events.  We override all of GtkCList's broken
 361  * behavior.
 362  */
 363 static gint
 364 gtk_sctree_button_release (GtkWidget *widget, GdkEventButton *event)
 365 {
 366         GtkSCTree *sctree;
 367         GtkCList *clist;
 368         gint on_row;
 369         gint row, col;
 370         gint retval;
 371
 372         g_return_val_if_fail (widget != NULL, FALSE);
 373         g_return_val_if_fail (GTK_IS_SCTREE (widget), FALSE);
 374         g_return_val_if_fail (event != NULL, FALSE);
 375
 376         sctree = GTK_SCTREE (widget);
 377         clist = GTK_CLIST (widget);
 378         retval = FALSE;
 379
 380         if (event->window != clist->clist_window)
 381                 return (* GTK_WIDGET_CLASS (parent_class)->button_release_event) (widget, event);
 382
 383         on_row = gtk_clist_get_selection_info (clist, event->x, event->y, &row, &col);
 384
 385         if (!(event->button == 1 || event->button == 2))
 386                 return FALSE;
 387
 388         sctree->dnd_press_button = 0;
 389         sctree->dnd_press_x = 0;
 390         sctree->dnd_press_y = 0;
 391
 392         if (on_row) {
 393                 if (sctree->dnd_select_pending) {
 394                         select_row (sctree, row, col, sctree->dnd_select_pending_state);
 395                         sctree->dnd_select_pending = FALSE;
 396                         sctree->dnd_select_pending_state = 0;
 397                 }
 398
 399                 retval = TRUE;
 400         }
 401
 402         return retval;
 403 }
 404
 405 /* Our handler for motion_notify events.  We override all of GtkCList's broken
 406  * behavior.
 407  */
 408 static gint
 409 gtk_sctree_motion (GtkWidget *widget, GdkEventMotion *event)
 410 {
 411         GtkSCTree *sctree;
 412         GtkCList *clist;
 413
 414         g_return_val_if_fail (widget != NULL, FALSE);
 415         g_return_val_if_fail (GTK_IS_SCTREE (widget), FALSE);
 416         g_return_val_if_fail (event != NULL, FALSE);
 417
 418         sctree = GTK_SCTREE (widget);
 419         clist = GTK_CLIST (widget);
 420
 421         if (event->window != clist->clist_window)
 422                 return (* GTK_WIDGET_CLASS (parent_class)->motion_notify_event) (widget, event);
 423
 424         if (!((sctree->dnd_press_button == 1 && (event->state & GDK_BUTTON1_MASK))
 425               || (sctree->dnd_press_button == 2 && (event->state & GDK_BUTTON2_MASK))))
 426                 return FALSE;
 427
 428         /* This is the same threshold value that is used in gtkdnd.c */
 429
 430         if (MAX (ABS (sctree->dnd_press_x - event->x),
 431                  ABS (sctree->dnd_press_y - event->y)) <= 3)
 432                 return FALSE;
 433
 434         /* Handle any pending selections */
 435
 436         if (sctree->dnd_select_pending) {
 437                 if (!row_is_selected(sctree,sctree->dnd_select_pending_row))
 438                         select_row (sctree,
 439                                     sctree->dnd_select_pending_row,
 440                                     -1,
 441                                     sctree->dnd_select_pending_state);
 442
 443                 sctree->dnd_select_pending = FALSE;
 444                 sctree->dnd_select_pending_state = 0;
 445         }
 446
 447         gtk_signal_emit (GTK_OBJECT (sctree),
 448                          sctree_signals[START_DRAG],
 449                          sctree->dnd_press_button,
 450                          event);
 451         return TRUE;
 452 }
 453
 454 /* We override the drag_begin signal to do nothing */
 455 static void
 456 gtk_sctree_drag_begin (GtkWidget *widget, GdkDragContext *context)
 457 {
 458         /* nothing */
 459 }
 460
 461 /* We override the drag_end signal to do nothing */
 462 static void
 463 gtk_sctree_drag_end (GtkWidget *widget, GdkDragContext *context)
 464 {
 465         /* nothing */
 466 }
 467
 468 /* We override the drag_data_get signal to do nothing */
 469 static void
 470 gtk_sctree_drag_data_get (GtkWidget *widget, GdkDragContext *context,
 471                                      GtkSelectionData *data, guint info, guint time)
 472 {
 473         /* nothing */
 474 }
 475
 476 /* We override the drag_leave signal to do nothing */
 477 static void
 478 gtk_sctree_drag_leave (GtkWidget *widget, GdkDragContext *context, guint time)
 479 {
 480         /* nothing */
 481 }
 482
 483 /* We override the drag_motion signal to do nothing */
 484 static gboolean
 485 gtk_sctree_drag_motion (GtkWidget *widget, GdkDragContext *context,
 486                                    gint x, gint y, guint time)
 487 {
 488         return FALSE;
 489 }
 490
 491 /* We override the drag_drop signal to do nothing */
 492 static gboolean
 493 gtk_sctree_drag_drop (GtkWidget *widget, GdkDragContext *context,
 494                                  gint x, gint y, guint time)
 495 {
 496         return FALSE;
 497 }
 498
 499 /* We override the drag_data_received signal to do nothing */
 500 static void
 501 gtk_sctree_drag_data_received (GtkWidget *widget, GdkDragContext *context,
 502                                           gint x, gint y, GtkSelectionData *data,
 503                                           guint info, guint time)
 504 {
 505         /* nothing */
 506 }
 507
 508 /* Our handler for the clear signal of the clist.  We have to reset the anchor
 509  * to null.
 510  */
 511 static void
 512 gtk_sctree_clear (GtkCList *clist)
 513 {
 514         GtkSCTree *sctree;
 515
 516         g_return_if_fail (clist != NULL);
 517         g_return_if_fail (GTK_IS_SCTREE (clist));
 518
 519         sctree = GTK_SCTREE (clist);
 520         sctree->anchor_row = NULL;
 521
 522         if (((GtkCListClass *)parent_class)->clear)
 523                 (* ((GtkCListClass *)parent_class)->clear) (clist);
 524 }
 525
 526 /* Our handler for the change_focus_row_expansion signal of the ctree.
 527  We have to set the anchor to parent visible node.
 528  */
 529 static void
 530 gtk_sctree_collapse (GtkCTree *ctree, GtkCTreeNode *node)
 531 {
 532         g_return_if_fail (ctree != NULL);
 533         g_return_if_fail (GTK_IS_SCTREE (ctree));
 534
 535         (* parent_class->tree_collapse) (ctree, node);
 536         GTK_SCTREE(ctree)->anchor_row =
 537                 gtk_ctree_node_nth(ctree, GTK_CLIST(ctree)->focus_row);
 538 }
 539
 540 GtkWidget *gtk_sctree_new_with_titles (gint columns,
 541                                        gint tree_column,
 542                                        gchar *titles[])
 543 {
 544         GtkSCTree* sctree;
 545
 546         sctree = gtk_type_new (gtk_sctree_get_type ());
 547         gtk_ctree_construct (GTK_CTREE (sctree), columns, tree_column, titles);
 548         gtk_clist_set_selection_mode(GTK_CLIST(sctree), GTK_SELECTION_EXTENDED);
 549
 550         return GTK_WIDGET (sctree);
 551 }
 552
 553 void  gtk_sctree_select (GtkSCTree *sctree,
 554                          GtkCTreeNode *node)
 555 {
 556         select_row(sctree,
 557                    g_list_position(GTK_CLIST(sctree)->row_list, (GList *)node),
 558                    -1, 0);
 559 }
 560
 561 void  gtk_sctree_unselect_all (GtkSCTree *sctree)
 562 {
 563         gtk_clist_unselect_all(GTK_CLIST(sctree));
 564         sctree->anchor_row = NULL;
 565 }
 566
 567 /***********************************************************
 568  *             Tree sorting functions                      *
 569  ***********************************************************/
 570
 571 static void sink(GtkCList *clist, GPtrArray *numbers, gint root, gint bottom)
 572 {
 573         gint j, k ;
 574         GtkCTreeNode *temp;
 575
 576         j = 2 * root;
 577         k = j + 1;
 578
 579         /* find the maximum element of numbers[root],
 580            numbers[2*root] and numbers[2*root+1] */
 581         if (j <= bottom) {
 582                 if (clist->compare( clist, GTK_CTREE_ROW (g_ptr_array_index(numbers, root)),
 583                                     GTK_CTREE_ROW(g_ptr_array_index( numbers, j))) >= 0)
 584                         j = root;
 585                 if (k <= bottom)
 586                         if (clist->compare( clist, GTK_CTREE_ROW (g_ptr_array_index(numbers, k)),
 587                                             GTK_CTREE_ROW (g_ptr_array_index( numbers, j))) > 0)
 588                                 j = k;
 589                 /* if numbers[root] wasn't the maximum element then
 590                    sink again */
 591                 if (root != j) {
 592                         temp = g_ptr_array_index( numbers,root);
 593                         g_ptr_array_index( numbers, root) = g_ptr_array_index( numbers, j);
 594                         g_ptr_array_index( numbers, j) = temp;
 595                         sink( clist, numbers, j, bottom);
 596                 }
 597         }
 598 }
 599
 600 static void heap_sort(GtkCList *clist, GPtrArray *numbers, gint array_size)
 601 {
 602         gint i;
 603         GtkCTreeNode *temp;
 604
 605         /* build the Heap */
 606         for (i = (array_size / 2); i >= 1; i--)
 607                 sink( clist, numbers, i, array_size);
 608         /* output the Heap */
 609         for (i = array_size; i >= 2; i--) {
 610                 temp = g_ptr_array_index( numbers, 1);
 611                 g_ptr_array_index( numbers, 1) = g_ptr_array_index( numbers, i);
 612                 g_ptr_array_index( numbers, i) = temp;
 613                 sink( clist, numbers, 1, i-1);
 614         }
 615 }
 616
 617 static void
 618 tree_sort (GtkCTree    *ctree,
 619            GtkCTreeNode *node,
 620            gpointer      data)
 621 {
 622         GtkCTreeNode *list_start, *work, *next;
 623         GPtrArray *row_array, *viewable_array;
 624         GtkCList *clist;
 625         gint i;
 626
 627
 628         clist = GTK_CLIST (ctree);
 629
 630         if (node)
 631                 work = GTK_CTREE_ROW (node)->children;
 632         else
 633                 work = GTK_CTREE_NODE (clist->row_list);
 634
 635         row_array = g_ptr_array_new();
 636         viewable_array = g_ptr_array_new();
 637
 638         if (work) {
 639                 g_ptr_array_add( row_array, NULL);
 640                 while (work) {
 641                         /* add all rows to row_array */
 642                         g_ptr_array_add( row_array, work);
 643                         if (GTK_CTREE_ROW (work)->parent && gtk_ctree_is_viewable( ctree, work))
 644                                 g_ptr_array_add( viewable_array, GTK_CTREE_ROW (work)->parent);
 645                         next = GTK_CTREE_ROW (work)->sibling;
 646                         gtk_ctree_unlink( ctree, work, FALSE);
 647                         work = next;
 648                 }
 649
 650                 heap_sort( clist, row_array, (row_array->len)-1);
 651
 652                 if (node)
 653                         list_start = GTK_CTREE_ROW (node)->children;
 654                 else
 655                         list_start = GTK_CTREE_NODE (clist->row_list);
 656
 657                 if (clist->sort_type == GTK_SORT_ASCENDING) {
 658                         for (i=(row_array->len)-1; i>=1; i--) {
 659                                 work = g_ptr_array_index( row_array, i);
 660                                 gtk_ctree_link( ctree, work, node, list_start, FALSE);
 661                                 list_start = work;
 662                                 /* insert work at the beginning of the list */
 663                         }
 664                 } else {
 665                         for (i=1; i<row_array->len; i++) {
 666                                 work = g_ptr_array_index( row_array, i);
 667                                 gtk_ctree_link( ctree, work, node, list_start, FALSE);
 668                                 list_start = work;
 669                                 /* insert work at the beginning of the list */
 670                         }
 671                 }
 672
 673                 for (i=0; i<viewable_array->len; i++) {
 674                         gtk_ctree_expand( ctree, g_ptr_array_index( viewable_array, i));
 675                 }
 676
 677         }
 678
 679         g_ptr_array_free( row_array, TRUE);
 680         g_ptr_array_free( viewable_array, TRUE);
 681 }
 682
 683 void
 684 gtk_sctree_sort_recursive (GtkCTree     *ctree,
 685                           GtkCTreeNode *node)
 686 {
 687         GtkCList *clist;
 688         GtkCTreeNode *focus_node = NULL;
 689
 690         g_return_if_fail (ctree != NULL);
 691         g_return_if_fail (GTK_IS_CTREE (ctree));
 692
 693         clist = GTK_CLIST (ctree);
 694
 695         gtk_clist_freeze (clist);
 696
 697         if (clist->selection_mode == GTK_SELECTION_EXTENDED) {
 698                 GTK_CLIST_CLASS_FW (clist)->resync_selection (clist, NULL);
 699
 700                 g_list_free (clist->undo_selection);
 701                 g_list_free (clist->undo_unselection);
 702                 clist->undo_selection = NULL;
 703                 clist->undo_unselection = NULL;
 704         }
 705
 706         if (!node || (node && gtk_ctree_is_viewable (ctree, node)))
 707                 focus_node = GTK_CTREE_NODE (g_list_nth (clist->row_list, clist->focus_row));
 708
 709         gtk_ctree_post_recursive (ctree, node, GTK_CTREE_FUNC (tree_sort), NULL);
 710
 711         if (!node)
 712                 tree_sort (ctree, NULL, NULL);
 713
 714         if (focus_node) {
 715                 clist->focus_row = g_list_position (clist->row_list,(GList *)focus_node);
 716                 clist->undo_anchor = clist->focus_row;
 717         }
 718
 719         gtk_clist_thaw (clist);
 720 }
 721
 722 static void
 723 real_sort_list (GtkCList *clist)
 724 {
 725         gtk_sctree_sort_recursive (GTK_CTREE (clist), NULL);
 726 }
 727
 728 void
 729 gtk_sctree_sort_node (GtkCTree     *ctree,
 730                      GtkCTreeNode *node)
 731 {
 732         GtkCList *clist;
 733         GtkCTreeNode *focus_node = NULL;
 734
 735         g_return_if_fail (ctree != NULL);
 736         g_return_if_fail (GTK_IS_CTREE (ctree));
 737
 738         clist = GTK_CLIST (ctree);
 739
 740         gtk_clist_freeze (clist);
 741
 742         if (clist->selection_mode == GTK_SELECTION_EXTENDED) {
 743                 GTK_CLIST_CLASS_FW (clist)->resync_selection (clist, NULL);
 744
 745                 g_list_free (clist->undo_selection);
 746                 g_list_free (clist->undo_unselection);
 747                 clist->undo_selection = NULL;
 748                 clist->undo_unselection = NULL;
 749         }
 750
 751         if (!node || (node && gtk_ctree_is_viewable (ctree, node)))
 752                 focus_node = GTK_CTREE_NODE (g_list_nth (clist->row_list, clist->focus_row));
 753
 754         tree_sort (ctree, node, NULL);
 755
 756         if (focus_node) {
 757                 clist->focus_row = g_list_position (clist->row_list,(GList *)focus_node);
 758                 clist->undo_anchor = clist->focus_row;
 759         }
 760
 761         gtk_clist_thaw (clist);
 762 }
 763
 764 /************************************************************************/
 765
 766 static void
 767 gtk_ctree_unlink (GtkCTree     *ctree,
 768                   GtkCTreeNode *node,
 769                   gboolean      update_focus_row)
 770 {
 771         GtkCList *clist;
 772         gint rows;
 773         gint level;
 774         gint visible;
 775         GtkCTreeNode *work;
 776         GtkCTreeNode *parent;
 777         GList *list;
 778
 779         g_return_if_fail (ctree != NULL);
 780         g_return_if_fail (GTK_IS_CTREE (ctree));
 781         g_return_if_fail (node != NULL);
 782
 783         clist = GTK_CLIST (ctree);
 784
 785         if (update_focus_row && clist->selection_mode == GTK_SELECTION_EXTENDED) {
 786                 GTK_CLIST_CLASS_FW (clist)->resync_selection (clist, NULL);
 787
 788                 g_list_free (clist->undo_selection);
 789                 g_list_free (clist->undo_unselection);
 790                 clist->undo_selection = NULL;
 791                 clist->undo_unselection = NULL;
 792         }
 793
 794         visible = gtk_ctree_is_viewable (ctree, node);
 795
 796         /* clist->row_list_end unlinked ? */
 797         if (visible && (GTK_CTREE_NODE_NEXT (node) == NULL ||
 798            (GTK_CTREE_ROW (node)->children && gtk_ctree_is_ancestor (ctree, node,
 799             GTK_CTREE_NODE (clist->row_list_end)))))
 800                 clist->row_list_end = (GList *) (GTK_CTREE_NODE_PREV (node));
 801
 802         /* update list */
 803         rows = 0;
 804         level = GTK_CTREE_ROW (node)->level;
 805         work = GTK_CTREE_NODE_NEXT (node);
 806         while (work && GTK_CTREE_ROW (work)->level > level) {
 807                 work = GTK_CTREE_NODE_NEXT (work);
 808                 rows++;
 809         }
 810
 811         if (visible) {
 812                 clist->rows -= (rows + 1);
 813
 814                 if (update_focus_row) {
 815                         gint pos;
 816
 817                         pos = g_list_position (clist->row_list, (GList *)node);
 818                         if (pos + rows < clist->focus_row)
 819                                 clist->focus_row -= (rows + 1);
 820                         else if (pos <= clist->focus_row) {
 821                                 if (!GTK_CTREE_ROW (node)->sibling)
 822                                         clist->focus_row = MAX (pos - 1, 0);
 823                                 else
 824                                         clist->focus_row = pos;
 825
 826                                 clist->focus_row = MIN (clist->focus_row, clist->rows - 1);
 827                         }
 828                         clist->undo_anchor = clist->focus_row;
 829                 }
 830         }
 831
 832         if (work) {
 833                 list = (GList *)GTK_CTREE_NODE_PREV (work);
 834                 list->next = NULL;
 835                 list = (GList *)work;
 836                 list->prev = (GList *)GTK_CTREE_NODE_PREV (node);
 837         }
 838
 839         if (GTK_CTREE_NODE_PREV (node) &&
 840             GTK_CTREE_NODE_NEXT (GTK_CTREE_NODE_PREV (node)) == node) {
 841                 list = (GList *)GTK_CTREE_NODE_PREV (node);
 842                 list->next = (GList *)work;
 843         }
 844
 845         /* update tree */
 846         parent = GTK_CTREE_ROW (node)->parent;
 847         if (parent) {
 848                 if (GTK_CTREE_ROW (parent)->children == node) {
 849                         GTK_CTREE_ROW (parent)->children = GTK_CTREE_ROW (node)->sibling;
 850                         if (!GTK_CTREE_ROW (parent)->children)
 851                                 gtk_ctree_collapse (ctree, parent);
 852                 }
 853                 else {
 854                         GtkCTreeNode *sibling;
 855
 856                         sibling = GTK_CTREE_ROW (parent)->children;
 857                         while (GTK_CTREE_ROW (sibling)->sibling != node)
 858                                 sibling = GTK_CTREE_ROW (sibling)->sibling;
 859                         GTK_CTREE_ROW (sibling)->sibling = GTK_CTREE_ROW (node)->sibling;
 860                 }
 861         }
 862         else {
 863                 if (clist->row_list == (GList *)node)
 864                         clist->row_list = (GList *) (GTK_CTREE_ROW (node)->sibling);
 865                 else {
 866                         GtkCTreeNode *sibling;
 867
 868                         sibling = GTK_CTREE_NODE (clist->row_list);
 869                         while (GTK_CTREE_ROW (sibling)->sibling != node)
 870                                 sibling = GTK_CTREE_ROW (sibling)->sibling;
 871                         GTK_CTREE_ROW (sibling)->sibling = GTK_CTREE_ROW (node)->sibling;
 872                 }
 873         }
 874 }
 875
 876 static void
 877 gtk_ctree_link (GtkCTree     *ctree,
 878                 GtkCTreeNode *node,
 879                 GtkCTreeNode *parent,
 880                 GtkCTreeNode *sibling,
 881                 gboolean      update_focus_row)
 882 {
 883         GtkCList *clist;
 884         GList *list_end;
 885         GList *list;
 886         GList *work;
 887         gboolean visible = FALSE;
 888         gint rows = 0;
 889
 890         if (sibling)
 891                 g_return_if_fail (GTK_CTREE_ROW (sibling)->parent == parent);
 892         g_return_if_fail (node != NULL);
 893         g_return_if_fail (node != sibling);
 894         g_return_if_fail (node != parent);
 895
 896         clist = GTK_CLIST (ctree);
 897
 898         if (update_focus_row && clist->selection_mode == GTK_SELECTION_EXTENDED) {
 899                 GTK_CLIST_CLASS_FW (clist)->resync_selection (clist, NULL);
 900
 901                 g_list_free (clist->undo_selection);
 902                 g_list_free (clist->undo_unselection);
 903                 clist->undo_selection = NULL;
 904                 clist->undo_unselection = NULL;
 905         }
 906
 907         for (rows = 1, list_end = (GList *)node; list_end->next;
 908              list_end = list_end->next)
 909                 rows++;
 910
 911         GTK_CTREE_ROW (node)->parent = parent;
 912         GTK_CTREE_ROW (node)->sibling = sibling;
 913
 914         if (!parent || (parent && (gtk_ctree_is_viewable (ctree, parent) &&
 915             GTK_CTREE_ROW (parent)->expanded))) {
 916                 visible = TRUE;
 917                 clist->rows += rows;
 918         }
 919
 920         if (parent)
 921                 work = (GList *)(GTK_CTREE_ROW (parent)->children);
 922         else
 923                 work = clist->row_list;
 924
 925         if (sibling) {
 926                 if (work != (GList *)sibling) {
 927                         while (GTK_CTREE_ROW (work)->sibling != sibling)
 928                                 work = (GList *)(GTK_CTREE_ROW (work)->sibling);
 929                         GTK_CTREE_ROW (work)->sibling = node;
 930                 }
 931
 932                 if (sibling == GTK_CTREE_NODE (clist->row_list))
 933                 clist->row_list = (GList *) node;
 934                 if (GTK_CTREE_NODE_PREV (sibling) &&
 935                     GTK_CTREE_NODE_NEXT (GTK_CTREE_NODE_PREV (sibling)) == sibling) {
 936                         list = (GList *)GTK_CTREE_NODE_PREV (sibling);
 937                         list->next = (GList *)node;
 938                 }
 939
 940                 list = (GList *)node;
 941                 list->prev = (GList *)GTK_CTREE_NODE_PREV (sibling);
 942                 list_end->next = (GList *)sibling;
 943                 list = (GList *)sibling;
 944                 list->prev = list_end;
 945                 if (parent && GTK_CTREE_ROW (parent)->children == sibling)
 946                         GTK_CTREE_ROW (parent)->children = node;
 947         }
 948         else {
 949                 if (work) {
 950                         /* find sibling */
 951                         while (GTK_CTREE_ROW (work)->sibling)
 952                         work = (GList *)(GTK_CTREE_ROW (work)->sibling);
 953                         GTK_CTREE_ROW (work)->sibling = node;
 954
 955                         /* find last visible child of sibling */
 956                         work = (GList *) gtk_ctree_last_visible (ctree,
 957                                GTK_CTREE_NODE (work));
 958
 959                         list_end->next = work->next;
 960                         if (work->next)
 961                                 list = work->next->prev = list_end;
 962                         work->next = (GList *)node;
 963                         list = (GList *)node;
 964                         list->prev = work;
 965                 }
 966                 else {
 967                         if (parent) {
 968                                 GTK_CTREE_ROW (parent)->children = node;
 969                                 list = (GList *)node;
 970                                 list->prev = (GList *)parent;
 971                                 if (GTK_CTREE_ROW (parent)->expanded) {
 972                                         list_end->next = (GList *)GTK_CTREE_NODE_NEXT (parent);
 973                                         if (GTK_CTREE_NODE_NEXT(parent)) {
 974                                                 list = (GList *)GTK_CTREE_NODE_NEXT (parent);
 975                                                 list->prev = list_end;
 976                                         }
 977                                         list = (GList *)parent;
 978                                         list->next = (GList *)node;
 979                                 }
 980                                 else
 981                                         list_end->next = NULL;
 982                         }
 983                         else {
 984                                 clist->row_list = (GList *)node;
 985                                 list = (GList *)node;
 986                                 list->prev = NULL;
 987                                 list_end->next = NULL;
 988                         }
 989                 }
 990         }
 991
 992         gtk_ctree_pre_recursive (ctree, node, tree_update_level, NULL);
 993
 994         if (clist->row_list_end == NULL ||
 995             clist->row_list_end->next == (GList *)node)
 996                 clist->row_list_end = list_end;
 997
 998         if (visible && update_focus_row) {
 999                 gint pos;
1000
1001                 pos = g_list_position (clist->row_list, (GList *)node);
1002
1003                 if (pos <= clist->focus_row) {
1004                         clist->focus_row += rows;
1005                         clist->undo_anchor = clist->focus_row;
1006                 }
1007         }
1008 }
1009
1010 static void
1011 tree_update_level (GtkCTree     *ctree,
1012                    GtkCTreeNode *node,
1013                    gpointer      data)
1014 {
1015         if (!node)
1016                 return;
1017
1018         if (GTK_CTREE_ROW (node)->parent)
1019                 GTK_CTREE_ROW (node)->level =
1020                 GTK_CTREE_ROW (GTK_CTREE_ROW (node)->parent)->level + 1;
1021         else
1022                 GTK_CTREE_ROW (node)->level = 1;
1023 }
1024
1025 static GtkCTreeNode *
1026 gtk_ctree_last_visible (GtkCTree     *ctree,
1027                         GtkCTreeNode *node)
1028 {
1029         GtkCTreeNode *work;
1030
1031         if (!node)
1032                 return NULL;
1033
1034         work = GTK_CTREE_ROW (node)->children;
1035
1036         if (!work || !GTK_CTREE_ROW (node)->expanded)
1037                 return node;
1038
1039         while (GTK_CTREE_ROW (work)->sibling)
1040                 work = GTK_CTREE_ROW (work)->sibling;
1041
1042         return gtk_ctree_last_visible (ctree, work);
1043 }