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