# HG changeset patch # User deba # Date 1082122923 0 # Node ID a2ce3c4780b7f31d4d3ba250b88879ca3c22a5cd # Parent 768ebc700baede2ce0552b7c6cb2d86709accd96 diff -r 768ebc700bae -r a2ce3c4780b7 src/work/deba/edge_map_base.h --- a/src/work/deba/edge_map_base.h Fri Apr 16 13:26:15 2004 +0000 +++ b/src/work/deba/edge_map_base.h Fri Apr 16 13:42:03 2004 +0000 @@ -1,18 +1,65 @@ #ifndef EDGE_MAP_BASE_H #define EDGE_MAP_BASE_H -template +/** + Template base class for implementing mapping on edges. + \param The first template parameter is the Graph class. The Graph + must have an \emp edge_maps member with \emp EdgeMapRegistry class. + \param The second template parameter is the Edge type of the class. + +*/ + +template class EdgeMapBase { public: typedef G Graph; typedef K KeyType; + /** + Default constructor. + */ + EdgeMapBase() : graph(0) {} + + /** + Simple constructor to register into a graph. + */ + EdgeMapBase(Graph& g) : graph(&g) { graph->edge_maps.add(*this); } + /** + Copy constructor with registering into the map. + */ + + EdgeMapBase(const EdgeMapBase& copy) : graph(copy.graph) { + if (graph) { + graph->edge_maps.add(*this); + } + } + + /** + Assign operator. + */ + + const EdgeMapBase& operator=(const EdgeMapBase& copy) { + if (graph) { + graph.edge_maps.erase(*this); + } + graph = copy.graph; + if (graph) { + graph->edge_maps.add(*this); + } + + } + + + /** + Destructor. + */ + virtual ~EdgeMapBase() { if (graph) { graph.edge_maps.erase(*this); @@ -25,20 +72,45 @@ int graph_index; + /** + Helper function to implement the default constructor in the subclasses. + */ + void init() { for (Graph::EdgeIt it(g); g.valid(it); g.next(it)) { add(it); } } + /** + Helper function to implement the destructor in the subclasses. + */ + void destroy() { for (Graph::EdgeIt it(g); g.valid(it); g.next(it)) { erase(it); } } + /** + The add member function should be overloaded in the subclasses. + \e Add extends the map with the new edge. + */ + virtual void add(const KeyType&) = 0; + + /** + The erase member function should be overloaded in the subclasses. + \e Erase removes the edge from the map. + */ + virtual void erase(const KeyType&) = 0; + + /** + Exception class to throw at unsupported operation. + */ + + class NotSupportedOperationException {}; friend class Graph; }; diff -r 768ebc700bae -r a2ce3c4780b7 src/work/deba/edge_map_registry.h --- a/src/work/deba/edge_map_registry.h Fri Apr 16 13:26:15 2004 +0000 +++ b/src/work/deba/edge_map_registry.h Fri Apr 16 13:42:03 2004 +0000 @@ -3,20 +3,22 @@ #include +#include "edge_map_base.h" + template class EdgeMapRegistry { public: typedef G Graph; typedef E Edge - typedef EdgeMapBase EdgeMapBase; + typedef EdgeMapBase MapBase; protected: typedef std::vector Container; Container container; - void add(EdgeMapBase& map_base) { + void add(MapBase& map_base) { if (map_base.graph) { map_base.graph->edge_maps.erase(map_base); } @@ -25,7 +27,7 @@ map_base.graph_index = container.size()-1; } - void erase(EdgeMapBase& map_base) { + void erase(MapBase& map_base) { if (map_base.graph != this) return; container.back()->graph_index = map_base.graph_index; container[map_base.graph_index] = container.back(); @@ -33,21 +35,21 @@ map_base.graph = 0; } - void addEdge(Edge& edge) { + void add(Edge& edge) { typename Container::iterator it; for (it = container.begin(); it != container.end(); ++it) { (*it)->add(edge); } } - void eraseEdge(Edge& edge) { + void erase(Edge& edge) { typename Container::iterator it; for (it = container.begin(); it != container.end(); ++it) { (*it)->erase(edge); } } - friend class EdgeMapBase; + friend class MapBase; }; #endif diff -r 768ebc700bae -r a2ce3c4780b7 src/work/deba/node_map_base.h --- a/src/work/deba/node_map_base.h Fri Apr 16 13:26:15 2004 +0000 +++ b/src/work/deba/node_map_base.h Fri Apr 16 13:42:03 2004 +0000 @@ -1,18 +1,65 @@ #ifndef NODE_MAP_BASE_H #define NODE_MAP_BASE_H -template +/** + Template base class for implementing mapping on nodes. + \param The first template parameter is the Graph class. The Graph + must have an \emp node_maps member with \emp NodeMapRegistry class. + \param The second template parameter is the Node type of the class. + +*/ + +template class NodeMapBase { public: typedef G Graph; typedef K KeyType; + /** + Default constructor. + */ + NodeMapBase() : graph(0) {} + + /** + Simple constructor to register into a graph. + */ + NodeMapBase(Graph& g) : graph(&g) { graph->node_maps.add(*this); } + /** + Copy constructor with registering into the map. + */ + + NodeMapBase(const NodeMapBase& copy) : graph(copy.graph) { + if (graph) { + graph->node_maps.add(*this); + } + } + + /** + Assign operator. + */ + + const NodeMapBase& operator=(const NodeMapBase& copy) { + if (graph) { + graph.node_maps.erase(*this); + } + graph = copy.graph; + if (graph) { + graph->node_maps.add(*this); + } + + } + + + /** + Destructor. + */ + virtual ~NodeMapBase() { if (graph) { graph.node_maps.erase(*this); @@ -25,20 +72,45 @@ int graph_index; + /** + Helper function to implement the default constructor in the subclasses. + */ + void init() { for (Graph::NodeIt it(g); g.valid(it); g.next(it)) { add(it); } } + /** + Helper function to implement the destructor in the subclasses. + */ + void destroy() { for (Graph::NodeIt it(g); g.valid(it); g.next(it)) { erase(it); } } + /** + The add member function should be overloaded in the subclasses. + \e Add extends the map with the new node. + */ + virtual void add(const KeyType&) = 0; + + /** + The erase member function should be overloaded in the subclasses. + \e Erase removes the node from the map. + */ + virtual void erase(const KeyType&) = 0; + + /** + Exception class to throw at unsupported operation. + */ + + class NotSupportedOperationException {}; friend class Graph; }; diff -r 768ebc700bae -r a2ce3c4780b7 src/work/deba/node_map_registry.h --- a/src/work/deba/node_map_registry.h Fri Apr 16 13:26:15 2004 +0000 +++ b/src/work/deba/node_map_registry.h Fri Apr 16 13:42:03 2004 +0000 @@ -3,6 +3,8 @@ #include +#include "node_map_base.h" + template class NodeMapRegistry { public: @@ -33,14 +35,14 @@ map_base.graph = 0; } - void addNode(Node& node) { + void add(Node& node) { typename Container::iterator it; for (it = container.begin(); it != container.end(); ++it) { (*it)->add(node); } } - void eraseNode(Node& node) { + void erase(Node& node) { typename Container::iterator it; for (it = container.begin(); it != container.end(); ++it) { (*it)->erase(node); diff -r 768ebc700bae -r a2ce3c4780b7 src/work/deba/test_graph.h --- a/src/work/deba/test_graph.h Fri Apr 16 13:26:15 2004 +0000 +++ b/src/work/deba/test_graph.h Fri Apr 16 13:42:03 2004 +0000 @@ -7,6 +7,12 @@ #include +#include "vector_map.h" +#include "edge_map_registry.h" +#include "node_map_registry.h" +#include "edge_map_base.h" +#include "node_map_base.h" + namespace hugo { template @@ -28,53 +34,22 @@ class InEdgeIt; class SymEdgeIt; - template class NodeMap; - template class EdgeMap; +// template class NodeMap; +// template class EdgeMap; private: - template friend class NodeMap; - template friend class EdgeMap; +// template friend class NodeMap; + // template friend class EdgeMap; - template - class NodeMap { - const ListGraph& G; - std::vector container; - public: - typedef T ValueType; - typedef Node KeyType; - NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { } - NodeMap(const ListGraph& _G, T a) : - G(_G), container(G.node_id, a) { } - void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; } - T get(Node n) const { return container[/*G.id(n)*/n.node->id]; } - typename std::vector::reference operator[](Node n) { - return container[/*G.id(n)*/n.node->id]; } - typename std::vector::const_reference operator[](Node n) const { - return container[/*G.id(n)*/n.node->id]; - } - void update() { container.resize(G.node_id); } - void update(T a) { container.resize(G.node_id, a); } - }; + NodeMapRegistry node_maps; template - class EdgeMap { - const ListGraph& G; - std::vector container; - public: - typedef T ValueType; - typedef Edge KeyType; - EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { } - EdgeMap(const ListGraph& _G, T a) : - G(_G), container(G.edge_id, a) { } - void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; } - T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; } - typename std::vector::reference operator[](Edge e) { - return container[/*G.id(e)*/e.edge->id]; } - typename std::vector::const_reference operator[](Edge e) const { - return container[/*G.id(e)*/e.edge->id]; - } - void update() { container.resize(G.edge_id); } - void update(T a) { container.resize(G.edge_id, a); } - }; + class NodeMap : public VectorMap {}; + + EdgeMapRegistry edge_maps; + + template + class EdgeMap : public VectorMap {}; + int node_id; int edge_id; @@ -323,18 +298,28 @@ /* adding nodes and edges */ - Node addNode() { return Node(_add_node()); } + Node addNode() { + Node n = _add_node(); + node_maps.add(n); + return n; + } Edge addEdge(Node u, Node v) { - return Edge(_add_edge(u.node, v.node)); + Edge e = _add_edge(u.node, v.node); + edge_maps.add(e); + return e; } void erase(Node i) { + node_map.erase(i); while (first(i).valid()) erase(first(i)); while (first(i).valid()) erase(first(i)); _delete_node(i.node); } - void erase(Edge e) { _delete_edge(e.edge); } + void erase(Edge e) { + edge_maps.erase(e); + _delete_edge(e.edge); + } void clear() { while (first().valid()) erase(first()); diff -r 768ebc700bae -r a2ce3c4780b7 src/work/deba/vector_map.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/deba/vector_map.h Fri Apr 16 13:42:03 2004 +0000 @@ -0,0 +1,48 @@ +#ifndef VECTOR_MAP_H +#define VECTOR_MAP_H + +#include + +template class MapBase > +class VectorMap : public MapBase { +public: + typedef V ValueType; + + VectorMap() {} + VectorMap(G& g) : MapBase(g) { + init(); + } + + ~VectorMap() { +// destroy(); + } + + ValueType& operator[](const K& key) { + return container[key->id]; + } + + const ValueType& operator[](const K& key) const { + return container[key->id]; + } + + const ValueType& get(const K& key) const { + return container[key->id]; + } + + void set(const K& key, const ValueType& val) { + container[key->id] = val; + } + + void add(const K& key) { + container.resize(key->id); + } + + void erase(const K& key) {} + +private: + typedef std::vector Container; + + Container container; +} + +#endif