source: trunk/src/qt3support/canvas/q3canvas.cpp@ 497

/****************************************************************************
**
** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
** Contact: Qt Software Information ([email protected])
**
** This file is part of the Qt3Support module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial Usage
** Licensees holding valid Qt Commercial licenses may use this file in
** accordance with the Qt Commercial License Agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and Nokia.
**
** 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.0, 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.
**
** If you are unsure which license is appropriate for your use, please
** contact the sales department at [email protected].
** $QT_END_LICENSE$
**
****************************************************************************/

#include "q3canvas.h"
#include "qapplication.h"
#include "qbitmap.h"
#include "qdesktopwidget.h"
#include "qimage.h"
#include "q3ptrdict.h"
#include "qpainter.h"
#include "q3polygonscanner.h"
#include "qtimer.h"
#include "q3tl.h"

#include <stdlib.h>

QT_BEGIN_NAMESPACE

using namespace Qt;

class Q3CanvasData {
public:
    Q3CanvasData() :
        itemDict(1013), animDict(503)
    {
    }

    Q3PtrList<Q3CanvasView> viewList;
    Q3PtrDict<void> itemDict;
    Q3PtrDict<void> animDict;
};

class Q3CanvasViewData {
public:
    Q3CanvasViewData() {}
#ifndef QT_NO_TRANSFORMATIONS
    QMatrix xform;
    QMatrix ixform;
#endif
    QRegion eraseRegion;
};

// clusterizer

class Q3CanvasClusterizer {
public:
    Q3CanvasClusterizer(int maxclusters);
    ~Q3CanvasClusterizer();

    void add(int x, int y); // 1x1 rectangle (point)
    void add(int x, int y, int w, int h);
    void add(const QRect& rect);

    void clear();
    int clusters() const { return count; }
    const QRect& operator[](int i) const;

private:
    QRect* cluster;
    int count;
    const int maxcl;
};

static
void include(QRect& r, const QRect& rect)
{
    if (rect.left()<r.left()) {
            r.setLeft(rect.left());
    }
    if (rect.right()>r.right()) {
            r.setRight(rect.right());
    }
    if (rect.top()<r.top()) {
            r.setTop(rect.top());
    }
    if (rect.bottom()>r.bottom()) {
            r.setBottom(rect.bottom());
    }
}

/*
A Q3CanvasClusterizer groups rectangles (QRects) into non-overlapping rectangles
by a merging heuristic.
*/
Q3CanvasClusterizer::Q3CanvasClusterizer(int maxclusters) :
    cluster(new QRect[maxclusters]),
    count(0),
    maxcl(maxclusters)
{ }

Q3CanvasClusterizer::~Q3CanvasClusterizer()
{
    delete [] cluster;
}

void Q3CanvasClusterizer::clear()
{
    count=0;
}

void Q3CanvasClusterizer::add(int x, int y)
{
    add(QRect(x,y,1,1));
}

void Q3CanvasClusterizer::add(int x, int y, int w, int h)
{
    add(QRect(x,y,w,h));
}

void Q3CanvasClusterizer::add(const QRect& rect)
{
    QRect biggerrect(rect.x()-1,rect.y()-1,rect.width()+2,rect.height()+2);

    //Q_ASSERT(rect.width()>0 && rect.height()>0);

    int cursor;

    for (cursor=0; cursor<count; cursor++) {
        if (cluster[cursor].contains(rect)) {
            // Wholly contained already.
            return;
        }
    }

    int lowestcost=9999999;
    int cheapest=-1;
    cursor = 0;
    while(cursor<count) {
        if (cluster[cursor].intersects(biggerrect)) {
            QRect larger=cluster[cursor];
            include(larger,rect);
            int cost = larger.width()*larger.height() -
                       cluster[cursor].width()*cluster[cursor].height();

            if (cost < lowestcost) {
                bool bad=false;
                for (int c=0; c<count && !bad; c++) {
                    bad=cluster[c].intersects(larger) && c!=cursor;
                }
                if (!bad) {
                    cheapest=cursor;
                    lowestcost=cost;
                }
            }
        }
        cursor++;
    }

    if (cheapest>=0) {
        include(cluster[cheapest],rect);
        return;
    }

    if (count < maxcl) {
        cluster[count++]=rect;
        return;
    }

    // Do cheapest of:
    //     add to closest cluster
    //     do cheapest cluster merge, add to new cluster

    lowestcost=9999999;
    cheapest=-1;
    cursor=0;
    while(cursor<count) {
        QRect larger=cluster[cursor];
        include(larger,rect);
        int cost=larger.width()*larger.height()
                - cluster[cursor].width()*cluster[cursor].height();
        if (cost < lowestcost) {
            bool bad=false;
            for (int c=0; c<count && !bad; c++) {
                bad=cluster[c].intersects(larger) && c!=cursor;
            }
            if (!bad) {
                cheapest=cursor;
                lowestcost=cost;
            }
        }
        cursor++;
    }

    // ###
    // could make an heuristic guess as to whether we need to bother
    // looking for a cheap merge.

    int cheapestmerge1 = -1;
    int cheapestmerge2 = -1;

    int merge1 = 0;
    while(merge1 < count) {
        int merge2=0;
        while(merge2 < count) {
            if(merge1!=merge2) {
                QRect larger=cluster[merge1];
                include(larger,cluster[merge2]);
                int cost=larger.width()*larger.height()
                    - cluster[merge1].width()*cluster[merge1].height()
                    - cluster[merge2].width()*cluster[merge2].height();
                if (cost < lowestcost) {
                    bool bad=false;
                    for (int c=0; c<count && !bad; c++) {
                        bad=cluster[c].intersects(larger) && c!=cursor;
                    }
                    if (!bad) {
                        cheapestmerge1=merge1;
                        cheapestmerge2=merge2;
                        lowestcost=cost;
                    }
                }
            }
            merge2++;
        }
        merge1++;
    }

    if (cheapestmerge1>=0) {
        include(cluster[cheapestmerge1],cluster[cheapestmerge2]);
        cluster[cheapestmerge2]=cluster[count--];
    } else {
        // if (!cheapest) debugRectangles(rect);
        include(cluster[cheapest],rect);
    }

    // NB: clusters do not intersect (or intersection will
    //     overwrite). This is a result of the above algorithm,
    //     given the assumption that (x,y) are ordered topleft
    //     to bottomright.

    // ###
    //
    // add explicit x/y ordering to that comment, move it to the top
    // and rephrase it as pre-/post-conditions.
}

const QRect& Q3CanvasClusterizer::operator[](int i) const
{
    return cluster[i];
}

// end of clusterizer

// there's no more device coordinate clipping done, so introduce these
// clip setting compat functions

static void qt_setclipregion(QPainter *p, const QRegion &r)
{
    QMatrix matrix = p->worldMatrix();
    p->setWorldMatrix(QMatrix());
    p->setClipRegion(r);
    p->setWorldMatrix(matrix);
}

static void qt_setcliprect(QPainter *p, const QRect &r)
{
    qt_setclipregion(p, QRegion(r));
}


class Q_COMPAT_EXPORT Q3CanvasItemPtr {
public:
    Q3CanvasItemPtr() : ptr(0) { }
    Q3CanvasItemPtr(Q3CanvasItem* p) : ptr(p) { }

    bool operator<=(const Q3CanvasItemPtr& that) const
    {
        // Order same-z objects by identity.
        if (that.ptr->z()==ptr->z())
            return that.ptr <= ptr;
        return that.ptr->z() <= ptr->z();
    }
    bool operator<(const Q3CanvasItemPtr& that) const
    {
        // Order same-z objects by identity.
        if (that.ptr->z()==ptr->z())
            return that.ptr < ptr;
        return that.ptr->z() < ptr->z();
    }
    bool operator>(const Q3CanvasItemPtr& that) const
    {
        // Order same-z objects by identity.
        if (that.ptr->z()==ptr->z())
            return that.ptr > ptr;
        return that.ptr->z() > ptr->z();
    }
    bool operator==(const Q3CanvasItemPtr& that) const
    {
            return that.ptr == ptr;
    }
    operator Q3CanvasItem*() const { return ptr; }

private:
    Q3CanvasItem* ptr;
};


/*!
    \class Q3CanvasItemList
    \compat
    \brief The Q3CanvasItemList class is a list of Q3CanvasItems.

    Q3CanvasItemList is a Q3ValueList of pointers to \l{Q3CanvasItem}s.
    This class is used by some methods in Q3Canvas that need to return
    a list of canvas items.

    The \l Q3ValueList documentation describes how to use this list.

    \sa QtCanvas, {Porting to Graphics View}
*/

/*!
  \internal
*/
void Q3CanvasItemList::sort()
{
    qHeapSort(*((Q3ValueList<Q3CanvasItemPtr>*)this));
}

/*!
  \internal
*/
void Q3CanvasItemList::drawUnique(QPainter& painter)
{
    Q3CanvasItem* prev=0;
    for (Iterator it=fromLast(); it!=end(); --it) {
        Q3CanvasItem *g=*it;
        if (g!=prev) {
            g->draw(painter);
            prev=g;
        }
    }
}

/*!
    Returns the concatenation of this list and list \a l.
*/
Q3CanvasItemList Q3CanvasItemList::operator+(const Q3CanvasItemList &l) const
{
    Q3CanvasItemList l2(*this);
    for(const_iterator it = l.begin(); it != l.end(); ++it)
       l2.append(*it);
    return l2;
}

class Q3CanvasChunk {
public:
    Q3CanvasChunk() : changed(true) { }
    // Other code assumes lists are not deleted. Assignment is also
    // done on ChunkRecs. So don't add that sort of thing here.

    void sort()
    {
        list.sort();
    }

    const Q3CanvasItemList* listPtr() const
    {
        return &list;
    }

    void add(Q3CanvasItem* item)
    {
        list.prepend(item);
        changed = true;
    }

    void remove(Q3CanvasItem* item)
    {
        list.remove(item);
        changed = true;
    }

    void change()
    {
        changed = true;
    }

    bool hasChanged() const
    {
        return changed;
    }

    bool takeChange()
    {
        bool y = changed;
        changed = false;
        return y;
    }

private:
    Q3CanvasItemList list;
    bool changed;
};


static int gcd(int a, int b)
{
    int r;
    while ((r = a%b)) {
        a=b;
        b=r;
    }
    return b;
}

static int scm(int a, int b)
{
    int g = gcd(a,b);
    return a/g*b;
}



/*!
    \class Q3Canvas
    \compat
    \brief The Q3Canvas class provides a 2D area that can contain Q3CanvasItem objects.

    The Q3Canvas class manages its 2D graphic area and all the canvas
    items the area contains. The canvas has no visual appearance of
    its own. Instead, it is displayed on screen using a Q3CanvasView.
    Multiple Q3CanvasView widgets may be associated with a canvas to
    provide multiple views of the same canvas.

    The canvas is optimized for large numbers of items, particularly
    where only a small percentage of the items change at any
    one time. If the entire display changes very frequently, you should
    consider using your own custom Q3ScrollView subclass.

    Qt provides a rich
    set of canvas item classes, e.g. Q3CanvasEllipse, Q3CanvasLine,
    Q3CanvasPolygon, Q3CanvasPolygonalItem, Q3CanvasRectangle, Q3CanvasSpline,
    Q3CanvasSprite and Q3CanvasText. You can subclass to create your own
    canvas items; Q3CanvasPolygonalItem is the most common base class used
    for this purpose.

    Items appear on the canvas after their \link Q3CanvasItem::show()
    show()\endlink function has been called (or \link
    Q3CanvasItem::setVisible() setVisible(true)\endlink), and \e after
    update() has been called. The canvas only shows items that are
    \link Q3CanvasItem::setVisible() visible\endlink, and then only if
    \l update() is called. (By default the canvas is white and so are
    canvas items, so if nothing appears try changing colors.)

    If you created the canvas without passing a width and height to
    the constructor you must also call resize().

    Although a canvas may appear to be similar to a widget with child
    widgets, there are several notable differences:

    \list
    \i Canvas items are usually much faster to manipulate and redraw than
    child widgets, with the speed advantage becoming especially great when
    there are \e many canvas items and non-rectangular items. In most
    situations canvas items are also a lot more memory efficient than child
    widgets.

    \i It's easy to detect overlapping items (collision detection).

    \i The canvas can be larger than a widget. A million-by-million canvas
    is perfectly possible. At such a size a widget might be very
    inefficient, and some window systems might not support it at all,
    whereas Q3Canvas scales well. Even with a billion pixels and a million
    items, finding a particular canvas item, detecting collisions, etc.,
    is still fast (though the memory consumption may be prohibitive
    at such extremes).

    \i Two or more Q3CanvasView objects can view the same canvas.

    \i An arbitrary transformation matrix can be set on each Q3CanvasView
    which makes it easy to zoom, rotate or shear the viewed canvas.

    \i Widgets provide a lot more functionality, such as input (QKeyEvent,
    QMouseEvent etc.) and layout management (QGridLayout etc.).

    \endlist

    A canvas consists of a background, a number of canvas items organized by
    x, y and z coordinates, and a foreground. A canvas item's z coordinate
    can be treated as a layer number -- canvas items with a higher z
    coordinate appear in front of canvas items with a lower z coordinate.

    The background is white by default, but can be set to a different color
    using setBackgroundColor(), or to a repeated pixmap using
    setBackgroundPixmap() or to a mosaic of smaller pixmaps using
    setTiles(). Individual tiles can be set with setTile(). There
    are corresponding get functions, e.g. backgroundColor() and
    backgroundPixmap().

    Note that Q3Canvas does not inherit from QWidget, even though it has some
    functions which provide the same functionality as those in QWidget. One
    of these is setBackgroundPixmap(); some others are resize(), size(),
    width() and height(). \l Q3CanvasView is the widget used to display a
    canvas on the screen.

    Canvas items are added to a canvas by constructing them and passing the
    canvas to the canvas item's constructor. An item can be moved to a
    different canvas using Q3CanvasItem::setCanvas().

    Canvas items are movable (and in the case of Q3CanvasSprites, animated)
    objects that inherit Q3CanvasItem. Each canvas item has a position on the
    canvas (x, y coordinates) and a height (z coordinate), all of which are
    held as floating-point numbers. Moving canvas items also have x and y
    velocities. It's possible for a canvas item to be outside the canvas
    (for example Q3CanvasItem::x() is greater than width()). When a canvas
    item is off the canvas, onCanvas() returns false and the canvas
    disregards the item. (Canvas items off the canvas do not slow down any
    of the common operations on the canvas.)

    Canvas items can be moved with Q3CanvasItem::move(). The advance()
    function moves all Q3CanvasItem::animated() canvas items and
    setAdvancePeriod() makes Q3Canvas move them automatically on a periodic
    basis. In the context of the Q3Canvas classes, to `animate' a canvas item
    is to set it in motion, i.e. using Q3CanvasItem::setVelocity(). Animation