summaryrefslogtreecommitdiff
path: root/Build/source/texk/dvisvgm/dvisvgm-1.9.2/src/DependencyGraph.h
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/dvisvgm/dvisvgm-1.9.2/src/DependencyGraph.h')
-rw-r--r--Build/source/texk/dvisvgm/dvisvgm-1.9.2/src/DependencyGraph.h122
1 files changed, 122 insertions, 0 deletions
diff --git a/Build/source/texk/dvisvgm/dvisvgm-1.9.2/src/DependencyGraph.h b/Build/source/texk/dvisvgm/dvisvgm-1.9.2/src/DependencyGraph.h
new file mode 100644
index 00000000000..e00a68ffbd1
--- /dev/null
+++ b/Build/source/texk/dvisvgm/dvisvgm-1.9.2/src/DependencyGraph.h
@@ -0,0 +1,122 @@
+/*************************************************************************
+** DependencyGraph.h **
+** **
+** This file is part of dvisvgm -- the DVI to SVG converter **
+** Copyright (C) 2005-2015 Martin Gieseking <martin.gieseking@uos.de> **
+** **
+** This program is free software; you can redistribute it and/or **
+** modify it under the terms of the GNU General Public License as **
+** published by the Free Software Foundation; either version 3 of **
+** the License, or (at your option) any later version. **
+** **
+** This program is distributed in the hope that it will be useful, but **
+** WITHOUT ANY WARRANTY; without even the implied warranty of **
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the **
+** GNU General Public License for more details. **
+** **
+** You should have received a copy of the GNU General Public License **
+** along with this program; if not, see <http://www.gnu.org/licenses/>. **
+*************************************************************************/
+
+
+#ifndef DEPENDENCYGRAPH_H
+#define DEPENDENCYGRAPH_H
+
+#include <map>
+#include <vector>
+
+template <typename T>
+class DependencyGraph
+{
+ struct GraphNode {
+ typedef typename std::vector<GraphNode*> Dependees;
+ typedef typename Dependees::iterator Iterator;
+
+ GraphNode (const T &k) : key(k), dependent(0) {}
+
+ void addDependee (GraphNode *node) {
+ if (node) {
+ node->dependent = this;
+ dependees.push_back(node);
+ }
+ }
+
+ void deleteDependentsAndSelf () {
+ if (dependent)
+ dependent->deleteDependentsAndSelf();
+ for (typename Dependees::iterator it = dependees.begin(); it != dependees.end(); ++it)
+ (*it)->dependent = 0;
+ delete this;
+ }
+
+ T key;
+ GraphNode *dependent;
+ Dependees dependees;
+ };
+
+ typedef std::map<T, GraphNode*> NodeMap;
+
+ public:
+ ~DependencyGraph() {
+ for (typename NodeMap::iterator it=_nodeMap.begin(); it != _nodeMap.end(); ++it)
+ delete it->second;
+ }
+
+ void insert (const T &key) {
+ if (!contains(key))
+ _nodeMap[key] = new GraphNode(key);
+ }
+
+ void insert (const T &depKey, const T &key) {
+ if (contains(key))
+ return;
+ typename NodeMap::iterator it = _nodeMap.find(depKey);
+ if (it != _nodeMap.end()) {
+ GraphNode *node = new GraphNode(key);
+ it->second->addDependee(node);
+ _nodeMap[key] = node;
+ }
+ }
+
+ void removeDependencyPath (const T &key) {
+ typename NodeMap::iterator it = _nodeMap.find(key);
+ if (it != _nodeMap.end()) {
+ GraphNode *startNode = it->second;
+ for (GraphNode *node=startNode; node; node=node->dependent)
+ _nodeMap.erase(node->key);
+ startNode->deleteDependentsAndSelf();
+ }
+ }
+
+ void getKeys (std::vector<T> &keys) const {
+ for (typename NodeMap::const_iterator it=_nodeMap.begin(); it != _nodeMap.end(); ++it)
+ keys.push_back(it->first);
+ }
+
+ bool contains (const T &value) const {
+ return _nodeMap.find(value) != _nodeMap.end();
+ }
+
+ bool empty () const {
+ return _nodeMap.empty();
+ }
+
+#if 0
+ void writeDOT (std::ostream &os) const {
+ os << "digraph {\n";
+ for (typename NodeMap::const_iterator it=_nodeMap.begin(); it != _nodeMap.end(); ++it) {
+ GraphNode *node = it->second;
+ if (node->dependent)
+ os << (node->key) << " -> " << (node->dependent->key) << ";\n";
+ else if (node->dependees.empty())
+ os << (node->key) << ";\n";
+ }
+ os << "}\n";
+ }
+#endif
+
+ private:
+ NodeMap _nodeMap;
+};
+
+#endif