1 /*
2 * This program is free software; you can redistribute it and/or modify it
3 * under the terms of the GNU Lesser General Public License as published by
4 * the Free Software Foundation.
5 *
6 * This program is distributed in the hope that it will be useful, but
7 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
8 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
9 * for more details.
10 *
11 * You should have received a copy of the GNU Lesser General Public License
12 * along with this program; if not, see <http://www.gnu.org/licenses/>.
13 *
14 *
15 * Authors:
16 * Chris Lahey <clahey@ximian.com>
17 *
18 * Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
19 *
20 */
21
22 #include "evolution-config.h"
23
24 #include "e-table-sorting-utils.h"
25
26 #include <string.h>
27 #include <camel/camel.h>
28
29 #include "e-misc-utils.h"
30
31 #define d(x)
32
33 /* This takes source rows. */
34 static gint
etsu_compare(ETableModel * source,ETableSortInfo * sort_info,ETableHeader * full_header,gint row1,gint row2,gpointer cmp_cache)35 etsu_compare (ETableModel *source,
36 ETableSortInfo *sort_info,
37 ETableHeader *full_header,
38 gint row1,
39 gint row2,
40 gpointer cmp_cache)
41 {
42 gint j;
43 gint sort_count = e_table_sort_info_sorting_get_count (sort_info);
44 gint comp_val = 0;
45 GtkSortType sort_type = GTK_SORT_ASCENDING;
46
47 for (j = 0; j < sort_count; j++) {
48 ETableColumnSpecification *spec;
49 ETableCol *col;
50 gpointer value1, value2;
51
52 spec = e_table_sort_info_sorting_get_nth (
53 sort_info, j, &sort_type);
54
55 col = e_table_header_get_column_by_spec (full_header, spec);
56 if (col == NULL) {
57 gint last = e_table_header_count (full_header) - 1;
58 col = e_table_header_get_column (full_header, last);
59 }
60
61 value1 = e_table_model_value_at (source, col->spec->compare_col, row1);
62 value2 = e_table_model_value_at (source, col->spec->compare_col, row2);
63
64 comp_val = (*col->compare) (value1, value2, cmp_cache);
65
66 e_table_model_free_value (source, col->spec->compare_col, value1);
67 e_table_model_free_value (source, col->spec->compare_col, value2);
68
69 if (comp_val != 0)
70 break;
71 }
72
73 if (comp_val == 0) {
74 if (row1 < row2)
75 comp_val = -1;
76 if (row1 > row2)
77 comp_val = 1;
78 }
79
80 if (sort_type == GTK_SORT_DESCENDING)
81 comp_val = -comp_val;
82
83 return comp_val;
84 }
85
86 typedef struct {
87 gint cols;
88 gpointer *vals;
89 GtkSortType *sort_type;
90 GCompareDataFunc *compare;
91 gpointer cmp_cache;
92 } ETableSortClosure;
93
94 typedef struct {
95 ETreeModel *tree;
96 ETableSortInfo *sort_info;
97 ETableHeader *full_header;
98 gpointer cmp_cache;
99 } ETreeSortClosure;
100
101 /* FIXME: Make it not cache the second and later columns (as if anyone cares.) */
102
103 static gint
e_sort_callback(gconstpointer data1,gconstpointer data2,gpointer user_data)104 e_sort_callback (gconstpointer data1,
105 gconstpointer data2,
106 gpointer user_data)
107 {
108 gint row1 = *(gint *) data1;
109 gint row2 = *(gint *) data2;
110 ETableSortClosure *closure = user_data;
111 gint j;
112 gint sort_count = closure->cols;
113 gint comp_val = 0;
114 GtkSortType sort_type = GTK_SORT_ASCENDING;
115
116 for (j = 0; j < sort_count; j++) {
117 comp_val = (*(closure->compare[j])) (
118 closure->vals[closure->cols * row1 + j],
119 closure->vals[closure->cols * row2 + j],
120 closure->cmp_cache);
121 sort_type = closure->sort_type[j];
122 if (comp_val != 0)
123 break;
124 }
125 if (comp_val == 0) {
126 if (row1 < row2)
127 comp_val = -1;
128 if (row1 > row2)
129 comp_val = 1;
130 }
131
132 if (sort_type == GTK_SORT_DESCENDING)
133 comp_val = -comp_val;
134
135 return comp_val;
136 }
137
138 void
e_table_sorting_utils_sort(ETableModel * source,ETableSortInfo * sort_info,ETableHeader * full_header,gint * map_table,gint rows)139 e_table_sorting_utils_sort (ETableModel *source,
140 ETableSortInfo *sort_info,
141 ETableHeader *full_header,
142 gint *map_table,
143 gint rows)
144 {
145 gint total_rows;
146 gint i;
147 gint j;
148 gint cols;
149 ETableSortClosure closure;
150
151 g_return_if_fail (E_IS_TABLE_MODEL (source));
152 g_return_if_fail (E_IS_TABLE_SORT_INFO (sort_info));
153 g_return_if_fail (E_IS_TABLE_HEADER (full_header));
154
155 total_rows = e_table_model_row_count (source);
156 cols = e_table_sort_info_sorting_get_count (sort_info);
157 closure.cols = cols;
158
159 closure.vals = g_new (gpointer, total_rows * cols);
160 closure.sort_type = g_new (GtkSortType, cols);
161 closure.compare = g_new (GCompareDataFunc, cols);
162 closure.cmp_cache = e_table_sorting_utils_create_cmp_cache ();
163
164 for (j = 0; j < cols; j++) {
165 ETableColumnSpecification *spec;
166 ETableCol *col;
167
168 spec = e_table_sort_info_sorting_get_nth (
169 sort_info, j, &closure.sort_type[j]);
170
171 col = e_table_header_get_column_by_spec (full_header, spec);
172 if (col == NULL) {
173 gint last = e_table_header_count (full_header) - 1;
174 col = e_table_header_get_column (full_header, last);
175 }
176
177 for (i = 0; i < rows; i++) {
178 closure.vals[map_table[i] * cols + j] = e_table_model_value_at (source, col->spec->compare_col, map_table[i]);
179 }
180 closure.compare[j] = col->compare;
181 }
182
183 g_qsort_with_data (
184 map_table, rows, sizeof (gint), e_sort_callback, &closure);
185
186 for (j = 0; j < cols; j++) {
187 ETableColumnSpecification *spec;
188 ETableCol *col;
189
190 spec = e_table_sort_info_sorting_get_nth (
191 sort_info, j, &closure.sort_type[j]);
192
193 col = e_table_header_get_column_by_spec (full_header, spec);
194 if (col == NULL) {
195 gint last = e_table_header_count (full_header) - 1;
196 col = e_table_header_get_column (full_header, last);
197 }
198
199 for (i = 0; i < rows; i++) {
200 e_table_model_free_value (source, col->spec->compare_col, closure.vals[map_table[i] * cols + j]);
201 }
202 }
203
204 g_free (closure.vals);
205 g_free (closure.sort_type);
206 g_free (closure.compare);
207 e_table_sorting_utils_free_cmp_cache (closure.cmp_cache);
208 }
209
210 gboolean
e_table_sorting_utils_affects_sort(ETableSortInfo * sort_info,ETableHeader * full_header,gint compare_col)211 e_table_sorting_utils_affects_sort (ETableSortInfo *sort_info,
212 ETableHeader *full_header,
213 gint compare_col)
214 {
215 gint j;
216 gint cols;
217
218 g_return_val_if_fail (E_IS_TABLE_SORT_INFO (sort_info), TRUE);
219 g_return_val_if_fail (E_IS_TABLE_HEADER (full_header), TRUE);
220
221 cols = e_table_sort_info_sorting_get_count (sort_info);
222
223 for (j = 0; j < cols; j++) {
224 ETableColumnSpecification *spec;
225 ETableCol *col;
226
227 spec = e_table_sort_info_sorting_get_nth (
228 sort_info, j, NULL);
229
230 col = e_table_header_get_column_by_spec (full_header, spec);
231 if (col == NULL) {
232 gint last = e_table_header_count (full_header) - 1;
233 col = e_table_header_get_column (full_header, last);
234 }
235
236 if (compare_col == col->spec->compare_col)
237 return TRUE;
238 }
239
240 return FALSE;
241 }
242
243 /* FIXME: This could be done in time log n instead of time n with a binary search. */
244 gint
e_table_sorting_utils_insert(ETableModel * source,ETableSortInfo * sort_info,ETableHeader * full_header,gint * map_table,gint rows,gint row)245 e_table_sorting_utils_insert (ETableModel *source,
246 ETableSortInfo *sort_info,
247 ETableHeader *full_header,
248 gint *map_table,
249 gint rows,
250 gint row)
251 {
252 gint i;
253 gpointer cmp_cache = e_table_sorting_utils_create_cmp_cache ();
254
255 i = 0;
256 /* handle insertions when we have a 'sort group' */
257 while (i < rows && etsu_compare (source, sort_info, full_header, map_table[i], row, cmp_cache) < 0)
258 i++;
259
260 e_table_sorting_utils_free_cmp_cache (cmp_cache);
261
262 return i;
263 }
264
265 /* FIXME: This could be done in time log n instead of time n with a binary search. */
266 gint
e_table_sorting_utils_check_position(ETableModel * source,ETableSortInfo * sort_info,ETableHeader * full_header,gint * map_table,gint rows,gint view_row)267 e_table_sorting_utils_check_position (ETableModel *source,
268 ETableSortInfo *sort_info,
269 ETableHeader *full_header,
270 gint *map_table,
271 gint rows,
272 gint view_row)
273 {
274 gint i;
275 gint row;
276 gpointer cmp_cache;
277
278 i = view_row;
279 row = map_table[i];
280 cmp_cache = e_table_sorting_utils_create_cmp_cache ();
281
282 i = view_row;
283 if (i < rows - 1 && etsu_compare (source, sort_info, full_header, map_table[i + 1], row, cmp_cache) < 0) {
284 i++;
285 while (i < rows - 1 && etsu_compare (source, sort_info, full_header, map_table[i], row, cmp_cache) < 0)
286 i++;
287 } else if (i > 0 && etsu_compare (source, sort_info, full_header, map_table[i - 1], row, cmp_cache) > 0) {
288 i--;
289 while (i > 0 && etsu_compare (source, sort_info, full_header, map_table[i], row, cmp_cache) > 0)
290 i--;
291 }
292
293 e_table_sorting_utils_free_cmp_cache (cmp_cache);
294
295 return i;
296 }
297
298 /* This takes source rows. */
299 static gint
etsu_tree_compare(ETreeModel * source,ETableSortInfo * sort_info,ETableHeader * full_header,ETreePath path1,ETreePath path2,gpointer cmp_cache)300 etsu_tree_compare (ETreeModel *source,
301 ETableSortInfo *sort_info,
302 ETableHeader *full_header,
303 ETreePath path1,
304 ETreePath path2,
305 gpointer cmp_cache)
306 {
307 gint j;
308 gint sort_count = e_table_sort_info_sorting_get_count (sort_info);
309 gint comp_val = 0;
310 GtkSortType sort_type = GTK_SORT_ASCENDING;
311
312 for (j = 0; j < sort_count; j++) {
313 ETableColumnSpecification *spec;
314 ETableCol *col;
315
316 spec = e_table_sort_info_sorting_get_nth (
317 sort_info, j, &sort_type);
318
319 col = e_table_header_get_column_by_spec (full_header, spec);
320 if (col == NULL) {
321 gint last = e_table_header_count (full_header) - 1;
322 col = e_table_header_get_column (full_header, last);
323 }
324
325 comp_val = (*col->compare) (
326 e_tree_model_value_at (
327 source, path1, col->spec->compare_col),
328 e_tree_model_value_at (
329 source, path2, col->spec->compare_col),
330 cmp_cache);
331 if (comp_val != 0)
332 break;
333 }
334
335 if (sort_type == GTK_SORT_DESCENDING)
336 comp_val = -comp_val;
337
338 return comp_val;
339 }
340
341 static gint
e_sort_tree_callback(gconstpointer data1,gconstpointer data2,gpointer user_data)342 e_sort_tree_callback (gconstpointer data1,
343 gconstpointer data2,
344 gpointer user_data)
345 {
346 ETreePath *path1 = *(ETreePath *) data1;
347 ETreePath *path2 = *(ETreePath *) data2;
348 ETreeSortClosure *closure = user_data;
349
350 return etsu_tree_compare (closure->tree, closure->sort_info, closure->full_header, path1, path2, closure->cmp_cache);
351 }
352
353 void
e_table_sorting_utils_tree_sort(ETreeModel * source,ETableSortInfo * sort_info,ETableHeader * full_header,ETreePath * map_table,gint count)354 e_table_sorting_utils_tree_sort (ETreeModel *source,
355 ETableSortInfo *sort_info,
356 ETableHeader *full_header,
357 ETreePath *map_table,
358 gint count)
359 {
360 ETableSortClosure closure;
361 gint cols;
362 gint i, j;
363 gint *map;
364 ETreePath *map_copy;
365
366 g_return_if_fail (E_IS_TREE_MODEL (source));
367 g_return_if_fail (E_IS_TABLE_SORT_INFO (sort_info));
368 g_return_if_fail (E_IS_TABLE_HEADER (full_header));
369
370 cols = e_table_sort_info_sorting_get_count (sort_info);
371 closure.cols = cols;
372
373 closure.vals = g_new (gpointer , count * cols);
374 closure.sort_type = g_new (GtkSortType, cols);
375 closure.compare = g_new (GCompareDataFunc, cols);
376 closure.cmp_cache = e_table_sorting_utils_create_cmp_cache ();
377
378 for (j = 0; j < cols; j++) {
379 ETableColumnSpecification *spec;
380 ETableCol *col;
381
382 spec = e_table_sort_info_sorting_get_nth (
383 sort_info, j, &closure.sort_type[j]);
384
385 col = e_table_header_get_column_by_spec (full_header, spec);
386 if (col == NULL) {
387 gint last = e_table_header_count (full_header) - 1;
388 col = e_table_header_get_column (full_header, last);
389 }
390
391 for (i = 0; i < count; i++) {
392 closure.vals[i * cols + j] = e_tree_model_sort_value_at (source, map_table[i], col->spec->compare_col);
393 }
394 closure.compare[j] = col->compare;
395 }
396
397 map = g_new (int, count);
398 for (i = 0; i < count; i++) {
399 map[i] = i;
400 }
401
402 g_qsort_with_data (
403 map, count, sizeof (gint), e_sort_callback, &closure);
404
405 map_copy = g_new (ETreePath, count);
406 for (i = 0; i < count; i++) {
407 map_copy[i] = map_table[i];
408 }
409 for (i = 0; i < count; i++) {
410 map_table[i] = map_copy[map[i]];
411 }
412
413 for (j = 0; j < cols; j++) {
414 ETableColumnSpecification *spec;
415 ETableCol *col;
416
417 spec = e_table_sort_info_sorting_get_nth (
418 sort_info, j, &closure.sort_type[j]);
419
420 col = e_table_header_get_column_by_spec (full_header, spec);
421 if (col == NULL) {
422 gint last = e_table_header_count (full_header) - 1;
423 col = e_table_header_get_column (full_header, last);
424 }
425
426 for (i = 0; i < count; i++) {
427 e_tree_model_free_value (source, col->spec->compare_col, closure.vals[i * cols + j]);
428 }
429 }
430
431 g_free (map);
432 g_free (map_copy);
433
434 g_free (closure.vals);
435 g_free (closure.sort_type);
436 g_free (closure.compare);
437 e_table_sorting_utils_free_cmp_cache (closure.cmp_cache);
438 }
439
440 /* FIXME: This could be done in time log n instead of time n with a binary search. */
441 gint
e_table_sorting_utils_tree_check_position(ETreeModel * source,ETableSortInfo * sort_info,ETableHeader * full_header,ETreePath * map_table,gint count,gint old_index)442 e_table_sorting_utils_tree_check_position (ETreeModel *source,
443 ETableSortInfo *sort_info,
444 ETableHeader *full_header,
445 ETreePath *map_table,
446 gint count,
447 gint old_index)
448 {
449 gint i;
450 ETreePath path;
451 gpointer cmp_cache = e_table_sorting_utils_create_cmp_cache ();
452
453 i = old_index;
454 path = map_table[i];
455
456 if (i < count - 1 && etsu_tree_compare (source, sort_info, full_header, map_table[i + 1], path, cmp_cache) < 0) {
457 i++;
458 while (i < count - 1 && etsu_tree_compare (source, sort_info, full_header, map_table[i], path, cmp_cache) < 0)
459 i++;
460 } else if (i > 0 && etsu_tree_compare (source, sort_info, full_header, map_table[i - 1], path, cmp_cache) > 0) {
461 i--;
462 while (i > 0 && etsu_tree_compare (source, sort_info, full_header, map_table[i], path, cmp_cache) > 0)
463 i--;
464 }
465
466 e_table_sorting_utils_free_cmp_cache (cmp_cache);
467
468 return i;
469 }
470
471 /* FIXME: This does not pay attention to making sure that it's a stable insert. This needs to be fixed. */
472 gint
e_table_sorting_utils_tree_insert(ETreeModel * source,ETableSortInfo * sort_info,ETableHeader * full_header,ETreePath * map_table,gint count,ETreePath path)473 e_table_sorting_utils_tree_insert (ETreeModel *source,
474 ETableSortInfo *sort_info,
475 ETableHeader *full_header,
476 ETreePath *map_table,
477 gint count,
478 ETreePath path)
479 {
480 gsize start;
481 gsize end;
482 ETreeSortClosure closure;
483
484 closure.tree = source;
485 closure.sort_info = sort_info;
486 closure.full_header = full_header;
487 closure.cmp_cache = e_table_sorting_utils_create_cmp_cache ();
488
489 e_bsearch (
490 &path, map_table, count, sizeof (ETreePath),
491 e_sort_tree_callback, &closure, &start, &end);
492
493 e_table_sorting_utils_free_cmp_cache (closure.cmp_cache);
494
495 return end;
496 }
497
498 /**
499 * e_table_sorting_utils_create_cmp_cache:
500 *
501 * Creates a new compare cache, which is storing pairs of string keys and
502 * string values. This can be accessed by
503 * e_table_sorting_utils_lookup_cmp_cache() and
504 * e_table_sorting_utils_add_to_cmp_cache().
505 *
506 * Returned pointer should be freed with
507 * e_table_sorting_utils_free_cmp_cache().
508 **/
509 gpointer
e_table_sorting_utils_create_cmp_cache(void)510 e_table_sorting_utils_create_cmp_cache (void)
511 {
512 return g_hash_table_new_full (
513 (GHashFunc) g_str_hash,
514 (GEqualFunc) g_str_equal,
515 (GDestroyNotify) camel_pstring_free,
516 (GDestroyNotify) g_free);
517 }
518
519 /**
520 * e_table_sorting_utils_free_cmp_cache:
521 * @cmp_cache: a compare cache; cannot be %NULL
522 *
523 * Frees a compare cache previously created with
524 * e_table_sorting_utils_create_cmp_cache().
525 **/
526 void
e_table_sorting_utils_free_cmp_cache(gpointer cmp_cache)527 e_table_sorting_utils_free_cmp_cache (gpointer cmp_cache)
528 {
529 g_return_if_fail (cmp_cache != NULL);
530
531 g_hash_table_destroy (cmp_cache);
532 }
533
534 /**
535 * e_table_sorting_utils_add_to_cmp_cache:
536 * @cmp_cache: a compare cache; cannot be %NULL
537 * @key: unique key to a cache; cannot be %NULL
538 * @value: value to store for a key
539 *
540 * Adds a new value for a given key to a compare cache. If such key
541 * already exists in a cache then its value will be replaced.
542 * Note: Given @value will be stolen and later freed with g_free.
543 **/
544 void
e_table_sorting_utils_add_to_cmp_cache(gpointer cmp_cache,const gchar * key,gchar * value)545 e_table_sorting_utils_add_to_cmp_cache (gpointer cmp_cache,
546 const gchar *key,
547 gchar *value)
548 {
549 g_return_if_fail (cmp_cache != NULL);
550 g_return_if_fail (key != NULL);
551
552 g_hash_table_insert (
553 cmp_cache, (gchar *) camel_pstring_strdup (key), value);
554 }
555
556 /**
557 * e_table_sorting_utils_lookup_cmp_cache:
558 * @cmp_cache: a compare cache
559 * @key: unique key to a cache
560 *
561 * Looks ups @key in @cmp_cache, which is passed in GCompareDataFunc as 'data'.
562 * Returns %NULL when not found or the cache wasn't provided.
563 **/
564 const gchar *
e_table_sorting_utils_lookup_cmp_cache(gpointer cmp_cache,const gchar * key)565 e_table_sorting_utils_lookup_cmp_cache (gpointer cmp_cache,
566 const gchar *key)
567 {
568 g_return_val_if_fail (key != NULL, NULL);
569
570 if (cmp_cache == NULL)
571 return NULL;
572
573 return g_hash_table_lookup (cmp_cache, key);
574 }
575