1/* This file is part of the KDE project
2 Copyright 2006-2007 Stefan Nikolaus <stefan.nikolaus@kdemail.net>
3 Copyright 2004 Tomas Mecir <mecirt@gmail.com>
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Library General Public
7 License as published by the Free Software Foundation; only
8 version 2 of the License.
9
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Library General Public License for more details.
14
15 You should have received a copy of the GNU Library General Public License
16 along with this library; see the file COPYING.LIB. If not, write to
17 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
19*/
20
21// Local
22#include "RecalcManager.h"
23
24#include "Cell.h"
25#include "CellStorage.h"
26#include "DependencyManager.h"
27#include "Formula.h"
28#include "FormulaStorage.h"
29#include "Map.h"
30#include "Sheet.h"
31#include "Region.h"
32#include "Value.h"
33#include "ValueFormatter.h"
34#include "DocBase.h"
35#include "ElapsedTime_p.h"
36
37#include <KoUpdater.h>
38
39#include <QHash>
40#include <QMap>
41
42using namespace Calligra::Sheets;
43
44class RecalcManager::Private
45{
46public:
47 /**
48 * Finds all cells in region and their dependents, that need recalculation.
49 *
50 * \see RecalcManager::regionChanged
51 */
52 void cellsToCalculate(const Region& region);
53
54 /**
55 * Finds all cells in \p sheet , that have got a formula and hence need
56 * recalculation.
57 * If \p sheet is zero, all cells in the Map a returned.
58 *
59 * \see RecalcManager::recalcMap
60 * \see RecalcManager::recalcSheet
61 */
62 void cellsToCalculate(Sheet* sheet = 0);
63
64 /**
65 * Helper function for cellsToCalculate(const Region&) and cellsToCalculate(Sheet*).
66 */
67 void cellsToCalculate(const Region& region, QSet<Cell>& cells) const;
68
69 /*
70 * Stores cells ordered by its reference depth.
71 * Depth means the maximum depth of all cells this cell depends on plus one,
72 * while a cell which has a formula without cell references has a depth
73 * of zero.
74 *
75 * Examples:
76 * \li A1: '=1.0'
77 * \li A2: '=A1+A1'
78 * \li A3: '=A1+A1+A2'
79 *
80 * \li depth(A1) = 0
81 * \li depth(A2) = 1
82 * \li depth(A3) = 2
83 */
84 QMap<int, Cell> cells;
85 const Map* map;
86 bool active;
87};
88
89void RecalcManager::Private::cellsToCalculate(const Region& region)
90{
91 if (region.isEmpty())
92 return;
93
94 // retrieve the cell depths
95 QMap<Cell, int> depths = map->dependencyManager()->depths();
96
97 // create the cell map ordered by depth
98 QSet<Cell> cells;
99 cellsToCalculate(region, cells);
100 const QSet<Cell>::ConstIterator end(cells.end());
101 for (QSet<Cell>::ConstIterator it(cells.begin()); it != end; ++it) {
102 if ((*it).sheet()->isAutoCalculationEnabled())
103 this->cells.insertMulti(depths[*it], *it);
104 }
105}
106
107void RecalcManager::Private::cellsToCalculate(Sheet* sheet)
108{
109 // retrieve the cell depths
110 QMap<Cell, int> depths = map->dependencyManager()->depths();
111
112 // NOTE Stefan: It's necessary, that the cells are filled in row-wise;
113 // beginning with the top left; ending with the bottom right.
114 // This ensures, that the value storage is processed the same
115 // way, which boosts performance (using PointStorage) for an
116 // empty storage (on loading). For an already filled value
117 // storage, the speed gain is not that sensible.
118 Cell cell;
119 if (!sheet) { // map recalculation
120 for (int s = 0; s < map->count(); ++s) {
121 sheet = map->sheet(s);
122 for (int c = 0; c < sheet->formulaStorage()->count(); ++c) {
123 cell = Cell(sheet, sheet->formulaStorage()->col(c), sheet->formulaStorage()->row(c));
124 cells.insertMulti(depths[cell], cell);
125 }
126 }
127 } else { // sheet recalculation
128 for (int c = 0; c < sheet->formulaStorage()->count(); ++c) {
129 cell = Cell(sheet, sheet->formulaStorage()->col(c), sheet->formulaStorage()->row(c));
130 cells.insertMulti(depths[cell], cell);
131 }
132 }
133}
134
135void RecalcManager::Private::cellsToCalculate(const Region& region, QSet<Cell>& cells) const
136{
137 Region::ConstIterator end(region.constEnd());
138 for (Region::ConstIterator it(region.constBegin()); it != end; ++it) {
139 const QRect range = (*it)->rect();
140 const Sheet* sheet = (*it)->sheet();
141 for (int col = range.left(); col <= range.right(); ++col) {
142 for (int row = range.top(); row <= range.bottom(); ++row) {
143 Cell cell(sheet, col, row);
144 // Even empty cells may act as value
145 // providers and need to be processed.
146
147 // check for already processed cells
148 if (cells.contains(cell))
149 continue;
150
151 // add it to the list
152 if (cell.isFormula())
153 cells.insert(cell);
154
155 // add its consumers to the list
156 cellsToCalculate(map->dependencyManager()->consumingRegion(cell), cells);
157 }
158 }
159 }
160}
161
162RecalcManager::RecalcManager(Map *const map)
163 : QObject(map)
164 , d(new Private)
165{
166 d->map = map;
167 d->active = false;
168}
169
170RecalcManager::~RecalcManager()
171{
172 delete d;
173}
174
175void RecalcManager::regionChanged(const Region& region)
176{
177 if (d->active || region.isEmpty())
178 return;
179 d->active = true;
180 kDebug(36002) << "RecalcManager::regionChanged" << region.name();
181 ElapsedTime et("Overall region recalculation", ElapsedTime::PrintOnlyTime);
182 d->cellsToCalculate(region);
183 recalc();
184 d->active = false;
185}
186
187void RecalcManager::recalcSheet(Sheet* const sheet)
188{
189 if (d->active)
190 return;
191 d->active = true;
192 ElapsedTime et("Overall sheet recalculation", ElapsedTime::PrintOnlyTime);
193 d->cellsToCalculate(sheet);
194 recalc();
195 d->active = false;
196}
197
198void RecalcManager::recalcMap(KoUpdater *updater)
199{
200 if (d->active)
201 return;
202 d->active = true;
203 ElapsedTime et("Overall map recalculation", ElapsedTime::PrintOnlyTime);
204 d->cellsToCalculate();
205 recalc(updater);
206 d->active = false;
207}
208
209bool RecalcManager::isActive() const
210{
211 return d->active;
212}
213
214void RecalcManager::addSheet(Sheet *sheet)
215{
216 // Manages also the revival of a deleted sheet.
217 Q_UNUSED(sheet);
218
219 // sebsauer: not recalc every time on loading - bug 284325
220 if (!d->map->isLoading()) {
221 recalcMap(); // FIXME Stefan: Implement a more elegant solution.
222 }
223}
224
225void RecalcManager::removeSheet(Sheet *sheet)
226{
227 Q_UNUSED(sheet);
228 recalcMap(); // FIXME Stefan: Implement a more elegant solution.
229}
230
231void RecalcManager::recalc(KoUpdater *updater)
232{
233 kDebug(36002) << "Recalculating" << d->cells.count() << " cell(s)..";
234 ElapsedTime et("Recalculating cells", ElapsedTime::PrintOnlyTime);
235
236 if (updater)
237 updater->setProgress(0);
238
239 const QList<Cell> cells = d->cells.values();
240 const int cellsCount = cells.count();
241 for (int c = 0; c < cellsCount; ++c) {
242 // only recalculate, if no circular dependency occurred
243 if (cells.value(c).value() == Value::errorCIRCLE())
244 continue;
245 // Check for valid formula; parses the expression, if not done already.
246 if (!cells.value(c).formula().isValid())
247 continue;
248
249 const Sheet* sheet = cells.value(c).sheet();
250
251 // evaluate the formula and set the result
252 Value result = cells.value(c).formula().eval();
253 if (result.isArray() && (result.columns() > 1 || result.rows() > 1)) {
254 const QRect rect = cells.value(c).lockedCells();
255 // unlock
256 sheet->cellStorage()->unlockCells(rect.left(), rect.top());
257 for (int row = rect.top(); row <= rect.bottom(); ++row) {
258 for (int col = rect.left(); col <= rect.right(); ++col) {
259 Cell(sheet, col, row).setValue(result.element(col - rect.left(), row - rect.top()));
260 }
261 }
262 // relock
263 sheet->cellStorage()->lockCells(rect);
264 } else {
265 Cell(cells.value(c)).setValue(result);
266 }
267 if (updater)
268 updater->setProgress(int(qreal(c) / qreal(cellsCount) * 100.));
269 }
270
271 if (updater)
272 updater->setProgress(100);
273
274// dump();
275 d->cells.clear();
276}
277
278void RecalcManager::dump() const
279{
280 QMap<int, Cell>::ConstIterator end(d->cells.constEnd());
281 for (QMap<int, Cell>::ConstIterator it(d->cells.constBegin()); it != end; ++it) {
282 Cell cell = it.value();
283 QString cellName = cell.name();
284 while (cellName.count() < 4) cellName.prepend(' ');
285 kDebug(36002) << "depth(" << cellName << " ) =" << it.key();
286 }
287}
288