src/ranges.c

   1 /* vim: set sw=8: -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
   2 /*
   3  * ranges.c: various functions for common operations on cell ranges.
   4  *
   5  * Author:
   6  *   Jody Goldberg   (jody@gnome.org)
   7  *   Miguel de Icaza (miguel@gnu.org).
   8  *   Michael Meeks   (mmeeks@gnu.org).
   9  * Copyright (C) 2007-2009 Morten Welinder (terra@gnome.org)
  10  */
  11 #include <gnumeric-config.h>
  12 #include "gnumeric.h"
  13 #include "ranges.h"
  14
  15 #include "commands.h"
  16 #include "numbers.h"
  17 #include "expr.h"
  18 #include "expr-impl.h"
  19 #include "expr-name.h"
  20 #include "sheet.h"
  21 #include "sheet-style.h"
  22 #include "parse-util.h"
  23 #include "value.h"
  24 #include "cell.h"
  25 #include "style.h"
  26 #include "workbook.h"
  27 #include "gnumeric-conf.h"
  28
  29 #include <stdlib.h>
  30 #include <glib.h>
  31 #include <glib/gi18n-lib.h>
  32 #include <string.h>
  33
  34 #undef RANGE_DEBUG
  35 #define UNICODE_ELLIPSIS "\xe2\x80\xa6"
  36
  37 /**
  38  * range_init_full_sheet:
  39  * @r: #GnmRange
  40  * @sheet: #Sheet
  41  *
  42  * Updates @r to fill @sheet in its entirety.
  43  *
  44  * Returns: (transfer none): @r
  45  */
  46 GnmRange *
  47 range_init_full_sheet (GnmRange *r, Sheet const *sheet)
  48 {
  49         r->start.col = 0;
  50         r->start.row = 0;
  51         r->end.col = gnm_sheet_get_last_col (sheet);
  52         r->end.row = gnm_sheet_get_last_row (sheet);
  53         return r;
  54 }
  55
  56 /**
  57  * range_init_cols:
  58  * @r: #GnmRange
  59  * @sheet: #Sheet
  60  * @start_col: Starting column
  61  * @end_col: Ending column
  62  *
  63  * Updates @r to span full columns @start_col through @end_col completely.
  64  *
  65  * Returns: (transfer none): @r
  66  */
  67 GnmRange *
  68 range_init_cols (GnmRange *r, Sheet const *sheet, int start_col, int end_col)
  69 {
  70         r->start.col = start_col;
  71         r->start.row = 0;
  72         r->end.col = end_col;
  73         r->end.row = gnm_sheet_get_last_row (sheet);
  74         return r;
  75 }
  76
  77 /**
  78  * range_init_rows:
  79  * @r: #GnmRange
  80  * @sheet: #Sheet
  81  * @start_row: Starting row
  82  * @end_row: Ending row
  83  *
  84  * Updates @r to span full rows @start_row through @end_row completely.
  85  *
  86  * Returns: (transfer none): @r
  87  */
  88 GnmRange *
  89 range_init_rows (GnmRange *r, Sheet const *sheet, int start_row, int end_row)
  90 {
  91         r->start.col = 0;
  92         r->start.row = start_row;
  93         r->end.col = gnm_sheet_get_last_col (sheet);
  94         r->end.row = end_row;
  95         return r;
  96 }
  97
  98 /**
  99  * range_init_invalid: (skip)
 100  * @r: #GnmRange
 101  *
 102  * Updates @r to a meaningless range
 103  *
 104  * Returns: (transfer none): @r
 105  */
 106 GnmRange *
 107 range_init_invalid (GnmRange *r)
 108 {
 109         r->start.col = -1;
 110         r->start.row = -1;
 111         r->end.col = -2;
 112         r->end.row = -2;
 113         return r;
 114 }
 115
 116 /**
 117  * range_init_rangeref:
 118  * @r: #GnmRange
 119  * @rr: #GnmRangeRef
 120  *
 121  * Updates @r to be the same as the range part of @rr.
 122  *
 123  * Returns: (transfer none): @r
 124  */
 125 GnmRange *
 126 range_init_rangeref (GnmRange *range, GnmRangeRef const *rr)
 127 {
 128         g_return_val_if_fail (range != NULL && rr != NULL, NULL);
 129
 130         range->start.col = rr->a.col;
 131         range->start.row = rr->a.row;
 132         range->end.col   = rr->b.col;
 133         range->end.row   = rr->b.row;
 134         return range;
 135 }
 136
 137
 138 /**
 139  * range_init_value:
 140  * @r: A #GnmRange to change
 141  * @v: A #GnmValue containing a cell range
 142  *
 143  * Updates @r to be the same as the cell range of @v.
 144  *
 145  * Returns: (transfer none) (nullable): @r
 146  */
 147 GnmRange *
 148 range_init_value (GnmRange *range, GnmValue const *v)
 149 {
 150         g_return_val_if_fail (range != NULL, NULL);
 151         g_return_val_if_fail (v != NULL && VALUE_IS_CELLRANGE (v), NULL);
 152
 153         return range_init_rangeref (range, &v->v_range.cell);
 154 }
 155
 156 /**
 157  * range_init_cellpos:
 158  * @r: A #GnmRange to change
 159  * @pos: A #GnmCellPos
 160  *
 161  * Updates @r to be the singleton range of @pos
 162  *
 163  * Returns: (transfer none): @r
 164  */
 165 GnmRange *
 166 range_init_cellpos (GnmRange *r, GnmCellPos const *pos)
 167 {
 168         r->start = *pos;
 169         r->end = *pos;
 170
 171         return r;
 172 }
 173
 174 /**
 175  * range_init_cellpos_size:
 176  * @r: A #GnmRange to change
 177  * @start: A #GnmCellPos for the upper left corner of the desired range
 178  * @cols: number of columns
 179  * @rows: number of rows
 180  *
 181  * Updates @r to start at @start and spanning @cols columns and @rows rows.
 182  *
 183  * Returns: (transfer none): @r
 184  */
 185 GnmRange *
 186 range_init_cellpos_size (GnmRange *r,
 187                          GnmCellPos const *start, int cols, int rows)
 188 {
 189         r->start = *start;
 190         r->end.col = start->col + cols - 1;
 191         r->end.row = start->row + rows - 1;
 192
 193         return r;
 194 }
 195
 196 /**
 197  * range_init:
 198  * @r: A #GnmRange to change
 199  * @start_col: Column
 200  * @start_row: Row
 201  * @end_col: Column
 202  * @end_row: Row
 203  *
 204  * Updates @r to start at (@start_col,@start_row) and end
 205  * at (@end_col,@end_row).
 206  *
 207  * Returns: (transfer none): @r
 208  */
 209 GnmRange *
 210 range_init (GnmRange *r, int start_col, int start_row,
 211             int end_col, int end_row)
 212 {
 213         g_return_val_if_fail (r != NULL, r);
 214
 215         r->start.col = start_col;
 216         r->start.row = start_row;
 217         r->end.col   = end_col;
 218         r->end.row   = end_row;
 219
 220         return r;
 221 }
 222
 223 /**
 224  * range_parse:
 225  * @r: #GnmRange
 226  * @text: text to parse
 227  * @ss: #GnmSheetSize describing the size of the sheet in which @r lives.
 228  *
 229  * Parse a simple range (no abs/rel refs, no sheet refs)
 230  * Store the result in @r.
 231  *
 232  * Returns: %TRUE on success.
 233  **/
 234 gboolean
 235 range_parse (GnmRange *r, char const *text, GnmSheetSize const *ss)
 236 {
 237         text = cellpos_parse (text, ss, &r->start, FALSE);
 238         if (!text)
 239                 return FALSE;
 240
 241         if (*text == '\0') {
 242                 r->end = r->start;
 243                 return TRUE;
 244         }
 245
 246         if (*text != ':')
 247                 return FALSE;
 248
 249         text = cellpos_parse (text + 1, ss, &r->end, TRUE);
 250         return text != NULL;
 251 }
 252
 253 /**
 254  * range_list_destroy:
 255  * @ranges: (element-type GnmValue) (transfer full): a list of value ranges
 256  * to destroy.
 257  *
 258  * Destroys a list of ranges returned from parse_cell_range_list
 259  **/
 260 void
 261 range_list_destroy (GSList *ranges)
 262 {
 263         GSList *l;
 264
 265         for (l = ranges; l; l = l->next){
 266                 GnmValue *value = l->data;
 267
 268                 value_release (value);
 269         }
 270         g_slist_free (ranges);
 271 }
 272
 273
 274 /**
 275  * range_as_string:
 276  * @r: A #GnmRange
 277  *
 278  * Returns: (transfer none): a string repesentation of @src
 279  **/
 280 char const *
 281 range_as_string (GnmRange const *r)
 282 {
 283         static char buffer[(6 + 4 * sizeof (long)) * 2 + 1];
 284
 285         g_return_val_if_fail (r != NULL, "");
 286
 287         sprintf (buffer, "%s%s",
 288                  col_name (r->start.col), row_name (r->start.row));
 289
 290         if (r->start.col != r->end.col || r->start.row != r->end.row)
 291                 sprintf (buffer + strlen(buffer), ":%s%s",
 292                          col_name (r->end.col), row_name (r->end.row));
 293
 294         return buffer;
 295 }
 296
 297 void
 298 range_dump (GnmRange const *src, char const *suffix)
 299 {
 300         /*
 301          * keep these as 2 print statements, because
 302          * col_name and row_name use a static buffer
 303          */
 304         g_printerr ("%s%s",
 305                 col_name (src->start.col),
 306                 row_name (src->start.row));
 307
 308         if (src->start.col != src->end.col ||
 309             src->start.row != src->end.row)
 310                 g_printerr (":%s%s",
 311                         col_name (src->end.col),
 312                         row_name (src->end.row));
 313         g_printerr ("%s", suffix);
 314 }
 315
 316 #ifdef RANGE_DEBUG
 317 static void
 318 ranges_dump (GList *l, char const *txt)
 319 {
 320         g_printerr ("%s: ", txt);
 321         for (; l; l = l->next) {
 322                 range_dump (l->data, "");
 323                 if (l->next)
 324                         g_printerr (", ");
 325         }
 326         g_printerr ("\n");
 327 }
 328 #endif
 329
 330 /**
 331  * range_contained:
 332  * @a:
 333  * @b:
 334  *
 335  * Is @a totaly contained by @b
 336  *
 337  * Return value:
 338  **/
 339 gboolean
 340 range_contained (GnmRange const *a, GnmRange const *b)
 341 {
 342         if (a->start.row < b->start.row)
 343                 return FALSE;
 344
 345         if (a->end.row > b->end.row)
 346                 return FALSE;
 347
 348         if (a->start.col < b->start.col)
 349                 return FALSE;
 350
 351         if (a->end.col > b->end.col)
 352                 return FALSE;
 353
 354         return TRUE;
 355 }
 356
 357 /**
 358  * range_split_ranges:
 359  * @hard: The region that is split against
 360  * @soft: The region that is split
 361  *
 362  * Splits soft into several chunks, and returns the still
 363  * overlapping remainder of soft as the first list item
 364  * ( the central region in the pathalogical case ).
 365  *
 366  * Returns: (element-type GnmRange) (transfer full): A list of fragments.
 367  **/
 368 GSList *
 369 range_split_ranges (GnmRange const *hard, GnmRange const *soft)
 370 {
 371         /*
 372          * There are lots of cases so think carefully.
 373          *
 374          * Original Methodology ( approximately )
 375          *      a) Get a vertex: is it contained ?
 376          *      b) Yes: split so it isn't
 377          *      c) Continue for all verticees.
 378          *
 379          * NB. We prefer to have long columns at the expense
 380          *     of long rows.
 381          */
 382         GSList *split  = NULL;
 383         GnmRange *middle, *sp;
 384         gboolean split_left  = FALSE;
 385         gboolean split_right = FALSE;
 386
 387         g_return_val_if_fail (range_overlap (hard, soft), NULL);
 388
 389         middle = g_new (GnmRange, 1);
 390         *middle = *soft;
 391
 392         /* Split off left entirely */
 393         if (hard->start.col > soft->start.col) {
 394                 sp = g_new (GnmRange, 1);
 395                 sp->start.col = soft->start.col;
 396                 sp->start.row = soft->start.row;
 397                 sp->end.col   = hard->start.col - 1;
 398                 sp->end.row   = soft->end.row;
 399                 split = g_slist_prepend (split, sp);
 400
 401                 middle->start.col = hard->start.col;
 402                 split_left = TRUE;
 403         } /* else shared edge */
 404
 405         /* Split off right entirely */
 406         if (hard->end.col < soft->end.col) {
 407                 sp = g_new (GnmRange, 1);
 408                 sp->start.col = hard->end.col + 1;
 409                 sp->start.row = soft->start.row;
 410                 sp->end.col   = soft->end.col;
 411                 sp->end.row   = soft->end.row;
 412                 split = g_slist_prepend (split, sp);
 413
 414                 middle->end.col = hard->end.col;
 415                 split_right = TRUE;
 416         }  /* else shared edge */
 417
 418         /* Top */
 419         if (split_left && split_right) {
 420                 if (hard->start.row > soft->start.row) {
 421                         /* The top middle bit */
 422                         sp = g_new (GnmRange, 1);
 423                         sp->start.col = hard->start.col;
 424                         sp->start.row = soft->start.row;
 425                         sp->end.col   = hard->end.col;
 426                         sp->end.row   = hard->start.row - 1;
 427                         split = g_slist_prepend (split, sp);
 428
 429                         middle->start.row = hard->start.row;
 430                 } /* else shared edge */
 431         } else if (split_left) {
 432                 if (hard->start.row > soft->start.row) {
 433                         /* The top middle + right bits */
 434                         sp = g_new (GnmRange, 1);
 435                         sp->start.col = hard->start.col;
 436                         sp->start.row = soft->start.row;
 437                         sp->end.col   = soft->end.col;
 438                         sp->end.row   = hard->start.row - 1;
 439                         split = g_slist_prepend (split, sp);
 440
 441                         middle->start.row = hard->start.row;
 442                 } /* else shared edge */
 443         } else if (split_right) {
 444                 if (hard->start.row > soft->start.row) {
 445                         /* The top middle + left bits */
 446                         sp = g_new (GnmRange, 1);
 447                         sp->start.col = soft->start.col;
 448                         sp->start.row = soft->start.row;
 449                         sp->end.col   = hard->end.col;
 450                         sp->end.row   = hard->start.row - 1;
 451                         split = g_slist_prepend (split, sp);
 452
 453                         middle->start.row = hard->start.row;
 454                 } /* else shared edge */
 455         } else {
 456                 if (hard->start.row > soft->start.row) {
 457                         /* Hack off the top bit */
 458                         sp = g_new (GnmRange, 1);
 459                         sp->start.col = soft->start.col;
 460                         sp->start.row = soft->start.row;
 461                         sp->end.col   = soft->end.col;
 462                         sp->end.row   = hard->start.row - 1;
 463                         split = g_slist_prepend (split, sp);
 464
 465                         middle->start.row = hard->start.row;
 466                 } /* else shared edge */
 467         }
 468
 469         /* Bottom */
 470         if (split_left && split_right) {
 471                 if (hard->end.row < soft->end.row) {
 472                         /* The bottom middle bit */
 473                         sp = g_new (GnmRange, 1);
 474                         sp->start.col = hard->start.col;
 475                         sp->start.row = hard->end.row + 1;
 476                         sp->end.col   = hard->end.col;
 477                         sp->end.row   = soft->end.row;
 478                         split = g_slist_prepend (split, sp);
 479
 480                         middle->end.row = hard->end.row;
 481                 } /* else shared edge */
 482         } else if (split_left) {
 483                 if (hard->end.row < soft->end.row) {
 484                         /* The bottom middle + right bits */
 485                         sp = g_new (GnmRange, 1);
 486                         sp->start.col = hard->start.col;
 487                         sp->start.row = hard->end.row + 1;
 488                         sp->end.col   = soft->end.col;
 489                         sp->end.row   = soft->end.row;
 490                         split = g_slist_prepend (split, sp);
 491
 492                         middle->end.row = hard->end.row;
 493                 } /* else shared edge */
 494         } else if (split_right) {
 495                 if (hard->end.row < soft->end.row) {
 496                         /* The bottom middle + left bits */
 497                         sp = g_new (GnmRange, 1);
 498                         sp->start.col = soft->start.col;
 499                         sp->start.row = hard->end.row + 1;
 500                         sp->end.col   = hard->end.col;
 501                         sp->end.row   = soft->end.row;
 502                         split = g_slist_prepend (split, sp);
 503
 504                         middle->end.row = hard->end.row;
 505                 } /* else shared edge */
 506         } else {
 507                 if (hard->end.row < soft->end.row) {
 508                         /* Hack off the bottom bit */
 509                         sp = g_new (GnmRange, 1);
 510                         sp->start.col = soft->start.col;
 511                         sp->start.row = hard->end.row + 1;
 512                         sp->end.col   = soft->end.col;
 513                         sp->end.row   = soft->end.row;
 514                         split = g_slist_prepend (split, sp);
 515
 516                         middle->end.row = hard->end.row;
 517                 } /* else shared edge */
 518         }
 519
 520         return g_slist_prepend (split, middle);
 521 }
 522
 523 /**
 524  * gnm_range_dup:
 525  * @r: Source range to copy
 526  *
 527  * Copies the @r range.
 528  *
 529  * Returns: (transfer full): A copy of the GnmRange.
 530  **/
 531 GnmRange *
 532 gnm_range_dup (GnmRange const *a)
 533 {
 534         GnmRange *r = g_new (GnmRange, 1);
 535         *r = *a;
 536         return r;
 537 }
 538
 539 /**
 540  * range_fragment:
 541  * @a: #GnmRange a
 542  * @b: #GnmRange b
 543  *
 544  * Fragments the ranges into totaly non-overlapping regions,
 545  *
 546  * Returns: (element-type GnmRange) (transfer full): A list of fragmented
 547  * ranges or at minimum simply a and b.
 548  **/
 549 GSList *
 550 range_fragment (GnmRange const *a, GnmRange const *b)
 551 {
 552         GSList *split, *ans = NULL;
 553
 554         split = range_split_ranges (a, b);
 555         ans   = g_slist_concat (ans, split);
 556
 557         split = range_split_ranges (b, a);
 558         if (split) {
 559                 g_free (split->data);
 560                 split = g_slist_remove (split, split->data);
 561         }
 562         ans = g_slist_concat (ans, split);
 563
 564         return ans;
 565 }
 566
 567 /**
 568  * range_intersection:
 569  * @r: intersection range
 570  * @a: range a
 571  * @b: range b
 572  *
 573  * This computes the intersection of two ranges; on a Venn
 574  * diagram this would be A (upside down U) B.
 575  * If the ranges do not intersect, false is returned an the
 576  * values of r are unpredictable.
 577  *
 578  * NB. totally commutative
 579  *
 580  * Return value: %TRUE if the ranges intersect, %FALSE otherwise
 581  **/
 582 gboolean
 583 range_intersection (GnmRange *r, GnmRange const *a, GnmRange const *b)
 584 {
 585         if (!range_overlap (a, b)) {
 586                 *r = *a; // Something
 587                 return FALSE;
 588         }
 589
 590         r->start.col = MAX (a->start.col, b->start.col);
 591         r->start.row = MAX (a->start.row, b->start.row);
 592
 593         r->end.col = MIN (a->end.col, b->end.col);
 594         r->end.row = MIN (a->end.row, b->end.row);
 595
 596         return TRUE;
 597 }
 598
 599 /**
 600  * range_normalize:
 601  * @src: a range
 602  *
 603  * Ensures that start <= end for rows and cols.
 604  **/
 605 void
 606 range_normalize (GnmRange *src)
 607 {
 608         int tmp;
 609
 610         tmp = src->end.col;
 611         if (src->start.col > tmp) {
 612                 src->end.col = src->start.col;
 613                 src->start.col = tmp;
 614         }
 615         tmp = src->end.row;
 616         if (src->start.row > tmp) {
 617                 src->end.row = src->start.row;
 618                 src->start.row = tmp;
 619         }
 620 }
 621
 622 /**
 623  * range_union:
 624  * @a: range a
 625  * @b: range b
 626  *
 627  * This computes the union; on a Venn
 628  * diagram this would be A U B
 629  * NB. totally commutative. Also, this may
 630  * include cells not in either range since
 631  * it must return a GnmRange.
 632  *
 633  * Return value: the union
 634  **/
 635 GnmRange
 636 range_union (GnmRange const *a, GnmRange const *b)
 637 {
 638         GnmRange ans;
 639
 640         if (a->start.col < b->start.col)
 641                 ans.start.col = a->start.col;
 642         else
 643                 ans.start.col = b->start.col;
 644
 645         if (a->end.col > b->end.col)
 646                 ans.end.col   = a->end.col;
 647         else
 648                 ans.end.col   = b->end.col;
 649
 650         if (a->start.row < b->start.row)
 651                 ans.start.row = a->start.row;
 652         else
 653                 ans.start.row = b->start.row;
 654
 655         if (a->end.row > b->end.row)
 656                 ans.end.row   = a->end.row;
 657         else
 658                 ans.end.row   = b->end.row;
 659
 660         return ans;
 661 }
 662
 663 /**
 664  * range_is_singleton:
 665  * @r: the range.
 666  *
 667  * Returns: %TRUE if @r is a single-cell range.
 668  */
 669 gboolean
 670 range_is_singleton (GnmRange const *r)
 671 {
 672         return r->start.col == r->end.col && r->start.row == r->end.row;
 673 }
 674
 675 /**
 676  * range_is_full:
 677  * @r: the range.
 678  * @sheet: the sheet in which @r lives
 679  * @horiz: %TRUE to check for a horizontal full ref (_cols_ [0..MAX))
 680  *
 681  * This determines whether @r completely spans a sheet
 682  * in the dimension specified by @horiz.
 683  *
 684  * Return value: %TRUE if it is infinite else %FALSE.
 685  **/
 686 gboolean
 687 range_is_full (GnmRange const *r, Sheet const *sheet, gboolean horiz)
 688 {
 689         if (horiz)
 690                 return (r->start.col <= 0 &&
 691                         r->end.col >= gnm_sheet_get_last_col (sheet));
 692         else
 693                 return (r->start.row <= 0 &&
 694                         r->end.row >= gnm_sheet_get_last_row (sheet));
 695 }
 696
 697 /**
 698  * range_clip_to_finite:
 699  * @range:
 700  * @sheet: the sheet in which @range lives
 701  *
 702  * Clip the range to the area of the sheet with content.
 703  * if the range reaches the edge
 704  *
 705  * The idea here is that users may select a whole column or row when they
 706  * really are only concerned with the extent of the sheet.
 707  * On the otehr hand, if users select any smaller region they probably
 708  * intend to selec tjust that.
 709  *
 710  * WARNING THIS IS EXPENSIVE!
 711  **/
 712 void
 713 range_clip_to_finite (GnmRange *range, Sheet *sheet)
 714 {
 715         GnmRange extent;
 716
 717         /* FIXME : This seems expensive.  We should see if there is a faster
 718          * way of doing this.  possibly using a flag for content changes, and
 719          * using the current values as a cache
 720          */
 721         extent = sheet_get_extent (sheet, FALSE, TRUE);
 722         if (range->end.col >= gnm_sheet_get_max_cols (sheet) - 1)
 723                 range->end.col = extent.end.col;
 724         if (range->end.row >= gnm_sheet_get_max_rows (sheet) - 1)
 725                 range->end.row = extent.end.row;
 726 }
 727
 728 int
 729 range_width (GnmRange const *r)
 730 {
 731         g_return_val_if_fail (r != NULL, 0);
 732         return ABS (r->end.col - r->start.col) + 1;
 733 }
 734
 735 int
 736 range_height (GnmRange const *r)
 737 {
 738         g_return_val_if_fail (r != NULL, 0);
 739         return ABS (r->end.row - r->start.row) + 1;
 740 }
 741
 742 /**
 743  * range_translate:
 744  * @range:
 745  * @sheet: the sheet in which @range lives
 746  * @col_offset:
 747  * @row_offset:
 748  *
 749  * Translate the range and return TRUE if it is invalidated.
 750  *
 751  * return TRUE if the range is no longer valid.
 752  **/
 753 gboolean
 754 range_translate (GnmRange *range, Sheet const *sheet, int col_offset, int row_offset)
 755 {
 756         /*
 757          * FIXME: we should probably check for overflow without actually
 758          * performing it.
 759          */
 760         range->start.col += col_offset;
 761         range->end.col   += col_offset;
 762         range->start.row += row_offset;
 763         range->end.row   += row_offset;
 764
 765         /* check for completely out of bounds */
 766         if (range->start.col >= gnm_sheet_get_max_cols (sheet) || range->start.col < 0 ||
 767             range->start.row >= gnm_sheet_get_max_rows (sheet) || range->start.row < 0 ||
 768             range->end.col >= gnm_sheet_get_max_cols (sheet) || range->end.col < 0 ||
 769             range->end.row >= gnm_sheet_get_max_rows (sheet) || range->end.row < 0)
 770                 return TRUE;
 771
 772         return FALSE;
 773 }
 774
 775 /**
 776  * range_ensure_sanity:
 777  * @range: the range to check
 778  * @sheet: the sheet in which @range lives
 779  *
 780  * Silently clip a range to ensure that it does not contain areas
 781  * outside the valid bounds.  Does NOT fix inverted ranges.
 782  **/
 783 void
 784 range_ensure_sanity (GnmRange *range, Sheet const *sheet)
 785 {
 786         range->start.col = MAX (0, range->start.col);
 787         range->end.col = MIN (range->end.col, gnm_sheet_get_last_col (sheet));
 788
 789         range->start.row = MAX (0, range->start.row);
 790         range->end.row = MIN (range->end.row, gnm_sheet_get_last_row (sheet));
 791 }
 792
 793 /**
 794  * range_is_sane:
 795  * @range: the range to check
 796  *
 797  * Generate warnings if the range is out of bounds or inverted.
 798  **/
 799 gboolean
 800 range_is_sane (GnmRange const *range)
 801 {
 802         g_return_val_if_fail (range != NULL, FALSE);
 803         g_return_val_if_fail (range->start.col >= 0, FALSE);
 804         g_return_val_if_fail (range->end.col >= range->start.col, FALSE);
 805         g_return_val_if_fail (range->end.col <= G_MAXINT / 2, FALSE);
 806         g_return_val_if_fail (range->start.row >= 0, FALSE);
 807         g_return_val_if_fail (range->end.row >= range->start.row, FALSE);
 808         g_return_val_if_fail (range->end.row <= G_MAXINT / 2, FALSE);
 809
 810         return TRUE;
 811 }
 812
 813 /**
 814  * range_transpose:
 815  * @range: The range.
 816  * @sheet: the sheet in which @range lives
 817  * @origin: The box to transpose inside
 818  *
 819  * Effectively mirrors the ranges in 'boundary' around a
 820  * leading diagonal projected from offset.
 821  *
 822  * Return value: whether we clipped the range.
 823  **/
 824 gboolean
 825 range_transpose (GnmRange *range, Sheet const *sheet, GnmCellPos const *origin)
 826 {
 827         gboolean clipped = FALSE;
 828         GnmRange src;
 829         int t;
 830         int last_col = gnm_sheet_get_last_col (sheet);
 831         int last_row = gnm_sheet_get_last_row (sheet);
 832
 833         g_return_val_if_fail (range != NULL, TRUE);
 834
 835         src = *range;
 836
 837         /* Start col */
 838         t = origin->col + (src.start.row - origin->row);
 839         if (t > last_col) {
 840                 clipped = TRUE;
 841                 range->start.col = last_col;
 842         } else if (t < 0) {
 843                 clipped = TRUE;
 844                 range->start.col = 0;
 845         }
 846                 range->start.col = t;
 847
 848         /* Start row */
 849         t = origin->row + (src.start.col - origin->col);
 850         if (t > last_row) {
 851                 clipped = TRUE;
 852                 range->start.row = last_row;
 853         } else if (t < 0) {
 854                 clipped = TRUE;
 855                 range->start.row = 0;
 856         }
 857                 range->start.row = t;
 858
 859
 860         /* End col */
 861         t = origin->col + (src.end.row - origin->row);
 862         if (t > last_col) {
 863                 clipped = TRUE;
 864                 range->end.col = last_col;
 865         } else if (t < 0) {
 866                 clipped = TRUE;
 867                 range->end.col = 0;
 868         }
 869                 range->end.col = t;
 870
 871         /* End row */
 872         t = origin->row + (src.end.col - origin->col);
 873         if (t > last_row) {
 874                 clipped = TRUE;
 875                 range->end.row = last_row;
 876         } else if (t < 0) {
 877                 clipped = TRUE;
 878                 range->end.row = 0;
 879         }
 880                 range->end.row = t;
 881
 882         g_assert (range_valid (range));
 883
 884         return clipped;
 885 }
 886
 887 gboolean
 888 gnm_range_equal (const GnmRange *a, const GnmRange *b)
 889 {
 890         return range_equal (a, b);
 891 }
 892
 893 /**
 894  * gnm_range_compare:
 895  * @a: first range
 896  * @b: second range
 897  *
 898  * Returns: a value that is negative if range @a comes before range @b;
 899  * zero if the two ranges are equal; positive if range @a comes after
 900  * range @b.  The order imposed is lexicographical by starting row,
 901  * then column, then ending row, then column.
 902  */
 903 int
 904 gnm_range_compare (GnmRange const *a, GnmRange const *b)
 905 {
 906         int i = 0;
 907         if (!i) i = a->start.row - b->start.row;
 908         if (!i) i = a->start.col - b->start.col;
 909         if (!i) i = a->end.row - b->end.row;
 910         if (!i) i = a->end.col - b->end.col;
 911         return i;
 912 }
 913
 914
 915 GnmSheetRange *
 916 gnm_sheet_range_new (Sheet *sheet, GnmRange const *r)
 917 {
 918         GnmSheetRange *gr;
 919
 920         g_return_val_if_fail (IS_SHEET (sheet), NULL);
 921         g_return_val_if_fail (r != NULL, NULL);
 922
 923         gr = g_new0 (GnmSheetRange, 1);
 924         gr->sheet = sheet;
 925         gr->range = *r;
 926
 927         return gr;
 928 }
 929
 930 GnmSheetRange *
 931 gnm_sheet_range_dup (GnmSheetRange const *sr)
 932 {
 933         g_return_val_if_fail (sr != NULL, NULL);
 934         return gnm_sheet_range_new (sr->sheet, &sr->range);
 935 }
 936
 937 /**
 938  * gnm_sheet_range_from_value:
 939  * @r: #GnmSheetRange to change
 940  * @v: #GnmValue containing a cell range.
 941  *
 942  * Convert @v into a GnmSheetRange.
 943  *
 944  * Returns: %TRUE
 945  **/
 946 gboolean
 947 gnm_sheet_range_from_value (GnmSheetRange *r, GnmValue const *v)
 948 {
 949         g_return_val_if_fail (VALUE_IS_CELLRANGE (v), FALSE);
 950
 951         r->sheet = v->v_range.cell.a.sheet;
 952         range_init_value (&r->range, v);
 953
 954         return TRUE;
 955 }
 956
 957 void
 958 gnm_sheet_range_free (GnmSheetRange *gr)
 959 {
 960         g_free (gr);
 961 }
 962
 963 GType
 964 gnm_sheet_range_get_type (void)
 965 {
 966         static GType t = 0;
 967
 968         if (t == 0)
 969                 t = g_boxed_type_register_static ("GnmSheetRange",
 970                          (GBoxedCopyFunc)gnm_sheet_range_dup,
 971                          (GBoxedFreeFunc)gnm_sheet_range_free);
 972         return t;
 973 }
 974
 975 gboolean
 976 gnm_sheet_range_equal (const GnmSheetRange *a,
 977                        const GnmSheetRange *b)
 978 {
 979         return a->sheet == b->sheet && range_equal (&a->range, &b->range);
 980 }
 981
 982 gboolean
 983 gnm_sheet_range_overlap (GnmSheetRange const *a, GnmSheetRange const *b)
 984 {
 985         g_return_val_if_fail (a != NULL, FALSE);
 986         g_return_val_if_fail (b != NULL, FALSE);
 987
 988         if (a->sheet == b->sheet && range_overlap (&a->range, &b->range))
 989                 return TRUE;
 990
 991         return FALSE;
 992 }
 993
 994 char *
 995 global_range_name (Sheet const *sheet, GnmRange const *r)
 996 {
 997         char const * the_range_name = range_as_string (r);
 998
 999         if (sheet == NULL)
1000                 return g_strdup (the_range_name);
1001
1002         return g_strdup_printf ("%s!%s", sheet->name_quoted, the_range_name);
1003 }
1004
1005 /**
1006  * undo_cell_pos_name:
1007  * @sheet:
1008  * @pos:
1009  *
1010  * Returns the range name depending on the preference setting.
1011  **/
1012 char *
1013 undo_cell_pos_name (Sheet const *sheet, GnmCellPos const *pos)
1014 {
1015         GnmRange r;
1016         r.end = r.start = *pos;
1017         return undo_range_name (sheet, &r);
1018 }
1019
1020 /**
1021  * undo_range_name:
1022  * @sheet:
1023  * @r:
1024  *
1025  * Returns the range name depending on the preference setting.
1026  **/
1027 char *
1028 undo_range_name (Sheet const *sheet, GnmRange const *r)
1029 {
1030         char const *the_range_name = range_as_string (r);
1031
1032         if (sheet != NULL && gnm_conf_get_undo_show_sheet_name ()) {
1033                 GString *str  = g_string_new (NULL);
1034                 gboolean truncated = FALSE;
1035
1036                 g_string_printf (str, "%s!%s", sheet->name_quoted, the_range_name);
1037                 gnm_cmd_trunc_descriptor (str, &truncated);
1038
1039                 if (!truncated)
1040                         return g_string_free (str, FALSE);
1041
1042                 g_string_printf (str, UNICODE_ELLIPSIS "!%s", the_range_name);
1043                 gnm_cmd_trunc_descriptor (str, &truncated);
1044
1045                 if (!truncated)
1046                         return g_string_free (str, FALSE);
1047                 g_string_free (str, TRUE);
1048         }
1049
1050         return g_string_free
1051                 (gnm_cmd_trunc_descriptor (g_string_new (the_range_name), NULL), FALSE);
1052 }
1053
1054
1055 /*
1056  * Create range list name, but don't exceed max_width.
1057  * Return TRUE iff the name is complete.
1058  */
1059 static gboolean
1060 range_list_name_try (GString *names, char const *sheet, GSList const *ranges)
1061 {
1062         GSList const *l;
1063         char const *n = range_as_string (ranges->data);
1064         gboolean truncated;
1065
1066         if (sheet == NULL)
1067                 g_string_assign (names, n);
1068         else
1069                 g_string_printf (names, "%s!%s", sheet, n);
1070
1071         gnm_cmd_trunc_descriptor (names, &truncated);
1072
1073         if (truncated)
1074                 return FALSE;
1075
1076         for (l = ranges->next; l != NULL; l = l->next) {
1077                 n = range_as_string (l->data);
1078
1079                 if (sheet == NULL)
1080                         g_string_append_printf (names, ", %s", n);
1081                 else
1082                         g_string_append_printf (names, ", %s!%s",
1083                                                 sheet, n);
1084
1085                 gnm_cmd_trunc_descriptor (names, &truncated);
1086
1087                 if (truncated)
1088                         return FALSE;
1089         }
1090
1091         /* Have we reached the end? */
1092         return TRUE;
1093 }
1094
1095
1096 /**
1097  * undo_range_list_name:
1098  * @sheet:
1099  * @ranges: (element-type GnmRange): GSList containing GnmRange *'s
1100  *
1101  * Returns the range list name depending on the preference setting.
1102  * (The result will be something like: "A1:C3, D4:E5"). The string will be
1103  * truncated to max_descriptor_width.
1104  **/
1105 char *
1106 undo_range_list_name (Sheet const *sheet, GSList const *ranges)
1107 {
1108         GString *names_with_sheet = NULL, *names_with_ellipsis, *names;
1109
1110         g_return_val_if_fail (ranges != NULL, NULL);
1111
1112         /* With the sheet name. */
1113         if (sheet != NULL && gnm_conf_get_undo_show_sheet_name ()) {
1114                 names_with_sheet = g_string_new (NULL);
1115                 if (range_list_name_try (names_with_sheet, sheet->name_quoted, ranges)) {
1116                         /* We have reached the end, return the data from names. */
1117                         return g_string_free (names_with_sheet, FALSE);
1118                 }
1119                 names_with_ellipsis = g_string_new (NULL);
1120                 if (range_list_name_try (names_with_ellipsis, UNICODE_ELLIPSIS, ranges)) {
1121                         /* We have reached the end, return the data from names. */
1122                         g_string_free (names_with_sheet, TRUE);
1123                         return g_string_free (names_with_ellipsis, FALSE);
1124                 }
1125                 g_string_free (names_with_ellipsis, TRUE);
1126         }
1127
1128         /* Without the sheet name. */
1129         names = g_string_new (NULL);
1130         if (range_list_name_try (names, NULL, ranges)) {
1131                 /* We have reached the end, return the data from names. */
1132                 if (names_with_sheet != NULL)
1133                         g_string_free (names_with_sheet, TRUE);
1134                 return g_string_free (names, FALSE);
1135         }
1136
1137         /* We have to use a truncated version. */
1138         if (names_with_sheet != NULL) {
1139                 g_string_free (names, TRUE);
1140                 return g_string_free (names_with_sheet, FALSE);
1141         }
1142         return g_string_free (names, FALSE);
1143 }
1144
1145 /**
1146  * global_range_list_parse:
1147  * @sheet: Sheet where the range specification is relatively parsed to
1148  * @str: a range or list of ranges to parse (ex: "A1", "A1:B1,C2,Sheet2!D2:D4")
1149  *
1150  * Parses a list of ranges, relative to the @sheet and returns a list with the
1151  * results.
1152  *
1153  * Returns: (element-type GnmValue) (transfer full): a #GSList of #GnmValue.
1154  **/
1155 GSList *
1156 global_range_list_parse (Sheet *sheet, char const *str)
1157 {
1158         GnmParsePos  pp;
1159         GnmExprTop const *texpr;
1160         GSList   *ranges = NULL;
1161         GnmValue         *v;
1162
1163         g_return_val_if_fail (IS_SHEET (sheet), NULL);
1164         g_return_val_if_fail (str != NULL, NULL);
1165
1166         texpr = gnm_expr_parse_str (str,
1167                  parse_pos_init_sheet (&pp, sheet),
1168                  GNM_EXPR_PARSE_FORCE_EXPLICIT_SHEET_REFERENCES |
1169                  GNM_EXPR_PARSE_PERMIT_MULTIPLE_EXPRESSIONS |
1170                  GNM_EXPR_PARSE_UNKNOWN_NAMES_ARE_STRINGS,
1171                  NULL, NULL);
1172
1173         if (texpr != NULL)  {
1174                 if (GNM_EXPR_GET_OPER (texpr->expr) == GNM_EXPR_OP_SET) {
1175                         GnmExpr const *expr = texpr->expr;
1176                         int i;
1177                         for (i = 0; i < expr->set.argc; i++) {
1178                                 v = gnm_expr_get_range (expr->set.argv[i]);
1179                                 if (v == NULL) {
1180                                         range_list_destroy (ranges);
1181                                         ranges = NULL;
1182                                         break;
1183                                 } else
1184                                         ranges = g_slist_prepend (ranges, v);
1185                         }
1186                 } else {
1187                         v = gnm_expr_top_get_range (texpr);
1188                         if (v != NULL)
1189                                 ranges = g_slist_prepend (ranges, v);
1190                 }
1191                 gnm_expr_top_unref (texpr);
1192         }
1193
1194         return g_slist_reverse (ranges);
1195 }
1196
1197 /**
1198  * global_range_list_foreach:
1199  * @gr_list: (element-type GnmRange): list of ranges.
1200  * @ep:
1201  * @flags:
1202  * @handler: (scope call):
1203  * @closure: user data.
1204  *
1205  * Returns: (transfer none):
1206  **/
1207 GnmValue *
1208 global_range_list_foreach (GSList *gr_list, GnmEvalPos const *ep,
1209                            CellIterFlags flags,
1210                            CellIterFunc  handler,
1211                            gpointer      closure)
1212 {
1213         GnmValue *v;
1214         for (; gr_list != NULL; gr_list = gr_list->next) {
1215                 v = workbook_foreach_cell_in_range (ep, gr_list->data,
1216                         flags, handler, closure);
1217                 if (v != NULL)
1218                         return v;
1219         }
1220
1221         return NULL;
1222 }
1223
1224
1225 /**
1226  * global_range_contained:
1227  * @sheet: The calling context #Sheet for references with sheet==NULL
1228  * @a:
1229  * @b:
1230  *
1231  * return true if a is contained in b
1232  * we do not handle 3d ranges
1233  **/
1234 gboolean
1235 global_range_contained (Sheet const *sheet, GnmValue const *a, GnmValue const *b)
1236 {
1237         Sheet const *target;
1238
1239         g_return_val_if_fail (a != NULL, FALSE);
1240         g_return_val_if_fail (b != NULL, FALSE);
1241
1242         if (!VALUE_IS_CELLRANGE (a) || !VALUE_IS_CELLRANGE (b))
1243                 return FALSE;
1244
1245         target = eval_sheet (a->v_range.cell.a.sheet, sheet);
1246         if (target != eval_sheet (a->v_range.cell.b.sheet, sheet))
1247                 return FALSE;
1248
1249         if (target != eval_sheet (b->v_range.cell.a.sheet, sheet) ||
1250             target != eval_sheet (b->v_range.cell.b.sheet, sheet))
1251                 return FALSE;
1252
1253         if (a->v_range.cell.a.row < b->v_range.cell.a.row)
1254                 return FALSE;
1255
1256         if (a->v_range.cell.b.row > b->v_range.cell.b.row)
1257                 return FALSE;
1258
1259         if (a->v_range.cell.a.col < b->v_range.cell.a.col)
1260                 return FALSE;
1261
1262         if (a->v_range.cell.b.col > b->v_range.cell.b.col)
1263                 return FALSE;
1264
1265         return TRUE;
1266 }
1267
1268 GType
1269 gnm_range_get_type (void)
1270 {
1271         static GType t = 0;
1272
1273         if (t == 0)
1274                 t = g_boxed_type_register_static ("GnmRange",
1275                          (GBoxedCopyFunc)gnm_range_dup,
1276                          (GBoxedFreeFunc)g_free);
1277         return t;
1278 }