00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_ARRAY_MAP_H
00018 #define LEMON_ARRAY_MAP_H
00019
00020 #include <memory>
00021
00026
00027 namespace lemon {
00028
00029
00032
00042 template <typename _Graph,
00043 typename _Item,
00044 typename _ItemIt,
00045 typename _Value>
00046 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
00047
00048 public:
00049
00051 typedef _Graph Graph;
00053 typedef _Item Key;
00054
00055 typedef AlterationNotifier<_Item> Registry;
00056
00057 private:
00059 typedef _ItemIt KeyIt;
00060
00062 typedef typename Registry::ObserverBase Parent;
00063
00064
00065 public:
00066
00068 typedef _Value Value;
00070 typedef Value& Reference;
00072 typedef Value* Pointer;
00073
00075 typedef const Value ConstValue;
00077 typedef const Value& ConstReference;
00079 typedef const Value* ConstPointer;
00080
00081
00082 private:
00083 typedef std::allocator<Value> Allocator;
00084
00085
00086 public:
00087
00090 ArrayMap(const Graph& _g) : graph(&_g) {
00091 attach(_g.getNotifier(_Item()));
00092 allocate_memory();
00093 for (KeyIt it(*graph); it != INVALID; ++it) {
00094 int id = graph->id(it);;
00095 allocator.construct(&(values[id]), Value());
00096 }
00097 }
00098
00100
00102
00103 ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
00104 attach(_g.getNotifier(_Item()));
00105 allocate_memory();
00106 for (KeyIt it(*graph); it != INVALID; ++it) {
00107 int id = graph->id(it);;
00108 allocator.construct(&(values[id]), _v);
00109 }
00110 }
00111
00114 ArrayMap(const ArrayMap& copy) {
00115 if (copy.attached()) {
00116 attach(*copy.getRegistry());
00117 }
00118 capacity = copy.capacity;
00119 if (capacity == 0) return;
00120 values = allocator.allocate(capacity);
00121 for (KeyIt it(*graph); it != INVALID; ++it) {
00122 int id = graph->id(it);;
00123 allocator.construct(&(values[id]), copy.values[id]);
00124 }
00125 }
00126
00127 using Parent::attach;
00128 using Parent::detach;
00129 using Parent::attached;
00130
00133 ArrayMap& operator=(const ArrayMap& copy) {
00134 if (© == this) return *this;
00135
00136 if (graph != copy.graph) {
00137 if (attached()) {
00138 clear();
00139 detach();
00140 }
00141 if (copy.attached()) {
00142 attach(*copy.getRegistry());
00143 }
00144 capacity = copy.capacity;
00145 if (capacity == 0) return *this;
00146 values = allocator.allocate(capacity);
00147 }
00148
00149 for (KeyIt it(*graph); it != INVALID; ++it) {
00150 int id = graph->id(it);;
00151 allocator.construct(&(values[id]), copy.values[id]);
00152 }
00153
00154 return *this;
00155 }
00156
00159 virtual ~ArrayMap() {
00160 if (attached()) {
00161 clear();
00162 detach();
00163 }
00164 }
00165
00166
00171 Reference operator[](const Key& key) {
00172 int id = graph->id(key);
00173 return values[id];
00174 }
00175
00180 ConstReference operator[](const Key& key) const {
00181 int id = graph->id(key);
00182 return values[id];
00183 }
00184
00188 void set(const Key& key, const Value& val) {
00189 (*this)[key] = val;
00190 }
00191
00194 void add(const Key& key) {
00195 int id = graph->id(key);
00196 if (id >= capacity) {
00197 int new_capacity = (capacity == 0 ? 1 : capacity);
00198 while (new_capacity <= id) {
00199 new_capacity <<= 1;
00200 }
00201 Value* new_values = allocator.allocate(new_capacity);
00202 for (KeyIt it(*graph); it != INVALID; ++it) {
00203 int jd = graph->id(it);;
00204 if (id != jd) {
00205 allocator.construct(&(new_values[jd]), values[jd]);
00206 allocator.destroy(&(values[jd]));
00207 }
00208 }
00209 if (capacity != 0) allocator.deallocate(values, capacity);
00210 values = new_values;
00211 capacity = new_capacity;
00212 }
00213 allocator.construct(&(values[id]), Value());
00214 }
00215
00218 void erase(const Key& key) {
00219 int id = graph->id(key);
00220 allocator.destroy(&(values[id]));
00221 }
00222
00223 void build() {
00224 allocate_memory();
00225 for (KeyIt it(*graph); it != INVALID; ++it) {
00226 int id = graph->id(it);;
00227 allocator.construct(&(values[id]), Value());
00228 }
00229 }
00230
00231 void clear() {
00232 if (capacity != 0) {
00233 for (KeyIt it(*graph); it != INVALID; ++it) {
00234 int id = graph->id(it);;
00235 allocator.destroy(&(values[id]));
00236 }
00237 allocator.deallocate(values, capacity);
00238 capacity = 0;
00239 }
00240 }
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280
00281
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295 private:
00296
00297 void allocate_memory() {
00298 int max_id = graph->maxId(_Item());
00299 if (max_id == -1) {
00300 capacity = 0;
00301 values = 0;
00302 return;
00303 }
00304 capacity = 1;
00305 while (capacity <= max_id) {
00306 capacity <<= 1;
00307 }
00308 values = allocator.allocate(capacity);
00309 }
00310
00311 const Graph* graph;
00312 int capacity;
00313 Value* values;
00314 Allocator allocator;
00315
00316 public:
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328 };
00329
00330 template <typename _Base>
00331 class ArrayMappableGraphExtender : public _Base {
00332 public:
00333
00334 typedef ArrayMappableGraphExtender<_Base> Graph;
00335 typedef _Base Parent;
00336
00337 typedef typename Parent::Node Node;
00338 typedef typename Parent::NodeIt NodeIt;
00339 typedef typename Parent::NodeNotifier NodeObserverRegistry;
00340
00341 typedef typename Parent::Edge Edge;
00342 typedef typename Parent::EdgeIt EdgeIt;
00343 typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
00344
00345
00346
00347 template <typename _Value>
00348 class NodeMap : public ArrayMap<Graph, Node, NodeIt, _Value> {
00349 public:
00350 typedef ArrayMappableGraphExtender<_Base> Graph;
00351
00352 typedef typename Graph::Node Node;
00353 typedef typename Graph::NodeIt NodeIt;
00354
00355 typedef ArrayMap<Graph, Node, NodeIt, _Value> Parent;
00356
00357
00358 typedef typename Parent::Value Value;
00359
00360 NodeMap(const Graph& g)
00361 : Parent(g) {}
00362 NodeMap(const Graph& g, const Value& v)
00363 : Parent(g, v) {}
00364
00365 };
00366
00367 template <typename _Value>
00368 class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, _Value> {
00369 public:
00370 typedef ArrayMappableGraphExtender<_Base> Graph;
00371
00372 typedef typename Graph::Edge Edge;
00373 typedef typename Graph::EdgeIt EdgeIt;
00374
00375 typedef ArrayMap<Graph, Edge, EdgeIt, _Value> Parent;
00376
00377
00378 typedef typename Parent::Value Value;
00379
00380 EdgeMap(const Graph& g)
00381 : Parent(g) {}
00382 EdgeMap(const Graph& g, const Value& v)
00383 : Parent(g, v) {}
00384
00385 };
00386
00387 };
00388
00390
00391 }
00392
00393 #endif //LEMON_ARRAY_MAP_H