diff -r 000000000000 -r 1918ee327afb src/gui/graphicsview/qgraph_p.h --- /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 +#include +#include +#include + +#include + +QT_BEGIN_NAMESPACE + +template +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 * >::const_iterator row; + Q_TYPENAME QHash::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 *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 adjacentVertices(Vertex *vertex) const + { + QHash *row = m_graph.value(vertex); + QList l; + if (row) + l = row->keys(); + return l; + } + + void setRootVertex(Vertex *vertex) + { + userVertex = vertex; + } + + QSet vertices() const { + QSet setOfVertices; + for (const_iterator it = constBegin(); it != constEnd(); ++it) { + setOfVertices.insert(*it); + } + return setOfVertices; + } + + QList > connections() const { + QList > 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 setOfVertices = vertices(); + for (Q_TYPENAME QSet::const_iterator it = setOfVertices.begin(); it != setOfVertices.end(); ++it) { + Vertex *v = *it; + QList 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 *adjacentToFirst = m_graph.value(from); + if (!adjacentToFirst) { + adjacentToFirst = new QHash(); + m_graph.insert(from, adjacentToFirst); + } + adjacentToFirst->insert(to, data); + } + + void removeDirectedEdge(Vertex *from, Vertex *to) + { + QHash *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 *> m_graph; +}; + +QT_END_NAMESPACE + +#endif