src/gtk/gtksctree.c

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