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