sort.c 8.1 KB
Newer Older
1 2
/* vim: set sw=8: -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */

3 4 5 6
/*
 * sort.c : Routines for sorting cell ranges
 *
 * Author:
7
 *	JP Rosevear <jpr@arcavia.com>
8 9
 *
 * (C) 2000 JP Rosevear
Morten Welinder's avatar
Morten Welinder committed
10
 * (C) 2000 Morten Welinder
11
 */
12 13 14 15
#include <gnumeric-config.h>
#include "gnumeric.h"
#include "sort.h"

16
#include "commands.h"
17
#include "clipboard.h"
18
#include "cell.h"
19
#include "value.h"
Jody Goldberg's avatar
Jody Goldberg committed
20
#include "sheet.h"
21
#include "ranges.h"
22
#include <goffice/goffice.h>
23
#include <stdlib.h>
Morten Welinder's avatar
Morten Welinder committed
24 25 26

typedef struct {
	int index;
Jody Goldberg's avatar
Jody Goldberg committed
27
	GnmSortData *data;
Morten Welinder's avatar
Morten Welinder committed
28 29
} SortDataPerm;

30

31 32
/* Data stuff */
void
Morten Welinder's avatar
Morten Welinder committed
33
gnm_sort_data_destroy (GnmSortData *data)
34
{
35
	g_free (data->clauses);
36
	g_free (data->range);
37
	g_free (data->locale);
38 39 40
	g_free (data);
}

41
static int
Morten Welinder's avatar
Morten Welinder committed
42
gnm_sort_data_length (GnmSortData const *data)
Morten Welinder's avatar
Morten Welinder committed
43 44
{
	if (data->top)
45
		return range_height (data->range);
Morten Welinder's avatar
Morten Welinder committed
46
	else
47
		return range_width (data->range);
Morten Welinder's avatar
Morten Welinder committed
48 49
}

50 51
/* The routines to do the sorting */
static int
Morten Welinder's avatar
Morten Welinder committed
52
sort_compare_cells (GnmCell const *ca, GnmCell const *cb,
53
		    GnmSortClause *clause, gboolean default_locale)
54
{
Jody Goldberg's avatar
Jody Goldberg committed
55 56
	GnmValue *a, *b;
	GnmValueType ta, tb;
57
	GnmValDiff comp = IS_EQUAL;
JP Rosevear's avatar
JP Rosevear committed
58
	int ans = 0;
59 60

	if (!ca)
JP Rosevear's avatar
JP Rosevear committed
61
		a = NULL;
62 63 64
	else
		a = ca->value;
	if (!cb)
JP Rosevear's avatar
JP Rosevear committed
65
		b = NULL;
66 67 68
	else
		b = cb->value;

69 70
	ta = VALUE_IS_EMPTY (a) ? VALUE_EMPTY : a->v_any.type;
	tb = VALUE_IS_EMPTY (b) ? VALUE_EMPTY : b->v_any.type;
JP Rosevear's avatar
JP Rosevear committed
71 72 73 74 75 76 77 78 79

	if (ta == VALUE_EMPTY && tb != VALUE_EMPTY) {
		comp = clause->asc ? IS_LESS : IS_GREATER;
	} else if (tb == VALUE_EMPTY && ta != VALUE_EMPTY) {
		comp = clause->asc ? IS_GREATER : IS_LESS;
	} else if (ta == VALUE_ERROR && tb != VALUE_ERROR) {
		comp = IS_GREATER;
	} else if (tb == VALUE_ERROR && ta != VALUE_ERROR) {
		comp = IS_LESS;
80
	} else {
81 82
		comp = default_locale ? value_compare (a, b, clause->cs)
			: value_compare_no_cache (a, b, clause->cs);
JP Rosevear's avatar
JP Rosevear committed
83
	}
84

JP Rosevear's avatar
JP Rosevear committed
85 86 87 88
	if (comp == IS_LESS) {
		ans = clause->asc ?  1 : -1;
	} else if (comp == IS_GREATER) {
		ans = clause->asc ? -1 :  1;
89 90
	}

JP Rosevear's avatar
JP Rosevear committed
91
	return ans;
92 93 94
}

static int
95 96
sort_compare_sets (GnmSortData const *data, int indexa, int indexb,
		   gboolean default_locale)
97
{
98
	GnmCell *ca, *cb;
99 100 101 102 103 104 105
	int clause = 0;

	while (clause < data->num_clause) {
		int result = 0;
		int offset = data->clauses[clause].offset;

		if (data->top) {
106
			ca = sheet_cell_get (data->sheet,
107 108
					     data->range->start.col + offset,
					     data->range->start.row + indexa);
109
			cb = sheet_cell_get (data->sheet,
110 111 112
					     data->range->start.col + offset,
					     data->range->start.row + indexb);
		} else {
113
			ca = sheet_cell_get (data->sheet,
114 115
					     data->range->start.col + indexa,
					     data->range->start.row + offset);
116
			cb = sheet_cell_get (data->sheet,
117 118 119
					     data->range->start.col + indexb,
					     data->range->start.row + offset);
		}
120

121 122
		result = sort_compare_cells (ca, cb, &(data->clauses[clause]),
					     default_locale);
123 124 125
		if (result) {
			return result;
		}
126
		clause++;
127 128
	}

Morten Welinder's avatar
Morten Welinder committed
129 130
	/* Items are identical; make sort stable by using the indices.  */
	return indexa - indexb;
131 132 133
}

static int
134
sort_qsort_compare (void const *_a, void const *_b)
135
{
136 137
	SortDataPerm const *a = (SortDataPerm const *)_a;
	SortDataPerm const *b = (SortDataPerm const *)_b;
138

139 140 141 142 143 144 145 146 147 148
	return sort_compare_sets (a->data, a->index, b->index, TRUE);
}

static int
sort_qsort_compare_in_locale (void const *_a, void const *_b)
{
	SortDataPerm const *a = (SortDataPerm const *)_a;
	SortDataPerm const *b = (SortDataPerm const *)_b;

	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 157 158 159
		range->start.row = data->range->start.row + adj;
		range->start.col = data->range->start.col;
		range->end.row = range->start.row;
		range->end.col = data->range->end.col;
160
	} else {
161 162 163 164
		range->start.row = data->range->start.row;
		range->start.col = data->range->start.col + adj;
		range->end.row = data->range->end.row;
		range->end.col = range->start.col;
165
	}
166
}
167

168
int *
Morten Welinder's avatar
Morten Welinder committed
169
gnm_sort_permute_invert (int const *perm, int length)
170 171 172 173 174 175 176 177 178 179 180
{
	int i, *rperm;

	rperm = g_new (int, length);
	for (i = 0; i < length; i++)
		rperm[perm[i]] = i;

	return rperm;
}


Morten Welinder's avatar
Morten Welinder committed
181 182
#undef DEBUG_SORT

183
static void
184
sort_permute (GnmSortData *data, int const *perm, int length,
185
	      GOCmdContext *cc)
186
{
Morten Welinder's avatar
Morten Welinder committed
187
	int i, *rperm;
Morten Welinder's avatar
Morten Welinder committed
188
	GnmPasteTarget pt;
189

Morten Welinder's avatar
Morten Welinder committed
190
	pt.sheet = data->sheet;
191
	pt.paste_flags = PASTE_CONTENTS | PASTE_COMMENTS | PASTE_NO_RECALC;
192 193
	if (!data->retain_formats)
		pt.paste_flags = pt.paste_flags | PASTE_FORMATS;
194

Morten Welinder's avatar
Morten Welinder committed
195
#ifdef DEBUG_SORT
196
	g_printerr ("Permutation:");
Morten Welinder's avatar
Morten Welinder committed
197
	for (i = 0; i < length; i++)
198 199
		g_printerr (" %d", perm[i]);
	g_printerr ("\n");
Morten Welinder's avatar
Morten Welinder committed
200
#endif
201

Morten Welinder's avatar
Morten Welinder committed
202
	rperm = gnm_sort_permute_invert (perm, length);
203

Morten Welinder's avatar
Morten Welinder committed
204
	for (i = 0; i < length; i++) {
Jody Goldberg's avatar
Jody Goldberg committed
205
		GnmRange range1, range2;
Morten Welinder's avatar
Morten Welinder committed
206
		GnmCellRegion *rcopy1, *rcopy2 = NULL;
Morten Welinder's avatar
Morten Welinder committed
207 208 209 210 211
		int i1, i2;

		/* Special case: element is already in place.  */
		if (i == rperm[i]) {
#ifdef DEBUG_SORT
212
			g_printerr ("  Fixpoint: %d\n", i);
Morten Welinder's avatar
Morten Welinder committed
213 214 215
#endif
			continue;
		}
216

Morten Welinder's avatar
Morten Welinder committed
217 218 219 220 221
		/* Track a full cycle.  */
		sort_permute_range (data, &range1, i);
		rcopy1 = clipboard_copy_range (data->sheet, &range1);

#ifdef DEBUG_SORT
222
		g_printerr ("  Cycle:");
Morten Welinder's avatar
Morten Welinder committed
223 224 225 226
#endif
		i1 = i;
		do {
#ifdef DEBUG_SORT
227
			g_printerr (" %d", i1);
Morten Welinder's avatar
Morten Welinder committed
228 229 230 231 232 233 234 235 236
#endif

			i2 = rperm[i1];

			sort_permute_range (data, &range2, i2);
			if (i2 != i) {
				/* Don't copy the start of the loop; we did that above.  */
				rcopy2 = clipboard_copy_range (data->sheet, &range2);
			}
237

Morten Welinder's avatar
Morten Welinder committed
238
			pt.range = range2;
239
			clipboard_paste_region (rcopy1, &pt, cc);
240
			cellregion_unref (rcopy1);
241

Morten Welinder's avatar
Morten Welinder committed
242 243
			/* This is one step behind.  */
			rperm[i1] = i1;
244

Morten Welinder's avatar
Morten Welinder committed
245 246 247 248 249
			rcopy1 = rcopy2;
			range1 = range2;
			i1 = i2;
		} while (i1 != i);
#ifdef DEBUG_SORT
250
		g_printerr ("\n");
Morten Welinder's avatar
Morten Welinder committed
251
#endif
252
	}
Morten Welinder's avatar
Morten Welinder committed
253 254

	g_free (rperm);
255 256 257
}

void
Morten Welinder's avatar
Morten Welinder committed
258
gnm_sort_position (GnmSortData *data, int *perm, GOCmdContext *cc)
259
{
Morten Welinder's avatar
Morten Welinder committed
260 261
	int length;

Morten Welinder's avatar
Morten Welinder committed
262
	length = gnm_sort_data_length (data);
263
	sort_permute (data, perm, length, cc);
264 265
}

266
int *
Morten Welinder's avatar
Morten Welinder committed
267
gnm_sort_contents (GnmSortData *data, GOCmdContext *cc)
268
{
269
	ColRowInfo const *cra;
Morten Welinder's avatar
Morten Welinder committed
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

Morten Welinder's avatar
Morten Welinder committed
274
	length = gnm_sort_data_length (data);
275
	real_length = 0;
276

277 278 279 280
	/* Discern the rows/cols to be actually sorted */
	real = g_new (int, length);
	for (i = 0; i < length; i++) {
		cra = data->top
281 282
			? sheet_row_get (data->sheet, first + i)
			: sheet_col_get (data->sheet, first + i);
Morten Welinder's avatar
Morten Welinder committed
283

284 285 286 287 288
		if (cra && !cra->visible) {
			real[i] = -1;
		} else {
			real[i] = i;
			real_length++;
289
		}
290
	}
291

292 293
	cur = 0;
	perm = g_new (SortDataPerm, real_length);
294
	for (i = 0; i < length; i++) {
295 296 297 298 299
		if (real[i] != -1) {
			perm[cur].index = i;
			perm[cur].data = data;
			cur++;
		}
300 301
	}

302 303
	if (real_length > 1) {
		if (data->locale) {
Morten Welinder's avatar
Morten Welinder committed
304
			char *old_locale
305
				= g_strdup (go_setlocale (LC_ALL, NULL));
306 307
			go_setlocale (LC_ALL, data->locale);

Morten Welinder's avatar
Morten Welinder committed
308 309 310
			qsort (perm, real_length, sizeof (SortDataPerm),
			       g_str_has_prefix
			       (old_locale, data->locale)
311 312
			       ? sort_qsort_compare
			       : sort_qsort_compare_in_locale);
Morten Welinder's avatar
Morten Welinder committed
313

314 315
			go_setlocale (LC_ALL, old_locale);
			g_free (old_locale);
316
		} else
Morten Welinder's avatar
Morten Welinder committed
317
			qsort (perm, real_length, sizeof (SortDataPerm),
318
			       sort_qsort_compare);
319 320
	}

321
	cur = 0;
Morten Welinder's avatar
Morten Welinder committed
322
	iperm = g_new (int, length);
323 324 325 326 327 328 329 330
	for (i = 0; i < length; i++) {
		if (real[i] != -1) {
			iperm[i] = perm[cur].index;
			cur++;
		} else {
			iperm[i] = i;
		}
	}
Morten Welinder's avatar
Morten Welinder committed
331
	g_free (perm);
332
	g_free (real);
333

334
	sort_permute (data, iperm, length, cc);
335

Morten Welinder's avatar
Morten Welinder committed
336 337 338 339
	/* Make up for the PASTE_NO_RECALC.  */
	sheet_region_queue_recalc (data->sheet, data->range);
	sheet_flag_status_update_range (data->sheet, data->range);
	sheet_range_calc_spans (data->sheet, data->range,
340
				data->retain_formats ? GNM_SPANCALC_RENDER : GNM_SPANCALC_RE_RENDER);
Morten Welinder's avatar
Morten Welinder committed
341 342
	sheet_redraw_all (data->sheet, FALSE);

Morten Welinder's avatar
Morten Welinder committed
343
	return iperm;
344
}
345 346 347 348 349 350


GnmSortData *
gnm_sort_data_copy   (GnmSortData *data)
{
	GnmSortData *result;
Morten Welinder's avatar
Morten Welinder committed
351

352
	g_return_val_if_fail (data != NULL, NULL);
Morten Welinder's avatar
Morten Welinder committed
353

354 355
	result = g_memdup (data, sizeof (GnmSortData));
	result->range = g_memdup (result->range, sizeof (GnmRange));
Morten Welinder's avatar
Morten Welinder committed
356
	result->clauses = g_memdup (result->clauses,
357 358 359 360 361
				    result->num_clause * sizeof (GnmSortClause));
	result->locale = g_strdup (result->locale);

	return result;
}
362 363 364 365 366 367 368 369 370 371 372 373 374

GType
gnm_sort_data_get_type (void)
{
	static GType t = 0;

	if (t == 0) {
		t = g_boxed_type_register_static ("GnmSortData",
			 (GBoxedCopyFunc)gnm_sort_data_copy,
			 (GBoxedFreeFunc)gnm_sort_data_destroy);
	}
	return t;
}