1/* This file is part of the KDE project
2 Copyright 2010 Marijn Kruisselbrink <mkruisselbrink@kde.org>
3 Copyright 2006,2007 Stefan Nikolaus <stefan.nikolaus@kdemail.net>
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Library General Public
7 License as published by the Free Software Foundation; either
8 version 2 of the License, or (at your option) any later version.
9
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Library General Public License for more details.
14
15 You should have received a copy of the GNU Library General Public License
16 along with this library; see the file COPYING.LIB. If not, write to
17 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
19*/
20
21#ifndef CALLIGRA_SHEETS_RECT_STORAGE
22#define CALLIGRA_SHEETS_RECT_STORAGE
23
24#include <QCache>
25#include <QRegion>
26#include <QTimer>
27#include <QRunnable>
28#include <QTime>
29#ifdef CALLIGRA_SHEETS_MT
30#include <QMutex>
31#include <QMutexLocker>
32#endif
33
34#include "calligra_sheets_export.h"
35
36#include "Map.h"
37#include "Region.h"
38#include "RTree.h"
39
40static const int g_garbageCollectionTimeOut = 100;
41
42namespace Calligra
43{
44namespace Sheets
45{
46
47template<typename T>
48class RectStorageLoader;
49
50/**
51 * \ingroup Storage
52 * A custom rectangular storage.
53 * Based on an R-Tree data structure.
54 * Usable for any kind of data attached to rectangular regions.
55 *
56 * Acts mainly as a wrapper around the R-Tree data structure to allow a future
57 * replacement of this backend. Decorated with some additional features like
58 * garbage collection, caching, used area tracking, etc.
59 *
60 * \author Stefan Nikolaus <stefan.nikolaus@kdemail.net>
61 *
62 * \note For data assigned to points use PointStorage.
63 */
64template<typename T>
65class RectStorage
66{
67public:
68 explicit RectStorage(Map* map);
69 RectStorage(const RectStorage& other);
70 virtual ~RectStorage();
71
72 /**
73 * \return the stored value at the position \p point .
74 */
75 T contains(const QPoint& point) const;
76
77 /**
78 * \return the stored rect/value pair at the position \p point .
79 */
80 QPair<QRectF, T> containedPair(const QPoint& point) const;
81
82 QList< QPair<QRectF, T> > intersectingPairs(const Region& region) const;
83
84 QList< QPair<QRectF, T> > undoData(const Region& region) const;
85
86 /**
87 * Returns the area, which got data attached.
88 * \return the area using data
89 */
90 QRect usedArea() const;
91
92 /**
93 * Mass loading of data, removes any existing data first
94 */
95 void load(const QList<QPair<QRegion, T> >& data);
96
97 /**
98 * Assigns \p data to \p region .
99 */
100 void insert(const Region& region, const T& data);
101
102 /**
103 * Removes \p data from \p region .
104 */
105 void remove(const Region& region, const T& data);
106
107 /**
108 * Inserts \p number rows at the position \p position .
109 * It extends or shifts rectangles, respectively.
110 */
111 QList< QPair<QRectF, T> > insertRows(int position, int number);
112
113 /**
114 * Inserts \p number columns at the position \p position .
115 * It extends or shifts rectangles, respectively.
116 */
117 QList< QPair<QRectF, T> > insertColumns(int position, int number);
118
119 /**
120 * Deletes \p number rows at the position \p position .
121 * It shrinks or shifts rectangles, respectively.
122 */
123 QList< QPair<QRectF, T> > removeRows(int position, int number);
124
125 /**
126 * Deletes \p number columns at the position \p position .
127 * It shrinks or shifts rectangles, respectively.
128 */
129 QList< QPair<QRectF, T> > removeColumns(int position, int number);
130
131 /**
132 * Shifts the rows right of \p rect to the right by the width of \p rect .
133 * It extends or shifts rectangles, respectively.
134 */
135 QList< QPair<QRectF, T> > insertShiftRight(const QRect& rect);
136
137 /**
138 * Shifts the columns at the bottom of \p rect to the bottom by the height of \p rect .
139 * It extends or shifts rectangles, respectively.
140 */
141 QList< QPair<QRectF, T> > insertShiftDown(const QRect& rect);
142
143 /**
144 * Shifts the rows left of \p rect to the left by the width of \p rect .
145 * It shrinks or shifts rectangles, respectively.
146 * \return the former rectangle/data pairs
147 */
148 QList< QPair<QRectF, T> > removeShiftLeft(const QRect& rect);
149
150 /**
151 * Shifts the columns on top of \p rect to the top by the height of \p rect .
152 * It shrinks or shifts rectangles, respectively.
153 * \return the former rectangle/data pairs
154 */
155 QList< QPair<QRectF, T> > removeShiftUp(const QRect& rect);
156
157protected:
158 virtual void triggerGarbageCollection();
159 virtual void garbageCollection();
160
161 /**
162 * Triggers all necessary actions after a change of \p rect .
163 * Calls invalidateCache() and adds the data in
164 * \p rect to the list of possible garbage.
165 */
166 void regionChanged(const QRect& rect);
167
168 /**
169 * Invalidates all cached styles lying in \p rect .
170 */
171 void invalidateCache(const QRect& rect);
172
173 /**
174 * Ensures that any load() operation has completed.
175 */
176 void ensureLoaded() const;
177private:
178 Map* m_map;
179 RTree<T> m_tree;
180 QRegion m_usedArea;
181 QMap<int, QPair<QRectF, T> > m_possibleGarbage;
182 QList<T> m_storedData;
183 mutable QCache<QPoint, T> m_cache;
184#ifdef CALLIGRA_SHEETS_MT
185 mutable QMutex m_mutex;
186#endif
187 mutable QRegion m_cachedArea;
188
189 RectStorageLoader<T>* m_loader;
190 friend class RectStorageLoader<T>;
191};
192
193template<typename T>
194class RectStorageLoader : public QRunnable
195{
196public:
197 RectStorageLoader(RectStorage<T>* storage, const QList<QPair<QRegion, T> >& data);
198 virtual void run();
199 void waitForFinished();
200 bool isFinished() const;
201 QList<QPair<QRegion, T> > data() const;
202private:
203 RectStorage<T>* m_storage;
204 QList<QPair<QRegion, T> > m_data;
205};
206
207template<typename T>
208RectStorage<T>::RectStorage(Map* map)
209 : m_map(map), m_loader(0)
210{
211}
212
213template<typename T>
214RectStorage<T>::RectStorage(const RectStorage& other)
215 : m_map(other.m_map)
216 , m_usedArea(other.m_usedArea)
217 , m_storedData(other.m_storedData)
218 , m_loader(0)
219{
220 m_tree = other.m_tree;
221 if (other.m_loader) {
222 m_loader = new RectStorageLoader<T>(this, other.m_loader->data());
223 }
224}
225
226template<typename T>
227RectStorage<T>::~RectStorage()
228{
229 delete m_loader; // needs fixing if this ever gets to be multithreaded
230}
231
232template<typename T>
233T RectStorage<T>::contains(const QPoint& point) const
234{
235 ensureLoaded();
236#ifdef CALLIGRA_SHEETS_MT
237 QMutexLocker ml(&m_mutex);
238#endif
239 if (!usedArea().contains(point))
240 return T();
241 // first, lookup point in the cache
242 if (m_cache.contains(point)) {
243 return *m_cache.object(point);
244 }
245 // not found, lookup in the tree
246 QList<T> results = m_tree.contains(point);
247 T data = results.isEmpty() ? T() : results.last();
248 // insert style into the cache
249 m_cache.insert(point, new T(data));
250 m_cachedArea += QRect(point, point);
251 return data;
252}
253
254template<typename T>
255QPair<QRectF, T> RectStorage<T>::containedPair(const QPoint& point) const
256{
257 ensureLoaded();
258 const QList< QPair<QRectF, T> > results = m_tree.intersectingPairs(QRect(point, point)).values();
259 return results.isEmpty() ? qMakePair(QRectF(), T()) : results.last();
260}
261
262template<typename T>
263QList< QPair<QRectF, T> > RectStorage<T>::intersectingPairs(const Region& region) const
264{
265 ensureLoaded();
266 QList< QPair<QRectF, T> > result;
267 Region::ConstIterator end = region.constEnd();
268 for (Region::ConstIterator it = region.constBegin(); it != end; ++it)
269 result += m_tree.intersectingPairs((*it)->rect()).values();
270 return result;
271}
272
273template<typename T>
274QList< QPair<QRectF, T> > RectStorage<T>::undoData(const Region& region) const
275{
276 ensureLoaded();
277 QList< QPair<QRectF, T> > result;
278 Region::ConstIterator end = region.constEnd();
279 for (Region::ConstIterator it = region.constBegin(); it != end; ++it) {
280 const QRect rect = (*it)->rect();
281 QList< QPair<QRectF, T> > pairs = m_tree.intersectingPairs(rect).values();
282 for (int i = 0; i < pairs.count(); ++i) {
283 // trim the rects
284 pairs[i].first = pairs[i].first.intersected(rect);
285 }
286 // Always add a default value even if there are no pairs.
287 result << qMakePair(QRectF(rect), T()) << pairs;
288 }
289 return result;
290}
291
292template<typename T>
293QRect RectStorage<T>::usedArea() const
294{
295 ensureLoaded();
296 return m_tree.boundingBox().toRect();
297}
298
299template<typename T>
300void RectStorage<T>::load(const QList<QPair<QRegion, T> >& data)
301{
302 Q_ASSERT(!m_loader);
303 m_loader = new RectStorageLoader<T>(this, data);
304}
305
306template<typename T>
307void RectStorage<T>::insert(const Region& region, const T& _data)
308{
309 ensureLoaded();
310 T data;
311 // lookup already used data
312 int index = m_storedData.indexOf(_data);
313 if (index != -1)
314 data = m_storedData[index];
315 else {
316 data = _data;
317 m_storedData.append(_data);
318 }
319
320 Region::ConstIterator end(region.constEnd());
321 for (Region::ConstIterator it(region.constBegin()); it != end; ++it) {
322 // insert data
323 m_tree.insert((*it)->rect(), data);
324 regionChanged((*it)->rect());
325 }
326}
327
328template<typename T>
329void RectStorage<T>::remove(const Region& region, const T& data)
330{
331 ensureLoaded();
332 if (!m_storedData.contains(data)) {
333 return;
334 }
335 const Region::ConstIterator end(region.constEnd());
336 for (Region::ConstIterator it(region.constBegin()); it != end; ++it) {
337 // remove data
338 m_tree.remove((*it)->rect(), data);
339 regionChanged((*it)->rect());
340 }
341}
342
343template<typename T>
344QList< QPair<QRectF, T> > RectStorage<T>::insertRows(int position, int number)
345{
346 ensureLoaded();
347 const QRect invalidRect(1, position, KS_colMax, KS_rowMax);
348 // invalidate the affected, cached styles
349 invalidateCache(invalidRect);
350 // process the tree
351 QList< QPair<QRectF, T> > undoData;
352 undoData << qMakePair(QRectF(1, KS_rowMax - number + 1, KS_colMax, number), T());
353 undoData << m_tree.insertRows(position, number, RTree<T>::CopyCurrent);
354 return undoData;
355}
356
357template<typename T>
358QList< QPair<QRectF, T> > RectStorage<T>::insertColumns(int position, int number)
359{
360 ensureLoaded();
361 const QRect invalidRect(position, 1, KS_colMax, KS_rowMax);
362 // invalidate the affected, cached styles
363 invalidateCache(invalidRect);
364 // process the tree
365 QList< QPair<QRectF, T> > undoData;
366 undoData << qMakePair(QRectF(KS_colMax - number + 1, 1, number, KS_rowMax), T());
367 undoData << m_tree.insertColumns(position, number, RTree<T>::CopyCurrent);
368 return undoData;
369}
370
371template<typename T>
372QList< QPair<QRectF, T> > RectStorage<T>::removeRows(int position, int number)
373{
374 ensureLoaded();
375 const QRect invalidRect(1, position, KS_colMax, KS_rowMax);
376 // invalidate the affected, cached styles
377 invalidateCache(invalidRect);
378 // process the tree
379 QList< QPair<QRectF, T> > undoData;
380 undoData << qMakePair(QRectF(1, position, KS_colMax, number), T());
381 undoData << m_tree.removeRows(position, number);
382 return undoData;
383}
384
385template<typename T>
386QList< QPair<QRectF, T> > RectStorage<T>::removeColumns(int position, int number)
387{
388 ensureLoaded();
389 const QRect invalidRect(position, 1, KS_colMax, KS_rowMax);
390 // invalidate the affected, cached styles
391 invalidateCache(invalidRect);
392 // process the tree
393 QList< QPair<QRectF, T> > undoData;
394 undoData << qMakePair(QRectF(position, 1, number, KS_rowMax), T());
395 undoData << m_tree.removeColumns(position, number);
396 return undoData;
397}
398
399template<typename T>
400QList< QPair<QRectF, T> > RectStorage<T>::insertShiftRight(const QRect& rect)
401{
402 ensureLoaded();
403 const QRect invalidRect(rect.topLeft(), QPoint(KS_colMax, rect.bottom()));
404 QList< QPair<QRectF, T> > undoData;
405 undoData << qMakePair(QRectF(rect), T());
406 undoData << m_tree.insertShiftRight(rect);
407 regionChanged(invalidRect);
408 return undoData;
409}
410
411template<typename T>
412QList< QPair<QRectF, T> > RectStorage<T>::insertShiftDown(const QRect& rect)
413{
414 ensureLoaded();
415 const QRect invalidRect(rect.topLeft(), QPoint(rect.right(), KS_rowMax));
416 QList< QPair<QRectF, T> > undoData;
417 undoData << qMakePair(QRectF(rect), T());
418 undoData << m_tree.insertShiftDown(rect);
419 regionChanged(invalidRect);
420 return undoData;
421}
422
423template<typename T>
424QList< QPair<QRectF, T> > RectStorage<T>::removeShiftLeft(const QRect& rect)
425{
426 ensureLoaded();
427 const QRect invalidRect(rect.topLeft(), QPoint(KS_colMax, rect.bottom()));
428 QList< QPair<QRectF, T> > undoData;
429 undoData << qMakePair(QRectF(rect), T());
430 undoData << m_tree.removeShiftLeft(rect);
431 regionChanged(invalidRect);
432 return undoData;
433}
434
435template<typename T>
436QList< QPair<QRectF, T> > RectStorage<T>::removeShiftUp(const QRect& rect)
437{
438 ensureLoaded();
439 const QRect invalidRect(rect.topLeft(), QPoint(rect.right(), KS_rowMax));
440 QList< QPair<QRectF, T> > undoData;
441 undoData << qMakePair(QRectF(rect), T());
442 undoData << m_tree.removeShiftUp(rect);
443 regionChanged(invalidRect);
444 return undoData;
445}
446
447template<typename T>
448void RectStorage<T>::triggerGarbageCollection()
449{
450}
451
452template<typename T>
453void RectStorage<T>::garbageCollection()
454{
455 if (m_loader && !m_loader->isFinished())
456 return;
457
458 // any possible garbage left?
459 if (m_possibleGarbage.isEmpty())
460 return;
461
462 const int currentZIndex = m_possibleGarbage.constBegin().key();
463 const QPair<QRectF, T> currentPair = m_possibleGarbage.take(currentZIndex);
464
465 typedef QPair<QRectF, T> DataPair;
466 QMap<int, DataPair> pairs = m_tree.intersectingPairs(currentPair.first.toRect());
467 if (pairs.isEmpty()) // actually never true, just for sanity
468 return;
469 int zIndex = pairs.constBegin().key();
470 DataPair pair = pairs[zIndex];
471
472 // check whether the default style is placed first
473 if (zIndex == currentZIndex &&
474 currentPair.second == T() &&
475 pair.second == T() &&
476 pair.first == currentPair.first) {
477 kDebug(36001) << "RectStorage: removing default data at" << Region(currentPair.first.toRect()).name();
478 m_tree.remove(currentPair.first.toRect(), currentPair.second);
479 triggerGarbageCollection();
480 return; // already done
481 }
482
483 bool found = false;
484 typename QMap<int, DataPair>::ConstIterator end = pairs.constEnd();
485 for (typename QMap<int, DataPair>::ConstIterator it = pairs.constFind(currentZIndex); it != end; ++it) {
486 zIndex = it.key();
487 pair = it.value();
488
489 // as long as the substyle in question was not found, skip the substyle
490 if (!found) {
491 if (zIndex == currentZIndex &&
492 pair.first == currentPair.first &&
493 pair.second == currentPair.second) {
494 found = true;
495 }
496 continue;
497 }
498
499 // remove the current pair, if another substyle of the same type,
500 // the default style or a named style follows and the rectangle
501 // is completely covered
502 if (zIndex != currentZIndex &&
503 (pair.second == currentPair.second || pair.second == T()) &&
504 pair.first.toRect().contains(currentPair.first.toRect())) {
505 kDebug(36001) << "RectStorage: removing data at" << Region(currentPair.first.toRect()).name();
506 m_tree.remove(currentPair.first.toRect(), currentPair.second);
507 break;
508 }
509 }
510 triggerGarbageCollection();
511}
512
513template<typename T>
514void RectStorage<T>::regionChanged(const QRect& rect)
515{
516 if (m_loader && !m_loader->isFinished())
517 return;
518 if (m_map->isLoading())
519 return;
520 // mark the possible garbage
521 // NOTE Stefan: The map may contain multiple indices. The already existing possible garbage has
522 // has to be inserted most recently, because it should be accessed first.
523 m_possibleGarbage = m_tree.intersectingPairs(rect).unite(m_possibleGarbage);
524 triggerGarbageCollection();
525 // invalidate cache
526 invalidateCache(rect);
527}
528
529template<typename T>
530void RectStorage<T>::invalidateCache(const QRect& invRect)
531{
532 if (m_loader && !m_loader->isFinished())
533 return;
534#ifdef CALLIGRA_SHEETS_MT
535 QMutexLocker ml(&m_mutex);
536#endif
537 const QVector<QRect> rects = m_cachedArea.intersected(invRect).rects();
538 m_cachedArea = m_cachedArea.subtracted(invRect);
539 foreach(const QRect& rect, rects) {
540 for (int col = rect.left(); col <= rect.right(); ++col) {
541 for (int row = rect.top(); row <= rect.bottom(); ++row)
542 m_cache.remove(QPoint(col, row)); // also deletes it
543 }
544 }
545}
546
547template<typename T>
548void RectStorage<T>::ensureLoaded() const
549{
550 if (m_loader) {
551 m_loader->waitForFinished();
552 delete m_loader;
553 const_cast<RectStorage<T>*>(this)->m_loader = 0;
554 }
555}
556
557template<typename T>
558RectStorageLoader<T>::RectStorageLoader(RectStorage<T> *storage, const QList<QPair<QRegion, T> > &data)
559 : m_storage(storage)
560 , m_data(data)
561{
562}
563
564template<typename T>
565void RectStorageLoader<T>::run()
566{
567 static int total = 0;
568 kDebug(36001) << "Loading conditional styles";
569 QTime t; t.start();
570
571 QList<QPair<QRegion, T> > treeData;
572 typedef QPair<QRegion, T> TRegion;
573 QMap<T, int> indexCache;
574 foreach (const TRegion& tr, m_data) {
575 const QRegion& reg = tr.first;
576 const T& d = tr.second;
577
578 typename QMap<T, int>::iterator idx = indexCache.find(d);
579 int index = idx != indexCache.end() ? idx.value() : m_storage->m_storedData.indexOf(d);
580 if (index != -1) {
581 treeData.append(qMakePair(reg, m_storage->m_storedData[index]));
582 if (idx == indexCache.end()) indexCache.insert(d, index);
583 } else {
584 treeData.append(tr);
585 if (idx == indexCache.end()) indexCache.insert(d, m_storage->m_storedData.size());
586 m_storage->m_storedData.append(d);
587 }
588 }
589
590 m_storage->m_tree.load(treeData);
591 int e = t.elapsed();
592 total += e;
593 kDebug(36001) << "Time: " << e << total;
594}
595
596template<typename T>
597void RectStorageLoader<T>::waitForFinished()
598{
599 run();
600}
601
602template<typename T>
603bool RectStorageLoader<T>::isFinished() const
604{
605 return false;
606}
607
608template<typename T>
609QList<QPair<QRegion, T> > RectStorageLoader<T>::data() const
610{
611 return m_data;
612}
613
614class CommentStorage : public QObject, public RectStorage<QString>
615{
616 Q_OBJECT
617public:
618 explicit CommentStorage(Map* map) : QObject(map), RectStorage<QString>(map) {}
619 CommentStorage(const CommentStorage& other) : QObject(other.parent()), RectStorage<QString>(other) {}
620
621protected Q_SLOTS:
622 virtual void triggerGarbageCollection() {
623 QTimer::singleShot(g_garbageCollectionTimeOut, this, SLOT(garbageCollection()));
624 }
625 virtual void garbageCollection() {
626 RectStorage<QString>::garbageCollection();
627 }
628};
629
630
631
632class CALLIGRA_SHEETS_ODF_EXPORT FusionStorage : public QObject, public RectStorage<bool>
633{
634 Q_OBJECT
635public:
636 explicit FusionStorage(Map* map) : QObject(map), RectStorage<bool>(map) {}
637 FusionStorage(const FusionStorage& other) : QObject(other.parent()), RectStorage<bool>(other) {}
638
639protected Q_SLOTS:
640 virtual void triggerGarbageCollection() {
641 QTimer::singleShot(g_garbageCollectionTimeOut, this, SLOT(garbageCollection()));
642 }
643 virtual void garbageCollection() {
644 RectStorage<bool>::garbageCollection();
645 }
646};
647
648
649
650class MatrixStorage : public QObject, public RectStorage<bool>
651{
652 Q_OBJECT
653public:
654 explicit MatrixStorage(Map* map) : QObject(map), RectStorage<bool>(map) {}
655 MatrixStorage(const MatrixStorage& other) : QObject(other.parent()), RectStorage<bool>(other) {}
656
657protected Q_SLOTS:
658 virtual void triggerGarbageCollection() {
659 QTimer::singleShot(g_garbageCollectionTimeOut, this, SLOT(garbageCollection()));
660 }
661 virtual void garbageCollection() {
662 RectStorage<bool>::garbageCollection();
663 }
664};
665
666} // namespace Sheets
667} // namespace Calligra
668
669#endif // CALLIGRA_SHEETS_RECT_STORAGE
670