1/* This file is part of the KDE project
2 Copyright 2010 Marijn Kruisselbrink <mkruisselbrink@kde.org>
3 Copyright 2006 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 KSPREAD_RTREE
22#define KSPREAD_RTREE
23
24#include <QRect>
25#include <QVector>
26
27#include <kdebug.h>
28
29#include <KoRTree.h>
30
31#include "calligra_sheets_limits.h"
32
33// Use dynamic_cast instead of cached root node
34// this is much slower but it is here so it is easy to check that still all works.
35//#define DYNAMIC_CAST
36
37namespace Calligra
38{
39namespace Sheets
40{
41
42/**
43 * \class RTree
44 * \brief An R-Tree template
45 * \ingroup Storage
46 *
47 * An R-Tree template extended by special needs of KSpread:
48 * \li adjusts the rectangles on insertion to avoid unwanted overlapping
49 * (caused by different intersection/containment behaviour of QRectF and QRect)
50 * \li checks for sane rectangle dimensions
51 * \li provides insertion and deletion of columns and rows
52 *
53 * \author Stefan Nikolaus <stefan.nikolaus@kdemail.net>
54 */
55template<typename T>
56class RTree : public KoRTree<T>
57{
58public:
59 /**
60 * Column/row insertion mode.
61 */
62 enum InsertMode {
63 /// default insertion mode
64 DefaultInsertMode = 0,
65 /**
66 * Shifts the rectangles, starting from the column/row preceding the
67 * insertion position.
68 * Thus, the inserted columns/rows carry the same data as the previous
69 * column/row.
70 */
71 CopyPrevious = DefaultInsertMode,
72 /**
73 * Shifts the rectangles, starting from the column/row at the insertion
74 * position.
75 * Thus, the inserted columns/rows carry the same data as the current
76 * column/row.
77 */
78 CopyCurrent,
79 /**
80 * Splits the rectangles at the insertion column/row position.
81 * Thus, the inserted columns/rows do not carry any data.
82 */
83 CopyNone
84 };
85
86 /**
87 * Constructs an empty R-Tree.
88 */
89 RTree();
90
91 /**
92 * Destroys the whole R-Tree.
93 */
94 virtual ~RTree();
95
96 /**
97 * @brief Insert data item into the tree
98 *
99 * This will insert a data item into the tree. If necessary the tree will
100 * adjust itself.
101 *
102 * \note Reimplemented for KSpread, because of the QRectF behaviour differs from
103 * the one of QRect. Intersection or containment for boundary lines or points is
104 * not the same, e.g. QRectF(1, 1, 1, 1) intersects QRectF(2, 1, 1, 1) while for
105 * QRect it does not. Therefore, this method subtracts 0.1 from the width and
106 * height of \p rect .
107 *
108 * @param data
109 * @param rect
110 */
111 virtual void insert(const QRectF& rect, const T& data);
112
113 void load(const QList<QPair<QRegion, T> >& data);
114
115 void remove(const QRectF& rect, const T& data, int id = -1);
116
117 /**
118 * Finds all data items at the location \p point .
119 *
120 * \param point where the objects have to be in
121 *
122 * \return objects at the location
123 */
124 virtual QList<T> contains(const QPointF& point) const;
125
126 /**
127 * Finds all data items that cover \p rect completely.
128 *
129 * \param rect where the objects have to be in
130 *
131 * \return objects containing the rect
132 */
133 virtual QList<T> contains(const QRectF& rect) const;
134
135 /**
136 * @brief Find all data items which intersects rect
137 *
138 * \note Reimplemented for KSpread, because of the QRectF behaviour differs from
139 * the one of QRect. Intersection or containment for boundary lines or points is
140 * not the same, e.g. QRectF(1, 1, 1, 1) intersects QRectF(2, 1, 1, 1) while for
141 * QRect it does not. Therefore, this method subtracts 0.1 from the width and
142 * height of \p rect .
143 *
144 * @param rect where the objects have to be in
145 *
146 * @return objects intersecting the rect
147 */
148 virtual QList<T> intersects(const QRectF& rect) const;
149
150 virtual QMap<int, QPair<QRectF, T> > intersectingPairs(const QRectF& rect) const;
151
152 /**
153 * Inserts \p number rows at the position \p position .
154 * It extends or shifts rectangles, respectively.
155 * \return the removed rectangle/data pairs
156 */
157 virtual QList< QPair<QRectF, T> > insertRows(int position, int number, InsertMode mode = DefaultInsertMode);
158
159 /**
160 * Inserts \p number columns at the position \p position .
161 * It extends or shifts rectangles, respectively.
162 * \return the removed rectangle/data pairs
163 */
164 virtual QList< QPair<QRectF, T> > insertColumns(int position, int number, InsertMode mode = DefaultInsertMode);
165
166 /**
167 * Deletes \p number rows at the position \p position .
168 * It shrinks or shifts rectangles, respectively.
169 * \return the removed rectangle/data pairs
170 */
171 virtual QList< QPair<QRectF, T> > removeRows(int position, int number);
172
173 /**
174 * Deletes \p number columns at the position \p position .
175 * It shrinks or shifts rectangles, respectively.
176 * \return the removed rectangle/data pairs
177 */
178 virtual QList< QPair<QRectF, T> > removeColumns(int position, int number);
179
180 /**
181 * Shifts the rows right of \p rect to the right by the width of \p rect .
182 * It extends or shifts rectangles, respectively.
183 * \return the former rectangle/data pairs
184 */
185 virtual QList< QPair<QRectF, T> > insertShiftRight(const QRect& rect, InsertMode mode = DefaultInsertMode);
186
187 /**
188 * Shifts the columns at the bottom of \p rect to the bottom by the height of \p rect .
189 * It extends or shifts rectangles, respectively.
190 * \return the former rectangle/data pairs
191 */
192 virtual QList< QPair<QRectF, T> > insertShiftDown(const QRect& rect, InsertMode mode = DefaultInsertMode);
193
194 /**
195 * Shifts the rows left of \p rect to the left by the width of \p rect .
196 * It shrinks or shifts rectangles, respectively.
197 * \return the former rectangle/data pairs
198 */
199 virtual QList< QPair<QRectF, T> > removeShiftLeft(const QRect& rect);
200
201 /**
202 * Shifts the columns on top of \p rect to the top by the height of \p rect .
203 * It shrinks or shifts rectangles, respectively.
204 * \return the former rectangle/data pairs
205 */
206 virtual QList< QPair<QRectF, T> > removeShiftUp(const QRect& rect);
207
208 /**
209 * Assignment.
210 */
211 void operator=(const RTree& other);
212
213 /**
214 * Returns the bounding box for the entire tree.
215 */
216 QRectF boundingBox() const { return KoRTree<T>::m_root->boundingBox(); }
217
218 void clear() {
219 KoRTree<T>::clear();
220 m_castRoot = dynamic_cast<Node*>(this->m_root);
221 }
222
223protected:
224 class Node;
225 class NonLeafNode;
226 class LeafNode;
227
228 // factory methods
229 virtual LeafNode* createLeafNode(int capacity, int level, typename KoRTree<T>::Node * parent) {
230 return new LeafNode(capacity, level, dynamic_cast<Node*>(parent));
231 }
232 virtual NonLeafNode* createNonLeafNode(int capacity, int level, typename KoRTree<T>::Node * parent) {
233 return new NonLeafNode(capacity, level, dynamic_cast<Node*>(parent));
234 }
235
236 void adjustTree(typename KoRTree<T>::Node *node1, typename KoRTree<T>::Node *node2) {
237 KoRTree<T>::adjustTree(node1, node2);
238 m_castRoot = dynamic_cast<Node*>(this->m_root);
239 }
240
241 void condenseTree(typename KoRTree<T>::Node * node, QVector<typename KoRTree<T>::Node *> & reinsert) {
242 KoRTree<T>::condenseTree(node, reinsert);
243 m_castRoot = dynamic_cast<Node*>(this->m_root);
244 }
245
246private:
247 // disable copy constructor
248 RTree(const RTree& other);
249
250 struct LoadData {
251 QRect rect;
252 const T* data;
253 qreal value;
254 LoadData(const QRect& r, const T* d, qreal v)
255 : rect(r), data(d), value(v)
256 {}
257 };
258 struct LoadDataIndexCompare {
259 const QList<LoadData>& m_data;
260 LoadDataIndexCompare(const QList<LoadData>& data) : m_data(data) {}
261 bool operator()(int a, int b) {
262 return m_data[a].value < m_data[b].value;
263 }
264 };
265 struct NodeLoadDataIndexCompare {
266 const QList<QPair<Node*, qreal> >& m_data;
267 NodeLoadDataIndexCompare(const QList<QPair<Node*, qreal> >& data) : m_data(data) {}
268 bool operator()(int a, int b) {
269 return m_data[a].second < m_data[b].second;
270 }
271 };
272
273 Node* m_castRoot;
274};
275
276/**
277 * Abstract base class for nodes and leaves.
278 */
279template<typename T>
280class RTree<T>::Node : virtual public KoRTree<T>::Node
281{
282public:
283 Node(int capacity, int level, Node * parent)
284 : KoRTree<T>::Node(capacity, level, parent) {}
285 virtual ~Node() {}
286
287 virtual void remove(int index) {
288 KoRTree<T>::Node::remove(index);
289 }
290 virtual void remove(const QRectF& rect, const T& data, int id = -1) = 0;
291 virtual void contains(const QPointF & point, QMap<int, T> & result) const = 0;
292 virtual void contains(const QRectF& rect, QMap<int, T>& result) const = 0;
293 virtual void intersectingPairs(const QRectF& rect, QMap<int, QPair<QRectF, T> >& result) const = 0;
294 virtual QMap< int, QPair<QRectF, T> > insertRows(int position, int number, InsertMode mode) = 0;
295 virtual QMap< int, QPair<QRectF, T> > insertColumns(int position, int number, InsertMode mode) = 0;
296 virtual QMap< int, QPair<QRectF, T> > removeRows(int position, int number) = 0;
297 virtual QMap< int, QPair<QRectF, T> > removeColumns(int position, int number) = 0;
298 virtual const QRectF& childBoundingBox(int index) const {
299 return KoRTree<T>::Node::childBoundingBox(index);
300 }
301 QVector<QRectF> childBoundingBox() const {
302 return this->m_childBoundingBox;
303 }
304private:
305 // disable copy constructor
306 Node(const Node& other);
307};
308
309/**
310 * An R-Tree leaf.
311 */
312template<typename T>
313class RTree<T>::LeafNode : public RTree<T>::Node, public KoRTree<T>::LeafNode
314{
315public:
316 LeafNode(int capacity, int level, Node * parent)
317 : KoRTree<T>::Node(capacity, level, parent)
318 , RTree<T>::Node(capacity, level, parent)
319 , KoRTree<T>::LeafNode(capacity, level, parent) {}
320 virtual ~LeafNode() {}
321
322 virtual void remove(int index) {
323 KoRTree<T>::LeafNode::remove(index);
324 }
325 virtual void remove(const T& data) {
326 KoRTree<T>::LeafNode::remove(data);
327 }
328 virtual void remove(const QRectF& rect, const T& data, int id = -1);
329 virtual void contains(const QPointF & point, QMap<int, T> & result) const {
330 KoRTree<T>::LeafNode::contains(point, result);
331 }
332 virtual void contains(const QRectF& rect, QMap<int, T>& result) const;
333 virtual void intersectingPairs(const QRectF& rect, QMap<int, QPair<QRectF, T> >& result) const;
334 virtual QMap< int, QPair<QRectF, T> > insertRows(int position, int number, InsertMode mode);
335 virtual QMap< int, QPair<QRectF, T> > insertColumns(int position, int number, InsertMode mode);
336 virtual QMap< int, QPair<QRectF, T> > removeRows(int position, int number);
337 virtual QMap< int, QPair<QRectF, T> > removeColumns(int position, int number);
338 virtual void operator=(const LeafNode& other);
339private:
340 // disable copy constructor
341 LeafNode(const LeafNode& other);
342};
343
344/**
345 * An R-Tree node.
346 */
347template<typename T>
348class RTree<T>::NonLeafNode : public RTree<T>::Node, public KoRTree<T>::NonLeafNode
349{
350public:
351 NonLeafNode(int capacity, int level, Node * parent)
352 : KoRTree<T>::Node(capacity, level, parent)
353 , RTree<T>::Node(capacity, level, parent)
354 , KoRTree<T>::NonLeafNode(capacity, level, parent) {}
355 virtual ~NonLeafNode() {}
356
357 virtual void remove(int index) {
358 KoRTree<T>::NonLeafNode::remove(index);
359 }
360 virtual void remove(const QRectF& rect, const T& data, int id = -1);
361 virtual void contains(const QPointF & point, QMap<int, T> & result) const {
362 KoRTree<T>::NonLeafNode::contains(point, result);
363 }
364 virtual void contains(const QRectF& rect, QMap<int, T>& result) const;
365 virtual void intersectingPairs(const QRectF& rect, QMap<int, QPair<QRectF, T> >& result) const;
366 virtual QMap< int, QPair<QRectF, T> > insertRows(int position, int number, InsertMode mode);
367 virtual QMap< int, QPair<QRectF, T> > insertColumns(int position, int number, InsertMode mode);
368 virtual QMap< int, QPair<QRectF, T> > removeRows(int position, int number);
369 virtual QMap< int, QPair<QRectF, T> > removeColumns(int position, int number);
370 virtual void operator=(const NonLeafNode& other);
371private:
372 // disable copy constructor
373 NonLeafNode(const NonLeafNode& other);
374};
375
376
377/////////////////////////////////////////////////////////////////////////////
378// RTree definition
379//
380template<typename T>
381RTree<T>::RTree()
382 : KoRTree<T>(8, 4)
383{
384 delete this->m_root;
385 this->m_root = new LeafNode(this->m_capacity + 1, 0, 0);
386 m_castRoot = dynamic_cast<Node*>(this->m_root);
387}
388
389template<typename T>
390RTree<T>::~RTree()
391{
392}
393
394template<typename T>
395void RTree<T>::insert(const QRectF& rect, const T& data)
396{
397 Q_ASSERT(rect.x() - (int)rect.x() == 0.0);
398 Q_ASSERT(rect.y() - (int)rect.y() == 0.0);
399 Q_ASSERT(rect.height() - (int)rect.height() == 0.0);
400 Q_ASSERT(rect.width() - (int)rect.width() == 0.0);
401 KoRTree<T>::insert(rect.normalized().adjusted(0, 0, -0.1, -0.1), data);
402}
403
404static inline qreal calcLoadingRectValue(const QRectF& r)
405{
406 QPointF center = r.center();
407 // TODO: better value would be hilbert value of center of rect
408 return center.x();
409}
410
411template<typename T>
412void RTree<T>::load(const QList<QPair<QRegion, T> >& data)
413{
414 // clear current tree
415 clear();
416
417 // make rect->data mapping
418 typedef QPair<QRegion, T> DataRegion;
419
420 QList<LoadData> rectData;
421 QVector<int> indices;
422 foreach (const DataRegion& dataRegion, data) {
423 foreach (const QRect& rect, dataRegion.first.rects()) {
424 qreal h = calcLoadingRectValue(rect);
425 rectData.append(LoadData(rect, &dataRegion.second, h));
426 indices.append(indices.size());
427 }
428 }
429
430 qSort(indices.begin(), indices.end(), LoadDataIndexCompare(rectData));
431
432 QList<QPair<Node*, qreal> > nodes;
433 // create LeafNodes
434 for (int i = 0; i < indices.size(); i += KoRTree<T>::m_capacity) {
435 LeafNode* n = createLeafNode(KoRTree<T>::m_capacity + 1, 0, 0);
436 for (int j = 0; j < KoRTree<T>::m_capacity && i+j < indices.size(); j++) {
437 const LoadData& d = rectData[indices[i+j]];
438 n->insert(QRectF(d.rect).normalized().adjusted(0, 0, -0.1, -0.1), *d.data, LeafNode::dataIdCounter + indices[i+j]);
439 }
440 n->updateBoundingBox();
441 nodes.append(qMakePair<Node*, qreal>(n, calcLoadingRectValue(n->boundingBox())));
442 }
443 LeafNode::dataIdCounter += indices.size();
444
445 while (nodes.size() > 1) {
446 indices.resize(nodes.size());
447 for (int i = 0; i < indices.size(); i++) indices[i] = i;
448
449 qSort(indices.begin(), indices.end(), NodeLoadDataIndexCompare(nodes));
450
451 QList<QPair<Node*, qreal> > newNodes;
452
453 for (int i = 0; i < indices.size(); i += KoRTree<T>::m_capacity) {
454 NonLeafNode* n = createNonLeafNode(KoRTree<T>::m_capacity + 1, 0, 0);
455 for (int j = 0; j < KoRTree<T>::m_capacity && i+j < indices.size(); j++) {
456 Node* oldNode = nodes[indices[i+j]].first;
457 n->insert(oldNode->boundingBox(), oldNode);
458 }
459 n->updateBoundingBox();
460 newNodes.append(qMakePair<Node*, qreal>(n, calcLoadingRectValue(n->boundingBox())));
461 }
462 nodes = newNodes;
463 }
464
465 if (!nodes.isEmpty()) {
466 // set root node
467 delete KoRTree<T>::m_root;
468 KoRTree<T>::m_root = nodes.first().first;
469 m_castRoot = dynamic_cast<Node*>(this->m_root);
470 }
471}
472
473template<typename T>
474void RTree<T>::remove(const QRectF& rect, const T& data, int id)
475{
476 Q_ASSERT(rect.x() - (int)rect.x() == 0.0);
477 Q_ASSERT(rect.y() - (int)rect.y() == 0.0);
478 Q_ASSERT(rect.height() - (int)rect.height() == 0.0);
479 Q_ASSERT(rect.width() - (int)rect.width() == 0.0);
480#ifdef DYNAMIC_CAST
481 dynamic_cast<Node*>(this->m_root)->remove(rect.normalized().adjusted(0, 0, -0.1, -0.1), data, id);
482#else
483 m_castRoot->remove(rect.normalized().adjusted(0, 0, -0.1, -0.1), data, id);
484#endif
485}
486
487template<typename T>
488QList<T> RTree<T>::contains(const QPointF& point) const
489{
490 return KoRTree<T>::contains(point);
491}
492
493template<typename T>
494QList<T> RTree<T>::contains(const QRectF& rect) const
495{
496 Q_ASSERT(rect.x() - (int)rect.x() == 0.0);
497 Q_ASSERT(rect.y() - (int)rect.y() == 0.0);
498 Q_ASSERT(rect.height() - (int)rect.height() == 0.0);
499 Q_ASSERT(rect.width() - (int)rect.width() == 0.0);
500 QMap<int, T> result;
501#ifdef DYNAMIC_CAST
502 dynamic_cast<Node*>(this->m_root)->contains(rect.normalized().adjusted(0, 0, -0.1, -0.1), result);
503#else
504 m_castRoot->contains(rect.normalized().adjusted(0, 0, -0.1, -0.1), result);
505#endif
506 return result.values();
507}
508
509template<typename T>
510QList<T> RTree<T>::intersects(const QRectF& rect) const
511{
512 Q_ASSERT(rect.x() - (int)rect.x() == 0.0);
513 Q_ASSERT(rect.y() - (int)rect.y() == 0.0);
514 Q_ASSERT(rect.height() - (int)rect.height() == 0.0);
515 Q_ASSERT(rect.width() - (int)rect.width() == 0.0);
516 return KoRTree<T>::intersects(rect.normalized().adjusted(0, 0, -0.1, -0.1));
517}
518
519template<typename T>
520QMap<int, QPair<QRectF, T> > RTree<T>::intersectingPairs(const QRectF& rect) const
521{
522 Q_ASSERT(rect.x() - (int)rect.x() == 0.0);
523 Q_ASSERT(rect.y() - (int)rect.y() == 0.0);
524 Q_ASSERT(rect.height() - (int)rect.height() == 0.0);
525 Q_ASSERT(rect.width() - (int)rect.width() == 0.0);
526 QMap<int, QPair<QRectF, T> > result;
527#ifdef DYNAMIC_CAST
528 dynamic_cast<Node*>(this->m_root)->intersectingPairs(rect.normalized().adjusted(0, 0, -0.1, -0.1), result);
529#else
530 m_castRoot->intersectingPairs(rect.normalized().adjusted(0, 0, -0.1, -0.1), result);
531#endif
532 return result;
533}
534
535template<typename T>
536QList< QPair<QRectF, T> > RTree<T>::insertRows(int position, int number, InsertMode mode)
537{
538 Q_ASSERT(position >= 1);
539 Q_ASSERT(position <= KS_rowMax);
540 if (position < 1 || position > KS_rowMax)
541 return QList< QPair<QRectF, T> >();
542#ifdef DYNAMIC_CAST
543 return dynamic_cast<Node*>(this->m_root)->insertRows(position, number, mode).values();
544#else
545 return m_castRoot->insertRows(position, number, mode).values();
546#endif
547}
548
549template<typename T>
550QList< QPair<QRectF, T> > RTree<T>::insertColumns(int position, int number, InsertMode mode)
551{
552 Q_ASSERT(position >= 1);
553 Q_ASSERT(position <= KS_colMax);
554 if (position < 1 || position > KS_colMax)
555 return QList< QPair<QRectF, T> >();
556#ifdef DYNAMIC_CAST
557 return dynamic_cast<Node*>(this->m_root)->insertColumns(position, number, mode).values();
558#else
559 return m_castRoot->insertColumns(position, number, mode).values();
560#endif
561}
562
563template<typename T>
564QList< QPair<QRectF, T> > RTree<T>::removeRows(int position, int number)
565{
566 Q_ASSERT(position >= 1);
567 Q_ASSERT(position <= KS_rowMax);
568 if (position < 1 || position > KS_rowMax)
569 return QList< QPair<QRectF, T> >();
570#ifdef DYNAMIC_CAST
571 return dynamic_cast<Node*>(this->m_root)->removeRows(position, number).values();
572#else
573 return m_castRoot->removeRows(position, number).values();
574#endif
575}
576
577template<typename T>
578QList< QPair<QRectF, T> > RTree<T>::removeColumns(int position, int number)
579{
580 Q_ASSERT(position >= 1);
581 Q_ASSERT(position <= KS_colMax);
582 if (position < 1 || position > KS_colMax)
583 return QList< QPair<QRectF, T> >();
584#ifdef DYNAMIC_CAST
585 return dynamic_cast<Node*>(this->m_root)->removeColumns(position, number).values();
586#else
587 return m_castRoot->removeColumns(position, number).values();
588#endif
589}
590
591template<typename T>
592QList< QPair<QRectF, T> > RTree<T>::insertShiftRight(const QRect& r, InsertMode mode)
593{
594 const QRect rect(r.normalized());
595 if (rect.left() < 1 || rect.left() > KS_colMax)
596 return QList< QPair<QRectF, T> >();
597 const QRect boundingRect = QRect(rect.topLeft(), QPoint(KS_colMax, rect.bottom()));
598 const QList< QPair<QRectF, T> > oldPairs = intersectingPairs(boundingRect).values();
599 if (oldPairs.isEmpty())
600 return QList< QPair<QRectF, T> >();
601 // insert default data at the bounding rectangle
602 insert(boundingRect, T());
603 // fill the inserted rectangle
604 if (mode != CopyNone) {
605 const int offset = (mode == CopyPrevious) ? 1 : 0;
606 const QRect copyRect = QRect(rect.left() - offset, rect.top(), 1, rect.height());
607 const QList< QPair<QRectF, T> > copyPairs = intersectingPairs(copyRect).values();
608 for (int i = 0; i < copyPairs.count(); ++i) {
609 insert((copyPairs[i].first.toRect() & copyRect).adjusted(offset, 0, rect.width() + offset - 1, 0), copyPairs[i].second);
610 }
611 }
612 // insert the data at the shifted rectangles
613 for (int i = 0; i < oldPairs.count(); ++i) {
614 const QRect shiftedRect = oldPairs[i].first.toRect().adjusted(rect.width(), 0, rect.width(), 0);
615 insert(shiftedRect & boundingRect, oldPairs[i].second);
616 }
617 return oldPairs;
618}
619
620template<typename T>
621QList< QPair<QRectF, T> > RTree<T>::insertShiftDown(const QRect& r, InsertMode mode)
622{
623 Q_UNUSED(mode);
624 const QRect rect(r.normalized());
625 if (rect.top() < 1 || rect.top() > KS_rowMax)
626 return QList< QPair<QRectF, T> >();
627 const QRect boundingRect = QRect(rect.topLeft(), QPoint(rect.right(), KS_rowMax));
628 const QList< QPair<QRectF, T> > oldPairs = intersectingPairs(boundingRect).values();
629 if (oldPairs.isEmpty())
630 return QList< QPair<QRectF, T> >();
631 // insert default data at the bounding rectangle
632 insert(boundingRect, T());
633 // fill the inserted rectangle
634 if (mode != CopyNone) {
635 const int offset = (mode == CopyPrevious) ? 1 : 0;
636 const QRect copyRect = QRect(rect.left(), rect.top() - offset, rect.width(), 1);
637 const QList< QPair<QRectF, T> > copyPairs = intersectingPairs(copyRect).values();
638 for (int i = 0; i < copyPairs.count(); ++i) {
639 insert((copyPairs[i].first.toRect() & copyRect).adjusted(0, offset, 0, rect.height() + offset - 1), copyPairs[i].second);
640 }
641 }
642 // insert the data at the shifted rectangles
643 for (int i = 0; i < oldPairs.count(); ++i) {
644 const QRect shiftedRect = oldPairs[i].first.toRect().adjusted(0, rect.height(), 0, rect.height());
645 insert(shiftedRect & boundingRect, oldPairs[i].second);
646 }
647 return oldPairs;
648}
649
650template<typename T>
651QList< QPair<QRectF, T> > RTree<T>::removeShiftLeft(const QRect& r)
652{
653 const QRect rect(r.normalized());
654 if (rect.left() < 1 || rect.left() > KS_colMax)
655 return QList< QPair<QRectF, T> >();
656 const QRect boundingRect = QRect(rect.topLeft(), QPoint(KS_colMax, rect.bottom()));
657 const QList< QPair<QRectF, T> > oldPairs = intersectingPairs(boundingRect).values();
658 if (oldPairs.isEmpty())
659 return QList< QPair<QRectF, T> >();
660 // insert default data at the bounding rectangle
661 insert(boundingRect, T());
662 // insert the data at the shifted rectangles
663 for (int i = 0; i < oldPairs.count(); ++i) {
664 const QRect shiftedRect = oldPairs[i].first.toRect().adjusted(-rect.width(), 0, -rect.width(), 0);
665 insert(shiftedRect & boundingRect, oldPairs[i].second);
666 }
667 return oldPairs;
668}
669
670template<typename T>
671QList< QPair<QRectF, T> > RTree<T>::removeShiftUp(const QRect& r)
672{
673 const QRect rect(r.normalized());
674 if (rect.top() < 1 || rect.top() > KS_rowMax)
675 return QList< QPair<QRectF, T> >();
676 const QRect boundingRect = QRect(rect.topLeft(), QPoint(rect.right(), KS_rowMax));
677 const QList< QPair<QRectF, T> > oldPairs = intersectingPairs(boundingRect).values();
678 if (oldPairs.isEmpty())
679 return QList< QPair<QRectF, T> >();
680 // insert default data at the bounding rectangle
681 insert(boundingRect, T());
682 // insert the data at the shifted rectangles
683 for (int i = 0; i < oldPairs.count(); ++i) {
684 const QRect shiftedRect = oldPairs[i].first.toRect().adjusted(0, -rect.height(), 0, -rect.height());
685 insert(shiftedRect & boundingRect, oldPairs[i].second);
686 }
687 return oldPairs;
688}
689
690template<typename T>
691void RTree<T>::operator=(const RTree<T>& other)
692{
693 this->m_capacity = other.m_capacity;
694 this->m_minimum = other.m_minimum;
695 delete this->m_root;
696 if (other.m_root->isLeaf()) {
697 this->m_root = new LeafNode(this->m_capacity + 1, 0, 0);
698 *dynamic_cast<LeafNode*>(this->m_root) = *dynamic_cast<LeafNode*>(other.m_root);
699 } else {
700 this->m_root = new NonLeafNode(this->m_capacity + 1, 0, 0);
701 *dynamic_cast<NonLeafNode*>(this->m_root) = *dynamic_cast<NonLeafNode*>(other.m_root);
702 }
703 m_castRoot = dynamic_cast<Node*>(this->m_root);
704}
705
706/////////////////////////////////////////////////////////////////////////////
707// RTree<T>::LeafNode definition
708//
709template<typename T>
710void RTree<T>::LeafNode::remove(const QRectF& rect, const T& data, int id)
711{
712 for (int i = 0; i < this->m_counter; ++i) {
713 if (this->m_childBoundingBox[i] == rect && this->m_data[i] == data && (id == -1 || this->m_dataIds[i] == id)) {
714 //qDebug() << "LeafNode::remove id" << i;
715 KoRTree<T>::LeafNode::remove(i);
716 break;
717 }
718 }
719}
720
721template<typename T>
722void RTree<T>::LeafNode::contains(const QRectF& rect, QMap<int, T>& result) const
723{
724 for (int i = 0; i < this->m_counter; ++i) {
725 if (this->m_childBoundingBox[i].contains(rect)) {
726 result.insert(this->m_dataIds[i], this->m_data[i]);
727 }
728 }
729}
730
731template<typename T>
732void RTree<T>::LeafNode::intersectingPairs(const QRectF& rect, QMap<int, QPair<QRectF, T> >& result) const
733{
734 for (int i = 0; i < this->m_counter; ++i) {
735 if (this->m_childBoundingBox[i].intersects(rect)) {
736 QRectF rect = this->m_childBoundingBox[i].adjusted(0, 0, 0.1, 0.1);
737 result.insert(this->m_dataIds[i], qMakePair(rect, this->m_data[i]));
738 }
739 }
740}
741
742template<typename T>
743QMap< int, QPair<QRectF, T> > RTree<T>::LeafNode::insertRows(int position, int number, InsertMode mode)
744{
745 if (position - (mode == CopyPrevious ? 1 : 0) > this->m_boundingBox.bottom())
746 return QMap< int, QPair<QRectF, T> >();
747
748 QMap< int, QPair<QRectF, T> > result;
749
750 int shift = 0, endShift = number;
751 // Don't process complete columns.
752 if (this->m_boundingBox.top() != 1 || this->m_boundingBox.bottom() != KS_rowMax) {
753 if (mode == CopyNone)
754 shift = 0;
755 else if (position - (mode == CopyPrevious ? 1 : 0) < this->m_boundingBox.top())
756 shift = number;
757 if (position - (mode == CopyPrevious ? 1 : 0) < this->m_boundingBox.toRect().bottom())
758 endShift = number;
759 else
760 endShift = 0;
761 this->m_boundingBox.adjust(0, shift, 0, endShift);
762 }
763
764 for (int i = 0; i < this->childCount(); ++i) {
765 // Don't process complete columns.
766 if (this->m_childBoundingBox[i].top() == 1 && this->m_childBoundingBox[i].bottom() == KS_rowMax)
767 continue;
768
769 if (mode == CopyNone)
770 shift = 0;
771 else if (position - (mode == CopyPrevious ? 1 : 0) < this->m_childBoundingBox[i].top())
772 shift = number;
773 else
774 shift = 0;
775
776 if (position - (mode == CopyPrevious ? 1 : 0) < this->m_childBoundingBox[i].toRect().bottom())
777 endShift = number;
778 else
779 endShift = 0;
780 this->m_childBoundingBox[i].adjust(0, shift, 0, endShift);
781 }
782
783 return QMap< int, QPair<QRectF, T> >(); // FIXME
784}
785
786template<typename T>
787QMap< int, QPair<QRectF, T> > RTree<T>::LeafNode::insertColumns(int position, int number, InsertMode mode)
788{
789 if (position - (mode == CopyPrevious ? 1 : 0) > this->m_boundingBox.right())
790 return QMap< int, QPair<QRectF, T> >();
791
792 QMap< int, QPair<QRectF, T> > result;
793
794 int shift = 0;
795 // Don't process complete rows.
796 if (this->m_boundingBox.left() != 1 || this->m_boundingBox.right() != KS_colMax) {
797 if (mode == CopyNone)
798 shift = 0;
799 else if (position - (mode == CopyPrevious ? 1 : 0) < this->m_boundingBox.left())
800 shift = number;
801 this->m_boundingBox.adjust(shift, 0, number, 0);
802 }
803
804 for (int i = 0; i < this->childCount(); ++i) {
805 // Don't process complete rows.
806 if (this->m_childBoundingBox[i].left() == 1 && this->m_childBoundingBox[i].right() == KS_rowMax)
807 continue;
808
809 if (mode == CopyNone)
810 shift = 0;
811 else if (position - (mode == CopyPrevious ? 1 : 0) < this->m_childBoundingBox[i].left())
812 shift = number;
813 else
814 shift = 0;
815 this->m_childBoundingBox[i].adjust(shift, 0, number, 0);
816 }
817
818 return QMap< int, QPair<QRectF, T> >(); // FIXME
819}
820
821template<typename T>
822QMap< int, QPair<QRectF, T> > RTree<T>::LeafNode::removeRows(int position, int number)
823{
824 if (position > this->m_boundingBox.bottom())
825 return QMap< int, QPair<QRectF, T> >();
826
827 QMap< int, QPair<QRectF, T> > removedPairs;
828
829 QRect rect = this->m_boundingBox.toRect();
830 int shift = 0;
831 int cut = 0;
832 // Don't process complete columns.
833 if (this->m_boundingBox.top() != 1 || this->m_boundingBox.bottom() != KS_rowMax) {
834 if (position < rect.top()) {
835 shift = qMin(rect.top() - position, number);
836 cut = qMax(0, position + number - rect.top());
837 } else {
838 shift = 0;
839 cut = qMin(number, rect.bottom() - position + 1);
840 }
841 this->m_boundingBox.adjust(0, -shift, 0, -shift - cut);
842 }
843
844 for (int i = 0; i < this->childCount(); ++i) {
845 // Don't process complete columns.
846 if (this->m_childBoundingBox[i].top() == 1 && this->m_childBoundingBox[i].bottom() == KS_rowMax)
847 continue;
848
849 const QRectF oldRect(this->m_childBoundingBox[ i ]);
850 rect = this->m_childBoundingBox[i].toRect();
851 if (position < rect.top()) {
852 shift = qMin(rect.top() - position, number);
853 cut = qMax(0, position + number - rect.top());
854 } else {
855 shift = 0;
856 cut = qMin(number, rect.bottom() - position + 1);
857 }
858 this->m_childBoundingBox[i].adjust(0, -shift, 0, -shift - cut);
859
860 if (this->m_childBoundingBox[ i ].isEmpty()) {
861 removedPairs.insert(this->m_dataIds[i], qMakePair(oldRect, this->m_data[i]));
862 KoRTree<T>::LeafNode::remove(i--);
863 }
864 }
865 return removedPairs;
866}
867
868template<typename T>
869QMap< int, QPair<QRectF, T> > RTree<T>::LeafNode::removeColumns(int position, int number)
870{
871 if (position > this->m_boundingBox.right())
872 return QMap< int, QPair<QRectF, T> >();
873
874 QMap< int, QPair<QRectF, T> > removedPairs;
875
876 QRect rect = this->m_boundingBox.toRect();
877 int shift = 0;
878 int cut = 0;
879 // Don't process complete rows.
880 if (this->m_boundingBox.left() != 1 || this->m_boundingBox.right() != KS_colMax) {
881 if (position < rect.left()) {
882 shift = qMin(rect.left() - position, number);
883 cut = qMax(0, position + number - rect.left());
884 } else {
885 shift = 0;
886 cut = qMin(number, rect.right() - position + 1);
887 }
888 this->m_boundingBox.adjust(-shift, 0, -shift - cut, 0);
889 }
890
891 for (int i = 0; i < this->childCount(); ++i) {
892 // Don't process complete rows.
893 if (this->m_childBoundingBox[i].left() == 1 && this->m_childBoundingBox[i].right() == KS_rowMax)
894 continue;
895
896 const QRectF oldRect(this->m_childBoundingBox[ i ]);
897 rect = this->m_childBoundingBox[i].toRect();
898 if (position < rect.left()) {
899 shift = qMin(rect.left() - position, number);
900 cut = qMax(0, position + number - rect.left());
901 } else {
902 shift = 0;
903 cut = qMin(number, rect.right() - position + 1);
904 }
905 this->m_childBoundingBox[i].adjust(-shift, 0, -shift - cut, 0);
906
907 if (this->m_childBoundingBox[ i ].isEmpty()) {
908 removedPairs.insert(this->m_dataIds[i], qMakePair(oldRect, this->m_data[i]));
909 KoRTree<T>::LeafNode::remove(i--);
910 }
911 }
912 return removedPairs;
913}
914
915template<typename T>
916void RTree<T>::LeafNode::operator=(const LeafNode& other)
917{
918 // leave alone the m_parent
919 this->m_boundingBox = other.m_boundingBox;
920 this->m_childBoundingBox = other.m_childBoundingBox;
921 this->m_counter = other.m_counter;
922 this->m_place = other.m_place;
923#ifdef CALLIGRA_RTREE_DEBUG
924 this->m_nodeId = other.m_nodeId;
925#endif
926 this->m_level = other.m_level;
927 this->m_data = other.m_data;
928 this->m_dataIds = other.m_dataIds;
929}
930
931/////////////////////////////////////////////////////////////////////////////
932// RTree<T>::NonLeafNode definition
933//
934template<typename T>
935void RTree<T>::NonLeafNode::remove(const QRectF& rect, const T& data, int id)
936{
937 for (int i = 0; i < this->m_counter; ++i) {
938 if (this->m_childBoundingBox[i].contains(rect)) {
939 dynamic_cast<Node*>(this->m_childs[i])->remove(rect, data, id);
940 }
941 }
942}
943
944template<typename T>
945void RTree<T>::NonLeafNode::contains(const QRectF& rect, QMap<int, T>& result) const
946{
947 for (int i = 0; i < this->m_counter; ++i) {
948 if (this->m_childBoundingBox[i].intersects(rect)) {
949 this->m_childs[i]->intersects(rect, result);
950 }
951 }
952}
953
954template<typename T>
955void RTree<T>::NonLeafNode::intersectingPairs(const QRectF& rect, QMap<int, QPair<QRectF, T> >& result) const
956{
957 for (int i = 0; i < this->m_counter; ++i) {
958 if (this->m_childBoundingBox[i].intersects(rect)) {
959 dynamic_cast<Node*>(this->m_childs[i])->intersectingPairs(rect, result);
960 }
961 }
962}
963
964template<typename T>
965QMap< int, QPair<QRectF, T> > RTree<T>::NonLeafNode::insertRows(int position, int number, InsertMode mode)
966{
967 if (position - (mode == CopyPrevious ? 1 : 0) > this->m_boundingBox.bottom())
968 return QMap< int, QPair<QRectF, T> >();
969
970 QMap< int, QPair<QRectF, T> > result;
971
972 for (int i = 0; i < this->childCount(); ++i) {
973 this->m_childBoundingBox[i].adjust(0, (position < this->m_childBoundingBox[i].top()) ? number : 0, 0, number);
974 result.unite(dynamic_cast<Node*>(this->m_childs[i])->insertRows(position, number, mode));
975 }
976
977 // position < m_rect.top() ? shift : extend
978 this->m_boundingBox.adjust(0, (position < this->m_boundingBox.top()) ? number : 0, 0, number);
979 return QMap< int, QPair<QRectF, T> >(); // FIXME
980}
981
982template<typename T>
983QMap< int, QPair<QRectF, T> > RTree<T>::NonLeafNode::insertColumns(int position, int number, InsertMode mode)
984{
985 if (position - (mode == CopyPrevious ? 1 : 0) > this->m_boundingBox.right())
986 return QMap< int, QPair<QRectF, T> >();
987
988 QMap< int, QPair<QRectF, T> > result;
989
990 for (int i = 0; i < this->childCount(); ++i) {
991 this->m_childBoundingBox[i].adjust((position < this->m_childBoundingBox[i].left()) ? number : 0, 0, number, 0);
992 result.unite(dynamic_cast<Node*>(this->m_childs[i])->insertColumns(position, number, mode));
993 }
994
995 // position < m_rect.left() ? shift : extend
996 this->m_boundingBox.adjust((position < this->m_boundingBox.left()) ? number : 0, 0, number, 0);
997 return QMap< int, QPair<QRectF, T> >(); // FIXME
998}
999
1000template<typename T>
1001QMap< int, QPair<QRectF, T> > RTree<T>::NonLeafNode::removeRows(int position, int number)
1002{
1003 if (position > this->m_boundingBox.bottom())
1004 return QMap< int, QPair<QRectF, T> >();
1005
1006 QMap< int, QPair<QRectF, T> > removedPairs;
1007
1008 QRect rect = this->m_boundingBox.toRect();
1009 int shift = 0;
1010 int cut = 0;
1011 if (position < rect.top()) {
1012 shift = qMin(rect.top() - position, number);
1013 cut = qMax(0, position + number - rect.top());
1014 } else {
1015 shift = 0;
1016 cut = qMin(number, rect.bottom() - position + 1);
1017 }
1018 this->m_boundingBox.adjust(0, -shift, 0, -shift - cut);
1019
1020 for (int i = 0; i < this->childCount(); ++i) {
1021 rect = this->m_childBoundingBox[i].toRect();
1022 if (position < rect.top()) {
1023 shift = qMin(rect.top() - position, number);
1024 cut = qMax(0, position + number - rect.top());
1025 } else {
1026 shift = 0;
1027 cut = qMin(number, rect.bottom() - position + 1);
1028 }
1029 this->m_childBoundingBox[i].adjust(0, -shift, 0, -shift - cut);
1030
1031 removedPairs.unite(dynamic_cast<Node*>(this->m_childs[i])->removeRows(position, number));
1032 if (this->m_childBoundingBox[ i ].isEmpty()) {
1033 delete this->m_childs[i];
1034 KoRTree<T>::NonLeafNode::remove(i--);
1035 }
1036 }
1037 return removedPairs;
1038}
1039
1040template<typename T>
1041QMap< int, QPair<QRectF, T> > RTree<T>::NonLeafNode::removeColumns(int position, int number)
1042{
1043 if (position > this->m_boundingBox.right())
1044 return QMap< int, QPair<QRectF, T> >();
1045
1046 QMap< int, QPair<QRectF, T> > removedPairs;
1047
1048 QRect rect = this->m_boundingBox.toRect();
1049 int shift = 0;
1050 int cut = 0;
1051 if (position < rect.left()) {
1052 shift = qMin(rect.left() - position, number);
1053 cut = qMax(0, position + number - rect.left());
1054 } else {
1055 shift = 0;
1056 cut = qMin(number, rect.right() - position + 1);
1057 }
1058 this->m_boundingBox.adjust(-shift, 0, -shift - cut, 0);
1059
1060 for (int i = 0; i < this->childCount(); ++i) {
1061 rect = this->m_childBoundingBox[i].toRect();
1062 if (position < rect.left()) {
1063 shift = qMin(rect.left() - position, number);
1064 cut = qMax(0, position + number - rect.left());
1065 } else {
1066 shift = 0;
1067 cut = qMin(number, rect.right() - position + 1);
1068 }
1069 this->m_childBoundingBox[i].adjust(-shift, 0, -shift - cut, 0);
1070
1071 removedPairs.unite(dynamic_cast<Node*>(this->m_childs[i])->removeColumns(position, number));
1072 if (this->m_childBoundingBox[ i ].isEmpty()) {
1073 delete this->m_childs[i];
1074 KoRTree<T>::NonLeafNode::remove(i--);
1075 }
1076 }
1077 return removedPairs;
1078}
1079
1080template<typename T>
1081void RTree<T>::NonLeafNode::operator=(const NonLeafNode& other)
1082{
1083 // leave alone the m_parent
1084 this->m_boundingBox = other.m_boundingBox;
1085 this->m_childBoundingBox = other.childBoundingBox();
1086 this->m_counter = other.m_counter;
1087 this->m_place = other.m_place;
1088#ifdef CALLIGRA_RTREE_DEBUG
1089 this->m_nodeId = other.m_nodeId;
1090#endif
1091 this->m_level = other.m_level;
1092 for (int i = 0; i < other.m_counter; ++i) {
1093 if (other.m_childs[i]->isLeaf()) {
1094 LeafNode* child = dynamic_cast<LeafNode*>(other.m_childs[i]);
1095 this->m_childs[i] = new LeafNode(child->childBoundingBox().size(), child->level(), this);
1096 *dynamic_cast<LeafNode*>(this->m_childs[i]) = *child;
1097 } else {
1098 NonLeafNode* child = dynamic_cast<NonLeafNode*>(other.m_childs[i]);
1099 this->m_childs[i] = new NonLeafNode(child->childBoundingBox().size(), child->level(), this);
1100 *dynamic_cast<NonLeafNode*>(this->m_childs[i]) = *child;
1101 }
1102 }
1103}
1104
1105} // namespace Sheets
1106} // namespace Calligra
1107
1108#endif // KSPREAD_RTREE
1109