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 | |
37 | namespace Calligra |
38 | { |
39 | namespace 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 | */ |
55 | template<typename T> |
56 | class RTree : public KoRTree<T> |
57 | { |
58 | public: |
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 | |
223 | protected: |
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 | |
246 | private: |
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 | */ |
279 | template<typename T> |
280 | class RTree<T>::Node : virtual public KoRTree<T>::Node |
281 | { |
282 | public: |
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 | } |
304 | private: |
305 | // disable copy constructor |
306 | Node(const Node& other); |
307 | }; |
308 | |
309 | /** |
310 | * An R-Tree leaf. |
311 | */ |
312 | template<typename T> |
313 | class RTree<T>::LeafNode : public RTree<T>::Node, public KoRTree<T>::LeafNode |
314 | { |
315 | public: |
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); |
339 | private: |
340 | // disable copy constructor |
341 | LeafNode(const LeafNode& other); |
342 | }; |
343 | |
344 | /** |
345 | * An R-Tree node. |
346 | */ |
347 | template<typename T> |
348 | class RTree<T>::NonLeafNode : public RTree<T>::Node, public KoRTree<T>::NonLeafNode |
349 | { |
350 | public: |
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); |
371 | private: |
372 | // disable copy constructor |
373 | NonLeafNode(const NonLeafNode& other); |
374 | }; |
375 | |
376 | |
377 | ///////////////////////////////////////////////////////////////////////////// |
378 | // RTree definition |
379 | // |
380 | template<typename T> |
381 | RTree<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 | |
389 | template<typename T> |
390 | RTree<T>::~RTree() |
391 | { |
392 | } |
393 | |
394 | template<typename T> |
395 | void 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 | |
404 | static 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 | |
411 | template<typename T> |
412 | void 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 | |
473 | template<typename T> |
474 | void 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 | |
487 | template<typename T> |
488 | QList<T> RTree<T>::contains(const QPointF& point) const |
489 | { |
490 | return KoRTree<T>::contains(point); |
491 | } |
492 | |
493 | template<typename T> |
494 | QList<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 | |
509 | template<typename T> |
510 | QList<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 | |
519 | template<typename T> |
520 | QMap<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 | |
535 | template<typename T> |
536 | QList< 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 | |
549 | template<typename T> |
550 | QList< 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 | |
563 | template<typename T> |
564 | QList< 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 | |
577 | template<typename T> |
578 | QList< 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 | |
591 | template<typename T> |
592 | QList< 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 | |
620 | template<typename T> |
621 | QList< 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 | |
650 | template<typename T> |
651 | QList< 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 | |
670 | template<typename T> |
671 | QList< 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 | |
690 | template<typename T> |
691 | void 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 | // |
709 | template<typename T> |
710 | void 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 | |
721 | template<typename T> |
722 | void 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 | |
731 | template<typename T> |
732 | void 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 | |
742 | template<typename T> |
743 | QMap< 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 | |
786 | template<typename T> |
787 | QMap< 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 | |
821 | template<typename T> |
822 | QMap< 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 | |
868 | template<typename T> |
869 | QMap< 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 | |
915 | template<typename T> |
916 | void 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 | // |
934 | template<typename T> |
935 | void 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 | |
944 | template<typename T> |
945 | void 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 | |
954 | template<typename T> |
955 | void 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 | |
964 | template<typename T> |
965 | QMap< 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 | |
982 | template<typename T> |
983 | QMap< 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 | |
1000 | template<typename T> |
1001 | QMap< 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 | |
1040 | template<typename T> |
1041 | QMap< 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 | |
1080 | template<typename T> |
1081 | void 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 | |