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