kspread
dependencies.cc00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include "dependencies.h"
00022
00023 #include "formula.h"
00024
00025 #include "kspread_cell.h"
00026 #include "kspread_sheet.h"
00027
00028 #include <qmap.h>
00029
00030
00031
00032 #define CELLCHUNK_ROWS 128
00033 #define CELLCHUNK_COLS 16
00034
00035 namespace KSpread {
00036
00037
00039 class DependencyList {
00040 public:
00041 DependencyList (Sheet *s);
00042 ~DependencyList () { reset (); };
00044 void reset ();
00045
00047 void cellChanged (const Point &cell);
00048
00050 void generateDependencies (const Point &cell);
00052 void generateDependencies (const Range &range);
00054 void generateDependencies (const RangeList &rangeList);
00055
00057 void processDependencies (const Point &cell);
00059 void processDependencies (const Range &range);
00061 void processDependencies (const RangeList &rangeList);
00062
00064 RangeList getDependencies (const Point &cell);
00066 QValueList<Point> getDependants (const Point &cell);
00067
00068 void areaModified (const QString &name);
00069 protected:
00071 void addDependency (const Point &cell1, const Point &cell2);
00073 void addRangeDependency (const RangeDependency &rd);
00075 void removeDependencies (const Point &cell);
00076
00078 void processRangeDependencies (const Point &cell);
00079
00081 void processRangeDependencies (const Range &range);
00082
00084 void updateCell (const Point &cell) const;
00085
00088 Point leadingCell (const Point &cell) const;
00090 QValueList<Point> leadingCells (const Range &range) const;
00092 RangeList computeDependencies (const Point &cell) const;
00093
00094 QValueList<Point> getCellDeps(const Point& cell) const {
00095 CellDepsMap::const_iterator it = cellDeps.find( cell );
00096 return it == cellDeps.end() ? QValueList<Point>() : *it;
00097 }
00098
00100 void dump();
00101
00103 Sheet *sheet;
00104
00106 QMap<Point, RangeList> dependencies;
00108 typedef QMap<Point, QValueList<Point> > CellDepsMap;
00109 CellDepsMap cellDeps;
00111 QMap<Point, QValueList<RangeDependency> > rangeDeps;
00113 QMap<QString, QMap<Point, bool> > areaDeps;
00114 };
00115
00116 }
00117
00118 using namespace KSpread;
00119
00120
00121
00122 void DependencyList::dump()
00123 {
00124 QMap<Point, RangeList>::const_iterator it = dependencies.begin();
00125 for ( ; it != dependencies.end(); ++it ) {
00126 Point p = it.key();
00127 kdDebug() << "Cell " << p.sheetName() << " " << p.pos()
00128 << " depends on :" << endl;
00129 RangeList rl = (*it);
00130 QValueList<Point>::const_iterator itp = rl.cells.begin();
00131 for ( ; itp != rl.cells.end(); ++itp )
00132 kdDebug() << " cell " << (*itp).pos() << endl;
00133 QValueList<Range>::const_iterator itr = rl.ranges.begin();
00134 for ( ; itr != rl.ranges.end(); ++itr )
00135 kdDebug() << " range " << (*itr).toString() << endl;
00136 }
00137
00138 CellDepsMap::const_iterator cit = cellDeps.begin();
00139 for ( ; cit != cellDeps.end(); ++cit )
00140 {
00141 Point p = cit.key();
00142 kdDebug() << "The cells that depend on " << p.sheetName() << " " << p.pos()
00143 << " are :" << endl;
00144 QValueList<Point>::const_iterator itp = (*cit).begin();
00145 for ( ; itp != (*cit).end(); ++itp )
00146 kdDebug() << " cell " << (*itp).pos() << endl;
00147 }
00148
00149 }
00150
00151 DependencyManager::DependencyManager (Sheet *s)
00152 {
00153 deps = new DependencyList (s);
00154 }
00155
00156 DependencyManager::~DependencyManager ()
00157 {
00158 delete deps;
00159 deps = 0;
00160 }
00161
00162 void DependencyManager::reset ()
00163 {
00164 deps->reset();
00165 }
00166
00167 void DependencyManager::cellChanged (const Point &cell)
00168 {
00169 deps->cellChanged (cell);
00170 }
00171
00172 void DependencyManager::rangeChanged (const Range &range)
00173 {
00174 deps->generateDependencies (range);
00175 deps->processDependencies (range);
00176 }
00177
00178 void DependencyManager::rangeListChanged (const RangeList &rangeList)
00179 {
00180 deps->generateDependencies (rangeList);
00181 deps->processDependencies (rangeList);
00182 }
00183
00184 void DependencyManager::areaModified (const QString &name)
00185 {
00186 deps->areaModified (name);
00187 }
00188
00189 RangeList DependencyManager::getDependencies (const Point &cell)
00190 {
00191 return deps->getDependencies (cell);
00192 }
00193
00194 QValueList<Point> DependencyManager::getDependants (const Point &cell)
00195 {
00196 return deps->getDependants (cell);
00197 }
00198
00199 DependencyList::DependencyList (Sheet *s)
00200 : sheet (s)
00201 {
00202 }
00203
00204 void DependencyList::reset ()
00205 {
00206 dependencies.clear();
00207 cellDeps.clear();
00208 rangeDeps.clear();
00209 }
00210
00211 void DependencyList::cellChanged (const Point &cell)
00212 {
00213 Cell *c = cell.cell();
00214
00215
00216 if( c->isDefault() )
00217 return;
00218
00219
00220 if (c->testFlag (Cell::Flag_CircularCalculation))
00221 return;
00222
00223
00224 if ( !(c->testFlag (Cell::Flag_Progress)))
00225 generateDependencies (cell);
00226
00227 processDependencies (cell);
00228 }
00229
00230 RangeList DependencyList::getDependencies (const Point &cell)
00231 {
00232 RangeList rl;
00233
00234 if (!dependencies.contains (cell))
00235 return rl;
00236
00237
00238 return dependencies[cell];
00239 }
00240
00241 QValueList<Point> DependencyList::getDependants (const Point &cell)
00242 {
00243
00244 QValueList<Point> list = getCellDeps( cell );
00245
00246 Point leading = leadingCell (cell);
00247 QValueList<RangeDependency>::iterator it;
00248 if (!rangeDeps.count (leading))
00249 return list;
00250
00251 for (it = rangeDeps[leading].begin();
00252 it != rangeDeps[leading].end(); ++it)
00253 {
00254
00255
00256 if ((*it).range.contains (cell))
00257 {
00258 Point c;
00259 c.setRow ((*it).cellrow);
00260 c.setColumn ((*it).cellcolumn);
00261 c.setSheet ( (*it).cellsheet );
00262 list.push_back (c);
00263 }
00264 }
00265
00266 return list;
00267 }
00268
00269 void DependencyList::areaModified (const QString &name)
00270 {
00271
00272
00273
00274
00275 if (!areaDeps.contains (name))
00276 return;
00277
00278 QMap<Point, bool>::iterator it;
00279 for (it = areaDeps[name].begin(); it != areaDeps[name].end(); ++it)
00280 {
00281 Cell *c = it.key().cell();
00282
00283
00284 c->setValue (c->value ());
00285 }
00286 }
00287
00288 void DependencyList::addDependency (const Point &cell1,
00289 const Point &cell2)
00290 {
00291
00292 Sheet *sh = cell2.sheet();
00293 if (!sh)
00294 sh = sheet;
00295
00296 dependencies[cell1].cells.push_back (cell2);
00297 sh->dependencies()->deps->cellDeps[cell2].push_back (cell1);
00298 }
00299
00300 void DependencyList::addRangeDependency (const RangeDependency &rd)
00301 {
00302
00303 Sheet *sh = rd.range.sheet();
00304 if (!sh)
00305 sh = sheet;
00306
00307 Point cell;
00308 cell.setSheet (rd.cellsheet);
00309 cell.setRow (rd.cellrow);
00310 cell.setColumn (rd.cellcolumn);
00311 dependencies[cell].ranges.push_back (rd.range);
00312
00313 QValueList<Point> leadings = leadingCells (rd.range);
00314 QValueList<Point>::iterator it;
00315 for (it = leadings.begin(); it != leadings.end(); ++it)
00316 sh->dependencies()->deps->rangeDeps[*it].push_back (rd);
00317
00318
00319 if (!rd.range.namedArea().isNull())
00320 areaDeps[rd.range.namedArea()][cell] = true;
00321 }
00322
00323 void DependencyList::removeDependencies (const Point &cell)
00324 {
00325
00326 if (!dependencies.contains (cell))
00327 return;
00328
00329
00330 QValueList<Point> cells = dependencies[cell].cells;
00331 QValueList<Point>::iterator it1;
00332 for (it1 = cells.begin(); it1 != cells.end(); ++it1)
00333 {
00334
00335 Sheet *sh = (*it1).sheet();
00336 if (!sh)
00337 sh = sheet;
00338
00339 if (!sh->dependencies()->deps->cellDeps.contains (*it1))
00340 continue;
00341
00342
00343 QValueList<Point>::iterator cit;
00344 cit = sh->dependencies()->deps->cellDeps[*it1].find (cell);
00345 if (cit != sh->dependencies()->deps->cellDeps[*it1].end())
00346 sh->dependencies()->deps->cellDeps[*it1].erase (cit);
00347 }
00348
00349
00350 QValueList<Range> ranges = dependencies[cell].ranges;
00351 QValueList<Range>::iterator it2;
00352 QValueList<Point> leads;
00353 for (it2 = ranges.begin(); it2 != ranges.end(); ++it2)
00354 {
00355
00356
00357 QValueList<Point> leadings = leadingCells (*it2);
00358 for (it1 = leadings.begin(); it1 != leadings.end(); ++it1)
00359 if (!leads.contains (*it1))
00360 leads.push_back (*it1);
00361 }
00362 for (it1 = leads.begin(); it1 != leads.end(); ++it1)
00363 {
00364
00365 Sheet *sh = (*it1).sheet();
00366 if (!sh)
00367 sh = sheet;
00368
00369 if (sh->dependencies()->deps->rangeDeps.contains (*it1))
00370 {
00371 QValueList<RangeDependency>::iterator it3;
00372 it3 = sh->dependencies()->deps->rangeDeps[*it1].begin();
00373
00374 while (it3 != sh->dependencies()->deps->rangeDeps[*it1].end())
00375 if (((*it3).cellrow == cell.row()) &&
00376 ((*it3).cellcolumn == cell.column()))
00377 it3 = sh->dependencies()->deps->rangeDeps[*it1].erase (it3);
00378 else
00379 ++it3;
00380
00381 if (sh->dependencies()->deps->rangeDeps[*it1].empty())
00382 sh->dependencies()->deps->rangeDeps.erase (*it1);
00383 }
00384 }
00385
00386
00387 QMap<QString, QMap<Point, bool> >::iterator itr;
00388 for (itr = areaDeps.begin(); itr != areaDeps.end(); ++itr) {
00389 if (itr.data().contains (cell))
00390 itr.data().remove (cell);
00391 }
00392
00393
00394 dependencies[cell].cells.clear();
00395 dependencies[cell].ranges.clear();
00396 dependencies.erase (cell);
00397 }
00398
00399 void DependencyList::generateDependencies (const Point &cell)
00400 {
00401
00402 removeDependencies (cell);
00403
00404
00405 Cell *c = sheet->cellAt (cell.column(), cell.row());
00406 if( c->isDefault() )
00407 return;
00408 if (!c->isFormula())
00409 return;
00410
00411
00412 RangeList rl = computeDependencies (cell);
00413
00414
00415
00416 QValueList<Point>::iterator it1;
00417 QValueList<Range>::iterator it2;
00418
00419 for (it1 = rl.cells.begin(); it1 != rl.cells.end(); ++it1)
00420 addDependency (cell, *it1);
00421 for (it2 = rl.ranges.begin(); it2 != rl.ranges.end(); ++it2)
00422 {
00423 RangeDependency rd;
00424 rd.cellrow = cell.row();
00425 rd.cellcolumn = cell.column();
00426 rd.cellsheet = sheet;
00427 rd.range = *it2;
00428
00429 if (rd.range.sheet() == 0)
00430 rd.range.setSheet(sheet);
00431
00432 addRangeDependency (rd);
00433 }
00434 }
00435
00436 void DependencyList::generateDependencies (const Range &range)
00437 {
00438 for (int row = range.startRow(); row <= range.endRow(); row++)
00439 for (int col = range.startCol(); col <= range.endCol(); col++)
00440 {
00441 Point c;
00442 c.setRow (row);
00443 c.setColumn (col);
00444 c.setSheet(sheet);
00445 generateDependencies (c);
00446 }
00447 }
00448
00449 void DependencyList::generateDependencies (const RangeList &rangeList)
00450 {
00451 QValueList<Point>::const_iterator it1;
00452 QValueList<Range>::const_iterator it2;
00453
00454 for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
00455 generateDependencies (*it1);
00456 for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
00457 generateDependencies (*it2);
00458 }
00459
00460 void DependencyList::processDependencies (const Point &cell)
00461 {
00462 const QValueList<Point> d = getCellDeps(cell);
00463 QValueList<Point>::const_iterator it = d.begin();
00464 const QValueList<Point>::const_iterator end = d.end();
00465 for (; it != end; ++it)
00466 updateCell (*it);
00467
00468 processRangeDependencies (cell);
00469 }
00470
00471 void DependencyList::processRangeDependencies (const Point &cell)
00472 {
00473 Point leading = leadingCell (cell);
00474 if (!rangeDeps.count (leading))
00475 return;
00476
00477 const QValueList<RangeDependency> rd = rangeDeps[leading];
00478
00479 QValueList<RangeDependency>::const_iterator it;
00480 for (it = rd.begin(); it != rd.end(); ++it)
00481 {
00482
00483
00484 if ((*it).range.contains (cell))
00485 {
00486 Point c;
00487 c.setRow ((*it).cellrow);
00488 c.setColumn ((*it).cellcolumn);
00489 c.setSheet ( (*it).cellsheet );
00490 updateCell (c);
00491 }
00492 }
00493 }
00494
00495 void DependencyList::processDependencies (const Range &range)
00496 {
00497
00498
00499 for (int row = range.startRow(); row <= range.endRow(); row++)
00500 for (int col = range.startCol(); col <= range.endCol(); col++)
00501 {
00502 Point c;
00503 c.setRow (row);
00504 c.setColumn (col);
00505 c.setSheet( sheet );
00506
00507 const QValueList<Point> d = getCellDeps(c);
00508 QValueList<Point>::const_iterator it = d.begin();
00509 const QValueList<Point>::const_iterator end = d.end();
00510 for (; it != end; ++it)
00511 updateCell (*it);
00512 }
00513
00514 processRangeDependencies (range);
00515 }
00516
00517 void DependencyList::processRangeDependencies (const Range &range)
00518 {
00519
00520
00521
00522
00523
00524 QValueList<Point> leadings = leadingCells (range);
00525 QValueList<Point>::iterator it;
00526 for (it = leadings.begin(); it != leadings.end(); ++it)
00527 {
00528 if (!rangeDeps.count (*it))
00529 continue;
00530 QValueList<RangeDependency>::iterator it2;
00531 for (it2 = rangeDeps[*it].begin(); it2 != rangeDeps[*it].end(); ++it2)
00532 {
00533
00534
00535 if ((*it2).range.intersects (range))
00536 {
00537 Point c;
00538 c.setRow ((*it2).range.startRow());
00539 c.setColumn ((*it2).range.startCol());
00540 c.setSheet(sheet);
00541 updateCell (c);
00542 }
00543 }
00544 }
00545 }
00546
00547 void DependencyList::processDependencies (const RangeList &rangeList)
00548 {
00549 QValueList<Point>::const_iterator it1;
00550 QValueList<Range>::const_iterator it2;
00551
00552 for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
00553 processDependencies (*it1);
00554 for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
00555 processDependencies (*it2);
00556 }
00557
00558 void DependencyList::updateCell (const Point &cell) const
00559 {
00560 Cell *c = cell.cell();
00561
00562 if (c->testFlag (Cell::Flag_Progress) ||
00563 c->testFlag (Cell::Flag_CircularCalculation))
00564 {
00565 kdError(36001) << "ERROR: Circle, cell " << c->fullName() <<
00566 ", in dep.manager for sheet " << sheet->name() << endl;
00567 Value v;
00568
00569
00570
00571
00572 if (!c->testFlag (Cell::Flag_CircularCalculation))
00573 {
00574 c->setFlag(Cell::Flag_CircularCalculation);
00575 v.setError ( "####" );
00576 c->setValue (v);
00577 }
00578
00579 c->clearFlag (Cell::Flag_Progress);
00580 return;
00581 }
00582
00583 c->setFlag (Cell::Flag_Progress);
00584
00585
00586 c->setCalcDirtyFlag();
00587
00588
00589 c->calc (false);
00590
00591
00592 c->clearFlag (Cell::Flag_Progress);
00593 }
00594
00595 Point DependencyList::leadingCell (const Point &cell) const
00596 {
00597 Point c;
00598 c.setRow (cell.row() - cell.row() % CELLCHUNK_ROWS + 1);
00599 c.setColumn (cell.column() - cell.column() % CELLCHUNK_COLS + 1);
00600 c.setSheet(cell.sheet());
00601 return c;
00602 }
00603
00604 QValueList<Point> DependencyList::leadingCells (const Range &range) const
00605 {
00606 QValueList<Point> cells;
00607 Point cell1, cell2, cell;
00608
00609 cell1.setRow (range.startRow());
00610 cell1.setColumn (range.startCol());
00611 cell2.setRow (range.endRow());
00612 cell2.setColumn (range.endCol());
00613 cell1.setSheet(range.sheet());
00614 cell2.setSheet(range.sheet());
00615
00616 cell1 = leadingCell (cell1);
00617 cell2 = leadingCell (cell2);
00618 for (int row = cell1.row(); row <= cell2.row(); row += CELLCHUNK_ROWS)
00619 for (int col = cell1.column(); col <= cell2.column();
00620 col += CELLCHUNK_COLS)
00621 {
00622 cell.setRow (row);
00623 cell.setColumn (col);
00624 cell.setSheet(range.sheet());
00625 cells.push_back (cell);
00626 }
00627 return cells;
00628 }
00629
00630 RangeList DependencyList::computeDependencies (const Point &cell) const
00631 {
00632 Cell *c = cell.cell();
00633
00634
00635 if (!c->isFormula())
00636 return RangeList();
00637
00638
00639
00640 if (c->hasError())
00641 return RangeList();
00642
00643 Formula* f = c->formula();
00644 Q_ASSERT(f);
00645 if (f==NULL)
00646 {
00647 kdDebug() << "Cell at row " << cell.row() << ", col " << cell.column() << " marked as formula, but formula is NULL" << endl;
00648 return RangeList();
00649 }
00650
00651 Tokens tokens = f->tokens();
00652
00653
00654 if (!tokens.valid())
00655 return RangeList();
00656
00657 RangeList rl;
00658 for( unsigned i = 0; i < tokens.count(); i++ )
00659 {
00660 Token token = tokens[i];
00661 Token::Type tokenType = token.type();
00662
00663
00664 if (tokenType == Token::Cell)
00665 {
00666 QString text = token.text();
00667 Point cell (text, sheet->workbook(), sheet);
00668 if (cell.isValid())
00669 rl.cells.push_back (cell);
00670 }
00671 else if (tokenType == Token::Range)
00672 {
00673 QString text = token.text();
00674 Range range (text, sheet->workbook(), sheet);
00675 if (range.isValid())
00676 rl.ranges.push_back (range);
00677 }
00678 }
00679
00680 return rl;
00681 }
00682
|