1 files changed, 158 insertions, 0 deletions
diff --git a/src/libs/installer/graph.h b/src/libs/installer/graph.h
new file mode 100644
index 000000000..59778a440
--- /dev/null
+++ b/src/libs/installer/graph.h
@@ -0,0 +1,158 @@
+/**************************************************************************
+**
+** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of the Qt Installer Framework.
+**
+** $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 Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/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 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, Digia gives you certain additional
+** rights.  These rights are described in the Digia 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.
+**
+**
+** $QT_END_LICENSE$
+**
+**************************************************************************/
+
+#ifndef GRAPH_H
+#define GRAPH_H
+
+#include <QHash>
+#include <QList>
+#include <QPair>
+#include <QSet>
+
+namespace QInstaller {
+
+template <class T> class Graph
+{
+public:
+    inline Graph() {}
+    explicit Graph(const QList<T> &nodes)
+    {
+        addNodes(nodes);
+    }
+
+    const QList<T> nodes() const
+    {
+        return m_graph.keys();
+    }
+
+    void addNode(const T &node)
+    {
+        m_graph.insert(node, QSet<T>());
+    }
+
+    void addNodes(const QList<T> &nodes)
+    {
+        foreach (const T &node, nodes)
+            addNode(node);
+    }
+
+    QList<T> edges(const T &node) const
+    {
+        return m_graph.value(node).toList();
+    }
+
+    void addEdge(const T &node, const T &edge)
+    {
+        m_graph[node].insert(edge);
+    }
+
+    void addEdges(const T &node, const QList<T> &edges)
+    {
+        foreach (const T &edge, edges)
+            addEdge(node, edge);
+    }
+
+    bool hasCycle() const
+    {
+        return m_hasCycle;
+    }
+
+    QPair<T, T> cycle() const
+    {
+        return m_cycle;
+    }
+
+    QList<T> sort() const
+    {
+        QSet<T> visitedNodes;
+        QList<T> resolvedNodes;
+
+        m_hasCycle = false;
+        m_cycle = qMakePair(T(), T());
+        foreach (const T &node, nodes())
+            visit(node, &resolvedNodes, &visitedNodes);
+        return resolvedNodes;
+    }
+
+    QList<T> sortReverse() const
+    {
+        QList<T> result = sort();
+        std::reverse(result.begin(), result.end());
+        return result;
+    }
+
+private:
+    void visit(const T &node, QList<T> *const resolvedNodes, QSet<T> *const visitedNodes) const
+    {
+        if (m_hasCycle)
+            return;
+
+        // if we visited this node already
+        if (visitedNodes->contains(node)) {
+            // and if the node is already in the ordered list
+            if (resolvedNodes->contains(node))
+                return;
+
+            m_hasCycle = true;
+            m_cycle.second = node;
+            return; // if not yet in the ordered list, we detected a cycle
+        }
+
+        // mark this node as visited
+        visitedNodes->insert(node);
+
+        m_cycle.first = node;
+        // recursively visit all adjacency
+        foreach (const T &adjacency, edges(node))
+            visit(adjacency, resolvedNodes, visitedNodes);
+
+        // append this node the the ordered list
+        resolvedNodes->append(node);
+    }
+
+private:
+    mutable bool m_hasCycle;
+    QHash<T, QSet<T> > m_graph;
+    mutable QPair<T,T> m_cycle;
+};
+
+}
+#endif // GRAPH_H