1.1 --- a/src/lemon/Makefile.am Wed Nov 10 21:59:59 2004 +0000
1.2 +++ b/src/lemon/Makefile.am Thu Nov 11 09:31:55 2004 +0000
1.3 @@ -1,4 +1,5 @@
1.4 pkginclude_HEADERS = \
1.5 + map_defines.h \
1.6 array_map.h \
1.7 bfs.h \
1.8 dfs.h \
1.9 @@ -6,7 +7,6 @@
1.10 default_map.h \
1.11 dijkstra.h \
1.12 dimacs.h \
1.13 - extended_pair.h \
1.14 fib_heap.h \
1.15 full_graph.h \
1.16 graph_wrapper.h \
1.17 @@ -14,7 +14,6 @@
1.18 invalid.h \
1.19 kruskal.h \
1.20 list_graph.h \
1.21 - map_iterator.h \
1.22 alteration_observer_registry.h \
1.23 maps.h \
1.24 min_cost_flow.h \
1.25 @@ -27,11 +26,8 @@
1.26 vector_map.h \
1.27 xy.h \
1.28 concept_check.h \
1.29 - map_defines.h \
1.30 - map_bits.h \
1.31 utility.h \
1.32 iterable_graph_extender.h \
1.33 - idmappable_graph_extender.h \
1.34 extendable_graph_extender.h \
1.35 clearable_graph_extender.h \
1.36 erasable_graph_extender.h \
2.1 --- a/src/lemon/alteration_observer_registry.h Wed Nov 10 21:59:59 2004 +0000
2.2 +++ b/src/lemon/alteration_observer_registry.h Thu Nov 11 09:31:55 2004 +0000
2.3 @@ -321,11 +321,11 @@
2.4
2.5 public:
2.6
2.7 - EdgeObserverRegistry& getEdgeObserverRegistry() const {
2.8 + EdgeObserverRegistry& getObserverRegistry(Edge = INVALID) const {
2.9 return edge_observers;
2.10 }
2.11
2.12 - NodeObserverRegistry& getNodeObserverRegistry() const {
2.13 + NodeObserverRegistry& getObserverRegistry(Node = INVALID) const {
2.14 return node_observers;
2.15 }
2.16
2.17 @@ -364,7 +364,7 @@
2.18
2.19 mutable UndirEdgeObserverRegistry undir_edge_observers;
2.20
2.21 - UndirEdgeObserverRegistry& getUndirEdgeObserverRegistry() const {
2.22 + UndirEdgeObserverRegistry& getObserverRegistry(UndirEdge = INVALID) const {
2.23 return undir_edge_observers;
2.24 }
2.25
3.1 --- a/src/lemon/array_map.h Wed Nov 10 21:59:59 2004 +0000
3.2 +++ b/src/lemon/array_map.h Thu Nov 11 09:31:55 2004 +0000
3.3 @@ -44,7 +44,6 @@
3.4 template <typename _Graph,
3.5 typename _Item,
3.6 typename _ItemIt,
3.7 - typename _IdMap,
3.8 typename _Value>
3.9 class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {
3.10
3.11 @@ -61,8 +60,6 @@
3.12 /// The iterator to iterate on the keys.
3.13 typedef _ItemIt KeyIt;
3.14
3.15 - typedef _IdMap IdMap;
3.16 -
3.17 typedef _Value Value;
3.18
3.19 /// The MapBase of the Map which imlements the core regisitry function.
3.20 @@ -94,11 +91,11 @@
3.21
3.22 /** Graph and Registry initialized map constructor.
3.23 */
3.24 - ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) {
3.25 - attach(_r);
3.26 + ArrayMap(const Graph& _g) : graph(&_g) {
3.27 + attach(_g.getObserverRegistry(_Item()));
3.28 allocate_memory();
3.29 for (KeyIt it(*graph); it != INVALID; ++it) {
3.30 - int id = IdMap(*graph)[it];
3.31 + int id = graph->id(it);;
3.32 allocator.construct(&(values[id]), Value());
3.33 }
3.34 }
3.35 @@ -107,11 +104,11 @@
3.36
3.37 /// It constrates a map and initialize all of the the map.
3.38
3.39 - ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) {
3.40 - attach(_r);
3.41 + ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
3.42 + attach(_g.getObserverRegistry(_Item()));
3.43 allocate_memory();
3.44 for (KeyIt it(*graph); it != INVALID; ++it) {
3.45 - int id = IdMap(*graph)[it];
3.46 + int id = graph->id(it);;
3.47 allocator.construct(&(values[id]), _v);
3.48 }
3.49 }
3.50 @@ -126,7 +123,7 @@
3.51 if (capacity == 0) return;
3.52 values = allocator.allocate(capacity);
3.53 for (KeyIt it(*graph); it != INVALID; ++it) {
3.54 - int id = IdMap(*graph)[it];
3.55 + int id = graph->id(it);;
3.56 allocator.construct(&(values[id]), copy.values[id]);
3.57 }
3.58 }
3.59 @@ -154,7 +151,7 @@
3.60 }
3.61
3.62 for (KeyIt it(*graph); it != INVALID; ++it) {
3.63 - int id = IdMap(*graph)[it];
3.64 + int id = graph->id(it);;
3.65 allocator.construct(&(values[id]), copy.values[id]);
3.66 }
3.67
3.68 @@ -176,7 +173,7 @@
3.69 * actual keys of the graph.
3.70 */
3.71 ReferenceType operator[](const KeyType& key) {
3.72 - int id = IdMap(*graph)[key];
3.73 + int id = graph->id(key);
3.74 return values[id];
3.75 }
3.76
3.77 @@ -185,7 +182,7 @@
3.78 * actual keys of the graph.
3.79 */
3.80 ConstReferenceType operator[](const KeyType& key) const {
3.81 - int id = IdMap(*graph)[key];
3.82 + int id = graph->id(key);
3.83 return values[id];
3.84 }
3.85
3.86 @@ -199,7 +196,7 @@
3.87 /** Add a new key to the map. It called by the map registry.
3.88 */
3.89 void add(const KeyType& key) {
3.90 - int id = IdMap(*graph)[key];
3.91 + int id = graph->id(key);
3.92 if (id >= capacity) {
3.93 int new_capacity = (capacity == 0 ? 1 : capacity);
3.94 while (new_capacity <= id) {
3.95 @@ -207,7 +204,7 @@
3.96 }
3.97 Value* new_values = allocator.allocate(new_capacity);
3.98 for (KeyIt it(*graph); it != INVALID; ++it) {
3.99 - int jd = IdMap(*graph)[it];
3.100 + int jd = graph->id(it);;
3.101 if (id != jd) {
3.102 allocator.construct(&(new_values[jd]), values[jd]);
3.103 allocator.destroy(&(values[jd]));
3.104 @@ -223,14 +220,14 @@
3.105 /** Erase a key from the map. It called by the map registry.
3.106 */
3.107 void erase(const KeyType& key) {
3.108 - int id = IdMap(*graph)[key];
3.109 + int id = graph->id(key);
3.110 allocator.destroy(&(values[id]));
3.111 }
3.112
3.113 void build() {
3.114 allocate_memory();
3.115 for (KeyIt it(*graph); it != INVALID; ++it) {
3.116 - int id = IdMap(*graph)[it];
3.117 + int id = graph->id(it);;
3.118 allocator.construct(&(values[id]), Value());
3.119 }
3.120 }
3.121 @@ -238,7 +235,7 @@
3.122 void clear() {
3.123 if (capacity != 0) {
3.124 for (KeyIt it(*graph); it != INVALID; ++it) {
3.125 - int id = IdMap(*graph)[it];
3.126 + int id = graph->id(it);;
3.127 allocator.destroy(&(values[id]));
3.128 }
3.129 allocator.deallocate(values, capacity);
3.130 @@ -302,7 +299,7 @@
3.131 private:
3.132
3.133 void allocate_memory() {
3.134 - int max_id = IdMap(*graph).maxId();
3.135 + int max_id = graph->maxId(_Item());
3.136 if (max_id == -1) {
3.137 capacity = 0;
3.138 values = 0;
3.139 @@ -343,55 +340,51 @@
3.140
3.141 typedef typename Parent::Node Node;
3.142 typedef typename Parent::NodeIt NodeIt;
3.143 - typedef typename Parent::NodeIdMap NodeIdMap;
3.144 typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
3.145
3.146 typedef typename Parent::Edge Edge;
3.147 typedef typename Parent::EdgeIt EdgeIt;
3.148 - typedef typename Parent::EdgeIdMap EdgeIdMap;
3.149 typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
3.150
3.151
3.152
3.153 template <typename _Value>
3.154 - class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
3.155 + class NodeMap : public ArrayMap<Graph, Node, NodeIt, _Value> {
3.156 public:
3.157 typedef ArrayMappableGraphExtender<_Base> Graph;
3.158
3.159 typedef typename Graph::Node Node;
3.160 typedef typename Graph::NodeIt NodeIt;
3.161 - typedef typename Graph::NodeIdMap NodeIdMap;
3.162
3.163 - typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
3.164 + typedef ArrayMap<Graph, Node, NodeIt, _Value> Parent;
3.165
3.166 //typedef typename Parent::Graph Graph;
3.167 typedef typename Parent::Value Value;
3.168
3.169 NodeMap(const Graph& g)
3.170 - : Parent(g, g.getNodeObserverRegistry()) {}
3.171 + : Parent(g) {}
3.172 NodeMap(const Graph& g, const Value& v)
3.173 - : Parent(g, g.getNodeObserverRegistry(), v) {}
3.174 + : Parent(g, v) {}
3.175
3.176 };
3.177
3.178 template <typename _Value>
3.179 - class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
3.180 + class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, _Value> {
3.181 public:
3.182 typedef ArrayMappableGraphExtender<_Base> Graph;
3.183
3.184 typedef typename Graph::Edge Edge;
3.185 typedef typename Graph::EdgeIt EdgeIt;
3.186 - typedef typename Graph::EdgeIdMap EdgeIdMap;
3.187
3.188 - typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
3.189 + typedef ArrayMap<Graph, Edge, EdgeIt, _Value> Parent;
3.190
3.191 //typedef typename Parent::Graph Graph;
3.192 typedef typename Parent::Value Value;
3.193
3.194 EdgeMap(const Graph& g)
3.195 - : Parent(g, g.getEdgeObserverRegistry()) {}
3.196 + : Parent(g) {}
3.197 EdgeMap(const Graph& g, const Value& v)
3.198 - : Parent(g, g.getEdgeObserverRegistry(), v) {}
3.199 + : Parent(g, v) {}
3.200
3.201 };
3.202
4.1 --- a/src/lemon/clearable_graph_extender.h Wed Nov 10 21:59:59 2004 +0000
4.2 +++ b/src/lemon/clearable_graph_extender.h Thu Nov 11 09:31:55 2004 +0000
4.3 @@ -14,10 +14,12 @@
4.4
4.5 typedef ClearableGraphExtender Graph;
4.6 typedef _Base Parent;
4.7 + typedef typename Parent::Node Node;
4.8 + typedef typename Parent::Edge Edge;
4.9
4.10 void clear() {
4.11 - Parent::getNodeObserverRegistry().clear();
4.12 - Parent::getEdgeObserverRegistry().clear();
4.13 + Parent::getObserverRegistry(Node()).clear();
4.14 + Parent::getObserverRegistry(Edge()).clear();
4.15 Parent::clear();
4.16 }
4.17
5.1 --- a/src/lemon/concept/graph_component.h Wed Nov 10 21:59:59 2004 +0000
5.2 +++ b/src/lemon/concept/graph_component.h Thu Nov 11 09:31:55 2004 +0000
5.3 @@ -161,6 +161,10 @@
5.4 Node(Invalid) {}
5.5
5.6
5.7 + /// Assign operator for nodes.
5.8 +
5.9 + /// The nodes are assignable.
5.10 + ///
5.11 Node& operator=(const Node&) { return *this;}
5.12
5.13 /// Equality operator.
5.14 @@ -210,7 +214,10 @@
5.15 /// \sa Invalid for more details.
5.16 Edge(Invalid) {}
5.17
5.18 + /// Assign operator for edges.
5.19
5.20 + /// The edges are assignable.
5.21 + ///
5.22 Edge& operator=(const Edge&) { return *this;}
5.23
5.24 /// Equality operator.
5.25 @@ -429,13 +436,13 @@
5.26
5.27 /// Gives back an integer greater or equal to the maximum Node id.
5.28 ///
5.29 - int maxEdgeId() const { return -1;}
5.30 + int maxId(Node = INVALID) const { return -1;}
5.31
5.32 /// Gives back an integer greater or equal to the maximum Edge id.
5.33
5.34 /// Gives back an integer greater or equal to the maximum Edge id.
5.35 ///
5.36 - int maxNodeId() const { return -1;}
5.37 + int maxId(Edge = INVALID) const { return -1;}
5.38 };
5.39
5.40 /// Concept check structure for MaxIdableBaseGraph.
5.41 @@ -447,9 +454,9 @@
5.42
5.43 void constraints() {
5.44 function_requires< BaseGraphComponentConcept<Graph> >();
5.45 - int nid = graph.maxEdgeId();
5.46 + int nid = graph.maxId(typename Graph::Node());
5.47 ignore_unused_variable_warning(nid);
5.48 - int eid = graph.maxNodeId();
5.49 + int eid = graph.maxId(typename Graph::Edge());
5.50 ignore_unused_variable_warning(eid);
5.51 }
5.52
5.53 @@ -662,52 +669,6 @@
5.54 };
5.55
5.56
5.57 - class IdMappableGraphComponent : virtual public BaseGraphComponent {
5.58 -
5.59 - typedef IdMappableGraphComponent Graph;
5.60 -
5.61 - public:
5.62 -
5.63 - typedef BaseGraphComponent::Node Node;
5.64 - typedef BaseGraphComponent::Edge Edge;
5.65 -
5.66 - class NodeIdMap : public ReadMap<Node, int> {
5.67 - public:
5.68 - NodeIdMap(const Graph&) {}
5.69 - int maxId() const { return -1;}
5.70 - };
5.71 -
5.72 - class EdgeIdMap : public ReadMap<Edge, int> {
5.73 - public:
5.74 - EdgeIdMap(const Graph&) {}
5.75 - int maxId() const { return -1;}
5.76 - };
5.77 -
5.78 - };
5.79 -
5.80 - template <typename Graph>
5.81 - struct IdMappableGraphComponentConcept {
5.82 - void constraints() {
5.83 - function_requires< BaseGraphComponentConcept<Graph> >();
5.84 - {
5.85 - typedef typename Graph::EdgeIdMap EdgeIdMap;
5.86 - function_requires<ReadMapConcept<EdgeIdMap> >();
5.87 - EdgeIdMap edge_map(graph);
5.88 - int n = edge_map.maxId();
5.89 - ignore_unused_variable_warning(n);
5.90 - }
5.91 - {
5.92 - typedef typename Graph::NodeIdMap NodeIdMap;
5.93 - function_requires<ReadMapConcept<NodeIdMap> >();
5.94 - NodeIdMap node_map(graph);
5.95 - int n = node_map.maxId();
5.96 - ignore_unused_variable_warning(n);
5.97 - }
5.98 - }
5.99 - Graph& graph;
5.100 - };
5.101 -
5.102 -
5.103 class MappableGraphComponent : virtual public BaseGraphComponent {
5.104 public:
5.105
6.1 --- a/src/lemon/default_map.h Wed Nov 10 21:59:59 2004 +0000
6.2 +++ b/src/lemon/default_map.h Thu Nov 11 09:31:55 2004 +0000
6.3 @@ -42,97 +42,97 @@
6.4
6.5
6.6
6.7 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap, typename _Value>
6.8 + template <typename _Graph, typename _Item, typename _ItemIt, typename _Value>
6.9 struct DefaultMapSelector {
6.10 - typedef ArrayMap<_Graph, _Item, _ItemIt, _IdMap, _Value> Map;
6.11 + typedef ArrayMap<_Graph, _Item, _ItemIt, _Value> Map;
6.12 };
6.13
6.14 // bool
6.15 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.16 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, bool> {
6.17 - typedef VectorMap<_Graph, _Item, _IdMap, bool> Map;
6.18 + template <typename _Graph, typename _Item, typename _ItemIt>
6.19 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, bool> {
6.20 + typedef VectorMap<_Graph, _Item, bool> Map;
6.21 };
6.22
6.23 // char
6.24 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.25 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, char> {
6.26 - typedef VectorMap<_Graph, _Item, _IdMap, char> Map;
6.27 + template <typename _Graph, typename _Item, typename _ItemIt>
6.28 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, char> {
6.29 + typedef VectorMap<_Graph, _Item, char> Map;
6.30 };
6.31
6.32 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.33 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed char> {
6.34 - typedef VectorMap<_Graph, _Item, _IdMap, signed char> Map;
6.35 + template <typename _Graph, typename _Item, typename _ItemIt>
6.36 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed char> {
6.37 + typedef VectorMap<_Graph, _Item, signed char> Map;
6.38 };
6.39
6.40 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.41 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned char> {
6.42 - typedef VectorMap<_Graph, _Item, _IdMap, unsigned char> Map;
6.43 + template <typename _Graph, typename _Item, typename _ItemIt>
6.44 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned char> {
6.45 + typedef VectorMap<_Graph, _Item, unsigned char> Map;
6.46 };
6.47
6.48
6.49 // int
6.50 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.51 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed int> {
6.52 - typedef VectorMap<_Graph, _Item, _IdMap, signed int> Map;
6.53 + template <typename _Graph, typename _Item, typename _ItemIt>
6.54 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed int> {
6.55 + typedef VectorMap<_Graph, _Item, signed int> Map;
6.56 };
6.57
6.58 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.59 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned int> {
6.60 - typedef VectorMap<_Graph, _Item, _IdMap, unsigned int> Map;
6.61 + template <typename _Graph, typename _Item, typename _ItemIt>
6.62 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned int> {
6.63 + typedef VectorMap<_Graph, _Item, unsigned int> Map;
6.64 };
6.65
6.66
6.67 // short
6.68 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.69 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed short> {
6.70 - typedef VectorMap<_Graph, _Item, _IdMap, signed short> Map;
6.71 + template <typename _Graph, typename _Item, typename _ItemIt>
6.72 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed short> {
6.73 + typedef VectorMap<_Graph, _Item, signed short> Map;
6.74 };
6.75
6.76 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.77 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned short> {
6.78 - typedef VectorMap<_Graph, _Item, _IdMap, unsigned short> Map;
6.79 + template <typename _Graph, typename _Item, typename _ItemIt>
6.80 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned short> {
6.81 + typedef VectorMap<_Graph, _Item, unsigned short> Map;
6.82 };
6.83
6.84
6.85 // long
6.86 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.87 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed long> {
6.88 - typedef VectorMap<_Graph, _Item, _IdMap, signed long> Map;
6.89 + template <typename _Graph, typename _Item, typename _ItemIt>
6.90 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed long> {
6.91 + typedef VectorMap<_Graph, _Item, signed long> Map;
6.92 };
6.93
6.94 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.95 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned long> {
6.96 - typedef VectorMap<_Graph, _Item, _IdMap, unsigned long> Map;
6.97 + template <typename _Graph, typename _Item, typename _ItemIt>
6.98 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned long> {
6.99 + typedef VectorMap<_Graph, _Item, unsigned long> Map;
6.100 };
6.101
6.102 // \todo handling long long type
6.103
6.104
6.105 // float
6.106 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.107 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, float> {
6.108 - typedef VectorMap<_Graph, _Item, _IdMap, float> Map;
6.109 + template <typename _Graph, typename _Item, typename _ItemIt>
6.110 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, float> {
6.111 + typedef VectorMap<_Graph, _Item, float> Map;
6.112 };
6.113
6.114
6.115 // double
6.116 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.117 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, double> {
6.118 - typedef VectorMap<_Graph, _Item, _IdMap, double> Map;
6.119 + template <typename _Graph, typename _Item, typename _ItemIt>
6.120 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, double> {
6.121 + typedef VectorMap<_Graph, _Item, double> Map;
6.122 };
6.123
6.124
6.125 // long double
6.126 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
6.127 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, long double> {
6.128 - typedef VectorMap<_Graph, _Item, _IdMap, long double> Map;
6.129 + template <typename _Graph, typename _Item, typename _ItemIt>
6.130 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, long double> {
6.131 + typedef VectorMap<_Graph, _Item, long double> Map;
6.132 };
6.133
6.134
6.135 // pointer
6.136 - template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap, typename _Ptr>
6.137 - struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Ptr*> {
6.138 - typedef VectorMap<_Graph, _Item, _IdMap, _Ptr*> Map;
6.139 + template <typename _Graph, typename _Item, typename _ItemIt, typename _Ptr>
6.140 + struct DefaultMapSelector<_Graph, _Item, _ItemIt, _Ptr*> {
6.141 + typedef VectorMap<_Graph, _Item, _Ptr*> Map;
6.142 };
6.143
6.144
6.145 @@ -140,19 +140,17 @@
6.146 template <typename _Graph,
6.147 typename _Item,
6.148 typename _ItemIt,
6.149 - typename _IdMap,
6.150 typename _Value>
6.151 - class DefaultMap : public DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Value>::Map {
6.152 + class DefaultMap : public DefaultMapSelector<_Graph, _Item, _ItemIt, _Value>::Map {
6.153 public:
6.154 - typedef typename DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Value>::Map Parent;
6.155 - typedef DefaultMap<_Graph, _Item, _ItemIt, _IdMap, bool> Map;
6.156 + typedef typename DefaultMapSelector<_Graph, _Item, _ItemIt, _Value>::Map Parent;
6.157 + typedef DefaultMap<_Graph, _Item, _ItemIt, _Value> Map;
6.158
6.159 typedef typename Parent::Graph Graph;
6.160 - typedef typename Parent::Registry Registry;
6.161 typedef typename Parent::ValueType ValueType;
6.162
6.163 - DefaultMap(const Graph& _g, Registry& _r) : Parent(_g, _r) {}
6.164 - DefaultMap(const Graph& _g, Registry& _r, const ValueType& _v) : Parent(_g, _r, _v) {}
6.165 + DefaultMap(const Graph& _g) : Parent(_g) {}
6.166 + DefaultMap(const Graph& _g, const ValueType& _v) : Parent(_g, _v) {}
6.167 };
6.168
6.169
6.170 @@ -166,55 +164,48 @@
6.171
6.172 typedef typename Parent::Node Node;
6.173 typedef typename Parent::NodeIt NodeIt;
6.174 - typedef typename Parent::NodeIdMap NodeIdMap;
6.175 - typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
6.176
6.177 typedef typename Parent::Edge Edge;
6.178 typedef typename Parent::EdgeIt EdgeIt;
6.179 - typedef typename Parent::EdgeIdMap EdgeIdMap;
6.180 - typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
6.181
6.182
6.183 -
6.184 template <typename _Value>
6.185 - class NodeMap : public DefaultMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
6.186 + class NodeMap : public DefaultMap<Graph, Node, NodeIt, _Value> {
6.187 public:
6.188 typedef DefaultMappableGraphExtender<_Base> Graph;
6.189
6.190 typedef typename Graph::Node Node;
6.191 typedef typename Graph::NodeIt NodeIt;
6.192 - typedef typename Graph::NodeIdMap NodeIdMap;
6.193
6.194 - typedef DefaultMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
6.195 + typedef DefaultMap<Graph, Node, NodeIt, _Value> Parent;
6.196
6.197 //typedef typename Parent::Graph Graph;
6.198 typedef typename Parent::ValueType ValueType;
6.199
6.200 - NodeMap(const Graph& g)
6.201 - : Parent(g, g.getNodeObserverRegistry()) {}
6.202 - NodeMap(const Graph& g, const ValueType& v)
6.203 - : Parent(g, g.getNodeObserverRegistry(), v) {}
6.204 + NodeMap(const Graph& _g)
6.205 + : Parent(_g) {}
6.206 + NodeMap(const Graph& _g, const ValueType& _v)
6.207 + : Parent(_g, _v) {}
6.208
6.209 };
6.210
6.211 template <typename _Value>
6.212 - class EdgeMap : public DefaultMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
6.213 + class EdgeMap : public DefaultMap<Graph, Edge, EdgeIt, _Value> {
6.214 public:
6.215 typedef DefaultMappableGraphExtender<_Base> Graph;
6.216
6.217 typedef typename Graph::Edge Edge;
6.218 typedef typename Graph::EdgeIt EdgeIt;
6.219 - typedef typename Graph::EdgeIdMap EdgeIdMap;
6.220
6.221 - typedef DefaultMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
6.222 + typedef DefaultMap<Graph, Edge, EdgeIt, _Value> Parent;
6.223
6.224 //typedef typename Parent::Graph Graph;
6.225 typedef typename Parent::ValueType ValueType;
6.226
6.227 - EdgeMap(const Graph& g)
6.228 - : Parent(g, g.getEdgeObserverRegistry()) {}
6.229 - EdgeMap(const Graph& g, const ValueType& v)
6.230 - : Parent(g, g.getEdgeObserverRegistry(), v) {}
6.231 + EdgeMap(const Graph& _g)
6.232 + : Parent(_g) {}
6.233 + EdgeMap(const Graph& _g, const ValueType& _v)
6.234 + : Parent(_g, _v) {}
6.235
6.236 };
6.237
7.1 --- a/src/lemon/erasable_graph_extender.h Wed Nov 10 21:59:59 2004 +0000
7.2 +++ b/src/lemon/erasable_graph_extender.h Thu Nov 11 09:31:55 2004 +0000
7.3 @@ -32,12 +32,12 @@
7.4 Parent::firstIn(edge, node);
7.5 }
7.6
7.7 - Parent::getNodeObserverRegistry().erase(node);
7.8 + Parent::getObserverRegistry(Node()).erase(node);
7.9 Parent::erase(node);
7.10 }
7.11
7.12 void erase(const Edge& edge) {
7.13 - Parent::getEdgeObserverRegistry().erase(edge);
7.14 + Parent::getObserverRegistry(Edge()).erase(edge);
7.15 Parent::erase(edge);
7.16 }
7.17
8.1 --- a/src/lemon/extendable_graph_extender.h Wed Nov 10 21:59:59 2004 +0000
8.2 +++ b/src/lemon/extendable_graph_extender.h Thu Nov 11 09:31:55 2004 +0000
8.3 @@ -17,13 +17,13 @@
8.4
8.5 Node addNode() {
8.6 Node node = Parent::addNode();
8.7 - Parent::getNodeObserverRegistry().add(node);
8.8 + Parent::getObserverRegistry(Node()).add(node);
8.9 return node;
8.10 }
8.11
8.12 Edge addEdge(const Node& from, const Node& to) {
8.13 Edge edge = Parent::addEdge(from, to);
8.14 - Parent::getEdgeObserverRegistry().add(edge);
8.15 + Parent::getObserverRegistry(Edge()).add(edge);
8.16 return edge;
8.17 }
8.18
9.1 --- a/src/lemon/full_graph.h Wed Nov 10 21:59:59 2004 +0000
9.2 +++ b/src/lemon/full_graph.h Thu Nov 11 09:31:55 2004 +0000
9.3 @@ -18,7 +18,6 @@
9.4 #define LEMON_FULL_GRAPH_H
9.5
9.6
9.7 -#include <lemon/idmappable_graph_extender.h>
9.8 #include <lemon/iterable_graph_extender.h>
9.9 #include <lemon/alteration_observer_registry.h>
9.10 #include <lemon/default_map.h>
9.11 @@ -70,12 +69,12 @@
9.12
9.13 /// Maximum node ID.
9.14 ///\sa id(Node)
9.15 - int maxNodeId() const { return NodeNum-1; }
9.16 + int maxId(Node = INVALID) const { return NodeNum-1; }
9.17 /// Maximum edge ID.
9.18
9.19 /// Maximum edge ID.
9.20 ///\sa id(Edge)
9.21 - int maxEdgeId() const { return EdgeNum-1; }
9.22 + int maxId(Edge = INVALID) const { return EdgeNum-1; }
9.23
9.24 Node tail(Edge e) const { return e.id % NodeNum; }
9.25 Node head(Edge e) const { return e.id / NodeNum; }
9.26 @@ -188,8 +187,7 @@
9.27
9.28 typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
9.29 typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
9.30 - typedef IdMappableGraphExtender<IterableFullGraphBase> IdMappableFullGraphBase;
9.31 - typedef DefaultMappableGraphExtender<IdMappableFullGraphBase> MappableFullGraphBase;
9.32 + typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase;
9.33
9.34 ///A full graph class.
9.35
10.1 --- a/src/lemon/idmappable_graph_extender.h Wed Nov 10 21:59:59 2004 +0000
10.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
10.3 @@ -1,52 +0,0 @@
10.4 -// -*- c++ -*-
10.5 -
10.6 -#ifndef LEMON_IDMAPPABLE_GRAPH_EXTENDER_H
10.7 -#define LEMON_IDMAPPABLE_GRAPH_EXTENDER_H
10.8 -
10.9 -
10.10 -namespace lemon {
10.11 -
10.12 - template <typename Base>
10.13 - class IdMappableGraphExtender : public Base {
10.14 - public:
10.15 -
10.16 - typedef IdMappableGraphExtender Graph;
10.17 - typedef Base Parent;
10.18 -
10.19 - typedef typename Parent::Node Node;
10.20 - typedef typename Parent::Edge Edge;
10.21 -
10.22 -
10.23 - public:
10.24 -
10.25 - class NodeIdMap {
10.26 - private:
10.27 - const Graph* graph;
10.28 -
10.29 - public:
10.30 - NodeIdMap(const Graph& g) : graph(&g) {}
10.31 -
10.32 - int operator[](const Node& node) const { return graph->id(node); }
10.33 -
10.34 - int maxId() const {return graph->maxNodeId(); }
10.35 -
10.36 - };
10.37 -
10.38 - class EdgeIdMap {
10.39 - private:
10.40 - const Graph* graph;
10.41 -
10.42 - public:
10.43 - EdgeIdMap(const Graph& g) : graph(&g) {}
10.44 -
10.45 - int operator[](const Edge& edge) const { return graph->id(edge); }
10.46 -
10.47 - int maxId() const {return graph->maxEdgeId(); }
10.48 -
10.49 - };
10.50 -
10.51 - };
10.52 -
10.53 -}
10.54 -
10.55 -#endif
11.1 --- a/src/lemon/list_graph.h Wed Nov 10 21:59:59 2004 +0000
11.2 +++ b/src/lemon/list_graph.h Thu Nov 11 09:31:55 2004 +0000
11.3 @@ -25,8 +25,6 @@
11.4 #include <lemon/clearable_graph_extender.h>
11.5 #include <lemon/extendable_graph_extender.h>
11.6
11.7 -#include <lemon/idmappable_graph_extender.h>
11.8 -
11.9 #include <lemon/iterable_graph_extender.h>
11.10
11.11 #include <lemon/alteration_observer_registry.h>
11.12 @@ -105,13 +103,13 @@
11.13
11.14 /// Maximum node ID.
11.15 ///\sa id(Node)
11.16 - int maxNodeId() const { return nodes.size()-1; }
11.17 + int maxId(Node = INVALID) const { return nodes.size()-1; }
11.18
11.19 /// Maximum edge ID.
11.20
11.21 /// Maximum edge ID.
11.22 ///\sa id(Edge)
11.23 - int maxEdgeId() const { return edges.size()-1; }
11.24 + int maxId(Edge = INVALID) const { return edges.size()-1; }
11.25
11.26 Node tail(Edge e) const { return edges[e.id].tail; }
11.27 Node head(Edge e) const { return edges[e.id].head; }
11.28 @@ -303,8 +301,7 @@
11.29
11.30 typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
11.31 typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
11.32 - typedef IdMappableGraphExtender<IterableListGraphBase> IdMappableListGraphBase;
11.33 - typedef DefaultMappableGraphExtender<IdMappableListGraphBase> MappableListGraphBase;
11.34 + typedef DefaultMappableGraphExtender<IterableListGraphBase> MappableListGraphBase;
11.35 typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
11.36 typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
11.37 typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
12.1 --- a/src/lemon/map_bits.h Wed Nov 10 21:59:59 2004 +0000
12.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
12.3 @@ -1,67 +0,0 @@
12.4 -/* -*- C++ -*-
12.5 - * src/lemon/map_bits.h - Part of LEMON, a generic C++ optimization library
12.6 - *
12.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
12.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
12.9 - *
12.10 - * Permission to use, modify and distribute this software is granted
12.11 - * provided that this copyright notice appears in all copies. For
12.12 - * precise terms see the accompanying LICENSE file.
12.13 - *
12.14 - * This software is provided "AS IS" with no warranty of any kind,
12.15 - * express or implied, and with no claim as to its suitability for any
12.16 - * purpose.
12.17 - *
12.18 - */
12.19 -
12.20 -#ifndef LEMON_MAP_BITS_H
12.21 -#define LEMON_MAP_BITS_H
12.22 -
12.23 -///\ingroup graphmaps
12.24 -///\file
12.25 -///\brief Some utils to help implement maps.
12.26 -
12.27 -namespace lemon {
12.28 -
12.29 -
12.30 - /// \addtogroup graphmaps
12.31 - /// @{
12.32 -
12.33 - /// Helper class to get information about the key type.
12.34 - template <typename Graph, typename KeyIt>
12.35 - struct KeyInfo {};
12.36 -
12.37 - template <typename Graph>
12.38 - struct KeyInfo<Graph, typename Graph::NodeIt> {
12.39 - static int maxId(const Graph& graph) {
12.40 - return graph.maxNodeId();
12.41 - }
12.42 - static int id(const Graph& graph, const typename Graph::Node& node) {
12.43 - return graph.id(node);
12.44 - }
12.45 - };
12.46 -
12.47 - template <typename Graph>
12.48 - struct KeyInfo<Graph, typename Graph::EdgeIt> {
12.49 - static int maxId(const Graph& graph) {
12.50 - return graph.maxEdgeId();
12.51 - }
12.52 - static int id(const Graph& graph, const typename Graph::Edge& edge) {
12.53 - return graph.id(edge);
12.54 - }
12.55 - };
12.56 -
12.57 - template <typename Graph>
12.58 - struct KeyInfo<Graph, typename Graph::SymEdgeIt> {
12.59 - static int maxId(const Graph& graph) {
12.60 - return graph.maxSymEdgeId();
12.61 - }
12.62 - static int id(const Graph& graph, const typename Graph::SymEdge& edge) {
12.63 - return graph.id(edge);
12.64 - }
12.65 - };
12.66 -
12.67 - /// @}
12.68 -}
12.69 -
12.70 -#endif
13.1 --- a/src/lemon/smart_graph.h Wed Nov 10 21:59:59 2004 +0000
13.2 +++ b/src/lemon/smart_graph.h Thu Nov 11 09:31:55 2004 +0000
13.3 @@ -27,7 +27,6 @@
13.4
13.5 #include <lemon/clearable_graph_extender.h>
13.6 #include <lemon/extendable_graph_extender.h>
13.7 -#include <lemon/idmappable_graph_extender.h>
13.8 #include <lemon/iterable_graph_extender.h>
13.9 #include <lemon/alteration_observer_registry.h>
13.10 #include <lemon/default_map.h>
13.11 @@ -91,12 +90,12 @@
13.12
13.13 /// Maximum node ID.
13.14 ///\sa id(Node)
13.15 - int maxNodeId() const { return nodes.size()-1; }
13.16 + int maxId(Node = INVALID) const { return nodes.size()-1; }
13.17 /// Maximum edge ID.
13.18
13.19 /// Maximum edge ID.
13.20 ///\sa id(Edge)
13.21 - int maxEdgeId() const { return edges.size()-1; }
13.22 + int maxId(Edge = INVALID) const { return edges.size()-1; }
13.23
13.24 Node tail(Edge e) const { return edges[e.n].tail; }
13.25 Node head(Edge e) const { return edges[e.n].head; }
13.26 @@ -221,8 +220,7 @@
13.27
13.28 typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
13.29 typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
13.30 - typedef IdMappableGraphExtender<IterableSmartGraphBase> IdMappableSmartGraphBase;
13.31 - typedef DefaultMappableGraphExtender<IdMappableSmartGraphBase> MappableSmartGraphBase;
13.32 + typedef DefaultMappableGraphExtender<IterableSmartGraphBase> MappableSmartGraphBase;
13.33 typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
13.34 typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
13.35
13.36 @@ -239,7 +237,7 @@
13.37 ///\todo Some member functions could be \c static.
13.38 ///
13.39 ///\author Alpar Juttner
13.40 - class SmartGraph :public ClearableSmartGraphBase {
13.41 + class SmartGraph : public ClearableSmartGraphBase {
13.42 public:
13.43 /// Finds an edge between two nodes.
13.44
14.1 --- a/src/lemon/vector_map.h Wed Nov 10 21:59:59 2004 +0000
14.2 +++ b/src/lemon/vector_map.h Thu Nov 11 09:31:55 2004 +0000
14.3 @@ -46,7 +46,6 @@
14.4
14.5 template <typename _Graph,
14.6 typename _Item,
14.7 - typename _IdMap,
14.8 typename _Value>
14.9 class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase {
14.10 public:
14.11 @@ -56,8 +55,6 @@
14.12 /// The key type of the map.
14.13 typedef _Item KeyType;
14.14 /// The id map type of the map.
14.15 - typedef _IdMap IdMap;
14.16 - /// The registry type of the map.
14.17 typedef AlterationObserverRegistry<_Item> Registry;
14.18 /// The value type of the map.
14.19 typedef _Value Value;
14.20 @@ -93,8 +90,8 @@
14.21 /// It construates a map and attachs it into the registry.
14.22 /// It adds all the items of the graph to the map.
14.23
14.24 - VectorMap(const Graph& _g, Registry& _r) : graph(&_g) {
14.25 - attach(_r);
14.26 + VectorMap(const Graph& _g) : graph(&_g) {
14.27 + attach(_g.getObserverRegistry(_Item()));
14.28 build();
14.29 }
14.30
14.31 @@ -103,15 +100,15 @@
14.32 /// It construates a map uses a given value to initialize the map.
14.33 /// It adds all the items of the graph to the map.
14.34
14.35 - VectorMap(const Graph& g, Registry& r, const Value& v) : graph(&g) {
14.36 - attach(r);
14.37 - container.resize(IdMap(*graph).maxId() + 1, v);
14.38 + VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
14.39 + attach(_g.getObserverRegistry(_Item()));
14.40 + container.resize(graph->maxId(_Item()) + 1, _v);
14.41 }
14.42
14.43 - VectorMap(const VectorMap& copy) : graph(copy.getGraph()) {
14.44 - if (copy.attached()) {
14.45 - attach(*copy.getRegistry());
14.46 - container = copy.container;
14.47 + VectorMap(const VectorMap& _copy) : graph(_copy.getGraph()) {
14.48 + if (_copy.attached()) {
14.49 + attach(*_copy.getRegistry());
14.50 + container = _copy.container;
14.51 }
14.52 }
14.53
14.54 @@ -154,7 +151,7 @@
14.55 /// actual items of the graph.
14.56
14.57 ReferenceType operator[](const KeyType& key) {
14.58 - return container[IdMap(*graph)[key]];
14.59 + return container[graph->id(key)];
14.60 }
14.61
14.62 /// The const subcript operator.
14.63 @@ -163,7 +160,7 @@
14.64 /// actual items of the graph.
14.65
14.66 ConstReferenceType operator[](const KeyType& key) const {
14.67 - return container[IdMap(*graph)[key]];
14.68 + return container[graph->id(key)];
14.69 }
14.70
14.71
14.72 @@ -182,7 +179,7 @@
14.73 /// and it overrides the add() member function of the observer base.
14.74
14.75 void add(const KeyType& key) {
14.76 - int id = IdMap(*graph)[key];
14.77 + int id = graph->id(key);
14.78 if (id >= (int)container.size()) {
14.79 container.resize(id + 1);
14.80 }
14.81 @@ -200,7 +197,7 @@
14.82 /// and it overrides the build() member function of the observer base.
14.83
14.84 void build() {
14.85 - container.resize(IdMap(*graph).maxId() + 1);
14.86 + container.resize(graph->maxId(_Item()) + 1);
14.87 }
14.88
14.89 /// Clear the map.
14.90 @@ -239,42 +236,40 @@
14.91
14.92
14.93 template <typename _Value>
14.94 - class NodeMap : public VectorMap<Graph, Node, NodeIdMap, _Value> {
14.95 + class NodeMap : public VectorMap<Graph, Node, _Value> {
14.96 public:
14.97 typedef VectorMappableGraphExtender<_Base> Graph;
14.98
14.99 typedef typename Graph::Node Node;
14.100 - typedef typename Graph::NodeIdMap NodeIdMap;
14.101
14.102 - typedef VectorMap<Graph, Node, NodeIdMap, _Value> Parent;
14.103 + typedef VectorMap<Graph, Node, _Value> Parent;
14.104
14.105 //typedef typename Parent::Graph Graph;
14.106 typedef typename Parent::Value Value;
14.107
14.108 NodeMap(const Graph& g)
14.109 - : Parent(g, g.getNodeObserverRegistry()) {}
14.110 + : Parent(g) {}
14.111 NodeMap(const Graph& g, const Value& v)
14.112 - : Parent(g, g.getNodeObserverRegistry(), v) {}
14.113 + : Parent(g, v) {}
14.114
14.115 };
14.116
14.117 template <typename _Value>
14.118 - class EdgeMap : public VectorMap<Graph, Edge, EdgeIdMap, _Value> {
14.119 + class EdgeMap : public VectorMap<Graph, Edge, _Value> {
14.120 public:
14.121 typedef VectorMappableGraphExtender<_Base> Graph;
14.122
14.123 typedef typename Graph::Edge Edge;
14.124 - typedef typename Graph::EdgeIdMap EdgeIdMap;
14.125
14.126 - typedef VectorMap<Graph, Edge, EdgeIdMap, _Value> Parent;
14.127 + typedef VectorMap<Graph, Edge, _Value> Parent;
14.128
14.129 //typedef typename Parent::Graph Graph;
14.130 typedef typename Parent::Value Value;
14.131
14.132 EdgeMap(const Graph& g)
14.133 - : Parent(g, g.getEdgeObserverRegistry()) {}
14.134 + : Parent(g) {}
14.135 EdgeMap(const Graph& g, const Value& v)
14.136 - : Parent(g, g.getEdgeObserverRegistry(), v) {}
14.137 + : Parent(g, v) {}
14.138
14.139 };
14.140
15.1 --- a/src/test/graph_test.cc Wed Nov 10 21:59:59 2004 +0000
15.2 +++ b/src/test/graph_test.cc Thu Nov 11 09:31:55 2004 +0000
15.3 @@ -33,7 +33,6 @@
15.4
15.5 function_requires<IterableGraphComponentConcept<IterableGraphComponent> >();
15.6
15.7 - function_requires<IdMappableGraphComponentConcept<IdMappableGraphComponent> >();
15.8 function_requires<MappableGraphComponentConcept<MappableGraphComponent> >();
15.9
15.10 function_requires<ExtendableGraphComponentConcept<ExtendableGraphComponent> >();