Skeleton for paths.
2 #ifndef ARRAY_MAP_FACTORY_H
3 #define ARRAY_MAP_FACTORY_H
7 #include <hugo/extended_pair.h>
9 ///\ingroup graphmapfactory
11 ///\brief Graph maps that construates and destruates
12 ///their elements dynamically.
16 /// \addtogroup graphmapfactory
20 template <typename MapRegistry> class ArrayMapFactory {
24 typedef typename MapRegistry::Graph Graph;
25 typedef typename MapRegistry::KeyType KeyType;
26 typedef typename MapRegistry::KeyIt KeyIt;
28 typedef typename MapRegistry::MapBase MapBase;
30 template <typename V, typename A = std::allocator<V> >
31 class Map : public MapBase {
40 Map() : values(0), capacity(0) {}
42 Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
44 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
45 int id = MapBase::getGraph()->id(it);
46 allocator.construct(&(values[id]), Value());
50 Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
52 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
53 int id = MapBase::getGraph()->id(it);
54 allocator.construct(&(values[id]), v);
58 Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
59 capacity = copy.capacity;
60 if (capacity == 0) return;
61 values = allocator.allocate(capacity);
62 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
63 int id = MapBase::getGraph()->id(it);
64 allocator.construct(&(values[id]), copy.values[id]);
68 template <typename CMap> Map(const CMap& copy)
69 : MapBase(copy), capacity(0), values(0) {
70 if (MapBase::getGraph()) {
72 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
78 Map& operator=(const Map& copy) {
79 if (© == this) return *this;
82 allocator.deallocate(values, capacity);
84 capacity = copy.capacity;
85 if (capacity == 0) return *this;
86 values = allocator.allocate(capacity);
87 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
88 int id = MapBase::getGraph()->id(it);
89 allocator.construct(&(values[id]), copy.values[id]);
94 template <typename CMap> Map& operator=(const CMap& copy) {
95 if (MapBase::getGraph()) {
98 MapBase::operator=(copy);
99 if (MapBase::getGraph()) {
101 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
111 allocator.deallocate(values, capacity);
116 Value& operator[](const KeyType& key) {
117 int id = MapBase::getGraph()->id(key);
121 const Value& operator[](const KeyType& key) const {
122 int id = MapBase::getGraph()->id(key);
126 const Value& get(const KeyType& key) const {
127 int id = MapBase::getGraph()->id(key);
131 void set(const KeyType& key, const Value& val) {
132 int id = MapBase::getGraph()->id(key);
136 void add(const KeyType& key) {
137 int id = MapBase::getGraph()->id(key);
138 if (id >= capacity) {
139 int new_capacity = (capacity == 0 ? 1 : capacity);
140 while (new_capacity <= id) {
143 Value* new_values = allocator.allocate(new_capacity);;
144 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
145 int jd = MapBase::getGraph()->id(it);
147 allocator.construct(&(new_values[jd]), values[jd]);
148 allocator.destroy(&(values[jd]));
151 if (capacity != 0) allocator.deallocate(values, capacity);
153 capacity = new_capacity;
155 allocator.construct(&(values[id]), Value());
158 void erase(const KeyType& key) {
159 int id = MapBase::getGraph()->id(key);
160 allocator.destroy(&(values[id]));
166 allocator.deallocate(values, capacity);
173 friend class const_iterator;
176 /** Private constructor to initalize the the iterators returned
177 * by the begin() and end().
179 iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
183 /** Default constructor.
187 typedef extended_pair<const KeyType&, const KeyType&,
188 Value&, Value&> Reference;
190 /** Dereference operator for map.
192 Reference operator*() {
193 return Reference(it, (*map)[it]);
197 friend class iterator;
200 Pointer(const KeyType& key, Value& val) : data(key, val) {}
202 Reference* operator->() {return &data;}
205 /** Arrow operator for map.
207 Pointer operator->() {
208 return Pointer(it, ((*map)[it]));
211 /** The pre increment operator of the map.
213 iterator& operator++() {
218 /** The post increment operator of the map.
220 iterator operator++(int) {
226 /** The equality operator of the map.
228 bool operator==(const_iterator p_it) {
229 return p_it.it == it;
232 /** The not-equality operator of the map.
234 bool operator!=(const_iterator p_it) {
235 return !(*this == p_it);
244 /** Returns the begin iterator of the map.
247 return iterator(*this, KeyIt(*MapBase::getGraph()));
250 /** Returns the end iterator of the map.
253 return iterator(*this, INVALID);
256 class const_iterator {
258 friend class iterator;
261 /** Private constructor to initalize the the iterators returned
262 * by the begin() and end().
264 const_iterator (const Map& pmap, const KeyIt& pit)
265 : map(&pmap), it(pit) {}
269 /** Default constructor.
273 /** Constructor to convert iterator to const_iterator.
275 const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
277 typedef extended_pair<const KeyType&, const KeyType&,
278 const Value&, const Value&> Reference;
280 /** Dereference operator for map.
282 Reference operator*() {
283 return Reference(it, (*map)[it]);
288 friend class const_iterator;
291 Pointer(const KeyType& key, const Value& val) : data(key, val) {}
293 Reference* operator->() {return &data;}
296 /** Arrow operator for map.
298 Pointer operator->() {
299 return Pointer(it, ((*map)[it]));
302 /** The pre increment operator of the map.
304 const_iterator& operator++() {
309 /** The post increment operator of the map.
311 const_iterator operator++(int) {
312 const_iterator tmp(it);
317 /** The equality operator of the map.
319 bool operator==(const_iterator p_it) {
320 return p_it.it == it;
323 /** The not-equality operator of the map.
325 bool operator!=(const_iterator p_it) {
326 return !(*this == p_it);
335 /** Returns the begin const_iterator of the map.
337 const_iterator begin() const {
338 return const_iterator(*this, KeyIt(*MapBase::getGraph()));
341 /** Returns the end const_iterator of the map.
343 const_iterator end() const {
344 return const_iterator(*this, INVALID);
349 void allocate_memory() {
351 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
352 int id = MapBase::getGraph()->id(it);
363 while (capacity <= max_id) {
366 values = allocator.allocate(capacity);