1.1 --- a/src/work/deba/array_map_factory.h Wed Jul 14 21:16:10 2004 +0000
1.2 +++ b/src/work/deba/array_map_factory.h Thu Jul 15 12:15:58 2004 +0000
1.3 @@ -1,11 +1,10 @@
1.4 +// -*- c++ -*-
1.5 #ifndef ARRAY_MAP_H
1.6 #define ARRAY_MAP_H
1.7
1.8 #include <memory>
1.9
1.10 -
1.11 -#include <iostream>
1.12 -using namespace std;
1.13 +#include "extended_pair.h"
1.14
1.15 namespace hugo {
1.16
1.17 @@ -19,7 +18,8 @@
1.18
1.19 typedef typename MapRegistry::MapBase MapBase;
1.20
1.21 - template <typename V, typename A = std::allocator<V> > class Map : public MapBase {
1.22 + template <typename V, typename A = std::allocator<V> >
1.23 + class Map : public MapBase {
1.24
1.25 public:
1.26
1.27 @@ -30,23 +30,7 @@
1.28 Map() : values(0), capacity(0) {}
1.29
1.30 Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
1.31 - int max_id = -1;
1.32 - for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.33 - int id = getGraph()->id(it);
1.34 - if (id > max_id) {
1.35 - max_id = id;
1.36 - }
1.37 - }
1.38 - if (max_id == -1) {
1.39 - capacity = 0;
1.40 - values = 0;
1.41 - return;
1.42 - }
1.43 - capacity = 1;
1.44 - while (capacity <= max_id) {
1.45 - capacity <<= 1;
1.46 - }
1.47 - values = allocator.allocate(capacity);
1.48 + allocate_memory();
1.49 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.50 int id = getGraph()->id(it);
1.51 allocator.construct(&(values[id]), Value());
1.52 @@ -54,23 +38,7 @@
1.53 }
1.54
1.55 Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
1.56 - int max_id = -1;
1.57 - for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.58 - int id = getGraph()->id(it);
1.59 - if (id > max_id) {
1.60 - max_id = id;
1.61 - }
1.62 - }
1.63 - if (max_id == -1) {
1.64 - capacity = 0;
1.65 - values = 0;
1.66 - return;
1.67 - }
1.68 - capacity = 1;
1.69 - while (capacity <= max_id) {
1.70 - capacity <<= 1;
1.71 - }
1.72 - values = allocator.allocate(capacity);
1.73 + allocate_memory();
1.74 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.75 int id = getGraph()->id(it);
1.76 allocator.construct(&(values[id]), v);
1.77 @@ -87,9 +55,10 @@
1.78 }
1.79 }
1.80
1.81 - template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
1.82 + template <typename CMap> Map(const CMap& copy)
1.83 + : capacity(0), values(0), MapBase(copy) {
1.84 if (getGraph()) {
1.85 - init();
1.86 + allocate_memory();
1.87 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.88 set(it, copy[it]);
1.89 }
1.90 @@ -117,14 +86,12 @@
1.91 }
1.92 this->MapBase::operator=(copy);
1.93 if (getGraph()) {
1.94 - init();
1.95 + allocate_memory();
1.96 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.97 set(it, copy[it]);
1.98 }
1.99 }
1.100 }
1.101 -
1.102 -
1.103
1.104 virtual ~Map() {
1.105 if (capacity != 0) {
1.106 @@ -181,36 +148,44 @@
1.107 allocator.destroy(&(values[id]));
1.108 }
1.109
1.110 - /** Compatible iterator with the stl maps' iterators.
1.111 - * It iterates on pairs of a key and a value.
1.112 - */
1.113 class iterator {
1.114 friend class Map;
1.115 friend class const_iterator;
1.116 - private:
1.117 + private:
1.118
1.119 /** Private constructor to initalize the the iterators returned
1.120 * by the begin() and end().
1.121 */
1.122 iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
1.123
1.124 - public:
1.125 + public:
1.126
1.127 /** Default constructor.
1.128 */
1.129 iterator() {}
1.130
1.131 + typedef extended_pair<const Key&, const Key&,
1.132 + Value&, Value&> Reference;
1.133 +
1.134 /** Dereference operator for map.
1.135 */
1.136 - std::pair<const Key, Value> operator*() {
1.137 - return std::pair<const Key, Value>(it, (*map)[it]);
1.138 + Reference operator*() {
1.139 + return Reference(it, (*map)[it]);
1.140 }
1.141
1.142 + class Pointer {
1.143 + friend class iterator;
1.144 + private:
1.145 + Reference data;
1.146 + Pointer(const Key& key, Value& val) : data(key, val) {}
1.147 + public:
1.148 + Reference* operator->() {return &data;}
1.149 + };
1.150 +
1.151 /** Arrow operator for map.
1.152 */
1.153 - std::pair<const Key, Value>* operator->() {
1.154 - static std::pair<const Key, Value> tmp = operator*();
1.155 - return &tmp;
1.156 + Pointer operator->() {
1.157 + return Pointer(it, ((*map)[it]));
1.158 }
1.159
1.160 /** The pre increment operator of the map.
1.161 @@ -239,8 +214,9 @@
1.162 bool operator!=(const_iterator p_it) {
1.163 return !(*this == p_it);
1.164 }
1.165 +
1.166
1.167 - private:
1.168 + private:
1.169 Map* map;
1.170 KeyIt it;
1.171 };
1.172 @@ -260,14 +236,15 @@
1.173 class const_iterator {
1.174 friend class Map;
1.175 friend class iterator;
1.176 - private:
1.177 + private:
1.178
1.179 /** Private constructor to initalize the the iterators returned
1.180 * by the begin() and end().
1.181 */
1.182 - const_iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
1.183 + const_iterator (const Map& pmap, const KeyIt& pit)
1.184 + : map(&pmap), it(pit) {}
1.185
1.186 - public:
1.187 + public:
1.188
1.189 /** Default constructor.
1.190 */
1.191 @@ -275,21 +252,31 @@
1.192
1.193 /** Constructor to convert iterator to const_iterator.
1.194 */
1.195 - const_iterator(iterator p_it) {
1.196 - it = p_it.it;
1.197 - }
1.198 + const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
1.199
1.200 + typedef extended_pair<const Key&, const Key&,
1.201 + const Value&, const Value&> Reference;
1.202 +
1.203 /** Dereference operator for map.
1.204 */
1.205 - std::pair<const Key, const Value> operator*() const {
1.206 - return std::pair<const Key, const Value>(it, (*map)[it]);
1.207 + Reference operator*() {
1.208 + return Reference(it, (*map)[it]);
1.209 }
1.210
1.211 +
1.212 + class Pointer {
1.213 + friend class const_iterator;
1.214 + private:
1.215 + Reference data;
1.216 + Pointer(const Key& key, const Value& val) : data(key, val) {}
1.217 + public:
1.218 + Reference* operator->() {return &data;}
1.219 + };
1.220 +
1.221 /** Arrow operator for map.
1.222 */
1.223 - std::pair<const Key, const Value>* operator->() const {
1.224 - static std::pair<const Key, const Value> tmp = operator*();
1.225 - return &tmp;
1.226 + Pointer operator->() {
1.227 + return Pointer(it, ((*map)[it]));
1.228 }
1.229
1.230 /** The pre increment operator of the map.
1.231 @@ -319,7 +306,8 @@
1.232 return !(*this == p_it);
1.233 }
1.234
1.235 - private:
1.236 +
1.237 + private:
1.238 const Map* map;
1.239 KeyIt it;
1.240 };
1.241 @@ -336,7 +324,27 @@
1.242 return const_iterator(*this, INVALID);
1.243 }
1.244
1.245 - private:
1.246 + private:
1.247 +
1.248 + void allocate_memory() {
1.249 + int max_id = -1;
1.250 + for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
1.251 + int id = getGraph()->id(it);
1.252 + if (id > max_id) {
1.253 + max_id = id;
1.254 + }
1.255 + }
1.256 + if (max_id == -1) {
1.257 + capacity = 0;
1.258 + values = 0;
1.259 + return;
1.260 + }
1.261 + capacity = 1;
1.262 + while (capacity <= max_id) {
1.263 + capacity <<= 1;
1.264 + }
1.265 + values = allocator.allocate(capacity);
1.266 + }
1.267 int capacity;
1.268 Value* values;
1.269 Allocator allocator;
2.1 --- a/src/work/deba/extended_pair.h Wed Jul 14 21:16:10 2004 +0000
2.2 +++ b/src/work/deba/extended_pair.h Thu Jul 15 12:15:58 2004 +0000
2.3 @@ -1,3 +1,4 @@
2.4 +// -*- c++ -*-
2.5 #ifndef EXTENDED_PAIR_H
2.6 #define EXTENDED_PAIR_H
2.7
2.8 @@ -6,10 +7,59 @@
2.9 typedef T1 first_type;
2.10 typedef T2 second_type;
2.11
2.12 + extended_pair() : first(), second() {}
2.13 +
2.14 extended_pair(A1 f, A2 s) : first(f), second(s) {}
2.15
2.16 + template <class Pair>
2.17 + extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {}
2.18 +
2.19 T1 first;
2.20 T2 second;
2.21 };
2.22
2.23 +template <typename T1, typename T2,
2.24 + typename LA1, typename LA2, typename RA1, typename RA2>
2.25 +bool operator==(const extended_pair<T1, LA1, T2, LA2>& left,
2.26 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.27 + return left.first == right.first && left.second == right.second;
2.28 +}
2.29 +
2.30 +template <typename T1, typename T2,
2.31 + typename LA1, typename LA2, typename RA1, typename RA2>
2.32 +bool operator!=(const extended_pair<T1, LA1, T2, LA2>& left,
2.33 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.34 + return !(left == right);
2.35 +}
2.36 +
2.37 +template <typename T1, typename T2,
2.38 + typename LA1, typename LA2, typename RA1, typename RA2>
2.39 +bool operator<(const extended_pair<T1, LA1, T2, LA2>& left,
2.40 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.41 + if (left.first == right.first) return left.second == right.second;
2.42 + return left.first < right.first;
2.43 +}
2.44 +
2.45 +template <typename T1, typename T2,
2.46 + typename LA1, typename LA2, typename RA1, typename RA2>
2.47 +bool operator>(const extended_pair<T1, LA1, T2, LA2>& left,
2.48 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.49 + return right < left;
2.50 +}
2.51 +
2.52 +template <typename T1, typename T2,
2.53 + typename LA1, typename LA2, typename RA1, typename RA2>
2.54 +bool operator<=(const extended_pair<T1, LA1, T2, LA2>& left,
2.55 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.56 + return !(right > left);
2.57 +}
2.58 +
2.59 +template <typename T1, typename T2,
2.60 + typename LA1, typename LA2, typename RA1, typename RA2>
2.61 +bool operator>=(const extended_pair<T1, LA1, T2, LA2>& left,
2.62 + const extended_pair<T1, RA1, T2, RA2>& right) {
2.63 + return !(right < left);
2.64 +}
2.65 +
2.66 +
2.67 #endif
3.1 --- a/src/work/deba/list_graph.h Wed Jul 14 21:16:10 2004 +0000
3.2 +++ b/src/work/deba/list_graph.h Thu Jul 15 12:15:58 2004 +0000
3.3 @@ -12,7 +12,7 @@
3.4
3.5 #include "invalid.h"
3.6
3.7 -#include "vector_map_factory.h"
3.8 +#include "array_map_factory.h"
3.9 #include "map_registry.h"
3.10
3.11 #include "map_defines.h"
3.12 @@ -76,7 +76,7 @@
3.13 class InEdgeIt;
3.14
3.15 CREATE_MAP_REGISTRIES;
3.16 - CREATE_MAPS(VectorMapFactory);
3.17 + CREATE_MAPS(ArrayMapFactory);
3.18 public:
3.19
3.20 ListGraph() : nodes(), first_node(-1),
4.1 --- a/src/work/deba/main.cpp Wed Jul 14 21:16:10 2004 +0000
4.2 +++ b/src/work/deba/main.cpp Thu Jul 15 12:15:58 2004 +0000
4.3 @@ -1,3 +1,4 @@
4.4 +// -*- c++ -*-
4.5 #include <iostream>
4.6 #include <cstdlib>
4.7 #include "list_graph.h"
4.8 @@ -6,6 +7,7 @@
4.9 using namespace hugo;
4.10
4.11
4.12 +
4.13 int main() {
4.14 ListGraph g;
4.15 for (int i = 0; i < 10; ++i) {
4.16 @@ -22,18 +24,15 @@
4.17 ListGraph::NodeMap<int>::iterator pit;
4.18 for (pit = map.begin(); pit != map.end(); ++pit) {
4.19 cout << g.id(pit->first) << ' ' << pit->second << endl;
4.20 - }
4.21 - /*
4.22 - ListGraph::NodeMap<double> ot_map = map;
4.23 - for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
4.24 - ot_map[it] *= 2.1;
4.25 - cout << ot_map[it] << endl;
4.26 - }
4.27 - ot_map = map;
4.28 - for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
4.29 - ot_map[it] *= 3.1;
4.30 - cout << ot_map[it] << endl;
4.31 - }*/
4.32 + (*pit).second = g.id(pit->first);
4.33 + cout << g.id((*pit).first) << ' ' << (*pit).second << endl;
4.34 + }
4.35 + const ListGraph::NodeMap<int> const_map = map;
4.36 + ListGraph::NodeMap<int>::const_iterator cit;
4.37 + for (cit = const_map.begin(); cit != const_map.end(); ++cit) {
4.38 + cerr << g.id(cit->first) << ' ' << cit->second << endl;
4.39 + cerr << g.id((*cit).first) << ' ' << (*cit).second << endl;
4.40 + }
4.41 return 0;
4.42 }
4.43
5.1 --- a/src/work/deba/map_defines.h Wed Jul 14 21:16:10 2004 +0000
5.2 +++ b/src/work/deba/map_defines.h Thu Jul 15 12:15:58 2004 +0000
5.3 @@ -53,10 +53,11 @@
5.4 NodeMap() {} \
5.5 NodeMap(const Graph& g) : Factory::Map<V>(&g, &(g.node_maps)) {} \
5.6 NodeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
5.7 -NodeMap(const NodeMap& copy) : Factory::Map<V>(copy) {} \
5.8 +NodeMap(const NodeMap& copy) \
5.9 + : Factory::Map<V>(static_cast<const Factory::Map<V>&>(copy)) {} \
5.10 template <typename CMap> NodeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
5.11 NodeMap& operator=(const NodeMap& copy) { \
5.12 - this->Factory::Map<V>::operator=(copy); \
5.13 + this->Factory::Map<V>::operator=(static_cast<Factory::Map<V>&>(copy)); \
5.14 return *this; \
5.15 } \
5.16 template <typename CMap>NodeMap& operator=(const CMap& copy) { \
5.17 @@ -78,10 +79,11 @@
5.18 EdgeMap() {} \
5.19 EdgeMap(const Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \
5.20 EdgeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
5.21 -EdgeMap(const EdgeMap& copy) : Factory::Map<V>(copy) {} \
5.22 +EdgeMap(const EdgeMap& copy) \
5.23 + : Factory::Map<V>(static_cast<Factory::Map<V>&>(copy)) {} \
5.24 template <typename CMap> EdgeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
5.25 EdgeMap& operator=(const EdgeMap& copy) { \
5.26 - this->Factory::Map<V>::operator=(copy); \
5.27 + this->Factory::Map<V>::operator=(static_cast<Factory::Map<V>&>(copy)); \
5.28 return *this; \
5.29 } \
5.30 template <typename CMap>EdgeMap& operator=(const CMap& copy) { \
6.1 --- a/src/work/deba/map_registry.h Wed Jul 14 21:16:10 2004 +0000
6.2 +++ b/src/work/deba/map_registry.h Thu Jul 15 12:15:58 2004 +0000
6.3 @@ -91,9 +91,9 @@
6.4
6.5 const Graph* getGraph() const { return graph; }
6.6
6.7 - private:
6.8 + protected:
6.9
6.10 - const Graph* graph;
6.11 + const Graph* graph;
6.12 Registry* registry;
6.13
6.14 int registry_index;
7.1 --- a/src/work/deba/vector_map_factory.h Wed Jul 14 21:16:10 2004 +0000
7.2 +++ b/src/work/deba/vector_map_factory.h Thu Jul 15 12:15:58 2004 +0000
7.3 @@ -1,8 +1,8 @@
7.4 +// -*- c++ -*-
7.5 #ifndef VECTOR_MAP_H
7.6 #define VECTOR_MAP_H
7.7
7.8 #include <vector>
7.9 -#include <iostream>
7.10
7.11 #include "extended_pair.h"
7.12
7.13 @@ -55,9 +55,12 @@
7.14 /** Constructor to use default value to initialize the map.
7.15 */
7.16 Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
7.17 - init();
7.18 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
7.19 - set(it, v);
7.20 + int id = getGraph->id(it);
7.21 + if (id >= container.size) {
7.22 + container.resize(id + 1);
7.23 + }
7.24 + set(it, v);
7.25 }
7.26 }
7.27
7.28 @@ -65,8 +68,11 @@
7.29 */
7.30 template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
7.31 if (getGraph()) {
7.32 - init();
7.33 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
7.34 + int id = getGraph->id(it);
7.35 + if (id >= container.size) {
7.36 + container.resize(id + 1);
7.37 + }
7.38 set(it, copy[it]);
7.39 }
7.40 }
7.41 @@ -80,8 +86,11 @@
7.42 }
7.43 this->MapBase::operator=(copy);
7.44 if (getGraph()) {
7.45 - init();
7.46 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
7.47 + int id = getGraph->id(it);
7.48 + if (id >= container.size) {
7.49 + container.resize(id + 1);
7.50 + }
7.51 set(it, copy[it]);
7.52 }
7.53 }
7.54 @@ -90,7 +99,6 @@
7.55 /** The destructor of the map.
7.56 */
7.57 virtual ~Map() {
7.58 - destroy();
7.59 }
7.60
7.61 /**
7.62 @@ -151,21 +159,22 @@
7.63 */
7.64 iterator() {}
7.65
7.66 + typedef extended_pair<const Key&, const Key&,
7.67 + Value&, Value&> Reference;
7.68 +
7.69 /** Dereference operator for map.
7.70 */
7.71 - std::pair<const Key, Value> operator*() {
7.72 - return std::pair<const Key, Value>(it, (*map)[it]);
7.73 + Reference operator*() {
7.74 + return Reference(it, (*map)[it]);
7.75 }
7.76
7.77 -
7.78 class Pointer {
7.79 friend class iterator;
7.80 private:
7.81 - typedef extended_pair<const Key&, const Key&, Value&, Value&> Pair;
7.82 - Pair data;
7.83 + Reference data;
7.84 Pointer(const Key& key, Value& val) : data(key, val) {}
7.85 public:
7.86 - Pair* operator->() {return &data;}
7.87 + Reference* operator->() {return &data;}
7.88 };
7.89
7.90 /** Arrow operator for map.
7.91 @@ -227,7 +236,8 @@
7.92 /** Private constructor to initalize the the iterators returned
7.93 * by the begin() and end().
7.94 */
7.95 - const_iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
7.96 + const_iterator (const Map& pmap, const KeyIt& pit)
7.97 + : map(&pmap), it(pit) {}
7.98
7.99 public:
7.100
7.101 @@ -237,29 +247,31 @@
7.102
7.103 /** Constructor to convert iterator to const_iterator.
7.104 */
7.105 - const_iterator(iterator p_it) {
7.106 - it = p_it.it;
7.107 - }
7.108 + const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
7.109
7.110 + typedef extended_pair<const Key&, const Key&,
7.111 + const Value&, const Value&> Reference;
7.112 +
7.113 /** Dereference operator for map.
7.114 */
7.115 - std::pair<const Key, const Value> operator*() const {
7.116 - return std::pair<const Key, const Value>(it, (*map)[it]);
7.117 + Reference operator*() {
7.118 + return Reference(it, (*map)[it]);
7.119 }
7.120
7.121 +
7.122 class Pointer {
7.123 friend class const_iterator;
7.124 private:
7.125 - typedef extended_pair<const Key&, const Key&, const Value&, const Value&> Pair;
7.126 - Pair data;
7.127 + Reference data;
7.128 Pointer(const Key& key, const Value& val) : data(key, val) {}
7.129 public:
7.130 - Pair* operator->() {return &data;}
7.131 + Reference* operator->() {return &data;}
7.132 };
7.133 +
7.134 /** Arrow operator for map.
7.135 */
7.136 - Pointer operator->() const {
7.137 - return Pointer(it, (*map)[it]);
7.138 + Pointer operator->() {
7.139 + return Pointer(it, ((*map)[it]));
7.140 }
7.141
7.142 /** The pre increment operator of the map.