kspread

dependencies.cc

00001 /* This file is part of the KDE project
00002    Copyright 2004 Tomas Mecir <mecirt@gmail.com>
00003 
00004    This library is free software; you can redistribute it and/or
00005    modify it under the terms of the GNU Library General Public
00006    License as published by the Free Software Foundation; either
00007    version 2 of the License, or (at your option) any later version.
00008 
00009    This library is distributed in the hope that it will be useful,
00010    but WITHOUT ANY WARRANTY; without even the implied warranty of
00011    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012    Library General Public License for more details.
00013 
00014    You should have received a copy of the GNU Library General Public License
00015    along with this library; see the file COPYING.LIB.  If not, write to
00016    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00017  * Boston, MA 02110-1301, USA.
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 //rows x cols in one cell-chunk; bigger values lead to slower updating
00031 //of range-dependencies, lower values will increase memory usage
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 } // namespace KSpread
00117 
00118 using namespace KSpread;
00119 
00120 // This is currently not called - but it's really convenient to call it from
00121 // gdb or from debug output to check that everything is set up ok.
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   // empty or default cell? do nothing
00216   if( c->isDefault() )
00217     return;
00218 
00219   //if the cell contains the circle error, we mustn't do anything
00220   if (c->testFlag (Cell::Flag_CircularCalculation))
00221     return;
00222 
00223   //don't re-generate dependencies if we're updating dependencies
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   //look if the cell has any dependencies
00234   if (!dependencies.contains (cell))
00235     return rl;  //it doesn't - return an empty list
00236 
00237   //the cell does have dependencies - return them!
00238   return dependencies[cell];
00239 }
00240 
00241 QValueList<Point> DependencyList::getDependants (const Point &cell)
00242 {
00243   //cell dependencies go first
00244   QValueList<Point> list = getCellDeps( cell );
00245   //next, append range dependencies
00246   Point leading = leadingCell (cell);
00247   QValueList<RangeDependency>::iterator it;
00248   if (!rangeDeps.count (leading))
00249     return list;  //no range dependencies in this cell chunk -> nothing more to do
00250 
00251   for (it = rangeDeps[leading].begin();
00252       it != rangeDeps[leading].end(); ++it)
00253   {
00254     //process all range dependencies, and for each range including the questioned cell,
00255     //add the depending cell to the list
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   // since area names are something like aliases, modifying an area name
00272   // basically means that all cells referencing this area should be treated
00273   // as modified - that will retrieve updated area ranges and also update
00274   // everything as necessary ...
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     // this forces the cell to regenerate everything - new range dependencies
00283     // and so on
00284     c->setValue (c->value ());
00285   }
00286 }
00287 
00288 void DependencyList::addDependency (const Point &cell1,
00289     const Point &cell2)
00290 {
00291   //cell2 can be in another sheet (inter-sheet dependency)
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   //target range can be in another sheet (inter-sheet dependency)
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   // the target range could be a named area ...
00319   if (!rd.range.namedArea().isNull())
00320     areaDeps[rd.range.namedArea()][cell] = true;
00321 }
00322 
00323 void DependencyList::removeDependencies (const Point &cell)
00324 {
00325   //look if the cell has any dependencies
00326   if (!dependencies.contains (cell))
00327     return;  //it doesn't - nothing more to do
00328 
00329   //first we remove cell-dependencies
00330   QValueList<Point> cells = dependencies[cell].cells;
00331   QValueList<Point>::iterator it1;
00332   for (it1 = cells.begin(); it1 != cells.end(); ++it1)
00333   {
00334     //get sheet-pointer - needed to handle inter-sheet dependencies correctly
00335     Sheet *sh = (*it1).sheet();
00336     if (!sh)
00337       sh = sheet;
00338 
00339     if (!sh->dependencies()->deps->cellDeps.contains (*it1))
00340       continue;  //this should never happen
00341 
00342     //we no longer depend on this cell
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   //then range-dependencies are removed
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     //we construct a list of cell-chunks containing a range and merge it
00356     //with lists generated from all previous ranges (duplicates are removed)
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     //get sheet-pointer - needed to handle inter-sheet dependencies correctly
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       //erase all range dependencies of this cell in this cell-chunk
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       //erase the list if we no longer need it
00381       if (sh->dependencies()->deps->rangeDeps[*it1].empty())
00382         sh->dependencies()->deps->rangeDeps.erase (*it1);
00383     }
00384   }
00385 
00386   // remove information about named area dependencies
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   // finally, remove the entry about this cell
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   //get rid of old dependencies first
00402   removeDependencies (cell);
00403 
00404   //new dependencies only need to be generated if the cell contains a formula
00405   Cell *c = sheet->cellAt (cell.column(), cell.row());
00406   if( c->isDefault() )
00407     return;
00408   if (!c->isFormula())
00409     return;
00410 
00411   //now we need to generate dependencies
00412   RangeList rl = computeDependencies (cell);
00413 
00414   //now that we have the new dependencies, we put them into our data structures
00415   //and we're done
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;  //no range dependencies in this cell chunk
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     //process all range dependencies, and for each range including the modified cell,
00483     //recalc the depending cell
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   //each cell's dependencies need to be updated - that cannot be helped - having a range
00498   //only helps with range dependencies
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   //TODO: some optimization, so that we don't recompute cells depending of huge
00520   //ranges more than once (now we recompute them once per cell-chunk used by their dependency)
00521   //This will probably happen as a part of splitting this into dep manager
00522   //and recalc manager
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;  //no range dependencies in this cell chunk
00530     QValueList<RangeDependency>::iterator it2;
00531     for (it2 = rangeDeps[*it].begin(); it2 != rangeDeps[*it].end(); ++it2)
00532     {
00533       //process all range dependencies, and for each range intersecting with our range,
00534       //recalc the depending cell
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   //prevent infinite recursion (circular dependencies)
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     // don't set anything if the cell already has all these things set
00569     // this prevents endless loop for inter-sheet curcular dependencies,
00570     // where the usual mechanisms fail doe to having multiple dependency
00571     // managers ...
00572     if (!c->testFlag (Cell::Flag_CircularCalculation))
00573     {
00574       c->setFlag(Cell::Flag_CircularCalculation);
00575       v.setError ( "####" );
00576       c->setValue (v);
00577     }
00578     //clear the computing-dependencies flag
00579     c->clearFlag (Cell::Flag_Progress);
00580     return;
00581   }
00582   //set the computing-dependencies flag
00583   c->setFlag (Cell::Flag_Progress);
00584 
00585   //mark the cell as calc-dirty
00586   c->setCalcDirtyFlag();
00587 
00588   //recalculate the cell
00589   c->calc (false);
00590 
00591   //clear the computing-dependencies flag
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   // Not a formula -> no dependencies
00635   if (!c->isFormula())
00636     return RangeList();
00637 
00638   // Broken formula -> meaningless dependencies
00639   // (tries to avoid c->formula() being null)
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   //return empty list if the tokens aren't valid
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     //parse each cell/range and put it to our RangeList
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 
KDE Home | KDE Accessibility Home | Description of Access Keys