2 * consolidate.c : Implementation of the data consolidation feature.
4 * Copyright (C) Almer S. Tigelaar <almer@gnome.org>
5 * Copyright (C) Andreas J Guelzow <aguelzow@taliesin.ca>
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, see <https://www.gnu.org/licenses/>.
21 #include <gnumeric-config.h>
23 #include <glib/gi18n-lib.h>
24 #include "consolidate.h"
27 #include "dependent.h"
32 #include "selection.h"
36 #include "workbook-control.h"
39 /**********************************************************************************
41 **********************************************************************************/
45 * @granges: A list with globalranges
46 * @box: A reference to a range, this parameter
47 * must be set and will be modified to reflect
50 * calculate the bounding box of all the global ranges
51 * combined and put this into the extent parameter.
52 * The origin is always (0,0). The result specifies the
53 * size of the region not the exact placement.
56 get_bounding_box (GSList
const *granges
, GnmRange
*box
)
59 GnmSheetRange
const *gr
;
60 int ext_x
, ext_y
, max_x
, max_y
;
62 g_return_if_fail (granges
!= NULL
);
63 g_return_if_fail (box
!= NULL
);
66 for (l
= granges
; l
!= NULL
; l
= l
->next
) {
69 g_return_if_fail (range_is_sane (&gr
->range
));
71 if ((ext_x
= gr
->range
.end
.col
- gr
->range
.start
.col
) > max_x
)
73 if ((ext_y
= gr
->range
.end
.row
- gr
->range
.start
.row
) > max_y
)
77 box
->start
.row
= box
->start
.col
= 0;
84 cb_value_compare (GnmValue
const *a
, GnmValue
const *b
)
86 GnmValDiff vc
= value_compare (a
, b
, TRUE
);
89 case IS_EQUAL
: return 0;
90 case IS_LESS
: return -1;
91 case IS_GREATER
: return 1;
92 case TYPE_MISMATCH
: return 1; /* Push time mismatches to the end */
94 g_warning ("Unknown value comparison result");
100 /**********************************************************************************/
103 gnm_consolidate_new (void)
107 cs
= g_new0 (GnmConsolidate
, 1);
110 cs
->mode
= CONSOLIDATE_PUT_VALUES
;
117 gnm_consolidate_free (GnmConsolidate
*cs
, gboolean content_only
)
121 g_return_if_fail (cs
!= NULL
);
123 if (cs
->ref_count
-- > 1)
126 gnm_func_unref (cs
->fd
);
130 for (l
= cs
->src
; l
!= NULL
; l
= l
->next
)
131 gnm_sheet_range_free ((GnmSheetRange
*) l
->data
);
132 g_slist_free (cs
->src
);
139 static GnmConsolidate
*
140 gnm_consolidate_ref (GnmConsolidate
*cs
)
147 gnm_consolidate_unref (GnmConsolidate
*cs
)
150 if (cs
->ref_count
== 0)
151 gnm_consolidate_free (cs
, TRUE
);
155 gnm_consolidate_get_type (void)
160 t
= g_boxed_type_register_static ("GnmConsolidate",
161 (GBoxedCopyFunc
)gnm_consolidate_ref
,
162 (GBoxedFreeFunc
)gnm_consolidate_unref
);
168 gnm_consolidate_set_function (GnmConsolidate
*cs
, GnmFunc
*fd
)
170 g_return_if_fail (cs
!= NULL
);
171 g_return_if_fail (fd
!= NULL
);
174 gnm_func_unref (cs
->fd
);
181 gnm_consolidate_set_mode (GnmConsolidate
*cs
, GnmConsolidateMode mode
)
183 g_return_if_fail (cs
!= NULL
);
189 gnm_consolidate_check_destination (GnmConsolidate
*cs
, data_analysis_output_t
*dao
)
195 g_return_val_if_fail (cs
!= NULL
, FALSE
);
196 g_return_val_if_fail (dao
!= NULL
, FALSE
);
198 if (dao
->type
== NewSheetOutput
|| dao
->type
== NewWorkbookOutput
)
201 range_init (&r
, dao
->start_col
, dao
->start_row
,
202 dao
->start_col
+ dao
->cols
- 1,
203 dao
->start_row
+ dao
->rows
- 1);
204 new = gnm_sheet_range_new (dao
->sheet
, &r
);
206 for (l
= cs
->src
; l
!= NULL
; l
= l
->next
) {
207 GnmSheetRange
const *gr
= l
->data
;
209 if (gnm_sheet_range_overlap (new, gr
)) {
210 gnm_sheet_range_free (new);
215 gnm_sheet_range_free (new);
220 gnm_consolidate_add_source (GnmConsolidate
*cs
, GnmValue
*range
)
224 g_return_val_if_fail (cs
!= NULL
, FALSE
);
225 g_return_val_if_fail (range
!= NULL
, FALSE
);
227 new = g_new (GnmSheetRange
, 1);
229 new->sheet
= range
->v_range
.cell
.a
.sheet
;
230 range_init_value (&new->range
, range
);
231 value_release (range
);
233 cs
->src
= g_slist_append (cs
->src
, new);
238 /**********************************************************************************
239 * TREE MANAGEMENT/RETRIEVAL
240 **********************************************************************************/
248 cb_tree_free (GnmValue
const *key
, TreeItem
*ti
,
249 G_GNUC_UNUSED gpointer user_data
)
251 g_return_val_if_fail (key
!= NULL
, FALSE
);
254 * No need to release the ti->key!, it's const.
260 for (l
= ti
->val
; l
!= NULL
; l
= l
->next
)
261 gnm_sheet_range_free ((GnmSheetRange
*) l
->data
);
263 g_slist_free (ti
->val
);
271 tree_free (GTree
*tree
)
273 g_tree_foreach (tree
, (GTraverseFunc
) cb_tree_free
, NULL
);
274 g_tree_destroy (tree
);
280 * This routine traverses the whole source list
281 * of regions and puts all rows in regions which
282 * have a similar key (the key is the first column
283 * in a row) together.
285 * For example, you have (from a single source region, or multiple):
290 * This will be put in the tree like :
294 * This routine can also be called with "with_ranges" set to false,
295 * in that case the ranges will not be stored, but only the unique
298 * The tree will be sorted automatically.
301 retrieve_row_tree (GnmConsolidate
*cs
)
309 g_return_val_if_fail (cs
!= NULL
, NULL
);
311 tree
= g_tree_new ((GCompareFunc
) cb_value_compare
);
313 for (l
= cs
->src
; l
!= NULL
; l
= l
->next
) {
314 GnmSheetRange
const *sgr
= l
->data
;
317 for (row
= sgr
->range
.start
.row
; row
<= sgr
->range
.end
.row
; row
++) {
318 GnmValue
const *v
= sheet_cell_get_value (sgr
->sheet
, sgr
->range
.start
.col
, row
);
320 if (!VALUE_IS_EMPTY (v
)) {
321 if (NULL
== (ti
= g_tree_lookup (tree
, (gpointer
) v
))) {
322 /* NOTE: There is no need to duplicate
323 * the value as it will not change
324 * during the consolidation operation.
325 * We simply store it as const */
326 ti
= g_new0 (TreeItem
, 1);
331 s
.start
.col
= sgr
->range
.start
.col
+ 1;
332 s
.end
.col
= sgr
->range
.end
.col
;
333 if (s
.end
.col
>= s
.start
.col
) {
334 s
.start
.row
= s
.end
.row
= row
;
335 gr
= gnm_sheet_range_new (sgr
->sheet
, &s
);
336 ti
->val
= g_slist_append (ti
->val
, gr
);
338 g_tree_insert (tree
, (GnmValue
*) ti
->key
, ti
);
349 * Same as retrieve_row_tree, but for cols
352 retrieve_col_tree (GnmConsolidate
*cs
)
357 g_return_val_if_fail (cs
!= NULL
, NULL
);
359 tree
= g_tree_new ((GCompareFunc
) cb_value_compare
);
361 for (l
= cs
->src
; l
!= NULL
; l
= l
->next
) {
362 GnmSheetRange
const *sgr
= l
->data
;
365 for (col
= sgr
->range
.start
.col
; col
<= sgr
->range
.end
.col
; col
++) {
366 GnmValue
const *v
= sheet_cell_get_value (sgr
->sheet
, col
, sgr
->range
.start
.row
);
368 if (!VALUE_IS_EMPTY (v
)) {
374 ti
= g_tree_lookup (tree
, (GnmValue
*) v
);
381 s
.start
.col
= s
.end
.col
= col
;
382 s
.start
.row
= sgr
->range
.start
.row
+ 1;
383 s
.end
.row
= sgr
->range
.end
.row
;
385 gr
= gnm_sheet_range_new (sgr
->sheet
, &s
);
386 granges
= g_slist_append (granges
, gr
);
389 * NOTE: There is no need to duplicate the value
390 * as it will not change during the consolidation
391 * operation. We simply store it as const
394 ti
= g_new0 (TreeItem
, 1);
399 g_tree_insert (tree
, (GnmValue
*) ti
->key
, ti
);
408 cb_key_find (GnmValue
const *current
, GnmValue
const *wanted
)
410 return !(value_compare (current
, wanted
, TRUE
) == IS_EQUAL
);
414 key_list_get (GnmConsolidate
*cs
, gboolean is_cols
)
419 for (l
= cs
->src
; l
!= NULL
; l
= l
->next
) {
420 GnmSheetRange
*sgr
= l
->data
;
422 ? sgr
->range
.start
.col
423 : sgr
->range
.start
.row
;
426 : sgr
->range
.end
.row
;
429 * NOTE: We always need to skip the first col/row
430 * because it's situated in the corner and it is not
432 * Keep into account that this only the case
433 * for col/row consolidations.
436 for (; i
<= max
; i
++) {
437 GnmValue
const *v
= sheet_cell_get_value (sgr
->sheet
,
438 is_cols
? i
: sgr
->range
.start
.col
,
439 is_cols
? sgr
->range
.start
.row
: i
);
441 * We avoid adding duplicates, this list needs to contain unique keys,
442 * also we treat the value as a constant, we don't duplicate it. It will
443 * not change during the consolidation.
445 if (!VALUE_IS_EMPTY (v
) &&
446 g_slist_find_custom (keys
, (GnmValue
*) v
, (GCompareFunc
) cb_key_find
) == NULL
)
447 keys
= g_slist_insert_sorted (keys
, (GnmValue
*) v
, (GCompareFunc
) cb_value_compare
);
454 /**********************************************************************************
455 * CONSOLIDATION ROUTINES
456 **********************************************************************************/
459 * simple_consolidate:
461 * This routine consolidates all the ranges in source into
462 * the region dst using the function "fd" on all the overlapping
467 * src contains : A1:B2 (4 cells containing all 1's) and A3:B4 (4 cells containing all 2's).
469 * The consolidated result will be :
473 * Note that the topleft of the result will be put at the topleft of the
474 * destination FullRange. Currently no clipping is done on the destination
475 * range so the dst->range->end.* are ignored. (clipping isn't terribly
479 simple_consolidate (GnmFunc
*fd
, GSList
const *src
,
480 gboolean is_col_or_row
,
481 data_analysis_output_t
*dao
)
485 Sheet
*prev_sheet
= NULL
;
486 GnmRangeRef
*prev_r
= NULL
;
489 g_return_if_fail (fd
!= NULL
);
490 g_return_if_fail (src
!= NULL
);
492 get_bounding_box (src
, &box
);
493 for (y
= box
.start
.row
; y
<= box
.end
.row
; y
++) {
494 for (x
= box
.start
.col
; x
<= box
.end
.col
; x
++) {
495 GnmExprList
*args
= NULL
;
497 for (l
= src
; l
!= NULL
; l
= l
->next
) {
498 GnmSheetRange
const *gr
= l
->data
;
503 * We don't want to include this range
504 * this time if the current traversal
505 * offset falls out of its bounds
507 if (gr
->range
.start
.row
+ y
> gr
->range
.end
.row
||
508 gr
->range
.start
.col
+ x
> gr
->range
.end
.col
)
511 r
.start
.col
= r
.end
.col
= gr
->range
.start
.col
+ x
;
512 r
.start
.row
= r
.end
.row
= gr
->range
.start
.row
+ y
;
515 * If possible add it to the previous range
516 * this looks nicer for the formula's and can
517 * save us much allocations which in turn
518 * improves performance. Don't remove!
519 * NOTE: Only for col/row consolidation!
520 * This won't work for simple consolidations.
522 if (is_col_or_row
&& prev_sheet
== gr
->sheet
) {
523 if (prev_r
->a
.row
== r
.start
.row
524 && prev_r
->b
.row
== r
.start
.row
525 && prev_r
->b
.col
+ 1 == r
.start
.col
) {
528 } else if (prev_r
->a
.col
== r
.start
.col
529 && prev_r
->b
.col
== r
.start
.col
530 && prev_r
->b
.row
+ 1 == r
.start
.row
) {
536 val
= value_new_cellrange_r (gr
->sheet
, &r
);
537 prev_r
= &val
->v_range
.cell
;
538 prev_sheet
= gr
->sheet
;
540 args
= gnm_expr_list_append (args
, gnm_expr_new_constant (val
));
544 dao_set_cell_expr (dao
, x
, y
,
545 gnm_expr_new_funcall (fd
, args
));
552 data_analysis_output_t
*dao
;
553 WorkbookControl
*wbc
;
554 } ConsolidateContext
;
557 * row_consolidate_row:
559 * Consolidates a list of regions which all specify a single
560 * row and share the same key into a single target range.
563 cb_row_tree (GnmValue
const *key
, TreeItem
*ti
, ConsolidateContext
*cc
)
565 GnmConsolidate
*cs
= cc
->cs
;
567 if (cs
->mode
& CONSOLIDATE_COPY_LABELS
)
568 dao_set_cell_value (cc
->dao
, -1, 0, value_dup (key
));
570 simple_consolidate (cs
->fd
, ti
->val
, FALSE
, cc
->dao
);
572 cc
->dao
->offset_col
++;
580 * High level routine for row consolidation, retrieves
581 * the row (name) hash and uses a callback routine to do a
582 * simple consolidation for each row.
585 row_consolidate (GnmConsolidate
*cs
, data_analysis_output_t
*dao
)
587 ConsolidateContext cc
;
590 g_return_if_fail (cs
!= NULL
);
592 tree
= retrieve_row_tree (cs
);
596 if (cs
->mode
& CONSOLIDATE_COPY_LABELS
)
599 g_tree_foreach (tree
, (GTraverseFunc
) cb_row_tree
, &cc
);
607 * Consolidates a list of regions which all specify a single
608 * column and share the same key into a single target range.
611 cb_col_tree (GnmValue
const *key
, TreeItem
*ti
, ConsolidateContext
*cc
)
613 GnmConsolidate
*cs
= cc
->cs
;
615 if (cs
->mode
& CONSOLIDATE_COPY_LABELS
)
616 dao_set_cell_value (cc
->dao
, 0, -1, value_dup (key
));
618 simple_consolidate (cs
->fd
, ti
->val
, FALSE
, cc
->dao
);
620 cc
->dao
->offset_col
++;
628 * High level routine for column consolidation, retrieves
629 * the column (name) hash and uses a callback routine to do a
630 * simple consolidation for each column.
633 col_consolidate (GnmConsolidate
*cs
, data_analysis_output_t
*dao
)
635 ConsolidateContext cc
;
638 g_return_if_fail (cs
!= NULL
);
640 tree
= retrieve_col_tree (cs
);
645 if (cs
->mode
& CONSOLIDATE_COPY_LABELS
)
648 g_tree_foreach (tree
, (GTraverseFunc
) cb_col_tree
, &cc
);
654 colrow_formula_args_build (GnmValue
const *row_name
, GnmValue
const *col_name
, GSList
*granges
)
657 GnmExprList
*args
= NULL
;
659 for (l
= granges
; l
!= NULL
; l
= l
->next
) {
660 GnmSheetRange
*gr
= l
->data
;
664 * Now walk trough the entire area the range
665 * covers and attempt to find cells that have
666 * the right row_name and col_name keys. If such
667 * a cell is found we append it to the formula
669 for (ry
= gr
->range
.start
.row
+ 1; ry
<= gr
->range
.end
.row
; ry
++) {
670 GnmValue
const *rowtxt
= sheet_cell_get_value (gr
->sheet
, gr
->range
.start
.col
, ry
);
672 if (rowtxt
== NULL
|| value_compare (rowtxt
, row_name
, TRUE
) != IS_EQUAL
)
675 for (rx
= gr
->range
.start
.col
+ 1; rx
<= gr
->range
.end
.col
; rx
++) {
676 GnmValue
const *coltxt
= sheet_cell_get_value (gr
->sheet
, rx
, gr
->range
.start
.row
);
679 if (coltxt
== NULL
|| value_compare (coltxt
, col_name
, TRUE
) != IS_EQUAL
)
682 ref
.sheet
= gr
->sheet
;
685 ref
.col_relative
= ref
.row_relative
= FALSE
;
687 args
= gnm_expr_list_append (args
, gnm_expr_new_cellref (&ref
));
697 colrow_consolidate (GnmConsolidate
*cs
, data_analysis_output_t
*dao
)
706 g_return_if_fail (cs
!= NULL
);
708 rows
= key_list_get (cs
, FALSE
);
709 cols
= key_list_get (cs
, TRUE
);
711 if (cs
->mode
& CONSOLIDATE_COPY_LABELS
) {
712 for (l
= rows
, y
= 1; l
!= NULL
; l
= l
->next
, y
++) {
713 GnmValue
const *row_name
= l
->data
;
715 dao_set_cell_value (dao
, 0, y
, value_dup (row_name
));
717 for (m
= cols
, x
= 1; m
!= NULL
; m
= m
->next
, x
++) {
718 GnmValue
const *col_name
= m
->data
;
720 dao_set_cell_value (dao
, x
, 0, value_dup (col_name
));
726 for (l
= rows
, y
= 0; l
!= NULL
; l
= l
->next
, y
++) {
727 GnmValue
const *row_name
= l
->data
;
729 for (m
= cols
, x
= 0; m
!= NULL
; m
= m
->next
, x
++) {
730 GnmValue
const *col_name
= m
->data
;
733 args
= colrow_formula_args_build (row_name
, col_name
, cs
->src
);
736 GnmExpr
const *expr
= gnm_expr_new_funcall (cs
->fd
, args
);
738 dao_set_cell_expr (dao
, x
, y
, expr
);
748 consolidate_apply (GnmConsolidate
*cs
,
749 data_analysis_output_t
*dao
)
751 /* WorkbookView *wbv = wb_control_view (wbc); */
753 g_return_val_if_fail (cs
!= NULL
, TRUE
);
756 * All parameters must be set, it's not
757 * a critical error if one of them is not set,
758 * we just don't do anything in that case
760 if (!cs
->fd
|| !cs
->src
)
763 if ((cs
->mode
& CONSOLIDATE_ROW_LABELS
) && (cs
->mode
& CONSOLIDATE_COL_LABELS
))
764 colrow_consolidate (cs
, dao
);
765 else if (cs
->mode
& CONSOLIDATE_ROW_LABELS
)
766 row_consolidate (cs
, dao
);
767 else if (cs
->mode
& CONSOLIDATE_COL_LABELS
)
768 col_consolidate (cs
, dao
);
770 simple_consolidate (cs
->fd
, cs
->src
, FALSE
, dao
);
771 dao_redraw_respan (dao
);
778 gnm_tool_consolidate_engine (G_GNUC_UNUSED GOCmdContext
*gcc
, data_analysis_output_t
*dao
, gpointer specs
,
779 analysis_tool_engine_t selector
, gpointer result
)
781 GnmConsolidate
*cs
= specs
;
784 case TOOL_ENGINE_UPDATE_DESCRIPTOR
:
785 return (dao_command_descriptor (dao
, _("Consolidating to (%s)"),
787 case TOOL_ENGINE_UPDATE_DAO
:
791 range_init (&r
, 0, 0, 0, 0);
792 get_bounding_box (cs
->src
, &r
);
794 if ((cs
->mode
& CONSOLIDATE_ROW_LABELS
) &&
795 (cs
->mode
& CONSOLIDATE_COL_LABELS
))
796 dao_adjust (dao
, r
.end
.col
+ 1 +
797 ((cs
->mode
& CONSOLIDATE_COPY_LABELS
) ?
800 ((cs
->mode
& CONSOLIDATE_COPY_LABELS
) ?
802 else if (cs
->mode
& CONSOLIDATE_ROW_LABELS
)
803 dao_adjust (dao
, r
.end
.col
+ 1,
805 ((cs
->mode
& CONSOLIDATE_COPY_LABELS
) ?
808 else if (cs
->mode
& CONSOLIDATE_COL_LABELS
)
809 dao_adjust (dao
, r
.end
.col
+ 1 +
810 ((cs
->mode
& CONSOLIDATE_COPY_LABELS
) ?
814 dao_adjust (dao
, r
.end
.col
+ 1,
818 case TOOL_ENGINE_CLEAN_UP
:
819 gnm_consolidate_free (cs
, TRUE
);
821 case TOOL_ENGINE_LAST_VALIDITY_CHECK
:
823 case TOOL_ENGINE_PREPARE_OUTPUT_RANGE
:
824 dao_prepare_output (NULL
, dao
, _("Data Consolidation"));
826 case TOOL_ENGINE_FORMAT_OUTPUT_RANGE
:
827 return dao_format_output (dao
, _("Data Consolidation"));
828 case TOOL_ENGINE_PERFORM_CALC
:
830 return consolidate_apply (cs
, dao
);
832 return TRUE
; /* We shouldn't get here */