1.1 --- a/src/work/deba/edge_map_base.h Thu Apr 22 16:07:17 2004 +0000
1.2 +++ b/src/work/deba/edge_map_base.h Thu Apr 22 16:36:57 2004 +0000
1.3 @@ -11,8 +11,12 @@
1.4
1.5 template <typename G, typename K>
1.6 class EdgeMapBase {
1.7 +
1.8 +#include "edge_map_registry.h"
1.9 +
1.10 public:
1.11 typedef G Graph;
1.12 + friend class EdgeMapRegistry<G, K>;
1.13
1.14 typedef K KeyType;
1.15
1.16 @@ -77,7 +81,7 @@
1.17 */
1.18
1.19 void init() {
1.20 - for (Graph::EdgeIt it(g); g.valid(it); g.next(it)) {
1.21 + for (typename Graph::EdgeIt it(g); g.valid(it); g.next(it)) {
1.22 add(it);
1.23 }
1.24 }
1.25 @@ -87,7 +91,7 @@
1.26 */
1.27
1.28 void destroy() {
1.29 - for (Graph::EdgeIt it(g); g.valid(it); g.next(it)) {
1.30 + for (typename Graph::EdgeIt it(g); g.valid(it); g.next(it)) {
1.31 erase(it);
1.32 }
1.33 }
1.34 @@ -112,7 +116,6 @@
1.35
1.36 class NotSupportedOperationException {};
1.37
1.38 - friend class Graph;
1.39 };
1.40
1.41 #endif
2.1 --- a/src/work/deba/edge_map_register.h Thu Apr 22 16:07:17 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,52 +0,0 @@
2.4 -#ifndef EDGE_MAP_REGISTER_H
2.5 -#define EDGE_MAP_REGISTER_H
2.6 -
2.7 -#include <vector>
2.8 -
2.9 -template <typename G, typename E>
2.10 -class EdgeMapRegister {
2.11 -public:
2.12 - typedef G Graph;
2.13 - typedef E Edge
2.14 -
2.15 - typedef EdgeMapBase<Graph, Edge> EdgeMapBase;
2.16 -
2.17 -protected:
2.18 - typedef std::vector<EdgeMapBase*> Container;
2.19 -
2.20 - Container container;
2.21 -
2.22 - void add(EdgeMapBase& map_base) {
2.23 - if (map_base.graph) {
2.24 - map_base.graph->edge_maps.erase(map_base);
2.25 - }
2.26 - container.push_back(&map_base);
2.27 - map_base.graph_index = container.size()-1;
2.28 - }
2.29 -
2.30 - void erase(EdgeMapBase& map_base) {
2.31 - if (map_base.graph != this) return;
2.32 - container.back()->graph_index = map_base.graph_index;
2.33 - container[map_base.graph_index] = container.back();
2.34 - container.pop_back();
2.35 - map_base.graph = 0;
2.36 - }
2.37 -
2.38 - void addEdge(Edge& edge) {
2.39 - typename Container::iterator it;
2.40 - for (it = container.begin(); it != container.end(); ++it) {
2.41 - (*it)->add(edge);
2.42 - }
2.43 - }
2.44 -
2.45 - void eraseEdge(Edge& edge) {
2.46 - typename Container::iterator it;
2.47 - for (it = container.begin(); it != container.end(); ++it) {
2.48 - (*it)->erase(edge);
2.49 - }
2.50 - }
2.51 -
2.52 - friend class EdgeMapBase;
2.53 -};
2.54 -
2.55 -#endif
3.1 --- a/src/work/deba/edge_map_registry.h Thu Apr 22 16:07:17 2004 +0000
3.2 +++ b/src/work/deba/edge_map_registry.h Thu Apr 22 16:36:57 2004 +0000
3.3 @@ -3,37 +3,48 @@
3.4
3.5 #include <vector>
3.6
3.7 +template <typename G, typename K>
3.8 +class EdgeMapRegistry;
3.9 +
3.10 #include "edge_map_base.h"
3.11
3.12 -template <typename G, typename E>
3.13 +template <typename G, typename K>
3.14 class EdgeMapRegistry {
3.15 public:
3.16 typedef G Graph;
3.17 - typedef E Edge
3.18 + typedef K Edge;
3.19
3.20 typedef EdgeMapBase<Graph, Edge> MapBase;
3.21 + friend class MapBase;
3.22
3.23 protected:
3.24 - typedef std::vector<EdgeMapBase*> Container;
3.25 +
3.26 + Graph* graph;
3.27 +
3.28 + typedef std::vector<MapBase*> Container;
3.29
3.30 Container container;
3.31 -
3.32 +
3.33 +public:
3.34 +
3.35 + EdgeMapRegistry(Graph g) : graph(&g) {}
3.36 +
3.37 void add(MapBase& map_base) {
3.38 if (map_base.graph) {
3.39 map_base.graph->edge_maps.erase(map_base);
3.40 }
3.41 container.push_back(&map_base);
3.42 - map_base.graph = this;
3.43 + map_base.graph = graph;
3.44 map_base.graph_index = container.size()-1;
3.45 }
3.46
3.47 void erase(MapBase& map_base) {
3.48 - if (map_base.graph != this) return;
3.49 container.back()->graph_index = map_base.graph_index;
3.50 container[map_base.graph_index] = container.back();
3.51 container.pop_back();
3.52 map_base.graph = 0;
3.53 }
3.54 +
3.55
3.56 void add(Edge& edge) {
3.57 typename Container::iterator it;
3.58 @@ -49,7 +60,6 @@
3.59 }
3.60 }
3.61
3.62 - friend class MapBase;
3.63 };
3.64
3.65 #endif
4.1 --- a/src/work/deba/mapbase.h Thu Apr 22 16:07:17 2004 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,31 +0,0 @@
4.4 -#ifndef MAPBASE_H
4.5 -#define MAPBASE_H
4.6 -
4.7 -template <class GB, class K>
4.8 -class MapBase {
4.9 -public:
4.10 - typedef GB GraphBase;
4.11 - typedef MappedGraph<GraphBase> Graph;
4.12 -
4.13 - typedef K KeyType;
4.14 -
4.15 -
4.16 - MapBase() : graph(0) {}
4.17 - MapBase(Graph& g) : graph(&g) {graph.add(*this);}
4.18 -
4.19 - virtual ~MapBase() {graph.erase(*this);}
4.20 -
4.21 -protected:
4.22 -
4.23 - Graph* graph;
4.24 -
4.25 - int graph_index;
4.26 -
4.27 -
4.28 - virtual void add(const KeyType&) = 0;
4.29 - virtual void erase(const KeyType&) = 0;
4.30 -
4.31 - friend class Graph;
4.32 -};
4.33 -
4.34 -#endif
5.1 --- a/src/work/deba/mappedgraph.h Thu Apr 22 16:07:17 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,88 +0,0 @@
5.4 -#ifndef MAPPEDGRAPH_H
5.5 -#define MAPPEDGRAPH_H
5.6 -
5.7 -#include <vector>
5.8 -
5.9 -template <typename GB, typename K>
5.10 -class MapBase;
5.11 -
5.12 -template <typename GB>
5.13 -class MappedGraph : public GB {
5.14 -public:
5.15 - typedef GB GraphBase;
5.16 -
5.17 - typedef MapBase<GB, typename GB::Edge> EdgeMapBase;
5.18 - typedef MapBase<GB, typename GB::Node> NodeMapBase;
5.19 -
5.20 -protected:
5.21 - typedef std::vector<EdgeMapBase*> EdgeMaps;
5.22 - typedef std::vector<NodeMapBase*> NodeMaps;
5.23 -
5.24 - EdgeMaps edge_maps;
5.25 - NodeMaps node_maps;
5.26 -
5.27 - void add(EdgeMapBase& map_base) {
5.28 - if (map_base.graph) {
5.29 - map_base.graph->erase(map_base);
5.30 - }
5.31 - edge_maps.push_back(&map_base);
5.32 - map_base.graph_index = map_base.size()-1;
5.33 - }
5.34 -
5.35 - void erase(EdgeMapBase& map_base) {
5.36 - if (map_base.graph != this) return;
5.37 - edge_maps.back()->graph_index = map_base.graph_index;
5.38 - edge_maps[map_base.graph_index] = edge_maps.back();
5.39 - edge_maps.pop_back();
5.40 - map_base.graph = 0;
5.41 - }
5.42 -
5.43 - void addEdge(typename GB::Edge& edge) {
5.44 - typename EdgeMaps::iterator it;
5.45 - for (it = edge_maps.begin(); it != edge_maps.end(); ++it) {
5.46 - (*it)->add(edge);
5.47 - }
5.48 - }
5.49 -
5.50 - void eraseEdge(typename GB::Edge& edge) {
5.51 - typename EdgeMaps::iterator it;
5.52 - for (it = edge_maps.begin(); it != edge_maps.end(); ++it) {
5.53 - (*it)->erase(edge);
5.54 - }
5.55 - }
5.56 -
5.57 - void add(NodeMapBase& map_base) {
5.58 - if (map_base.graph) {
5.59 - map_base.graph->erase(map_base);
5.60 - }
5.61 - node_maps.push_back(&map_base);
5.62 - map_base.graph_index = node_maps.size()-1;
5.63 - }
5.64 -
5.65 - void erase(NodeMapBase& map_base) {
5.66 - if (map_base.graph != this) return;
5.67 - node_maps.back()->graph_index = map_base.graph_index;
5.68 - node_maps[map_base.graph_index] = node_maps.back();
5.69 - node_maps.pop_back();
5.70 - map_base.graph = 0;
5.71 - }
5.72 -
5.73 - void addNode(typename GB::Node& node) {
5.74 - typename NodeMaps::iterator it;
5.75 - for (it = node_maps.begin(); it != node_maps.end(); ++it) {
5.76 - (*it)->add(node);
5.77 - }
5.78 - }
5.79 -
5.80 - void eraseNode(typename GB::Node& node) {
5.81 - typename NodeMaps::iterator it;
5.82 - for (it = node_maps.begin(); it != node_maps.end(); ++it) {
5.83 - (*it)->erase(node);
5.84 - }
5.85 - }
5.86 -
5.87 - friend class EdgeMapBase;
5.88 - friend class NodeMapBase;
5.89 -};
5.90 -
5.91 -#endif
6.1 --- a/src/work/deba/node_map_base.h Thu Apr 22 16:07:17 2004 +0000
6.2 +++ b/src/work/deba/node_map_base.h Thu Apr 22 16:36:57 2004 +0000
6.3 @@ -11,8 +11,12 @@
6.4
6.5 template <typename G, typename K>
6.6 class NodeMapBase {
6.7 +
6.8 +#include "node_map_registry.h"
6.9 +
6.10 public:
6.11 typedef G Graph;
6.12 + friend class NodeMapRegistry<G, K>;
6.13
6.14 typedef K KeyType;
6.15
6.16 @@ -62,7 +66,7 @@
6.17
6.18 virtual ~NodeMapBase() {
6.19 if (graph) {
6.20 - graph.node_maps.erase(*this);
6.21 + graph->node_maps.erase(*this);
6.22 }
6.23 }
6.24
6.25 @@ -77,7 +81,7 @@
6.26 */
6.27
6.28 void init() {
6.29 - for (Graph::NodeIt it(g); g.valid(it); g.next(it)) {
6.30 + for (typename Graph::NodeIt it(g); g.valid(it); g.next(it)) {
6.31 add(it);
6.32 }
6.33 }
6.34 @@ -87,7 +91,7 @@
6.35 */
6.36
6.37 void destroy() {
6.38 - for (Graph::NodeIt it(g); g.valid(it); g.next(it)) {
6.39 + for (typename Graph::NodeIt it(g); g.valid(it); g.next(it)) {
6.40 erase(it);
6.41 }
6.42 }
6.43 @@ -112,7 +116,6 @@
6.44
6.45 class NotSupportedOperationException {};
6.46
6.47 - friend class Graph;
6.48 };
6.49
6.50 #endif
7.1 --- a/src/work/deba/node_map_registry.h Thu Apr 22 16:07:17 2004 +0000
7.2 +++ b/src/work/deba/node_map_registry.h Thu Apr 22 16:36:57 2004 +0000
7.3 @@ -3,37 +3,48 @@
7.4
7.5 #include <vector>
7.6
7.7 +template <typename G, typename K>
7.8 +class NodeMapRegistry;
7.9 +
7.10 #include "node_map_base.h"
7.11
7.12 -template <typename G, typename E>
7.13 +template <typename G, typename K>
7.14 class NodeMapRegistry {
7.15 public:
7.16 typedef G Graph;
7.17 - typedef E Node
7.18 + typedef K Node;
7.19
7.20 - typedef NodeMapBase<Graph, Node> NodeMapBase;
7.21 + typedef NodeMapBase<Graph, Node> MapBase;
7.22 + friend class MapBase;
7.23
7.24 protected:
7.25 - typedef std::vector<NodeMapBase*> Container;
7.26 +
7.27 + Graph* graph;
7.28 +
7.29 + typedef std::vector<MapBase*> Container;
7.30
7.31 Container container;
7.32 -
7.33 - void add(NodeMapBase& map_base) {
7.34 +
7.35 +public:
7.36 +
7.37 + NodeMapRegistry(Graph g) : graph(&g) {}
7.38 +
7.39 + void add(MapBase& map_base) {
7.40 if (map_base.graph) {
7.41 map_base.graph->node_maps.erase(map_base);
7.42 }
7.43 container.push_back(&map_base);
7.44 - map_base.graph = this;
7.45 + map_base.graph = graph;
7.46 map_base.graph_index = container.size()-1;
7.47 }
7.48
7.49 - void erase(NodeMapBase& map_base) {
7.50 - if (map_base.graph != this) return;
7.51 + void erase(MapBase& map_base) {
7.52 container.back()->graph_index = map_base.graph_index;
7.53 container[map_base.graph_index] = container.back();
7.54 container.pop_back();
7.55 map_base.graph = 0;
7.56 }
7.57 +
7.58
7.59 void add(Node& node) {
7.60 typename Container::iterator it;
7.61 @@ -49,7 +60,6 @@
7.62 }
7.63 }
7.64
7.65 - friend class NodeMapBase;
7.66 };
7.67
7.68 #endif
8.1 --- a/src/work/deba/slowgraph.h Thu Apr 22 16:07:17 2004 +0000
8.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
8.3 @@ -1,17 +0,0 @@
8.4 -#ifndef SLOWGRAPH_H
8.5 -#define SLOWGRAPH_H
8.6 -
8.7 -class SlowGraphBase {
8.8 -private:
8.9 - typedef vector<int> EdgeVector;
8.10 - typedef vector<EdgeVector> NodeVector;
8.11 -
8.12 - NodeVector in_nodes, out_nodes;
8.13 -
8.14 -public:
8.15 - typedef Edge
8.16 -};
8.17 -
8.18 -typedef MappedGraph<SlowGraphBase> SlowGraph;
8.19 -
8.20 -#endif
8.21 \ No newline at end of file
9.1 --- a/src/work/deba/test_graph.h Thu Apr 22 16:07:17 2004 +0000
9.2 +++ b/src/work/deba/test_graph.h Thu Apr 22 16:36:57 2004 +0000
9.3 @@ -5,13 +5,13 @@
9.4 #include <iostream>
9.5 #include <vector>
9.6
9.7 -#include <invalid.h>
9.8 +#include "invalid.h"
9.9
9.10 -#include "vector_map.h"
9.11 #include "edge_map_registry.h"
9.12 #include "node_map_registry.h"
9.13 #include "edge_map_base.h"
9.14 #include "node_map_base.h"
9.15 +#include "vector_map.h"
9.16
9.17 namespace hugo {
9.18
9.19 @@ -40,15 +40,24 @@
9.20 // template <typename T> friend class NodeMap;
9.21 // template <typename T> friend class EdgeMap;
9.22
9.23 - NodeMapRegistry<ListGraph, Node> node_maps;
9.24 + private:
9.25 +
9.26 + NodeMapRegistry<ListGraph, Node> node_maps(*this);
9.27 + EdgeMapRegistry<ListGraph, Edge> edge_maps(*this);
9.28 +
9.29 + public:
9.30 +
9.31
9.32 template <typename T>
9.33 - class NodeMap : public VectorMap<ListGraph, Edge, T, EdgeMapBase> {};
9.34 + class NodeMap : public VectorMap<ListGraph, Node, T, NodeMapBase> {
9.35 + public:
9.36 + NodeMap(ListGraph& g) : VectorMap<ListGraph, Node, T, NodeMapBase>(g) {}
9.37 + };
9.38
9.39 EdgeMapRegistry<ListGraph, Edge> edge_maps;
9.40
9.41 template <typename T>
9.42 - class EdgeMap : public VectorMap<Graph, Node, T, NodeMapBase> {};
9.43 + class EdgeMap : public VectorMap<ListGraph, Edge, T, EdgeMapBase> {};
9.44
9.45
9.46 int node_id;
9.47 @@ -310,7 +319,7 @@
9.48 }
9.49
9.50 void erase(Node i) {
9.51 - node_map.erase(i);
9.52 + node_maps.erase(i);
9.53 while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
9.54 while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
9.55 _delete_node(i.node);
10.1 --- a/src/work/deba/vector_map.h Thu Apr 22 16:07:17 2004 +0000
10.2 +++ b/src/work/deba/vector_map.h Thu Apr 22 16:36:57 2004 +0000
10.3 @@ -34,7 +34,9 @@
10.4 }
10.5
10.6 void add(const K& key) {
10.7 - container.resize(key->id);
10.8 + if (key->id() >= container.size()) {
10.9 + container.resize(key->id() + 1);
10.10 + }
10.11 }
10.12
10.13 void erase(const K& key) {}
10.14 @@ -43,6 +45,6 @@
10.15 typedef std::vector<ValueType> Container;
10.16
10.17 Container container;
10.18 -}
10.19 +};
10.20
10.21 #endif