/****************************************************************************

**

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

** All rights reserved.

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

**

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

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

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

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

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, 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.

**

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

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

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

/*!

    \class QGraphicsScene

    \brief The QGraphicsScene class provides a surface for managing a large

    number of 2D graphical items.

    \since 4.2

    \ingroup graphicsview-api

    The class serves as a container for QGraphicsItems. It is used together

    with QGraphicsView for visualizing graphical items, such as lines,

    rectangles, text, or even custom items, on a 2D surface. QGraphicsScene is

    part of the \l{Graphics View Framework}.

    QGraphicsScene also provides functionality that lets you efficiently

    determine both the location of items, and for determining what items are

    visible within an arbitrary area on the scene. With the QGraphicsView

    widget, you can either visualize the whole scene, or zoom in and view only

    parts of the scene.

    Example:

    \snippet doc/src/snippets/code/src_gui_graphicsview_qgraphicsscene.cpp 0

    Note that QGraphicsScene has no visual appearance of its own; it only

    manages the items. You need to create a QGraphicsView widget to visualize

    the scene.

    To add items to a scene, you start off by constructing a QGraphicsScene

    object. Then, you have two options: either add your existing QGraphicsItem

    objects by calling addItem(), or you can call one of the convenience

    functions addEllipse(), addLine(), addPath(), addPixmap(), addPolygon(),

    addRect(), or addText(), which all return a pointer to the newly added item.

    The dimensions of the items added with these functions are relative to the

    item's coordinate system, and the items position is initialized to (0,

    0) in the scene.

    You can then visualize the scene using QGraphicsView. When the scene

    changes, (e.g., when an item moves or is transformed) QGraphicsScene

    emits the changed() signal. To remove an item, call removeItem().

    QGraphicsScene uses an indexing algorithm to manage the location of items

    efficiently. By default, a BSP (Binary Space Partitioning) tree is used; an

    algorithm suitable for large scenes where most items remain static (i.e.,

    do not move around). You can choose to disable this index by calling

    setItemIndexMethod(). For more information about the available indexing

    algorithms, see the itemIndexMethod property.

    The scene's bounding rect is set by calling setSceneRect(). Items can be

    placed at any position on the scene, and the size of the scene is by

    default unlimited. The scene rect is used only for internal bookkeeping,

    maintaining the scene's item index. If the scene rect is unset,

    QGraphicsScene will use the bounding area of all items, as returned by

    itemsBoundingRect(), as the scene rect. However, itemsBoundingRect() is a

    relatively time consuming function, as it operates by collecting

    positional information for every item on the scene. Because of this, you

    should always set the scene rect when operating on large scenes.

    One of QGraphicsScene's greatest strengths is its ability to efficiently

    determine the location of items. Even with millions of items on the scene,

    the items() functions can determine the location of an item within few

    milliseconds. There are several overloads to items(): one that finds items

    at a certain position, one that finds items inside or intersecting with a

    polygon or a rectangle, and more. The list of returned items is sorted by

    stacking order, with the topmost item being the first item in the list.

    For convenience, there is also an itemAt() function that returns the

    topmost item at a given position.

    QGraphicsScene maintains selection information for the scene. To select

    items, call setSelectionArea(), and to clear the current selection, call

    clearSelection(). Call selectedItems() to get the list of all selected

    items.

    \section1 Event Handling and Propagation

    Another responsibility that QGraphicsScene has, is to propagate events

    from QGraphicsView. To send an event to a scene, you construct an event

    that inherits QEvent, and then send it using, for example,

    QApplication::sendEvent(). event() is responsible for dispatching

    the event to the individual items. Some common events are handled by

    convenience event handlers. For example, key press events are handled by

    keyPressEvent(), and mouse press events are handled by mousePressEvent().

    Key events are delivered to the \e {focus item}. To set the focus item,

    you can either call setFocusItem(), passing an item that accepts focus, or

    the item itself can call QGraphicsItem::setFocus().  Call focusItem() to

    get the current focus item. For compatibility with widgets, the scene also

    maintains its own focus information. By default, the scene does not have

    focus, and all key events are discarded. If setFocus() is called, or if an

    item on the scene gains focus, the scene automatically gains focus. If the

    scene has focus, hasFocus() will return true, and key events will be

    forwarded to the focus item, if any. If the scene loses focus, (i.e.,

    someone calls clearFocus(),) while an item has focus, the scene will

    maintain its item focus information, and once the scene regains focus, it

    will make sure the last focus item regains focus.

    For mouse-over effects, QGraphicsScene dispatches \e {hover

    events}. If an item accepts hover events (see

    QGraphicsItem::acceptHoverEvents()), it will receive a \l

    {QEvent::}{GraphicsSceneHoverEnter} event when the mouse enters

    its area. As the mouse continues moving inside the item's area,

    QGraphicsScene will send it \l {QEvent::}{GraphicsSceneHoverMove}

    events. When the mouse leaves the item's area, the item will

    receive a \l {QEvent::}{GraphicsSceneHoverLeave} event.

    All mouse events are delivered to the current \e {mouse grabber}

    item. An item becomes the scene's mouse grabber if it accepts

    mouse events (see QGraphicsItem::acceptedMouseButtons()) and it

    receives a mouse press. It stays the mouse grabber until it

    receives a mouse release when no other mouse buttons are

    pressed. You can call mouseGrabberItem() to determine what item is

    currently grabbing the mouse.

    \sa QGraphicsItem, QGraphicsView

*/

/*!

    \enum QGraphicsScene::SceneLayer

    \since 4.3

    This enum describes the rendering layers in a QGraphicsScene. When

    QGraphicsScene draws the scene contents, it renders each of these layers

    separately, in order.

    Each layer represents a flag that can be OR'ed together when calling

    functions such as invalidate() or QGraphicsView::invalidateScene().

    \value ItemLayer The item layer. QGraphicsScene renders all items are in

    this layer by calling the virtual function drawItems(). The item layer is

    drawn after the background layer, but before the foreground layer.

    \value BackgroundLayer The background layer. QGraphicsScene renders the

    scene's background in this layer by calling the virtual function

    drawBackground(). The background layer is drawn first of all layers.

    \value ForegroundLayer The foreground layer. QGraphicsScene renders the

    scene's foreground in this layer by calling the virtual function

    drawForeground().  The foreground layer is drawn last of all layers.

    \value AllLayers All layers; this value represents a combination of all

    three layers.

    \sa invalidate(), QGraphicsView::invalidateScene()

*/

/*!

    \enum QGraphicsScene::ItemIndexMethod

    This enum describes the indexing algorithms QGraphicsScene provides for

    managing positional information about items on the scene.

    \value BspTreeIndex A Binary Space Partitioning tree is applied. All

    QGraphicsScene's item location algorithms are of an order close to

    logarithmic complexity, by making use of binary search. Adding, moving and

    removing items is logarithmic. This approach is best for static scenes

    (i.e., scenes where most items do not move).

    \value NoIndex No index is applied. Item location is of linear complexity,

    as all items on the scene are searched. Adding, moving and removing items,

    however, is done in constant time. This approach is ideal for dynamic

    scenes, where many items are added, moved or removed continuously.

    \sa setItemIndexMethod(), bspTreeDepth

*/

#include "qgraphicsscene.h"

#ifndef QT_NO_GRAPHICSVIEW

#include "qgraphicsitem.h"

#include "qgraphicsitem_p.h"

#include "qgraphicslayout.h"

#include "qgraphicsscene_p.h"

#include "qgraphicssceneevent.h"

#include "qgraphicsview.h"

#include "qgraphicsview_p.h"

#include "qgraphicswidget.h"

#include "qgraphicswidget_p.h"

#include "qgraphicssceneindex_p.h"

#include "qgraphicsscenebsptreeindex_p.h"

#include "qgraphicsscenelinearindex_p.h"

#include <QtCore/qdebug.h>

#include <QtCore/qlist.h>

#include <QtCore/qmath.h>

#include <QtCore/qrect.h>

#include <QtCore/qset.h>

#include <QtCore/qstack.h>

#include <QtCore/qtimer.h>

#include <QtCore/qvarlengtharray.h>

#include <QtCore/QMetaMethod>

#include <QtGui/qapplication.h>

#include <QtGui/qdesktopwidget.h>

#include <QtGui/qevent.h>

#include <QtGui/qgraphicslayout.h>

#include <QtGui/qgraphicsproxywidget.h>

#include <QtGui/qgraphicswidget.h>

#include <QtGui/qmatrix.h>

#include <QtGui/qpaintengine.h>

#include <QtGui/qpainter.h>

#include <QtGui/qpixmapcache.h>

#include <QtGui/qpolygon.h>

#include <QtGui/qstyleoption.h>

#include <QtGui/qtooltip.h>

#include <QtGui/qtransform.h>

#include <QtGui/qinputcontext.h>

#include <QtGui/qgraphicseffect.h>

#include <private/qapplication_p.h>

#include <private/qobject_p.h>

#ifdef Q_WS_X11

#include <private/qt_x11_p.h>

#endif

#include <private/qgraphicseffect_p.h>

#include <private/qgesturemanager_p.h>

#include <private/qpathclipper_p.h>

// #define GESTURE_DEBUG

#ifndef GESTURE_DEBUG

# define DEBUG if (0) qDebug

#else

# define DEBUG qDebug

#endif

QT_BEGIN_NAMESPACE

bool qt_sendSpontaneousEvent(QObject *receiver, QEvent *event);

static void _q_hoverFromMouseEvent(QGraphicsSceneHoverEvent *hover, const QGraphicsSceneMouseEvent *mouseEvent)

{

    hover->setWidget(mouseEvent->widget());

    hover->setPos(mouseEvent->pos());

    hover->setScenePos(mouseEvent->scenePos());

    hover->setScreenPos(mouseEvent->screenPos());

    hover->setLastPos(mouseEvent->lastPos());

    hover->setLastScenePos(mouseEvent->lastScenePos());

    hover->setLastScreenPos(mouseEvent->lastScreenPos());

    hover->setModifiers(mouseEvent->modifiers());

    hover->setAccepted(mouseEvent->isAccepted());

}

/*!

    \internal

*/

QGraphicsScenePrivate::QGraphicsScenePrivate()

    : indexMethod(QGraphicsScene::BspTreeIndex),

      index(0),

      lastItemCount(0),

      hasSceneRect(false),

      dirtyGrowingItemsBoundingRect(true),

      updateAll(false),

      calledEmitUpdated(false),

      processDirtyItemsEmitted(false),

      needSortTopLevelItems(true),

      holesInTopLevelSiblingIndex(false),

      topLevelSequentialOrdering(true),

      scenePosDescendantsUpdatePending(false),

      stickyFocus(false),

      hasFocus(false),

      lastMouseGrabberItemHasImplicitMouseGrab(false),

      allItemsIgnoreHoverEvents(true),

      allItemsUseDefaultCursor(true),

      painterStateProtection(true),

      sortCacheEnabled(false),

      allItemsIgnoreTouchEvents(true),

      selectionChanging(0),

      rectAdjust(2),

      focusItem(0),

      lastFocusItem(0),

      tabFocusFirst(0),

      activePanel(0),

      lastActivePanel(0),

      activationRefCount(0),

      childExplicitActivation(0),

      lastMouseGrabberItem(0),

      dragDropItem(0),

      enterWidget(0),

      lastDropAction(Qt::IgnoreAction),

      style(0)

{

}

/*!

    \internal

*/

void QGraphicsScenePrivate::init()

{

    Q_Q(QGraphicsScene);

    index = new QGraphicsSceneBspTreeIndex(q);

    // Keep this index so we can check for connected slots later on.

    changedSignalIndex = signalIndex("changed(QList<QRectF>)");

    processDirtyItemsIndex = q->metaObject()->indexOfSlot("_q_processDirtyItems()");

    polishItemsIndex = q->metaObject()->indexOfSlot("_q_polishItems()");

    qApp->d_func()->scene_list.append(q);

    q->update();

}

/*!

    \internal

*/

QGraphicsScenePrivate *QGraphicsScenePrivate::get(QGraphicsScene *q)

{

    return q->d_func();

}

void QGraphicsScenePrivate::_q_emitUpdated()

{

    Q_Q(QGraphicsScene);

    calledEmitUpdated = false;

    if (dirtyGrowingItemsBoundingRect) {

        if (!hasSceneRect) {

            const QRectF oldGrowingItemsBoundingRect = growingItemsBoundingRect;

            growingItemsBoundingRect |= q->itemsBoundingRect();

            if (oldGrowingItemsBoundingRect != growingItemsBoundingRect)

                emit q->sceneRectChanged(growingItemsBoundingRect);

        }

        dirtyGrowingItemsBoundingRect = false;

    }

    // Ensure all views are connected if anything is connected. This disables

    // the optimization that items send updates directly to the views, but it

    // needs to happen in order to keep compatibility with the behavior from

    // Qt 4.4 and backward.

    if (isSignalConnected(changedSignalIndex)) {

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

            QGraphicsView *view = views.at(i);

            if (!view->d_func()->connectedToScene) {

                view->d_func()->connectedToScene = true;

                q->connect(q, SIGNAL(changed(QList<QRectF>)),

                           views.at(i), SLOT(updateScene(QList<QRectF>)));

            }

        }

    } else {

        if (views.isEmpty()) {

            updateAll = false;

            return;

        }

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

            views.at(i)->d_func()->processPendingUpdates();

        // It's important that we update all views before we dispatch, hence two for-loops.

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

            views.at(i)->d_func()->dispatchPendingUpdateRequests();

        return;

    }

    // Notify the changes to anybody interested.

    QList<QRectF> oldUpdatedRects;

    oldUpdatedRects = updateAll ? (QList<QRectF>() << q->sceneRect()) : updatedRects;

    updateAll = false;

    updatedRects.clear();

    emit q->changed(oldUpdatedRects);

}

/*!

    \internal

    ### This function is almost identical to QGraphicsItemPrivate::addChild().

*/

void QGraphicsScenePrivate::registerTopLevelItem(QGraphicsItem *item)

{

    item->d_ptr->ensureSequentialSiblingIndex();

    needSortTopLevelItems = true; // ### maybe false

    item->d_ptr->siblingIndex = topLevelItems.size();

    topLevelItems.append(item);

}

/*!

    \internal

    ### This function is almost identical to QGraphicsItemPrivate::removeChild().

*/

void QGraphicsScenePrivate::unregisterTopLevelItem(QGraphicsItem *item)

{

    if (!holesInTopLevelSiblingIndex)

        holesInTopLevelSiblingIndex = item->d_ptr->siblingIndex != topLevelItems.size() - 1;

    if (topLevelSequentialOrdering && !holesInTopLevelSiblingIndex)

        topLevelItems.removeAt(item->d_ptr->siblingIndex);

    else

        topLevelItems.removeOne(item);

    // NB! Do not use topLevelItems.removeAt(item->d_ptr->siblingIndex) because

    // the item is not guaranteed to be at the index after the list is sorted

    // (see ensureSortedTopLevelItems()).

    item->d_ptr->siblingIndex = -1;

    if (topLevelSequentialOrdering)

        topLevelSequentialOrdering = !holesInTopLevelSiblingIndex;

}

/*!

    \internal

*/

void QGraphicsScenePrivate::_q_polishItems()

{

    if (unpolishedItems.isEmpty())

        return;

    const QVariant booleanTrueVariant(true);

    QGraphicsItem *item = 0;

    QGraphicsItemPrivate *itemd = 0;

    const int oldUnpolishedCount = unpolishedItems.count();

    for (int i = 0; i < oldUnpolishedCount; ++i) {

        item = unpolishedItems.at(i);

        if (!item)

            continue;

        itemd = item->d_ptr.data();

        itemd->pendingPolish = false;

        if (!itemd->explicitlyHidden) {

            item->itemChange(QGraphicsItem::ItemVisibleChange, booleanTrueVariant);

            item->itemChange(QGraphicsItem::ItemVisibleHasChanged, booleanTrueVariant);

        }

        if (itemd->isWidget) {

            QEvent event(QEvent::Polish);

            QApplication::sendEvent((QGraphicsWidget *)item, &event);

        }

    }

    if (unpolishedItems.count() == oldUnpolishedCount) {

        // No new items were added to the vector.

        unpolishedItems.clear();

    } else {

        // New items were appended; keep them and remove the old ones.

        unpolishedItems.remove(0, oldUnpolishedCount);

        unpolishedItems.squeeze();

        QMetaObject::invokeMethod(q_ptr, "_q_polishItems", Qt::QueuedConnection);

    }

}

void QGraphicsScenePrivate::_q_processDirtyItems()

{

    processDirtyItemsEmitted = false;

    if (updateAll) {

        Q_ASSERT(calledEmitUpdated);

        // No need for further processing (except resetting the dirty states).

        // The growingItemsBoundingRect is updated in _q_emitUpdated.

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

            resetDirtyItem(topLevelItems.at(i), /*recursive=*/true);

        return;

    }

    const bool wasPendingSceneUpdate = calledEmitUpdated;

    const QRectF oldGrowingItemsBoundingRect = growingItemsBoundingRect;

    // Process items recursively.

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

        processDirtyItemsRecursive(topLevelItems.at(i));

    dirtyGrowingItemsBoundingRect = false;

    if (!hasSceneRect && oldGrowingItemsBoundingRect != growingItemsBoundingRect)

        emit q_func()->sceneRectChanged(growingItemsBoundingRect);

    if (wasPendingSceneUpdate)

        return;

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

        views.at(i)->d_func()->processPendingUpdates();

    if (calledEmitUpdated) {

        // We did a compatibility QGraphicsScene::update in processDirtyItemsRecursive

        // and we cannot wait for the control to reach the eventloop before the

        // changed signal is emitted, so we emit it now.

        _q_emitUpdated();

    }

    // Immediately dispatch all pending update requests on the views.

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

        views.at(i)->d_func()->dispatchPendingUpdateRequests();

}

/*!

    \internal

*/

void QGraphicsScenePrivate::setScenePosItemEnabled(QGraphicsItem *item, bool enabled)

{

    QGraphicsItem *p = item->d_ptr->parent;

    while (p) {

        p->d_ptr->scenePosDescendants = enabled;

        p = p->d_ptr->parent;

    }

    if (!enabled && !scenePosDescendantsUpdatePending) {