q3canvas.cpp

qt-x11-opensource-src-4.1.4.tar.gz源码

/****************************************************************************
**
** Copyright (C) 1992-2006 Trolltech ASA. All rights reserved.
**
** This file is part of the Qt3Support module of the Qt Toolkit.
**
** This file may be used under the terms of the GNU General Public
** License version 2.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 GNU
** General Public Licensing requirements will be met:
** http://www.trolltech.com/products/qt/opensource.html
**
** If you are unsure which license is appropriate for your use, please
** review the following information:
** http://www.trolltech.com/products/qt/licensing.html or contact the
** sales department at [e-mail].
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
****************************************************************************/

#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>
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);

    //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)
{
    bool xfrm = p->hasWorldXForm();
    p->setWorldXForm(false);
    p->setClipRegion(r);
    p->setWorldXForm(xfrm);
}

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
*/

/*!
  \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 qcanvas.h
    \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.