1.1 --- a/src/work/deba/edge_map_base.h Fri Apr 16 13:26:15 2004 +0000
1.2 +++ b/src/work/deba/edge_map_base.h Fri Apr 16 13:42:03 2004 +0000
1.3 @@ -1,18 +1,65 @@
1.4 #ifndef EDGE_MAP_BASE_H
1.5 #define EDGE_MAP_BASE_H
1.6
1.7 -template <class G, class K>
1.8 +/**
1.9 + Template base class for implementing mapping on edges.
1.10 + \param The first template parameter is the Graph class. The Graph
1.11 + must have an \emp edge_maps member with \emp EdgeMapRegistry class.
1.12 + \param The second template parameter is the Edge type of the class.
1.13 +
1.14 +*/
1.15 +
1.16 +template <typename G, typename K>
1.17 class EdgeMapBase {
1.18 public:
1.19 typedef G Graph;
1.20
1.21 typedef K KeyType;
1.22
1.23 + /**
1.24 + Default constructor.
1.25 + */
1.26 +
1.27 EdgeMapBase() : graph(0) {}
1.28 +
1.29 + /**
1.30 + Simple constructor to register into a graph.
1.31 + */
1.32 +
1.33 EdgeMapBase(Graph& g) : graph(&g) {
1.34 graph->edge_maps.add(*this);
1.35 }
1.36
1.37 + /**
1.38 + Copy constructor with registering into the map.
1.39 + */
1.40 +
1.41 + EdgeMapBase(const EdgeMapBase& copy) : graph(copy.graph) {
1.42 + if (graph) {
1.43 + graph->edge_maps.add(*this);
1.44 + }
1.45 + }
1.46 +
1.47 + /**
1.48 + Assign operator.
1.49 + */
1.50 +
1.51 + const EdgeMapBase& operator=(const EdgeMapBase& copy) {
1.52 + if (graph) {
1.53 + graph.edge_maps.erase(*this);
1.54 + }
1.55 + graph = copy.graph;
1.56 + if (graph) {
1.57 + graph->edge_maps.add(*this);
1.58 + }
1.59 +
1.60 + }
1.61 +
1.62 +
1.63 + /**
1.64 + Destructor.
1.65 + */
1.66 +
1.67 virtual ~EdgeMapBase() {
1.68 if (graph) {
1.69 graph.edge_maps.erase(*this);
1.70 @@ -25,20 +72,45 @@
1.71
1.72 int graph_index;
1.73
1.74 + /**
1.75 + Helper function to implement the default constructor in the subclasses.
1.76 + */
1.77 +
1.78 void init() {
1.79 for (Graph::EdgeIt it(g); g.valid(it); g.next(it)) {
1.80 add(it);
1.81 }
1.82 }
1.83
1.84 + /**
1.85 + Helper function to implement the destructor in the subclasses.
1.86 + */
1.87 +
1.88 void destroy() {
1.89 for (Graph::EdgeIt it(g); g.valid(it); g.next(it)) {
1.90 erase(it);
1.91 }
1.92 }
1.93
1.94 + /**
1.95 + The add member function should be overloaded in the subclasses.
1.96 + \e Add extends the map with the new edge.
1.97 + */
1.98 +
1.99 virtual void add(const KeyType&) = 0;
1.100 +
1.101 + /**
1.102 + The erase member function should be overloaded in the subclasses.
1.103 + \e Erase removes the edge from the map.
1.104 + */
1.105 +
1.106 virtual void erase(const KeyType&) = 0;
1.107 +
1.108 + /**
1.109 + Exception class to throw at unsupported operation.
1.110 + */
1.111 +
1.112 + class NotSupportedOperationException {};
1.113
1.114 friend class Graph;
1.115 };
2.1 --- a/src/work/deba/edge_map_registry.h Fri Apr 16 13:26:15 2004 +0000
2.2 +++ b/src/work/deba/edge_map_registry.h Fri Apr 16 13:42:03 2004 +0000
2.3 @@ -3,20 +3,22 @@
2.4
2.5 #include <vector>
2.6
2.7 +#include "edge_map_base.h"
2.8 +
2.9 template <typename G, typename E>
2.10 class EdgeMapRegistry {
2.11 public:
2.12 typedef G Graph;
2.13 typedef E Edge
2.14
2.15 - typedef EdgeMapBase<Graph, Edge> EdgeMapBase;
2.16 + typedef EdgeMapBase<Graph, Edge> MapBase;
2.17
2.18 protected:
2.19 typedef std::vector<EdgeMapBase*> Container;
2.20
2.21 Container container;
2.22
2.23 - void add(EdgeMapBase& map_base) {
2.24 + void add(MapBase& map_base) {
2.25 if (map_base.graph) {
2.26 map_base.graph->edge_maps.erase(map_base);
2.27 }
2.28 @@ -25,7 +27,7 @@
2.29 map_base.graph_index = container.size()-1;
2.30 }
2.31
2.32 - void erase(EdgeMapBase& map_base) {
2.33 + void erase(MapBase& map_base) {
2.34 if (map_base.graph != this) return;
2.35 container.back()->graph_index = map_base.graph_index;
2.36 container[map_base.graph_index] = container.back();
2.37 @@ -33,21 +35,21 @@
2.38 map_base.graph = 0;
2.39 }
2.40
2.41 - void addEdge(Edge& edge) {
2.42 + void add(Edge& edge) {
2.43 typename Container::iterator it;
2.44 for (it = container.begin(); it != container.end(); ++it) {
2.45 (*it)->add(edge);
2.46 }
2.47 }
2.48
2.49 - void eraseEdge(Edge& edge) {
2.50 + void erase(Edge& edge) {
2.51 typename Container::iterator it;
2.52 for (it = container.begin(); it != container.end(); ++it) {
2.53 (*it)->erase(edge);
2.54 }
2.55 }
2.56
2.57 - friend class EdgeMapBase;
2.58 + friend class MapBase;
2.59 };
2.60
2.61 #endif
3.1 --- a/src/work/deba/node_map_base.h Fri Apr 16 13:26:15 2004 +0000
3.2 +++ b/src/work/deba/node_map_base.h Fri Apr 16 13:42:03 2004 +0000
3.3 @@ -1,18 +1,65 @@
3.4 #ifndef NODE_MAP_BASE_H
3.5 #define NODE_MAP_BASE_H
3.6
3.7 -template <class G, class K>
3.8 +/**
3.9 + Template base class for implementing mapping on nodes.
3.10 + \param The first template parameter is the Graph class. The Graph
3.11 + must have an \emp node_maps member with \emp NodeMapRegistry class.
3.12 + \param The second template parameter is the Node type of the class.
3.13 +
3.14 +*/
3.15 +
3.16 +template <typename G, typename K>
3.17 class NodeMapBase {
3.18 public:
3.19 typedef G Graph;
3.20
3.21 typedef K KeyType;
3.22
3.23 + /**
3.24 + Default constructor.
3.25 + */
3.26 +
3.27 NodeMapBase() : graph(0) {}
3.28 +
3.29 + /**
3.30 + Simple constructor to register into a graph.
3.31 + */
3.32 +
3.33 NodeMapBase(Graph& g) : graph(&g) {
3.34 graph->node_maps.add(*this);
3.35 }
3.36
3.37 + /**
3.38 + Copy constructor with registering into the map.
3.39 + */
3.40 +
3.41 + NodeMapBase(const NodeMapBase& copy) : graph(copy.graph) {
3.42 + if (graph) {
3.43 + graph->node_maps.add(*this);
3.44 + }
3.45 + }
3.46 +
3.47 + /**
3.48 + Assign operator.
3.49 + */
3.50 +
3.51 + const NodeMapBase& operator=(const NodeMapBase& copy) {
3.52 + if (graph) {
3.53 + graph.node_maps.erase(*this);
3.54 + }
3.55 + graph = copy.graph;
3.56 + if (graph) {
3.57 + graph->node_maps.add(*this);
3.58 + }
3.59 +
3.60 + }
3.61 +
3.62 +
3.63 + /**
3.64 + Destructor.
3.65 + */
3.66 +
3.67 virtual ~NodeMapBase() {
3.68 if (graph) {
3.69 graph.node_maps.erase(*this);
3.70 @@ -25,20 +72,45 @@
3.71
3.72 int graph_index;
3.73
3.74 + /**
3.75 + Helper function to implement the default constructor in the subclasses.
3.76 + */
3.77 +
3.78 void init() {
3.79 for (Graph::NodeIt it(g); g.valid(it); g.next(it)) {
3.80 add(it);
3.81 }
3.82 }
3.83
3.84 + /**
3.85 + Helper function to implement the destructor in the subclasses.
3.86 + */
3.87 +
3.88 void destroy() {
3.89 for (Graph::NodeIt it(g); g.valid(it); g.next(it)) {
3.90 erase(it);
3.91 }
3.92 }
3.93
3.94 + /**
3.95 + The add member function should be overloaded in the subclasses.
3.96 + \e Add extends the map with the new node.
3.97 + */
3.98 +
3.99 virtual void add(const KeyType&) = 0;
3.100 +
3.101 + /**
3.102 + The erase member function should be overloaded in the subclasses.
3.103 + \e Erase removes the node from the map.
3.104 + */
3.105 +
3.106 virtual void erase(const KeyType&) = 0;
3.107 +
3.108 + /**
3.109 + Exception class to throw at unsupported operation.
3.110 + */
3.111 +
3.112 + class NotSupportedOperationException {};
3.113
3.114 friend class Graph;
3.115 };
4.1 --- a/src/work/deba/node_map_registry.h Fri Apr 16 13:26:15 2004 +0000
4.2 +++ b/src/work/deba/node_map_registry.h Fri Apr 16 13:42:03 2004 +0000
4.3 @@ -3,6 +3,8 @@
4.4
4.5 #include <vector>
4.6
4.7 +#include "node_map_base.h"
4.8 +
4.9 template <typename G, typename E>
4.10 class NodeMapRegistry {
4.11 public:
4.12 @@ -33,14 +35,14 @@
4.13 map_base.graph = 0;
4.14 }
4.15
4.16 - void addNode(Node& node) {
4.17 + void add(Node& node) {
4.18 typename Container::iterator it;
4.19 for (it = container.begin(); it != container.end(); ++it) {
4.20 (*it)->add(node);
4.21 }
4.22 }
4.23
4.24 - void eraseNode(Node& node) {
4.25 + void erase(Node& node) {
4.26 typename Container::iterator it;
4.27 for (it = container.begin(); it != container.end(); ++it) {
4.28 (*it)->erase(node);
5.1 --- a/src/work/deba/test_graph.h Fri Apr 16 13:26:15 2004 +0000
5.2 +++ b/src/work/deba/test_graph.h Fri Apr 16 13:42:03 2004 +0000
5.3 @@ -7,6 +7,12 @@
5.4
5.5 #include <invalid.h>
5.6
5.7 +#include "vector_map.h"
5.8 +#include "edge_map_registry.h"
5.9 +#include "node_map_registry.h"
5.10 +#include "edge_map_base.h"
5.11 +#include "node_map_base.h"
5.12 +
5.13 namespace hugo {
5.14
5.15 template <typename It>
5.16 @@ -28,53 +34,22 @@
5.17 class InEdgeIt;
5.18 class SymEdgeIt;
5.19
5.20 - template <typename T> class NodeMap;
5.21 - template <typename T> class EdgeMap;
5.22 +// template <typename T> class NodeMap;
5.23 +// template <typename T> class EdgeMap;
5.24 private:
5.25 - template <typename T> friend class NodeMap;
5.26 - template <typename T> friend class EdgeMap;
5.27 +// template <typename T> friend class NodeMap;
5.28 + // template <typename T> friend class EdgeMap;
5.29
5.30 - template <typename T>
5.31 - class NodeMap {
5.32 - const ListGraph& G;
5.33 - std::vector<T> container;
5.34 - public:
5.35 - typedef T ValueType;
5.36 - typedef Node KeyType;
5.37 - NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
5.38 - NodeMap(const ListGraph& _G, T a) :
5.39 - G(_G), container(G.node_id, a) { }
5.40 - void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; }
5.41 - T get(Node n) const { return container[/*G.id(n)*/n.node->id]; }
5.42 - typename std::vector<T>::reference operator[](Node n) {
5.43 - return container[/*G.id(n)*/n.node->id]; }
5.44 - typename std::vector<T>::const_reference operator[](Node n) const {
5.45 - return container[/*G.id(n)*/n.node->id];
5.46 - }
5.47 - void update() { container.resize(G.node_id); }
5.48 - void update(T a) { container.resize(G.node_id, a); }
5.49 - };
5.50 + NodeMapRegistry<ListGraph, Node> node_maps;
5.51
5.52 template <typename T>
5.53 - class EdgeMap {
5.54 - const ListGraph& G;
5.55 - std::vector<T> container;
5.56 - public:
5.57 - typedef T ValueType;
5.58 - typedef Edge KeyType;
5.59 - EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
5.60 - EdgeMap(const ListGraph& _G, T a) :
5.61 - G(_G), container(G.edge_id, a) { }
5.62 - void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
5.63 - T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; }
5.64 - typename std::vector<T>::reference operator[](Edge e) {
5.65 - return container[/*G.id(e)*/e.edge->id]; }
5.66 - typename std::vector<T>::const_reference operator[](Edge e) const {
5.67 - return container[/*G.id(e)*/e.edge->id];
5.68 - }
5.69 - void update() { container.resize(G.edge_id); }
5.70 - void update(T a) { container.resize(G.edge_id, a); }
5.71 - };
5.72 + class NodeMap : public VectorMap<ListGraph, Edge, T, EdgeMapBase> {};
5.73 +
5.74 + EdgeMapRegistry<ListGraph, Edge> edge_maps;
5.75 +
5.76 + template <typename T>
5.77 + class EdgeMap : public VectorMap<Graph, Node, T, NodeMapBase> {};
5.78 +
5.79
5.80 int node_id;
5.81 int edge_id;
5.82 @@ -323,18 +298,28 @@
5.83
5.84 /* adding nodes and edges */
5.85
5.86 - Node addNode() { return Node(_add_node()); }
5.87 + Node addNode() {
5.88 + Node n = _add_node();
5.89 + node_maps.add(n);
5.90 + return n;
5.91 + }
5.92 Edge addEdge(Node u, Node v) {
5.93 - return Edge(_add_edge(u.node, v.node));
5.94 + Edge e = _add_edge(u.node, v.node);
5.95 + edge_maps.add(e);
5.96 + return e;
5.97 }
5.98
5.99 void erase(Node i) {
5.100 + node_map.erase(i);
5.101 while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
5.102 while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
5.103 _delete_node(i.node);
5.104 }
5.105
5.106 - void erase(Edge e) { _delete_edge(e.edge); }
5.107 + void erase(Edge e) {
5.108 + edge_maps.erase(e);
5.109 + _delete_edge(e.edge);
5.110 + }
5.111
5.112 void clear() {
5.113 while (first<NodeIt>().valid()) erase(first<NodeIt>());
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/work/deba/vector_map.h Fri Apr 16 13:42:03 2004 +0000
6.3 @@ -0,0 +1,48 @@
6.4 +#ifndef VECTOR_MAP_H
6.5 +#define VECTOR_MAP_H
6.6 +
6.7 +#include <vector>
6.8 +
6.9 +template <typename G, typename K, typename V, template <typename, typename> class MapBase >
6.10 +class VectorMap : public MapBase<G, K> {
6.11 +public:
6.12 + typedef V ValueType;
6.13 +
6.14 + VectorMap() {}
6.15 + VectorMap(G& g) : MapBase<G, K>(g) {
6.16 + init();
6.17 + }
6.18 +
6.19 + ~VectorMap() {
6.20 +// destroy();
6.21 + }
6.22 +
6.23 + ValueType& operator[](const K& key) {
6.24 + return container[key->id];
6.25 + }
6.26 +
6.27 + const ValueType& operator[](const K& key) const {
6.28 + return container[key->id];
6.29 + }
6.30 +
6.31 + const ValueType& get(const K& key) const {
6.32 + return container[key->id];
6.33 + }
6.34 +
6.35 + void set(const K& key, const ValueType& val) {
6.36 + container[key->id] = val;
6.37 + }
6.38 +
6.39 + void add(const K& key) {
6.40 + container.resize(key->id);
6.41 + }
6.42 +
6.43 + void erase(const K& key) {}
6.44 +
6.45 +private:
6.46 + typedef std::vector<ValueType> Container;
6.47 +
6.48 + Container container;
6.49 +}
6.50 +
6.51 +#endif