3 * sort.c : Routines for sorting cell ranges
6 * JP Rosevear <jpr@arcavia.com>
9 * (C) 2000 Morten Welinder
11 #include <gnumeric-config.h>
16 #include <clipboard.h>
21 #include <goffice/goffice.h>
32 gnm_sort_data_destroy (GnmSortData
*data
)
34 g_free (data
->clauses
);
36 g_free (data
->locale
);
41 gnm_sort_data_length (GnmSortData
const *data
)
44 return range_height (data
->range
);
46 return range_width (data
->range
);
49 /* The routines to do the sorting */
51 sort_compare_cells (GnmCell
const *ca
, GnmCell
const *cb
,
52 GnmSortClause
*clause
, gboolean default_locale
)
56 GnmValDiff comp
= IS_EQUAL
;
68 ta
= VALUE_IS_EMPTY (a
) ? VALUE_EMPTY
: a
->v_any
.type
;
69 tb
= VALUE_IS_EMPTY (b
) ? VALUE_EMPTY
: b
->v_any
.type
;
71 if (ta
== VALUE_EMPTY
&& tb
!= VALUE_EMPTY
) {
72 comp
= clause
->asc
? IS_LESS
: IS_GREATER
;
73 } else if (tb
== VALUE_EMPTY
&& ta
!= VALUE_EMPTY
) {
74 comp
= clause
->asc
? IS_GREATER
: IS_LESS
;
75 } else if (ta
== VALUE_ERROR
&& tb
!= VALUE_ERROR
) {
77 } else if (tb
== VALUE_ERROR
&& ta
!= VALUE_ERROR
) {
80 comp
= default_locale
? value_compare (a
, b
, clause
->cs
)
81 : value_compare_no_cache (a
, b
, clause
->cs
);
84 if (comp
== IS_LESS
) {
85 ans
= clause
->asc
? 1 : -1;
86 } else if (comp
== IS_GREATER
) {
87 ans
= clause
->asc
? -1 : 1;
94 sort_compare_sets (GnmSortData
const *data
, int indexa
, int indexb
,
95 gboolean default_locale
)
100 while (clause
< data
->num_clause
) {
102 int offset
= data
->clauses
[clause
].offset
;
105 ca
= sheet_cell_get (data
->sheet
,
106 data
->range
->start
.col
+ offset
,
107 data
->range
->start
.row
+ indexa
);
108 cb
= sheet_cell_get (data
->sheet
,
109 data
->range
->start
.col
+ offset
,
110 data
->range
->start
.row
+ indexb
);
112 ca
= sheet_cell_get (data
->sheet
,
113 data
->range
->start
.col
+ indexa
,
114 data
->range
->start
.row
+ offset
);
115 cb
= sheet_cell_get (data
->sheet
,
116 data
->range
->start
.col
+ indexb
,
117 data
->range
->start
.row
+ offset
);
120 result
= sort_compare_cells (ca
, cb
, &(data
->clauses
[clause
]),
128 /* Items are identical; make sort stable by using the indices. */
129 return indexa
- indexb
;
133 sort_qsort_compare (void const *_a
, void const *_b
)
135 SortDataPerm
const *a
= (SortDataPerm
const *)_a
;
136 SortDataPerm
const *b
= (SortDataPerm
const *)_b
;
138 return sort_compare_sets (a
->data
, a
->index
, b
->index
, TRUE
);
142 sort_qsort_compare_in_locale (void const *_a
, void const *_b
)
144 SortDataPerm
const *a
= (SortDataPerm
const *)_a
;
145 SortDataPerm
const *b
= (SortDataPerm
const *)_b
;
147 return sort_compare_sets (a
->data
, a
->index
, b
->index
, FALSE
);
152 sort_permute_range (GnmSortData
const *data
, GnmRange
*range
, int adj
)
155 range
->start
.row
= data
->range
->start
.row
+ adj
;
156 range
->start
.col
= data
->range
->start
.col
;
157 range
->end
.row
= range
->start
.row
;
158 range
->end
.col
= data
->range
->end
.col
;
160 range
->start
.row
= data
->range
->start
.row
;
161 range
->start
.col
= data
->range
->start
.col
+ adj
;
162 range
->end
.row
= data
->range
->end
.row
;
163 range
->end
.col
= range
->start
.col
;
168 gnm_sort_permute_invert (int const *perm
, int length
)
172 rperm
= g_new (int, length
);
173 for (i
= 0; i
< length
; i
++)
183 sort_permute (GnmSortData
*data
, int const *perm
, int length
,
189 pt
.sheet
= data
->sheet
;
190 pt
.paste_flags
= PASTE_CONTENTS
| PASTE_COMMENTS
| PASTE_NO_RECALC
;
191 if (!data
->retain_formats
)
192 pt
.paste_flags
= pt
.paste_flags
| PASTE_FORMATS
;
195 g_printerr ("Permutation:");
196 for (i
= 0; i
< length
; i
++)
197 g_printerr (" %d", perm
[i
]);
201 rperm
= gnm_sort_permute_invert (perm
, length
);
203 for (i
= 0; i
< length
; i
++) {
204 GnmRange range1
, range2
;
205 GnmCellRegion
*rcopy1
, *rcopy2
= NULL
;
208 /* Special case: element is already in place. */
211 g_printerr (" Fixpoint: %d\n", i
);
216 /* Track a full cycle. */
217 sort_permute_range (data
, &range1
, i
);
218 rcopy1
= clipboard_copy_range (data
->sheet
, &range1
);
221 g_printerr (" Cycle:");
226 g_printerr (" %d", i1
);
231 sort_permute_range (data
, &range2
, i2
);
233 /* Don't copy the start of the loop; we did that above. */
234 rcopy2
= clipboard_copy_range (data
->sheet
, &range2
);
238 clipboard_paste_region (rcopy1
, &pt
, cc
);
239 cellregion_unref (rcopy1
);
241 /* This is one step behind. */
257 gnm_sort_position (GnmSortData
*data
, int *perm
, GOCmdContext
*cc
)
261 length
= gnm_sort_data_length (data
);
262 sort_permute (data
, perm
, length
, cc
);
266 gnm_sort_contents (GnmSortData
*data
, GOCmdContext
*cc
)
268 ColRowInfo
const *cra
;
270 int length
, real_length
, i
, cur
, *iperm
, *real
;
271 int const first
= data
->top
? data
->range
->start
.row
: data
->range
->start
.col
;
273 length
= gnm_sort_data_length (data
);
276 /* Discern the rows/cols to be actually sorted */
277 real
= g_new (int, length
);
278 for (i
= 0; i
< length
; i
++) {
280 ? sheet_row_get (data
->sheet
, first
+ i
)
281 : sheet_col_get (data
->sheet
, first
+ i
);
283 if (cra
&& !cra
->visible
) {
292 perm
= g_new (SortDataPerm
, real_length
);
293 for (i
= 0; i
< length
; i
++) {
296 perm
[cur
].data
= data
;
301 if (real_length
> 1) {
304 = g_strdup (go_setlocale (LC_ALL
, NULL
));
305 go_setlocale (LC_ALL
, data
->locale
);
307 qsort (perm
, real_length
, sizeof (SortDataPerm
),
309 (old_locale
, data
->locale
)
311 : sort_qsort_compare_in_locale
);
313 go_setlocale (LC_ALL
, old_locale
);
316 qsort (perm
, real_length
, sizeof (SortDataPerm
),
321 iperm
= g_new (int, length
);
322 for (i
= 0; i
< length
; i
++) {
324 iperm
[i
] = perm
[cur
].index
;
333 sort_permute (data
, iperm
, length
, cc
);
335 /* Make up for the PASTE_NO_RECALC. */
336 sheet_region_queue_recalc (data
->sheet
, data
->range
);
337 sheet_flag_status_update_range (data
->sheet
, data
->range
);
338 sheet_range_calc_spans (data
->sheet
, data
->range
,
339 data
->retain_formats
? GNM_SPANCALC_RENDER
: GNM_SPANCALC_RE_RENDER
);
340 sheet_redraw_all (data
->sheet
, FALSE
);
347 gnm_sort_data_copy (GnmSortData
*data
)
351 g_return_val_if_fail (data
!= NULL
, NULL
);
353 result
= g_memdup (data
, sizeof (GnmSortData
));
354 result
->range
= g_memdup (result
->range
, sizeof (GnmRange
));
355 result
->clauses
= g_memdup (result
->clauses
,
356 result
->num_clause
* sizeof (GnmSortClause
));
357 result
->locale
= g_strdup (result
->locale
);
363 gnm_sort_data_get_type (void)
368 t
= g_boxed_type_register_static ("GnmSortData",
369 (GBoxedCopyFunc
)gnm_sort_data_copy
,
370 (GBoxedFreeFunc
)gnm_sort_data_destroy
);