--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/gui/graphicsview/qgraph_p.h Mon Jan 11 14:00:40 2010 +0000
@@ -0,0 +1,296 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the 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 Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#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;
+ }
+
+ void setRootVertex(Vertex *vertex)
+ {
+ userVertex = vertex;
+ }
+
+ QSet<Vertex*> vertices() const {
+ QSet<Vertex *> setOfVertices;
+ for (const_iterator it = constBegin(); it != constEnd(); ++it) {
+ setOfVertices.insert(*it);
+ }
+ return setOfVertices;
+ }
+
+ QList<QPair<Vertex*, Vertex*> > connections() const {
+ QList<QPair<Vertex*, Vertex*> > conns;
+ for (const_iterator it = constBegin(); it != constEnd(); ++it) {
+ Vertex *from = it.from();
+ Vertex *to = it.to();
+ // do not return (from,to) *and* (to,from)
+ if (from < to) {
+ conns.append(qMakePair(from, to));
+ }
+ }
+ return conns;
+ }
+
+#if defined(QT_DEBUG)
+ QString serializeToDot() { // traversal
+ QString strVertices;
+ QString edges;
+
+ QSet<Vertex *> setOfVertices = vertices();
+ for (Q_TYPENAME QSet<Vertex*>::const_iterator it = setOfVertices.begin(); it != setOfVertices.end(); ++it) {
+ Vertex *v = *it;
+ QList<Vertex*> adjacents = adjacentVertices(v);
+ for (int i = 0; i < adjacents.count(); ++i) {
+ Vertex *v1 = adjacents.at(i);
+ EdgeData *data = edgeData(v, v1);
+ bool forward = data->from == v;
+ if (forward) {
+ edges += QString::fromAscii("%1->%2 [label=\"[%3,%4,%5]\" dir=both color=\"#000000:#a0a0a0\"] \n")
+ .arg(v->toString())
+ .arg(v1->toString())
+ .arg(data->minSize)
+ .arg(data->prefSize)
+ .arg(data->maxSize)
+ ;
+ }
+ }
+ strVertices += QString::fromAscii("%1 [label=\"%2\"]\n").arg(v->toString()).arg(v->toString());
+ }
+ return QString::fromAscii("%1\n%2\n").arg(strVertices).arg(edges);
+ }
+#endif
+
+ Vertex *rootVertex() const
+ {
+ return userVertex;
+ }
+
+protected:
+ void createDirectedEdge(Vertex *from, Vertex *to, EdgeData *data)
+ {
+ QHash<Vertex *, EdgeData *> *adjacentToFirst = m_graph.value(from);
+ if (!adjacentToFirst) {
+ adjacentToFirst = new QHash<Vertex *, EdgeData *>();
+ m_graph.insert(from, adjacentToFirst);
+ }
+ adjacentToFirst->insert(to, data);
+ }
+
+ void removeDirectedEdge(Vertex *from, Vertex *to)
+ {
+ QHash<Vertex *, EdgeData *> *adjacentToFirst = m_graph.value(from);
+ Q_ASSERT(adjacentToFirst);
+
+ adjacentToFirst->remove(to);
+ if (adjacentToFirst->isEmpty()) {
+ //nobody point to 'from' so we can remove it from the graph
+ m_graph.remove(from);
+ delete adjacentToFirst;
+ }
+ }
+
+private:
+ Vertex *userVertex;
+
+ QHash<Vertex *, QHash<Vertex *, EdgeData *> *> m_graph;
+};
+
+QT_END_NAMESPACE
+
+#endif