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