/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtWidgets module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $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 <QtWidgets/private/qtwidgetsglobal_p.h>
#include <QtCore/QHash>
#include <QtCore/QQueue>
#include <QtCore/QString>
#include <QtCore/QDebug>

#include <functional> // for std::less

#include <float.h>

QT_REQUIRE_CONFIG(graphicsview);

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->cbegin();
            } 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;
           }
        }

        // prefix
        const_iterator &operator++() {
            if (row != g->m_graph.constEnd()) {
                ++column;
                if (column == row->cend()) {
                    ++row;
                    if (row != g->m_graph.constEnd()) {
                        column = row->cbegin();
                    }
                }
            }
            return *this;
        }

    private:
        const Graph *g;
        typename QHash<Vertex *, QHash<Vertex *, EdgeData *> >::const_iterator row;
        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) {
        const auto it = m_graph.constFind(first);
        if (it == m_graph.cend())
            return nullptr;
        const auto jt = it->constFind(second);
        if (jt == it->cend())
            return nullptr;
        return *jt;
    }

    void createEdge(Vertex *first, Vertex *second, EdgeData *data)
    {
        // Creates a bidirectional edge
#if defined(QT_DEBUG) && 0
        qDebug("Graph::createEdge(): %s",
               qPrintable(QString::fromLatin1("%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::fromLatin1("%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::fromLatin1("%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
    {
        const auto it = m_graph.constFind(vertex);
        if (it == m_graph.cend())
            return QList<Vertex *>();
        else
            return it->keys();
    }

    QSet<Vertex*> vertices() const {
        QSet<Vertex *> setOfVertices;
        for (const_iterator it = constBegin(); it != constEnd(); ++it) {
            setOfVertices.insert(*it);
        }
        return setOfVertices;
    }

    QVector<QPair<Vertex*, Vertex*> > connections() const {
        QVector<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 (std::less<Vertex*>()(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 (typename QSet<Vertex*>::const_iterator it = setOfVertices.begin(); it != setOfVertices.end(); ++it) {
            Vertex *v = *it;
            const QList<Vertex*> adjacents = adjacentVertices(v);
            for (auto *v1 : adjacents) {
                EdgeData *data = edgeData(v, v1);
                bool forward = data->from == v;
                if (forward) {
                    edges += QString::fromLatin1("\"%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::fromLatin1("\"%1\" [label=\"%2\"]\n").arg(v->toString()).arg(v->toString());
        }
        return QString::fromLatin1("%1\n%2\n").arg(strVertices, edges);
    }
#endif

protected:
    void createDirectedEdge(Vertex *from, Vertex *to, EdgeData *data)
    {
        m_graph[from][to] = data;
    }

    void removeDirectedEdge(Vertex *from, Vertex *to)
    {
        const auto it = m_graph.find(from);
        Q_ASSERT(it != m_graph.end());

        it->remove(to);
        if (it->isEmpty()) {
            //nobody point to 'from' so we can remove it from the graph
            m_graph.erase(it);
        }
    }

private:
    QHash<Vertex *, QHash<Vertex *, EdgeData *> > m_graph;
};

QT_END_NAMESPACE

#endif