Windows-4.7.4/src/gui/graphicsview/qgraph_p.h - platform/external/qt - Git at Google

 /****************************************************************************
 **
 ** 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
	/****************************************************************************
	**
	** 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