src/sort.c

   1
   2 /*
   3  * sort.c : Routines for sorting cell ranges
   4  *
   5  * Author:
   6  *      JP Rosevear <jpr@arcavia.com>
   7  *
   8  * (C) 2000 JP Rosevear
   9  * (C) 2000 Morten Welinder
  10  */
  11 #include <gnumeric-config.h>
  12 #include <gnumeric.h>
  13 #include <sort.h>
  14
  15 #include <commands.h>
  16 #include <clipboard.h>
  17 #include <cell.h>
  18 #include <value.h>
  19 #include <sheet.h>
  20 #include <ranges.h>
  21 #include <goffice/goffice.h>
  22 #include <stdlib.h>
  23
  24 typedef struct {
  25         int index;
  26         GnmSortData *data;
  27 } SortDataPerm;
  28
  29
  30 /* Data stuff */
  31 void
  32 gnm_sort_data_destroy (GnmSortData *data)
  33 {
  34         g_free (data->clauses);
  35         g_free (data->range);
  36         g_free (data->locale);
  37         g_free (data);
  38 }
  39
  40 static int
  41 gnm_sort_data_length (GnmSortData const *data)
  42 {
  43         if (data->top)
  44                 return range_height (data->range);
  45         else
  46                 return range_width (data->range);
  47 }
  48
  49 /* The routines to do the sorting */
  50 static int
  51 sort_compare_cells (GnmCell const *ca, GnmCell const *cb,
  52                     GnmSortClause *clause, gboolean default_locale)
  53 {
  54         GnmValue *a, *b;
  55         GnmValueType ta, tb;
  56         GnmValDiff comp = IS_EQUAL;
  57         int ans = 0;
  58
  59         if (!ca)
  60                 a = NULL;
  61         else
  62                 a = ca->value;
  63         if (!cb)
  64                 b = NULL;
  65         else
  66                 b = cb->value;
  67
  68         ta = VALUE_IS_EMPTY (a) ? VALUE_EMPTY : a->v_any.type;
  69         tb = VALUE_IS_EMPTY (b) ? VALUE_EMPTY : b->v_any.type;
  70
  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) {
  76                 comp = IS_GREATER;
  77         } else if (tb == VALUE_ERROR && ta != VALUE_ERROR) {
  78                 comp = IS_LESS;
  79         } else {
  80                 comp = default_locale ? value_compare (a, b, clause->cs)
  81                         : value_compare_no_cache (a, b, clause->cs);
  82         }
  83
  84         if (comp == IS_LESS) {
  85                 ans = clause->asc ?  1 : -1;
  86         } else if (comp == IS_GREATER) {
  87                 ans = clause->asc ? -1 :  1;
  88         }
  89
  90         return ans;
  91 }
  92
  93 static int
  94 sort_compare_sets (GnmSortData const *data, int indexa, int indexb,
  95                    gboolean default_locale)
  96 {
  97         GnmCell *ca, *cb;
  98         int clause = 0;
  99
 100         while (clause < data->num_clause) {
 101                 int result = 0;
 102                 int offset = data->clauses[clause].offset;
 103
 104                 if (data->top) {
 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);
 111                 } else {
 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);
 118                 }
 119
 120                 result = sort_compare_cells (ca, cb, &(data->clauses[clause]),
 121                                              default_locale);
 122                 if (result) {
 123                         return result;
 124                 }
 125                 clause++;
 126         }
 127
 128         /* Items are identical; make sort stable by using the indices.  */
 129         return indexa - indexb;
 130 }
 131
 132 static int
 133 sort_qsort_compare (void const *_a, void const *_b)
 134 {
 135         SortDataPerm const *a = (SortDataPerm const *)_a;
 136         SortDataPerm const *b = (SortDataPerm const *)_b;
 137
 138         return sort_compare_sets (a->data, a->index, b->index, TRUE);
 139 }
 140
 141 static int
 142 sort_qsort_compare_in_locale (void const *_a, void const *_b)
 143 {
 144         SortDataPerm const *a = (SortDataPerm const *)_a;
 145         SortDataPerm const *b = (SortDataPerm const *)_b;
 146
 147         return sort_compare_sets (a->data, a->index, b->index, FALSE);
 148 }
 149
 150
 151 static void
 152 sort_permute_range (GnmSortData const *data, GnmRange *range, int adj)
 153 {
 154         if (data->top) {
 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;
 159         } else {
 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;
 164         }
 165 }
 166
 167 int *
 168 gnm_sort_permute_invert (int const *perm, int length)
 169 {
 170         int i, *rperm;
 171
 172         rperm = g_new (int, length);
 173         for (i = 0; i < length; i++)
 174                 rperm[perm[i]] = i;
 175
 176         return rperm;
 177 }
 178
 179
 180 #undef DEBUG_SORT
 181
 182 static void
 183 sort_permute (GnmSortData *data, int const *perm, int length,
 184               GOCmdContext *cc)
 185 {
 186         int i, *rperm;
 187         GnmPasteTarget pt;
 188
 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;
 193
 194 #ifdef DEBUG_SORT
 195         g_printerr ("Permutation:");
 196         for (i = 0; i < length; i++)
 197                 g_printerr (" %d", perm[i]);
 198         g_printerr ("\n");
 199 #endif
 200
 201         rperm = gnm_sort_permute_invert (perm, length);
 202
 203         for (i = 0; i < length; i++) {
 204                 GnmRange range1, range2;
 205                 GnmCellRegion *rcopy1, *rcopy2 = NULL;
 206                 int i1, i2;
 207
 208                 /* Special case: element is already in place.  */
 209                 if (i == rperm[i]) {
 210 #ifdef DEBUG_SORT
 211                         g_printerr ("  Fixpoint: %d\n", i);
 212 #endif
 213                         continue;
 214                 }
 215
 216                 /* Track a full cycle.  */
 217                 sort_permute_range (data, &range1, i);
 218                 rcopy1 = clipboard_copy_range (data->sheet, &range1);
 219
 220 #ifdef DEBUG_SORT
 221                 g_printerr ("  Cycle:");
 222 #endif
 223                 i1 = i;
 224                 do {
 225 #ifdef DEBUG_SORT
 226                         g_printerr (" %d", i1);
 227 #endif
 228
 229                         i2 = rperm[i1];
 230
 231                         sort_permute_range (data, &range2, i2);
 232                         if (i2 != i) {
 233                                 /* Don't copy the start of the loop; we did that above.  */
 234                                 rcopy2 = clipboard_copy_range (data->sheet, &range2);
 235                         }
 236
 237                         pt.range = range2;
 238                         clipboard_paste_region (rcopy1, &pt, cc);
 239                         cellregion_unref (rcopy1);
 240
 241                         /* This is one step behind.  */
 242                         rperm[i1] = i1;
 243
 244                         rcopy1 = rcopy2;
 245                         range1 = range2;
 246                         i1 = i2;
 247                 } while (i1 != i);
 248 #ifdef DEBUG_SORT
 249                 g_printerr ("\n");
 250 #endif
 251         }
 252
 253         g_free (rperm);
 254 }
 255
 256 void
 257 gnm_sort_position (GnmSortData *data, int *perm, GOCmdContext *cc)
 258 {
 259         int length;
 260
 261         length = gnm_sort_data_length (data);
 262         sort_permute (data, perm, length, cc);
 263 }
 264
 265 int *
 266 gnm_sort_contents (GnmSortData *data, GOCmdContext *cc)
 267 {
 268         ColRowInfo const *cra;
 269         SortDataPerm *perm;
 270         int length, real_length, i, cur, *iperm, *real;
 271         int const first = data->top ? data->range->start.row : data->range->start.col;
 272
 273         length = gnm_sort_data_length (data);
 274         real_length = 0;
 275
 276         /* Discern the rows/cols to be actually sorted */
 277         real = g_new (int, length);
 278         for (i = 0; i < length; i++) {
 279                 cra = data->top
 280                         ? sheet_row_get (data->sheet, first + i)
 281                         : sheet_col_get (data->sheet, first + i);
 282
 283                 if (cra && !cra->visible) {
 284                         real[i] = -1;
 285                 } else {
 286                         real[i] = i;
 287                         real_length++;
 288                 }
 289         }
 290
 291         cur = 0;
 292         perm = g_new (SortDataPerm, real_length);
 293         for (i = 0; i < length; i++) {
 294                 if (real[i] != -1) {
 295                         perm[cur].index = i;
 296                         perm[cur].data = data;
 297                         cur++;
 298                 }
 299         }
 300
 301         if (real_length > 1) {
 302                 if (data->locale) {
 303                         char *old_locale
 304                                 = g_strdup (go_setlocale (LC_ALL, NULL));
 305                         go_setlocale (LC_ALL, data->locale);
 306
 307                         qsort (perm, real_length, sizeof (SortDataPerm),
 308                                g_str_has_prefix
 309                                (old_locale, data->locale)
 310                                ? sort_qsort_compare
 311                                : sort_qsort_compare_in_locale);
 312
 313                         go_setlocale (LC_ALL, old_locale);
 314                         g_free (old_locale);
 315                 } else
 316                         qsort (perm, real_length, sizeof (SortDataPerm),
 317                                sort_qsort_compare);
 318         }
 319
 320         cur = 0;
 321         iperm = g_new (int, length);
 322         for (i = 0; i < length; i++) {
 323                 if (real[i] != -1) {
 324                         iperm[i] = perm[cur].index;
 325                         cur++;
 326                 } else {
 327                         iperm[i] = i;
 328                 }
 329         }
 330         g_free (perm);
 331         g_free (real);
 332
 333         sort_permute (data, iperm, length, cc);
 334
 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);
 341
 342         return iperm;
 343 }
 344
 345
 346 GnmSortData *
 347 gnm_sort_data_copy   (GnmSortData *data)
 348 {
 349         GnmSortData *result;
 350
 351         g_return_val_if_fail (data != NULL, NULL);
 352
 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);
 358
 359         return result;
 360 }
 361
 362 GType
 363 gnm_sort_data_get_type (void)
 364 {
 365         static GType t = 0;
 366
 367         if (t == 0) {
 368                 t = g_boxed_type_register_static ("GnmSortData",
 369                          (GBoxedCopyFunc)gnm_sort_data_copy,
 370                          (GBoxedFreeFunc)gnm_sort_data_destroy);
 371         }
 372         return t;
 373 }