summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/location/mapsgl/intervaltree_p.h859
-rw-r--r--src/location/mapsgl/mapitem.cpp248
-rw-r--r--src/location/mapsgl/mapitem.h32
-rw-r--r--src/location/mapsgl/mapsgl.pri1
-rw-r--r--tests/auto/auto.pro2
-rw-r--r--tests/auto/intervaltree/intervaltree.pro8
-rw-r--r--tests/auto/intervaltree/tst_intervaltree.cpp772
-rw-r--r--tests/auto/mapitemtree/mapitemtree.pro7
-rw-r--r--tests/auto/mapitemtree/tst_mapitemtree.cpp628
9 files changed, 2551 insertions, 6 deletions
diff --git a/src/location/mapsgl/intervaltree_p.h b/src/location/mapsgl/intervaltree_p.h
new file mode 100644
index 00000000..6ed897cd
--- /dev/null
+++ b/src/location/mapsgl/intervaltree_p.h
@@ -0,0 +1,859 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtLocation module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+#ifndef INTERVALTREE_P_H
+#define INTERVALTREE_P_H
+
+//
+// W A R N I N G
+// -------------
+//
+// This file is not part of the Qt API. It exists purely as an
+// implementation detail. This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include <QString>
+#include <QRect>
+#include <QPoint>
+
+QT_BEGIN_NAMESPACE
+
+template <class D>
+class AAIntervalTreeNodeOperation;
+
+template <class D>
+class AAIntervalTreeNode
+{
+public:
+ AAIntervalTreeNode();
+ ~AAIntervalTreeNode();
+
+ bool operator == (const AAIntervalTreeNode<D> &other) const;
+ bool operator != (const AAIntervalTreeNode<D> &other) const;
+
+ AAIntervalTreeNode<D> * find(int min, int max);
+
+ AAIntervalTreeNode<D> * insert(int min, int max, D data);
+ AAIntervalTreeNode<D> * remove(int min, int max, D data);
+
+ void visitRange(int x1, int x2, AAIntervalTreeNodeOperation<D> *op);
+
+ D& data();
+
+ QList<D> items() const;
+ QList<D> itemsAt(int x) const;
+ QList<D> itemsWithin(int x1, int x2) const;
+
+ QList<AAIntervalTreeNode<D>*> nodes();
+ QList<AAIntervalTreeNode<D>*> nodesAt(int x);
+ QList<AAIntervalTreeNode<D>*> nodesWithin(int x1, int x2);
+
+ QString print(const QString &indent);
+
+private:
+ AAIntervalTreeNode<D> * skew();
+ AAIntervalTreeNode<D> * split();
+
+ bool nodeLess(int min, int max) const;
+ bool nodeGreater(int min, int max) const;
+
+ int min_;
+ int max_;
+ int maxTree_;
+ D data_;
+
+ int level_;
+ AAIntervalTreeNode<D> * left_;
+ AAIntervalTreeNode<D> * right_;
+};
+
+template <class D>
+class AAIntervalTreeNodeOperation
+{
+public:
+ virtual ~AAIntervalTreeNodeOperation() {}
+ virtual void apply(D data) = 0;
+};
+
+template <class D>
+AAIntervalTreeNode<D>::AAIntervalTreeNode()
+ : min_(-1),
+ max_(-1),
+ maxTree_(-1),
+ level_(0),
+ left_(0),
+ right_(0)
+{
+}
+
+template <class D>
+AAIntervalTreeNode<D>::~AAIntervalTreeNode()
+{
+ if (left_)
+ delete left_;
+ if (right_)
+ delete right_;
+}
+
+template <class D>
+bool AAIntervalTreeNode<D>::operator == (const AAIntervalTreeNode<D> &other) const
+{
+ if (min_ != other.min_)
+ return false;
+
+ if (max_ != other.max_)
+ return false;
+
+ if (data_ != other.data_)
+ return false;
+
+ if ((left_ == 0) != (other.left_ == 0))
+ return false;
+
+ if ((right_ == 0) != (other.right_ == 0))
+ return false;
+
+ if (left_ && !(*left_ == *(other.left_)))
+ return false;
+
+ if (right_ && !(*right_ == *(other.right_)))
+ return false;
+
+ return true;
+}
+
+template <class D>
+bool AAIntervalTreeNode<D>::operator != (const AAIntervalTreeNode<D> &other) const
+{
+ return !(*this == other);
+}
+
+template <class D>
+bool AAIntervalTreeNode<D>::nodeLess(int min, int max) const
+{
+ if (this->min_ < min)
+ return true;
+ if (min < this->min_)
+ return false;
+ return (this->max_ < max);
+}
+
+template <class D>
+bool AAIntervalTreeNode<D>::nodeGreater(int min, int max) const
+{
+ if (min < this->min_)
+ return true;
+ if (this->min_ < min)
+ return false;
+ return (max < this->max_);
+}
+
+template <class D>
+AAIntervalTreeNode<D> * AAIntervalTreeNode<D>::find(int min, int max)
+{
+ if (nodeGreater(min, max)) {
+ if (left_)
+ return left_->find(min, max);
+ return 0;
+ } else if (nodeLess(min, max)) {
+ if (right_)
+ return right_->find(min, max);
+ return 0;
+ } else {
+ return this;
+ }
+}
+
+template <class D>
+void AAIntervalTreeNode<D>::visitRange(int x1, int x2, AAIntervalTreeNodeOperation<D> *op)
+{
+ if (left_ && (x1 <= left_->maxTree_))
+ left_->visitRange(x1, x2, op);
+
+ if ((min_ <= x2) && (x1 <= max_))
+ op->apply(data_);
+
+ if (right_ && (min_ <= x2))
+ right_->visitRange(x1, x2, op);
+}
+
+template <class D>
+AAIntervalTreeNode<D> * AAIntervalTreeNode<D>::insert(int min, int max, D data)
+{
+ if (level_ == 0) {
+ level_ = 1;
+ this->min_ = min;
+ this->max_ = max;
+ this->maxTree_ = max;
+ this->data_ = data;
+ return this;
+ }
+
+ if (nodeGreater(min, max)) {
+ if (!left_)
+ left_ = new AAIntervalTreeNode<D>();
+ left_ = left_->insert(min, max, data);
+ } else if (nodeLess(min, max)) {
+ if (!right_)
+ right_ = new AAIntervalTreeNode<D>();
+ right_ = right_->insert(min, max, data);
+ } else {
+ // TODO handle equal case ie don't silently ignore it
+ }
+
+ AAIntervalTreeNode<D> * result = this->skew()->split();
+
+ int m = result->max_;
+ if (result->left_)
+ m = qMax(m, result->left_->maxTree_);
+ if (result->right_)
+ m = qMax(m, result->right_->maxTree_);
+ result->maxTree_ = m;
+
+ return result;
+}
+
+template <class D>
+AAIntervalTreeNode<D> * AAIntervalTreeNode<D>::remove(int min, int max, D data)
+{
+ if (nodeGreater(min, max)) {
+ if (left_) {
+ AAIntervalTreeNode<D> *newLeft = left_->remove(min, max, data);
+ if (newLeft) {
+ left_ = newLeft;
+ } else {
+ delete left_;
+ left_ = 0;
+ }
+ }
+ } else if (nodeLess(min, max)) {
+ if (right_) {
+ AAIntervalTreeNode<D> *newRight = right_->remove(min, max, data);
+ if (newRight) {
+ right_ = newRight;
+ } else {
+ delete right_;
+ right_ = 0;
+ }
+ }
+ } else {
+ // TODO handle multiple equal cases
+ // - remove particular case
+ // - return unless the list of cases is now empty
+ if (left_) {
+ if (right_) {
+ AAIntervalTreeNode<D> *prev = left_;
+
+ while (prev->right_)
+ prev = prev->right_;
+
+ this->min_ = prev->min_;
+ this->max_ = prev->max_;
+ this->data_ = prev->data_;
+
+ left_ = left_->remove(this->min_, this->max_, this->data_);
+ } else {
+ return left_;
+ }
+ } else {
+ if (right_) {
+ return right_;
+ } else {
+ return 0;
+ }
+ }
+ }
+
+ AAIntervalTreeNode<D> *newRoot = this;
+
+ if ((left_ && (left_->level_ < level_ - 1))
+ || (right_ && (right_->level_ < level_ - 1))) {
+
+ if (right_ && (right_->level_ > --level_))
+ right_->level_ = level_;
+
+ newRoot = newRoot->skew()->split();
+ }
+
+ int m = newRoot->max_;
+ if (newRoot->left_)
+ m = qMax(m, newRoot->left_->maxTree_);
+ if (newRoot->right_)
+ m = qMax(m, newRoot->right_->maxTree_);
+ newRoot->maxTree_ = m;
+
+ return newRoot;
+}
+
+template <class D>
+D& AAIntervalTreeNode<D>::data()
+{
+ return data_;
+}
+
+template <class D>
+QList<D> AAIntervalTreeNode<D>::items() const
+{
+ QList<D> result;
+
+ if (left_)
+ result.append(left_->items());
+ result.append(data_);
+ if (right_)
+ result.append(right_->items());
+
+ return result;
+}
+
+template <class D>
+QList<D> AAIntervalTreeNode<D>::itemsAt(int x) const
+{
+ QList<D> result;
+
+ if (left_ && (x <= left_->maxTree_))
+ result.append(left_->itemsAt(x));
+ if ((min_ <= x) && (x <= max_))
+ result.append(data_);
+ if (right_ && (min_ <= x))
+ result.append(right_->itemsAt(x));
+
+ return result;
+}
+
+template <class D>
+QList<D> AAIntervalTreeNode<D>::itemsWithin(int x1, int x2) const
+{
+ QList<D> result;
+
+ if (left_ && (x1 <= left_->maxTree_))
+ result.append(left_->itemsWithin(x1, x2));
+ if ((min_ <= x2) && (x1 <= max_))
+ result.append(data_);
+ if (right_ && (min_ <= x2))
+ result.append(right_->itemsWithin(x1, x2));
+
+ return result;
+}
+
+template <class D>
+QList<AAIntervalTreeNode<D>*> AAIntervalTreeNode<D>::nodes()
+{
+ QList<AAIntervalTreeNode<D>*> result;
+
+ if (left_)
+ result.append(left_->nodes());
+ result.append(this);
+ if (right_)
+ result.append(right_->nodes());
+
+ return result;
+}
+
+template <class D>
+QList<AAIntervalTreeNode<D>*> AAIntervalTreeNode<D>::nodesAt(int x)
+{
+ QList<AAIntervalTreeNode<D>*> result;
+
+ if (left_ && (x <= left_->maxTree_))
+ result.append(left_->nodesAt(x));
+ if ((min_ <= x) && (x <= max_))
+ result.append(this);
+ if (right_ && (min_ <= x))
+ result.append(right_->nodesAt(x));
+
+ return result;
+}
+
+template <class D>
+QList<AAIntervalTreeNode<D>*> AAIntervalTreeNode<D>::nodesWithin(int x1, int x2)
+{
+ QList<AAIntervalTreeNode<D>*> result;
+
+ if (left_ && (x1 <= left_->maxTree_))
+ result.append(left_->nodesWithin(x1, x2));
+ if ((min_ <= x2) && (x1 <= max_))
+ result.append(this);
+ if (right_ && (min_ <= x2))
+ result.append(right_->nodesWithin(x1, x2));
+
+ return result;
+}
+
+template <class D>
+AAIntervalTreeNode<D> * AAIntervalTreeNode<D>::skew()
+{
+ if (level_ == 0)
+ return this;
+
+ AAIntervalTreeNode<D> *newRoot = this;
+
+ if (left_ && (level_ == left_->level_)) {
+ AAIntervalTreeNode<D> *newRight = this;
+
+ newRoot = left_;
+ newRight->left_ = newRoot->right_;
+ newRoot->right_ = newRight;
+ }
+
+ if (newRoot->right_)
+ newRoot->right_ = newRoot->right_->skew();
+
+ return newRoot;
+}
+
+template <class D>
+AAIntervalTreeNode<D> * AAIntervalTreeNode<D>::split()
+{
+ if (level_ == 0)
+ return this;
+
+ AAIntervalTreeNode<D> *newRoot = this;
+
+ if (right_ && right_->right_ && (level_ == right_->right_->level_)) {
+ AAIntervalTreeNode<D> *newLeft = this;
+
+ newRoot = right_;
+ newLeft->right_ = newRoot->left_;
+ newRoot->left_ = newLeft;
+
+ ++(newRoot->level_);
+
+ if (newRoot->right_)
+ newRoot->right_ = newRoot->right_->split();
+ }
+
+ return newRoot;
+}
+
+template <class D>
+QString AAIntervalTreeNode<D>::print(const QString &indent)
+{
+ QString s;
+ s += indent + "level " + QString::number(level_) + "\n";
+ s += indent + "min " + QString::number(min_) + "\n";
+ s += indent + "max " + QString::number(max_) + "\n";
+ s += indent + "maxTree " + QString::number(maxTree_) + "\n";
+ s += indent + "left\n";
+ if (left_)
+ s += left_->print(indent + " ");
+ s += indent + "right\n";
+ if (right_)
+ s += right_->print(indent + " ");
+ return s;
+}
+
+template <class D>
+class Q_LOCATION_EXPORT AAIntervalTree
+{
+public:
+ AAIntervalTree();
+ ~AAIntervalTree();
+
+ bool operator == (const AAIntervalTree<D> &other) const;
+ bool operator != (const AAIntervalTree<D> &other) const;
+
+ bool isEmpty() const;
+
+ void insert(int min, int max, D data);
+ void remove(int min, int max, D data);
+
+ QList<D> items() const;
+ QList<D> itemsAt(int x) const;
+ QList<D> itemsWithin(int x1, int x2) const;
+
+ QString print();
+
+private:
+ AAIntervalTreeNode<D> * root_;
+};
+
+template <class D>
+AAIntervalTree<D>::AAIntervalTree()
+ : root_(0) {}
+
+template <class D>
+AAIntervalTree<D>::~AAIntervalTree()
+{
+ if (root_)
+ delete root_;
+}
+
+template <class D>
+bool AAIntervalTree<D>::operator == (const AAIntervalTree<D> &other) const
+{
+ if ((root_ == 0) != (other.root_ == 0))
+ return false;
+
+ return (*root_ == *(other.root_));
+}
+
+template <class D>
+bool AAIntervalTree<D>::operator != (const AAIntervalTree<D> &other) const
+{
+ return !(*this == other);
+}
+
+template <class D>
+bool AAIntervalTree<D>::isEmpty() const
+{
+ return (root_ == 0);
+}
+
+template <class D>
+void AAIntervalTree<D>::insert(int min, int max, D data)
+{
+ if (!root_)
+ root_ = new AAIntervalTreeNode<D>();
+ root_ = root_->insert(min, max, data);
+}
+
+template <class D>
+void AAIntervalTree<D>::remove(int min, int max, D data)
+{
+ if (!root_)
+ return;
+
+ AAIntervalTreeNode<D> *newRoot = root_->remove(min, max, data);
+ if (newRoot) {
+ root_ = newRoot;
+ } else {
+ delete root_;
+ root_ = 0;
+ }
+}
+
+template <class D>
+QList<D> AAIntervalTree<D>::items() const
+{
+ QList<D> result;
+
+ if (root_)
+ result = root_->items();
+
+ return result;
+}
+
+template <class D>
+QList<D> AAIntervalTree<D>::itemsAt(int x) const
+{
+ QList<D> result;
+
+ if (root_)
+ result = root_->itemsAt(x);
+
+ return result;
+}
+
+template <class D>
+QList<D> AAIntervalTree<D>::itemsWithin(int x1, int x2) const
+{
+ QList<D> result;
+
+ if (root_)
+ result = root_->itemsWithin(x1, x2);
+
+ return result;
+}
+
+template <class D>
+QString AAIntervalTree<D>::print()
+{
+ QString s;
+
+ if (root_)
+ s = root_->print("");
+
+ return s;
+}
+
+template <class D>
+class Q_LOCATION_EXPORT AAInterval2DTree
+{
+public:
+ AAInterval2DTree();
+ ~AAInterval2DTree();
+
+ bool operator == (const AAInterval2DTree<D> &other) const;
+ bool operator != (const AAInterval2DTree<D> &other) const;
+
+ bool isEmpty() const;
+
+ void insert(const QRect &rect, D data);
+ void remove(const QRect &rect, D data);
+
+ void visitRect(const QRect &rect, AAIntervalTreeNodeOperation<D> *op);
+
+ QList<D> items() const;
+ QList<D> itemsAt(const QPoint &point) const;
+ QList<D> itemsWithin(const QRect &viewport) const;
+
+ QString print();
+
+private:
+ AAIntervalTreeNode<AAIntervalTreeNode<QList<D> >*> * root_;
+};
+
+template <class D>
+class InnerOp : public AAIntervalTreeNodeOperation<AAIntervalTreeNode<QList<D> >*>
+{
+public:
+ InnerOp(const QRect &rect, AAIntervalTreeNodeOperation<D> *op)
+ : rect_(rect), op_(op) {}
+
+ void apply(AAIntervalTreeNode<QList<D> >* data) {
+ if (!data)
+ return;
+ data->visitRange(rect_.y(), rect_.y() + rect_.height(), op_);
+ }
+
+private:
+ QRect rect_;
+ AAIntervalTreeNodeOperation<D> *op_;
+};
+
+template <class D>
+AAInterval2DTree<D>::AAInterval2DTree()
+ : root_(0) {}
+
+template <class D>
+AAInterval2DTree<D>::~AAInterval2DTree()
+{
+ if (root_)
+ delete root_;
+}
+
+template <class D>
+bool AAInterval2DTree<D>::operator == (const AAInterval2DTree<D> &other) const
+{
+ if ((root_ == 0) != (other.root_ == 0))
+ return false;
+
+ return (*root_ == *(other.root_));
+}
+
+template <class D>
+bool AAInterval2DTree<D>::operator != (const AAInterval2DTree<D> &other) const
+{
+ return !(*this == other);
+}
+
+template <class D>
+bool AAInterval2DTree<D>::isEmpty() const
+{
+ return (root_ == 0);
+}
+
+template <class D>
+void AAInterval2DTree<D>::visitRect(const QRect &rect, AAIntervalTreeNodeOperation<D> *op)
+{
+ if (!root_)
+ return;
+
+ AAIntervalTreeNodeOperation<D> *innerOp = new InnerOp<D>(rect, op);
+
+ root_->visitRange(rect.x(), rect.x() + rect.width(), innerOp);
+
+ delete innerOp;
+}
+
+template <class D>
+void AAInterval2DTree<D>::insert(const QRect &rect, D data)
+{
+ if (!root_)
+ root_ = new AAIntervalTreeNode<AAIntervalTreeNode<QList<D> >*>();
+
+ AAIntervalTreeNode<AAIntervalTreeNode<QList<D> >*> *childNode
+ = root_->find(rect.x(), rect.x() + rect.width());
+
+ AAIntervalTreeNode<QList<D> > *child = 0;
+ if (childNode)
+ child = childNode->data();
+
+ if (!child)
+ child = new AAIntervalTreeNode<QList<D> >();
+
+ AAIntervalTreeNode<QList<D> > *grandchildNode
+ = child->find(rect.y(), rect.y() + rect.height());
+
+ QList<D> list;
+
+ if (grandchildNode)
+ list = grandchildNode->data();
+
+ if (!list.contains(data))
+ list.append(data);
+
+ if (grandchildNode)
+ grandchildNode->data() = list;
+ else
+ child = child->insert(rect.y(), rect.y() + rect.height(), list);
+
+ if (childNode)
+ childNode->data() = child;
+ else
+ root_ = root_->insert(rect.x(), rect.x() + rect.width(), child);
+}
+
+template <class D>
+void AAInterval2DTree<D>::remove(const QRect &rect, D data)
+{
+ if (!root_)
+ return;
+
+ AAIntervalTreeNode<AAIntervalTreeNode<QList<D> >*> *childNode
+ = root_->find(rect.x(), rect.x() + rect.width());
+
+ if (!childNode)
+ return;
+
+ AAIntervalTreeNode<QList<D> > *child = childNode->data();
+
+ if (!child)
+ return;
+
+ AAIntervalTreeNode<QList<D> > *grandchildNode
+ = child->find(rect.y(), rect.y() + rect.height());
+
+ if (!grandchildNode)
+ return;
+
+ QList<D> list = grandchildNode->data();
+
+ if (!list.contains(data))
+ return;
+
+ list.removeAll(data);
+
+ grandchildNode->data() = list;
+
+ if (!list.isEmpty())
+ return;
+
+ AAIntervalTreeNode<QList<D> > * newChild = child->remove(rect.y(), rect.y() + rect.height(), list);
+
+ if (newChild) {
+ childNode->data() = newChild;
+ return;
+ }
+
+ AAIntervalTreeNode<AAIntervalTreeNode<QList<D> >*> *newRoot
+ = root_->remove(rect.x(), rect.x() + rect.width(), child);
+
+ delete child;
+
+ if (newRoot) {
+ root_ = newRoot;
+ } else {
+ delete root_;
+ root_ = 0;
+ }
+}
+
+template <class D>
+QList<D> AAInterval2DTree<D>::items() const
+{
+ QList<D> result;
+
+ if (root_) {
+ QList<AAIntervalTreeNode<AAIntervalTreeNode<QList<D> >*>*> tmp1 = root_->nodes();
+ for (int i = 0; i < tmp1.size(); ++i) {
+ QList<AAIntervalTreeNode<QList<D> >*> tmp2 = tmp1.at(i)->data()->nodes();
+ for (int j = 0; j < tmp2.size(); ++j)
+ result.append(tmp2.at(j)->data());
+ }
+ }
+
+ return result;
+}
+
+template <class D>
+QList<D> AAInterval2DTree<D>::itemsAt(const QPoint &point) const
+{
+ QList<D> result;
+
+ if (root_) {
+ QList<AAIntervalTreeNode<AAIntervalTreeNode<QList<D> >*>*> tmp1 = root_->nodesAt(point.x());
+ for (int i = 0; i < tmp1.size(); ++i) {
+ QList<AAIntervalTreeNode<QList<D> >*> tmp2 = tmp1.at(i)->data()->nodesAt(point.y());
+ for (int j = 0; j < tmp2.size(); ++j)
+ result.append(tmp2.at(j)->data());
+ }
+ }
+
+ return result;
+}
+
+template <class D>
+QList<D> AAInterval2DTree<D>::itemsWithin(const QRect &viewport) const
+{
+ QList<D> result;
+
+ if (root_) {
+ QList<AAIntervalTreeNode<AAIntervalTreeNode<QList<D> >*>*> tmp1
+ = root_->nodesWithin(viewport.x(), viewport.x() + viewport.width());
+ for (int i = 0; i < tmp1.size(); ++i) {
+ QList<AAIntervalTreeNode<QList<D> >*> tmp2
+ = tmp1.at(i)->data()->nodesWithin(viewport.y(), viewport.y() + viewport.height());
+ for (int j = 0; j < tmp2.size(); ++j)
+ result.append(tmp2.at(j)->data());
+ }
+ }
+
+ return result;
+}
+
+template <class D>
+QString AAInterval2DTree<D>::print()
+{
+ QString s;
+
+ if (root_)
+ s = root_->print("");
+
+ return s;
+}
+
+QT_END_NAMESPACE
+
+#endif // INTERVALTREE_P_H
+
diff --git a/src/location/mapsgl/mapitem.cpp b/src/location/mapsgl/mapitem.cpp
index 494b0f7c..d561a982 100644
--- a/src/location/mapsgl/mapitem.cpp
+++ b/src/location/mapsgl/mapitem.cpp
@@ -45,12 +45,13 @@
#include <Qt3D/qglmaterial.h>
MapItem::MapItem()
- : zoom_(8.0),
- sceneNode_(0),
- textureId_(0), // invalid value according to specs
- textureDirty_(false),
- texture_(0),
- defaultMaterial_(0)
+ : zoom_(8.0),
+ visible_(true),
+ sceneNode_(0),
+ textureId_(0), // invalid value according to specs
+ textureDirty_(false),
+ texture_(0),
+ defaultMaterial_(0)
{
// TODO optimize the defaultMaterial be common for all
defaultMaterial_ = new QGLMaterial();
@@ -165,3 +166,238 @@ QGLSceneNode* MapItem::sceneNode() const
{
return sceneNode_;
}
+
+// TODO make this into a property and update the item tree when it changes?
+void MapItem::setBounds(const QRect &bounds)
+{
+ bounds_ = bounds;
+}
+
+QRect MapItem::bounds() const
+{
+ return bounds_;
+}
+
+void MapItem::setVisibleFromViewport(bool visible)
+{
+ visible_ = visible;
+}
+
+bool MapItem::visibleFromViewport() const
+{
+ return visible_;
+}
+
+MapItemTree::MapItemTree()
+ : root_(new AAInterval2DTree<MapItem*>()) {}
+
+MapItemTree::~MapItemTree()
+{
+ delete root_;
+}
+
+void MapItemTree::insert(MapItem *item)
+{
+ if (item && item->bounds().isValid())
+ root_->insert(item->bounds(), item);
+}
+
+void MapItemTree::remove(MapItem *item)
+{
+ if (item && item->bounds().isValid())
+ root_->remove(item->bounds(), item);
+}
+
+bool MapItemTree::isEmpty() const
+{
+ return root_->isEmpty();
+}
+
+int MapItemTree::size() const
+{
+ return root_->items().size();
+}
+
+QList<MapItem*> MapItemTree::items() const
+{
+ return root_->items();
+}
+
+QList<MapItem*> MapItemTree::itemsAt(const QPoint &point) const
+{
+ return root_->itemsAt(point);
+}
+
+QList<MapItem*> MapItemTree::itemsWithin(const QRect &viewport) const
+{
+ return root_->itemsWithin(viewport);
+}
+
+// TODO make static private
+bool checkPoint(const QPoint &p, const QRect &r)
+{
+ return ((r.x() <= p.x())
+ && (p.x() <= r.x() + r.width())
+ && (r.y() <= p.y())
+ && (p.y() <= r.y() + r.height()));
+}
+
+bool checkOverlap(const QRect& r1, const QRect &r2)
+{
+ return (((r1.x() <= r2.x() + r2.width()) && (r2.x() <= r1.x() + r1.width()))
+ &&
+ ((r1.y() <= r2.y() + r2.height()) && (r2.y() <= r1.y() + r1.height())));
+}
+
+int getIndex(const QPoint &p, const QRect &oldRec, const QRect &newRect)
+{
+ int result = 0;
+
+ if (oldRec.isValid() && checkPoint(p, oldRec))
+ result += 1;
+
+ if (checkPoint(p, newRect))
+ result += 2;
+
+ return result;
+}
+
+void MapItemTree::makeVisible(const QRect& viewport, QList<MapItem*> &added, QList<MapItem*> &removed)
+{
+ added.clear();
+ removed.clear();
+
+ QList<int> x;
+
+ if (viewport_.isValid()) {
+ x << viewport_.x();
+ if (viewport_.width() != 0)
+ x << viewport_.x() + viewport_.width();
+ }
+
+ x << viewport.x();
+ if (viewport.width() != 0)
+ x << viewport.x() + viewport.width();
+
+ qSort(x.begin(), x.end());
+
+ for (int i = x.size() - 1; i > 0; --i) {
+ int x1 = x.at(i);
+ int x2 = x.at(i - 1);
+ if (x1 == x2) {
+ x.removeAt(i);
+ }
+ }
+
+ QList<int> y;
+
+ if (viewport_.isValid()) {
+ y << viewport_.y();
+ if (viewport_.height() != 0)
+ y << viewport_.y() + viewport_.height();
+ }
+
+ y << viewport.y();
+ if (viewport.height() != 0)
+ y << viewport.y() + viewport.height();
+
+ qSort(y.begin(), y.end());
+
+ for (int i = y.size() - 1; i > 0; --i) {
+ int y1 = y.at(i);
+ int y2 = y.at(i - 1);
+ if (y1 == y2) {
+ y.removeAt(i);
+ }
+ }
+
+ QList<QRect> wasVisible;
+ QList<QRect> isVisible;
+ QRect overlap;
+
+ int xsize = x.size();
+ int ysize = y.size();
+
+ for (int j = 0; j < ysize - 1; ++j) {
+ int y1 = y.at(j);
+ int y2 = y.at(j + 1);
+ for (int i = 0; i < xsize - 1; ++i) {
+ int x1 = x.at(i);
+ int x2 = x.at(i + 1);
+
+ QRect r = QRect(x1, y1, x2 - x1, y2 - y1);
+
+ QHash<int, int> counts;
+ counts[0] = 0;
+ counts[1] = 0;
+ counts[2] = 0;
+ counts[3] = 0;
+
+ counts[getIndex(QPoint(x1, y1), viewport_, viewport)] += 1;
+ counts[getIndex(QPoint(x1, y2), viewport_, viewport)] += 1;
+ counts[getIndex(QPoint(x2, y1), viewport_, viewport)] += 1;
+ counts[getIndex(QPoint(x2, y2), viewport_, viewport)] += 1;
+
+ if (counts[0] != 0) {
+ continue;
+ }
+ if (counts[3] == 4) {
+ overlap = r;
+ continue;
+ }
+
+ if (counts[1] != 0) {
+ if (counts[2] != 0) {
+ continue;
+ } else {
+ wasVisible << r;
+ }
+ } else {
+ if (counts[2] != 0) {
+ isVisible << r;
+ } else {
+ continue;
+ }
+ }
+ }
+ }
+
+ for (int i = 0; i < wasVisible.size(); ++i) {
+
+ QList<MapItem*> items = itemsWithin(wasVisible.at(i));
+
+ for (int j = 0; j < items.size(); ++j) {
+
+ MapItem *item = items.at(j);
+
+ bool inMiddleGround = false;
+ if (overlap.isValid())
+ inMiddleGround = checkOverlap(item->bounds(), overlap);
+
+ if (item->visibleFromViewport() && !inMiddleGround) {
+ item->setVisibleFromViewport(false);
+ removed << item;
+ }
+ }
+ }
+
+ if (overlap.isValid())
+ isVisible << overlap;
+
+ for (int i = 0; i < isVisible.size(); ++i) {
+
+ QList<MapItem*> items = itemsWithin(isVisible.at(i));
+
+ for (int j = 0; j < items.size(); ++j) {
+
+ MapItem *item = items.at(j);
+
+ if (!item->visibleFromViewport()) {
+ item->setVisibleFromViewport(true);
+ added << item;
+ }
+ }
+ }
+
+ viewport_ = viewport;
+}
diff --git a/src/location/mapsgl/mapitem.h b/src/location/mapsgl/mapitem.h
index c9aa0da3..2c61bf07 100644
--- a/src/location/mapsgl/mapitem.h
+++ b/src/location/mapsgl/mapitem.h
@@ -46,6 +46,8 @@
#include <QSizeF>
#include <QtOpenGL/qgl.h>
+#include "intervaltree_p.h"
+
QT_BEGIN_HEADER
QT_BEGIN_NAMESPACE
@@ -82,11 +84,19 @@ public:
void setSceneNode(QGLSceneNode *sceneNode);
QGLSceneNode* sceneNode() const;
+ void setBounds(const QRect &bounds);
+ QRect bounds() const;
+
+ void setVisibleFromViewport(bool visible);
+ bool visibleFromViewport() const;
+
private:
QGeoCoordinate coordinate_;
QPointF anchor_;
QSizeF size_;
double zoom_;
+ QRect bounds_;
+ bool visible_;
QGLSceneNode* sceneNode_;
GLuint textureId_;
bool textureDirty_;
@@ -94,6 +104,28 @@ private:
QGLMaterial* defaultMaterial_;
};
+class Q_LOCATION_EXPORT MapItemTree
+{
+public:
+ MapItemTree();
+ ~MapItemTree();
+
+ void insert(MapItem *item);
+ void remove(MapItem *item);
+
+ bool isEmpty() const;
+ int size() const;
+
+ QList<MapItem*> items() const;
+ QList<MapItem*> itemsAt(const QPoint &point) const;
+ QList<MapItem*> itemsWithin(const QRect &viewport) const;
+ void makeVisible(const QRect& viewport, QList<MapItem*> &added, QList<MapItem*> &removed);
+private:
+
+ QRect viewport_;
+ AAInterval2DTree<MapItem*> *root_;
+};
+
QT_END_NAMESPACE
QT_END_HEADER
diff --git a/src/location/mapsgl/mapsgl.pri b/src/location/mapsgl/mapsgl.pri
index 59f40f08..19f6f390 100644
--- a/src/location/mapsgl/mapsgl.pri
+++ b/src/location/mapsgl/mapsgl.pri
@@ -28,6 +28,7 @@ PUBLIC_HEADERS += \
PRIVATE_HEADERS += \
mapsgl/frustum_p.h \
+ mapsgl/intervaltree_p.h \
mapsgl/map_p.h \
mapsgl/mapsphere_p.h \
mapsgl/projection_p.h
diff --git a/tests/auto/auto.pro b/tests/auto/auto.pro
index 49fc881e..6cc76b65 100644
--- a/tests/auto/auto.pro
+++ b/tests/auto/auto.pro
@@ -22,6 +22,8 @@ SUBDIRS += geotestplugin \
qplacesupplier \
qplacesearchresult \
declarative \
+ intervaltree \
+ mapitemtree \
sphere
contains(config_test_jsondb, yes) {
diff --git a/tests/auto/intervaltree/intervaltree.pro b/tests/auto/intervaltree/intervaltree.pro
new file mode 100644
index 00000000..6b919c5f
--- /dev/null
+++ b/tests/auto/intervaltree/intervaltree.pro
@@ -0,0 +1,8 @@
+TEMPLATE = app
+CONFIG += testcase
+TARGET = tst_intervaltree
+
+INCLUDEPATH = ../../../src/location/mapsgl
+SOURCES += tst_intervaltree.cpp
+
+QT += location testlib
diff --git a/tests/auto/intervaltree/tst_intervaltree.cpp b/tests/auto/intervaltree/tst_intervaltree.cpp
new file mode 100644
index 00000000..9c28e427
--- /dev/null
+++ b/tests/auto/intervaltree/tst_intervaltree.cpp
@@ -0,0 +1,772 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the test suite of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+#include <QObject>
+#include <QtTest/QtTest>
+
+#include "intervaltree_p.h"
+
+#include <QHash>
+
+QT_USE_NAMESPACE
+
+uint qHash(const QRect &rect)
+{
+ uint result = qHash(rect.x());
+ result = 17 * result + qHash(rect.y());
+ result = 17 * result + qHash(rect.width());
+ result = 17 * result + qHash(rect.height());
+ return result;
+}
+
+class tst_IntervalTree : public QObject
+{
+ Q_OBJECT
+
+public:
+ tst_IntervalTree() {
+
+ }
+
+private slots:
+ void insert_min();
+ void remove_min();
+
+ void insert_max();
+ void remove_max();
+
+ void insert_minmax();
+ void remove_minmax();
+
+ void itemsAt();
+ void itemsWithin();
+
+ void insert2D();
+ void insert2D_sameRect_sameData();
+ void insert2D_sameRect_uniqueData();
+
+ void remove2D();
+ void remove2D_duplicates();
+
+ void itemsAt2D();
+ void itemsWithin2D();
+};
+
+void tst_IntervalTree::insert_min()
+{
+ // effectively tests all the sizes lower than this as it goes
+ int size = 8;
+
+ // tree contains [1..size], inserted in order
+ AAIntervalTree<int> tree;
+ QList<int> data;
+ int limit = 1;
+
+ for (int j = 1; j <= size; ++j) {
+ tree.insert(j, 0, j);
+ data.append(j);
+ limit *= j;
+ }
+
+ QCOMPARE(tree.items(), data);
+
+ // we insert [1..size] into testTree in every possible order
+ // and compare the inorder traversal
+ for (int i = 0; i < limit; ++i) {
+ QList<int> tmp = data;
+ QList<int> input;
+ int div = 1;
+ for (int j = size; j > 0; --j) {
+ input.append(tmp.takeAt((i / div) % j));
+ div *= j;
+ }
+
+ AAIntervalTree<int> testTree;
+ for (int j = 0; j < input.size(); ++j) {
+ int k = input.at(j);
+ testTree.insert(k, 0, k);
+ }
+
+ QCOMPARE(testTree.items(), data);
+ }
+}
+
+void tst_IntervalTree::remove_min()
+{
+ // effectively tests all the sizes lower than this as it goes
+ int size = 8;
+
+ QList<int> data;
+ int limit = 1;
+
+ for (int j = 1; j <= size; ++j) {
+ data.append(j);
+ limit *= j;
+ }
+
+ for (int i = 0; i < limit; ++i) {
+ QList<int> tmp = data;
+ QList<int> input;
+ int div = 1;
+ for (int j = size; j > 0; --j) {
+ input.append(tmp.takeAt((i / div) % j));
+ div *= j;
+ }
+
+ // tree contains [1..size], inserted in order
+ AAIntervalTree<int> tree;
+ for (int j = 1; j <= size; ++j) {
+ tree.insert(j, 0, j);
+ }
+
+ // we remove [1..size] into tree in every possible order
+ // and compare the inorder traversal to a sorted list from
+ // which we remove the same values
+ QList<int> tmp2 = data;
+ for (int j = 0; j < input.size(); ++j) {
+ int k = input.at(j);
+ tmp2.removeAll(k);
+ tree.remove(k, 0, k);
+
+ QCOMPARE(tree.items(), tmp2);
+ }
+ }
+}
+
+void tst_IntervalTree::insert_max()
+{
+ // effectively tests all the sizes lower than this as it goes
+ int size = 8;
+
+ // tree contains [1..size], inserted in order
+ AAIntervalTree<int> tree;
+ QList<int> data;
+ int limit = 1;
+
+ for (int j = 1; j <= size; ++j) {
+ tree.insert(0, j, j);
+ data.append(j);
+ limit *= j;
+ }
+
+ QCOMPARE(tree.items(), data);
+
+ // we insert [1..size] into testTree in every possible order
+ // and compare the inorder traversal
+ for (int i = 0; i < limit; ++i) {
+ QList<int> tmp = data;
+ QList<int> input;
+ int div = 1;
+ for (int j = size; j > 0; --j) {
+ input.append(tmp.takeAt((i / div) % j));
+ div *= j;
+ }
+
+ AAIntervalTree<int> testTree;
+ for (int j = 0; j < input.size(); ++j) {
+ int k = input.at(j);
+ testTree.insert(0, k, k);
+ }
+
+ QCOMPARE(testTree.items(), data);
+ }
+}
+
+void tst_IntervalTree::remove_max()
+{
+ // effectively tests all the sizes lower than this as it goes
+ int size = 8;
+
+ QList<int> data;
+ int limit = 1;
+
+ for (int j = 1; j <= size; ++j) {
+ data.append(j);
+ limit *= j;
+ }
+
+ for (int i = 0; i < limit; ++i) {
+ QList<int> tmp = data;
+ QList<int> input;
+ int div = 1;
+ for (int j = size; j > 0; --j) {
+ input.append(tmp.takeAt((i / div) % j));
+ div *= j;
+ }
+
+ // tree contains [1..size], inserted in order
+ AAIntervalTree<int> tree;
+ for (int j = 1; j <= size; ++j) {
+ tree.insert(0, j, j);
+ }
+
+ // we remove [1..size] into tree in every possible order
+ // and compare the inorder traversal to a sorted list from
+ // which we remove the same values
+ QList<int> tmp2 = data;
+ for (int j = 0; j < input.size(); ++j) {
+ int k = input.at(j);
+ tmp2.removeAll(k);
+ tree.remove(0, k, k);
+
+ QCOMPARE(tree.items(), tmp2);
+ }
+ }
+}
+
+
+void tst_IntervalTree::insert_minmax()
+{
+ // effectively tests all the sizes lower than this as it goes
+ int size = 6;
+
+ // tree contains [(1,1),(1,2)..(size, size+1),(size,size+2)], inserted in order
+ AAIntervalTree<int> tree;
+ QList<int> data;
+ int limit = 1;
+
+ for (int j = 1; j <= size; ++j) {
+ tree.insert(j, j + 1, j * 2);
+ data.append(j * 2);
+ tree.insert(j, j + 2, j * 2 + 1);
+ data.append(j * 2 + 1);
+ limit *= 2 * j;
+ }
+
+ QCOMPARE(tree.items(), data);
+
+ // we insert the same data into testTree in every possible order
+ // and compare the inorder traversal
+ for (int i = 0; i < limit; ++i) {
+ QList<int> tmp = data;
+ QList<int> input;
+ int div = 1;
+ for (int j = size * 2; j > 0; --j) {
+ input.append(tmp.takeAt((i / div) % j));
+ div *= j;
+ }
+
+ AAIntervalTree<int> testTree;
+ for (int j = 0; j < input.size(); ++j) {
+ int k = input.at(j);
+ testTree.insert(k / 2, k / 2 + 1 + k % 2, k);
+ }
+
+ QCOMPARE(testTree.items(), data);
+ }
+}
+
+void tst_IntervalTree::remove_minmax()
+{
+ // effectively tests all the sizes lower than this as it goes
+ int size = 6;
+
+ QList<int> data;
+ int limit = 1;
+
+ for (int j = 1; j <= size; ++j) {
+ data.append(j * 2);
+ data.append(j * 2 + 1);
+ limit *= 2 * j;
+ }
+
+ for (int i = 0; i < limit; ++i) {
+ QList<int> tmp = data;
+ QList<int> input;
+ int div = 1;
+ for (int j = 2 * size; j > 0; --j) {
+ input.append(tmp.takeAt((i / div) % j));
+ div *= j;
+ }
+
+ // tree contains [1..size], inserted in order
+ AAIntervalTree<int> tree;
+ for (int j = 1; j <= size; ++j) {
+ tree.insert(j, j + 1, 2 * j);
+ tree.insert(j, j + 2, 2 * j + 1);
+ }
+
+ // we remove [1..size] into tree in every possible order
+ // and compare the inorder traversal to a sorted list from
+ // which we remove the same values
+ QList<int> tmp2 = data;
+ for (int j = 0; j < input.size(); ++j) {
+ int k = input.at(j);
+ tmp2.removeAll(k);
+ tree.remove(k / 2, k / 2 + 1 + k % 2, k);
+
+ QCOMPARE(tree.items(), tmp2);
+ }
+ }
+}
+
+struct ItemTriple {
+ ItemTriple(int min, int max, int value)
+ : min(min),
+ max(max),
+ value(value) {}
+
+ int min;
+ int max;
+ int value;
+};
+
+void tst_IntervalTree::itemsAt()
+{
+ QList<ItemTriple> triples;
+
+ triples << ItemTriple(1, 4, 1);
+ triples << ItemTriple(6, 9, 2);
+ triples << ItemTriple(7, 11, 3);
+ triples << ItemTriple(9, 10, 4);
+ triples << ItemTriple(16, 24, 5);
+ triples << ItemTriple(17, 22, 6);
+ triples << ItemTriple(18, 20, 7);
+ triples << ItemTriple(20, 21, 8);
+ triples << ItemTriple(26, 31, 9);
+ triples << ItemTriple(27, 27, 10);
+
+ QHash<int, QSet<int> > data;
+
+ AAIntervalTree<int> tree;
+
+ for (int i = 0; i < triples.size(); ++i) {
+ ItemTriple t1 = triples.at(i);
+ tree.insert(t1.min, t1.max, t1.value);
+ for (int j = t1.min; j <= t1.max; ++j) {
+ data[j].insert(t1.value);
+ }
+ }
+
+ for (int i = 1; i <= 31; ++i) {
+ QCOMPARE(tree.itemsAt(i).toSet(), data.value(i));
+ }
+}
+
+void tst_IntervalTree::itemsWithin()
+{
+ QList<ItemTriple> triples;
+
+ triples << ItemTriple(1, 4, 1);
+ triples << ItemTriple(6, 9, 2);
+ triples << ItemTriple(7, 11, 3);
+ triples << ItemTriple(9, 10, 4);
+ triples << ItemTriple(16, 24, 5);
+ triples << ItemTriple(17, 22, 6);
+ triples << ItemTriple(18, 20, 7);
+ triples << ItemTriple(20, 21, 8);
+ triples << ItemTriple(26, 31, 9);
+ triples << ItemTriple(27, 27, 10);
+
+ QHash<int, QSet<int> > data;
+
+ AAIntervalTree<int> tree;
+
+ for (int i = 0; i < triples.size(); ++i) {
+ ItemTriple t1 = triples.at(i);
+ tree.insert(t1.min, t1.max, t1.value);
+ for (int j = t1.min; j <= t1.max; ++j) {
+ data[j].insert(t1.value);
+ }
+ }
+
+ for (int i = 1; i <= 31; ++i) {
+ for (int j = i; j <= 31; ++j) {
+ QSet<int> d;
+ for (int k = i; k <= j; ++k)
+ d += data.value(k);
+ QCOMPARE(tree.itemsWithin(i, j).toSet(), d);
+ }
+ }
+}
+
+void tst_IntervalTree::insert2D()
+{
+ AAInterval2DTree<int> *tree = new AAInterval2DTree<int>();
+
+ int size = 6;
+ int index = 0;
+
+ QList<int> data;
+
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ tree->insert(QRect(x1, y1, x2 - x1, y2 - y1), index);
+ data.append(index);
+ ++index;
+ }
+ }
+ }
+ }
+
+ QCOMPARE(tree->items(), data);
+
+ delete tree;
+}
+
+void tst_IntervalTree::insert2D_sameRect_sameData()
+{
+ AAInterval2DTree<int> *tree = new AAInterval2DTree<int>();
+
+ int size = 6;
+ int index = 0;
+
+ QList<int> data;
+
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ tree->insert(QRect(x1, y1, x2 - x1, y2 - y1), index);
+ tree->insert(QRect(x1, y1, x2 - x1, y2 - y1), index);
+ data.append(index);
+ ++index;
+ }
+ }
+ }
+ }
+
+ QCOMPARE(tree->items(), data);
+
+ delete tree;
+}
+
+
+void tst_IntervalTree::insert2D_sameRect_uniqueData()
+{
+ AAInterval2DTree<int> *tree = new AAInterval2DTree<int>();
+
+ int size = 6;
+ int index = 0;
+
+ QList<int> data;
+
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ tree->insert(QRect(x1, y1, x2 - x1, y2 - y1), index);
+ data.append(index);
+ ++index;
+ tree->insert(QRect(x1, y1, x2 - x1, y2 - y1), index);
+ data.append(index);
+ ++index;
+ }
+ }
+ }
+ }
+
+ QCOMPARE(tree->items(), data);
+
+ delete tree;
+}
+
+void tst_IntervalTree::remove2D()
+{
+ int size = 6;
+ int index = 0;
+
+ QHash<QRect, int> indexHash;
+
+ QList<QList<QPair<QRect, int> > > removals;
+
+ QList<QPair<QRect, int> > removal1;
+
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ QRect r = QRect(x1, y1, x2 - x1, y2 - y1);
+ indexHash[r] = index;
+ removal1 << QPair<QRect, int>(QRect(x1, y1, x2 - x1, y2 - y1), index);
+ ++index;
+ }
+ }
+ }
+ }
+
+ removals << removal1;
+
+ QList<QPair<QRect, int> > removal2;
+
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ QRect r = QRect(x1, y1, x2 - x1, y2 - y1);
+ removal2 << QPair<QRect, int>(r, indexHash.value(r, -1));
+ }
+ }
+ }
+ }
+
+ removals << removal2;
+
+ QList<QPair<QRect, int> > removal3;
+
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ QRect r = QRect(x1, y1, x2 - x1, y2 - y1);
+ removal3 << QPair<QRect, int>(r, indexHash.value(r, -1));
+ }
+ }
+ }
+ }
+
+ removals << removal3;
+
+ QList<QPair<QRect, int> > removal4;
+
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ QRect r = QRect(x1, y1, x2 - x1, y2 - y1);
+ removal4 << QPair<QRect, int>(r, indexHash.value(r, -1));
+ }
+ }
+ }
+ }
+
+ removals << removal4;
+
+ QList<QPair<QRect, int> > removal5;
+
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ QRect r = QRect(x1, y1, x2 - x1, y2 - y1);
+ removal5 << QPair<QRect, int>(r, indexHash.value(r, -1));
+ }
+ }
+ }
+ }
+
+ removals << removal5;
+
+ QList<QPair<QRect, int> > removal6;
+
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ QRect r = QRect(x1, y1, x2 - x1, y2 - y1);
+ removal6 << QPair<QRect, int>(r, indexHash.value(r, -1));
+ }
+ }
+ }
+ }
+
+ removals << removal6;
+
+ index = 0;
+
+ for (int i = 0; i < removals.size(); ++i) {
+ AAInterval2DTree<int> *tree = new AAInterval2DTree<int>();
+
+ QList<int> data;
+
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ tree->insert(QRect(x1, y1, x2 - x1, y2 - y1), index);
+ data.append(index);
+ ++index;
+ }
+ }
+ }
+ }
+
+ QCOMPARE(tree->items(), data);
+
+ QList<QPair<QRect, int> > removal = removals.at(i);
+
+ for (int j = 0; j < removal.size(); ++j) {
+ QPair<QRect, int> p = removal.at(j);
+ tree->remove(p.first, p.second);
+ data.removeAll(p.second);
+
+ QCOMPARE(tree->items(), data);
+ }
+
+ delete tree;
+ }
+}
+
+void tst_IntervalTree::remove2D_duplicates()
+{
+ AAInterval2DTree<int> *tree = new AAInterval2DTree<int>();
+
+ QList<int> data;
+
+ QList<QPair<QRect, int> > items;
+
+ int size = 6;
+ int index = 0;
+
+ for (int x1 = 0; x1 < size; ++x1) {
+ for (int x2 = x1; x2 < size; ++x2) {
+ for (int y1 = 0; y1 < size; ++y1) {
+ for (int y2 = y1; y2 < size; ++y2) {
+ QRect r = QRect(x1, y1, x2 - x1, y2 - y1);
+ tree->insert(r, index);
+ data.append(index);
+ items << QPair<QRect, int>(r, index);
+ ++index;
+ tree->insert(r, index);
+ data.append(index);
+ items << QPair<QRect, int>(r, index);
+ ++index;
+ }
+ }
+ }
+ }
+
+ QCOMPARE(tree->items(), data);
+
+ for (int i = 0; i < items.size(); ++i) {
+ QPair<QRect, int> p = items.at(i);
+ tree->remove(p.first, p.second);
+ data.removeAll(p.second);
+ QCOMPARE(tree->items(), data);
+ }
+
+ delete tree;
+}
+
+void tst_IntervalTree::itemsAt2D()
+{
+ QList<ItemTriple> triples;
+
+ triples << ItemTriple(1, 4, 1);
+ triples << ItemTriple(6, 9, 2);
+ triples << ItemTriple(7, 11, 3);
+ triples << ItemTriple(9, 10, 4);
+ triples << ItemTriple(16, 24, 5);
+ triples << ItemTriple(17, 22, 6);
+ triples << ItemTriple(18, 20, 7);
+ triples << ItemTriple(20, 21, 8);
+ triples << ItemTriple(26, 31, 9);
+ triples << ItemTriple(27, 27, 10);
+
+ QHash<int, QSet<int> > data;
+
+ AAInterval2DTree<int> tree;
+
+ for (int i = 0; i < triples.size(); ++i) {
+ ItemTriple t1 = triples.at(i);
+ for (int j = 0; j < triples.size(); ++j) {
+ ItemTriple t2 = triples.at(i);
+ tree.insert(QRect(t1.min, t2.min, t1.max - t1.min, t2.max - t2.min), t1.value * 32 + t2.value);
+ for (int k = t1.min; k <= t1.max; ++k) {
+ for (int l = t2.min; l <= t2.max; ++l) {
+ data[k * 32 + l].insert(t1.value * 32 + t2.value);
+ }
+ }
+ }
+ }
+
+ for (int i = 1; i <= 31; ++i) {
+ for (int j = 1; j <= 31; ++j) {
+ QCOMPARE(tree.itemsAt(QPoint(i, j)).toSet(), data.value(i * 32 + j));
+ }
+ }
+}
+
+void tst_IntervalTree::itemsWithin2D()
+{
+ QList<ItemTriple> triples;
+
+ triples << ItemTriple(1, 4, 1);
+ triples << ItemTriple(6, 9, 2);
+ triples << ItemTriple(7, 11, 3);
+ triples << ItemTriple(9, 10, 4);
+ triples << ItemTriple(16, 24, 5);
+ triples << ItemTriple(17, 22, 6);
+ triples << ItemTriple(18, 20, 7);
+ triples << ItemTriple(20, 21, 8);
+ triples << ItemTriple(26, 31, 9);
+ triples << ItemTriple(27, 27, 10);
+
+ QHash<int, QSet<int> > data;
+
+ AAInterval2DTree<int> tree;
+
+ for (int i = 0; i < triples.size(); ++i) {
+ ItemTriple t1 = triples.at(i);
+ for (int j = 0; j < triples.size(); ++j) {
+ ItemTriple t2 = triples.at(i);
+ tree.insert(QRect(t1.min, t2.min, t1.max - t1.min, t2.max - t2.min), t1.value * 32 + t2.value);
+ for (int k = t1.min; k <= t1.max; ++k) {
+ for (int l = t2.min; l <= t2.max; ++l) {
+ data[k * 32 + l].insert(t1.value * 32 + t2.value);
+ }
+ }
+ }
+ }
+
+ for (int i1 = 1; i1 <= 31; ++i1) {
+ for (int i2 = i1; i2 <= 31; ++i2) {
+ for (int j1 = 1; j1 <= 31; ++j1) {
+ for (int j2 = j1; j2 <= 31; ++j2) {
+ QSet<int> d;
+ for (int x = i1; x <= i2; ++x) {
+ for (int y = j1; y <= j2; ++y) {
+ d += data.value(32 * x + y);
+ }
+ }
+ QCOMPARE(tree.itemsWithin(QRect(i1, j1, i2 - i1, j2 - j1)).toSet(), d);
+ }
+ }
+ }
+ }
+}
+
+
+QTEST_APPLESS_MAIN(tst_IntervalTree)
+#include "tst_intervaltree.moc"
+
+
diff --git a/tests/auto/mapitemtree/mapitemtree.pro b/tests/auto/mapitemtree/mapitemtree.pro
new file mode 100644
index 00000000..367d4eb3
--- /dev/null
+++ b/tests/auto/mapitemtree/mapitemtree.pro
@@ -0,0 +1,7 @@
+TEMPLATE = app
+CONFIG += testcase
+TARGET = tst_mapitemtree
+
+SOURCES += tst_mapitemtree.cpp
+
+QT += location testlib
diff --git a/tests/auto/mapitemtree/tst_mapitemtree.cpp b/tests/auto/mapitemtree/tst_mapitemtree.cpp
new file mode 100644
index 00000000..083cc152
--- /dev/null
+++ b/tests/auto/mapitemtree/tst_mapitemtree.cpp
@@ -0,0 +1,628 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the test suite of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+#include <QObject>
+#include <QtTest/QtTest>
+
+#include <mapitem.h>
+
+#include <QSet>
+#include <QHash>
+
+#include <QMetaType>
+
+#include <cmath>
+
+QT_USE_NAMESPACE
+
+uint qHash(const QRect &rect)
+{
+ uint result = qHash(rect.x());
+ result = 17 * result + qHash(rect.y());
+ result = 17 * result + qHash(rect.width());
+ result = 17 * result + qHash(rect.height());
+ return result;
+}
+
+class tst_MapItemTree : public QObject
+{
+ Q_OBJECT
+
+public:
+ tst_MapItemTree() {
+
+ }
+
+private slots:
+ void insertRemove();
+ void itemsAt_allQuads();
+ void itemsAt_singleQuad();
+ void itemsWithin_allQuads();
+ void itemsWithin_singleQuad();
+ void makeVisible();
+
+private:
+ MapItemTree* setupTree();
+ MapItem* dummyItemFromRect(const QRect &rect);
+};
+
+MapItem* tst_MapItemTree::dummyItemFromRect(const QRect &rect)
+{
+ MapItem *item = new MapItem();
+ item->setBounds(rect);
+ return item;
+}
+
+void tst_MapItemTree::insertRemove()
+{
+// MapItemTree *root = new MapItemTree(QRect(0, 0, 512, 512));
+ MapItemTree *root = new MapItemTree();
+
+ MapItem* item1 = dummyItemFromRect(QRect(16, 16, 16, 16));
+ MapItem* item2 = dummyItemFromRect(QRect(272, 16, 16, 16));
+ MapItem* item3 = dummyItemFromRect(QRect(16, 272, 16, 16));
+ MapItem* item4 = dummyItemFromRect(QRect(272, 272, 16, 16));
+ MapItem* item5 = dummyItemFromRect(QRect(248, 248, 16, 16));
+
+ MapItem* badItem1 = dummyItemFromRect(QRect(17, 17, 16, 16));
+ MapItem* badItem2 = dummyItemFromRect(QRect(273, 17, 16, 16));
+ MapItem* badItem3 = dummyItemFromRect(QRect(17, 273, 16, 16));
+ MapItem* badItem4 = dummyItemFromRect(QRect(273, 273, 16, 16));
+ MapItem* badItem5 = dummyItemFromRect(QRect(249, 249, 16, 16));
+
+ QCOMPARE(root->isEmpty(), true);
+ QCOMPARE(root->size(), 0);
+ QCOMPARE(root->items().size(), 0);
+
+ root->insert(item1);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 1);
+ QCOMPARE(root->items().size(), 1);
+
+ root->insert(item2);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 2);
+ QCOMPARE(root->items().size(), 2);
+
+ root->insert(item3);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 3);
+ QCOMPARE(root->items().size(), 3);
+
+ root->insert(item4);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 4);
+ QCOMPARE(root->items().size(), 4);
+
+ root->insert(item5);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 5);
+ QCOMPARE(root->items().size(), 5);
+
+ root->remove(badItem1);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 5);
+ QCOMPARE(root->items().size(), 5);
+
+ root->remove(badItem2);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 5);
+ QCOMPARE(root->items().size(), 5);
+
+ root->remove(badItem3);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 5);
+ QCOMPARE(root->items().size(), 5);
+
+ root->remove(badItem4);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 5);
+ QCOMPARE(root->items().size(), 5);
+
+ root->remove(badItem5);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 5);
+ QCOMPARE(root->items().size(), 5);
+
+ root->remove(item1);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 4);
+ QCOMPARE(root->items().size(), 4);
+
+ root->remove(item2);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 3);
+ QCOMPARE(root->items().size(), 3);
+
+ root->remove(item3);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 2);
+ QCOMPARE(root->items().size(), 2);
+
+ root->remove(item4);
+
+ QCOMPARE(root->isEmpty(), false);
+ QCOMPARE(root->size(), 1);
+ QCOMPARE(root->items().size(), 1);
+
+ root->remove(item5);
+
+ QCOMPARE(root->isEmpty(), true);
+ QCOMPARE(root->size(), 0);
+ QCOMPARE(root->items().size(), 0);
+
+ root->remove(badItem1);
+
+ QCOMPARE(root->isEmpty(), true);
+ QCOMPARE(root->size(), 0);
+ QCOMPARE(root->items().size(), 0);
+
+ root->remove(badItem2);
+
+ QCOMPARE(root->isEmpty(), true);
+ QCOMPARE(root->size(), 0);
+ QCOMPARE(root->items().size(), 0);
+
+ root->remove(badItem3);
+
+ QCOMPARE(root->isEmpty(), true);
+ QCOMPARE(root->size(), 0);
+ QCOMPARE(root->items().size(), 0);
+
+ root->remove(badItem4);
+
+ QCOMPARE(root->isEmpty(), true);
+ QCOMPARE(root->size(), 0);
+ QCOMPARE(root->items().size(), 0);
+
+ root->remove(badItem5);
+
+ QCOMPARE(root->isEmpty(), true);
+ QCOMPARE(root->size(), 0);
+ QCOMPARE(root->items().size(), 0);
+
+ delete root;
+
+ delete item1;
+ delete item2;
+ delete item3;
+ delete item4;
+ delete item5;
+
+ delete badItem1;
+ delete badItem2;
+ delete badItem3;
+ delete badItem4;
+ delete badItem5;
+}
+
+void tst_MapItemTree::itemsAt_allQuads()
+{
+ MapItemTree *tree = setupTree();
+
+ QList<int> empty;
+ empty.append(0);
+ empty.append(2);
+ empty.append(3);
+ empty.append(5);
+ empty.append(6);
+ empty.append(9);
+ empty.append(10);
+ empty.append(12);
+ empty.append(13);
+ empty.append(15);
+
+ QList<int> full;
+ full.append(1);
+ full.append(4);
+ full.append(7);
+ full.append(8);
+ full.append(11);
+ full.append(14);
+
+ // Test mid points of the "cells"
+
+ for (int x = 0; x < 16; ++x) {
+ for (int i = 0; i < empty.size(); ++i) {
+ int y = empty.at(i);
+ QCOMPARE(tree->itemsAt(QPoint(x * 16 + 8, y * 16 + 8)).size(), 0);
+ }
+ }
+
+ for (int i = 0; i < empty.size(); ++i) {
+ int x = empty.at(i);
+ for (int y = 0; y < 16; ++y) {
+ QCOMPARE(tree->itemsAt(QPoint(x * 16 + 8, y * 16 + 8)).size(), 0);
+ }
+ }
+
+ for (int i = 0; i < full.size(); ++i) {
+ int x = full.at(i);
+ for (int j = 0; j < full.size(); ++j) {
+ int y = full.at(j);
+ QList<MapItem*> items = tree->itemsAt(QPoint(x * 16 + 8, y * 16 + 8));
+
+ QCOMPARE(items.size(), 1);
+
+ QRect r = items.at(0)->bounds();
+
+ if (x != 8) {
+ QCOMPARE(r.x(), x * 16);
+ if (x != 7) {
+ QCOMPARE(r.width(), 15);
+ } else {
+ QCOMPARE(r.width(), 31);
+ }
+ } else {
+ QCOMPARE(r.x(), (x - 1) * 16);
+ QCOMPARE(r.width(), 31);
+ }
+
+ if (y != 8) {
+ QCOMPARE(r.y(), y * 16);
+ if (y != 7) {
+ QCOMPARE(r.height(), 15);
+ } else {
+ QCOMPARE(r.height(), 31);
+ }
+ } else {
+ QCOMPARE(r.y(), (y - 1) * 16);
+ QCOMPARE(r.height(), 31);
+ }
+ }
+ }
+
+ QList<MapItem*> items = tree->items();
+ delete tree;
+ qDeleteAll(items);
+}
+
+void tst_MapItemTree::itemsAt_singleQuad()
+{
+ MapItemTree *tree = setupTree();
+
+ // Test that we include x and x+width but don't go
+ // beyond that range on either side
+
+ QList<QPair<int, bool> > vals;
+ vals.append(QPair<int, bool>(15, false));
+ vals.append(QPair<int, bool>(16, true));
+ vals.append(QPair<int, bool>(24, true));
+ vals.append(QPair<int, bool>(31, true));
+ vals.append(QPair<int, bool>(32, false));
+
+ for (int i = 0; i < vals.size(); ++i) {
+
+ QPair<int, bool> px = vals.at(i);
+
+ for (int j = 0; j < vals.size(); ++j) {
+
+ QPair<int, bool> py = vals.at(j);
+
+ QList<MapItem*> items = tree->itemsAt(QPoint(px.first, py.first));
+
+ if (px.second && py.second) {
+ QCOMPARE(items.size(), 1);
+ QCOMPARE(items.at(0)->bounds(), QRect(16, 16, 15, 15));
+ } else {
+ QCOMPARE(items.size(), 0);
+ }
+ }
+ }
+
+ QList<MapItem*> items = tree->items();
+ delete tree;
+ qDeleteAll(items);
+}
+
+struct intervalAll {
+ intervalAll(int start, int end, int count)
+ : start(start),
+ end(end),
+ count(count) {}
+
+ int start;
+ int end;
+ int count;
+};
+
+void tst_MapItemTree::itemsWithin_allQuads()
+{
+ MapItemTree *tree = setupTree();
+
+ QList<int> start;
+ start.append(16);
+ start.append(64);
+ start.append(112);
+ start.append(176);
+ start.append(224);
+
+ QList<int> end;
+ end.append(31);
+ end.append(79);
+ end.append(143);
+ end.append(191);
+ end.append(239);
+
+ QList<intervalAll> vals;
+
+ for (int i = 0; i < start.size(); ++i) {
+
+ int s = start.at(i);
+
+ vals.append(intervalAll(s - 1, s, 1));
+ vals.append(intervalAll(s, s + 1, 1));
+ vals.append(intervalAll(s - 1, s + 1, 1));
+
+ for (int j = i; j < end.size(); ++j) {
+
+ int e = end.at(j);
+ int c = j - i + 1;
+
+ vals.append(intervalAll(s - 1, e + 1, c));
+ vals.append(intervalAll(s, e, c));
+ vals.append(intervalAll(s + 1, e - 1, c));
+ }
+ }
+
+ for (int i = 0; i < end.size() - 1; ++i) {
+ int e = end.at(i);
+ for (int j = i + 1; j < start.size(); ++j) {
+ int s = start.at(j);
+ vals.append(intervalAll(e + 1, s - 1, j - i - 1));
+ }
+ }
+
+ for (int i = 0; i < vals.size(); ++i) {
+
+ intervalAll ix = vals.at(i);
+
+ for (int j = 0; j < vals.size(); ++j) {
+
+ intervalAll iy = vals.at(j);
+
+ QRect r(ix.start, iy.start, ix.end - ix.start, iy.end - iy.start);
+
+ QList<MapItem*> items = tree->itemsWithin(r);
+
+ QCOMPARE(items.size(), ix.count * iy.count);
+ }
+ }
+
+ QList<MapItem*> items = tree->items();
+ delete tree;
+ qDeleteAll(items);
+}
+
+struct intervalSingle {
+ intervalSingle(int start, int end, bool contains)
+ : start(start),
+ end(end),
+ contains(contains) {}
+
+ int start;
+ int end;
+ bool contains;
+};
+
+void tst_MapItemTree::itemsWithin_singleQuad()
+{
+ MapItemTree *tree = setupTree();
+
+ QList<intervalSingle> vals;
+ vals.append(intervalSingle(14, 15, false));
+ vals.append(intervalSingle(15, 16, true));
+ vals.append(intervalSingle(15, 17, true));
+ vals.append(intervalSingle(16, 17, true));
+
+ vals.append(intervalSingle(15, 32, true));
+ vals.append(intervalSingle(16, 31, true));
+ vals.append(intervalSingle(17, 30, true));
+
+ vals.append(intervalSingle(30, 31, true));
+ vals.append(intervalSingle(30, 32, true));
+ vals.append(intervalSingle(31, 32, true));
+ vals.append(intervalSingle(32, 33, false));
+
+ for (int i = 0; i < vals.size(); ++i) {
+
+ intervalSingle ix = vals.at(i);
+
+ for (int j = 0; j < vals.size(); ++j) {
+
+ intervalSingle iy = vals.at(j);
+
+ QRect r(ix.start, iy.start, ix.end - ix.start, iy.end - iy.start);
+
+ QList<MapItem*> items = tree->itemsWithin(r);
+
+ if (ix.contains && iy.contains) {
+ QCOMPARE(items.size(), 1);
+ QCOMPARE(items.at(0)->bounds(), QRect(16, 16, 15, 15));
+ } else {
+ QCOMPARE(items.size(), 0);
+ }
+ }
+ }
+
+ QList<MapItem*> items = tree->items();
+ delete tree;
+ qDeleteAll(items);
+}
+
+void tst_MapItemTree::makeVisible()
+{
+ MapItemTree *tree = setupTree();
+
+ QList<MapItem*> added;
+ QList<MapItem*> removed;
+
+ tree->makeVisible(QRect(0, 0, 1, 1), added, removed);
+ QCOMPARE(added.size(), 0);
+ QCOMPARE(removed.size(), 25);
+
+ QList<int> start;
+ start.append(16);
+ start.append(64);
+ start.append(112);
+ start.append(176);
+ start.append(224);
+
+ QList<int> end;
+ end.append(31);
+ end.append(79);
+ end.append(143);
+ end.append(191);
+ end.append(239);
+
+ QList<intervalAll> vals;
+
+ for (int i = 0; i < start.size(); ++i) {
+
+ int s = start.at(i);
+
+ vals.append(intervalAll(s - 1, s, 1));
+ vals.append(intervalAll(s, s + 1, 1));
+ vals.append(intervalAll(s - 1, s + 1, 1));
+
+ for (int j = i; j < end.size(); ++j) {
+
+ int e = end.at(j);
+ int c = j - i + 1;
+
+ vals.append(intervalAll(s - 1, e + 1, c));
+ vals.append(intervalAll(s, e, c));
+ vals.append(intervalAll(s + 1, e - 1, c));
+ }
+ }
+
+ for (int i = 0; i < end.size() - 1; ++i) {
+ int e = end.at(i);
+ for (int j = i + 1; j < start.size(); ++j) {
+ int s = start.at(j);
+ vals.append(intervalAll(e + 1, s - 1, j - i - 1));
+ }
+ }
+
+ for (int i = 0; i < vals.size(); ++i) {
+
+ intervalAll ix = vals.at(i);
+
+ for (int j = 0; j < vals.size(); ++j) {
+
+ intervalAll iy = vals.at(j);
+
+ QRect r(ix.start, iy.start, ix.end - ix.start, iy.end - iy.start);
+
+ tree->makeVisible(r, added, removed);
+
+ QCOMPARE(added.size(), ix.count * iy.count);
+ QCOMPARE(removed.size(), 0);
+
+ tree->makeVisible(QRect(0, 0, 1, 1), added, removed);
+
+ QCOMPARE(added.size(), 0);
+ QCOMPARE(removed.size(), ix.count * iy.count);
+ }
+ }
+
+ QList<MapItem*> items = tree->items();
+ delete tree;
+ qDeleteAll(items);
+}
+
+MapItemTree* tst_MapItemTree::setupTree()
+{
+ MapItemTree *root = new MapItemTree();
+
+ root->insert(dummyItemFromRect(QRect(16, 16, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(64, 16, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(112, 16, 31, 15)));
+ root->insert(dummyItemFromRect(QRect(176, 16, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(224, 16, 15, 15)));
+
+ root->insert(dummyItemFromRect(QRect(16, 64, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(64, 64, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(112, 64, 31, 15)));
+ root->insert(dummyItemFromRect(QRect(176, 64, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(224, 64, 15, 15)));
+
+ root->insert(dummyItemFromRect(QRect(16, 112, 15, 31)));
+ root->insert(dummyItemFromRect(QRect(64, 112, 15, 31)));
+ root->insert(dummyItemFromRect(QRect(112, 112, 31, 31)));
+ root->insert(dummyItemFromRect(QRect(176, 112, 15, 31)));
+ root->insert(dummyItemFromRect(QRect(224, 112, 15, 31)));
+
+ root->insert(dummyItemFromRect(QRect(16, 176, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(64, 176, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(112, 176, 31, 15)));
+ root->insert(dummyItemFromRect(QRect(176, 176, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(224, 176, 15, 15)));
+
+ root->insert(dummyItemFromRect(QRect(16, 224, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(64, 224, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(112, 224, 31, 15)));
+ root->insert(dummyItemFromRect(QRect(176, 224, 15, 15)));
+ root->insert(dummyItemFromRect(QRect(224, 224, 15, 15)));
+
+ QList<MapItem*> added;
+ QList<MapItem*> removed;
+ root->makeVisible(QRect(0, 0, 256, 256), added, removed);
+
+ return root;
+}
+
+QTEST_APPLESS_MAIN(tst_MapItemTree)
+
+#include "tst_mapitemtree.moc"
+
View Lorry Controller Status