kspread Library API Documentation

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., 59 Temple Place - Suite 330,
00017    Boston, MA 02111-1307, 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 (KSpreadSheet *s);
00042   ~DependencyList () { reset (); };
00044   void reset ();
00045   
00047   void generateDependencies (const KSpreadPoint &cell);
00049   void generateDependencies (const KSpreadRange &range);
00051   void generateDependencies (const RangeList &rangeList);
00052 
00054   void processDependencies (const KSpreadPoint &cell);
00056   void processDependencies (const KSpreadRange &range);
00058   void processDependencies (const RangeList &rangeList);
00059 
00061   RangeList getDependencies (const KSpreadPoint &cell);
00063   QValueList<KSpreadPoint> getDependants (const KSpreadPoint &cell);
00064 
00065  protected:
00067   void addDependency (const KSpreadPoint &cell1, const KSpreadPoint &cell2);
00069   void addRangeDependency (const RangeDependency &rd);
00071   void removeDependencies (const KSpreadPoint &cell);
00072   
00074   void processRangeDependencies (const KSpreadPoint &cell);
00075 
00077   void processRangeDependencies (const KSpreadRange &range);
00078   
00080   void updateCell (const KSpreadPoint &cell) const;
00081 
00084   KSpreadPoint leadingCell (const KSpreadPoint &cell) const;
00086   QValueList<KSpreadPoint> leadingCells (const KSpreadRange &range) const;
00088   RangeList computeDependencies (const KSpreadPoint &cell) const;
00089   
00091   KSpreadSheet *sheet;
00092   
00094   QMap<KSpreadPoint, RangeList> dependencies;
00096   QMap<KSpreadPoint, QValueList<KSpreadPoint> > cellDeps;
00098   QMap<KSpreadPoint, QValueList<RangeDependency> > rangeDeps;
00099 };
00100 
00101 }
00102 
00103 using namespace KSpread;
00104 
00105 DependencyManager::DependencyManager (KSpreadSheet *s)
00106 {
00107   deps = new DependencyList (s);
00108 }
00109 
00110 DependencyManager::~DependencyManager ()
00111 {
00112   delete deps;
00113   deps = 0;
00114 }
00115 
00116 void DependencyManager::reset ()
00117 {
00118   deps->reset();
00119 }
00120 
00121 void DependencyManager::cellChanged (const KSpreadPoint &cell)
00122 {
00123   KSpreadCell *c = cell.cell();
00124   
00125   // empty or default cell? do nothing
00126   if( c->isDefault() )
00127     return;
00128   
00129   //if the cell contains the circle error, we mustn't do anything
00130   if (c->testFlag (KSpreadCell::Flag_CircularCalculation))
00131     return;
00132   
00133   //kdDebug(36001) << "updating dependencies for cell (" <<
00134   //    c->row() << "," << c->column() << ")" << endl;
00135   
00136   //don't re-generate dependencies if we're updating dependencies
00137   if ( !(c->testFlag (KSpreadCell::Flag_Progress)))
00138     deps->generateDependencies (cell);
00139 
00140   deps->processDependencies (cell);
00141 }
00142 
00143 void DependencyManager::rangeChanged (const KSpreadRange &range)
00144 {
00145   deps->generateDependencies (range);
00146   deps->processDependencies (range);
00147 }
00148 
00149 void DependencyManager::rangeListChanged (const RangeList &rangeList)
00150 {
00151   deps->generateDependencies (rangeList);
00152   deps->processDependencies (rangeList);
00153 }
00154 
00155 RangeList DependencyManager::getDependencies (const KSpreadPoint &cell)
00156 {
00157   return deps->getDependencies (cell);
00158 }
00159 
00160 QValueList<KSpreadPoint> DependencyManager::getDependants (const KSpreadPoint &cell)
00161 {
00162   return deps->getDependants (cell);
00163 }
00164 
00165 DependencyList::DependencyList (KSpreadSheet *s)
00166     : sheet (s)
00167 {
00168 }
00169 
00170 void DependencyList::reset ()
00171 {
00172   dependencies.clear();
00173   cellDeps.clear();
00174   rangeDeps.clear();
00175 }
00176 
00177 RangeList DependencyList::getDependencies (const KSpreadPoint &cell)
00178 {
00179   RangeList rl;
00180   //look if the cell has any dependencies
00181   if (!dependencies.contains (cell))
00182     return rl;  //it doesn't - return an empty list
00183   
00184   //the cell does have dependencies - return them!
00185   return dependencies[cell];
00186 }
00187 
00188 QValueList<KSpreadPoint> DependencyList::getDependants (const KSpreadPoint &cell)
00189 {
00190   QValueList<KSpreadPoint> list;
00191   
00192   //cell dependencies go first
00193   if (cellDeps.contains (cell))
00194     list = cellDeps[cell];
00195   
00196   //next, append range dependencies
00197   KSpreadPoint leading = leadingCell (cell);
00198   QValueList<RangeDependency>::iterator it;
00199   if (!rangeDeps.count (leading))
00200     return list;  //no range dependencies in this cell chunk -> nothing more to do
00201   
00202   for (it = rangeDeps[leading].begin();
00203       it != rangeDeps[leading].end(); ++it)
00204   {
00205     //process all range dependencies, and for each range including the questioned cell,
00206     //add the depending cell to the list
00207     if ((*it).range.contains (cell))
00208     {
00209       KSpreadPoint c;
00210       c.setRow ((*it).cellrow);
00211       c.setColumn ((*it).cellcolumn);
00212       c.sheet = (*it).cellsheet;
00213       list.push_back (c);
00214     }
00215   }
00216   
00217   return list;
00218 }
00219 
00220 void DependencyList::addDependency (const KSpreadPoint &cell1,
00221     const KSpreadPoint &cell2)
00222 {
00223   //kdDebug(36001) << "Dep. manager: added a dependency" << endl;
00224   
00225   //cell2 can be in another sheet (inter-sheet dependency)
00226   KSpreadSheet *sh = cell2.sheet;
00227   if (!sh)
00228     sh = sheet;
00229 
00230   dependencies[cell1].cells.push_back (cell2);
00231   sh->dependencies()->deps->cellDeps[cell2].push_back (cell1);
00232 }
00233 
00234 void DependencyList::addRangeDependency (const RangeDependency &rd)
00235 {
00236   //target range can be in another sheet (inter-sheet dependency)
00237   KSpreadSheet *sh = rd.range.sheet;
00238   if (!sh)
00239     sh = sheet;
00240   
00241   KSpreadPoint cell;
00242   cell.sheet = rd.cellsheet;
00243   cell.setRow (rd.cellrow);
00244   cell.setColumn (rd.cellcolumn);
00245   dependencies[cell].ranges.push_back (rd.range);
00246   
00247   QValueList<KSpreadPoint> leadings = leadingCells (rd.range);
00248   QValueList<KSpreadPoint>::iterator it;
00249   for (it = leadings.begin(); it != leadings.end(); ++it)
00250     sh->dependencies()->deps->rangeDeps[*it].push_back (rd);
00251 }
00252 
00253 void DependencyList::removeDependencies (const KSpreadPoint &cell)
00254 {
00255   //look if the cell has any dependencies
00256   if (!dependencies.contains (cell))
00257     return;  //it doesn't - nothing more to do
00258   
00259   //first we remove cell-dependencies
00260   QValueList<KSpreadPoint> cells = dependencies[cell].cells;
00261   QValueList<KSpreadPoint>::iterator it1;
00262   for (it1 = cells.begin(); it1 != cells.end(); ++it1)
00263   {
00264     //get sheet-pointer - needed to handle inter-sheet dependencies correctly
00265     KSpreadSheet *sh = (*it1).sheet;
00266     if (!sh)
00267       sh = sheet;
00268     
00269     if (!sh->dependencies()->deps->cellDeps.contains (*it1))
00270       continue;  //this should never happen
00271     
00272     //we no longer depend on this cell
00273     QValueList<KSpreadPoint>::iterator cit;
00274     cit = sh->dependencies()->deps->cellDeps[*it1].find (cell);
00275     if (cit != sh->dependencies()->deps->cellDeps[*it1].end())
00276       sh->dependencies()->deps->cellDeps[*it1].erase (cit);
00277   }
00278   
00279   //then range-dependencies are removed
00280   QValueList<KSpreadRange> ranges = dependencies[cell].ranges;
00281   QValueList<KSpreadRange>::iterator it2;
00282   QValueList<KSpreadPoint> leads;
00283   for (it2 = ranges.begin(); it2 != ranges.end(); ++it2)
00284   {
00285     //we construct a list of cell-chunks containing a range and merge it
00286     //with lists generated from all previous ranges (duplicates are removed)
00287     QValueList<KSpreadPoint> leadings = leadingCells (*it2);
00288     for (it1 = leadings.begin(); it1 != leadings.end(); ++it1)
00289       if (!leads.contains (*it1))
00290         leads.push_back (*it1);
00291   }
00292   for (it1 = leads.begin(); it1 != leads.end(); ++it1)
00293   {
00294     //get sheet-pointer - needed to handle inter-sheet dependencies correctly
00295     KSpreadSheet *sh = (*it1).sheet;
00296     if (!sh)
00297       sh = sheet;
00298 
00299     if (sh->dependencies()->deps->rangeDeps.contains (*it1))
00300     {
00301       QValueList<RangeDependency>::iterator it3;
00302       QValueList<RangeDependency> rdeps =
00303           sh->dependencies()->deps->rangeDeps[*it1];
00304       it3 = rdeps.begin();
00305       //erase all range dependencies of this cell in this cell-chunk
00306       while (it3 != rdeps.end())
00307         if (((*it3).cellrow == cell.row()) &&
00308             ((*it3).cellcolumn == cell.column()))
00309           it3 = rdeps.erase (it3);
00310         else
00311           ++it3;
00312       //erase the list if we no longer need it
00313       if (rdeps.empty())
00314         sh->dependencies()->deps->rangeDeps.erase (*it1);
00315     }
00316   }
00317   
00318   //finally, remove the entry about this cell
00319   dependencies[cell].cells.clear();
00320   dependencies[cell].ranges.clear();
00321   dependencies.erase (cell);
00322 }
00323 
00324 void DependencyList::generateDependencies (const KSpreadPoint &cell)
00325 {
00326   //get rid of old dependencies first
00327   removeDependencies (cell);
00328 
00329   //new dependencies only need to be generated if the cell contains a formula
00330   KSpreadCell *c = sheet->cellAt (cell.column(), cell.row());
00331   if( c->isDefault() )
00332     return;
00333   if (!c->isFormula())
00334     return;
00335   
00336   //now we need to generate dependencies
00337   RangeList rl = computeDependencies (cell);
00338   
00339   //now that we have the new dependencies, we put them into our data structures
00340   //and we're done
00341   QValueList<KSpreadPoint>::iterator it1;
00342   QValueList<KSpreadRange>::iterator it2;
00343   
00344   for (it1 = rl.cells.begin(); it1 != rl.cells.end(); ++it1)
00345     addDependency (cell, *it1);
00346   for (it2 = rl.ranges.begin(); it2 != rl.ranges.end(); ++it2)
00347   {
00348     RangeDependency rd;
00349     rd.cellrow = cell.row();
00350     rd.cellcolumn = cell.column();
00351     rd.cellsheet = sheet;
00352     rd.range = *it2;
00353     if (rd.range.sheet == 0) rd.range.sheet = sheet;
00354     addRangeDependency (rd);
00355   }
00356 }
00357 
00358 void DependencyList::generateDependencies (const KSpreadRange &range)
00359 {
00360   for (int row = range.startRow(); row <= range.endRow(); row++)
00361     for (int col = range.startCol(); col <= range.endCol(); col++)
00362     {
00363       KSpreadPoint c;
00364       c.setRow (row);
00365       c.setColumn (col);
00366       c.sheet = sheet;
00367       generateDependencies (c);
00368     }
00369 }
00370 
00371 void DependencyList::generateDependencies (const RangeList &rangeList)
00372 {
00373   QValueList<KSpreadPoint>::const_iterator it1;
00374   QValueList<KSpreadRange>::const_iterator it2;
00375   
00376   for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
00377     generateDependencies (*it1);
00378   for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
00379     generateDependencies (*it2);
00380 }
00381 
00382 void DependencyList::processDependencies (const KSpreadPoint &cell)
00383 {
00384   if (cellDeps.contains (cell))
00385   {
00386     QValueList<KSpreadPoint> d = cellDeps[cell];
00387     QValueList<KSpreadPoint>::iterator it;
00388     for (it = d.begin(); it != d.end(); ++it)
00389       updateCell (*it);
00390   }
00391   
00392   processRangeDependencies (cell);
00393 }
00394 
00395 void DependencyList::processRangeDependencies (const KSpreadPoint &cell)
00396 {
00397   KSpreadPoint leading = leadingCell (cell);
00398   QValueList<RangeDependency>::iterator it;
00399   if (!rangeDeps.count (leading))
00400     return;  //no range dependencies in this cell chunk
00401 
00402   for (it = rangeDeps[leading].begin();
00403       it != rangeDeps[leading].end(); ++it)
00404   {
00405     //process all range dependencies, and for each range including the modified cell,
00406     //recalc the depending cell
00407     if ((*it).range.contains (cell))
00408     {
00409       KSpreadPoint c;
00410       c.setRow ((*it).cellrow);
00411       c.setColumn ((*it).cellcolumn);
00412       c.sheet = (*it).cellsheet;
00413       updateCell (c);
00414     }
00415   }
00416 }
00417 
00418 void DependencyList::processDependencies (const KSpreadRange &range)
00419 {
00420   //each cell's dependencies need to be updated - that cannot be helped - having a range
00421   //only helps with range dependencies
00422   for (int row = range.startRow(); row <= range.endRow(); row++)
00423     for (int col = range.startCol(); col <= range.endCol(); col++)
00424     {
00425       KSpreadPoint c;
00426       c.setRow (row);
00427       c.setColumn (col);
00428       c.sheet = sheet;
00429       if (cellDeps.contains (c))
00430       {
00431         QValueList<KSpreadPoint> d = cellDeps[c];
00432         QValueList<KSpreadPoint>::iterator it;
00433         for (it = d.begin(); it != d.end(); ++it)
00434           updateCell (*it);
00435       }
00436     }
00437   
00438   processRangeDependencies (range);
00439 }
00440 
00441 void DependencyList::processRangeDependencies (const KSpreadRange &range)
00442 {
00443   //TODO: some optimization, so that we don't recompute cells depending of huge
00444   //ranges more than once (now we recompute them once per cell-chunk used by their dependency)
00445   //This will probably happen as a part of splitting this into dep manager
00446   //and recalc manager
00447   
00448   QValueList<KSpreadPoint> leadings = leadingCells (range);
00449   QValueList<KSpreadPoint>::iterator it;
00450   for (it = leadings.begin(); it != leadings.end(); ++it)
00451   {
00452     if (!rangeDeps.count (*it))
00453       continue;  //no range dependencies in this cell chunk
00454     QValueList<RangeDependency>::iterator it2;
00455     for (it2 = rangeDeps[*it].begin(); it2 != rangeDeps[*it].end(); ++it2)
00456     {
00457       //process all range dependencies, and for each range intersecting with our range,
00458       //recalc the depending cell
00459       if ((*it2).range.intersects (range))
00460       {
00461         KSpreadPoint c;
00462         c.setRow ((*it2).range.startRow());
00463         c.setColumn ((*it2).range.startCol());
00464         c.sheet = sheet;
00465         updateCell (c);
00466       }
00467     }
00468   }
00469 }
00470 
00471 void DependencyList::processDependencies (const RangeList &rangeList)
00472 {
00473   QValueList<KSpreadPoint>::const_iterator it1;
00474   QValueList<KSpreadRange>::const_iterator it2;
00475   
00476   for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
00477     processDependencies (*it1);
00478   for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
00479     processDependencies (*it2);
00480 }
00481 
00482 void DependencyList::updateCell (const KSpreadPoint &cell) const
00483 {
00484   KSpreadCell *c = cell.cell();
00485 
00486   //prevent infinite recursion (circular dependencies)
00487   if (c->testFlag (KSpreadCell::Flag_Progress))
00488   {
00489     kdError(36001) << "ERROR: Circle" << endl;
00490     c->setFlag(KSpreadCell::Flag_CircularCalculation);
00491     KSpreadValue v;
00492     v.setError ( "####" );
00493     c->setValue (v);
00494     //clear the computing-dependencies flag
00495     c->clearFlag (KSpreadCell::Flag_Progress);
00496     return;
00497   }
00498   //kdDebug() << "Updating depending cell (" <<
00499   //    c->row() << "," << c->column() << ")" << endl;
00500   //set the computing-dependencies flag
00501   c->setFlag (KSpreadCell::Flag_Progress);
00502   
00503   //mark the cell as calc-dirty
00504   c->setCalcDirtyFlag();
00505   
00506   //recalculate the cell
00507   c->calc (false);
00508   
00509   //clear the computing-dependencies flag
00510   c->clearFlag (KSpreadCell::Flag_Progress);
00511 }
00512 
00513 KSpreadPoint DependencyList::leadingCell (const KSpreadPoint &cell) const
00514 {
00515   KSpreadPoint c;
00516   c.setRow (cell.row() - cell.row() % CELLCHUNK_ROWS + 1);
00517   c.setColumn (cell.column() - cell.column() % CELLCHUNK_COLS + 1);
00518   c.sheet = cell.sheet;
00519   return c;
00520 }
00521 
00522 QValueList<KSpreadPoint> DependencyList::leadingCells (const KSpreadRange &range) const
00523 {
00524   QValueList<KSpreadPoint> cells;
00525   KSpreadPoint cell1, cell2, cell;
00526   
00527   cell1.setRow (range.startRow());
00528   cell1.setColumn (range.startCol());
00529   cell2.setRow (range.endRow());
00530   cell2.setColumn (range.endCol());
00531   cell1.sheet = range.sheet;
00532   cell2.sheet = range.sheet;
00533   
00534   cell1 = leadingCell (cell1);
00535   cell2 = leadingCell (cell2);
00536   for (int row = cell1.row(); row <= cell2.row(); row += CELLCHUNK_ROWS)
00537     for (int col = cell1.column(); col <= cell2.column();
00538         col += CELLCHUNK_COLS)
00539     {
00540       cell.setRow (row);
00541       cell.setColumn (col);
00542       cell.sheet = range.sheet;
00543       cells.push_back (cell);
00544     }
00545   return cells;
00546 }
00547 
00548 RangeList DependencyList::computeDependencies (const KSpreadPoint &cell) const
00549 {
00550   KSpreadCell *c = cell.cell();
00551   if (!c->isFormula())
00552     return RangeList();   //not a formula -> no dependencies
00553 
00554   QString expr = c->text();
00555 
00556   //TODO: when the new parser is in use, KSpreadCell will hold a Formula
00557   //instance, hence we'll be able to use that one directly
00558   Tokens tokens = Formula::scan( expr );
00559 
00560   //return empty list if the tokens aren't valid
00561   if (!tokens.valid())
00562     return RangeList();
00563 
00564   kdDebug(36001) << "Retrieving dependencies for cell with text \"" << expr << "\"" << endl;
00565 
00566   RangeList rl;
00567   for( unsigned i = 0; i < tokens.count(); i++ )
00568   {
00569     Token token = tokens[i];
00570     Token::Type tokenType = token.type();
00571 
00572     //parse each cell/range and put it to our RangeList
00573     if (tokenType == Token::Cell)
00574     {
00575       QString text = token.text();
00576       KSpreadPoint cell (text, sheet->workbook(), sheet);
00577       if (cell.isValid())
00578         rl.cells.push_back (cell);
00579     }
00580     else if (tokenType == Token::Range)
00581     {
00582       QString text = token.text();
00583       KSpreadRange range (text, sheet->workbook(), sheet);
00584       if (range.isValid())
00585         rl.ranges.push_back (range);
00586     }
00587   }
00588   
00589   return rl;
00590 }
00591 
KDE Logo
This file is part of the documentation for kspread Library Version 1.4.2.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Mon Feb 13 09:42:44 2006 by doxygen 1.4.2 written by Dimitri van Heesch, © 1997-2003