Changeset 1414:01d9d6bc1284 in lemon-0.x for src/lemon/bits/array_map.h
- Timestamp:
- 05/14/05 19:20:40 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1884
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/bits/array_map.h
r1374 r1414 1 1 /* -*- C++ -*- 2 * src/lemon/ array_map.h - Part of LEMON, a generic C++ optimization library2 * src/lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library 3 3 * 4 4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport … … 32 32 /// @{ 33 33 34 / **The ArrayMap template class is graph map structure what35 *automatically updates the map when a key is added to or erased from36 *the map. This map factory uses the allocators to implement37 *the container functionality.38 *39 *The template parameter is the AlterationNotifier that the maps40 *will belong to and the Value.41 */34 /// The ArrayMap template class is graph map structure what 35 /// automatically updates the map when a key is added to or erased from 36 /// the map. This map factory uses the allocators to implement 37 /// the container functionality. 38 /// 39 /// The template parameter is the AlterationNotifier that the maps 40 /// will belong to and the Value. 41 42 42 43 43 template <typename _Graph, … … 69 69 public: 70 70 71 / **Graph and Registry initialized map constructor.72 */71 /// Graph and Registry initialized map constructor. 72 73 73 ArrayMap(const Graph& _g) : graph(&_g) { 74 74 Item it; … … 95 95 } 96 96 97 / **Constructor to copy a map of the same map type.98 */97 /// Constructor to copy a map of the same map type. 98 99 99 ArrayMap(const ArrayMap& copy) : Parent() { 100 100 if (copy.attached()) { … … 115 115 using Parent::attached; 116 116 117 / **Assign operator to copy a map of the same map type.118 */117 /// Assign operator to copy a map of the same map type. 118 119 119 ArrayMap& operator=(const ArrayMap& copy) { 120 120 if (© == this) return *this; … … 142 142 } 143 143 144 / **The destructor of the map.145 */144 /// The destructor of the map. 145 146 146 virtual ~ArrayMap() { 147 147 if (attached()) { … … 152 152 153 153 154 /** 155 * The subscript operator. The map can be subscripted by the 156 * actual keys of the graph. 157 */ 154 ///The subscript operator. The map can be subscripted by the 155 ///actual keys of the graph. 156 158 157 Value& operator[](const Key& key) { 159 158 int id = graph->id(key); … … 161 160 } 162 161 163 /** 164 *The const subscript operator. The map can be subscripted by the165 *actual keys of the graph.166 */162 163 ///The const subscript operator. The map can be subscripted by the 164 ///actual keys of the graph. 165 167 166 const Value& operator[](const Key& key) const { 168 167 int id = graph->id(key); … … 170 169 } 171 170 172 / **Setter function of the map. Equivalent with map[key] = val.173 *This is a compatibility feature with the not dereferable maps.174 */171 /// Setter function of the map. Equivalent with map[key] = val. 172 /// This is a compatibility feature with the not dereferable maps. 173 175 174 void set(const Key& key, const Value& val) { 176 175 (*this)[key] = val; 177 176 } 178 177 179 / **Add a new key to the map. It called by the map registry.180 */178 /// Add a new key to the map. It called by the map registry. 179 181 180 void add(const Key& key) { 182 181 int id = graph->id(key); … … 201 200 allocator.construct(&(values[id]), Value()); 202 201 } 203 204 /** Erase a key from the map. It called by the map registry. 205 */ 202 203 void add(const std::vector<Key>& keys) { 204 int max_id = -1; 205 for (int i = 0; i < (int)keys.size(); ++i) { 206 int id = graph->id(keys[i]); 207 if (id > max_id) { 208 max_id = id; 209 } 210 } 211 if (max_id >= capacity) { 212 int new_capacity = (capacity == 0 ? 1 : capacity); 213 while (new_capacity <= max_id) { 214 new_capacity <<= 1; 215 } 216 Value* new_values = allocator.allocate(new_capacity); 217 Item it; 218 for (graph->first(it); it != INVALID; graph->next(it)) { 219 int id = graph->id(it); 220 bool found = false; 221 for (int i = 0; i < (int)keys.size(); ++i) { 222 int jd = graph->id(keys[i]); 223 if (id == jd) { 224 found = true; 225 break; 226 } 227 } 228 if (found) continue; 229 allocator.construct(&(new_values[id]), values[id]); 230 allocator.destroy(&(values[id])); 231 } 232 if (capacity != 0) allocator.deallocate(values, capacity); 233 values = new_values; 234 capacity = new_capacity; 235 } 236 for (int i = 0; i < (int)keys.size(); ++i) { 237 int id = graph->id(keys[i]); 238 allocator.construct(&(values[id]), Value()); 239 } 240 } 241 242 /// Erase a key from the map. It called by the map registry. 243 206 244 void erase(const Key& key) { 207 245 int id = graph->id(key); 208 246 allocator.destroy(&(values[id])); 247 } 248 249 void erase(const std::vector<Key>& keys) { 250 for (int i = 0; i < (int)keys.size(); ++i) { 251 int id = graph->id(keys[i]); 252 allocator.destroy(&(values[id])); 253 } 209 254 } 210 255 … … 222 267 Item it; 223 268 for (graph->first(it); it != INVALID; graph->next(it)) { 224 int id = graph->id(it); ;269 int id = graph->id(it); 225 270 allocator.destroy(&(values[id])); 226 271 } … … 233 278 return graph; 234 279 } 235 236 // /// The stl compatible pair iterator of the map.237 // typedef MapIterator<ArrayMap> Iterator;238 // /// The stl compatible const pair iterator of the map.239 // typedef MapConstIterator<ArrayMap> ConstIterator;240 241 // /** Returns the begin iterator of the map.242 // */243 // Iterator begin() {244 // return Iterator(*this, KeyIt(*MapBase::getGraph()));245 // }246 247 // /** Returns the end iterator of the map.248 // */249 // Iterator end() {250 // return Iterator(*this, INVALID);251 // }252 253 // /** Returns the begin ConstIterator of the map.254 // */255 // ConstIterator begin() const {256 // return ConstIterator(*this, KeyIt(*MapBase::getGraph()));257 // }258 259 // /** Returns the end const_iterator of the map.260 // */261 // ConstIterator end() const {262 // return ConstIterator(*this, INVALID);263 // }264 265 // /// The KeySet of the Map.266 // typedef MapConstKeySet<ArrayMap> ConstKeySet;267 268 // /// KeySet getter function.269 // ConstKeySet keySet() const {270 // return ConstKeySet(*this);271 // }272 273 // /// The ConstValueSet of the Map.274 // typedef MapConstValueSet<ArrayMap> ConstValueSet;275 276 // /// ConstValueSet getter function.277 // ConstValueSet valueSet() const {278 // return ConstValueSet(*this);279 // }280 281 // /// The ValueSet of the Map.282 // typedef MapValueSet<ArrayMap> ValueSet;283 284 // /// ValueSet getter function.285 // ValueSet valueSet() {286 // return ValueSet(*this);287 // }288 280 289 281 private:
Note: See TracChangeset
for help on using the changeset viewer.