diff options
Diffstat (limited to 'src/widgets/graphicsview/qgraph_p.h')
| -rw-r--r-- | src/widgets/graphicsview/qgraph_p.h | 286 |
1 files changed, 286 insertions, 0 deletions
diff --git a/src/widgets/graphicsview/qgraph_p.h b/src/widgets/graphicsview/qgraph_p.h new file mode 100644 index 0000000000..3b9d839a17 --- /dev/null +++ b/src/widgets/graphicsview/qgraph_p.h @@ -0,0 +1,286 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** GNU Lesser General Public License Usage +** This file may be used under the terms of the GNU Lesser General Public +** License version 2.1 as published by the Free Software Foundation and +** appearing in the file LICENSE.LGPL included in the packaging of this +** file. Please review the following information to ensure the GNU Lesser +** General Public License version 2.1 requirements will be met: +** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** 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. +** +** Other Usage +** Alternatively, this file may be used in accordance with the terms and +** conditions contained in a signed written agreement between you and Nokia. +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QGRAPH_P_H +#define QGRAPH_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtCore/QHash> +#include <QtCore/QQueue> +#include <QtCore/QString> +#include <QtCore/QDebug> + +#include <float.h> + +QT_BEGIN_NAMESPACE + +template <typename Vertex, typename EdgeData> +class Graph +{ +public: + Graph() {} + + class const_iterator { + public: + const_iterator(const Graph *graph, bool begin) : g(graph){ + if (begin) { + row = g->m_graph.constBegin(); + //test if the graph is empty + if (row != g->m_graph.constEnd()) + { + column = (*row)->constBegin(); + } + } else { + row = g->m_graph.constEnd(); + } + } + + inline Vertex *operator*() { + return column.key(); + } + + inline Vertex *from() const { + return row.key(); + } + + inline Vertex *to() const { + return column.key(); + } + + inline bool operator==(const const_iterator &o) const { return !(*this != o); } + inline bool operator!=(const const_iterator &o) const { + if (row == g->m_graph.end()) { + return row != o.row; + } else { + return row != o.row || column != o.column; + } + } + inline const_iterator& operator=(const const_iterator &o) const { row = o.row; column = o.column; return *this;} + + // prefix + const_iterator &operator++() { + if (row != g->m_graph.constEnd()) { + ++column; + if (column == (*row)->constEnd()) { + ++row; + if (row != g->m_graph.constEnd()) { + column = (*row)->constBegin(); + } + } + } + return *this; + } + + private: + const Graph *g; + Q_TYPENAME QHash<Vertex *, QHash<Vertex *, EdgeData *> * >::const_iterator row; + Q_TYPENAME QHash<Vertex *, EdgeData *>::const_iterator column; + }; + + const_iterator constBegin() const { + return const_iterator(this,true); + } + + const_iterator constEnd() const { + return const_iterator(this,false); + } + + /*! + * \internal + * + * If there is an edge between \a first and \a second, it will return a structure + * containing the data associated with the edge, otherwise it will return 0. + * + */ + EdgeData *edgeData(Vertex* first, Vertex* second) { + QHash<Vertex *, EdgeData *> *row = m_graph.value(first); + return row ? row->value(second) : 0; + } + + void createEdge(Vertex *first, Vertex *second, EdgeData *data) + { + // Creates a bidirectional edge +#if defined(QT_DEBUG) && 0 + qDebug("Graph::createEdge(): %s", + qPrintable(QString::fromAscii("%1-%2") + .arg(first->toString()).arg(second->toString()))); +#endif + if (edgeData(first, second)) { +#ifdef QT_DEBUG + qWarning("%s-%s already has an edge", qPrintable(first->toString()), qPrintable(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; + } + + 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,%6,%7]\" color=\"#000000\"] \n") + .arg(v->toString()) + .arg(v1->toString()) + .arg(data->minSize) + .arg(data->minPrefSize) + .arg(data->prefSize) + .arg(data->maxPrefSize) + .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 + +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: + QHash<Vertex *, QHash<Vertex *, EdgeData *> *> m_graph; +}; + +QT_END_NAMESPACE + +#endif |