src/ranges.c

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