1 files changed, 682 insertions, 0 deletions
diff --git a/kspread/dependencies.cpp b/kspread/dependencies.cpp
new file mode 100644
index 000000000..66bbe61a1
--- /dev/null
+++ b/kspread/dependencies.cpp
@@ -0,0 +1,682 @@
+/* This file is part of the KDE project
+   Copyright 2004 Tomas Mecir <mecirt@gmail.com>
+
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+
+   You should have received a copy of the GNU Library General Public License
+   along with this library; see the file COPYING.LIB.  If not, write to
+   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+*/
+
+
+#include "dependencies.h"
+
+#include "formula.h"
+
+#include "kspread_cell.h"
+#include "kspread_sheet.h"
+
+#include <tqmap.h>
+
+//rows x cols in one cell-chunk; bigger values lead to slower updating
+//of range-dependencies, lower values will increase memory usage
+#define CELLCHUNK_ROWS 128
+#define CELLCHUNK_COLS 16
+
+namespace KSpread {
+
+
+/** d-pointer of DependencyManager */
+class DependencyList {
+ public:
+  DependencyList (Sheet *s);
+  ~DependencyList () { reset (); };
+  /** clear internal structures */
+  void reset ();
+
+  /** handle the fact that a cell has been changed */
+  void cellChanged (const Point &cell);
+
+  /** generate list of dependencies of a cell */
+  void generateDependencies (const Point &cell);
+  /** generate list of dependencies of a range */
+  void generateDependencies (const Range &range);
+  /** generate list of dependencies of a range list */
+  void generateDependencies (const RangeList &rangeList);
+
+  /** update cells dependending on a given cell */
+  void processDependencies (const Point &cell);
+  /** update cells dependending on a cell in a given range */
+  void processDependencies (const Range &range);
+  /** update cells dependending on a given range-list */
+  void processDependencies (const RangeList &rangeList);
+
+  /** get dependencies of a cell */
+  RangeList getDependencies (const Point &cell);
+  /** get cells depending on this cell, either through normal or range dependency */
+  TQValueList<Point> getDependants (const Point &cell);
+
+  void areaModified (const TQString &name);
+  protected:
+  /** update structures: cell 1 depends on cell 2 */
+  void addDependency (const Point &cell1, const Point &cell2);
+  /** update structures: cell depends on a range */
+  void addRangeDependency (const RangeDependency &rd);
+  /** remove all dependencies of a cell */
+  void removeDependencies (const Point &cell);
+
+  /** update all cells depending on a range containing this cell */
+  void processRangeDependencies (const Point &cell);
+
+  /** update all cells depending on a range intersecting with this range */
+  void processRangeDependencies (const Range &range);
+
+  /** update one cell due to changed dependencies */
+  void updateCell (const Point &cell) const;
+
+  /** return a leading cell for a given cell (used to store range
+  dependencies effectively) */
+  Point leadingCell (const Point &cell) const;
+  /** list of leading cells of all cell chunks that this range belongs to */
+  TQValueList<Point> leadingCells (const Range &range) const;
+  /** retrieve a list of cells that a given cell depends on */
+  RangeList computeDependencies (const Point &cell) const;
+
+  TQValueList<Point> getCellDeps(const Point& cell) const {
+      CellDepsMap::const_iterator it = cellDeps.find( cell );
+      return it == cellDeps.end() ? TQValueList<Point>() : *it;
+  }
+
+  /** debug */
+  void dump();
+
+  /** Sheet whose dependencies are managed by this instance */
+  Sheet *sheet;
+
+  /** dependencies of each cell */
+  TQMap<Point, RangeList> dependencies;
+  /** list of cells (but NOT ranges) that depend on a cell */
+  typedef TQMap<Point, TQValueList<Point> > CellDepsMap;
+  CellDepsMap cellDeps;
+  /** all range dependencies splitted into cell-chunks (TODO: describe) */
+  TQMap<Point, TQValueList<RangeDependency> > rangeDeps;
+  /** list of cells referencing a given named area */
+  TQMap<TQString, TQMap<Point, bool> > areaDeps;
+};
+
+} // namespace KSpread
+
+using namespace KSpread;
+
+// This is currently not called - but it's really convenient to call it from
+// gdb or from debug output to check that everything is set up ok.
+void DependencyList::dump()
+{
+  TQMap<Point, RangeList>::const_iterator it = dependencies.begin();
+  for ( ; it != dependencies.end(); ++it ) {
+    Point p = it.key();
+    kdDebug() << "Cell " << p.sheetName() << " " << p.pos()
+              << " depends on :" << endl;
+    RangeList rl = (*it);
+    TQValueList<Point>::const_iterator itp = rl.cells.begin();
+    for ( ; itp != rl.cells.end(); ++itp )
+      kdDebug() << "  cell " << (*itp).pos() << endl;
+    TQValueList<Range>::const_iterator itr = rl.ranges.begin();
+    for ( ; itr != rl.ranges.end(); ++itr )
+      kdDebug() << "  range " << (*itr).toString() << endl;
+  }
+
+  CellDepsMap::const_iterator cit = cellDeps.begin();
+  for ( ; cit != cellDeps.end(); ++cit )
+  {
+    Point p = cit.key();
+    kdDebug() << "The cells that depend on " << p.sheetName() << " " << p.pos()
+              << " are :" << endl;
+    TQValueList<Point>::const_iterator itp = (*cit).begin();
+    for ( ; itp != (*cit).end(); ++itp )
+      kdDebug() << "  cell " << (*itp).pos() << endl;
+  }
+
+}
+
+DependencyManager::DependencyManager (Sheet *s)
+{
+  deps = new DependencyList (s);
+}
+
+DependencyManager::~DependencyManager ()
+{
+  delete deps;
+  deps = 0;
+}
+
+void DependencyManager::reset ()
+{
+  deps->reset();
+}
+
+void DependencyManager::cellChanged (const Point &cell)
+{
+  deps->cellChanged (cell);
+}
+
+void DependencyManager::rangeChanged (const Range &range)
+{
+  deps->generateDependencies (range);
+  deps->processDependencies (range);
+}
+
+void DependencyManager::rangeListChanged (const RangeList &rangeList)
+{
+  deps->generateDependencies (rangeList);
+  deps->processDependencies (rangeList);
+}
+
+void DependencyManager::areaModified (const TQString &name)
+{
+  deps->areaModified (name);
+}
+
+RangeList DependencyManager::getDependencies (const Point &cell)
+{
+  return deps->getDependencies (cell);
+}
+
+TQValueList<Point> DependencyManager::getDependants (const Point &cell)
+{
+  return deps->getDependants (cell);
+}
+
+DependencyList::DependencyList (Sheet *s)
+    : sheet (s)
+{
+}
+
+void DependencyList::reset ()
+{
+  dependencies.clear();
+  cellDeps.clear();
+  rangeDeps.clear();
+}
+
+void DependencyList::cellChanged (const Point &cell)
+{
+  Cell *c = cell.cell();
+
+  // empty or default cell? do nothing
+  if( c->isDefault() )
+    return;
+
+  //if the cell contains the circle error, we mustn't do anything
+  if (c->testFlag (Cell::Flag_CircularCalculation))
+    return;
+
+  //don't re-generate dependencies if we're updating dependencies
+  if ( !(c->testFlag (Cell::Flag_Progress)))
+    generateDependencies (cell);
+
+  processDependencies (cell);
+}
+
+RangeList DependencyList::getDependencies (const Point &cell)
+{
+  RangeList rl;
+  //look if the cell has any dependencies
+  if (!dependencies.contains (cell))
+    return rl;  //it doesn't - return an empty list
+
+  //the cell does have dependencies - return them!
+  return dependencies[cell];
+}
+
+TQValueList<Point> DependencyList::getDependants (const Point &cell)
+{
+  //cell dependencies go first
+  TQValueList<Point> list = getCellDeps( cell );
+  //next, append range dependencies
+  Point leading = leadingCell (cell);
+  TQValueList<RangeDependency>::iterator it;
+  if (!rangeDeps.count (leading))
+    return list;  //no range dependencies in this cell chunk -> nothing more to do
+
+  for (it = rangeDeps[leading].begin();
+      it != rangeDeps[leading].end(); ++it)
+  {
+    //process all range dependencies, and for each range including the questioned cell,
+    //add the depending cell to the list
+    if ((*it).range.contains (cell))
+    {
+      Point c;
+      c.setRow ((*it).cellrow);
+      c.setColumn ((*it).cellcolumn);
+      c.setSheet ( (*it).cellsheet );
+      list.push_back (c);
+    }
+  }
+
+  return list;
+}
+
+void DependencyList::areaModified (const TQString &name)
+{
+  // since area names are something like aliases, modifying an area name
+  // basically means that all cells referencing this area should be treated
+  // as modified - that will retrieve updated area ranges and also update
+  // everything as necessary ...
+  if (!areaDeps.contains (name))
+    return;
+
+  TQMap<Point, bool>::iterator it;
+  for (it = areaDeps[name].begin(); it != areaDeps[name].end(); ++it)
+  {
+    Cell *c = it.key().cell();
+    // this forces the cell to regenerate everything - new range dependencies
+    // and so on
+    c->setValue (c->value ());
+  }
+}
+
+void DependencyList::addDependency (const Point &cell1,
+    const Point &cell2)
+{
+  //cell2 can be in another sheet (inter-sheet dependency)
+  Sheet *sh = cell2.sheet();
+  if (!sh)
+    sh = sheet;
+
+  dependencies[cell1].cells.push_back (cell2);
+  sh->dependencies()->deps->cellDeps[cell2].push_back (cell1);
+}
+
+void DependencyList::addRangeDependency (const RangeDependency &rd)
+{
+  //target range can be in another sheet (inter-sheet dependency)
+  Sheet *sh = rd.range.sheet();
+  if (!sh)
+    sh = sheet;
+
+  Point cell;
+  cell.setSheet (rd.cellsheet);
+  cell.setRow (rd.cellrow);
+  cell.setColumn (rd.cellcolumn);
+  dependencies[cell].ranges.push_back (rd.range);
+
+  TQValueList<Point> leadings = leadingCells (rd.range);
+  TQValueList<Point>::iterator it;
+  for (it = leadings.begin(); it != leadings.end(); ++it)
+    sh->dependencies()->deps->rangeDeps[*it].push_back (rd);
+
+  // the target range could be a named area ...
+  if (!rd.range.namedArea().isNull())
+    areaDeps[rd.range.namedArea()][cell] = true;
+}
+
+void DependencyList::removeDependencies (const Point &cell)
+{
+  //look if the cell has any dependencies
+  if (!dependencies.contains (cell))
+    return;  //it doesn't - nothing more to do
+
+  //first we remove cell-dependencies
+  TQValueList<Point> cells = dependencies[cell].cells;
+  TQValueList<Point>::iterator it1;
+  for (it1 = cells.begin(); it1 != cells.end(); ++it1)
+  {
+    //get sheet-pointer - needed to handle inter-sheet dependencies correctly
+    Sheet *sh = (*it1).sheet();
+    if (!sh)
+      sh = sheet;
+
+    if (!sh->dependencies()->deps->cellDeps.contains (*it1))
+      continue;  //this should never happen
+
+    //we no longer depend on this cell
+    TQValueList<Point>::iterator cit;
+    cit = sh->dependencies()->deps->cellDeps[*it1].find (cell);
+    if (cit != sh->dependencies()->deps->cellDeps[*it1].end())
+      sh->dependencies()->deps->cellDeps[*it1].erase (cit);
+  }
+
+  //then range-dependencies are removed
+  TQValueList<Range> ranges = dependencies[cell].ranges;
+  TQValueList<Range>::iterator it2;
+  TQValueList<Point> leads;
+  for (it2 = ranges.begin(); it2 != ranges.end(); ++it2)
+  {
+    //we construct a list of cell-chunks containing a range and merge it
+    //with lists generated from all previous ranges (duplicates are removed)
+    TQValueList<Point> leadings = leadingCells (*it2);
+    for (it1 = leadings.begin(); it1 != leadings.end(); ++it1)
+      if (!leads.contains (*it1))
+        leads.push_back (*it1);
+  }
+  for (it1 = leads.begin(); it1 != leads.end(); ++it1)
+  {
+    //get sheet-pointer - needed to handle inter-sheet dependencies correctly
+    Sheet *sh = (*it1).sheet();
+    if (!sh)
+      sh = sheet;
+
+    if (sh->dependencies()->deps->rangeDeps.contains (*it1))
+    {
+      TQValueList<RangeDependency>::iterator it3;
+      it3 = sh->dependencies()->deps->rangeDeps[*it1].begin();
+      //erase all range dependencies of this cell in this cell-chunk
+      while (it3 != sh->dependencies()->deps->rangeDeps[*it1].end())
+        if (((*it3).cellrow == cell.row()) &&
+            ((*it3).cellcolumn == cell.column()))
+          it3 = sh->dependencies()->deps->rangeDeps[*it1].erase (it3);
+        else
+          ++it3;
+      //erase the list if we no longer need it
+      if (sh->dependencies()->deps->rangeDeps[*it1].empty())
+        sh->dependencies()->deps->rangeDeps.erase (*it1);
+    }
+  }
+
+  // remove information about named area dependencies
+  TQMap<TQString, TQMap<Point, bool> >::iterator itr;
+  for (itr = areaDeps.begin(); itr != areaDeps.end(); ++itr) {
+    if (itr.data().contains (cell))
+      itr.data().remove (cell);
+  }
+
+  // finally, remove the entry about this cell
+  dependencies[cell].cells.clear();
+  dependencies[cell].ranges.clear();
+  dependencies.erase (cell);
+}
+
+void DependencyList::generateDependencies (const Point &cell)
+{
+  //get rid of old dependencies first
+  removeDependencies (cell);
+
+  //new dependencies only need to be generated if the cell contains a formula
+  Cell *c = sheet->cellAt (cell.column(), cell.row());
+  if( c->isDefault() )
+    return;
+  if (!c->isFormula())
+    return;
+
+  //now we need to generate dependencies
+  RangeList rl = computeDependencies (cell);
+
+  //now that we have the new dependencies, we put them into our data structures
+  //and we're done
+  TQValueList<Point>::iterator it1;
+  TQValueList<Range>::iterator it2;
+
+  for (it1 = rl.cells.begin(); it1 != rl.cells.end(); ++it1)
+    addDependency (cell, *it1);
+  for (it2 = rl.ranges.begin(); it2 != rl.ranges.end(); ++it2)
+  {
+    RangeDependency rd;
+    rd.cellrow = cell.row();
+    rd.cellcolumn = cell.column();
+    rd.cellsheet = sheet;
+    rd.range = *it2;
+
+    if (rd.range.sheet() == 0)
+        rd.range.setSheet(sheet);
+
+    addRangeDependency (rd);
+  }
+}
+
+void DependencyList::generateDependencies (const Range &range)
+{
+  for (int row = range.startRow(); row <= range.endRow(); row++)
+    for (int col = range.startCol(); col <= range.endCol(); col++)
+    {
+      Point c;
+      c.setRow (row);
+      c.setColumn (col);
+      c.setSheet(sheet);
+      generateDependencies (c);
+    }
+}
+
+void DependencyList::generateDependencies (const RangeList &rangeList)
+{
+  TQValueList<Point>::const_iterator it1;
+  TQValueList<Range>::const_iterator it2;
+
+  for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
+    generateDependencies (*it1);
+  for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
+    generateDependencies (*it2);
+}
+
+void DependencyList::processDependencies (const Point &cell)
+{
+  const TQValueList<Point> d = getCellDeps(cell);
+  TQValueList<Point>::const_iterator it = d.begin();
+  const TQValueList<Point>::const_iterator end = d.end();
+  for (; it != end; ++it)
+      updateCell (*it);
+
+  processRangeDependencies (cell);
+}
+
+void DependencyList::processRangeDependencies (const Point &cell)
+{
+  Point leading = leadingCell (cell);
+  if (!rangeDeps.count (leading))
+    return;  //no range dependencies in this cell chunk
+
+  const TQValueList<RangeDependency> rd = rangeDeps[leading];
+
+  TQValueList<RangeDependency>::const_iterator it;
+  for (it = rd.begin(); it != rd.end(); ++it)
+  {
+    //process all range dependencies, and for each range including the modified cell,
+    //recalc the depending cell
+    if ((*it).range.contains (cell))
+    {
+      Point c;
+      c.setRow ((*it).cellrow);
+      c.setColumn ((*it).cellcolumn);
+      c.setSheet ( (*it).cellsheet );
+      updateCell (c);
+    }
+  }
+}
+
+void DependencyList::processDependencies (const Range &range)
+{
+  //each cell's dependencies need to be updated - that cannot be helped - having a range
+  //only helps with range dependencies
+  for (int row = range.startRow(); row <= range.endRow(); row++)
+    for (int col = range.startCol(); col <= range.endCol(); col++)
+    {
+      Point c;
+      c.setRow (row);
+      c.setColumn (col);
+      c.setSheet( sheet );
+
+      const TQValueList<Point> d = getCellDeps(c);
+      TQValueList<Point>::const_iterator it = d.begin();
+      const TQValueList<Point>::const_iterator end = d.end();
+      for (; it != end; ++it)
+          updateCell (*it);
+    }
+
+  processRangeDependencies (range);
+}
+
+void DependencyList::processRangeDependencies (const Range &range)
+{
+  //TODO: some optimization, so that we don't recompute cells depending of huge
+  //ranges more than once (now we recompute them once per cell-chunk used by their dependency)
+  //This will probably happen as a part of splitting this into dep manager
+  //and recalc manager
+
+  TQValueList<Point> leadings = leadingCells (range);
+  TQValueList<Point>::iterator it;
+  for (it = leadings.begin(); it != leadings.end(); ++it)
+  {
+    if (!rangeDeps.count (*it))
+      continue;  //no range dependencies in this cell chunk
+    TQValueList<RangeDependency>::iterator it2;
+    for (it2 = rangeDeps[*it].begin(); it2 != rangeDeps[*it].end(); ++it2)
+    {
+      //process all range dependencies, and for each range intersecting with our range,
+      //recalc the depending cell
+      if ((*it2).range.intersects (range))
+      {
+        Point c;
+        c.setRow ((*it2).range.startRow());
+        c.setColumn ((*it2).range.startCol());
+        c.setSheet(sheet);
+        updateCell (c);
+      }
+    }
+  }
+}
+
+void DependencyList::processDependencies (const RangeList &rangeList)
+{
+  TQValueList<Point>::const_iterator it1;
+  TQValueList<Range>::const_iterator it2;
+
+  for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
+    processDependencies (*it1);
+  for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
+    processDependencies (*it2);
+}
+
+void DependencyList::updateCell (const Point &cell) const
+{
+  Cell *c = cell.cell();
+  //prevent infinite recursion (circular dependencies)
+  if (c->testFlag (Cell::Flag_Progress) ||
+      c->testFlag (Cell::Flag_CircularCalculation))
+  {
+    kdError(36001) << "ERROR: Circle, cell " << c->fullName() <<
+        ", in dep.manager for sheet " << sheet->name() << endl;
+    Value v;
+    // don't set anything if the cell already has all these things set
+    // this prevents endless loop for inter-sheet curcular dependencies,
+    // where the usual mechanisms fail doe to having multiple dependency
+    // managers ...
+    if (!c->testFlag (Cell::Flag_CircularCalculation))
+    {
+      c->setFlag(Cell::Flag_CircularCalculation);
+      v.setError ( "####" );
+      c->setValue (v);
+    }
+    //clear the computing-dependencies flag
+    c->clearFlag (Cell::Flag_Progress);
+    return;
+  }
+  //set the computing-dependencies flag
+  c->setFlag (Cell::Flag_Progress);
+
+  //mark the cell as calc-dirty
+  c->setCalcDirtyFlag();
+
+  //recalculate the cell
+  c->calc (false);
+
+  //clear the computing-dependencies flag
+  c->clearFlag (Cell::Flag_Progress);
+}
+
+Point DependencyList::leadingCell (const Point &cell) const
+{
+  Point c;
+  c.setRow (cell.row() - cell.row() % CELLCHUNK_ROWS + 1);
+  c.setColumn (cell.column() - cell.column() % CELLCHUNK_COLS + 1);
+  c.setSheet(cell.sheet());
+  return c;
+}
+
+TQValueList<Point> DependencyList::leadingCells (const Range &range) const
+{
+  TQValueList<Point> cells;
+  Point cell1, cell2, cell;
+
+  cell1.setRow (range.startRow());
+  cell1.setColumn (range.startCol());
+  cell2.setRow (range.endRow());
+  cell2.setColumn (range.endCol());
+  cell1.setSheet(range.sheet());
+  cell2.setSheet(range.sheet());
+
+  cell1 = leadingCell (cell1);
+  cell2 = leadingCell (cell2);
+  for (int row = cell1.row(); row <= cell2.row(); row += CELLCHUNK_ROWS)
+    for (int col = cell1.column(); col <= cell2.column();
+        col += CELLCHUNK_COLS)
+    {
+      cell.setRow (row);
+      cell.setColumn (col);
+      cell.setSheet(range.sheet());
+      cells.push_back (cell);
+    }
+  return cells;
+}
+
+RangeList DependencyList::computeDependencies (const Point &cell) const
+{
+  Cell *c = cell.cell();
+
+  // Not a formula -> no dependencies
+  if (!c->isFormula())
+    return RangeList();
+
+  // Broken formula -> meaningless dependencies
+  // (tries to avoid c->formula() being null)
+  if (c->hasError())
+    return RangeList();
+
+  Formula* f = c->formula();
+  Q_ASSERT(f);
+  if (f==NULL)
+  {
+    kdDebug() << "Cell at row " << cell.row() << ", col " << cell.column() << " marked as formula, but formula is NULL" << endl;
+    return RangeList();
+  }
+
+  Tokens tokens = f->tokens();
+
+  //return empty list if the tokens aren't valid
+  if (!tokens.valid())
+    return RangeList();
+
+  RangeList rl;
+  for( unsigned i = 0; i < tokens.count(); i++ )
+  {
+    Token token = tokens[i];
+    Token::Type tokenType = token.type();
+
+    //parse each cell/range and put it to our RangeList
+    if (tokenType == Token::Cell)
+    {
+      TQString text = token.text();
+      Point cell (text, sheet->workbook(), sheet);
+      if (cell.isValid())
+        rl.cells.push_back (cell);
+    }
+    else if (tokenType == Token::Range)
+    {
+      TQString text = token.text();
+      Range range (text, sheet->workbook(), sheet);
+      if (range.isValid())
+        rl.ranges.push_back (range);
+    }
+  }
+
+  return rl;
+}
+