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