1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "qgraphicsscene_bsp_p.h"

    43 

    44 #ifndef QT_NO_GRAPHICSVIEW

    45 

    46 #include <QtCore/qstring.h>

    47 #include <private/qgraphicsitem_p.h>

    48 

    49 QT_BEGIN_NAMESPACE

    50 

    51 class QGraphicsSceneInsertItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor

    52 {

    53 public:

    54     QGraphicsItem *item;

    55 

    56     void visit(QList<QGraphicsItem *> *items)

    57     { items->prepend(item); }

    58 };

    59 

    60 class QGraphicsSceneRemoveItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor

    61 {

    62 public:

    63     QGraphicsItem *item;

    64 

    65     void visit(QList<QGraphicsItem *> *items)

    66     { items->removeAll(item); }

    67 };

    68 

    69 class QGraphicsSceneFindItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor

    70 {

    71 public:

    72     QList<QGraphicsItem *> *foundItems;

    73     bool onlyTopLevelItems;

    74 

    75     void visit(QList<QGraphicsItem *> *items)

    76     {

    77         for (int i = 0; i < items->size(); ++i) {

    78             QGraphicsItem *item = items->at(i);

    79             if (onlyTopLevelItems && item->d_ptr->parent)

    80                 item = item->topLevelItem();

    81             if (!item->d_func()->itemDiscovered && item->d_ptr->visible) {

    82                 item->d_func()->itemDiscovered = 1;

    83                 foundItems->prepend(item);

    84             }

    85         }

    86     }

    87 };

    88 

    89 QGraphicsSceneBspTree::QGraphicsSceneBspTree()

    90     : leafCnt(0)

    91 {

    92     insertVisitor = new QGraphicsSceneInsertItemBspTreeVisitor;

    93     removeVisitor = new QGraphicsSceneRemoveItemBspTreeVisitor;

    94     findVisitor = new QGraphicsSceneFindItemBspTreeVisitor;

    95 }

    96 

    97 QGraphicsSceneBspTree::~QGraphicsSceneBspTree()

    98 {

    99     delete insertVisitor;

   100     delete removeVisitor;

   101     delete findVisitor;

   102 }

   103 

   104 void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth)

   105 {

   106     this->rect = rect;

   107     leafCnt = 0;

   108     nodes.resize((1 << (depth + 1)) - 1);

   109     nodes.fill(Node());

   110     leaves.resize(1 << depth);

   111     leaves.fill(QList<QGraphicsItem *>());

   112 

   113     initialize(rect, depth, 0);

   114 }

   115 

   116 void QGraphicsSceneBspTree::clear()

   117 {

   118     leafCnt = 0;

   119     nodes.clear();

   120     leaves.clear();

   121 }

   122 

   123 void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item, const QRectF &rect)

   124 {

   125     insertVisitor->item = item;

   126     climbTree(insertVisitor, rect);

   127 }

   128 

   129 void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item, const QRectF &rect)

   130 {

   131     removeVisitor->item = item;

   132     climbTree(removeVisitor, rect);

   133 }

   134 

   135 void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items)

   136 {

   137     for (int i = 0; i < leaves.size(); ++i) {

   138         QList<QGraphicsItem *> newItemList;

   139         const QList<QGraphicsItem *> &oldItemList = leaves[i];

   140         for (int j = 0; j < oldItemList.size(); ++j) {

   141             QGraphicsItem *item = oldItemList.at(j);

   142             if (!items.contains(item))

   143                 newItemList << item;

   144         }

   145         leaves[i] = newItemList;

   146     }

   147 }

   148 

   149 QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect, bool onlyTopLevelItems) const

   150 {

   151     QList<QGraphicsItem *> tmp;

   152     findVisitor->foundItems = &tmp;

   153     findVisitor->onlyTopLevelItems = onlyTopLevelItems;

   154     climbTree(findVisitor, rect);

   155     // Reset discovery bits.

   156     for (int i = 0; i < tmp.size(); ++i)

   157         tmp.at(i)->d_ptr->itemDiscovered = 0;

   158     return tmp;

   159 }

   160 

   161 int QGraphicsSceneBspTree::leafCount() const

   162 {

   163     return leafCnt;

   164 }

   165 

   166 QString QGraphicsSceneBspTree::debug(int index) const

   167 {

   168     const Node *node = &nodes.at(index);

   169 

   170     QString tmp;

   171     if (node->type == Node::Leaf) {

   172         QRectF rect = rectForIndex(index);

   173         if (!leaves[node->leafIndex].isEmpty()) {

   174             tmp += QString::fromLatin1("[%1, %2, %3, %4] contains %5 items\n")

   175                    .arg(rect.left()).arg(rect.top())

   176                    .arg(rect.width()).arg(rect.height())

   177                    .arg(leaves[node->leafIndex].size());

   178         }

   179     } else {

   180         if (node->type == Node::Horizontal) {

   181             tmp += debug(firstChildIndex(index));

   182             tmp += debug(firstChildIndex(index) + 1);

   183         } else {

   184             tmp += debug(firstChildIndex(index));

   185             tmp += debug(firstChildIndex(index) + 1);

   186         }

   187     }

   188 

   189     return tmp;

   190 }

   191 

   192 void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index)

   193 {

   194     Node *node = &nodes[index];

   195     if (index == 0) {

   196         node->type = Node::Horizontal;

   197         node->offset = rect.center().x();

   198     }

   199 

   200     if (depth) {

   201         Node::Type type;

   202         QRectF rect1, rect2;

   203         qreal offset1, offset2;

   204 

   205         if (node->type == Node::Horizontal) {

   206             type = Node::Vertical;

   207             rect1.setRect(rect.left(), rect.top(), rect.width(), rect.height() / 2);

   208             rect2.setRect(rect1.left(), rect1.bottom(), rect1.width(), rect.height() - rect1.height());

   209             offset1 = rect1.center().x();

   210             offset2 = rect2.center().x();

   211         } else {

   212             type = Node::Horizontal;

   213             rect1.setRect(rect.left(), rect.top(), rect.width() / 2, rect.height());

   214             rect2.setRect(rect1.right(), rect1.top(), rect.width() - rect1.width(), rect1.height());

   215             offset1 = rect1.center().y();

   216             offset2 = rect2.center().y();

   217         }

   218 

   219         int childIndex = firstChildIndex(index);

   220 

   221         Node *child = &nodes[childIndex];

   222         child->offset = offset1;

   223         child->type = type;

   224 

   225         child = &nodes[childIndex + 1];

   226         child->offset = offset2;

   227         child->type = type;

   228 

   229         initialize(rect1, depth - 1, childIndex);

   230         initialize(rect2, depth - 1, childIndex + 1);

   231     } else {

   232         node->type = Node::Leaf;

   233         node->leafIndex = leafCnt++;

   234     }

   235 }

   236 

   237 void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) const

   238 {

   239     if (nodes.isEmpty())

   240         return;

   241 

   242     const Node &node = nodes.at(index);

   243     const int childIndex = firstChildIndex(index);

   244 

   245     switch (node.type) {

   246     case Node::Leaf: {

   247         visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex]));

   248         break;

   249     }

   250     case Node::Vertical:

   251         if (rect.left() < node.offset) {

   252             climbTree(visitor, rect, childIndex);

   253             if (rect.right() >= node.offset)

   254                 climbTree(visitor, rect, childIndex + 1);

   255         } else {

   256             climbTree(visitor, rect, childIndex + 1);

   257         }

   258         break;

   259     case Node::Horizontal:

   260         if (rect.top() < node.offset) {

   261             climbTree(visitor, rect, childIndex);

   262             if (rect.bottom() >= node.offset)

   263                 climbTree(visitor, rect, childIndex + 1);

   264         } else {

   265             climbTree(visitor, rect, childIndex + 1);

   266         }

   267     }

   268 }

   269 

   270 QRectF QGraphicsSceneBspTree::rectForIndex(int index) const

   271 {

   272     if (index <= 0)

   273         return rect;

   274 

   275     int parentIdx = parentIndex(index);

   276     QRectF rect = rectForIndex(parentIdx);

   277     const Node *parent = &nodes.at(parentIdx);

   278 

   279     if (parent->type == Node::Horizontal) {

   280         if (index & 1)

   281             rect.setRight(parent->offset);

   282         else

   283             rect.setLeft(parent->offset);

   284     } else {

   285         if (index & 1)

   286             rect.setBottom(parent->offset);

   287         else

   288             rect.setTop(parent->offset);

   289     }

   290 

   291     return rect;

   292 }

   293 

   294 QT_END_NAMESPACE

   295 

   296 #endif // QT_NO_GRAPHICSVIEW