83ef9d7736ee046aa4a61980c900ef246c653393
[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         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 }