src/sort.c

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