summaryrefslogtreecommitdiffstats
path: root/src/gui/graphicsview
diff options
context:
space:
mode:
Diffstat (limited to 'src/gui/graphicsview')
-rw-r--r--src/gui/graphicsview/graphicsview.pri12
-rw-r--r--src/gui/graphicsview/qgraph_p.h240
-rw-r--r--src/gui/graphicsview/qgraphicsanchorlayout.cpp453
-rw-r--r--src/gui/graphicsview/qgraphicsanchorlayout.h141
-rw-r--r--src/gui/graphicsview/qgraphicsanchorlayout_p.cpp2104
-rw-r--r--src/gui/graphicsview/qgraphicsanchorlayout_p.h477
-rw-r--r--src/gui/graphicsview/qgraphicsitem.cpp44
-rw-r--r--src/gui/graphicsview/qgraphicsitem_p.h19
-rw-r--r--src/gui/graphicsview/qgraphicsscene.cpp17
-rw-r--r--src/gui/graphicsview/qgraphicsscene_p.h2
-rw-r--r--src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp4
-rw-r--r--src/gui/graphicsview/qgraphicstransform.cpp216
-rw-r--r--src/gui/graphicsview/qgraphicstransform.h26
-rw-r--r--src/gui/graphicsview/qsimplex_p.cpp371
-rw-r--r--src/gui/graphicsview/qsimplex_p.h125
15 files changed, 4093 insertions, 158 deletions
diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri
index 9d232e451..547d7ce7a 100644
--- a/src/gui/graphicsview/graphicsview.pri
+++ b/src/gui/graphicsview/graphicsview.pri
@@ -22,7 +22,12 @@ HEADERS += graphicsview/qgraphicsgridlayout.h \
graphicsview/qgraphicsview_p.h \
graphicsview/qgraphicswidget.h \
graphicsview/qgraphicswidget_p.h \
- graphicsview/qgridlayoutengine_p.h
+ graphicsview/qgridlayoutengine_p.h \
+ graphicsview/qgraph_p.h \
+ graphicsview/qsimplex_p.h \
+ graphicsview/qgraphicsanchorlayout_p.h \
+ graphicsview/qgraphicsanchorlayout.h
+
SOURCES += graphicsview/qgraphicsgridlayout.cpp \
graphicsview/qgraphicsitem.cpp \
graphicsview/qgraphicsitemanimation.cpp \
@@ -41,4 +46,7 @@ SOURCES += graphicsview/qgraphicsgridlayout.cpp \
graphicsview/qgraphicsview.cpp \
graphicsview/qgraphicswidget.cpp \
graphicsview/qgraphicswidget_p.cpp \
- graphicsview/qgridlayoutengine.cpp
+ graphicsview/qgridlayoutengine.cpp \
+ graphicsview/qsimplex_p.cpp \
+ graphicsview/qgraphicsanchorlayout_p.cpp \
+ graphicsview/qgraphicsanchorlayout.cpp
diff --git a/src/gui/graphicsview/qgraph_p.h b/src/gui/graphicsview/qgraph_p.h
new file mode 100644
index 000000000..7130003f3
--- /dev/null
+++ b/src/gui/graphicsview/qgraph_p.h
@@ -0,0 +1,240 @@
+#include <QtCore/QHash>
+#include <QtCore/QQueue>
+#include <QtCore/QString>
+#include <QtCore/QDebug>
+
+#include <float.h>
+
+QT_BEGIN_NAMESPACE
+
+template <typename Vertex, typename EdgeData>
+class Graph
+{
+public:
+ Graph() {}
+
+ class const_iterator {
+ public:
+ const_iterator(const Graph *graph, bool begin) : g(graph){
+ if (begin) {
+ row = g->m_graph.constBegin();
+ //test if the graph is empty
+ if (row != g->m_graph.constEnd())
+ {
+ column = (*row)->constBegin();
+ }
+ } else {
+ row = g->m_graph.constEnd();
+ }
+ }
+
+ inline Vertex *operator*() {
+ return column.key();
+ }
+
+ inline Vertex *from() const {
+ return row.key();
+ }
+
+ inline Vertex *to() const {
+ return column.key();
+ }
+
+ inline bool operator==(const const_iterator &o) const { return !(*this != o); }
+ inline bool operator!=(const const_iterator &o) const {
+ if (row == g->m_graph.end()) {
+ return row != o.row;
+ } else {
+ return row != o.row || column != o.column;
+ }
+ }
+ inline const_iterator& operator=(const const_iterator &o) const { row = o.row; column = o.column; return *this;}
+
+ // prefix
+ const_iterator &operator++() {
+ if (row != g->m_graph.constEnd()) {
+ ++column;
+ if (column == (*row)->constEnd()) {
+ ++row;
+ if (row != g->m_graph.constEnd()) {
+ column = (*row)->constBegin();
+ }
+ }
+ }
+ return *this;
+ }
+
+ private:
+ const Graph *g;
+ Q_TYPENAME QHash<Vertex *, QHash<Vertex *, EdgeData *> * >::const_iterator row;
+ Q_TYPENAME QHash<Vertex *, EdgeData *>::const_iterator column;
+ };
+
+ const_iterator constBegin() const {
+ return const_iterator(this,true);
+ }
+
+ const_iterator constEnd() const {
+ return const_iterator(this,false);
+ }
+
+ /*!
+ * \internal
+ *
+ * If there is an edge between \a first and \a second, it will return a structure
+ * containing the data associated with the edge, otherwise it will return 0.
+ *
+ */
+ EdgeData *edgeData(Vertex* first, Vertex* second) {
+ QHash<Vertex *, EdgeData *> *row = m_graph.value(first);
+ return row ? row->value(second) : 0;
+ }
+
+ void createEdge(Vertex *first, Vertex *second, EdgeData *data)
+ {
+ // Creates a bidirectional edge
+#if defined(QT_DEBUG) && 0
+ qDebug("Graph::createEdge(): %s",
+ qPrintable(QString::fromAscii("%1-%2")
+ .arg(first->toString()).arg(second->toString())));
+#endif
+ if (edgeData(first, second)) {
+#ifdef QT_DEBUG
+ qWarning(qPrintable(QString::fromAscii("%1-%2 already has an edge")
+ .arg(first->toString()).arg(second->toString())));
+#endif
+ }
+ createDirectedEdge(first, second, data);
+ createDirectedEdge(second, first, data);
+ }
+
+ void removeEdge(Vertex *first, Vertex *second)
+ {
+ // Removes a bidirectional edge
+#if defined(QT_DEBUG) && 0
+ qDebug("Graph::removeEdge(): %s",
+ qPrintable(QString::fromAscii("%1-%2")
+ .arg(first->toString()).arg(second->toString())));
+#endif
+ EdgeData *data = edgeData(first, second);
+ removeDirectedEdge(first, second);
+ removeDirectedEdge(second, first);
+ if (data) delete data;
+ }
+
+ EdgeData *takeEdge(Vertex* first, Vertex* second)
+ {
+#if defined(QT_DEBUG) && 0
+ qDebug("Graph::takeEdge(): %s",
+ qPrintable(QString::fromAscii("%1-%2")
+ .arg(first->toString()).arg(second->toString())));
+#endif
+ // Removes a bidirectional edge
+ EdgeData *data = edgeData(first, second);
+ if (data) {
+ removeDirectedEdge(first, second);
+ removeDirectedEdge(second, first);
+ }
+ return data;
+ }
+
+ QList<Vertex *> adjacentVertices(Vertex *vertex) const
+ {
+ QHash<Vertex *, EdgeData *> *row = m_graph.value(vertex);
+ QList<Vertex *> l;
+ if (row)
+ l = row->keys();
+ return l;
+ }
+
+ void setRootVertex(Vertex *vertex)
+ {
+ userVertex = vertex;
+ }
+
+ QSet<Vertex*> vertices() const {
+ QSet<Vertex *> setOfVertices;
+ for (const_iterator it = constBegin(); it != constEnd(); ++it) {
+ setOfVertices.insert(*it);
+ }
+ return setOfVertices;
+ }
+
+ QList<QPair<Vertex*, Vertex*> > connections() const {
+ QList<QPair<Vertex*, Vertex*> > conns;
+ for (const_iterator it = constBegin(); it != constEnd(); ++it) {
+ Vertex *from = it.from();
+ Vertex *to = it.to();
+ // do not return (from,to) *and* (to,from)
+ if (from < to) {
+ conns.append(qMakePair(from, to));
+ }
+ }
+ return conns;
+ }
+
+#if defined(QT_DEBUG)
+ QString serializeToDot() { // traversal
+ QString strVertices;
+ QString edges;
+
+ QSet<Vertex *> setOfVertices = vertices();
+ for (Q_TYPENAME QSet<Vertex*>::const_iterator it = setOfVertices.begin(); it != setOfVertices.end(); ++it) {
+ Vertex *v = *it;
+ QList<Vertex*> adjacents = adjacentVertices(v);
+ for (int i = 0; i < adjacents.count(); ++i) {
+ Vertex *v1 = adjacents.at(i);
+ EdgeData *data = edgeData(v, v1);
+ bool forward = data->from == v;
+ if (forward) {
+ edges += QString::fromAscii("%1->%2 [label=\"[%3,%4,%5]\" dir=both color=\"#000000:#a0a0a0\"] \n")
+ .arg(v->toString())
+ .arg(v1->toString())
+ .arg(data->minSize)
+ .arg(data->prefSize)
+ .arg(data->maxSize)
+ ;
+ }
+ }
+ strVertices += QString::fromAscii("%1 [label=\"%2\"]\n").arg(v->toString()).arg(v->toString());
+ }
+ return QString::fromAscii("%1\n%2\n").arg(strVertices).arg(edges);
+ }
+#endif
+
+ Vertex *rootVertex() const
+ {
+ return userVertex;
+ }
+
+protected:
+ void createDirectedEdge(Vertex *from, Vertex *to, EdgeData *data)
+ {
+ QHash<Vertex *, EdgeData *> *adjacentToFirst = m_graph.value(from);
+ if (!adjacentToFirst) {
+ adjacentToFirst = new QHash<Vertex *, EdgeData *>();
+ m_graph.insert(from, adjacentToFirst);
+ }
+ adjacentToFirst->insert(to, data);
+ }
+
+ void removeDirectedEdge(Vertex *from, Vertex *to)
+ {
+ QHash<Vertex *, EdgeData *> *adjacentToFirst = m_graph.value(from);
+ Q_ASSERT(adjacentToFirst);
+
+ adjacentToFirst->remove(to);
+ if (adjacentToFirst->isEmpty()) {
+ //nobody point to 'from' so we can remove it from the graph
+ m_graph.remove(from);
+ delete adjacentToFirst;
+ }
+ }
+
+private:
+ Vertex *userVertex;
+
+ QHash<Vertex *, QHash<Vertex *, EdgeData *> *> m_graph;
+};
+
+QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout.cpp b/src/gui/graphicsview/qgraphicsanchorlayout.cpp
new file mode 100644
index 000000000..fed0e5aed
--- /dev/null
+++ b/src/gui/graphicsview/qgraphicsanchorlayout.cpp
@@ -0,0 +1,453 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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 qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+/*!
+ \class QGraphicsAnchorLayout
+ \brief The QGraphicsAnchorLayout class provides a layout where one can anchor widgets
+ together in Graphics View.
+ \since 4.6
+ \ingroup appearance
+ \ingroup geomanagement
+ \ingroup graphicsview-api
+
+ The anchor layout is a layout where one can specify how widgets should be placed relative to
+ each other. The specification is called an anchor, and it is set up by calling anchor().
+ Anchors are always set up between edges of an item, where the "center" is also considered to
+ be an edge. Considering this example:
+ \code
+ QGraphicsAnchorLayout *l = new QGraphicsAnchorLayout;
+ QGraphicsWidget *a = new QGraphicsWidget;
+ QGraphicsWidget *b = new QGraphicsWidget;
+ l->anchor(a, Qt::AnchorRight, b, Qt::AnchorLeft);
+ \endcode
+
+ Here is the right edge of item A anchored to the left edge of item B, with the result that
+ item B will be placed to the right of item A, with a spacing between A and B. If the
+ spacing is negative, the items will overlap to some extent. Items that are anchored are
+ automatically added to the layout, and if items are removed, all their anchors will be
+ automatically removed
+
+ \section1 Size Hints and Size Policies in QGraphicsLinearLayout
+ QGraphicsLinearLayout respects each item's size hints and size policies. However it does
+ not respect stretch factors currently. This might change in the future, so please refrain
+ from using stretch factors in anchor layout to avoid any future regressions.
+
+ \section1 Spacing within QGraphicsAnchorLayout
+
+ Between the items, the layout can distribute some space. If the spacing has not been
+ explicitly specified, the actual amount of space will usually be 0, but if the first edge
+ is the "opposite" of the second edge (i.e. Right is anchored to Left or vice-versa), the
+ size of the anchor will be queried from the style through the pixelMetric
+ PM_LayoutHorizontalSpacing (or PM_LayoutVerticalSpacing for vertical anchors).
+*/
+
+#include "qgraphicsanchorlayout_p.h"
+
+QT_BEGIN_NAMESPACE
+
+QGraphicsAnchorLayout::QGraphicsAnchorLayout(QGraphicsLayoutItem *parent)
+ : QGraphicsLayout(*new QGraphicsAnchorLayoutPrivate(), parent)
+{
+ Q_D(QGraphicsAnchorLayout);
+ d->createLayoutEdges();
+}
+
+QGraphicsAnchorLayout::~QGraphicsAnchorLayout()
+{
+ Q_D(QGraphicsAnchorLayout);
+
+ for (int i = count() - 1; i >= 0; --i) {
+ QGraphicsLayoutItem *item = d->items.at(i);
+ removeAt(i);
+ if (item) {
+ if (item->ownedByLayout())
+ delete item;
+ }
+ }
+
+ d->removeCenterConstraints(this, QGraphicsAnchorLayoutPrivate::Horizontal);
+ d->removeCenterConstraints(this, QGraphicsAnchorLayoutPrivate::Vertical);
+ d->deleteLayoutEdges();
+
+ Q_ASSERT(d->itemCenterConstraints[0].isEmpty());
+ Q_ASSERT(d->itemCenterConstraints[1].isEmpty());
+ Q_ASSERT(d->items.isEmpty());
+ Q_ASSERT(d->m_vertexList.isEmpty());
+}
+
+/*!
+ * Creates an anchor between the edge \a firstEdge of item \a firstItem and the edge \a secondEdge
+ * of item \a secondItem. The magnitude of the anchor is picked up from the style. Anchors
+ * between a layout edge and an item edge will have a size of 0.
+ * If there is already an anchor between the edges, the the new anchor will replace the old one.
+ *
+ * \a firstItem and \a secondItem are automatically added to the layout if they are not part
+ * of the layout. This means that count() can increase with up to 2.
+ *
+ * The spacing an anchor will get depends on the type of anchor. For instance, anchors from the
+ * Right edge of one item to the Left edge of another (or vice versa) will use the default
+ * horizontal spacing. The same behaviour applies to Bottom to Top anchors, (but they will use
+ * the default vertical spacing). For all other anchor combinations, the spacing will be 0.
+ * All anchoring functions will follow this rule.
+ *
+ * The spacing can also be set manually by using setAnchorSpacing() method.
+ *
+ * \sa removeAnchor, addCornerAnchors, addLeftAndRightAnchors, addTopAndBottomAnchors, addAllAnchors
+ */
+void QGraphicsAnchorLayout::addAnchor(QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge)
+{
+ Q_D(QGraphicsAnchorLayout);
+ d->anchor(firstItem, firstEdge, secondItem, secondEdge);
+ invalidate();
+}
+
+/*!
+ * Creates two anchors between \a firstItem and \a secondItem, where one is for the horizontal
+ * edge and another one for the vertical edge that the corners \a firstCorner and \a
+ * secondCorner specifies.
+ * The magnitude of the anchors is picked up from the style.
+ *
+ * This is a convenience function, since anchoring corners can be expressed as anchoring two edges.
+ * For instance,
+ * \code
+ * layout->addAnchor(layout, Qt::AnchorTop, b, Qt::AnchorTop);
+ * layout->addAnchor(layout, Qt::AnchorLeft, b, Qt::AnchorLeft);
+ * \endcode
+ *
+ * has the same effect as
+ *
+ * \code
+ * layout->addCornerAnchors(layout, Qt::TopLeft, b, Qt::TopLeft);
+ * \endcode
+ *
+ * If there is already an anchor between the edge pairs, it will be replaced by the anchors that
+ * this function specifies.
+ *
+ * \a firstItem and \a secondItem are automatically added to the layout if they are not part
+ * of the layout. This means that count() can increase with up to 2.
+ */
+void QGraphicsAnchorLayout::addCornerAnchors(QGraphicsLayoutItem *firstItem,
+ Qt::Corner firstCorner,
+ QGraphicsLayoutItem *secondItem,
+ Qt::Corner secondCorner)
+{
+ Q_D(QGraphicsAnchorLayout);
+
+ // Horizontal anchor
+ Qt::AnchorPoint firstEdge = (firstCorner & 1 ? Qt::AnchorRight: Qt::AnchorLeft);
+ Qt::AnchorPoint secondEdge = (secondCorner & 1 ? Qt::AnchorRight: Qt::AnchorLeft);
+ d->anchor(firstItem, firstEdge, secondItem, secondEdge);
+
+ // Vertical anchor
+ firstEdge = (firstCorner & 2 ? Qt::AnchorBottom: Qt::AnchorTop);
+ secondEdge = (secondCorner & 2 ? Qt::AnchorBottom: Qt::AnchorTop);
+ d->anchor(firstItem, firstEdge, secondItem, secondEdge);
+
+ invalidate();
+}
+
+/*!
+ \fn QGraphicsAnchorLayout::addLeftAndRightAnchors(QGraphicsLayoutItem *firstEdge, QGraphicsLayoutItem *secondEdge)
+
+ This convenience function is equivalent to calling
+ \code
+ l->addAnchor(firstEdge, Qt::AnchorLeft, secondEdge, Qt::AnchorLeft);
+ l->addAnchor(firstEdge, Qt::AnchorRight, secondEdge, Qt::AnchorRight);
+ \endcode
+*/
+
+/*!
+ \fn QGraphicsAnchorLayout::addTopAndBottomAnchors(QGraphicsLayoutItem *firstEdge, QGraphicsLayoutItem *secondEdge)
+
+ This convenience function is equivalent to calling
+ \code
+ l->addAnchor(firstEdge, Qt::AnchorTop, secondEdge, Qt::AnchorTop);
+ l->addAnchor(firstEdge, Qt::AnchorBottom, secondEdge, Qt::AnchorBottom);
+ \endcode
+*/
+
+/*!
+ \fn QGraphicsAnchorLayout::addAllAnchors(QGraphicsLayoutItem *firstEdge, QGraphicsLayoutItem *secondEdge)
+
+ This convenience function is equivalent to calling
+ \code
+ l->addLeftAndRightAnchors(firstEdge, secondEdge);
+ l->addTopAndBottomAnchors(firstEdge, secondEdge);
+ \endcode
+*/
+
+/*!
+ Set the spacing between the anchor point defined by \a firstItem and \a firstEdge and
+ \a secondItem and \a secondEdge to be \a spacing.
+*/
+void QGraphicsAnchorLayout::setAnchorSpacing(const QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge,
+ qreal spacing)
+{
+ Q_D(QGraphicsAnchorLayout);
+
+ if (!d->setAnchorSize(firstItem, firstEdge, secondItem, secondEdge, &spacing)) {
+ qWarning("setAnchorSpacing: The anchor does not exist.");
+ }
+ invalidate();
+}
+
+/*!
+ Returns the spacing between the anchor point defined by \a firstItem and \a firstEdge and
+ \a secondItem and \a secondEdge. The anchor must exist.
+*/
+qreal QGraphicsAnchorLayout::anchorSpacing(const QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge) const
+{
+ Q_D(const QGraphicsAnchorLayout);
+ qreal size = 0;
+ if (!d->anchorSize(firstItem, firstEdge, secondItem, secondEdge, 0, &size)) {
+ qWarning("anchorSpacing: The anchor does not exist.");
+ }
+ return size;
+}
+
+/*!
+ Resets the spacing between the anchor point defined by \a firstItem and \a firstEdge and
+ \a secondItem and \a secondEdge to be the default spacing. Depending on the anchor type, the
+ default spacing is either 0 or a value returned from the style.
+
+ \sa setAnchorSpacing, anchorSpacing, addAnchor
+*/
+void QGraphicsAnchorLayout::unsetAnchorSpacing(const QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge)
+{
+ Q_D(QGraphicsAnchorLayout);
+
+ if (!d->setAnchorSize(firstItem, firstEdge, secondItem, secondEdge, 0)) {
+ qWarning("unsetAnchorSpacing: The anchor does not exist.");
+ }
+ invalidate();
+}
+
+/*!
+ Removes the anchor between the edge \a firstEdge of item \a firstItem and the edge \a secondEdge
+ of item \a secondItem. If such an anchor does not exist, the layout will be left unchanged.
+*/
+void QGraphicsAnchorLayout::removeAnchor(QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge)
+{
+ Q_D(QGraphicsAnchorLayout);
+ if ((firstItem == 0) || (secondItem == 0)) {
+ qWarning("QGraphicsAnchorLayout::removeAnchor: "
+ "Cannot remove anchor between NULL items");
+ return;
+ }
+
+ if (firstItem == secondItem) {
+ qWarning("QGraphicsAnchorLayout::removeAnchor: "
+ "Cannot remove anchor from the item to itself");
+ return;
+ }
+
+ if (d->edgeOrientation(secondEdge) != d->edgeOrientation(firstEdge)) {
+ qWarning("QGraphicsAnchorLayout::removeAnchor: "
+ "Cannot remove anchor from edges of different orientations");
+ return;
+ }
+
+ d->removeAnchor(firstItem, firstEdge, secondItem, secondEdge);
+ invalidate();
+}
+
+/*!
+ Sets the default horizontal spacing for the anchor layout to \a spacing.
+
+ \sa horizontalSpacing, setVerticalSpacing, setSpacing
+*/
+void QGraphicsAnchorLayout::setHorizontalSpacing(qreal spacing)
+{
+ Q_D(QGraphicsAnchorLayout);
+ d->spacings[0] = spacing;
+ invalidate();
+}
+
+/*!
+ Sets the default vertical spacing for the anchor layout to \a spacing.
+
+ \sa verticalSpacing, setHorizontalSpacing, setSpacing
+*/
+void QGraphicsAnchorLayout::setVerticalSpacing(qreal spacing)
+{
+ Q_D(QGraphicsAnchorLayout);
+ d->spacings[1] = spacing;
+ invalidate();
+}
+
+/*!
+ Sets the default horizontal and the default vertical spacing for the anchor layout to \a spacing.
+
+ If an item is anchored with no spacing associated with the anchor, it will use the default
+ spacing.
+ \sa setHorizontalSpacing, setVerticalSpacing
+*/
+void QGraphicsAnchorLayout::setSpacing(qreal spacing)
+{
+ Q_D(QGraphicsAnchorLayout);
+ d->spacings[0] = d->spacings[1] = spacing;
+ invalidate();
+}
+
+/*!
+ Returns the default horizontal spacing for the anchor layout.
+
+ \sa verticalSpacing, setHorizontalSpacing
+*/
+qreal QGraphicsAnchorLayout::horizontalSpacing() const
+{
+ Q_D(const QGraphicsAnchorLayout);
+ return d->effectiveSpacing(QGraphicsAnchorLayoutPrivate::Horizontal);
+}
+
+/*!
+ Returns the default vertical spacing for the anchor layout.
+
+ \sa horizontalSpacing, setVerticalSpacing
+*/
+qreal QGraphicsAnchorLayout::verticalSpacing() const
+{
+ Q_D(const QGraphicsAnchorLayout);
+ return d->effectiveSpacing(QGraphicsAnchorLayoutPrivate::Vertical);
+}
+
+/*!
+ \reimp
+*/
+void QGraphicsAnchorLayout::setGeometry(const QRectF &geom)
+{
+ Q_D(QGraphicsAnchorLayout);
+
+ QGraphicsLayout::setGeometry(geom);
+ d->calculateVertexPositions(QGraphicsAnchorLayoutPrivate::Horizontal);
+ d->calculateVertexPositions(QGraphicsAnchorLayoutPrivate::Vertical);
+ d->setItemsGeometries();
+}
+
+/*!
+ Removing an item will also remove any of the anchors associated with it.
+*/
+void QGraphicsAnchorLayout::removeAt(int index)
+{
+ Q_D(QGraphicsAnchorLayout);
+ QGraphicsLayoutItem *item = d->items.value(index);
+
+ if (!item)
+ return;
+
+ // Removing an item affects both horizontal and vertical graphs
+ d->restoreSimplifiedGraph(QGraphicsAnchorLayoutPrivate::Horizontal);
+ d->restoreSimplifiedGraph(QGraphicsAnchorLayoutPrivate::Vertical);
+
+ d->removeCenterConstraints(item, QGraphicsAnchorLayoutPrivate::Horizontal);
+ d->removeCenterConstraints(item, QGraphicsAnchorLayoutPrivate::Vertical);
+ d->removeAnchors(item);
+ d->items.remove(index);
+
+ item->setParentLayoutItem(0);
+ invalidate();
+}
+
+/*!
+ \reimp
+*/
+int QGraphicsAnchorLayout::count() const
+{
+ Q_D(const QGraphicsAnchorLayout);
+ return d->items.size();
+}
+
+/*!
+ \reimp
+*/
+QGraphicsLayoutItem *QGraphicsAnchorLayout::itemAt(int index) const
+{
+ Q_D(const QGraphicsAnchorLayout);
+ return d->items.value(index);
+}
+
+/*!
+ \reimp
+*/
+void QGraphicsAnchorLayout::invalidate()
+{
+ Q_D(QGraphicsAnchorLayout);
+ QGraphicsLayout::invalidate();
+ d->calculateGraphCacheDirty = 1;
+}
+
+/*!
+ \reimp
+*/
+QSizeF QGraphicsAnchorLayout::sizeHint(Qt::SizeHint which, const QSizeF &constraint) const
+{
+ Q_UNUSED(which);
+ Q_UNUSED(constraint);
+ Q_D(const QGraphicsAnchorLayout);
+
+ // Some setup calculations are delayed until the information is
+ // actually needed, avoiding unnecessary recalculations when
+ // adding multiple anchors.
+
+ // sizeHint() / effectiveSizeHint() already have a cache
+ // mechanism, using invalidate() to force recalculation. However
+ // sizeHint() is called three times after invalidation (for max,
+ // min and pref), but we just need do our setup once.
+
+ const_cast<QGraphicsAnchorLayoutPrivate *>(d)->calculateGraphs();
+
+ // ### apply constraint!
+ QSizeF engineSizeHint(
+ d->sizeHints[QGraphicsAnchorLayoutPrivate::Horizontal][which],
+ d->sizeHints[QGraphicsAnchorLayoutPrivate::Vertical][which]);
+
+ qreal left, top, right, bottom;
+ getContentsMargins(&left, &top, &right, &bottom);
+
+ return engineSizeHint + QSizeF(left + right, top + bottom);
+}
+
+QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout.h b/src/gui/graphicsview/qgraphicsanchorlayout.h
new file mode 100644
index 000000000..3de9ae5ac
--- /dev/null
+++ b/src/gui/graphicsview/qgraphicsanchorlayout.h
@@ -0,0 +1,141 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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 qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QGRAPHICSANCHORLAYOUT_H
+#define QGRAPHICSANCHORLAYOUT_H
+
+#include <QtGui/qgraphicsitem.h>
+#include <QtGui/qgraphicslayout.h>
+
+
+QT_BEGIN_HEADER
+
+QT_BEGIN_NAMESPACE
+
+QT_MODULE(Gui)
+
+#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
+
+class QGraphicsAnchorLayoutPrivate;
+
+class Q_GUI_EXPORT QGraphicsAnchorLayout : public QGraphicsLayout
+{
+public:
+ QGraphicsAnchorLayout(QGraphicsLayoutItem *parent = 0);
+ virtual ~QGraphicsAnchorLayout();
+
+ void addAnchor(QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge);
+
+ void addCornerAnchors(QGraphicsLayoutItem *firstItem, Qt::Corner firstCorner,
+ QGraphicsLayoutItem *secondItem, Qt::Corner secondCorner);
+
+ inline void addLeftAndRightAnchors(QGraphicsLayoutItem *firstItem,
+ QGraphicsLayoutItem *secondItem);
+
+ inline void addTopAndBottomAnchors(QGraphicsLayoutItem *firstItem,
+ QGraphicsLayoutItem *secondItem);
+
+ inline void addAllAnchors(QGraphicsLayoutItem *firstItem,
+ QGraphicsLayoutItem *secondItem);
+
+ void setAnchorSpacing(const QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge,
+ qreal spacing);
+
+ qreal anchorSpacing(const QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge) const;
+
+ void unsetAnchorSpacing(const QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge);
+
+ void removeAnchor(QGraphicsLayoutItem *firstItem, Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem, Qt::AnchorPoint secondEdge);
+
+ void setHorizontalSpacing(qreal spacing);
+ void setVerticalSpacing(qreal spacing);
+ void setSpacing(qreal spacing);
+ qreal horizontalSpacing() const;
+ qreal verticalSpacing() const;
+
+ void removeAt(int index);
+ void setGeometry(const QRectF &rect);
+ int count() const;
+ QGraphicsLayoutItem *itemAt(int index) const;
+
+ void invalidate();
+protected:
+ QSizeF sizeHint(Qt::SizeHint which, const QSizeF &constraint = QSizeF()) const;
+
+private:
+ Q_DISABLE_COPY(QGraphicsAnchorLayout)
+ Q_DECLARE_PRIVATE(QGraphicsAnchorLayout)
+};
+
+
+void QGraphicsAnchorLayout::addLeftAndRightAnchors(QGraphicsLayoutItem *firstItem,
+ QGraphicsLayoutItem *secondItem)
+{
+ addAnchor(secondItem, Qt::AnchorLeft, firstItem, Qt::AnchorLeft);
+ addAnchor(firstItem, Qt::AnchorRight, secondItem, Qt::AnchorRight);
+}
+
+void QGraphicsAnchorLayout::addTopAndBottomAnchors(QGraphicsLayoutItem *firstItem,
+ QGraphicsLayoutItem *secondItem)
+{
+ addAnchor(secondItem, Qt::AnchorTop, firstItem, Qt::AnchorTop);
+ addAnchor(firstItem, Qt::AnchorBottom, secondItem, Qt::AnchorBottom);
+}
+
+void QGraphicsAnchorLayout::addAllAnchors(QGraphicsLayoutItem *firstItem,
+ QGraphicsLayoutItem *secondItem)
+{
+ addLeftAndRightAnchors(firstItem, secondItem);
+ addTopAndBottomAnchors(firstItem, secondItem);
+}
+
+#endif
+
+QT_END_NAMESPACE
+
+QT_END_HEADER
+
+#endif
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
new file mode 100644
index 000000000..c137de3df
--- /dev/null
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
@@ -0,0 +1,2104 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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 qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QtGui/qwidget.h>
+#include <QtCore/qlinkedlist.h>
+#include <QtCore/qstack.h>
+
+#ifdef QT_DEBUG
+#include <QtCore/qfile.h>
+#endif
+
+#include "qgraphicsanchorlayout_p.h"
+
+QT_BEGIN_NAMESPACE
+
+void AnchorData::refreshSizeHints(qreal effectiveSpacing)
+{
+ if (!isLayoutAnchor && from->m_item == to->m_item) {
+ bool hasCenter = false;
+ QGraphicsLayoutItem *item = from->m_item;
+
+ if (QGraphicsAnchorLayoutPrivate::edgeOrientation(from->m_edge)
+ == QGraphicsAnchorLayoutPrivate::Horizontal) {
+ minSize = item->minimumWidth();
+ prefSize = item->preferredWidth();
+ maxSize = item->maximumWidth();
+ hasCenter = (from->m_edge == Qt::AnchorHorizontalCenter
+ || to->m_edge == Qt::AnchorHorizontalCenter);
+ } else {
+ minSize = item->minimumHeight();
+ prefSize = item->preferredHeight();
+ maxSize = item->maximumHeight();
+ hasCenter = (from->m_edge == Qt::AnchorVerticalCenter
+ || to->m_edge == Qt::AnchorVerticalCenter);
+ }
+
+ if (hasCenter) {
+ minSize /= 2;
+ prefSize /= 2;
+ maxSize /= 2;
+ }
+
+ // Set the anchor effective sizes to preferred.
+ //
+ // Note: The idea here is that all items should remain at their
+ // preferred size unless where that's impossible. In cases where
+ // the item is subject to restrictions (anchored to the layout
+ // edges, for instance), the simplex solver will be run to
+ // recalculate and override the values we set here.
+ sizeAtMinimum = prefSize;
+ sizeAtPreferred = prefSize;
+ sizeAtMaximum = prefSize;
+
+ } else if (!hasSize) {
+ // Anchor has no size defined, use given default information
+ minSize = effectiveSpacing;
+ prefSize = effectiveSpacing;
+ maxSize = effectiveSpacing;
+
+ sizeAtMinimum = prefSize;
+ sizeAtPreferred = prefSize;
+ sizeAtMaximum = prefSize;
+ }
+}
+
+void ParallelAnchorData::updateChildrenSizes()
+{
+ firstEdge->sizeAtMinimum = secondEdge->sizeAtMinimum = sizeAtMinimum;
+ firstEdge->sizeAtPreferred = secondEdge->sizeAtPreferred = sizeAtPreferred;
+ firstEdge->sizeAtMaximum = secondEdge->sizeAtMaximum = sizeAtMaximum;
+
+ firstEdge->updateChildrenSizes();
+ secondEdge->updateChildrenSizes();
+}
+
+void ParallelAnchorData::refreshSizeHints(qreal effectiveSpacing)
+{
+ // First refresh children information
+ firstEdge->refreshSizeHints(effectiveSpacing);
+ secondEdge->refreshSizeHints(effectiveSpacing);
+
+ // ### should we warn if the parallel connection is invalid?
+ // e.g. 1-2-3 with 10-20-30, the minimum of the latter is
+ // bigger than the maximum of the former.
+
+ minSize = qMax(firstEdge->minSize, secondEdge->minSize);
+ maxSize = qMin(firstEdge->maxSize, secondEdge->maxSize);
+
+ prefSize = qMax(firstEdge->prefSize, secondEdge->prefSize);
+ prefSize = qMin(prefSize, maxSize);
+
+ // See comment in AnchorData::refreshSizeHints() about sizeAt* values
+ sizeAtMinimum = prefSize;
+ sizeAtPreferred = prefSize;
+ sizeAtMaximum = prefSize;
+}
+
+/*!
+ \internal
+ returns the factor in the interval [-1, 1].
+ -1 is at Minimum
+ 0 is at Preferred
+ 1 is at Maximum
+*/
+static qreal getFactor(qreal value, qreal min, qreal pref, qreal max)
+{
+ // ### Maybe remove some of the assertions? (since outside is asserting us)
+ Q_ASSERT(value > min || qFuzzyCompare(value, min));
+ Q_ASSERT(value < max || qFuzzyCompare(value, max));
+
+ if (qFuzzyCompare(value, min)) {
+ return -1.0;
+ } else if (qFuzzyCompare(value, pref)) {
+ return 0.0;
+ } else if (qFuzzyCompare(value, max)) {
+ return 1.0;
+ } else if (value < pref) {
+ // Since value < pref and value != pref and min <= value,
+ // we can assert that min < pref.
+ Q_ASSERT(min < pref);
+ return (value - min) / (pref - min) - 1;
+ } else {
+ // Since value > pref and value != pref and max >= value,
+ // we can assert that max > pref.
+ Q_ASSERT(max > pref);
+ return (value - pref) / (max - pref);
+ }
+}
+
+void SequentialAnchorData::updateChildrenSizes()
+{
+ // ### REMOVE ME
+ // ### check whether we are guarantee to get those or we need to warn stuff at this
+ // point.
+ Q_ASSERT(sizeAtMinimum > minSize || qFuzzyCompare(sizeAtMinimum, minSize));
+ Q_ASSERT(sizeAtMinimum < maxSize || qFuzzyCompare(sizeAtMinimum, maxSize));
+ Q_ASSERT(sizeAtPreferred > minSize || qFuzzyCompare(sizeAtPreferred, minSize));
+ Q_ASSERT(sizeAtPreferred < maxSize || qFuzzyCompare(sizeAtPreferred, maxSize));
+ Q_ASSERT(sizeAtMaximum > minSize || qFuzzyCompare(sizeAtMaximum, minSize));
+ Q_ASSERT(sizeAtMaximum < maxSize || qFuzzyCompare(sizeAtMaximum, maxSize));
+
+ // Band here refers if the value is in the Minimum To Preferred
+ // band (the lower band) or the Preferred To Maximum (the upper band).
+
+ qreal minFactor = getFactor(sizeAtMinimum, minSize, prefSize, maxSize);
+ qreal prefFactor = getFactor(sizeAtPreferred, minSize, prefSize, maxSize);
+ qreal maxFactor = getFactor(sizeAtMaximum, minSize, prefSize, maxSize);
+
+ for (int i = 0; i < m_edges.count(); ++i) {
+ AnchorData *e = m_edges.at(i);
+
+ qreal bandSize = minFactor > 0 ? e->maxSize - e->prefSize : e->prefSize - e->minSize;
+ e->sizeAtMinimum = e->prefSize + bandSize * minFactor;
+
+ bandSize = prefFactor > 0 ? e->maxSize - e->prefSize : e->prefSize - e->minSize;
+ e->sizeAtPreferred = e->prefSize + bandSize * prefFactor;
+
+ bandSize = maxFactor > 0 ? e->maxSize - e->prefSize : e->prefSize - e->minSize;
+ e->sizeAtMaximum = e->prefSize + bandSize * maxFactor;
+
+ e->updateChildrenSizes();
+ }
+}
+
+void SequentialAnchorData::refreshSizeHints(qreal effectiveSpacing)
+{
+ minSize = 0;
+ prefSize = 0;
+ maxSize = 0;
+
+ for (int i = 0; i < m_edges.count(); ++i) {
+ AnchorData *edge = m_edges.at(i);
+
+ // First refresh children information
+ edge->refreshSizeHints(effectiveSpacing);
+
+ minSize += edge->minSize;
+ prefSize += edge->prefSize;
+ maxSize += edge->maxSize;
+ }
+
+ // See comment in AnchorData::refreshSizeHints() about sizeAt* values
+ sizeAtMinimum = prefSize;
+ sizeAtPreferred = prefSize;
+ sizeAtMaximum = prefSize;
+}
+
+#ifdef QT_DEBUG
+void AnchorData::dump(int indent) {
+ if (type == Parallel) {
+ qDebug("%*s type: parallel:", indent, "");
+ ParallelAnchorData *p = static_cast<ParallelAnchorData *>(this);
+ p->firstEdge->dump(indent+2);
+ p->secondEdge->dump(indent+2);
+ } else if (type == Sequential) {
+ SequentialAnchorData *s = static_cast<SequentialAnchorData *>(this);
+ int kids = s->m_edges.count();
+ qDebug("%*s type: sequential(%d):", indent, "", kids);
+ for (int i = 0; i < kids; ++i) {
+ s->m_edges.at(i)->dump(indent+2);
+ }
+ } else {
+ qDebug("%*s type: Normal:", indent, "");
+ }
+}
+
+#endif
+
+QSimplexConstraint *GraphPath::constraint(const GraphPath &path) const
+{
+ // Calculate
+ QSet<AnchorData *> cPositives;
+ QSet<AnchorData *> cNegatives;
+ QSet<AnchorData *> intersection;
+
+ cPositives = positives + path.negatives;
+ cNegatives = negatives + path.positives;
+
+ intersection = cPositives & cNegatives;
+
+ cPositives -= intersection;
+ cNegatives -= intersection;
+
+ // Fill
+ QSimplexConstraint *c = new QSimplexConstraint;
+ QSet<AnchorData *>::iterator i;
+ for (i = cPositives.begin(); i != cPositives.end(); ++i)
+ c->variables.insert(*i, 1.0);
+
+ for (i = cNegatives.begin(); i != cNegatives.end(); ++i)
+ c->variables.insert(*i, -1.0);
+
+ return c;
+}
+
+#ifdef QT_DEBUG
+QString GraphPath::toString() const
+{
+ QString string(QLatin1String("Path: "));
+ foreach(AnchorData *edge, positives)
+ string += QString::fromAscii(" (+++) %1").arg(edge->toString());
+
+ foreach(AnchorData *edge, negatives)
+ string += QString::fromAscii(" (---) %1").arg(edge->toString());
+
+ return string;
+}
+#endif
+
+QGraphicsAnchorLayoutPrivate::QGraphicsAnchorLayoutPrivate()
+ : calculateGraphCacheDirty(1)
+{
+ for (int i = 0; i < NOrientations; ++i) {
+ spacings[i] = -1;
+ graphSimplified[i] = false;
+ }
+}
+
+Qt::AnchorPoint QGraphicsAnchorLayoutPrivate::oppositeEdge(Qt::AnchorPoint edge)
+{
+ switch (edge) {
+ case Qt::AnchorLeft:
+ edge = Qt::AnchorRight;
+ break;
+ case Qt::AnchorRight:
+ edge = Qt::AnchorLeft;
+ break;
+ case Qt::AnchorTop:
+ edge = Qt::AnchorBottom;
+ break;
+ case Qt::AnchorBottom:
+ edge = Qt::AnchorTop;
+ break;
+ default:
+ break;
+ }
+ return edge;
+}
+
+
+/*!
+ * \internal
+ *
+ * helper function in order to avoid overflowing anchor sizes
+ * the returned size will never be larger than FLT_MAX
+ *
+ */
+inline static qreal checkAdd(qreal a, qreal b)
+{
+ if (FLT_MAX - b < a)
+ return FLT_MAX;
+ return a + b;
+}
+
+/*!
+ * \internal
+ *
+ * Takes the sequence of vertices described by (\a before, \a vertices, \a after) and replaces
+ * all anchors connected to the vertices in \a vertices with one simplified anchor between
+ * \a before and \a after. The simplified anchor will be a placeholder for all the previous
+ * anchors between \a before and \a after, and can be restored back to the anchors it is a
+ * placeholder for.
+ */
+static bool simplifySequentialChunk(Graph<AnchorVertex, AnchorData> *graph,
+ AnchorVertex *before,
+ const QVector<AnchorVertex*> &vertices,
+ AnchorVertex *after)
+{
+ int i;
+#if defined(QT_DEBUG) && 0
+ QString strVertices;
+ for (i = 0; i < vertices.count(); ++i)
+ strVertices += QString::fromAscii("%1 - ").arg(vertices.at(i)->toString());
+ QString strPath = QString::fromAscii("%1 - %2%3").arg(before->toString(), strVertices, after->toString());
+ qDebug("simplifying [%s] to [%s - %s]", qPrintable(strPath), qPrintable(before->toString()), qPrintable(after->toString()));
+#endif
+
+ qreal min = 0;
+ qreal pref = 0;
+ qreal max = 0;
+
+ SequentialAnchorData *sequence = new SequentialAnchorData;
+ AnchorVertex *prev = before;
+ AnchorData *data;
+ for (i = 0; i <= vertices.count(); ++i) {
+ AnchorVertex *next = (i < vertices.count()) ? vertices.at(i) : after;
+ data = graph->takeEdge(prev, next);
+ min += data->minSize;
+ pref += data->prefSize;
+ max = checkAdd(max, data->maxSize);
+ sequence->m_edges.append(data);
+ prev = next;
+ }
+
+ // insert new
+ sequence->minSize = min;
+ sequence->prefSize = pref;
+ sequence->maxSize = max;
+
+ // Unless these values are overhidden by the simplex solver later-on,
+ // anchors will keep their own preferred size.
+ sequence->sizeAtMinimum = pref;
+ sequence->sizeAtPreferred = pref;
+ sequence->sizeAtMaximum = pref;
+
+ sequence->setVertices(vertices);
+
+ sequence->from = before;
+ sequence->to = after;
+
+ // data here is the last edge in the sequence
+ // ### this seems to be here for supporting reverse order sequences,
+ // but doesnt seem to be used right now
+ if (data->from != vertices.last())
+ qSwap(sequence->from, sequence->to);
+
+ // Note that since layout 'edges' can't be simplified away from
+ // the graph, it's safe to assume that if there's a layout
+ // 'edge', it'll be in the boundaries of the sequence.
+ sequence->isLayoutAnchor = (sequence->m_edges.first()->isLayoutAnchor
+ || sequence->m_edges.last()->isLayoutAnchor);
+
+ AnchorData *newAnchor = sequence;
+ if (AnchorData *oldAnchor = graph->takeEdge(before, after)) {
+ newAnchor = new ParallelAnchorData(oldAnchor, sequence);
+
+ newAnchor->isLayoutAnchor = (oldAnchor->isLayoutAnchor
+ || sequence->isLayoutAnchor);
+
+ min = qMax(oldAnchor->minSize, sequence->minSize);
+ max = qMin(oldAnchor->maxSize, sequence->maxSize);
+
+ pref = qMax(oldAnchor->prefSize, sequence->prefSize);
+ pref = qMin(pref, max);
+
+ newAnchor->minSize = min;
+ newAnchor->prefSize = pref;
+ newAnchor->maxSize = max;
+
+ // Same as above, by default, keep preferred size.
+ newAnchor->sizeAtMinimum = pref;
+ newAnchor->sizeAtPreferred = pref;
+ newAnchor->sizeAtMaximum = pref;
+ }
+ graph->createEdge(before, after, newAnchor);
+
+ // True if we created a parallel anchor
+ return newAnchor != sequence;
+}
+
+/*!
+ \internal
+
+ The purpose of this function is to simplify the graph.
+ Simplification serves two purposes:
+ 1. Reduce the number of edges in the graph, (thus the number of variables to the equation
+ solver is reduced, and the solver performs better).
+ 2. Be able to do distribution of sequences of edges more intelligently (esp. with sequential
+ anchors)
+
+ It is essential that it must be possible to restore simplified anchors back to their "original"
+ form. This is done by restoreSimplifiedAnchor().
+
+ There are two types of simplification that can be done:
+ 1. Sequential simplification
+ Sequential simplification means that all sequences of anchors will be merged into one single
+ anchor. Only anhcors that points in the same direction will be merged.
+ 2. Parallel simplification
+ If a simplified sequential anchor is about to be inserted between two vertices in the graph
+ and there already exist an anchor between those two vertices, a parallel anchor will be
+ created that serves as a placeholder for the sequential anchor and the anchor that was
+ already between the two vertices.
+
+ The process of simplification can be described as:
+
+ 1. Simplify all sequences of anchors into one anchor.
+ If no further simplification was done, go to (3)
+ - If there already exist an anchor where the sequential anchor is supposed to be inserted,
+ take that anchor out of the graph
+ - Then create a parallel anchor that holds the sequential anchor and the anchor just taken
+ out of the graph.
+ 2. Go to (1)
+ 3. Done
+
+
+ * Gathering sequential anchors *
+ The algorithm walks the graph in depth-first order, and only collects vertices that has two
+ edges connected to it. If the vertex does not have two edges or if it is a layout edge,
+ it will take all the previously collected vertices and try to create a simplified sequential
+ anchor representing all the previously collected vertices.
+ Once the simplified anchor is inserted, the collected list is cleared in order to find the next
+ sequence to simplify.
+ Note that there are some catches to this that are not covered by the above explanation.
+*/
+void QGraphicsAnchorLayoutPrivate::simplifyGraph(Orientation orientation)
+{
+ static bool noSimplification = !qgetenv("QT_ANCHORLAYOUT_NO_SIMPLIFICATION").isEmpty();
+ if (noSimplification)
+ return;
+
+ if (graphSimplified[orientation])
+ return;
+ graphSimplified[orientation] = true;
+
+#if 0
+ qDebug("Simplifying Graph for %s",
+ orientation == Horizontal ? "Horizontal" : "Vertical");
+#endif
+
+ AnchorVertex *rootVertex = graph[orientation].rootVertex();
+
+ if (!rootVertex)
+ return;
+
+ bool dirty;
+ do {
+ dirty = simplifyGraphIteration(orientation);
+ } while (dirty);
+}
+
+bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutPrivate::Orientation orientation)
+{
+ Q_Q(QGraphicsAnchorLayout);
+ Graph<AnchorVertex, AnchorData> &g = graph[orientation];
+ AnchorVertex *v = g.rootVertex();
+
+ QSet<AnchorVertex *> visited;
+ QStack<AnchorVertex *> stack;
+ stack.push(v);
+ QVector<AnchorVertex*> candidates;
+
+ const Qt::AnchorPoint centerEdge = pickEdge(Qt::AnchorHorizontalCenter, orientation);
+ const Qt::AnchorPoint layoutEdge = oppositeEdge(v->m_edge);
+
+ bool dirty = false;
+
+ // walk depth-first.
+ while (!stack.isEmpty()) {
+ v = stack.pop();
+ QList<AnchorVertex *> vertices = g.adjacentVertices(v);
+ const int count = vertices.count();
+ bool endOfSequence = (v->m_item == q && v->m_edge == layoutEdge) || count != 2;
+ if (count == 2 && v->m_item != q) {
+ candidates.append(v);
+ if (visited.contains(vertices.first()) && visited.contains(vertices.last())) {
+ // in case of a cycle
+ endOfSequence = true;
+ }
+ }
+ if (endOfSequence && candidates.count() >= 2) {
+ int i;
+ AnchorVertex *afterSequence= 0;
+ QList<AnchorVertex *> adjacentOfSecondLastVertex = g.adjacentVertices(candidates.last());
+ Q_ASSERT(adjacentOfSecondLastVertex.count() == 2);
+ if (adjacentOfSecondLastVertex.first() == candidates.at(candidates.count() - 2))
+ afterSequence = adjacentOfSecondLastVertex.last();
+ else
+ afterSequence = adjacentOfSecondLastVertex.first();
+
+ AnchorVertex *beforeSequence = 0;
+ QList<AnchorVertex *> adjacentOfSecondVertex = g.adjacentVertices(candidates.first());
+ Q_ASSERT(adjacentOfSecondVertex.count() == 2);
+ if (adjacentOfSecondVertex.first() == candidates.at(1))
+ beforeSequence = adjacentOfSecondVertex.last();
+ else
+ beforeSequence = adjacentOfSecondVertex.first();
+ // The complete path of the sequence to simplify is: beforeSequence, <candidates>, afterSequence
+ // where beforeSequence and afterSequence are the endpoints where the anchor is inserted
+ // between.
+#if defined(QT_DEBUG) && 0
+ // ### DEBUG
+ QString strCandidates;
+ for (i = 0; i < candidates.count(); ++i)
+ strCandidates += QString::fromAscii("%1 - ").arg(candidates.at(i)->toString());
+ QString strPath = QString::fromAscii("%1 - %2%3").arg(beforeSequence->toString(), strCandidates, afterSequence->toString());
+ qDebug("candidate list for sequential simplification:\n[%s]", qPrintable(strPath));
+#endif
+
+ bool forward;
+ AnchorVertex *prev = beforeSequence;
+ int intervalFrom = 0;
+
+ // Check for directionality (from). We don't want to destroy that information,
+ // thus we only combine anchors with the same direction.
+
+ // "i" is the index *including* the beforeSequence and afterSequence vertices.
+ for (i = 1; i <= candidates.count() + 1; ++i) {
+ bool atVertexAfter = i > candidates.count();
+ AnchorVertex *v1 = atVertexAfter ? afterSequence : candidates.at(i - 1);
+ AnchorData *data = g.edgeData(prev, v1);
+ Q_ASSERT(data);
+ if (i == 1) {
+ forward = (prev == data->from ? true : false);
+ } else if (forward != (prev == data->from) || atVertexAfter) {
+ int intervalTo = i;
+ if (forward != (prev == data->from))
+ --intervalTo;
+
+ // intervalFrom and intervalTo should now be indices to the vertex before and
+ // after the sequential anchor.
+ if (intervalTo - intervalFrom >= 2) {
+ // simplify in the range [intervalFrom, intervalTo]
+
+ // Trim off internal center anchors (Left-Center/Center-Right) from the
+ // start and the end of the sequence. We never want to simplify internal
+ // center anchors where there is an external anchor connected to the center.
+ AnchorVertex *intervalVertexFrom = intervalFrom == 0 ? beforeSequence : candidates.at(intervalFrom - 1);
+ if (intervalVertexFrom->m_edge == centerEdge
+ && intervalVertexFrom->m_item == candidates.at(intervalFrom)->m_item) {
+ ++intervalFrom;
+ intervalVertexFrom = candidates.at(intervalFrom - 1);
+ }
+ AnchorVertex *intervalVertexTo = intervalTo <= candidates.count() ? candidates.at(intervalTo - 1) : afterSequence;
+ if (intervalVertexTo->m_edge == centerEdge
+ && intervalVertexTo->m_item == candidates.at(intervalTo - 2)->m_item) {
+ --intervalTo;
+ intervalVertexTo = candidates.at(intervalTo - 1);
+ }
+
+ QVector<AnchorVertex*> subCandidates;
+ if (forward) {
+ subCandidates = candidates.mid(intervalFrom, intervalTo - intervalFrom - 1);
+ } else {
+ // reverse the order of the candidates.
+ qSwap(intervalVertexFrom, intervalVertexTo);
+ do {
+ ++intervalFrom;
+ subCandidates.prepend(candidates.at(intervalFrom - 1));
+ } while (intervalFrom < intervalTo - 1);
+ }
+ if (simplifySequentialChunk(&g, intervalVertexFrom, subCandidates, intervalVertexTo)) {
+ dirty = true;
+ break;
+ }
+ // finished simplification of chunk with same direction
+ }
+ if (forward == (prev == data->from))
+ --intervalTo;
+ intervalFrom = intervalTo;
+
+ forward = !forward;
+ }
+ prev = v1;
+ }
+
+ if (dirty)
+ break;
+ }
+
+ if (endOfSequence)
+ candidates.clear();
+
+ for (int i = 0; i < count; ++i) {
+ AnchorVertex *next = vertices.at(i);
+ if (next->m_item == q && next->m_edge == centerEdge)
+ continue;
+ if (visited.contains(next))
+ continue;
+ stack.push(next);
+ }
+
+ visited.insert(v);
+ }
+
+ return dirty;
+}
+
+static void restoreSimplifiedAnchor(Graph<AnchorVertex, AnchorData> &g,
+ AnchorData *edge,
+ AnchorVertex *before,
+ AnchorVertex *after)
+{
+ Q_ASSERT(edge->type != AnchorData::Normal);
+#if 0
+ static const char *anchortypes[] = {"Normal",
+ "Sequential",
+ "Parallel"};
+ qDebug("Restoring %s edge.", anchortypes[int(edge->type)]);
+#endif
+ if (edge->type == AnchorData::Sequential) {
+ SequentialAnchorData* seqEdge = static_cast<SequentialAnchorData*>(edge);
+ // restore the sequential anchor
+ AnchorVertex *prev = before;
+ AnchorVertex *last = after;
+ if (edge->from != prev)
+ qSwap(last, prev);
+
+ for (int i = 0; i < seqEdge->m_edges.count(); ++i) {
+ AnchorVertex *v1 = (i < seqEdge->m_children.count()) ? seqEdge->m_children.at(i) : last;
+ AnchorData *data = seqEdge->m_edges.at(i);
+ if (data->type != AnchorData::Normal) {
+ restoreSimplifiedAnchor(g, data, prev, v1);
+ } else {
+ g.createEdge(prev, v1, data);
+ }
+ prev = v1;
+ }
+ } else if (edge->type == AnchorData::Parallel) {
+ ParallelAnchorData* parallelEdge = static_cast<ParallelAnchorData*>(edge);
+ AnchorData *parallelEdges[2] = {parallelEdge->firstEdge,
+ parallelEdge->secondEdge};
+ for (int i = 0; i < 2; ++i) {
+ AnchorData *data = parallelEdges[i];
+ if (data->type == AnchorData::Normal) {
+ g.createEdge(before, after, data);
+ } else {
+ restoreSimplifiedAnchor(g, data, before, after);
+ }
+ }
+ }
+}
+
+void QGraphicsAnchorLayoutPrivate::restoreSimplifiedGraph(Orientation orientation)
+{
+ if (!graphSimplified[orientation])
+ return;
+ graphSimplified[orientation] = false;
+
+#if 0
+ qDebug("Restoring Simplified Graph for %s",
+ orientation == Horizontal ? "Horizontal" : "Vertical");
+#endif
+
+ Graph<AnchorVertex, AnchorData> &g = graph[orientation];
+
+ QList<QPair<AnchorVertex*, AnchorVertex*> > connections = g.connections();
+ for (int i = 0; i < connections.count(); ++i) {
+ AnchorVertex *v1 = connections.at(i).first;
+ AnchorVertex *v2 = connections.at(i).second;
+ AnchorData *edge = g.edgeData(v1, v2);
+ if (edge->type != AnchorData::Normal) {
+ AnchorData *oldEdge = g.takeEdge(v1, v2);
+ restoreSimplifiedAnchor(g, edge, v1, v2);
+ delete oldEdge;
+ }
+ }
+}
+
+QGraphicsAnchorLayoutPrivate::Orientation
+QGraphicsAnchorLayoutPrivate::edgeOrientation(Qt::AnchorPoint edge)
+{
+ return edge > Qt::AnchorRight ? Vertical : Horizontal;
+}
+
+/*!
+ \internal
+
+ Create internal anchors to connect the layout edges (Left to Right and
+ Top to Bottom).
+
+ These anchors doesn't have size restrictions, that will be enforced by
+ other anchors and items in the layout.
+*/
+void QGraphicsAnchorLayoutPrivate::createLayoutEdges()
+{
+ Q_Q(QGraphicsAnchorLayout);
+ QGraphicsLayoutItem *layout = q;
+
+ // Horizontal
+ AnchorData *data = new AnchorData(0, 0, QWIDGETSIZE_MAX);
+ addAnchor(layout, Qt::AnchorLeft, layout,
+ Qt::AnchorRight, data);
+ data->skipInPreferred = 1;
+
+ // Set the Layout Left edge as the root of the horizontal graph.
+ AnchorVertex *v = internalVertex(layout, Qt::AnchorLeft);
+ graph[Horizontal].setRootVertex(v);
+
+ // Vertical
+ data = new AnchorData(0, 0, QWIDGETSIZE_MAX);
+ addAnchor(layout, Qt::AnchorTop, layout,
+ Qt::AnchorBottom, data);
+ data->skipInPreferred = 1;
+
+ // Set the Layout Top edge as the root of the vertical graph.
+ v = internalVertex(layout, Qt::AnchorTop);
+ graph[Vertical].setRootVertex(v);
+}
+
+void QGraphicsAnchorLayoutPrivate::deleteLayoutEdges()
+{
+ Q_Q(QGraphicsAnchorLayout);
+
+ Q_ASSERT(internalVertex(q, Qt::AnchorHorizontalCenter) == NULL);
+ Q_ASSERT(internalVertex(q, Qt::AnchorVerticalCenter) == NULL);
+
+ removeAnchor(q, Qt::AnchorLeft, q, Qt::AnchorRight);
+ removeAnchor(q, Qt::AnchorTop, q, Qt::AnchorBottom);
+}
+
+void QGraphicsAnchorLayoutPrivate::createItemEdges(QGraphicsLayoutItem *item)
+{
+ Q_ASSERT(!graphSimplified[Horizontal] && !graphSimplified[Vertical]);
+
+ items.append(item);
+
+ // Horizontal
+ int minimumSize = item->minimumWidth();
+ int preferredSize = item->preferredWidth();
+ int maximumSize = item->maximumWidth();
+
+ AnchorData *data = new AnchorData(minimumSize, preferredSize, maximumSize);
+ addAnchor(item, Qt::AnchorLeft, item,
+ Qt::AnchorRight, data);
+
+ // Vertical
+ minimumSize = item->minimumHeight();
+ preferredSize = item->preferredHeight();
+ maximumSize = item->maximumHeight();
+
+ data = new AnchorData(minimumSize, preferredSize, maximumSize);
+ addAnchor(item, Qt::AnchorTop, item,
+ Qt::AnchorBottom, data);
+}
+
+/*!
+ \internal
+
+ By default, each item in the layout is represented internally as
+ a single anchor in each direction. For instance, from Left to Right.
+
+ However, to support anchorage of items to the center of items, we
+ must split this internal anchor into two half-anchors. From Left
+ to Center and then from Center to Right, with the restriction that
+ these anchors must have the same time at all times.
+*/
+void QGraphicsAnchorLayoutPrivate::createCenterAnchors(
+ QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge)
+{
+ Orientation orientation;
+ switch (centerEdge) {
+ case Qt::AnchorHorizontalCenter:
+ orientation = Horizontal;
+ break;
+ case Qt::AnchorVerticalCenter:
+ orientation = Vertical;
+ break;
+ default:
+ // Don't create center edges unless needed
+ return;
+ }
+
+ Q_ASSERT(!graphSimplified[orientation]);
+
+ // Check if vertex already exists
+ if (internalVertex(item, centerEdge))
+ return;
+
+ // Orientation code
+ Qt::AnchorPoint firstEdge;
+ Qt::AnchorPoint lastEdge;
+
+ if (orientation == Horizontal) {
+ firstEdge = Qt::AnchorLeft;
+ lastEdge = Qt::AnchorRight;
+ } else {
+ firstEdge = Qt::AnchorTop;
+ lastEdge = Qt::AnchorBottom;
+ }
+
+ AnchorVertex *first = internalVertex(item, firstEdge);
+ AnchorVertex *last = internalVertex(item, lastEdge);
+ Q_ASSERT(first && last);
+
+ // Create new anchors
+ AnchorData *oldData = graph[orientation].edgeData(first, last);
+
+ int minimumSize = oldData->minSize / 2;
+ int preferredSize = oldData->prefSize / 2;
+ int maximumSize = oldData->maxSize / 2;
+
+ QSimplexConstraint *c = new QSimplexConstraint;
+ AnchorData *data = new AnchorData(minimumSize, preferredSize, maximumSize);
+ c->variables.insert(data, 1.0);
+ addAnchor(item, firstEdge, item, centerEdge, data);
+
+ data = new AnchorData(minimumSize, preferredSize, maximumSize);
+ c->variables.insert(data, -1.0);
+ addAnchor(item, centerEdge, item, lastEdge, data);
+
+ itemCenterConstraints[orientation].append(c);
+
+ // Remove old one
+ removeAnchor(item, firstEdge, item, lastEdge);
+}
+
+void QGraphicsAnchorLayoutPrivate::removeCenterAnchors(
+ QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge,
+ bool substitute)
+{
+ Orientation orientation;
+ switch (centerEdge) {
+ case Qt::AnchorHorizontalCenter:
+ orientation = Horizontal;
+ break;
+ case Qt::AnchorVerticalCenter:
+ orientation = Vertical;
+ break;
+ default:
+ // Don't remove edges that not the center ones
+ return;
+ }
+
+ Q_ASSERT(!graphSimplified[orientation]);
+
+ // Orientation code
+ Qt::AnchorPoint firstEdge;
+ Qt::AnchorPoint lastEdge;
+
+ if (orientation == Horizontal) {
+ firstEdge = Qt::AnchorLeft;
+ lastEdge = Qt::AnchorRight;
+ } else {
+ firstEdge = Qt::AnchorTop;
+ lastEdge = Qt::AnchorBottom;
+ }
+
+ AnchorVertex *center = internalVertex(item, centerEdge);
+ if (!center)
+ return;
+ AnchorVertex *first = internalVertex(item, firstEdge);
+
+ Q_ASSERT(first);
+ Q_ASSERT(center);
+
+ Graph<AnchorVertex, AnchorData> &g = graph[orientation];
+
+
+ AnchorData *oldData = g.edgeData(first, center);
+ // Remove center constraint
+ for (int i = itemCenterConstraints[orientation].count() - 1; i >= 0; --i) {
+ if (itemCenterConstraints[orientation][i]->variables.contains(oldData)) {
+ delete itemCenterConstraints[orientation].takeAt(i);
+ break;
+ }
+ }
+
+ if (substitute) {
+ // Create the new anchor that should substitute the left-center-right anchors.
+ AnchorData *oldData = g.edgeData(first, center);
+
+ int minimumSize = oldData->minSize * 2;
+ int preferredSize = oldData->prefSize * 2;
+ int maximumSize = oldData->maxSize * 2;
+
+ AnchorData *data = new AnchorData(minimumSize, preferredSize, maximumSize);
+ addAnchor(item, firstEdge, item, lastEdge, data);
+
+ // Remove old anchors
+ removeAnchor(item, firstEdge, item, centerEdge);
+ removeAnchor(item, centerEdge, item, lastEdge);
+
+ } else {
+ // this is only called from removeAnchors()
+ // first, remove all non-internal anchors
+ QList<AnchorVertex*> adjacents = g.adjacentVertices(center);
+ for (int i = 0; i < adjacents.count(); ++i) {
+ AnchorVertex *v = adjacents.at(i);
+ if (v->m_item != item) {
+ removeAnchor(item, centerEdge, v->m_item, v->m_edge);
+ }
+ }
+ // when all non-internal anchors is removed it will automatically merge the
+ // center anchor into a left-right (or top-bottom) anchor. We must also delete that.
+ // by this time, the center vertex is deleted and merged into a non-centered internal anchor
+ removeAnchor(item, firstEdge, item, lastEdge);
+ }
+}
+
+
+void QGraphicsAnchorLayoutPrivate::removeCenterConstraints(QGraphicsLayoutItem *item,
+ Orientation orientation)
+{
+ Q_ASSERT(!graphSimplified[orientation]);
+
+ // Remove the item center constraints associated to this item
+ // ### This is a temporary solution. We should probably use a better
+ // data structure to hold items and/or their associated constraints
+ // so that we can remove those easily
+
+ AnchorVertex *first = internalVertex(item, orientation == Horizontal ?
+ Qt::AnchorLeft :
+ Qt::AnchorTop);
+ AnchorVertex *center = internalVertex(item, orientation == Horizontal ?
+ Qt::AnchorHorizontalCenter :
+ Qt::AnchorVerticalCenter);
+
+ // Skip if no center constraints exist
+ if (!center)
+ return;
+
+ Q_ASSERT(first);
+ AnchorData *internalAnchor = graph[orientation].edgeData(first, center);
+
+ // Look for our anchor in all item center constraints, then remove it
+ for (int i = 0; i < itemCenterConstraints[orientation].size(); ++i) {
+ if (itemCenterConstraints[orientation][i]->variables.contains(internalAnchor)) {
+ delete itemCenterConstraints[orientation].takeAt(i);
+ break;
+ }
+ }
+}
+
+/*!
+ * \internal
+ *
+ * Helper function that is called from the anchor functions in the public API.
+ * If \a spacing is 0, it will pick up the spacing defined by the style.
+ */
+void QGraphicsAnchorLayoutPrivate::anchor(QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge,
+ qreal *spacing)
+{
+ Q_Q(QGraphicsAnchorLayout);
+ if ((firstItem == 0) || (secondItem == 0)) {
+ qWarning("QGraphicsAnchorLayout::addAnchor(): "
+ "Cannot anchor NULL items");
+ return;
+ }
+
+ if (firstItem == secondItem) {
+ qWarning("QGraphicsAnchorLayout::addAnchor(): "
+ "Cannot anchor the item to itself");
+ return;
+ }
+
+ if (edgeOrientation(secondEdge) != edgeOrientation(firstEdge)) {
+ qWarning("QGraphicsAnchorLayout::addAnchor(): "
+ "Cannot anchor edges of different orientations");
+ return;
+ }
+
+ // Guarantee that the graph is no simplified when adding this anchor,
+ // anchor manipulation always happen in the full graph
+ restoreSimplifiedGraph(edgeOrientation(firstEdge));
+
+ // In QGraphicsAnchorLayout, items are represented in its internal
+ // graph as four anchors that connect:
+ // - Left -> HCenter
+ // - HCenter-> Right
+ // - Top -> VCenter
+ // - VCenter -> Bottom
+
+ // Ensure that the internal anchors have been created for both items.
+ if (firstItem != q && !items.contains(firstItem)) {
+ restoreSimplifiedGraph(edgeOrientation(firstEdge) == Horizontal ? Vertical : Horizontal);
+ createItemEdges(firstItem);
+ addChildLayoutItem(firstItem);
+ }
+ if (secondItem != q && !items.contains(secondItem)) {
+ restoreSimplifiedGraph(edgeOrientation(firstEdge) == Horizontal ? Vertical : Horizontal);
+ createItemEdges(secondItem);
+ addChildLayoutItem(secondItem);
+ }
+
+ // Create center edges if needed
+ createCenterAnchors(firstItem, firstEdge);
+ createCenterAnchors(secondItem, secondEdge);
+
+ // Use heuristics to find out what the user meant with this anchor.
+ correctEdgeDirection(firstItem, firstEdge, secondItem, secondEdge);
+
+ AnchorData *data;
+ if (!spacing) {
+ // If firstItem or secondItem is the layout itself, the spacing will default to 0.
+ // Otherwise, the following matrix is used (questionmark means that the spacing
+ // is queried from the style):
+ // from
+ // to Left HCenter Right
+ // Left 0 0 ?
+ // HCenter 0 0 0
+ // Right ? 0 0
+ if (firstItem != q
+ && secondItem != q
+ && pickEdge(firstEdge, Horizontal) != Qt::AnchorHorizontalCenter
+ && oppositeEdge(firstEdge) == secondEdge) {
+ data = new AnchorData; // ask the style later
+ } else {
+ data = new AnchorData(0); // spacing should be 0
+ }
+ addAnchor(firstItem, firstEdge, secondItem, secondEdge, data);
+ } else if (*spacing >= 0) {
+ data = new AnchorData(*spacing);
+ addAnchor(firstItem, firstEdge, secondItem, secondEdge, data);
+ } else {
+ data = new AnchorData(-*spacing);
+ addAnchor(secondItem, secondEdge, firstItem, firstEdge, data);
+ }
+}
+
+void QGraphicsAnchorLayoutPrivate::addAnchor(QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge,
+ AnchorData *data)
+{
+ Q_Q(QGraphicsAnchorLayout);
+
+ // Guarantee that the graph is no simplified when adding this anchor,
+ // anchor manipulation always happen in the full graph
+ restoreSimplifiedGraph(edgeOrientation(firstEdge));
+
+ // Is the Vertex (firstItem, firstEdge) already represented in our
+ // internal structure?
+ AnchorVertex *v1 = addInternalVertex(firstItem, firstEdge);
+ AnchorVertex *v2 = addInternalVertex(secondItem, secondEdge);
+
+ // Remove previous anchor
+ // ### Could we update the existing edgeData rather than creating a new one?
+ if (graph[edgeOrientation(firstEdge)].edgeData(v1, v2))
+ removeAnchor(firstItem, firstEdge, secondItem, secondEdge);
+
+ // Create a bi-directional edge in the sense it can be transversed both
+ // from v1 or v2. "data" however is shared between the two references
+ // so we still know that the anchor direction is from 1 to 2.
+ data->from = v1;
+ data->to = v2;
+#ifdef QT_DEBUG
+ data->name = QString::fromAscii("%1 --to--> %2").arg(v1->toString()).arg(v2->toString());
+#endif
+ // Keep track of anchors that are connected to the layout 'edges'
+ data->isLayoutAnchor = (v1->m_item == q || v2->m_item == q);
+
+ graph[edgeOrientation(firstEdge)].createEdge(v1, v2, data);
+}
+
+void QGraphicsAnchorLayoutPrivate::removeAnchor(QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge)
+{
+ // Guarantee that the graph is no simplified when adding this anchor,
+ // anchor manipulation always happen in the full graph
+ restoreSimplifiedGraph(edgeOrientation(firstEdge));
+
+ // Look for both vertices
+ AnchorVertex *v1 = internalVertex(firstItem, firstEdge);
+ AnchorVertex *v2 = internalVertex(secondItem, secondEdge);
+
+ Q_ASSERT(v1 && v2);
+
+ // Remove edge from graph
+ graph[edgeOrientation(firstEdge)].removeEdge(v1, v2);
+
+ // Decrease vertices reference count (may trigger a deletion)
+ removeInternalVertex(firstItem, firstEdge);
+ removeInternalVertex(secondItem, secondEdge);
+}
+
+bool QGraphicsAnchorLayoutPrivate::setAnchorSize(const QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge,
+ const qreal *anchorSize)
+{
+ // ### we can avoid restoration if we really want to, but we would have to
+ // search recursively through all composite anchors
+ restoreSimplifiedGraph(edgeOrientation(firstEdge));
+ AnchorVertex *v1 = internalVertex(firstItem, firstEdge);
+ AnchorVertex *v2 = internalVertex(secondItem, secondEdge);
+
+ AnchorData *data = graph[edgeOrientation(firstEdge)].edgeData(v1, v2);
+ if (data) {
+ if (anchorSize) {
+ data->setFixedSize(*anchorSize);
+ } else {
+ data->unsetSize();
+ }
+ }
+
+ return data;
+}
+
+bool QGraphicsAnchorLayoutPrivate::anchorSize(const QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge,
+ qreal *minSize,
+ qreal *prefSize,
+ qreal *maxSize) const
+{
+ Q_ASSERT(minSize || prefSize || maxSize);
+ QGraphicsAnchorLayoutPrivate *that = const_cast<QGraphicsAnchorLayoutPrivate *>(this);
+ that->restoreSimplifiedGraph(edgeOrientation(firstEdge));
+ AnchorVertex *v1 = internalVertex(firstItem, firstEdge);
+ AnchorVertex *v2 = internalVertex(secondItem, secondEdge);
+
+ AnchorData *data = that->graph[edgeOrientation(firstEdge)].edgeData(v1, v2);
+ if (data) {
+ if (minSize)
+ *minSize = data->minSize;
+ if (prefSize)
+ *prefSize = data->prefSize;
+ if (maxSize)
+ *maxSize = data->maxSize;
+ }
+ return data;
+}
+
+AnchorVertex *QGraphicsAnchorLayoutPrivate::addInternalVertex(QGraphicsLayoutItem *item,
+ Qt::AnchorPoint edge)
+{
+ QPair<QGraphicsLayoutItem *, Qt::AnchorPoint> pair(item, edge);
+ QPair<AnchorVertex *, int> v = m_vertexList.value(pair);
+
+ if (!v.first) {
+ Q_ASSERT(v.second == 0);
+ v.first = new AnchorVertex(item, edge);
+ }
+ v.second++;
+ m_vertexList.insert(pair, v);
+ return v.first;
+}
+
+/**
+ * \internal
+ *
+ * returns the AnchorVertex that was dereferenced, also when it was removed.
+ * returns 0 if it did not exist.
+ */
+void QGraphicsAnchorLayoutPrivate::removeInternalVertex(QGraphicsLayoutItem *item,
+ Qt::AnchorPoint edge)
+{
+ QPair<QGraphicsLayoutItem *, Qt::AnchorPoint> pair(item, edge);
+ QPair<AnchorVertex *, int> v = m_vertexList.value(pair);
+
+ if (!v.first) {
+ qWarning("This item with this edge is not in the graph");
+ return;
+ }
+
+ v.second--;
+ if (v.second == 0) {
+ // Remove reference and delete vertex
+ m_vertexList.remove(pair);
+ delete v.first;
+ } else {
+ // Update reference count
+ m_vertexList.insert(pair, v);
+
+ if ((v.second == 2) &&
+ ((edge == Qt::AnchorHorizontalCenter) ||
+ (edge == Qt::AnchorVerticalCenter))) {
+ removeCenterAnchors(item, edge, true);
+ }
+ }
+}
+
+void QGraphicsAnchorLayoutPrivate::removeVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
+{
+ if (AnchorVertex *v = internalVertex(item, edge)) {
+ Graph<AnchorVertex, AnchorData> &g = graph[edgeOrientation(edge)];
+ const QList<AnchorVertex *> allVertices = graph[edgeOrientation(edge)].adjacentVertices(v);
+ AnchorVertex *v2;
+ foreach (v2, allVertices) {
+ g.removeEdge(v, v2);
+ removeInternalVertex(item, edge);
+ removeInternalVertex(v2->m_item, v2->m_edge);
+ }
+ }
+}
+
+void QGraphicsAnchorLayoutPrivate::removeAnchors(QGraphicsLayoutItem *item)
+{
+ Q_ASSERT(!graphSimplified[Horizontal] && !graphSimplified[Vertical]);
+
+ // remove the center anchor first!!
+ removeCenterAnchors(item, Qt::AnchorHorizontalCenter, false);
+ removeVertex(item, Qt::AnchorLeft);
+ removeVertex(item, Qt::AnchorRight);
+
+ removeCenterAnchors(item, Qt::AnchorVerticalCenter, false);
+ removeVertex(item, Qt::AnchorTop);
+ removeVertex(item, Qt::AnchorBottom);
+}
+
+/*!
+ \internal
+
+ Use heuristics to determine the correct orientation of a given anchor.
+
+ After API discussions, we decided we would like expressions like
+ anchor(A, Left, B, Right) to mean the same as anchor(B, Right, A, Left).
+ The problem with this is that anchors could become ambiguous, for
+ instance, what does the anchor A, B of size X mean?
+
+ "pos(B) = pos(A) + X" or "pos(A) = pos(B) + X" ?
+
+ To keep the API user friendly and at the same time, keep our algorithm
+ deterministic, we use an heuristic to determine a direction for each
+ added anchor and then keep it. The heuristic is based on the fact
+ that people usually avoid overlapping items, therefore:
+
+ "A, RIGHT to B, LEFT" means that B is to the LEFT of A.
+ "B, LEFT to A, RIGHT" is corrected to the above anchor.
+
+ Special correction is also applied when one of the items is the
+ layout. We handle Layout Left as if it was another items's Right
+ and Layout Right as another item's Left.
+*/
+void QGraphicsAnchorLayoutPrivate::correctEdgeDirection(QGraphicsLayoutItem *&firstItem,
+ Qt::AnchorPoint &firstEdge,
+ QGraphicsLayoutItem *&secondItem,
+ Qt::AnchorPoint &secondEdge)
+{
+ Q_Q(QGraphicsAnchorLayout);
+
+ Qt::AnchorPoint effectiveFirst = firstEdge;
+ Qt::AnchorPoint effectiveSecond = secondEdge;
+
+ if (firstItem == q)
+ effectiveFirst = QGraphicsAnchorLayoutPrivate::oppositeEdge(firstEdge);
+ if (secondItem == q)
+ effectiveSecond = QGraphicsAnchorLayoutPrivate::oppositeEdge(secondEdge);
+
+ if (effectiveFirst < effectiveSecond) {
+
+ // ### DEBUG
+ /* printf("Swapping Anchor from %s %d --to--> %s %d\n",
+ firstItem->isLayout() ? "<layout>" :
+ qPrintable(static_cast<QGraphicsWidget *>(firstItem)->data(0).toString()),
+ firstEdge,
+ secondItem->isLayout() ? "<layout>" :
+ qPrintable(static_cast<QGraphicsWidget *>(secondItem)->data(0).toString()),
+ secondEdge);
+ */
+ qSwap(firstItem, secondItem);
+ qSwap(firstEdge, secondEdge);
+ }
+}
+
+qreal QGraphicsAnchorLayoutPrivate::effectiveSpacing(Orientation orientation) const
+{
+ Q_Q(const QGraphicsAnchorLayout);
+ qreal s = spacings[orientation];
+ if (s < 0) {
+ // ### make sure behaviour is the same as in QGraphicsGridLayout
+ QGraphicsLayoutItem *parent = q->parentLayoutItem();
+ while (parent && parent->isLayout()) {
+ parent = parent->parentLayoutItem();
+ }
+ if (parent) {
+ QGraphicsItem *parentItem = parent->graphicsItem();
+ if (parentItem && parentItem->isWidget()) {
+ QGraphicsWidget *w = static_cast<QGraphicsWidget*>(parentItem);
+ s = w->style()->pixelMetric(orientation == Horizontal
+ ? QStyle::PM_LayoutHorizontalSpacing
+ : QStyle::PM_LayoutVerticalSpacing);
+ }
+ }
+ }
+ return s;
+}
+
+/*!
+ \internal
+
+ Called on activation. Uses Linear Programming to define minimum, preferred
+ and maximum sizes for the layout. Also calculates the sizes that each item
+ should assume when the layout is in one of such situations.
+*/
+void QGraphicsAnchorLayoutPrivate::calculateGraphs()
+{
+ if (!calculateGraphCacheDirty)
+ return;
+
+ calculateGraphs(Horizontal);
+ calculateGraphs(Vertical);
+
+ calculateGraphCacheDirty = 0;
+}
+
+// ### remove me:
+QList<AnchorData *> getVariables(QList<QSimplexConstraint *> constraints)
+{
+ QSet<AnchorData *> variableSet;
+ for (int i = 0; i < constraints.count(); ++i) {
+ const QSimplexConstraint *c = constraints[i];
+ foreach (QSimplexVariable *var, c->variables.keys()) {
+ variableSet += static_cast<AnchorData *>(var);
+ }
+ }
+ return variableSet.toList();
+}
+
+/*!
+ \internal
+
+ Calculate graphs is the method that puts together all the helper routines
+ so that the AnchorLayout can calculate the sizes of each item.
+
+ In a nutshell it should do:
+
+ 1) Update anchor nominal sizes, that is, the size that each anchor would
+ have if no other restrictions applied. This is done by quering the
+ layout style and the sizeHints of the items belonging to the layout.
+
+ 2) Simplify the graph by grouping together parallel and sequential anchors
+ into "group anchors". These have equivalent minimum, preferred and maximum
+ sizeHints as the anchors they replace.
+
+ 3) Check if we got to a trivial case. In some cases, the whole graph can be
+ simplified into a single anchor. If so, use this information. If not,
+ then call the Simplex solver to calculate the anchors sizes.
+
+ 4) Once the root anchors had its sizes calculated, propagate that to the
+ anchors they represent.
+*/
+void QGraphicsAnchorLayoutPrivate::calculateGraphs(
+ QGraphicsAnchorLayoutPrivate::Orientation orientation)
+{
+ Q_Q(QGraphicsAnchorLayout);
+
+ // Simplify the graph
+ simplifyGraph(orientation);
+
+ // Reset the nominal sizes of each anchor based on the current item sizes
+ setAnchorSizeHintsFromItems(orientation);
+
+ // Traverse all graph edges and store the possible paths to each vertex
+ findPaths(orientation);
+
+ // From the paths calculated above, extract the constraints that the current
+ // anchor setup impose, to our Linear Programming problem.
+ constraintsFromPaths(orientation);
+
+ // Split the constraints and anchors into groups that should be fed to the
+ // simplex solver independently. Currently we find two groups:
+ //
+ // 1) The "trunk", that is, the set of anchors (items) that are connected
+ // to the two opposite sides of our layout, and thus need to stretch in
+ // order to fit in the current layout size.
+ //
+ // 2) The floating or semi-floating anchors (items) that are those which
+ // are connected to only one (or none) of the layout sides, thus are not
+ // influenced by the layout size.
+ QList<QList<QSimplexConstraint *> > parts;
+ parts = getGraphParts(orientation);
+
+ // Now run the simplex solver to calculate Minimum, Preferred and Maximum sizes
+ // of the "trunk" set of constraints and variables.
+ // ### does trunk always exist? empty = trunk is the layout left->center->right
+ QList<QSimplexConstraint *> trunkConstraints = parts[0];
+ QList<QSimplexConstraint *> sizeHintConstraints;
+ sizeHintConstraints = constraintsFromSizeHints(getVariables(trunkConstraints));
+ trunkConstraints += sizeHintConstraints;
+
+ // For minimum and maximum, use the path between the two layout sides as the
+ // objective function.
+
+ // Retrieve that path
+ AnchorVertex *v = internalVertex(q, pickEdge(Qt::AnchorRight, orientation));
+ GraphPath trunkPath = graphPaths[orientation].value(v);
+
+ if (!trunkConstraints.isEmpty()) {
+#if 0
+ qDebug("Simplex used for trunk of %s",
+ orientation == Horizontal ? "Horizontal" : "Vertical");
+#endif
+
+ // Solve min and max size hints for trunk
+ QPair<qreal, qreal> minMax = solveMinMax(trunkConstraints, trunkPath);
+ sizeHints[orientation][Qt::MinimumSize] = minMax.first;
+ sizeHints[orientation][Qt::MaximumSize] = minMax.second;
+
+ // Solve for preferred. The objective function is calculated from the constraints
+ // and variables internally.
+ solvePreferred(trunkConstraints);
+
+ // Propagate the new sizes down the simplified graph, ie. tell the
+ // group anchors to set their children anchors sizes.
+
+ // ### we calculated variables already a few times, can't we reuse that?
+ QList<AnchorData *> trunkVariables = getVariables(trunkConstraints);
+
+ for (int i = 0; i < trunkVariables.count(); ++i)
+ trunkVariables.at(i)->updateChildrenSizes();
+
+ // Calculate and set the preferred size for the layout from the edge sizes that
+ // were calculated above.
+ qreal pref(0.0);
+ foreach (const AnchorData *ad, trunkPath.positives) {
+ pref += ad->sizeAtPreferred;
+ }
+ foreach (const AnchorData *ad, trunkPath.negatives) {
+ pref -= ad->sizeAtPreferred;
+ }
+ sizeHints[orientation][Qt::PreferredSize] = pref;
+ } else {
+#if 0
+ qDebug("Simplex NOT used for trunk of %s",
+ orientation == Horizontal ? "Horizontal" : "Vertical");
+#endif
+
+ // No Simplex is necessary because the path was simplified all the way to a single
+ // anchor.
+ Q_ASSERT(trunkPath.positives.count() == 1);
+ Q_ASSERT(trunkPath.negatives.count() == 0);
+
+ AnchorData *ad = trunkPath.positives.toList()[0];
+ ad->sizeAtMinimum = ad->minSize;
+ ad->sizeAtPreferred = ad->prefSize;
+ ad->sizeAtMaximum = ad->maxSize;
+
+ // Propagate
+ ad->updateChildrenSizes();
+
+ sizeHints[orientation][Qt::MinimumSize] = ad->sizeAtMinimum;
+ sizeHints[orientation][Qt::PreferredSize] = ad->sizeAtPreferred;
+ sizeHints[orientation][Qt::MaximumSize] = ad->sizeAtMaximum;
+ }
+
+ // Delete the constraints, we won't use them anymore.
+ qDeleteAll(sizeHintConstraints);
+ sizeHintConstraints.clear();
+
+ // For the other parts that not the trunk, solve only for the preferred size
+ // that is the size they will remain at, since they are not stretched by the
+ // layout.
+
+ // Solve the other only for preferred, skip trunk
+ for (int i = 1; i < parts.count(); ++i) {
+ QList<QSimplexConstraint *> partConstraints = parts[i];
+ QList<AnchorData *> partVariables = getVariables(partConstraints);
+ Q_ASSERT(!partVariables.isEmpty());
+
+ sizeHintConstraints = constraintsFromSizeHints(partVariables);
+ partConstraints += sizeHintConstraints;
+ solvePreferred(partConstraints);
+
+ // Propagate size at preferred to other sizes. Semi-floats
+ // always will be in their sizeAtPreferred.
+ for (int j = 0; j < partVariables.count(); ++j) {
+ AnchorData *ad = partVariables[j];
+ Q_ASSERT(ad);
+ ad->sizeAtMinimum = ad->sizeAtPreferred;
+ ad->sizeAtMaximum = ad->sizeAtPreferred;
+ ad->updateChildrenSizes();
+ }
+
+ // Delete the constraints, we won't use them anymore.
+ qDeleteAll(sizeHintConstraints);
+ sizeHintConstraints.clear();
+ }
+
+ // Clean up our data structures. They are not needed anymore since
+ // distribution uses just interpolation.
+ qDeleteAll(constraints[orientation]);
+ constraints[orientation].clear();
+ graphPaths[orientation].clear(); // ###
+}
+
+/*!
+ \internal
+
+ For graph edges ("anchors") that represent items, this method updates their
+ intrinsic size restrictions, based on the item size hints.
+*/
+void QGraphicsAnchorLayoutPrivate::setAnchorSizeHintsFromItems(Orientation orientation)
+{
+ Graph<AnchorVertex, AnchorData> &g = graph[orientation];
+ QList<QPair<AnchorVertex *, AnchorVertex *> > vertices = g.connections();
+
+ qreal spacing = effectiveSpacing(orientation);
+
+ for (int i = 0; i < vertices.count(); ++i) {
+ AnchorData *data = g.edgeData(vertices.at(i).first, vertices.at(i).second);;
+ Q_ASSERT(data->from && data->to);
+ data->refreshSizeHints(spacing);
+ }
+}
+
+/*!
+ \internal
+
+ This method walks the graph using a breadth-first search to find paths
+ between the root vertex and each vertex on the graph. The edges
+ directions in each path are considered and they are stored as a
+ positive edge (left-to-right) or negative edge (right-to-left).
+
+ The list of paths is used later to generate a list of constraints.
+ */
+void QGraphicsAnchorLayoutPrivate::findPaths(Orientation orientation)
+{
+ QQueue<QPair<AnchorVertex *, AnchorVertex *> > queue;
+
+ QSet<AnchorData *> visited;
+
+ AnchorVertex *root = graph[orientation].rootVertex();
+
+ graphPaths[orientation].insert(root, GraphPath());
+
+ foreach (AnchorVertex *v, graph[orientation].adjacentVertices(root)) {
+ queue.enqueue(qMakePair(root, v));
+ }
+
+ while(!queue.isEmpty()) {
+ QPair<AnchorVertex *, AnchorVertex *> pair = queue.dequeue();
+ AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);
+
+ if (visited.contains(edge))
+ continue;
+
+ visited.insert(edge);
+ GraphPath current = graphPaths[orientation].value(pair.first);
+
+ if (edge->from == pair.first)
+ current.positives.insert(edge);
+ else
+ current.negatives.insert(edge);
+
+ graphPaths[orientation].insert(pair.second, current);
+
+ foreach (AnchorVertex *v,
+ graph[orientation].adjacentVertices(pair.second)) {
+ queue.enqueue(qMakePair(pair.second, v));
+ }
+ }
+}
+
+/*!
+ \internal
+
+ Each vertex on the graph that has more than one path to it
+ represents a contra int to the sizes of the items in these paths.
+
+ This method walks the list of paths to each vertex, generate
+ the constraints and store them in a list so they can be used later
+ by the Simplex solver.
+*/
+void QGraphicsAnchorLayoutPrivate::constraintsFromPaths(Orientation orientation)
+{
+ foreach (AnchorVertex *vertex, graphPaths[orientation].uniqueKeys())
+ {
+ int valueCount = graphPaths[orientation].count(vertex);
+ if (valueCount == 1)
+ continue;
+
+ QList<GraphPath> pathsToVertex = graphPaths[orientation].values(vertex);
+ for (int i = 1; i < valueCount; ++i) {
+ constraints[orientation] += \
+ pathsToVertex[0].constraint(pathsToVertex[i]);
+ }
+ }
+}
+
+/*!
+ \internal
+
+ Create LP constraints for each anchor based on its minimum and maximum
+ sizes, as specified in its size hints
+*/
+QList<QSimplexConstraint *> QGraphicsAnchorLayoutPrivate::constraintsFromSizeHints(
+ const QList<AnchorData *> &anchors)
+{
+ QList<QSimplexConstraint *> anchorConstraints;
+ for (int i = 0; i < anchors.size(); ++i) {
+ QSimplexConstraint *c = new QSimplexConstraint;
+ c->variables.insert(anchors[i], 1.0);
+ c->constant = anchors[i]->minSize;
+ c->ratio = QSimplexConstraint::MoreOrEqual;
+ anchorConstraints += c;
+
+ c = new QSimplexConstraint;
+ c->variables.insert(anchors[i], 1.0);
+ c->constant = anchors[i]->maxSize;
+ c->ratio = QSimplexConstraint::LessOrEqual;
+ anchorConstraints += c;
+ }
+
+ return anchorConstraints;
+}
+
+/*!
+ \Internal
+*/
+QList< QList<QSimplexConstraint *> >
+QGraphicsAnchorLayoutPrivate::getGraphParts(Orientation orientation)
+{
+ Q_Q(QGraphicsAnchorLayout);
+
+ // Find layout vertices and edges for the current orientation.
+ AnchorVertex *layoutFirstVertex = \
+ internalVertex(q, pickEdge(Qt::AnchorLeft, orientation));
+
+ AnchorVertex *layoutCentralVertex = \
+ internalVertex(q, pickEdge(Qt::AnchorHorizontalCenter, orientation));
+
+ AnchorVertex *layoutLastVertex = \
+ internalVertex(q, pickEdge(Qt::AnchorRight, orientation));
+
+ Q_ASSERT(layoutFirstVertex && layoutLastVertex);
+
+ AnchorData *edgeL1 = NULL;
+ AnchorData *edgeL2 = NULL;
+
+ // The layout may have a single anchor between Left and Right or two half anchors
+ // passing through the center
+ if (layoutCentralVertex) {
+ edgeL1 = graph[orientation].edgeData(layoutFirstVertex, layoutCentralVertex);
+ edgeL2 = graph[orientation].edgeData(layoutCentralVertex, layoutLastVertex);
+ } else {
+ edgeL1 = graph[orientation].edgeData(layoutFirstVertex, layoutLastVertex);
+ }
+
+ QLinkedList<QSimplexConstraint *> remainingConstraints;
+ for (int i = 0; i < constraints[orientation].count(); ++i) {
+ remainingConstraints += constraints[orientation][i];
+ }
+ for (int i = 0; i < itemCenterConstraints[orientation].count(); ++i) {
+ remainingConstraints += itemCenterConstraints[orientation][i];
+ }
+
+ QList<QSimplexConstraint *> trunkConstraints;
+ QSet<QSimplexVariable *> trunkVariables;
+
+ trunkVariables += edgeL1;
+ if (edgeL2)
+ trunkVariables += edgeL2;
+
+ bool dirty;
+ do {
+ dirty = false;
+
+ QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
+ while (it != remainingConstraints.end()) {
+ QSimplexConstraint *c = *it;
+ bool match = false;
+
+ // Check if this constraint have some overlap with current
+ // trunk variables...
+ foreach (QSimplexVariable *ad, trunkVariables) {
+ if (c->variables.contains(ad)) {
+ match = true;
+ break;
+ }
+ }
+
+ // If so, we add it to trunk, and erase it from the
+ // remaining constraints.
+ if (match) {
+ trunkConstraints += c;
+ trunkVariables += QSet<QSimplexVariable *>::fromList(c->variables.keys());
+ it = remainingConstraints.erase(it);
+ dirty = true;
+ } else {
+ // Note that we don't erase the constraint if it's not
+ // a match, since in a next iteration of a do-while we
+ // can pass on it again and it will be a match.
+ //
+ // For example: if trunk share a variable with
+ // remainingConstraints[1] and it shares with
+ // remainingConstraints[0], we need a second iteration
+ // of the do-while loop to match both.
+ ++it;
+ }
+ }
+ } while (dirty);
+
+ QList< QList<QSimplexConstraint *> > result;
+ result += trunkConstraints;
+
+ if (!remainingConstraints.isEmpty()) {
+ QList<QSimplexConstraint *> nonTrunkConstraints;
+ QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
+ while (it != remainingConstraints.end()) {
+ nonTrunkConstraints += *it;
+ ++it;
+ }
+ result += nonTrunkConstraints;
+ }
+
+ return result;
+}
+
+/*!
+ \internal
+
+ Use the current vertices distance to calculate and set the geometry of
+ each item.
+*/
+void QGraphicsAnchorLayoutPrivate::setItemsGeometries()
+{
+ AnchorVertex *firstH, *secondH, *firstV, *secondV;
+
+ foreach (QGraphicsLayoutItem *item, items) {
+ firstH = internalVertex(item, Qt::AnchorLeft);
+ secondH = internalVertex(item, Qt::AnchorRight);
+ firstV = internalVertex(item, Qt::AnchorTop);
+ secondV = internalVertex(item, Qt::AnchorBottom);
+
+ QPointF topLeft(firstH->distance, firstV->distance);
+ QPointF bottomRight(secondH->distance, secondV->distance);
+
+ item->setGeometry(QRectF(topLeft, bottomRight));
+ }
+}
+
+/*!
+ \internal
+
+ Calculate the position of each vertex based on the paths to each of
+ them as well as the current edges sizes.
+*/
+void QGraphicsAnchorLayoutPrivate::calculateVertexPositions(
+ QGraphicsAnchorLayoutPrivate::Orientation orientation)
+{
+ Q_Q(QGraphicsAnchorLayout);
+ QQueue<QPair<AnchorVertex *, AnchorVertex *> > queue;
+ QSet<AnchorVertex *> visited;
+
+ // Get root vertex
+ AnchorVertex *root = graph[orientation].rootVertex();
+
+ qreal widgetMargin;
+ qreal layoutMargin;
+
+ // Initialize the first vertex
+ if (orientation == Horizontal) {
+ widgetMargin = q->geometry().x();
+ q->getContentsMargins(&layoutMargin, 0, 0, 0);
+ } else {
+ // Root position is equal to the top margin
+ widgetMargin = q->geometry().y();
+ q->getContentsMargins(0, &layoutMargin, 0, 0);
+ }
+ root->distance = widgetMargin + layoutMargin;
+ visited.insert(root);
+
+ // Add initial edges to the queue
+ foreach (AnchorVertex *v, graph[orientation].adjacentVertices(root)) {
+ queue.enqueue(qMakePair(root, v));
+ }
+
+ // Do initial calculation required by "interpolateEdge()"
+ setupEdgesInterpolation(orientation);
+
+ // Traverse the graph and calculate vertex positions, we need to
+ // visit all pairs since each of them could have a sequential
+ // anchor inside, which hides more vertices.
+ while (!queue.isEmpty()) {
+ QPair<AnchorVertex *, AnchorVertex *> pair = queue.dequeue();
+ AnchorData *edge = graph[orientation].edgeData(pair.first, pair.second);
+
+ // Both vertices were interpolated, and the anchor itself can't have other
+ // anchors inside (it's not a complex anchor).
+ if (edge->type == AnchorData::Normal && visited.contains(pair.second))
+ continue;
+
+ visited.insert(pair.second);
+ interpolateEdge(pair.first, edge, orientation);
+
+ QList<AnchorVertex *> adjacents = graph[orientation].adjacentVertices(pair.second);
+ for (int i = 0; i < adjacents.count(); ++i) {
+ if (!visited.contains(adjacents.at(i)))
+ queue.enqueue(qMakePair(pair.second, adjacents.at(i)));
+ }
+ }
+}
+
+/*!
+ \internal
+
+ Calculate interpolation parameters based on current Layout Size.
+ Must once before calling "interpolateEdgeSize()" for each edge.
+*/
+void QGraphicsAnchorLayoutPrivate::setupEdgesInterpolation(
+ Orientation orientation)
+{
+ Q_Q(QGraphicsAnchorLayout);
+ qreal lower, upper, current;
+
+ if (orientation == Horizontal) {
+ current = q->contentsRect().width();
+ } else {
+ current = q->contentsRect().height();
+ }
+
+ if (current < sizeHints[orientation][Qt::PreferredSize]) {
+ interpolationInterval[orientation] = MinToPreferred;
+ lower = sizeHints[orientation][Qt::MinimumSize];
+ upper = sizeHints[orientation][Qt::PreferredSize];
+ } else {
+ interpolationInterval[orientation] = PreferredToMax;
+ lower = sizeHints[orientation][Qt::PreferredSize];
+ upper = sizeHints[orientation][Qt::MaximumSize];
+ }
+
+ if (upper == lower) {
+ interpolationProgress[orientation] = 0;
+ } else {
+ interpolationProgress[orientation] = (current - lower) / (upper - lower);
+ }
+}
+
+/*!
+ \internal
+
+ Calculate the current Edge size based on the current Layout size and the
+ size the edge is supposed to have when:
+
+ - the layout is at its minimum size.
+ - the layout is at its preferred size.
+ - the layout is at its maximum size.
+
+ These three key values are calculated in advance using linear
+ programming (more expensive) or the simplification algorithm, then
+ subsequential resizes of the parent layout require a simple
+ interpolation.
+
+ If the edge is sequential or parallel, it's possible to have more
+ vertices to be initalized, so it calls specialized functions that
+ will recurse back to interpolateEdge().
+ */
+void QGraphicsAnchorLayoutPrivate::interpolateEdge(AnchorVertex *base,
+ AnchorData *edge,
+ Orientation orientation)
+{
+ qreal lower, upper;
+
+ if (interpolationInterval[orientation] == MinToPreferred) {
+ lower = edge->sizeAtMinimum;
+ upper = edge->sizeAtPreferred;
+ } else {
+ lower = edge->sizeAtPreferred;
+ upper = edge->sizeAtMaximum;
+ }
+
+ qreal edgeDistance = (interpolationProgress[orientation] * (upper - lower)) + lower;
+
+ Q_ASSERT(edge->from == base || edge->to == base);
+
+ if (edge->from == base)
+ edge->to->distance = base->distance + edgeDistance;
+ else
+ edge->from->distance = base->distance - edgeDistance;
+
+ // Process child anchors
+ if (edge->type == AnchorData::Sequential)
+ interpolateSequentialEdges(edge->from,
+ static_cast<SequentialAnchorData *>(edge),
+ orientation);
+ else if (edge->type == AnchorData::Parallel)
+ interpolateParallelEdges(edge->from,
+ static_cast<ParallelAnchorData *>(edge),
+ orientation);
+}
+
+void QGraphicsAnchorLayoutPrivate::interpolateParallelEdges(
+ AnchorVertex *base, ParallelAnchorData *data, Orientation orientation)
+{
+ // In parallels the boundary vertices are already calculate, we
+ // just need to look for sequential groups inside, because only
+ // them may have new vertices associated.
+
+ // First edge
+ if (data->firstEdge->type == AnchorData::Sequential)
+ interpolateSequentialEdges(base,
+ static_cast<SequentialAnchorData *>(data->firstEdge),
+ orientation);
+ else if (data->firstEdge->type == AnchorData::Parallel)
+ interpolateParallelEdges(base,
+ static_cast<ParallelAnchorData *>(data->firstEdge),
+ orientation);
+
+ // Second edge
+ if (data->secondEdge->type == AnchorData::Sequential)
+ interpolateSequentialEdges(base,
+ static_cast<SequentialAnchorData *>(data->secondEdge),
+ orientation);
+ else if (data->secondEdge->type == AnchorData::Parallel)
+ interpolateParallelEdges(base,
+ static_cast<ParallelAnchorData *>(data->secondEdge),
+ orientation);
+}
+
+void QGraphicsAnchorLayoutPrivate::interpolateSequentialEdges(
+ AnchorVertex *base, SequentialAnchorData *data, Orientation orientation)
+{
+ AnchorVertex *prev = base;
+
+ // ### I'm not sure whether this assumption is safe. If not,
+ // consider that m_edges.last() could be used instead (so
+ // at(0) would be the one to be treated specially).
+ Q_ASSERT(base == data->m_edges.at(0)->to || base == data->m_edges.at(0)->from);
+
+ // Skip the last
+ for (int i = 0; i < data->m_edges.count() - 1; ++i) {
+ AnchorData *child = data->m_edges.at(i);
+ interpolateEdge(prev, child, orientation);
+ prev = child->to;
+ }
+
+ // Treat the last specially, since we already calculated it's end
+ // vertex, so it's only interesting if it's a complex one
+ if (data->m_edges.last()->type != AnchorData::Normal)
+ interpolateEdge(prev, data->m_edges.last(), orientation);
+}
+
+QPair<qreal, qreal>
+QGraphicsAnchorLayoutPrivate::solveMinMax(QList<QSimplexConstraint *> constraints,
+ GraphPath path)
+{
+ QSimplex simplex;
+ simplex.setConstraints(constraints);
+
+ // Obtain the objective constraint
+ QSimplexConstraint objective;
+ QSet<AnchorData *>::const_iterator iter;
+ for (iter = path.positives.constBegin(); iter != path.positives.constEnd(); ++iter)
+ objective.variables.insert(*iter, 1.0);
+
+ for (iter = path.negatives.constBegin(); iter != path.negatives.constEnd(); ++iter)
+ objective.variables.insert(*iter, -1.0);
+
+ simplex.setObjective(&objective);
+
+ // Calculate minimum values
+ qreal min = simplex.solveMin();
+
+ // Save sizeAtMinimum results
+ QList<QSimplexVariable *> variables = simplex.constraintsVariables();
+ for (int i = 0; i < variables.size(); ++i) {
+ AnchorData *ad = static_cast<AnchorData *>(variables[i]);
+ ad->sizeAtMinimum = ad->result;
+ }
+
+ // Calculate maximum values
+ qreal max = simplex.solveMax();
+
+ // Save sizeAtMaximum results
+ for (int i = 0; i < variables.size(); ++i) {
+ AnchorData *ad = static_cast<AnchorData *>(variables[i]);
+ ad->sizeAtMaximum = ad->result;
+ }
+
+ return qMakePair<qreal, qreal>(min, max);
+}
+
+void QGraphicsAnchorLayoutPrivate::solvePreferred(QList<QSimplexConstraint *> constraints)
+{
+ QList<AnchorData *> variables = getVariables(constraints);
+ QList<QSimplexConstraint *> preferredConstraints;
+ QList<QSimplexVariable *> preferredVariables;
+ QSimplexConstraint objective;
+
+ // Fill the objective coefficients for this variable. In the
+ // end the objective function will be
+ //
+ // z = n * (A_shrink + B_shrink + ...) + (A_grower + B_grower + ...)
+ //
+ // where n is the number of variables that have
+ // slacks. Note that here we use the number of variables
+ // as coefficient, this is to mark the "shrinker slack
+ // variable" less likely to get value than the "grower
+ // slack variable".
+
+ // This will fill the values for the structural constraints
+ // and we now fill the values for the slack constraints (one per variable),
+ // which have this form (the constant A_pref was set when creating the slacks):
+ //
+ // A + A_shrinker - A_grower = A_pref
+ //
+ for (int i = 0; i < variables.size(); ++i) {
+ AnchorData *ad = static_cast<AnchorData *>(variables[i]);
+ if (ad->skipInPreferred)
+ continue;
+
+ QSimplexVariable *grower = new QSimplexVariable;
+ QSimplexVariable *shrinker = new QSimplexVariable;
+ QSimplexConstraint *c = new QSimplexConstraint;
+ c->variables.insert(ad, 1.0);
+ c->variables.insert(shrinker, 1.0);
+ c->variables.insert(grower, -1.0);
+ c->constant = ad->prefSize;
+
+ preferredConstraints += c;
+ preferredVariables += grower;
+ preferredVariables += shrinker;
+
+ objective.variables.insert(grower, 1.0);
+ objective.variables.insert(shrinker, variables.size());
+ }
+
+
+ QSimplex *simplex = new QSimplex;
+ simplex->setConstraints(constraints + preferredConstraints);
+ simplex->setObjective(&objective);
+
+ // Calculate minimum values
+ simplex->solveMin();
+
+ // Save sizeAtPreferred results
+ for (int i = 0; i < variables.size(); ++i) {
+ AnchorData *ad = static_cast<AnchorData *>(variables[i]);
+ ad->sizeAtPreferred = ad->result;
+ }
+
+ // Make sure we delete the simplex solver -before- we delete the
+ // constraints used by it.
+ delete simplex;
+
+ // Delete constraints and variables we created.
+ qDeleteAll(preferredConstraints);
+ qDeleteAll(preferredVariables);
+}
+
+#ifdef QT_DEBUG
+void QGraphicsAnchorLayoutPrivate::dumpGraph()
+{
+ QFile file(QString::fromAscii("anchorlayout.dot"));
+ if (!file.open(QIODevice::WriteOnly | QIODevice::Text | QIODevice::Truncate))
+ qWarning("Could not write to %s", file.fileName().toLocal8Bit().constData());
+
+ QString str = QString::fromAscii("digraph anchorlayout {\nnode [shape=\"rect\"]\n%1}");
+ QString dotContents = graph[0].serializeToDot();
+ dotContents += graph[1].serializeToDot();
+ file.write(str.arg(dotContents).toLocal8Bit());
+
+ file.close();
+}
+#endif
+
+QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.h b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
new file mode 100644
index 000000000..15a1b44b8
--- /dev/null
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
@@ -0,0 +1,477 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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 qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QGraphicsWidget>
+
+#include "qgraphicslayout_p.h"
+#include "qgraphicsanchorlayout.h"
+#include "qgraph_p.h"
+#include "qsimplex_p.h"
+
+QT_BEGIN_NAMESPACE
+
+/*
+ The public QGraphicsAnchorLayout interface represents an anchorage point
+ as a pair of a <QGraphicsLayoutItem *> and a <Qt::AnchorPoint>.
+
+ Internally though, it has a graph of anchorage points (vertices) and
+ anchors (edges), represented by the AnchorVertex and AnchorData structs
+ respectively.
+*/
+
+/*!
+ \internal
+
+ Represents a vertex (anchorage point) in the internal graph
+*/
+struct AnchorVertex {
+ AnchorVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
+ : m_item(item), m_edge(edge) {}
+
+ AnchorVertex()
+ : m_item(0), m_edge(Qt::AnchorPoint(0)) {}
+
+#ifdef QT_DEBUG
+ inline QString toString() const;
+#endif
+ QGraphicsLayoutItem *m_item;
+ Qt::AnchorPoint m_edge;
+
+ // Current distance from this vertex to the layout edge (Left or Top)
+ // Value is calculated from the current anchors sizes.
+ qreal distance;
+};
+
+#ifdef QT_DEBUG
+inline QString AnchorVertex::toString() const
+{
+ if (!this || !m_item) {
+ return QLatin1String("NULL");
+ }
+ QString edge;
+ switch (m_edge) {
+ case Qt::AnchorLeft:
+ edge = QLatin1String("Left");
+ break;
+ case Qt::AnchorHorizontalCenter:
+ edge = QLatin1String("HorizontalCenter");
+ break;
+ case Qt::AnchorRight:
+ edge = QLatin1String("Right");
+ break;
+ case Qt::AnchorTop:
+ edge = QLatin1String("Top");
+ break;
+ case Qt::AnchorVerticalCenter:
+ edge = QLatin1String("VerticalCenter");
+ break;
+ case Qt::AnchorBottom:
+ edge = QLatin1String("Bottom");
+ break;
+ default:
+ edge = QLatin1String("None");
+ break;
+ }
+ QString itemName;
+ if (m_item->isLayout()) {
+ itemName = QLatin1String("layout");
+ } else {
+ if (QGraphicsItem *item = m_item->graphicsItem()) {
+ itemName = item->data(0).toString();
+ }
+ }
+ edge.insert(0, QLatin1String("%1_"));
+ return edge.arg(itemName);
+}
+#endif
+
+/*!
+ \internal
+
+ Represents an edge (anchor) in the internal graph.
+*/
+struct AnchorData : public QSimplexVariable {
+ enum Type {
+ Normal = 0,
+ Sequential,
+ Parallel
+ };
+ AnchorData(qreal minimumSize, qreal preferredSize, qreal maximumSize)
+ : QSimplexVariable(), from(0), to(0),
+ minSize(minimumSize), prefSize(preferredSize),
+ maxSize(maximumSize), sizeAtMinimum(preferredSize),
+ sizeAtPreferred(preferredSize), sizeAtMaximum(preferredSize),
+ skipInPreferred(0), type(Normal), hasSize(true),
+ isLayoutAnchor(false) {}
+
+ AnchorData(qreal size)
+ : QSimplexVariable(), from(0), to(0),
+ minSize(size), prefSize(size), maxSize(size),
+ sizeAtMinimum(size), sizeAtPreferred(size), sizeAtMaximum(size),
+ skipInPreferred(0), type(Normal), hasSize(true),
+ isLayoutAnchor(false) {}
+
+ AnchorData()
+ : QSimplexVariable(), from(0), to(0),
+ minSize(0), prefSize(0), maxSize(0),
+ sizeAtMinimum(0), sizeAtPreferred(0), sizeAtMaximum(0),
+ skipInPreferred(0), type(Normal), hasSize(false),
+ isLayoutAnchor(false) {}
+
+ virtual void updateChildrenSizes() { };
+ virtual void refreshSizeHints(qreal effectiveSpacing);
+
+ virtual ~AnchorData() {}
+
+#ifdef QT_DEBUG
+ void dump(int indent = 2);
+ inline QString toString() const;
+ QString name;
+#endif
+
+ inline void setFixedSize(qreal size)
+ {
+ minSize = size;
+ prefSize = size;
+ maxSize = size;
+ sizeAtMinimum = size;
+ sizeAtPreferred = size;
+ sizeAtMaximum = size;
+ hasSize = true;
+ }
+
+ inline void unsetSize()
+ {
+ hasSize = false;
+ }
+
+ // Anchor is semantically directed
+ AnchorVertex *from;
+ AnchorVertex *to;
+
+ // Size restrictions of this edge. For anchors internal to items, these
+ // values are derived from the respective item size hints. For anchors
+ // that were added by users, these values are equal to the specified anchor
+ // size.
+ qreal minSize;
+ qreal prefSize;
+ qreal maxSize;
+
+ // These attributes define which sizes should that anchor be in when the
+ // layout is at its minimum, preferred or maximum sizes. Values are
+ // calculated by the Simplex solver based on the current layout setup.
+ qreal sizeAtMinimum;
+ qreal sizeAtPreferred;
+ qreal sizeAtMaximum;
+
+ uint skipInPreferred : 1;
+ uint type : 2; // either Normal, Sequential or Parallel
+ uint hasSize : 1; // if false, get size from style.
+ uint isLayoutAnchor : 1; // if this anchor is connected to a layout 'edge'
+protected:
+ AnchorData(Type type, qreal size = 0)
+ : QSimplexVariable(), from(0), to(0),
+ minSize(size), prefSize(size),
+ maxSize(size), sizeAtMinimum(size),
+ sizeAtPreferred(size), sizeAtMaximum(size),
+ skipInPreferred(0), type(type), hasSize(true),
+ isLayoutAnchor(false) {}
+};
+
+#ifdef QT_DEBUG
+inline QString AnchorData::toString() const
+{
+ return QString::fromAscii("Anchor(%1)").arg(name);
+}
+#endif
+
+struct SequentialAnchorData : public AnchorData
+{
+ SequentialAnchorData() : AnchorData(AnchorData::Sequential)
+ {
+#ifdef QT_DEBUG
+ name = QLatin1String("SequentialAnchorData");
+#endif
+ }
+
+ virtual void updateChildrenSizes();
+ virtual void refreshSizeHints(qreal effectiveSpacing);
+
+ void setVertices(const QVector<AnchorVertex*> &vertices)
+ {
+ m_children = vertices;
+#ifdef QT_DEBUG
+ name = QString::fromAscii("%1 -- %2").arg(vertices.first()->toString(), vertices.last()->toString());
+#endif
+ }
+
+ QVector<AnchorVertex*> m_children; // list of vertices in the sequence
+ QVector<AnchorData*> m_edges; // keep the list of edges too.
+};
+
+struct ParallelAnchorData : public AnchorData
+{
+ ParallelAnchorData(AnchorData *first, AnchorData *second)
+ : AnchorData(AnchorData::Parallel),
+ firstEdge(first), secondEdge(second)
+ {
+ // ### Those asserts force that both child anchors have the same direction,
+ // but can't we simplify a pair of anchors in opposite directions?
+ Q_ASSERT(first->from == second->from);
+ Q_ASSERT(first->to == second->to);
+ from = first->from;
+ to = first->to;
+#ifdef QT_DEBUG
+ name = QString::fromAscii("%1 | %2").arg(first->toString(), second->toString());
+#endif
+ }
+
+ virtual void updateChildrenSizes();
+ virtual void refreshSizeHints(qreal effectiveSpacing);
+
+ AnchorData* firstEdge;
+ AnchorData* secondEdge;
+};
+
+/*!
+ \internal
+
+ Representation of a valid path for a given vertex in the graph.
+ In this struct, "positives" is the set of anchors that have been
+ traversed in the forward direction, while "negatives" is the set
+ with the ones walked backwards.
+
+ This paths are compared against each other to produce LP Constraints,
+ the exact order in which the anchors were traversed is not relevant.
+*/
+class GraphPath
+{
+public:
+ GraphPath() {};
+
+ QSimplexConstraint *constraint(const GraphPath &path) const;
+#ifdef QT_DEBUG
+ QString toString() const;
+#endif
+ QSet<AnchorData *> positives;
+ QSet<AnchorData *> negatives;
+};
+
+
+/*!
+ \internal
+
+ QGraphicsAnchorLayout private methods and attributes.
+*/
+class QGraphicsAnchorLayoutPrivate : public QGraphicsLayoutPrivate
+{
+ Q_DECLARE_PUBLIC(QGraphicsAnchorLayout)
+
+public:
+ // When the layout geometry is different from its Minimum, Preferred
+ // or Maximum values, interpolation is used to calculate the geometries
+ // of the items.
+ //
+ // Interval represents which interpolation interval are we operating in.
+ enum Interval {
+ MinToPreferred = 0,
+ PreferredToMax
+ };
+
+ // Several structures internal to the layout are duplicated to handle
+ // both Horizontal and Vertical restrictions.
+ //
+ // Orientation is used to reference the right structure in each context
+ enum Orientation {
+ Horizontal = 0,
+ Vertical,
+ NOrientations
+ };
+
+ QGraphicsAnchorLayoutPrivate();
+
+ static Qt::AnchorPoint oppositeEdge(
+ Qt::AnchorPoint edge);
+
+ static Orientation edgeOrientation(Qt::AnchorPoint edge);
+
+ static Qt::AnchorPoint pickEdge(Qt::AnchorPoint edge, Orientation orientation)
+ {
+ if (orientation == Vertical && int(edge) <= 2)
+ return (Qt::AnchorPoint)(edge + 3);
+ else if (orientation == Horizontal && int(edge) >= 3) {
+ return (Qt::AnchorPoint)(edge - 3);
+ }
+ return edge;
+ }
+
+ // Init methods
+ void createLayoutEdges();
+ void deleteLayoutEdges();
+ void createItemEdges(QGraphicsLayoutItem *item);
+ void createCenterAnchors(QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge);
+ void removeCenterAnchors(QGraphicsLayoutItem *item, Qt::AnchorPoint centerEdge, bool substitute = true);
+ void removeCenterConstraints(QGraphicsLayoutItem *item, Orientation orientation);
+
+ // helper function used by the 4 API functions
+ void anchor(QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge,
+ qreal *spacing = 0);
+
+ // Anchor Manipulation methods
+ void addAnchor(QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge,
+ AnchorData *data);
+
+ void removeAnchor(QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge);
+
+ bool setAnchorSize(const QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge,
+ const qreal *anchorSize);
+
+ bool anchorSize(const QGraphicsLayoutItem *firstItem,
+ Qt::AnchorPoint firstEdge,
+ const QGraphicsLayoutItem *secondItem,
+ Qt::AnchorPoint secondEdge,
+ qreal *minSize = 0,
+ qreal *prefSize = 0,
+ qreal *maxSize = 0) const;
+
+ void removeAnchors(QGraphicsLayoutItem *item);
+
+ void removeVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge);
+
+ void correctEdgeDirection(QGraphicsLayoutItem *&firstItem,
+ Qt::AnchorPoint &firstEdge,
+ QGraphicsLayoutItem *&secondItem,
+ Qt::AnchorPoint &secondEdge);
+ // for getting the actual spacing (will query the style if the
+ // spacing is not explicitly set).
+ qreal effectiveSpacing(Orientation orientation) const;
+
+ // Activation methods
+ void simplifyGraph(Orientation orientation);
+ bool simplifyGraphIteration(Orientation orientation);
+ void restoreSimplifiedGraph(Orientation orientation);
+
+ void calculateGraphs();
+ void calculateGraphs(Orientation orientation);
+ void setAnchorSizeHintsFromItems(Orientation orientation);
+ void findPaths(Orientation orientation);
+ void constraintsFromPaths(Orientation orientation);
+ QList<QSimplexConstraint *> constraintsFromSizeHints(const QList<AnchorData *> &anchors);
+ QList<QList<QSimplexConstraint *> > getGraphParts(Orientation orientation);
+
+ inline AnchorVertex *internalVertex(const QPair<QGraphicsLayoutItem*, Qt::AnchorPoint> &itemEdge) const
+ {
+ return m_vertexList.value(itemEdge).first;
+ }
+
+ inline AnchorVertex *internalVertex(const QGraphicsLayoutItem *item, Qt::AnchorPoint edge) const
+ {
+ return internalVertex(qMakePair(const_cast<QGraphicsLayoutItem *>(item), edge));
+ }
+
+ AnchorVertex *addInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge);
+ void removeInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge);
+
+ // Geometry interpolation methods
+ void setItemsGeometries();
+
+ void calculateVertexPositions(Orientation orientation);
+ void setupEdgesInterpolation(Orientation orientation);
+ void interpolateEdge(AnchorVertex *base, AnchorData *edge, Orientation orientation);
+ void interpolateSequentialEdges(AnchorVertex *base, SequentialAnchorData *edge,
+ Orientation orientation);
+ void interpolateParallelEdges(AnchorVertex *base, ParallelAnchorData *edge,
+ Orientation orientation);
+
+ // Linear Programming solver methods
+ QPair<qreal, qreal> solveMinMax(QList<QSimplexConstraint *> constraints,
+ GraphPath path);
+ void solvePreferred(QList<QSimplexConstraint *> constraints);
+
+#ifdef QT_DEBUG
+ void dumpGraph();
+#endif
+
+
+ qreal spacings[NOrientations];
+ // Size hints from simplex engine
+ qreal sizeHints[2][3];
+
+ // Items
+ QVector<QGraphicsLayoutItem *> items;
+
+ // Mapping between high level anchorage points (Item, Edge) to low level
+ // ones (Graph Vertices)
+
+ QHash<QPair<QGraphicsLayoutItem*, Qt::AnchorPoint>, QPair<AnchorVertex *, int> > m_vertexList;
+
+ // Internal graph of anchorage points and anchors, for both orientations
+ Graph<AnchorVertex, AnchorData> graph[2];
+
+ // Graph paths and constraints, for both orientations
+ QMultiHash<AnchorVertex *, GraphPath> graphPaths[2];
+ QList<QSimplexConstraint *> constraints[2];
+ QList<QSimplexConstraint *> itemCenterConstraints[2];
+
+ // The interpolation interval and progress based on the current size
+ // as well as the key values (minimum, preferred and maximum)
+ Interval interpolationInterval[2];
+ qreal interpolationProgress[2];
+
+ // ###
+ bool graphSimplified[2];
+
+ uint calculateGraphCacheDirty : 1;
+};
+
+QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index 4f64c2acd..88fac1470 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -1023,7 +1023,7 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent)
}
// Resolve depth.
- resolveDepth(parent ? parent->d_ptr->depth : -1);
+ invalidateDepthRecursively();
dirtySceneTransform = 1;
// Restore the sub focus chain.
@@ -4413,14 +4413,42 @@ bool QGraphicsItemPrivate::discardUpdateRequest(bool ignoreClipping, bool ignore
/*!
\internal
+*/
+int QGraphicsItemPrivate::depth() const
+{
+ if (itemDepth == -1)
+ const_cast<QGraphicsItemPrivate *>(this)->resolveDepth();
+
+ return itemDepth;
+}
- Resolves the stacking depth of this object and all its children.
+/*!
+ \internal
*/
-void QGraphicsItemPrivate::resolveDepth(int parentDepth)
+void QGraphicsItemPrivate::invalidateDepthRecursively()
{
- depth = parentDepth + 1;
+ if (itemDepth == -1)
+ return;
+
+ itemDepth = -1;
for (int i = 0; i < children.size(); ++i)
- children.at(i)->d_ptr->resolveDepth(depth);
+ children.at(i)->d_ptr->invalidateDepthRecursively();
+}
+
+/*!
+ \internal
+
+ Resolves the stacking depth of this object and all its ancestors.
+*/
+void QGraphicsItemPrivate::resolveDepth()
+{
+ if (!parent)
+ itemDepth = 0;
+ else {
+ if (parent->d_ptr->itemDepth == -1)
+ parent->d_ptr->resolveDepth();
+ itemDepth = parent->d_ptr->itemDepth + 1;
+ }
}
/*!
@@ -5590,8 +5618,8 @@ QGraphicsItem *QGraphicsItem::commonAncestorItem(const QGraphicsItem *other) con
return const_cast<QGraphicsItem *>(this);
const QGraphicsItem *thisw = this;
const QGraphicsItem *otherw = other;
- int thisDepth = d_ptr->depth;
- int otherDepth = other->d_ptr->depth;
+ int thisDepth = d_ptr->depth();
+ int otherDepth = other->d_ptr->depth();
while (thisDepth > otherDepth) {
thisw = thisw->d_ptr->parent;
--thisDepth;
@@ -6601,7 +6629,7 @@ void QGraphicsItem::prepareGeometryChange()
// if someone is connected to the changed signal or the scene has no views.
// Note that this has to be done *after* markDirty to ensure that
// _q_processDirtyItems is called before _q_emitUpdated.
- if ((scenePrivate->connectedSignals[0] & scenePrivate->changedSignalMask)
+ if (scenePrivate->isSignalConnected(scenePrivate->changedSignalIndex)
|| scenePrivate->views.isEmpty()) {
if (d_ptr->hasTranslateOnlySceneTransform()) {
d_ptr->scene->update(boundingRect().translated(d_ptr->sceneTransform.dx(),
diff --git a/src/gui/graphicsview/qgraphicsitem_p.h b/src/gui/graphicsview/qgraphicsitem_p.h
index 24326f6f0..fea82aeb5 100644
--- a/src/gui/graphicsview/qgraphicsitem_p.h
+++ b/src/gui/graphicsview/qgraphicsitem_p.h
@@ -123,7 +123,7 @@ public:
transformData(0),
index(-1),
siblingIndex(-1),
- depth(0),
+ itemDepth(-1),
focusProxy(0),
subFocusItem(0),
imHints(Qt::ImhNone),
@@ -209,7 +209,9 @@ public:
void setEnabledHelper(bool newEnabled, bool explicitly, bool update = true);
bool discardUpdateRequest(bool ignoreClipping = false, bool ignoreVisibleBit = false,
bool ignoreDirtyBit = false, bool ignoreOpacity = false) const;
- void resolveDepth(int parentDepth);
+ int depth() const;
+ void invalidateDepthRecursively();
+ void resolveDepth();
void addChild(QGraphicsItem *child);
void removeChild(QGraphicsItem *child);
void setParentItemHelper(QGraphicsItem *parent);
@@ -419,7 +421,7 @@ public:
QTransform sceneTransform;
int index;
int siblingIndex;
- int depth;
+ int itemDepth; // Lazily calculated when calling depth().
QGraphicsItem *focusProxy;
QList<QGraphicsItem **> focusProxyRefs;
QGraphicsItem *subFocusItem;
@@ -500,16 +502,17 @@ struct QGraphicsItemPrivate::TransformData
return transform * *postmultiplyTransform;
}
- QTransform x(transform);
+ QMatrix4x4 x(transform);
for (int i = 0; i < graphicsTransforms.size(); ++i)
graphicsTransforms.at(i)->applyTo(&x);
x.translate(xOrigin, yOrigin);
- x.rotate(rotation, Qt::ZAxis);
- x.scale(scale, scale);
+ x.rotate(rotation, 0, 0, 1);
+ x.scale(scale);
x.translate(-xOrigin, -yOrigin);
+ QTransform t = x.toTransform(); // project the 3D matrix back to 2D.
if (postmultiplyTransform)
- x *= *postmultiplyTransform;
- return x;
+ t *= *postmultiplyTransform;
+ return t;
}
};
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index a2a92b88d..a8db74d59 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -265,12 +265,13 @@ static void _q_hoverFromMouseEvent(QGraphicsSceneHoverEvent *hover, const QGraph
hover->setAccepted(mouseEvent->isAccepted());
}
+int QGraphicsScenePrivate::changedSignalIndex;
+
/*!
\internal
*/
QGraphicsScenePrivate::QGraphicsScenePrivate()
- : changedSignalMask(0),
- indexMethod(QGraphicsScene::BspTreeIndex),
+ : indexMethod(QGraphicsScene::BspTreeIndex),
index(0),
lastItemCount(0),
hasSceneRect(false),
@@ -311,7 +312,9 @@ void QGraphicsScenePrivate::init()
index = new QGraphicsSceneBspTreeIndex(q);
// Keep this index so we can check for connected slots later on.
- changedSignalMask = (1 << q->metaObject()->indexOfSignal("changed(QList<QRectF>)"));
+ if (!changedSignalIndex) {
+ changedSignalIndex = signalIndex("changed(QList<QRectF>)");
+ }
qApp->d_func()->scene_list.append(q);
q->update();
}
@@ -343,7 +346,7 @@ void QGraphicsScenePrivate::_q_emitUpdated()
// 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 (connectedSignals[0] & changedSignalMask) {
+ if (isSignalConnected(changedSignalIndex)) {
for (int i = 0; i < views.size(); ++i) {
QGraphicsView *view = views.at(i);
if (!view->d_func()->connectedToScene) {
@@ -2894,7 +2897,7 @@ void QGraphicsScene::update(const QRectF &rect)
// Check if anyone's connected; if not, we can send updates directly to
// the views. Otherwise or if there are no views, use old behavior.
- bool directUpdates = !(d->connectedSignals[0] & d->changedSignalMask) && !d->views.isEmpty();
+ bool directUpdates = !(d->isSignalConnected(d->changedSignalIndex)) && !d->views.isEmpty();
if (rect.isNull()) {
d->updateAll = true;
d->updatedRects.clear();
@@ -4473,7 +4476,7 @@ void QGraphicsScenePrivate::markDirty(QGraphicsItem *item, const QRectF &rect, b
if (removingItemFromScene) {
// Note that this function can be called from the item's destructor, so
// do NOT call any virtual functions on it within this block.
- if ((connectedSignals[0] & changedSignalMask) || views.isEmpty()) {
+ if (isSignalConnected(changedSignalIndex) || views.isEmpty()) {
// This block of code is kept for compatibility. Since 4.5, by default
// QGraphicsView does not connect the signal and we use the below
// method of delivering updates.
@@ -4619,7 +4622,7 @@ void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, bool
// Process item.
if (item->d_ptr->dirty || item->d_ptr->paintedViewBoundingRectsNeedRepaint) {
- const bool useCompatUpdate = views.isEmpty() || (connectedSignals[0] & changedSignalMask);
+ const bool useCompatUpdate = views.isEmpty() || isSignalConnected(changedSignalIndex);
const QRectF itemBoundingRect = adjustedItemBoundingRect(item);
if (useCompatUpdate && !itemIsUntransformable && qFuzzyIsNull(item->boundingRegionGranularity())) {
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index 685f534c2..f1ddb5acd 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -87,7 +87,7 @@ public:
static QGraphicsScenePrivate *get(QGraphicsScene *q);
- quint32 changedSignalMask;
+ static int changedSignalIndex;
QGraphicsScene::ItemIndexMethod indexMethod;
QGraphicsSceneIndex *index;
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
index 433d0a844..7483bc166 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
@@ -419,8 +419,8 @@ bool QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withoutCache(const QGra
// Find common ancestor, and each item's ancestor closest to the common
// ancestor.
- int item1Depth = d1->depth;
- int item2Depth = d2->depth;
+ int item1Depth = d1->depth();
+ int item2Depth = d2->depth();
const QGraphicsItem *p = item1;
const QGraphicsItem *t1 = item1;
while (item1Depth > item2Depth && (p = p->d_ptr->parent)) {
diff --git a/src/gui/graphicsview/qgraphicstransform.cpp b/src/gui/graphicsview/qgraphicstransform.cpp
index edfcf8aee..c5653d731 100644
--- a/src/gui/graphicsview/qgraphicstransform.cpp
+++ b/src/gui/graphicsview/qgraphicstransform.cpp
@@ -63,10 +63,17 @@
independent transformation. The resulting operation is then combined into a
single transform which is applied to QGraphicsItem.
+ Transformations are computed in true 3D space using QMatrix4x4.
+ When the transformation is applied to a QGraphicsItem, it will be
+ projected back to a 2D QTransform. When multiple QGraphicsTransform
+ objects are applied to a QGraphicsItem, all of the transformations
+ are computed in true 3D space, with the projection back to 2D
+ only occurring after the last QGraphicsTransform is applied.
+
If you want to create your own configurable transformation, you can create
a subclass of QGraphicsTransform (or any or the existing subclasses), and
reimplement the pure virtual applyTo() function, which takes a pointer to a
- QTransform. Each operation you would like to apply should be exposed as
+ QMatrix4x4. Each operation you would like to apply should be exposed as
properties (e.g., customTransform->setVerticalShear(2.5)). Inside you
reimplementation of applyTo(), you can modify the provided transform
respectively.
@@ -136,28 +143,13 @@ QGraphicsTransform::QGraphicsTransform(QGraphicsTransformPrivate &p, QObject *pa
}
/*!
- Applies this transformation to an identity transform, and returns the
- resulting transform.
-
- This is equivalent to passing an identity transform to applyTo().
-
- \sa applyTo()
-*/
-QTransform QGraphicsTransform::transform() const
-{
- QTransform t;
- applyTo(&t);
- return t;
-}
-
-/*!
- \fn void QGraphicsTransform::applyTo(QTransform *transform) const
+ \fn void QGraphicsTransform::applyTo(QMatrix4x4 *matrix) const
This pure virtual method has to be reimplemented in derived classes.
- It applies this transformation to \a transform.
+ It applies this transformation to \a matrix.
- \sa QGraphicsItem::transform()
+ \sa QGraphicsItem::transform(), QMatrix4x4::toTransform()
*/
/*!
@@ -189,11 +181,12 @@ void QGraphicsTransform::update()
relative to the parent as the rest of the item grows). By default the
origin is QPointF(0, 0).
- The two parameters xScale and yScale describe the scale factors to apply in
- horizontal and vertical direction. They can take on any value, including 0
- (to collapse the item to a point) or negativate value. A negative xScale
- value will mirror the item horizontally. A negative yScale value will flip
- the item vertically.
+ The parameters xScale, yScale, and zScale describe the scale factors to
+ apply in horizontal, vertical, and depth directions. They can take on any
+ value, including 0 (to collapse the item to a point) or negative value.
+ A negative xScale value will mirror the item horizontally. A negative yScale
+ value will flip the item vertically. A negative zScale will flip the
+ item end for end.
\sa QGraphicsTransform, QGraphicsItem::setScale(), QTransform::scale()
*/
@@ -202,10 +195,11 @@ class QGraphicsScalePrivate : public QGraphicsTransformPrivate
{
public:
QGraphicsScalePrivate()
- : xScale(1), yScale(1) {}
- QPointF origin;
+ : xScale(1), yScale(1), zScale(1) {}
+ QVector3D origin;
qreal xScale;
qreal yScale;
+ qreal zScale;
};
/*!
@@ -225,21 +219,23 @@ QGraphicsScale::~QGraphicsScale()
/*!
\property QGraphicsScale::origin
- \brief The QGraphicsScene class provides the origin of the scale.
+ \brief the origin of the scale in 3D space.
All scaling will be done relative to this point (i.e., this point
will stay fixed, relative to the parent, when the item is scaled).
- \sa xScale, yScale
+ \sa xScale, yScale, zScale
*/
-QPointF QGraphicsScale::origin() const
+QVector3D QGraphicsScale::origin() const
{
Q_D(const QGraphicsScale);
return d->origin;
}
-void QGraphicsScale::setOrigin(const QPointF &point)
+void QGraphicsScale::setOrigin(const QVector3D &point)
{
Q_D(QGraphicsScale);
+ if (d->origin == point)
+ return;
d->origin = point;
update();
emit originChanged();
@@ -254,7 +250,7 @@ void QGraphicsScale::setOrigin(const QPointF &point)
provide a negative value, the item will be mirrored horizontally around its
origin.
- \sa yScale, origin
+ \sa yScale, zScale, origin
*/
qreal QGraphicsScale::xScale() const
{
@@ -280,7 +276,7 @@ void QGraphicsScale::setXScale(qreal scale)
provide a negative value, the item will be flipped vertically around its
origin.
- \sa xScale, origin
+ \sa xScale, zScale, origin
*/
qreal QGraphicsScale::yScale() const
{
@@ -298,14 +294,40 @@ void QGraphicsScale::setYScale(qreal scale)
}
/*!
+ \property QGraphicsScale::zScale
+ \brief the depth scale factor.
+
+ The scale factor can be any real number; the default value is 1.0. If you
+ set the factor to 0.0, the item will be collapsed to a single point. If you
+ provide a negative value, the item will be flipped end for end around its
+ origin.
+
+ \sa xScale, yScale, origin
+*/
+qreal QGraphicsScale::zScale() const
+{
+ Q_D(const QGraphicsScale);
+ return d->zScale;
+}
+void QGraphicsScale::setZScale(qreal scale)
+{
+ Q_D(QGraphicsScale);
+ if (d->zScale == scale)
+ return;
+ d->zScale = scale;
+ update();
+ emit scaleChanged();
+}
+
+/*!
\reimp
*/
-void QGraphicsScale::applyTo(QTransform *transform) const
+void QGraphicsScale::applyTo(QMatrix4x4 *matrix) const
{
Q_D(const QGraphicsScale);
- transform->translate(d->origin.x(), d->origin.y());
- transform->scale(d->xScale, d->yScale);
- transform->translate(-d->origin.x(), -d->origin.y());
+ matrix->translate(d->origin);
+ matrix->scale(d->xScale, d->yScale, d->zScale);
+ matrix->translate(-d->origin);
}
/*!
@@ -319,10 +341,11 @@ void QGraphicsScale::applyTo(QTransform *transform) const
/*!
\fn QGraphicsScale::scaleChanged()
- This signal is emitted whenever the xScale or yScale of the object
- changes.
+ This signal is emitted whenever the xScale, yScale, or zScale
+ of the object changes.
\sa QGraphicsScale::xScale, QGraphicsScale::yScale
+ \sa QGraphicsScale::zScale
*/
/*!
@@ -359,20 +382,14 @@ void QGraphicsScale::applyTo(QTransform *transform) const
\sa QGraphicsTransform, QGraphicsItem::setRotation(), QTransform::rotate()
*/
-#define VECTOR_FOR_AXIS_X QVector3D(1, 0, 0)
-#define VECTOR_FOR_AXIS_Y QVector3D(0, 1, 0)
-#define VECTOR_FOR_AXIS_Z QVector3D(0, 0, 1)
-
-
class QGraphicsRotationPrivate : public QGraphicsTransformPrivate
{
public:
QGraphicsRotationPrivate()
- : angle(0), axis(VECTOR_FOR_AXIS_Z), simpleAxis(Qt::ZAxis) {}
- QPointF origin;
+ : angle(0), axis(0, 0, 1) {}
+ QVector3D origin;
qreal angle;
QVector3D axis;
- int simpleAxis;
};
/*!
@@ -392,21 +409,23 @@ QGraphicsRotation::~QGraphicsRotation()
/*!
\property QGraphicsRotation::origin
- \brief the origin of the rotation.
+ \brief the origin of the rotation in 3D space.
All rotations will be done relative to this point (i.e., this point
will stay fixed, relative to the parent, when the item is rotated).
\sa angle
*/
-QPointF QGraphicsRotation::origin() const
+QVector3D QGraphicsRotation::origin() const
{
Q_D(const QGraphicsRotation);
return d->origin;
}
-void QGraphicsRotation::setOrigin(const QPointF &point)
+void QGraphicsRotation::setOrigin(const QVector3D &point)
{
Q_D(QGraphicsRotation);
+ if (d->origin == point)
+ return;
d->origin = point;
update();
emit originChanged();
@@ -448,11 +467,11 @@ void QGraphicsRotation::setAngle(qreal angle)
*/
/*!
- \fn void QGraphicsRotation::angleChanged()
+ \fn void QGraphicsRotation::angleChanged()
- This signal is emitted whenever the angle has changed.
+ This signal is emitted whenever the angle has changed.
- \sa QGraphicsRotation::angle
+ \sa QGraphicsRotation::angle
*/
/*!
@@ -475,18 +494,9 @@ QVector3D QGraphicsRotation::axis() const
void QGraphicsRotation::setAxis(const QVector3D &axis)
{
Q_D(QGraphicsRotation);
- if (d->axis == axis)
+ if (d->axis == axis)
return;
- d->axis = axis;
- if (axis == VECTOR_FOR_AXIS_X) {
- d->simpleAxis = Qt::XAxis;
- } else if (axis == VECTOR_FOR_AXIS_Y) {
- d->simpleAxis = Qt::YAxis;
- } else if (axis == VECTOR_FOR_AXIS_Z) {
- d->simpleAxis = Qt::ZAxis;
- } else {
- d->simpleAxis = -1; // no predefined axis
- }
+ d->axis = axis;
update();
emit axisChanged();
}
@@ -495,90 +505,58 @@ void QGraphicsRotation::setAxis(const QVector3D &axis)
\fn void QGraphicsRotation::setAxis(Qt::Axis axis)
Convenience function to set the axis to \a axis.
-*/
+ Note: the Qt::YAxis rotation for QTransform is inverted from the
+ correct mathematical rotation in 3D space. The QGraphicsRotation
+ class implements a correct mathematical rotation. The following
+ two sequences of code will perform the same transformation:
+
+ \code
+ QTransform t;
+ t.rotate(45, Qt::YAxis);
+
+ QGraphicsRotation r;
+ r.setAxis(Qt::YAxis);
+ r.setAngle(-45);
+ \endcode
+*/
void QGraphicsRotation::setAxis(Qt::Axis axis)
{
switch (axis)
{
case Qt::XAxis:
- setAxis(VECTOR_FOR_AXIS_X);
+ setAxis(QVector3D(1, 0, 0));
break;
case Qt::YAxis:
- setAxis(VECTOR_FOR_AXIS_Y);
+ setAxis(QVector3D(0, 1, 0));
break;
case Qt::ZAxis:
- setAxis(VECTOR_FOR_AXIS_Z);
+ setAxis(QVector3D(0, 0, 1));
break;
}
}
-
-const qreal deg2rad = qreal(0.017453292519943295769); // pi/180
-static const qreal inv_dist_to_plane = 1. / 1024.;
-
/*!
\reimp
*/
-void QGraphicsRotation::applyTo(QTransform *t) const
+void QGraphicsRotation::applyTo(QMatrix4x4 *matrix) const
{
Q_D(const QGraphicsRotation);
- qreal a = d->angle;
-
- if (a == 0.)
- return;
-
- if (d->simpleAxis != -1) {
- //that's an optimization for simple axis
- t->translate(d->origin.x(), d->origin.y());
- t->rotate(a, Qt::Axis(d->simpleAxis));
- t->translate(-d->origin.x(), -d->origin.y());
- return;
- }
-
- qreal x = d->axis.x();
- qreal y = d->axis.y();
- qreal z = d->axis.z();
-
- if (x == 0. && y == 0 && z == 0)
+ if (d->angle == 0. || d->axis.isNull())
return;
- qreal c, s;
- if (a == 90. || a == -270.) {
- s = 1.;
- c = 0.;
- } else if (a == 270. || a == -90.) {
- s = -1.;
- c = 0.;
- } else if (a == 180.) {
- s = 0.;
- c = -1.;
- } else {
- qreal b = deg2rad*a;
- s = qSin(b);
- c = qCos(b);
- }
-
- qreal len = x * x + y * y + z * z;
- if (len != 1.) {
- len = 1. / qSqrt(len);
- x *= len;
- y *= len;
- z *= len;
- }
-
- t->translate(d->origin.x(), d->origin.y());
- *t = QTransform(x*x*(1-c)+c, x*y*(1-c)+z*s, x*z*(1-c)-y*s*inv_dist_to_plane,
- y*x*(1-c)-z*s, y*y*(1-c)+c, y*z*(1-c)-x*s*inv_dist_to_plane,
- 0, 0, 1) * *t;
- t->translate(-d->origin.x(), -d->origin.y());
+ matrix->translate(d->origin);
+ matrix->rotate(d->angle, d->axis.x(), d->axis.y(), d->axis.z());
+ matrix->translate(-d->origin);
}
/*!
\fn void QGraphicsRotation::axisChanged()
This signal is emitted whenever the axis of the object changes.
+
+ \sa QGraphicsRotation::axis
*/
#include "moc_qgraphicstransform.cpp"
diff --git a/src/gui/graphicsview/qgraphicstransform.h b/src/gui/graphicsview/qgraphicstransform.h
index 8ccc25854..d6d5b79f1 100644
--- a/src/gui/graphicsview/qgraphicstransform.h
+++ b/src/gui/graphicsview/qgraphicstransform.h
@@ -43,8 +43,9 @@
#define QGRAPHICSTRANSFORM_H
#include <QtCore/QObject>
-#include <QtGui/QTransform>
#include <QtGui/QVector3D>
+#include <QtGui/QTransform>
+#include <QtGui/QMatrix4x4>
QT_BEGIN_HEADER
@@ -62,8 +63,7 @@ public:
QGraphicsTransform(QObject *parent = 0);
~QGraphicsTransform();
- QTransform transform() const;
- virtual void applyTo(QTransform *transform) const = 0;
+ virtual void applyTo(QMatrix4x4 *matrix) const = 0;
protected Q_SLOTS:
void update();
@@ -83,15 +83,16 @@ class Q_GUI_EXPORT QGraphicsScale : public QGraphicsTransform
{
Q_OBJECT
- Q_PROPERTY(QPointF origin READ origin WRITE setOrigin NOTIFY originChanged)
+ Q_PROPERTY(QVector3D origin READ origin WRITE setOrigin NOTIFY originChanged)
Q_PROPERTY(qreal xScale READ xScale WRITE setXScale NOTIFY scaleChanged)
Q_PROPERTY(qreal yScale READ yScale WRITE setYScale NOTIFY scaleChanged)
+ Q_PROPERTY(qreal zScale READ zScale WRITE setZScale NOTIFY scaleChanged)
public:
QGraphicsScale(QObject *parent = 0);
~QGraphicsScale();
- QPointF origin() const;
- void setOrigin(const QPointF &point);
+ QVector3D origin() const;
+ void setOrigin(const QVector3D &point);
qreal xScale() const;
void setXScale(qreal);
@@ -99,7 +100,10 @@ public:
qreal yScale() const;
void setYScale(qreal);
- void applyTo(QTransform *transform) const;
+ qreal zScale() const;
+ void setZScale(qreal);
+
+ void applyTo(QMatrix4x4 *matrix) const;
Q_SIGNALS:
void originChanged();
@@ -115,15 +119,15 @@ class Q_GUI_EXPORT QGraphicsRotation : public QGraphicsTransform
{
Q_OBJECT
- Q_PROPERTY(QPointF origin READ origin WRITE setOrigin NOTIFY originChanged)
+ Q_PROPERTY(QVector3D origin READ origin WRITE setOrigin NOTIFY originChanged)
Q_PROPERTY(qreal angle READ angle WRITE setAngle NOTIFY angleChanged)
Q_PROPERTY(QVector3D axis READ axis WRITE setAxis NOTIFY axisChanged)
public:
QGraphicsRotation(QObject *parent = 0);
~QGraphicsRotation();
- QPointF origin() const;
- void setOrigin(const QPointF &point);
+ QVector3D origin() const;
+ void setOrigin(const QVector3D &point);
qreal angle() const;
void setAngle(qreal);
@@ -132,7 +136,7 @@ public:
void setAxis(const QVector3D &axis);
void setAxis(Qt::Axis axis);
- void applyTo(QTransform *transform) const;
+ void applyTo(QMatrix4x4 *matrix) const;
Q_SIGNALS:
void originChanged();
diff --git a/src/gui/graphicsview/qsimplex_p.cpp b/src/gui/graphicsview/qsimplex_p.cpp
new file mode 100644
index 000000000..7fa5ab025
--- /dev/null
+++ b/src/gui/graphicsview/qsimplex_p.cpp
@@ -0,0 +1,371 @@
+#include "qsimplex_p.h"
+
+#include <QtCore/qset.h>
+#include <QtCore/qdebug.h>
+
+#include <stdlib.h>
+
+QT_BEGIN_NAMESPACE
+
+QSimplex::QSimplex() : objective(0), rows(0), columns(0), firstArtificial(0), matrix(0)
+{
+}
+
+QSimplex::~QSimplex()
+{
+ clearDataStructures();
+}
+
+void QSimplex::clearDataStructures()
+{
+ if (matrix == 0)
+ return;
+
+ // Matrix
+ rows = 0;
+ columns = 0;
+ firstArtificial = 0;
+ free(matrix);
+ matrix = 0;
+
+ // Constraints
+ for (int i = 0; i < constraints.size(); ++i) {
+ delete constraints[i]->helper.first;
+ constraints[i]->helper.first = 0;
+ constraints[i]->helper.second = 0.0;
+ delete constraints[i]->artificial;
+ constraints[i]->artificial = 0;
+ }
+ constraints.clear();
+
+ // Other
+ variables.clear();
+ objective = 0;
+}
+
+void QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
+{
+ clearDataStructures();
+
+ if (newConstraints.isEmpty())
+ return;
+ constraints = newConstraints;
+
+ // Set Variables direct mapping
+ QSet<QSimplexVariable *> variablesSet;
+ for (int i = 0; i < constraints.size(); ++i)
+ variablesSet += \
+ QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
+ variables = variablesSet.toList();
+
+ // Set Variables reverse mapping
+ for (int i = 0; i < variables.size(); ++i) {
+ // The variable "0" goes at the column "1", etc...
+ variables[i]->index = i + 1;
+ }
+
+ // Normalize Constraints
+ int variableIndex = variables.size();
+ QList <QSimplexVariable *> artificialList;
+
+ for (int i = 0; i < constraints.size(); ++i) {
+ QSimplexVariable *slack;
+ QSimplexVariable *surplus;
+ QSimplexVariable *artificial;
+
+ Q_ASSERT(constraints[i]->helper.first == 0);
+ Q_ASSERT(constraints[i]->artificial == 0);
+
+ switch(constraints[i]->ratio) {
+ case QSimplexConstraint::LessOrEqual:
+ slack = new QSimplexVariable;
+ slack->index = ++variableIndex;
+ constraints[i]->helper.first = slack;
+ constraints[i]->helper.second = 1.0;
+ break;
+ case QSimplexConstraint::MoreOrEqual:
+ surplus = new QSimplexVariable;
+ surplus->index = ++variableIndex;
+ constraints[i]->helper.first = surplus;
+ constraints[i]->helper.second = -1.0;
+ // fall through
+ case QSimplexConstraint::Equal:
+ artificial = new QSimplexVariable;
+ constraints[i]->artificial = artificial;
+ artificialList += constraints[i]->artificial;
+ break;
+ }
+ }
+
+ firstArtificial = variableIndex + 1;
+ for (int i = 0; i < artificialList.size(); ++i)
+ artificialList[i]->index = ++variableIndex;
+ artificialList.clear();
+
+ // Matrix
+
+ // One for each variable plus the Basic and BFS columns (first and last)
+ columns = variableIndex + 2;
+ // One for each constraint plus the objective function
+ rows = constraints.size() + 1;
+
+ matrix = (qreal *)malloc(sizeof(qreal) * columns * rows);
+ if (!matrix) {
+ qWarning() << "QSimplex: Unable to allocate memory!";
+ return;
+ }
+ for (int i = columns * rows - 1; i >= 0; --i)
+ matrix[i] = 0.0;
+
+ // Fill Matrix
+ for (int i = 1; i <= constraints.size(); ++i) {
+ QSimplexConstraint *c = constraints[i - 1];
+
+ if (c->artificial) {
+ // Will use artificial basic variable
+ setValueAt(i, 0, c->artificial->index);
+ setValueAt(i, c->artificial->index, 1.0);
+
+ if (c->helper.second != 0.0) {
+ // Surplus variable
+ setValueAt(i, c->helper.first->index, c->helper.second);
+ }
+ } else {
+ // Slack is used as the basic variable
+ Q_ASSERT(c->helper.second == 1.0);
+ setValueAt(i, 0, c->helper.first->index);
+ setValueAt(i, c->helper.first->index, 1.0);
+ }
+
+ QHash<QSimplexVariable *, qreal>::const_iterator iter;
+ for (iter = c->variables.constBegin();
+ iter != c->variables.constEnd();
+ ++iter) {
+ setValueAt(i, iter.key()->index, iter.value());
+ }
+
+ setValueAt(i, columns - 1, c->constant);
+ }
+
+ // Set temporary objective: -1 * sum_of_artificial_vars
+ for (int j = firstArtificial; j < columns - 1; ++j)
+ setValueAt(0, j, 1.0);
+
+ // Maximize our objective (artificial vars go to zero)
+ solveMaxHelper();
+
+ if (valueAt(0, columns - 1) != 0.0) {
+ qWarning() << "QSimplex: No feasible solution!";
+ clearDataStructures();
+ return;
+ }
+
+ // Remove artificial variables
+ clearColumns(firstArtificial, columns - 2);
+}
+
+void QSimplex::solveMaxHelper()
+{
+ reducedRowEchelon();
+ while (iterate()) ;
+}
+
+void QSimplex::setObjective(QSimplexConstraint *newObjective)
+{
+ objective = newObjective;
+}
+
+void QSimplex::clearRow(int rowIndex)
+{
+ qreal *item = matrix + rowIndex * columns;
+ for (int i = 0; i < columns; ++i)
+ item[i] = 0.0;
+}
+
+void QSimplex::clearColumns(int first, int last)
+{
+ for (int i = 0; i < rows; ++i) {
+ qreal *row = matrix + i * columns;
+ for (int j = first; j <= last; ++j)
+ row[j] = 0.0;
+ }
+}
+
+void QSimplex::dumpMatrix()
+{
+ printf("---- Simplex Matrix ----\n");
+
+ printf(" ");
+ for (int j = 0; j < columns; ++j)
+ printf(" <% 2d >", j);
+ printf("\n");
+
+ for (int i = 0; i < rows; ++i) {
+ printf("Row %2d:", i);
+
+ qreal *row = matrix + i * columns;
+ for (int j = 0; j < columns; ++j) {
+ printf(" % 2.2f", row[j]);
+ }
+ printf("\n");
+ }
+ printf("------------------------\n\n");
+}
+
+void QSimplex::combineRows(int toIndex, int fromIndex, qreal factor)
+{
+ if (!factor)
+ return;
+
+ qreal *from = matrix + fromIndex * columns;
+ qreal *to = matrix + toIndex * columns;
+
+ for (int j = 1; j < columns; ++j) {
+ qreal value = from[j];
+
+ // skip to[j] = to[j] + factor*0.0
+ if (value == 0.0)
+ continue;
+
+ to[j] += factor * value;
+
+ // ### Avoid Numerical errors
+ if (qAbs(to[j]) < 0.0000000001)
+ to[j] = 0.0;
+ }
+}
+
+int QSimplex::findPivotColumn()
+{
+ qreal min = 0;
+ int minIndex = -1;
+
+ for (int j = 0; j < columns-1; ++j) {
+ if (valueAt(0, j) < min) {
+ min = valueAt(0, j);
+ minIndex = j;
+ }
+ }
+
+ return minIndex;
+}
+
+int QSimplex::pivotRowForColumn(int column)
+{
+ qreal min = 999999999999.0; // ###
+ int minIndex = -1;
+
+ for (int i = 1; i < rows; ++i) {
+ qreal divisor = valueAt(i, column);
+ if (divisor <= 0)
+ continue;
+
+ qreal quotient = valueAt(i, columns - 1) / divisor;
+ if (quotient < min) {
+ min = quotient;
+ minIndex = i;
+ }
+ }
+
+ return minIndex;
+}
+
+void QSimplex::reducedRowEchelon()
+{
+ for (int i = 1; i < rows; ++i) {
+ int factorInObjectiveRow = valueAt(i, 0);
+ combineRows(0, i, -1 * valueAt(0, factorInObjectiveRow));
+ }
+}
+
+bool QSimplex::iterate()
+{
+ // Find Pivot column
+ int pivotColumn = findPivotColumn();
+ if (pivotColumn == -1)
+ return false;
+
+ // Find Pivot row for column
+ int pivotRow = pivotRowForColumn(pivotColumn);
+ if (pivotRow == -1) {
+ qWarning() << "QSimplex: Unbounded problem!";
+ return false;
+ }
+
+ // Normalize Pivot Row
+ qreal pivot = valueAt(pivotRow, pivotColumn);
+ if (pivot != 1.0)
+ combineRows(pivotRow, pivotRow, (1.0 - pivot) / pivot);
+
+ // Update other rows
+ for (int row=0; row < rows; ++row) {
+ if (row == pivotRow)
+ continue;
+
+ combineRows(row, pivotRow, -1 * valueAt(row, pivotColumn));
+ }
+
+ // Update first column
+ setValueAt(pivotRow, 0, pivotColumn);
+
+ // dumpMatrix();
+ // printf("------------ end of iteration --------------\n");
+ return true;
+}
+
+/*!
+ \internal
+
+ Both solveMin and solveMax are interfaces to this method.
+
+ The enum solverFactor admits 2 values: Minimum (-1) and Maximum (+1).
+ */
+qreal QSimplex::solver(solverFactor factor)
+{
+ // Remove old objective
+ clearRow(0);
+
+ // Set new objective
+ QHash<QSimplexVariable *, qreal>::const_iterator iter;
+ for (iter = objective->variables.constBegin();
+ iter != objective->variables.constEnd();
+ ++iter) {
+ setValueAt(0, iter.key()->index, -1 * factor * iter.value());
+ }
+
+ solveMaxHelper();
+ collectResults();
+
+ return factor * valueAt(0, columns - 1);
+}
+
+qreal QSimplex::solveMin()
+{
+ return solver(Minimum);
+}
+
+qreal QSimplex::solveMax()
+{
+ return solver(Maximum);
+}
+
+void QSimplex::collectResults()
+{
+ // All variables are zero unless overridden below.
+
+ // ### Is this really needed? Is there any chance that an
+ // important variable remains as non-basic at the end of simplex?
+ for (int i = 0; i < variables.size(); ++i)
+ variables[i]->result = 0;
+
+ // Basic variables
+ // Update the variable indicated in the first column with the value
+ // in the last column.
+ for (int i = 1; i < rows; ++i) {
+ int index = valueAt(i, 0) - 1;
+ if (index < variables.size())
+ variables[index]->result = valueAt(i, columns - 1);
+ }
+}
+
+QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qsimplex_p.h b/src/gui/graphicsview/qsimplex_p.h
new file mode 100644
index 000000000..e3629dfa7
--- /dev/null
+++ b/src/gui/graphicsview/qsimplex_p.h
@@ -0,0 +1,125 @@
+/****************************************************************************
+**
+** Copyright (C) 1992-$THISYEAR$ $TROLLTECH$. All rights reserved.
+**
+** This file is part of the $MODULE$ of the Qt Toolkit.
+**
+** $TROLLTECH_DUAL_LICENSE$
+**
+** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+**
+****************************************************************************/
+
+#ifndef QSIMPLEX_P_H
+#define QSIMPLEX_P_H
+
+#include <QtCore/qhash.h>
+#include <QtCore/qpair.h>
+
+QT_BEGIN_NAMESPACE
+
+struct QSimplexVariable
+{
+ QSimplexVariable() : result(0), index(0) {};
+
+ qreal result;
+ uint index;
+};
+
+
+/*!
+ \internal
+
+ Representation of a LP constraint like:
+
+ (c1 * X1) + (c2 * X2) + ... = K
+ or <= K
+ or >= K
+
+ Where (ci, Xi) are the pairs in "variables" and K the real "constant".
+*/
+struct QSimplexConstraint
+{
+ QSimplexConstraint() : constant(0), ratio(Equal), artificial(0) {};
+
+ enum Ratio {
+ LessOrEqual = 0,
+ Equal,
+ MoreOrEqual
+ };
+
+ QHash<QSimplexVariable *, qreal> variables;
+ qreal constant;
+ Ratio ratio;
+
+ QPair<QSimplexVariable *, qreal> helper;
+ QSimplexVariable * artificial;
+};
+
+
+class QSimplex
+{
+public:
+ QSimplex();
+ virtual ~QSimplex();
+
+ qreal solveMin();
+ qreal solveMax();
+ QList<QSimplexVariable *> constraintsVariables();
+
+ void setConstraints(const QList<QSimplexConstraint *> constraints);
+ void setObjective(QSimplexConstraint *objective);
+
+ void dumpMatrix();
+
+private:
+ // Matrix handling
+ qreal valueAt(int row, int column);
+ void setValueAt(int row, int column, qreal value);
+ void clearRow(int rowIndex);
+ void clearColumns(int first, int last);
+ void combineRows(int toIndex, int fromIndex, qreal factor);
+
+ // Simplex
+ int findPivotColumn();
+ int pivotRowForColumn(int column);
+ void reducedRowEchelon();
+ bool iterate();
+
+ // Helpers
+ void clearDataStructures();
+ void solveMaxHelper();
+ enum solverFactor { Minimum = -1, Maximum = 1 };
+ qreal solver(solverFactor factor);
+ void collectResults();
+
+ QList<QSimplexConstraint *> constraints;
+ QList<QSimplexVariable *> variables;
+ QSimplexConstraint *objective;
+
+ int rows;
+ int columns;
+ int firstArtificial;
+
+ qreal *matrix;
+};
+
+inline QList<QSimplexVariable *> QSimplex::constraintsVariables()
+{
+ return variables;
+}
+
+inline qreal QSimplex::valueAt(int rowIndex, int columnIndex)
+{
+ return matrix[rowIndex * columns + columnIndex];
+}
+
+inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value)
+{
+ matrix[rowIndex * columns + columnIndex] = value;
+}
+
+QT_END_NAMESPACE
+
+#endif // QSIMPLEX_P_H
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-13 18:17:57 +0000