Changeset 946:c94ef40a22ce in lemon0.x for src/lemon/array_map.h
 Timestamp:
 10/28/04 00:38:50 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1322
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/array_map.h
r921 r946 21 21 22 22 #include <lemon/map_iterator.h> 23 #include <lemon/map_bits.h>24 23 25 24 ///\ingroup graphmaps … … 43 42 */ 44 43 45 template <typename MapRegistry, typename Value> 46 class ArrayMap : public MapRegistry::MapBase { 47 48 template <typename MR, typename V> friend class ArrayMap; 49 44 template <typename _Graph, 45 typename _Item, 46 typename _ItemIt, 47 typename _IdMap, 48 typename _Value> 49 class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase { 50 50 51 public: 51 52 52 53 /// The graph type of the maps. 53 typedef typename MapRegistry::Graph Graph;54 typedef _Graph Graph; 54 55 /// The key type of the maps. 55 typedef typename MapRegistry::KeyType KeyType; 56 typedef _Item KeyType; 57 58 typedef AlterationObserverRegistry<_Item> Registry; 59 60 private: 56 61 /// The iterator to iterate on the keys. 57 typedef typename MapRegistry::KeyIt KeyIt; 62 typedef _ItemIt KeyIt; 63 64 typedef _IdMap IdMap; 65 66 typedef _Value Value; 58 67 59 68 /// The MapBase of the Map which imlements the core regisitry function. 60 typedef typename MapRegistry::MapBase MapBase;69 typedef typename Registry::ObserverBase Parent; 61 70 62 71 … … 78 87 79 88 89 private: 80 90 typedef std::allocator<Value> Allocator; 81 91 82 92 93 public: 94 83 95 /** Graph and Registry initialized map constructor. 84 96 */ 85 ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) { 97 ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) { 98 attach(_r); 86 99 allocate_memory(); 87 for (KeyIt it(* MapBase::getGraph()); it != INVALID; ++it) {88 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);100 for (KeyIt it(*graph); it != INVALID; ++it) { 101 int id = IdMap(*graph)[it]; 89 102 allocator.construct(&(values[id]), Value()); 90 103 } 91 104 } 92 105 93 /** Constructor to use default value to initialize the map. 94 */ 95 ArrayMap(const Graph& g, MapRegistry& r, const Value& v) 96 : MapBase(g, r) { 106 /// Constructor to use default value to initialize the map. 107 108 /// It constrates a map and initialize all of the the map. 109 110 ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) { 111 attach(_r); 97 112 allocate_memory(); 98 for (KeyIt it(* MapBase::getGraph()); it != INVALID; ++it) {99 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);100 allocator.construct(&(values[id]), v);113 for (KeyIt it(*graph); it != INVALID; ++it) { 114 int id = IdMap(*graph)[it]; 115 allocator.construct(&(values[id]), _v); 101 116 } 102 117 } … … 104 119 /** Constructor to copy a map of the same map type. 105 120 */ 106 ArrayMap(const ArrayMap& copy) : MapBase(copy) { 121 ArrayMap(const ArrayMap& copy) { 122 if (copy.attached()) { 123 attach(*copy.getRegistry()); 124 } 107 125 capacity = copy.capacity; 108 126 if (capacity == 0) return; 109 127 values = allocator.allocate(capacity); 110 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { 111 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); 112 allocator.construct(&(values[id]), copy.values[id]); 113 } 114 } 115 116 /** Constructor to copy a map of an other map type. 117 */ 118 template <typename TT> 119 ArrayMap(const ArrayMap<MapRegistry, TT>& copy) 120 : MapBase(copy) { 121 capacity = copy.capacity; 122 if (capacity == 0) return; 123 values = allocator.allocate(capacity); 124 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { 125 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); 128 for (KeyIt it(*graph); it != INVALID; ++it) { 129 int id = IdMap(*graph)[it]; 126 130 allocator.construct(&(values[id]), copy.values[id]); 127 131 } … … 133 137 if (© == this) return *this; 134 138 135 if ( MapBase::getGraph() != copy.getGraph()) {136 if ( capacity != 0) {137 MapBase::destroy();138 allocator.deallocate(values, capacity);139 if (graph != copy.graph) { 140 if (attached()) { 141 clear(); 142 detach(); 139 143 } 140 141 MapBase::operator=(copy); 144 if (copy.attached()) { 145 attach(*copy.getRegistry()); 146 } 142 147 capacity = copy.capacity; 143 148 if (capacity == 0) return *this; … … 145 150 } 146 151 147 for (KeyIt it(* MapBase::getGraph()); it != INVALID; ++it) {148 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);152 for (KeyIt it(*graph); it != INVALID; ++it) { 153 int id = IdMap(*graph)[it]; 149 154 allocator.construct(&(values[id]), copy.values[id]); 150 155 } … … 153 158 } 154 159 155 /** Assign operator to copy a map of an other map type.156 */157 template <typename TT>158 ArrayMap& operator=(const ArrayMap<MapRegistry, TT>& copy) {159 160 if (MapBase::getGraph() != copy.getGraph()) {161 if (capacity != 0) {162 MapBase::destroy();163 allocator.deallocate(values, capacity);164 }165 166 MapBase::operator=(copy);167 168 capacity = copy.capacity;169 if (capacity == 0) return *this;170 values = allocator.allocate(capacity);171 }172 173 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {174 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);175 allocator.construct(&(values[id]), copy.values[id]);176 }177 178 return *this;179 }180 181 160 /** The destructor of the map. 182 161 */ 183 virtual ~ArrayMap() { 184 if ( capacity != 0) {185 MapBase::destroy();186 allocator.deallocate(values, capacity);162 virtual ~ArrayMap() { 163 if (attached()) { 164 clear(); 165 detach(); 187 166 } 188 167 } … … 194 173 */ 195 174 ReferenceType operator[](const KeyType& key) { 196 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);175 int id = IdMap(*graph)[key]; 197 176 return values[id]; 198 177 } … … 203 182 */ 204 183 ConstReferenceType operator[](const KeyType& key) const { 205 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);184 int id = IdMap(*graph)[key]; 206 185 return values[id]; 207 186 } … … 211 190 */ 212 191 void set(const KeyType& key, const ValueType& val) { 213 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); 214 values[id] = val; 192 (*this)[key] = val; 215 193 } 216 194 … … 218 196 */ 219 197 void add(const KeyType& key) { 220 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);198 int id = IdMap(*graph)[key]; 221 199 if (id >= capacity) { 222 200 int new_capacity = (capacity == 0 ? 1 : capacity); … … 224 202 new_capacity <<= 1; 225 203 } 226 Value* new_values = allocator.allocate(new_capacity); ;227 for (KeyIt it(* MapBase::getGraph()); it != INVALID; ++it) {228 int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);204 Value* new_values = allocator.allocate(new_capacity); 205 for (KeyIt it(*graph); it != INVALID; ++it) { 206 int jd = IdMap(*graph)[it]; 229 207 if (id != jd) { 230 208 allocator.construct(&(new_values[jd]), values[jd]); … … 242 220 */ 243 221 void erase(const KeyType& key) { 244 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);222 int id = IdMap(*graph)[key]; 245 223 allocator.destroy(&(values[id])); 246 224 } 247 225 248 /** Clear the data structure. 249 */ 226 void build() { 227 allocate_memory(); 228 for (KeyIt it(*graph); it != INVALID; ++it) { 229 int id = IdMap(*graph)[it]; 230 allocator.construct(&(values[id]), Value()); 231 } 232 } 233 250 234 void clear() { 251 235 if (capacity != 0) { 252 MapBase::destroy(); 236 for (KeyIt it(*graph); it != INVALID; ++it) { 237 int id = IdMap(*graph)[it]; 238 allocator.destroy(&(values[id])); 239 } 253 240 allocator.deallocate(values, capacity); 254 241 capacity = 0; … … 256 243 } 257 244 258 /// The stl compatible pair iterator of the map.259 typedef MapIterator<ArrayMap> Iterator;260 /// The stl compatible const pair iterator of the map.261 typedef MapConstIterator<ArrayMap> ConstIterator;262 263 /** Returns the begin iterator of the map.264 */265 Iterator begin() {266 return Iterator(*this, KeyIt(*MapBase::getGraph()));267 }268 269 /** Returns the end iterator of the map.270 */271 Iterator end() {272 return Iterator(*this, INVALID);273 }274 275 /** Returns the begin ConstIterator of the map.276 */277 ConstIterator begin() const {278 return ConstIterator(*this, KeyIt(*MapBase::getGraph()));279 }280 281 /** Returns the end const_iterator of the map.282 */283 ConstIterator end() const {284 return ConstIterator(*this, INVALID);285 }286 287 /// The KeySet of the Map.288 typedef MapConstKeySet<ArrayMap> ConstKeySet;289 290 /// KeySet getter function.291 ConstKeySet keySet() const {292 return ConstKeySet(*this);293 }294 295 /// The ConstValueSet of the Map.296 typedef MapConstValueSet<ArrayMap> ConstValueSet;297 298 /// ConstValueSet getter function.299 ConstValueSet valueSet() const {300 return ConstValueSet(*this);301 }302 303 /// The ValueSet of the Map.304 typedef MapValueSet<ArrayMap> ValueSet;305 306 /// ValueSet getter function.307 ValueSet valueSet() {308 return ValueSet(*this);309 }245 // /// The stl compatible pair iterator of the map. 246 // typedef MapIterator<ArrayMap> Iterator; 247 // /// The stl compatible const pair iterator of the map. 248 // typedef MapConstIterator<ArrayMap> ConstIterator; 249 250 // /** Returns the begin iterator of the map. 251 // */ 252 // Iterator begin() { 253 // return Iterator(*this, KeyIt(*MapBase::getGraph())); 254 // } 255 256 // /** Returns the end iterator of the map. 257 // */ 258 // Iterator end() { 259 // return Iterator(*this, INVALID); 260 // } 261 262 // /** Returns the begin ConstIterator of the map. 263 // */ 264 // ConstIterator begin() const { 265 // return ConstIterator(*this, KeyIt(*MapBase::getGraph())); 266 // } 267 268 // /** Returns the end const_iterator of the map. 269 // */ 270 // ConstIterator end() const { 271 // return ConstIterator(*this, INVALID); 272 // } 273 274 // /// The KeySet of the Map. 275 // typedef MapConstKeySet<ArrayMap> ConstKeySet; 276 277 // /// KeySet getter function. 278 // ConstKeySet keySet() const { 279 // return ConstKeySet(*this); 280 // } 281 282 // /// The ConstValueSet of the Map. 283 // typedef MapConstValueSet<ArrayMap> ConstValueSet; 284 285 // /// ConstValueSet getter function. 286 // ConstValueSet valueSet() const { 287 // return ConstValueSet(*this); 288 // } 289 290 // /// The ValueSet of the Map. 291 // typedef MapValueSet<ArrayMap> ValueSet; 292 293 // /// ValueSet getter function. 294 // ValueSet valueSet() { 295 // return ValueSet(*this); 296 // } 310 297 311 298 private: 312 299 313 300 void allocate_memory() { 314 int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());301 int max_id = IdMap(*graph).maxId(); 315 302 if (max_id == 1) { 316 303 capacity = 0; … … 325 312 } 326 313 314 const Graph* graph; 327 315 int capacity; 328 316 Value* values; … … 330 318 331 319 public: 332 // STL compatibility typedefs.333 typedef Iterator iterator;334 typedef ConstIterator const_iterator;335 typedef typename Iterator::PairValueType value_type;336 typedef typename Iterator::KeyType key_type;337 typedef typename Iterator::ValueType data_type;338 typedef typename Iterator::PairReferenceType reference;339 typedef typename Iterator::PairPointerType pointer;340 typedef typename ConstIterator::PairReferenceType const_reference;341 typedef typename ConstIterator::PairPointerType const_pointer;342 typedef int difference_type;320 // // STL compatibility typedefs. 321 // typedef Iterator iterator; 322 // typedef ConstIterator const_iterator; 323 // typedef typename Iterator::PairValueType value_type; 324 // typedef typename Iterator::KeyType key_type; 325 // typedef typename Iterator::ValueType data_type; 326 // typedef typename Iterator::PairReferenceType reference; 327 // typedef typename Iterator::PairPointerType pointer; 328 // typedef typename ConstIterator::PairReferenceType const_reference; 329 // typedef typename ConstIterator::PairPointerType const_pointer; 330 // typedef int difference_type; 343 331 }; 344 332 333 template <typename _Base> 334 class ArrayMappableGraphExtender : public _Base { 335 public: 336 337 typedef ArrayMappableGraphExtender<_Base> Graph; 338 typedef _Base Parent; 339 340 typedef typename Parent::Node Node; 341 typedef typename Parent::NodeIt NodeIt; 342 typedef typename Parent::NodeIdMap NodeIdMap; 343 typedef typename Parent::NodeObserverRegistry NodeObserverRegistry; 344 345 typedef typename Parent::Edge Edge; 346 typedef typename Parent::EdgeIt EdgeIt; 347 typedef typename Parent::EdgeIdMap EdgeIdMap; 348 typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry; 349 350 351 352 template <typename _Value> 353 class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> { 354 public: 355 typedef ArrayMappableGraphExtender<_Base> Graph; 356 357 typedef typename Graph::Node Node; 358 typedef typename Graph::NodeIt NodeIt; 359 typedef typename Graph::NodeIdMap NodeIdMap; 360 361 typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent; 362 363 typedef typename Parent::Graph Graph; 364 typedef typename Parent::Value Value; 365 366 NodeMap(const Graph& g) 367 : Parent(g, g.getNodeObserverRegistry()) {} 368 NodeMap(const Graph& g, const Value& v) 369 : Parent(g, g.getNodeObserverRegistry(), v) {} 370 371 }; 372 373 template <typename _Value> 374 class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> { 375 public: 376 typedef ArrayMappableGraphExtender<_Base> Graph; 377 378 typedef typename Graph::Edge Edge; 379 typedef typename Graph::EdgeIt EdgeIt; 380 typedef typename Graph::EdgeIdMap EdgeIdMap; 381 382 typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent; 383 384 typedef typename Parent::Graph Graph; 385 typedef typename Parent::Value Value; 386 387 EdgeMap(const Graph& g) 388 : Parent(g, g.getEdgeObserverRegistry()) {} 389 EdgeMap(const Graph& g, const Value& v) 390 : Parent(g, g.getEdgeObserverRegistry(), v) {} 391 392 }; 393 394 }; 395 345 396 /// @} 346 397
Note: See TracChangeset
for help on using the changeset viewer.