diff options
Diffstat (limited to 'src/gui')
| -rw-r--r-- | src/gui/graphicsview/graphicsview.pri | 12 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraph_p.h | 236 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsanchorlayout.cpp | 449 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsanchorlayout.h | 141 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsanchorlayout_p.cpp | 2097 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsanchorlayout_p.h | 474 | ||||
| -rw-r--r-- | src/gui/graphicsview/qsimplex_p.cpp | 368 | ||||
| -rw-r--r-- | src/gui/graphicsview/qsimplex_p.h | 122 |
8 files changed, 3897 insertions, 2 deletions
diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri index 9d232e4..547d7ce 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 0000000..c228902 --- /dev/null +++ b/src/gui/graphicsview/qgraph_p.h @@ -0,0 +1,236 @@ +#include <QtCore/QHash> +#include <QtCore/QQueue> +#include <QtCore/QString> +#include <QtCore/QDebug> + +#include <float.h> + +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; +}; diff --git a/src/gui/graphicsview/qgraphicsanchorlayout.cpp b/src/gui/graphicsview/qgraphicsanchorlayout.cpp new file mode 100644 index 0000000..5032dc6 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsanchorlayout.cpp @@ -0,0 +1,449 @@ +/**************************************************************************** +** +** 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" + +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); +} diff --git a/src/gui/graphicsview/qgraphicsanchorlayout.h b/src/gui/graphicsview/qgraphicsanchorlayout.h new file mode 100644 index 0000000..3de9ae5 --- /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 0000000..ffece0d --- /dev/null +++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp @@ -0,0 +1,2097 @@ +/**************************************************************************** +** +** 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 <QWidget> +#include <QLinkedList> +#include <QtCore/qstack.h> + +#include "qgraphicsanchorlayout_p.h" + +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 +#include <QFile> +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 diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.h b/src/gui/graphicsview/qgraphicsanchorlayout_p.h new file mode 100644 index 0000000..e17bd28 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.h @@ -0,0 +1,474 @@ +/**************************************************************************** +** +** 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" + +/* + 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; +}; + diff --git a/src/gui/graphicsview/qsimplex_p.cpp b/src/gui/graphicsview/qsimplex_p.cpp new file mode 100644 index 0000000..1349ced --- /dev/null +++ b/src/gui/graphicsview/qsimplex_p.cpp @@ -0,0 +1,368 @@ +#include "qsimplex_p.h" + +#include <QtCore/qset.h> +#include <QtCore/qdebug.h> + +#include <stdlib.h> + +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); + } +} diff --git a/src/gui/graphicsview/qsimplex_p.h b/src/gui/graphicsview/qsimplex_p.h new file mode 100644 index 0000000..dad82ce --- /dev/null +++ b/src/gui/graphicsview/qsimplex_p.h @@ -0,0 +1,122 @@ +/**************************************************************************** +** +** 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> + +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; +} + + +#endif |