KOffice – TDE office suite
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

683 lines
20KB

  1. /* This file is part of the KDE project
  2. Copyright 2004 Tomas Mecir <mecirt@gmail.com>
  3. This library is free software; you can redistribute it and/or
  4. modify it under the terms of the GNU Library General Public
  5. License as published by the Free Software Foundation; either
  6. version 2 of the License, or (at your option) any later version.
  7. This library is distributed in the hope that it will be useful,
  8. but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  10. Library General Public License for more details.
  11. You should have received a copy of the GNU Library General Public License
  12. along with this library; see the file COPYING.LIB. If not, write to
  13. the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  14. * Boston, MA 02110-1301, USA.
  15. */
  16. #include "dependencies.h"
  17. #include "formula.h"
  18. #include "kspread_cell.h"
  19. #include "kspread_sheet.h"
  20. #include <tqmap.h>
  21. //rows x cols in one cell-chunk; bigger values lead to slower updating
  22. //of range-dependencies, lower values will increase memory usage
  23. #define CELLCHUNK_ROWS 128
  24. #define CELLCHUNK_COLS 16
  25. namespace KSpread {
  26. /** d-pointer of DependencyManager */
  27. class DependencyList {
  28. public:
  29. DependencyList (Sheet *s);
  30. ~DependencyList () { reset (); };
  31. /** clear internal structures */
  32. void reset ();
  33. /** handle the fact that a cell has been changed */
  34. void cellChanged (const Point &cell);
  35. /** generate list of dependencies of a cell */
  36. void generateDependencies (const Point &cell);
  37. /** generate list of dependencies of a range */
  38. void generateDependencies (const Range &range);
  39. /** generate list of dependencies of a range list */
  40. void generateDependencies (const RangeList &rangeList);
  41. /** update cells dependending on a given cell */
  42. void processDependencies (const Point &cell);
  43. /** update cells dependending on a cell in a given range */
  44. void processDependencies (const Range &range);
  45. /** update cells dependending on a given range-list */
  46. void processDependencies (const RangeList &rangeList);
  47. /** get dependencies of a cell */
  48. RangeList getDependencies (const Point &cell);
  49. /** get cells depending on this cell, either through normal or range dependency */
  50. TQValueList<Point> getDependants (const Point &cell);
  51. void areaModified (const TQString &name);
  52. protected:
  53. /** update structures: cell 1 depends on cell 2 */
  54. void addDependency (const Point &cell1, const Point &cell2);
  55. /** update structures: cell depends on a range */
  56. void addRangeDependency (const RangeDependency &rd);
  57. /** remove all dependencies of a cell */
  58. void removeDependencies (const Point &cell);
  59. /** update all cells depending on a range containing this cell */
  60. void processRangeDependencies (const Point &cell);
  61. /** update all cells depending on a range intersecting with this range */
  62. void processRangeDependencies (const Range &range);
  63. /** update one cell due to changed dependencies */
  64. void updateCell (const Point &cell) const;
  65. /** return a leading cell for a given cell (used to store range
  66. dependencies effectively) */
  67. Point leadingCell (const Point &cell) const;
  68. /** list of leading cells of all cell chunks that this range belongs to */
  69. TQValueList<Point> leadingCells (const Range &range) const;
  70. /** retrieve a list of cells that a given cell depends on */
  71. RangeList computeDependencies (const Point &cell) const;
  72. TQValueList<Point> getCellDeps(const Point& cell) const {
  73. CellDepsMap::const_iterator it = cellDeps.find( cell );
  74. return it == cellDeps.end() ? TQValueList<Point>() : *it;
  75. }
  76. /** debug */
  77. void dump();
  78. /** Sheet whose dependencies are managed by this instance */
  79. Sheet *sheet;
  80. /** dependencies of each cell */
  81. TQMap<Point, RangeList> dependencies;
  82. /** list of cells (but NOT ranges) that depend on a cell */
  83. typedef TQMap<Point, TQValueList<Point> > CellDepsMap;
  84. CellDepsMap cellDeps;
  85. /** all range dependencies splitted into cell-chunks (TODO: describe) */
  86. TQMap<Point, TQValueList<RangeDependency> > rangeDeps;
  87. /** list of cells referencing a given named area */
  88. TQMap<TQString, TQMap<Point, bool> > areaDeps;
  89. };
  90. } // namespace KSpread
  91. using namespace KSpread;
  92. // This is currently not called - but it's really convenient to call it from
  93. // gdb or from debug output to check that everything is set up ok.
  94. void DependencyList::dump()
  95. {
  96. TQMap<Point, RangeList>::const_iterator it = dependencies.begin();
  97. for ( ; it != dependencies.end(); ++it ) {
  98. Point p = it.key();
  99. kdDebug() << "Cell " << p.sheetName() << " " << p.pos()
  100. << " depends on :" << endl;
  101. RangeList rl = (*it);
  102. TQValueList<Point>::const_iterator itp = rl.cells.begin();
  103. for ( ; itp != rl.cells.end(); ++itp )
  104. kdDebug() << " cell " << (*itp).pos() << endl;
  105. TQValueList<Range>::const_iterator itr = rl.ranges.begin();
  106. for ( ; itr != rl.ranges.end(); ++itr )
  107. kdDebug() << " range " << (*itr).toString() << endl;
  108. }
  109. CellDepsMap::const_iterator cit = cellDeps.begin();
  110. for ( ; cit != cellDeps.end(); ++cit )
  111. {
  112. Point p = cit.key();
  113. kdDebug() << "The cells that depend on " << p.sheetName() << " " << p.pos()
  114. << " are :" << endl;
  115. TQValueList<Point>::const_iterator itp = (*cit).begin();
  116. for ( ; itp != (*cit).end(); ++itp )
  117. kdDebug() << " cell " << (*itp).pos() << endl;
  118. }
  119. }
  120. DependencyManager::DependencyManager (Sheet *s)
  121. {
  122. deps = new DependencyList (s);
  123. }
  124. DependencyManager::~DependencyManager ()
  125. {
  126. delete deps;
  127. deps = 0;
  128. }
  129. void DependencyManager::reset ()
  130. {
  131. deps->reset();
  132. }
  133. void DependencyManager::cellChanged (const Point &cell)
  134. {
  135. deps->cellChanged (cell);
  136. }
  137. void DependencyManager::rangeChanged (const Range &range)
  138. {
  139. deps->generateDependencies (range);
  140. deps->processDependencies (range);
  141. }
  142. void DependencyManager::rangeListChanged (const RangeList &rangeList)
  143. {
  144. deps->generateDependencies (rangeList);
  145. deps->processDependencies (rangeList);
  146. }
  147. void DependencyManager::areaModified (const TQString &name)
  148. {
  149. deps->areaModified (name);
  150. }
  151. RangeList DependencyManager::getDependencies (const Point &cell)
  152. {
  153. return deps->getDependencies (cell);
  154. }
  155. TQValueList<Point> DependencyManager::getDependants (const Point &cell)
  156. {
  157. return deps->getDependants (cell);
  158. }
  159. DependencyList::DependencyList (Sheet *s)
  160. : sheet (s)
  161. {
  162. }
  163. void DependencyList::reset ()
  164. {
  165. dependencies.clear();
  166. cellDeps.clear();
  167. rangeDeps.clear();
  168. }
  169. void DependencyList::cellChanged (const Point &cell)
  170. {
  171. Cell *c = cell.cell();
  172. // empty or default cell? do nothing
  173. if( c->isDefault() )
  174. return;
  175. //if the cell contains the circle error, we mustn't do anything
  176. if (c->testFlag (Cell::Flag_CircularCalculation))
  177. return;
  178. //don't re-generate dependencies if we're updating dependencies
  179. if ( !(c->testFlag (Cell::Flag_Progress)))
  180. generateDependencies (cell);
  181. processDependencies (cell);
  182. }
  183. RangeList DependencyList::getDependencies (const Point &cell)
  184. {
  185. RangeList rl;
  186. //look if the cell has any dependencies
  187. if (!dependencies.contains (cell))
  188. return rl; //it doesn't - return an empty list
  189. //the cell does have dependencies - return them!
  190. return dependencies[cell];
  191. }
  192. TQValueList<Point> DependencyList::getDependants (const Point &cell)
  193. {
  194. //cell dependencies go first
  195. TQValueList<Point> list = getCellDeps( cell );
  196. //next, append range dependencies
  197. Point leading = leadingCell (cell);
  198. TQValueList<RangeDependency>::iterator it;
  199. if (!rangeDeps.count (leading))
  200. return list; //no range dependencies in this cell chunk -> nothing more to do
  201. for (it = rangeDeps[leading].begin();
  202. it != rangeDeps[leading].end(); ++it)
  203. {
  204. //process all range dependencies, and for each range including the questioned cell,
  205. //add the depending cell to the list
  206. if ((*it).range.contains (cell))
  207. {
  208. Point c;
  209. c.setRow ((*it).cellrow);
  210. c.setColumn ((*it).cellcolumn);
  211. c.setSheet ( (*it).cellsheet );
  212. list.push_back (c);
  213. }
  214. }
  215. return list;
  216. }
  217. void DependencyList::areaModified (const TQString &name)
  218. {
  219. // since area names are something like aliases, modifying an area name
  220. // basically means that all cells referencing this area should be treated
  221. // as modified - that will retrieve updated area ranges and also update
  222. // everything as necessary ...
  223. if (!areaDeps.contains (name))
  224. return;
  225. TQMap<Point, bool>::iterator it;
  226. for (it = areaDeps[name].begin(); it != areaDeps[name].end(); ++it)
  227. {
  228. Cell *c = it.key().cell();
  229. // this forces the cell to regenerate everything - new range dependencies
  230. // and so on
  231. c->setValue (c->value ());
  232. }
  233. }
  234. void DependencyList::addDependency (const Point &cell1,
  235. const Point &cell2)
  236. {
  237. //cell2 can be in another sheet (inter-sheet dependency)
  238. Sheet *sh = cell2.sheet();
  239. if (!sh)
  240. sh = sheet;
  241. dependencies[cell1].cells.push_back (cell2);
  242. sh->dependencies()->deps->cellDeps[cell2].push_back (cell1);
  243. }
  244. void DependencyList::addRangeDependency (const RangeDependency &rd)
  245. {
  246. //target range can be in another sheet (inter-sheet dependency)
  247. Sheet *sh = rd.range.sheet();
  248. if (!sh)
  249. sh = sheet;
  250. Point cell;
  251. cell.setSheet (rd.cellsheet);
  252. cell.setRow (rd.cellrow);
  253. cell.setColumn (rd.cellcolumn);
  254. dependencies[cell].ranges.push_back (rd.range);
  255. TQValueList<Point> leadings = leadingCells (rd.range);
  256. TQValueList<Point>::iterator it;
  257. for (it = leadings.begin(); it != leadings.end(); ++it)
  258. sh->dependencies()->deps->rangeDeps[*it].push_back (rd);
  259. // the target range could be a named area ...
  260. if (!rd.range.namedArea().isNull())
  261. areaDeps[rd.range.namedArea()][cell] = true;
  262. }
  263. void DependencyList::removeDependencies (const Point &cell)
  264. {
  265. //look if the cell has any dependencies
  266. if (!dependencies.contains (cell))
  267. return; //it doesn't - nothing more to do
  268. //first we remove cell-dependencies
  269. TQValueList<Point> cells = dependencies[cell].cells;
  270. TQValueList<Point>::iterator it1;
  271. for (it1 = cells.begin(); it1 != cells.end(); ++it1)
  272. {
  273. //get sheet-pointer - needed to handle inter-sheet dependencies correctly
  274. Sheet *sh = (*it1).sheet();
  275. if (!sh)
  276. sh = sheet;
  277. if (!sh->dependencies()->deps->cellDeps.contains (*it1))
  278. continue; //this should never happen
  279. //we no longer depend on this cell
  280. TQValueList<Point>::iterator cit;
  281. cit = sh->dependencies()->deps->cellDeps[*it1].find (cell);
  282. if (cit != sh->dependencies()->deps->cellDeps[*it1].end())
  283. sh->dependencies()->deps->cellDeps[*it1].erase (cit);
  284. }
  285. //then range-dependencies are removed
  286. TQValueList<Range> ranges = dependencies[cell].ranges;
  287. TQValueList<Range>::iterator it2;
  288. TQValueList<Point> leads;
  289. for (it2 = ranges.begin(); it2 != ranges.end(); ++it2)
  290. {
  291. //we construct a list of cell-chunks containing a range and merge it
  292. //with lists generated from all previous ranges (duplicates are removed)
  293. TQValueList<Point> leadings = leadingCells (*it2);
  294. for (it1 = leadings.begin(); it1 != leadings.end(); ++it1)
  295. if (!leads.contains (*it1))
  296. leads.push_back (*it1);
  297. }
  298. for (it1 = leads.begin(); it1 != leads.end(); ++it1)
  299. {
  300. //get sheet-pointer - needed to handle inter-sheet dependencies correctly
  301. Sheet *sh = (*it1).sheet();
  302. if (!sh)
  303. sh = sheet;
  304. if (sh->dependencies()->deps->rangeDeps.contains (*it1))
  305. {
  306. TQValueList<RangeDependency>::iterator it3;
  307. it3 = sh->dependencies()->deps->rangeDeps[*it1].begin();
  308. //erase all range dependencies of this cell in this cell-chunk
  309. while (it3 != sh->dependencies()->deps->rangeDeps[*it1].end())
  310. if (((*it3).cellrow == cell.row()) &&
  311. ((*it3).cellcolumn == cell.column()))
  312. it3 = sh->dependencies()->deps->rangeDeps[*it1].erase (it3);
  313. else
  314. ++it3;
  315. //erase the list if we no longer need it
  316. if (sh->dependencies()->deps->rangeDeps[*it1].empty())
  317. sh->dependencies()->deps->rangeDeps.erase (*it1);
  318. }
  319. }
  320. // remove information about named area dependencies
  321. TQMap<TQString, TQMap<Point, bool> >::iterator itr;
  322. for (itr = areaDeps.begin(); itr != areaDeps.end(); ++itr) {
  323. if (itr.data().contains (cell))
  324. itr.data().remove (cell);
  325. }
  326. // finally, remove the entry about this cell
  327. dependencies[cell].cells.clear();
  328. dependencies[cell].ranges.clear();
  329. dependencies.erase (cell);
  330. }
  331. void DependencyList::generateDependencies (const Point &cell)
  332. {
  333. //get rid of old dependencies first
  334. removeDependencies (cell);
  335. //new dependencies only need to be generated if the cell contains a formula
  336. Cell *c = sheet->cellAt (cell.column(), cell.row());
  337. if( c->isDefault() )
  338. return;
  339. if (!c->isFormula())
  340. return;
  341. //now we need to generate dependencies
  342. RangeList rl = computeDependencies (cell);
  343. //now that we have the new dependencies, we put them into our data structures
  344. //and we're done
  345. TQValueList<Point>::iterator it1;
  346. TQValueList<Range>::iterator it2;
  347. for (it1 = rl.cells.begin(); it1 != rl.cells.end(); ++it1)
  348. addDependency (cell, *it1);
  349. for (it2 = rl.ranges.begin(); it2 != rl.ranges.end(); ++it2)
  350. {
  351. RangeDependency rd;
  352. rd.cellrow = cell.row();
  353. rd.cellcolumn = cell.column();
  354. rd.cellsheet = sheet;
  355. rd.range = *it2;
  356. if (rd.range.sheet() == 0)
  357. rd.range.setSheet(sheet);
  358. addRangeDependency (rd);
  359. }
  360. }
  361. void DependencyList::generateDependencies (const Range &range)
  362. {
  363. for (int row = range.startRow(); row <= range.endRow(); row++)
  364. for (int col = range.startCol(); col <= range.endCol(); col++)
  365. {
  366. Point c;
  367. c.setRow (row);
  368. c.setColumn (col);
  369. c.setSheet(sheet);
  370. generateDependencies (c);
  371. }
  372. }
  373. void DependencyList::generateDependencies (const RangeList &rangeList)
  374. {
  375. TQValueList<Point>::const_iterator it1;
  376. TQValueList<Range>::const_iterator it2;
  377. for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
  378. generateDependencies (*it1);
  379. for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
  380. generateDependencies (*it2);
  381. }
  382. void DependencyList::processDependencies (const Point &cell)
  383. {
  384. const TQValueList<Point> d = getCellDeps(cell);
  385. TQValueList<Point>::const_iterator it = d.begin();
  386. const TQValueList<Point>::const_iterator end = d.end();
  387. for (; it != end; ++it)
  388. updateCell (*it);
  389. processRangeDependencies (cell);
  390. }
  391. void DependencyList::processRangeDependencies (const Point &cell)
  392. {
  393. Point leading = leadingCell (cell);
  394. if (!rangeDeps.count (leading))
  395. return; //no range dependencies in this cell chunk
  396. const TQValueList<RangeDependency> rd = rangeDeps[leading];
  397. TQValueList<RangeDependency>::const_iterator it;
  398. for (it = rd.begin(); it != rd.end(); ++it)
  399. {
  400. //process all range dependencies, and for each range including the modified cell,
  401. //recalc the depending cell
  402. if ((*it).range.contains (cell))
  403. {
  404. Point c;
  405. c.setRow ((*it).cellrow);
  406. c.setColumn ((*it).cellcolumn);
  407. c.setSheet ( (*it).cellsheet );
  408. updateCell (c);
  409. }
  410. }
  411. }
  412. void DependencyList::processDependencies (const Range &range)
  413. {
  414. //each cell's dependencies need to be updated - that cannot be helped - having a range
  415. //only helps with range dependencies
  416. for (int row = range.startRow(); row <= range.endRow(); row++)
  417. for (int col = range.startCol(); col <= range.endCol(); col++)
  418. {
  419. Point c;
  420. c.setRow (row);
  421. c.setColumn (col);
  422. c.setSheet( sheet );
  423. const TQValueList<Point> d = getCellDeps(c);
  424. TQValueList<Point>::const_iterator it = d.begin();
  425. const TQValueList<Point>::const_iterator end = d.end();
  426. for (; it != end; ++it)
  427. updateCell (*it);
  428. }
  429. processRangeDependencies (range);
  430. }
  431. void DependencyList::processRangeDependencies (const Range &range)
  432. {
  433. //TODO: some optimization, so that we don't recompute cells depending of huge
  434. //ranges more than once (now we recompute them once per cell-chunk used by their dependency)
  435. //This will probably happen as a part of splitting this into dep manager
  436. //and recalc manager
  437. TQValueList<Point> leadings = leadingCells (range);
  438. TQValueList<Point>::iterator it;
  439. for (it = leadings.begin(); it != leadings.end(); ++it)
  440. {
  441. if (!rangeDeps.count (*it))
  442. continue; //no range dependencies in this cell chunk
  443. TQValueList<RangeDependency>::iterator it2;
  444. for (it2 = rangeDeps[*it].begin(); it2 != rangeDeps[*it].end(); ++it2)
  445. {
  446. //process all range dependencies, and for each range intersecting with our range,
  447. //recalc the depending cell
  448. if ((*it2).range.intersects (range))
  449. {
  450. Point c;
  451. c.setRow ((*it2).range.startRow());
  452. c.setColumn ((*it2).range.startCol());
  453. c.setSheet(sheet);
  454. updateCell (c);
  455. }
  456. }
  457. }
  458. }
  459. void DependencyList::processDependencies (const RangeList &rangeList)
  460. {
  461. TQValueList<Point>::const_iterator it1;
  462. TQValueList<Range>::const_iterator it2;
  463. for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
  464. processDependencies (*it1);
  465. for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
  466. processDependencies (*it2);
  467. }
  468. void DependencyList::updateCell (const Point &cell) const
  469. {
  470. Cell *c = cell.cell();
  471. //prevent infinite recursion (circular dependencies)
  472. if (c->testFlag (Cell::Flag_Progress) ||
  473. c->testFlag (Cell::Flag_CircularCalculation))
  474. {
  475. kdError(36001) << "ERROR: Circle, cell " << c->fullName() <<
  476. ", in dep.manager for sheet " << sheet->name() << endl;
  477. Value v;
  478. // don't set anything if the cell already has all these things set
  479. // this prevents endless loop for inter-sheet curcular dependencies,
  480. // where the usual mechanisms fail doe to having multiple dependency
  481. // managers ...
  482. if (!c->testFlag (Cell::Flag_CircularCalculation))
  483. {
  484. c->setFlag(Cell::Flag_CircularCalculation);
  485. v.setError ( "####" );
  486. c->setValue (v);
  487. }
  488. //clear the computing-dependencies flag
  489. c->clearFlag (Cell::Flag_Progress);
  490. return;
  491. }
  492. //set the computing-dependencies flag
  493. c->setFlag (Cell::Flag_Progress);
  494. //mark the cell as calc-dirty
  495. c->setCalcDirtyFlag();
  496. //recalculate the cell
  497. c->calc (false);
  498. //clear the computing-dependencies flag
  499. c->clearFlag (Cell::Flag_Progress);
  500. }
  501. Point DependencyList::leadingCell (const Point &cell) const
  502. {
  503. Point c;
  504. c.setRow (cell.row() - cell.row() % CELLCHUNK_ROWS + 1);
  505. c.setColumn (cell.column() - cell.column() % CELLCHUNK_COLS + 1);
  506. c.setSheet(cell.sheet());
  507. return c;
  508. }
  509. TQValueList<Point> DependencyList::leadingCells (const Range &range) const
  510. {
  511. TQValueList<Point> cells;
  512. Point cell1, cell2, cell;
  513. cell1.setRow (range.startRow());
  514. cell1.setColumn (range.startCol());
  515. cell2.setRow (range.endRow());
  516. cell2.setColumn (range.endCol());
  517. cell1.setSheet(range.sheet());
  518. cell2.setSheet(range.sheet());
  519. cell1 = leadingCell (cell1);
  520. cell2 = leadingCell (cell2);
  521. for (int row = cell1.row(); row <= cell2.row(); row += CELLCHUNK_ROWS)
  522. for (int col = cell1.column(); col <= cell2.column();
  523. col += CELLCHUNK_COLS)
  524. {
  525. cell.setRow (row);
  526. cell.setColumn (col);
  527. cell.setSheet(range.sheet());
  528. cells.push_back (cell);
  529. }
  530. return cells;
  531. }
  532. RangeList DependencyList::computeDependencies (const Point &cell) const
  533. {
  534. Cell *c = cell.cell();
  535. // Not a formula -> no dependencies
  536. if (!c->isFormula())
  537. return RangeList();
  538. // Broken formula -> meaningless dependencies
  539. // (tries to avoid c->formula() being null)
  540. if (c->hasError())
  541. return RangeList();
  542. Formula* f = c->formula();
  543. Q_ASSERT(f);
  544. if (f==NULL)
  545. {
  546. kdDebug() << "Cell at row " << cell.row() << ", col " << cell.column() << " marked as formula, but formula is NULL" << endl;
  547. return RangeList();
  548. }
  549. Tokens tokens = f->tokens();
  550. //return empty list if the tokens aren't valid
  551. if (!tokens.valid())
  552. return RangeList();
  553. RangeList rl;
  554. for( unsigned i = 0; i < tokens.count(); i++ )
  555. {
  556. Token token = tokens[i];
  557. Token::Type tokenType = token.type();
  558. //parse each cell/range and put it to our RangeList
  559. if (tokenType == Token::Cell)
  560. {
  561. TQString text = token.text();
  562. Point cell (text, sheet->workbook(), sheet);
  563. if (cell.isValid())
  564. rl.cells.push_back (cell);
  565. }
  566. else if (tokenType == Token::Range)
  567. {
  568. TQString text = token.text();
  569. Range range (text, sheet->workbook(), sheet);
  570. if (range.isValid())
  571. rl.ranges.push_back (range);
  572. }
  573. }
  574. return rl;
  575. }