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

**

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

** All rights reserved.

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

**

** This file is part of the Qt3Support 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$

**

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

#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().