Warning, file /office/calligra/libs/flake/KoRTree.h was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).
0001 /* This file is part of the KDE project 0002 Copyright (c) 2006 Thorsten Zachmann <zachmann@kde.org> 0003 0004 This library is free software; you can redistribute it and/or 0005 modify it under the terms of the GNU Library General Public 0006 License as published by the Free Software Foundation; either 0007 version 2 of the License, or (at your option) any later version. 0008 0009 This library is distributed in the hope that it will be useful, 0010 but WITHOUT ANY WARRANTY; without even the implied warranty of 0011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0012 Library General Public License for more details. 0013 0014 You should have received a copy of the GNU Library General Public License 0015 along with this library; see the file COPYING.LIB. If not, write to 0016 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0017 Boston, MA 02110-1301, USA. 0018 0019 Based on code from Wolfgang Baer - WBaer@gmx.de 0020 */ 0021 0022 #ifndef KORTREE_H 0023 #define KORTREE_H 0024 0025 #include <QPair> 0026 #include <QMap> 0027 #include <QList> 0028 #include <QVector> 0029 #include <QPointF> 0030 #include <QRectF> 0031 #include <QVarLengthArray> 0032 0033 #include <QDebug> 0034 0035 // #define CALLIGRA_RTREE_DEBUG 0036 #ifdef CALLIGRA_RTREE_DEBUG 0037 #include <QPainter> 0038 #endif 0039 0040 /** 0041 * @brief The KoRTree class is a template class that provides a R-tree. 0042 * 0043 * This class implements a R-tree as described in 0044 * "R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING" by Antonin Guttman 0045 * 0046 * It only supports 2 dimensional bounding boxes which are represented by a QRectF. 0047 * For node splitting the Quadratic-Cost Algorithm is used as described by Guttman. 0048 */ 0049 template <typename T> 0050 class KoRTree 0051 { 0052 public: 0053 /** 0054 * @brief Constructor 0055 * 0056 * @param capacity the capacity a node can take 0057 * @param minimum the minimum filling of a node max 0.5 * capacity 0058 */ 0059 KoRTree(int capacity, int minimum); 0060 0061 /** 0062 * @brief Destructor 0063 */ 0064 virtual ~KoRTree(); 0065 0066 /** 0067 * @brief Insert data item into the tree 0068 * 0069 * This will insert a data item into the tree. If necessary the tree will 0070 * adjust itself. 0071 * 0072 * @param data 0073 * @param bb 0074 */ 0075 virtual void insert(const QRectF& bb, const T& data); 0076 0077 /** 0078 * @brief Remove a data item from the tree 0079 * 0080 * This removed a data item from the tree. If necessary the tree will 0081 * adjust itself. 0082 * 0083 * @param data 0084 */ 0085 void remove(const T& data); 0086 0087 /** 0088 * @brief Find all data items which intersects rect 0089 * The items are sorted by insertion time in ascending order. 0090 * 0091 * @param rect where the objects have to be in 0092 * 0093 * @return objects intersecting the rect 0094 */ 0095 virtual QList<T> intersects(const QRectF& rect) const; 0096 0097 /** 0098 * @brief Find all data item which contain the point 0099 * The items are sorted by insertion time in ascending order. 0100 * 0101 * @param point which should be contained in the objects 0102 * 0103 * @return objects which contain the point 0104 */ 0105 QList<T> contains(const QPointF &point) const; 0106 0107 /** 0108 * @brief Find all data rectangles 0109 * The order is NOT guaranteed to be the same as that used by values(). 0110 * 0111 * @return a list containing all the data rectangles used in the tree 0112 */ 0113 QList<QRectF> keys() const; 0114 0115 /** 0116 * @brief Find all data items 0117 * The order is NOT guaranteed to be the same as that used by keys(). 0118 * 0119 * @return a list containing all the data used in the tree 0120 */ 0121 QList<T> values() const; 0122 0123 virtual void clear() { 0124 delete m_root; 0125 m_root = createLeafNode(m_capacity + 1, 0, 0); 0126 m_leafMap.clear(); 0127 } 0128 0129 #ifdef CALLIGRA_RTREE_DEBUG 0130 /** 0131 * @brief Paint the tree 0132 * 0133 * @param p painter which should be used for painting 0134 */ 0135 void paint(QPainter & p) const; 0136 0137 /** 0138 * @brief Print the tree using qdebug 0139 */ 0140 void debug() const; 0141 #endif 0142 0143 protected: 0144 class NonLeafNode; 0145 class LeafNode; 0146 0147 class Node 0148 { 0149 public: 0150 #ifdef CALLIGRA_RTREE_DEBUG 0151 static int nodeIdCnt; 0152 #endif 0153 Node(int capacity, int level, Node * parent); 0154 virtual ~Node() {} 0155 0156 virtual void remove(int index); 0157 // move node between nodes of the same type from node 0158 virtual void move(Node * node, int index) = 0; 0159 0160 virtual LeafNode * chooseLeaf(const QRectF& bb) = 0; 0161 virtual NonLeafNode * chooseNode(const QRectF& bb, int level) = 0; 0162 0163 virtual void intersects(const QRectF& rect, QMap<int, T> & result) const = 0; 0164 virtual void contains(const QPointF & point, QMap<int, T> & result) const = 0; 0165 0166 virtual void keys(QList<QRectF> & result) const = 0; 0167 virtual void values(QMap<int, T> & result) const = 0; 0168 0169 virtual Node * parent() const { 0170 return m_parent; 0171 } 0172 virtual void setParent(Node * parent) { 0173 m_parent = parent; 0174 } 0175 0176 virtual int childCount() const { 0177 return m_counter; 0178 } 0179 0180 virtual const QRectF& boundingBox() const { 0181 return m_boundingBox; 0182 } 0183 virtual void updateBoundingBox(); 0184 0185 virtual const QRectF& childBoundingBox(int index) const { 0186 return m_childBoundingBox[index]; 0187 } 0188 virtual void setChildBoundingBox(int index, const QRectF& rect) { 0189 m_childBoundingBox[index] = rect; 0190 } 0191 0192 virtual void clear(); 0193 virtual bool isRoot() const { 0194 return m_parent == 0; 0195 } 0196 virtual bool isLeaf() const { 0197 return false; 0198 } 0199 0200 virtual int place() const { 0201 return m_place; 0202 } 0203 virtual void setPlace(int place) { 0204 m_place = place; 0205 } 0206 0207 virtual int level() const { 0208 return m_level; 0209 } 0210 virtual void setLevel(int level) { 0211 m_level = level; 0212 } 0213 0214 #ifdef CALLIGRA_RTREE_DEBUG 0215 virtual int nodeId() const { 0216 return m_nodeId; 0217 } 0218 0219 virtual void paint(QPainter & p, int level) const = 0; 0220 virtual void debug(QString line) const = 0; 0221 0222 protected: 0223 #define levelColorSize 5 0224 static QColor levelColor[levelColorSize]; 0225 virtual void paintRect(QPainter & p, int level) const; 0226 #endif 0227 protected: 0228 Node * m_parent; 0229 QRectF m_boundingBox; 0230 QVector<QRectF> m_childBoundingBox; 0231 int m_counter; 0232 // the position in the parent 0233 int m_place; 0234 #ifdef CALLIGRA_RTREE_DEBUG 0235 int m_nodeId; 0236 #endif 0237 int m_level; 0238 }; 0239 0240 class NonLeafNode : virtual public Node 0241 { 0242 public: 0243 NonLeafNode(int capacity, int level, Node * parent); 0244 ~NonLeafNode() override; 0245 0246 virtual void insert(const QRectF& bb, Node * data); 0247 void remove(int index) override; 0248 void move(Node * node, int index) override; 0249 0250 LeafNode * chooseLeaf(const QRectF& bb) override; 0251 NonLeafNode * chooseNode(const QRectF& bb, int level) override; 0252 0253 void intersects(const QRectF& rect, QMap<int, T> & result) const override; 0254 void contains(const QPointF & point, QMap<int, T> & result) const override; 0255 0256 void keys(QList<QRectF> & result) const override; 0257 void values(QMap<int, T> & result) const override; 0258 0259 virtual Node * getNode(int index) const; 0260 0261 #ifdef CALLIGRA_RTREE_DEBUG 0262 void paint(QPainter & p, int level) const override; 0263 void debug(QString line) const override; 0264 #endif 0265 protected: 0266 virtual Node * getLeastEnlargement(const QRectF& bb) const; 0267 0268 QVector<Node *> m_childs; 0269 }; 0270 0271 class LeafNode : virtual public Node 0272 { 0273 public: 0274 static int dataIdCounter; 0275 0276 LeafNode(int capacity, int level, Node * parent); 0277 ~LeafNode() override; 0278 0279 virtual void insert(const QRectF& bb, const T& data, int id); 0280 void remove(int index) override; 0281 virtual void remove(const T& data); 0282 void move(Node * node, int index) override; 0283 0284 LeafNode * chooseLeaf(const QRectF& bb) override; 0285 NonLeafNode * chooseNode(const QRectF& bb, int level) override; 0286 0287 void intersects(const QRectF& rect, QMap<int, T> & result) const override; 0288 void contains(const QPointF & point, QMap<int, T> & result) const override; 0289 0290 void keys(QList<QRectF> & result) const override; 0291 void values(QMap<int, T> & result) const override; 0292 0293 virtual const T& getData(int index) const; 0294 virtual int getDataId(int index) const; 0295 0296 bool isLeaf() const override { 0297 return true; 0298 } 0299 0300 #ifdef CALLIGRA_RTREE_DEBUG 0301 void debug(QString line) const override; 0302 void paint(QPainter & p, int level) const override; 0303 #endif 0304 protected: 0305 QVector<T> m_data; 0306 QVector<int> m_dataIds; 0307 }; 0308 0309 // factory methods 0310 virtual LeafNode* createLeafNode(int capacity, int level, Node * parent) { 0311 return new LeafNode(capacity, level, parent); 0312 } 0313 virtual NonLeafNode* createNonLeafNode(int capacity, int level, Node * parent) { 0314 return new NonLeafNode(capacity, level, parent); 0315 } 0316 0317 // methods for insert 0318 QPair<Node *, Node *> splitNode(Node * node); 0319 QPair<int, int> pickSeeds(Node * node); 0320 QPair<int, int> pickNext(Node * node, QVector<bool> & marker, Node * group1, Node * group2); 0321 virtual void adjustTree(Node * node1, Node * node2); 0322 void insertHelper(const QRectF& bb, const T& data, int id); 0323 0324 // methods for delete 0325 void insert(Node * node); 0326 virtual void condenseTree(Node * node, QVector<Node *> & reinsert); 0327 0328 int m_capacity; 0329 int m_minimum; 0330 Node * m_root; 0331 QMap<T, LeafNode *> m_leafMap; 0332 }; 0333 0334 template <typename T> 0335 KoRTree<T>::KoRTree(int capacity, int minimum) 0336 : m_capacity(capacity) 0337 , m_minimum(minimum) 0338 , m_root(createLeafNode(m_capacity + 1, 0, 0)) 0339 { 0340 if (minimum > capacity / 2) 0341 qFatal("KoRTree::KoRTree minimum can be maximal capacity/2"); 0342 //qDebug() << "root node " << m_root->nodeId(); 0343 } 0344 0345 template <typename T> 0346 KoRTree<T>::~KoRTree() 0347 { 0348 delete m_root; 0349 } 0350 0351 template <typename T> 0352 void KoRTree<T>::insert(const QRectF& bb, const T& data) 0353 { 0354 insertHelper(bb, data, LeafNode::dataIdCounter++); 0355 } 0356 0357 template <typename T> 0358 void KoRTree<T>::insertHelper(const QRectF& bb, const T& data, int id) 0359 { 0360 QRectF nbb(bb.normalized()); 0361 // This has to be done as it is not possible to use QRectF::united() with a isNull() 0362 if (nbb.isNull()) { 0363 nbb.setWidth(0.0001); 0364 nbb.setHeight(0.0001); 0365 qWarning() << "KoRTree::insert boundingBox isNull setting size to" << nbb.size(); 0366 } 0367 else { 0368 // This has to be done as QRectF::intersects() return false if the rect does not have any area overlapping. 0369 // If there is no width or height there is no area and therefore no overlapping. 0370 if ( nbb.width() == 0 ) { 0371 nbb.setWidth(0.0001); 0372 } 0373 if ( nbb.height() == 0 ) { 0374 nbb.setHeight(0.0001); 0375 } 0376 } 0377 0378 LeafNode * leaf = m_root->chooseLeaf(nbb); 0379 //qDebug() << " leaf" << leaf->nodeId() << nbb; 0380 0381 if (leaf->childCount() < m_capacity) { 0382 leaf->insert(nbb, data, id); 0383 m_leafMap[data] = leaf; 0384 adjustTree(leaf, 0); 0385 } else { 0386 leaf->insert(nbb, data, id); 0387 m_leafMap[data] = leaf; 0388 QPair<Node *, Node *> newNodes = splitNode(leaf); 0389 LeafNode * l = dynamic_cast<LeafNode *>(newNodes.first); 0390 if (l) 0391 for (int i = 0; i < l->childCount(); ++i) 0392 m_leafMap[l->getData(i)] = l; 0393 l = dynamic_cast<LeafNode *>(newNodes.second); 0394 if (l) 0395 for (int i = 0; i < l->childCount(); ++i) 0396 m_leafMap[l->getData(i)] = l; 0397 0398 adjustTree(newNodes.first, newNodes.second); 0399 } 0400 } 0401 0402 template <typename T> 0403 void KoRTree<T>::insert(Node * node) 0404 { 0405 if (node->level() == m_root->level()) { 0406 adjustTree(m_root, node); 0407 } else { 0408 QRectF bb(node->boundingBox()); 0409 NonLeafNode * newParent = m_root->chooseNode(bb, node->level() + 1); 0410 0411 newParent->insert(bb, node); 0412 0413 QPair<Node *, Node *> newNodes(node, 0); 0414 if (newParent->childCount() > m_capacity) { 0415 newNodes = splitNode(newParent); 0416 } 0417 adjustTree(newNodes.first, newNodes.second); 0418 } 0419 } 0420 0421 template <typename T> 0422 void KoRTree<T>::remove(const T&data) 0423 { 0424 //qDebug() << "KoRTree remove"; 0425 LeafNode * leaf = m_leafMap[data]; 0426 if (leaf == 0) { 0427 qWarning() << "KoRTree<T>::remove( const T&data) data not found"; 0428 return; 0429 } 0430 m_leafMap.remove(data); 0431 leaf->remove(data); 0432 0433 QVector<Node *> reinsert; 0434 condenseTree(leaf, reinsert); 0435 0436 for (int i = 0; i < reinsert.size(); ++i) { 0437 if (reinsert[i]->isLeaf()) { 0438 LeafNode * leaf = dynamic_cast<LeafNode *>(reinsert[i]); 0439 for (int j = 0; j < leaf->childCount(); ++j) { 0440 insertHelper(leaf->childBoundingBox(j), leaf->getData(j), leaf->getDataId(j)); 0441 } 0442 // clear is needed as the data items are not removed when insert into a new node 0443 leaf->clear(); 0444 delete leaf; 0445 } else { 0446 NonLeafNode * node = dynamic_cast<NonLeafNode *>(reinsert[i]); 0447 for (int j = 0; j < node->childCount(); ++j) { 0448 insert(node->getNode(j)); 0449 } 0450 // clear is needed as the data items are not removed when insert into a new node 0451 node->clear(); 0452 delete node; 0453 } 0454 } 0455 } 0456 0457 template <typename T> 0458 QList<T> KoRTree<T>::intersects(const QRectF& rect) const 0459 { 0460 QMap<int, T> found; 0461 m_root->intersects(rect, found); 0462 return found.values(); 0463 } 0464 0465 template <typename T> 0466 QList<T> KoRTree<T>::contains(const QPointF &point) const 0467 { 0468 QMap<int, T> found; 0469 m_root->contains(point, found); 0470 return found.values(); 0471 } 0472 0473 template <typename T> 0474 QList<QRectF> KoRTree<T>::keys() const 0475 { 0476 QList<QRectF> found; 0477 m_root->keys(found); 0478 return found; 0479 } 0480 0481 template <typename T> 0482 QList<T> KoRTree<T>::values() const 0483 { 0484 QMap<int, T> found; 0485 m_root->values(found); 0486 return found.values(); 0487 } 0488 0489 #ifdef CALLIGRA_RTREE_DEBUG 0490 template <typename T> 0491 void KoRTree<T>::paint(QPainter & p) const 0492 { 0493 if (m_root) { 0494 m_root->paint(p, 0); 0495 } 0496 } 0497 0498 template <typename T> 0499 void KoRTree<T>::debug() const 0500 { 0501 QString prefix(""); 0502 m_root->debug(prefix); 0503 } 0504 #endif 0505 0506 template <typename T> 0507 QPair< typename KoRTree<T>::Node*, typename KoRTree<T>::Node* > KoRTree<T>::splitNode(typename KoRTree<T>::Node* node) 0508 { 0509 //qDebug() << "KoRTree::splitNode" << node; 0510 Node * n1; 0511 Node * n2; 0512 if (node->isLeaf()) { 0513 n1 = createLeafNode(m_capacity + 1, node->level(), node->parent()); 0514 n2 = createLeafNode(m_capacity + 1, node->level(), node->parent()); 0515 } else { 0516 n1 = createNonLeafNode(m_capacity + 1, node->level(), node->parent()); 0517 n2 = createNonLeafNode(m_capacity + 1, node->level(), node->parent()); 0518 } 0519 //qDebug() << " n1" << n1 << n1->nodeId(); 0520 //qDebug() << " n2" << n2 << n2->nodeId(); 0521 0522 QVector<bool> marker(m_capacity + 1); 0523 0524 QPair<int, int> seeds(pickSeeds(node)); 0525 0526 n1->move(node, seeds.first); 0527 n2->move(node, seeds.second); 0528 0529 marker[seeds.first] = true; 0530 marker[seeds.second] = true; 0531 0532 // There is one more in a node to split than the capacity and as we 0533 // already put the seeds in the new nodes subtract them. 0534 int remaining = m_capacity + 1 - 2; 0535 0536 while (remaining > 0) { 0537 if (m_minimum - n1->childCount() == remaining) { 0538 for (int i = 0; i < m_capacity + 1; ++i) { 0539 if (!marker[i]) { 0540 n1->move(node, i); 0541 --remaining; 0542 } 0543 } 0544 } else if (m_minimum - n2->childCount() == remaining) { 0545 for (int i = 0; i < m_capacity + 1; ++i) { 0546 if (!marker[i]) { 0547 n2->move(node, i); 0548 --remaining; 0549 } 0550 } 0551 } else { 0552 QPair<int, int> next(pickNext(node, marker, n1, n2)); 0553 0554 if (next.first == 0) { 0555 n1->move(node, next.second); 0556 } else { 0557 n2->move(node, next.second); 0558 } 0559 --remaining; 0560 } 0561 } 0562 Q_ASSERT(n1->childCount() + n2->childCount() == node->childCount()); 0563 0564 // move the data back to the old node 0565 // this has to be done as the current node is already in the tree. 0566 node->clear(); 0567 for (int i = 0; i < n1->childCount(); ++i) { 0568 node->move(n1, i); 0569 } 0570 0571 //qDebug() << " delete n1" << n1 << n1->nodeId(); 0572 // clear is needed as the data items are not removed 0573 n1->clear(); 0574 delete n1; 0575 return qMakePair(node, n2); 0576 } 0577 0578 template <typename T> 0579 QPair<int, int> KoRTree<T>::pickSeeds(Node *node) 0580 { 0581 int s1 = 0; 0582 int s2 = 1; 0583 qreal max = 0; 0584 for (int i = 0; i < m_capacity + 1; ++i) { 0585 for (int j = i+1; j < m_capacity + 1; ++j) { 0586 if (i != j) { 0587 QRectF bb1(node->childBoundingBox(i)); 0588 QRectF bb2(node->childBoundingBox(j)); 0589 QRectF comp(node->childBoundingBox(i).united(node->childBoundingBox(j))); 0590 qreal area = comp.width() * comp.height() - bb1.width() * bb1.height() - bb2.width() * bb2.height(); 0591 //qDebug() << " ps" << i << j << area; 0592 if (area > max) { 0593 max = area; 0594 s1 = i; 0595 s2 = j; 0596 } 0597 } 0598 } 0599 } 0600 return qMakePair(s1, s2); 0601 } 0602 0603 template <typename T> 0604 QPair<int, int> KoRTree<T>::pickNext(Node * node, QVector<bool> & marker, Node * group1, Node * group2) 0605 { 0606 //qDebug() << "KoRTree::pickNext" << marker; 0607 qreal max = -1.0; 0608 int select = 0; 0609 int group = 0; 0610 for (int i = 0; i < m_capacity + 1; ++i) { 0611 if (marker[i] == false) { 0612 QRectF bb1 = group1->boundingBox().united(node->childBoundingBox(i)); 0613 QRectF bb2 = group2->boundingBox().united(node->childBoundingBox(i)); 0614 qreal d1 = bb1.width() * bb1.height() - group1->boundingBox().width() * group1->boundingBox().height(); 0615 qreal d2 = bb2.width() * bb2.height() - group2->boundingBox().width() * group2->boundingBox().height(); 0616 qreal diff = qAbs(d1 - d2); 0617 //qDebug() << " diff" << diff << i << d1 << d2; 0618 if (diff > max) { 0619 max = diff; 0620 select = i; 0621 //qDebug() << " i =" << i; 0622 if (qAbs(d1) > qAbs(d2)) { 0623 group = 1; 0624 } else { 0625 group = 0; 0626 } 0627 //qDebug() << " group =" << group; 0628 } 0629 } 0630 } 0631 marker[select] = true; 0632 return qMakePair(group, select); 0633 } 0634 0635 template <typename T> 0636 void KoRTree<T>::adjustTree(Node *node1, Node *node2) 0637 { 0638 //qDebug() << "KoRTree::adjustTree"; 0639 if (node1->isRoot()) { 0640 //qDebug() << " root"; 0641 if (node2) { 0642 NonLeafNode * newRoot = createNonLeafNode(m_capacity + 1, node1->level() + 1, 0); 0643 newRoot->insert(node1->boundingBox(), node1); 0644 newRoot->insert(node2->boundingBox(), node2); 0645 m_root = newRoot; 0646 //qDebug() << "new root" << m_root->nodeId(); 0647 } 0648 } else { 0649 NonLeafNode * parent = dynamic_cast<NonLeafNode *>(node1->parent()); 0650 if (!parent) { 0651 qFatal("KoRTree::adjustTree: no parent node found!"); 0652 return; 0653 } 0654 //QRectF pbbold( parent->boundingBox() ); 0655 parent->setChildBoundingBox(node1->place(), node1->boundingBox()); 0656 parent->updateBoundingBox(); 0657 //qDebug() << " bb1 =" << node1->boundingBox() << node1->place() << pbbold << "->" << parent->boundingBox() << parent->nodeId(); 0658 0659 if (!node2) { 0660 //qDebug() << " update"; 0661 adjustTree(parent, 0); 0662 } else { 0663 if (parent->childCount() < m_capacity) { 0664 //qDebug() << " no split needed"; 0665 parent->insert(node2->boundingBox(), node2); 0666 adjustTree(parent, 0); 0667 } else { 0668 //qDebug() << " split again"; 0669 parent->insert(node2->boundingBox(), node2); 0670 QPair<Node *, Node *> newNodes = splitNode(parent); 0671 adjustTree(newNodes.first, newNodes.second); 0672 } 0673 } 0674 } 0675 } 0676 0677 template <typename T> 0678 void KoRTree<T>::condenseTree(Node *node, QVector<Node*> & reinsert) 0679 { 0680 //qDebug() << "KoRTree::condenseTree begin reinsert.size()" << reinsert.size(); 0681 if (!node->isRoot()) { 0682 Node * parent = node->parent(); 0683 //qDebug() << " !node->isRoot us" << node->childCount(); 0684 0685 if (node->childCount() < m_minimum) { 0686 //qDebug() << " remove node"; 0687 parent->remove(node->place()); 0688 reinsert.push_back(node); 0689 } else { 0690 //qDebug() << " update BB parent is root" << parent->isRoot(); 0691 parent->setChildBoundingBox(node->place(), node->boundingBox()); 0692 parent->updateBoundingBox(); 0693 } 0694 condenseTree(parent, reinsert); 0695 } else { 0696 //qDebug() << " node->isRoot us" << node->childCount(); 0697 if (node->childCount() == 1 && !node->isLeaf()) { 0698 //qDebug() << " usedSpace = 1"; 0699 NonLeafNode * n = dynamic_cast<NonLeafNode *>(node); 0700 if (n) { 0701 Node * kid = n->getNode(0); 0702 // clear is needed as the data items are not removed 0703 m_root->clear(); 0704 delete m_root; 0705 m_root = kid; 0706 m_root->setParent(0); 0707 //qDebug() << " new root" << m_root; 0708 } else { 0709 qFatal("KoRTree::condenseTree cast to NonLeafNode failed"); 0710 } 0711 } 0712 } 0713 //qDebug() << "KoRTree::condenseTree end reinsert.size()" << reinsert.size(); 0714 } 0715 0716 #ifdef CALLIGRA_RTREE_DEBUG 0717 template <typename T> 0718 QColor KoRTree<T>::Node::levelColor[] = { 0719 QColor(Qt::green), 0720 QColor(Qt::red), 0721 QColor(Qt::cyan), 0722 QColor(Qt::magenta), 0723 QColor(Qt::yellow), 0724 }; 0725 0726 template <class T> 0727 int KoRTree<T>::Node::nodeIdCnt = 0; 0728 #endif 0729 0730 template <typename T> 0731 KoRTree<T>::Node::Node(int capacity, int level, Node * parent) 0732 : m_parent(parent) 0733 , m_childBoundingBox(capacity) 0734 , m_counter(0) 0735 #ifdef CALLIGRA_RTREE_DEBUG 0736 , m_nodeId(nodeIdCnt++) 0737 #endif 0738 , m_level(level) 0739 { 0740 } 0741 0742 template <typename T> 0743 void KoRTree<T>::Node::remove(int index) 0744 { 0745 for (int i = index + 1; i < m_counter; ++i) { 0746 m_childBoundingBox[i-1] = m_childBoundingBox[i]; 0747 } 0748 --m_counter; 0749 updateBoundingBox(); 0750 } 0751 0752 template <typename T> 0753 void KoRTree<T>::Node::updateBoundingBox() 0754 { 0755 m_boundingBox = QRectF(); 0756 for (int i = 0; i < m_counter; ++i) { 0757 m_boundingBox = m_boundingBox.united(m_childBoundingBox[i]); 0758 } 0759 } 0760 0761 template <typename T> 0762 void KoRTree<T>::Node::clear() 0763 { 0764 m_counter = 0; 0765 m_boundingBox = QRectF(); 0766 } 0767 0768 #ifdef CALLIGRA_RTREE_DEBUG 0769 template <typename T> 0770 void KoRTree<T>::Node::paintRect(QPainter & p, int level) const 0771 { 0772 QColor c(Qt::black); 0773 if (level < levelColorSize) { 0774 c = levelColor[level]; 0775 } 0776 0777 QPen pen(c, 0); 0778 p.setPen(pen); 0779 0780 QRectF bbdraw(this->m_boundingBox); 0781 bbdraw.adjust(level * 2, level * 2, -level * 2, -level * 2); 0782 p.drawRect(bbdraw); 0783 } 0784 #endif 0785 0786 template <typename T> 0787 KoRTree<T>::NonLeafNode::NonLeafNode(int capacity, int level, Node * parent) 0788 : Node(capacity, level, parent) 0789 , m_childs(capacity) 0790 { 0791 //qDebug() << "NonLeafNode::NonLeafNode()" << this; 0792 } 0793 0794 template <typename T> 0795 KoRTree<T>::NonLeafNode::~NonLeafNode() 0796 { 0797 //qDebug() << "NonLeafNode::~NonLeafNode()" << this; 0798 for (int i = 0; i < this->m_counter; ++i) { 0799 delete m_childs[i]; 0800 } 0801 } 0802 0803 template <typename T> 0804 void KoRTree<T>::NonLeafNode::insert(const QRectF& bb, Node * data) 0805 { 0806 m_childs[this->m_counter] = data; 0807 data->setPlace(this->m_counter); 0808 data->setParent(this); 0809 this->m_childBoundingBox[this->m_counter] = bb; 0810 this->m_boundingBox = this->m_boundingBox.united(bb); 0811 //qDebug() << "NonLeafNode::insert" << this->nodeId() << data->nodeId(); 0812 ++this->m_counter; 0813 } 0814 0815 template <typename T> 0816 void KoRTree<T>::NonLeafNode::remove(int index) 0817 { 0818 for (int i = index + 1; i < this->m_counter; ++i) { 0819 m_childs[i-1] = m_childs[i]; 0820 m_childs[i-1]->setPlace(i - 1); 0821 } 0822 Node::remove(index); 0823 } 0824 0825 template <typename T> 0826 void KoRTree<T>::NonLeafNode::move(Node * node, int index) 0827 { 0828 //qDebug() << "NonLeafNode::move" << this << node << index << node->nodeId() << "->" << this->nodeId(); 0829 NonLeafNode * n = dynamic_cast<NonLeafNode *>(node); 0830 if (n) { 0831 QRectF bb = n->childBoundingBox(index); 0832 insert(bb, n->getNode(index)); 0833 } 0834 } 0835 0836 template <typename T> 0837 typename KoRTree<T>::LeafNode * KoRTree<T>::NonLeafNode::chooseLeaf(const QRectF& bb) 0838 { 0839 return getLeastEnlargement(bb)->chooseLeaf(bb); 0840 } 0841 0842 template <typename T> 0843 typename KoRTree<T>::NonLeafNode * KoRTree<T>::NonLeafNode::chooseNode(const QRectF& bb, int level) 0844 { 0845 if (this->m_level > level) { 0846 return getLeastEnlargement(bb)->chooseNode(bb, level); 0847 } else { 0848 return this; 0849 } 0850 0851 } 0852 0853 template <typename T> 0854 void KoRTree<T>::NonLeafNode::intersects(const QRectF& rect, QMap<int, T> & result) const 0855 { 0856 for (int i = 0; i < this->m_counter; ++i) { 0857 if (this->m_childBoundingBox[i].intersects(rect)) { 0858 m_childs[i]->intersects(rect, result); 0859 } 0860 } 0861 } 0862 0863 template <typename T> 0864 void KoRTree<T>::NonLeafNode::contains(const QPointF & point, QMap<int, T> & result) const 0865 { 0866 for (int i = 0; i < this->m_counter; ++i) { 0867 if (this->m_childBoundingBox[i].contains(point)) { 0868 m_childs[i]->contains(point, result); 0869 } 0870 } 0871 } 0872 0873 template <typename T> 0874 void KoRTree<T>::NonLeafNode::keys(QList<QRectF> & result) const 0875 { 0876 for (int i = 0; i < this->m_counter; ++i) { 0877 m_childs[i]->keys(result); 0878 } 0879 } 0880 0881 template <typename T> 0882 void KoRTree<T>::NonLeafNode::values(QMap<int, T> & result) const 0883 { 0884 for (int i = 0; i < this->m_counter; ++i) { 0885 m_childs[i]->values(result); 0886 } 0887 } 0888 0889 template <typename T> 0890 typename KoRTree<T>::Node * KoRTree<T>::NonLeafNode::getNode(int index) const 0891 { 0892 return m_childs[index]; 0893 } 0894 0895 template <typename T> 0896 typename KoRTree<T>::Node * KoRTree<T>::NonLeafNode::getLeastEnlargement(const QRectF& bb) const 0897 { 0898 //qDebug() << "NonLeafNode::getLeastEnlargement"; 0899 QVarLengthArray<qreal> area(this->m_counter); 0900 for (int i = 0; i < this->m_counter; ++i) { 0901 QSizeF big(this->m_childBoundingBox[i].united(bb).size()); 0902 area[i] = big.width() * big.height() - this->m_childBoundingBox[i].width() * this->m_childBoundingBox[i].height(); 0903 } 0904 0905 int minIndex = 0; 0906 qreal minArea = area[minIndex]; 0907 //qDebug() << " min" << minIndex << minArea; 0908 0909 for (int i = 1; i < this->m_counter; ++i) { 0910 if (area[i] < minArea) { 0911 minIndex = i; 0912 minArea = area[i]; 0913 //qDebug() << " min" << minIndex << minArea; 0914 } 0915 } 0916 0917 return m_childs[minIndex]; 0918 } 0919 0920 #ifdef CALLIGRA_RTREE_DEBUG 0921 template <typename T> 0922 void KoRTree<T>::NonLeafNode::debug(QString line) const 0923 { 0924 for (int i = 0; i < this->m_counter; ++i) { 0925 qDebug("%s %d %d", qPrintable(line), this->nodeId(), i); 0926 m_childs[i]->debug(line + " "); 0927 } 0928 } 0929 0930 template <typename T> 0931 void KoRTree<T>::NonLeafNode::paint(QPainter & p, int level) const 0932 { 0933 this->paintRect(p, level); 0934 for (int i = 0; i < this->m_counter; ++i) { 0935 m_childs[i]->paint(p, level + 1); 0936 } 0937 0938 } 0939 #endif 0940 0941 template <class T> 0942 int KoRTree<T>::LeafNode::dataIdCounter = 0; 0943 0944 template <typename T> 0945 KoRTree<T>::LeafNode::LeafNode(int capacity, int level, Node * parent) 0946 : Node(capacity, level, parent) 0947 , m_data(capacity) 0948 , m_dataIds(capacity) 0949 { 0950 //qDebug() << "LeafNode::LeafNode" << this; 0951 } 0952 0953 template <typename T> 0954 KoRTree<T>::LeafNode::~LeafNode() 0955 { 0956 //qDebug() << "LeafNode::~LeafNode" << this; 0957 } 0958 0959 template <typename T> 0960 void KoRTree<T>::LeafNode::insert(const QRectF& bb, const T& data, int id) 0961 { 0962 m_data[this->m_counter] = data; 0963 m_dataIds[this->m_counter] = id; 0964 this->m_childBoundingBox[this->m_counter] = bb; 0965 this->m_boundingBox = this->m_boundingBox.united(bb); 0966 ++this->m_counter; 0967 } 0968 0969 template <typename T> 0970 void KoRTree<T>::LeafNode::remove(int index) 0971 { 0972 for (int i = index + 1; i < this->m_counter; ++i) { 0973 m_data[i-1] = m_data[i]; 0974 m_dataIds[i-1] = m_dataIds[i]; 0975 } 0976 Node::remove(index); 0977 } 0978 0979 template <typename T> 0980 void KoRTree<T>::LeafNode::remove(const T& data) 0981 { 0982 int old_counter = this->m_counter; 0983 for (int i = 0; i < this->m_counter; ++i) { 0984 if (m_data[i] == data) { 0985 //qDebug() << "LeafNode::remove id" << i; 0986 remove(i); 0987 break; 0988 } 0989 } 0990 if (old_counter == this->m_counter) { 0991 qWarning() << "LeafNode::remove( const T&data) data not found"; 0992 } 0993 } 0994 0995 template <typename T> 0996 void KoRTree<T>::LeafNode::move(Node * node, int index) 0997 { 0998 LeafNode * n = dynamic_cast<LeafNode*>(node); 0999 if (n) { 1000 //qDebug() << "LeafNode::move" << this << node << index 1001 // << node->nodeId() << "->" << this->nodeId() << n->childBoundingBox( index ); 1002 QRectF bb = n->childBoundingBox(index); 1003 insert(bb, n->getData(index), n->getDataId(index)); 1004 } 1005 } 1006 1007 template <typename T> 1008 typename KoRTree<T>::LeafNode * KoRTree<T>::LeafNode::chooseLeaf(const QRectF& bb) 1009 { 1010 Q_UNUSED(bb); 1011 return this; 1012 } 1013 1014 template <typename T> 1015 typename KoRTree<T>::NonLeafNode * KoRTree<T>::LeafNode::chooseNode(const QRectF& bb, int level) 1016 { 1017 Q_UNUSED(bb); 1018 Q_UNUSED(level); 1019 qFatal("LeafNode::chooseNode called. This should not happen!"); 1020 return 0; 1021 } 1022 1023 template <typename T> 1024 void KoRTree<T>::LeafNode::intersects(const QRectF& rect, QMap<int, T> & result) const 1025 { 1026 for (int i = 0; i < this->m_counter; ++i) { 1027 if (this->m_childBoundingBox[i].intersects(rect)) { 1028 result.insert(m_dataIds[i], m_data[i]); 1029 } 1030 } 1031 } 1032 1033 template <typename T> 1034 void KoRTree<T>::LeafNode::contains(const QPointF & point, QMap<int, T> & result) const 1035 { 1036 for (int i = 0; i < this->m_counter; ++i) { 1037 if (this->m_childBoundingBox[i].contains(point)) { 1038 result.insert(m_dataIds[i], m_data[i]); 1039 } 1040 } 1041 } 1042 1043 template <typename T> 1044 void KoRTree<T>::LeafNode::keys(QList<QRectF> & result) const 1045 { 1046 for (int i = 0; i < this->m_counter; ++i) { 1047 result.push_back(this->m_childBoundingBox[i]); 1048 } 1049 } 1050 1051 template <typename T> 1052 void KoRTree<T>::LeafNode::values(QMap<int, T> & result) const 1053 { 1054 for (int i = 0; i < this->m_counter; ++i) { 1055 result.insert(m_dataIds[i], m_data[i]); 1056 } 1057 } 1058 1059 template <typename T> 1060 const T& KoRTree<T>::LeafNode::getData(int index) const 1061 { 1062 return m_data[ index ]; 1063 } 1064 1065 template <typename T> 1066 int KoRTree<T>::LeafNode::getDataId(int index) const 1067 { 1068 return m_dataIds[ index ]; 1069 } 1070 1071 #ifdef CALLIGRA_RTREE_DEBUG 1072 template <typename T> 1073 void KoRTree<T>::LeafNode::debug(QString line) const 1074 { 1075 for (int i = 0; i < this->m_counter; ++i) { 1076 qDebug("%s %d %d %p", qPrintable(line), this->nodeId(), i, &(m_data[i])); 1077 qDebug() << this->m_childBoundingBox[i].toRect(); 1078 } 1079 } 1080 1081 template <typename T> 1082 void KoRTree<T>::LeafNode::paint(QPainter & p, int level) const 1083 { 1084 if (this->m_counter) { 1085 this->paintRect(p, level); 1086 } 1087 } 1088 #endif 1089 1090 #endif /* KORTREE_H */