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