1.1 --- a/lemon/bits/array_map.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/bits/array_map.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -38,16 +38,16 @@
1.13 ///
1.14 /// The ArrayMap template class is graph map structure what
1.15 /// automatically updates the map when a key is added to or erased from
1.16 - /// the map. This map uses the allocators to implement
1.17 + /// the map. This map uses the allocators to implement
1.18 /// the container functionality.
1.19 ///
1.20 /// The template parameters are the Graph the current Item type and
1.21 /// the Value type of the map.
1.22 template <typename _Graph, typename _Item, typename _Value>
1.23 - class ArrayMap
1.24 + class ArrayMap
1.25 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
1.26 public:
1.27 - /// The graph type of the maps.
1.28 + /// The graph type of the maps.
1.29 typedef _Graph Graph;
1.30 /// The item type of the map.
1.31 typedef _Item Item;
1.32 @@ -69,7 +69,7 @@
1.33
1.34 /// The MapBase of the Map which imlements the core regisitry function.
1.35 typedef typename Notifier::ObserverBase Parent;
1.36 -
1.37 +
1.38 private:
1.39 typedef std::allocator<Value> Allocator;
1.40
1.41 @@ -84,31 +84,31 @@
1.42 Notifier* nf = Parent::notifier();
1.43 Item it;
1.44 for (nf->first(it); it != INVALID; nf->next(it)) {
1.45 - int id = nf->id(it);;
1.46 - allocator.construct(&(values[id]), Value());
1.47 - }
1.48 + int id = nf->id(it);;
1.49 + allocator.construct(&(values[id]), Value());
1.50 + }
1.51 }
1.52
1.53 - /// \brief Constructor to use default value to initialize the map.
1.54 + /// \brief Constructor to use default value to initialize the map.
1.55 ///
1.56 - /// It constructs a map and initialize all of the the map.
1.57 + /// It constructs a map and initialize all of the the map.
1.58 ArrayMap(const Graph& graph, const Value& value) {
1.59 Parent::attach(graph.notifier(Item()));
1.60 allocate_memory();
1.61 Notifier* nf = Parent::notifier();
1.62 Item it;
1.63 for (nf->first(it); it != INVALID; nf->next(it)) {
1.64 - int id = nf->id(it);;
1.65 - allocator.construct(&(values[id]), value);
1.66 - }
1.67 + int id = nf->id(it);;
1.68 + allocator.construct(&(values[id]), value);
1.69 + }
1.70 }
1.71
1.72 /// \brief Constructor to copy a map of the same map type.
1.73 ///
1.74 - /// Constructor to copy a map of the same map type.
1.75 + /// Constructor to copy a map of the same map type.
1.76 ArrayMap(const ArrayMap& copy) : Parent() {
1.77 if (copy.attached()) {
1.78 - attach(*copy.notifier());
1.79 + attach(*copy.notifier());
1.80 }
1.81 capacity = copy.capacity;
1.82 if (capacity == 0) return;
1.83 @@ -116,18 +116,18 @@
1.84 Notifier* nf = Parent::notifier();
1.85 Item it;
1.86 for (nf->first(it); it != INVALID; nf->next(it)) {
1.87 - int id = nf->id(it);;
1.88 - allocator.construct(&(values[id]), copy.values[id]);
1.89 + int id = nf->id(it);;
1.90 + allocator.construct(&(values[id]), copy.values[id]);
1.91 }
1.92 }
1.93
1.94 /// \brief Assign operator.
1.95 ///
1.96 /// This operator assigns for each item in the map the
1.97 - /// value mapped to the same item in the copied map.
1.98 + /// value mapped to the same item in the copied map.
1.99 /// The parameter map should be indiced with the same
1.100 /// itemset because this assign operator does not change
1.101 - /// the container of the map.
1.102 + /// the container of the map.
1.103 ArrayMap& operator=(const ArrayMap& cmap) {
1.104 return operator=<ArrayMap>(cmap);
1.105 }
1.106 @@ -138,7 +138,7 @@
1.107 /// The given parameter should be conform to the ReadMap
1.108 /// concecpt and could be indiced by the current item set of
1.109 /// the NodeMap. In this case the value for each item
1.110 - /// is assigned by the value of the given ReadMap.
1.111 + /// is assigned by the value of the given ReadMap.
1.112 template <typename CMap>
1.113 ArrayMap& operator=(const CMap& cmap) {
1.114 checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
1.115 @@ -151,15 +151,15 @@
1.116 }
1.117
1.118 /// \brief The destructor of the map.
1.119 - ///
1.120 + ///
1.121 /// The destructor of the map.
1.122 - virtual ~ArrayMap() {
1.123 + virtual ~ArrayMap() {
1.124 if (attached()) {
1.125 - clear();
1.126 - detach();
1.127 + clear();
1.128 + detach();
1.129 }
1.130 }
1.131 -
1.132 +
1.133 protected:
1.134
1.135 using Parent::attach;
1.136 @@ -168,26 +168,26 @@
1.137
1.138 public:
1.139
1.140 - /// \brief The subscript operator.
1.141 + /// \brief The subscript operator.
1.142 ///
1.143 /// The subscript operator. The map can be subscripted by the
1.144 - /// actual keys of the graph.
1.145 + /// actual keys of the graph.
1.146 Value& operator[](const Key& key) {
1.147 int id = Parent::notifier()->id(key);
1.148 return values[id];
1.149 - }
1.150 -
1.151 + }
1.152 +
1.153 /// \brief The const subscript operator.
1.154 ///
1.155 /// The const subscript operator. The map can be subscripted by the
1.156 - /// actual keys of the graph.
1.157 + /// actual keys of the graph.
1.158 const Value& operator[](const Key& key) const {
1.159 int id = Parent::notifier()->id(key);
1.160 return values[id];
1.161 }
1.162
1.163 /// \brief Setter function of the map.
1.164 - ///
1.165 + ///
1.166 /// Setter function of the map. Equivalent with map[key] = val.
1.167 /// This is a compatibility feature with the not dereferable maps.
1.168 void set(const Key& key, const Value& val) {
1.169 @@ -197,81 +197,81 @@
1.170 protected:
1.171
1.172 /// \brief Adds a new key to the map.
1.173 - ///
1.174 + ///
1.175 /// It adds a new key to the map. It called by the observer notifier
1.176 - /// and it overrides the add() member function of the observer base.
1.177 + /// and it overrides the add() member function of the observer base.
1.178 virtual void add(const Key& key) {
1.179 Notifier* nf = Parent::notifier();
1.180 int id = nf->id(key);
1.181 if (id >= capacity) {
1.182 - int new_capacity = (capacity == 0 ? 1 : capacity);
1.183 - while (new_capacity <= id) {
1.184 - new_capacity <<= 1;
1.185 - }
1.186 - Value* new_values = allocator.allocate(new_capacity);
1.187 - Item it;
1.188 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.189 - int jd = nf->id(it);;
1.190 - if (id != jd) {
1.191 - allocator.construct(&(new_values[jd]), values[jd]);
1.192 - allocator.destroy(&(values[jd]));
1.193 - }
1.194 - }
1.195 - if (capacity != 0) allocator.deallocate(values, capacity);
1.196 - values = new_values;
1.197 - capacity = new_capacity;
1.198 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.199 + while (new_capacity <= id) {
1.200 + new_capacity <<= 1;
1.201 + }
1.202 + Value* new_values = allocator.allocate(new_capacity);
1.203 + Item it;
1.204 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.205 + int jd = nf->id(it);;
1.206 + if (id != jd) {
1.207 + allocator.construct(&(new_values[jd]), values[jd]);
1.208 + allocator.destroy(&(values[jd]));
1.209 + }
1.210 + }
1.211 + if (capacity != 0) allocator.deallocate(values, capacity);
1.212 + values = new_values;
1.213 + capacity = new_capacity;
1.214 }
1.215 allocator.construct(&(values[id]), Value());
1.216 }
1.217
1.218 /// \brief Adds more new keys to the map.
1.219 - ///
1.220 + ///
1.221 /// It adds more new keys to the map. It called by the observer notifier
1.222 - /// and it overrides the add() member function of the observer base.
1.223 + /// and it overrides the add() member function of the observer base.
1.224 virtual void add(const std::vector<Key>& keys) {
1.225 Notifier* nf = Parent::notifier();
1.226 int max_id = -1;
1.227 for (int i = 0; i < int(keys.size()); ++i) {
1.228 - int id = nf->id(keys[i]);
1.229 - if (id > max_id) {
1.230 - max_id = id;
1.231 - }
1.232 + int id = nf->id(keys[i]);
1.233 + if (id > max_id) {
1.234 + max_id = id;
1.235 + }
1.236 }
1.237 if (max_id >= capacity) {
1.238 - int new_capacity = (capacity == 0 ? 1 : capacity);
1.239 - while (new_capacity <= max_id) {
1.240 - new_capacity <<= 1;
1.241 - }
1.242 - Value* new_values = allocator.allocate(new_capacity);
1.243 - Item it;
1.244 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.245 - int id = nf->id(it);
1.246 - bool found = false;
1.247 - for (int i = 0; i < int(keys.size()); ++i) {
1.248 - int jd = nf->id(keys[i]);
1.249 - if (id == jd) {
1.250 - found = true;
1.251 - break;
1.252 - }
1.253 - }
1.254 - if (found) continue;
1.255 - allocator.construct(&(new_values[id]), values[id]);
1.256 - allocator.destroy(&(values[id]));
1.257 - }
1.258 - if (capacity != 0) allocator.deallocate(values, capacity);
1.259 - values = new_values;
1.260 - capacity = new_capacity;
1.261 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.262 + while (new_capacity <= max_id) {
1.263 + new_capacity <<= 1;
1.264 + }
1.265 + Value* new_values = allocator.allocate(new_capacity);
1.266 + Item it;
1.267 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.268 + int id = nf->id(it);
1.269 + bool found = false;
1.270 + for (int i = 0; i < int(keys.size()); ++i) {
1.271 + int jd = nf->id(keys[i]);
1.272 + if (id == jd) {
1.273 + found = true;
1.274 + break;
1.275 + }
1.276 + }
1.277 + if (found) continue;
1.278 + allocator.construct(&(new_values[id]), values[id]);
1.279 + allocator.destroy(&(values[id]));
1.280 + }
1.281 + if (capacity != 0) allocator.deallocate(values, capacity);
1.282 + values = new_values;
1.283 + capacity = new_capacity;
1.284 }
1.285 for (int i = 0; i < int(keys.size()); ++i) {
1.286 - int id = nf->id(keys[i]);
1.287 - allocator.construct(&(values[id]), Value());
1.288 + int id = nf->id(keys[i]);
1.289 + allocator.construct(&(values[id]), Value());
1.290 }
1.291 }
1.292 -
1.293 +
1.294 /// \brief Erase a key from the map.
1.295 ///
1.296 /// Erase a key from the map. It called by the observer notifier
1.297 - /// and it overrides the erase() member function of the observer base.
1.298 + /// and it overrides the erase() member function of the observer base.
1.299 virtual void erase(const Key& key) {
1.300 int id = Parent::notifier()->id(key);
1.301 allocator.destroy(&(values[id]));
1.302 @@ -280,67 +280,67 @@
1.303 /// \brief Erase more keys from the map.
1.304 ///
1.305 /// Erase more keys from the map. It called by the observer notifier
1.306 - /// and it overrides the erase() member function of the observer base.
1.307 + /// and it overrides the erase() member function of the observer base.
1.308 virtual void erase(const std::vector<Key>& keys) {
1.309 for (int i = 0; i < int(keys.size()); ++i) {
1.310 - int id = Parent::notifier()->id(keys[i]);
1.311 - allocator.destroy(&(values[id]));
1.312 + int id = Parent::notifier()->id(keys[i]);
1.313 + allocator.destroy(&(values[id]));
1.314 }
1.315 }
1.316
1.317 /// \brief Buildes the map.
1.318 - ///
1.319 + ///
1.320 /// It buildes the map. It called by the observer notifier
1.321 - /// and it overrides the build() member function of the observer base.
1.322 + /// and it overrides the build() member function of the observer base.
1.323 virtual void build() {
1.324 Notifier* nf = Parent::notifier();
1.325 allocate_memory();
1.326 Item it;
1.327 for (nf->first(it); it != INVALID; nf->next(it)) {
1.328 - int id = nf->id(it);;
1.329 - allocator.construct(&(values[id]), Value());
1.330 - }
1.331 + int id = nf->id(it);;
1.332 + allocator.construct(&(values[id]), Value());
1.333 + }
1.334 }
1.335
1.336 /// \brief Clear the map.
1.337 ///
1.338 /// It erase all items from the map. It called by the observer notifier
1.339 - /// and it overrides the clear() member function of the observer base.
1.340 - virtual void clear() {
1.341 + /// and it overrides the clear() member function of the observer base.
1.342 + virtual void clear() {
1.343 Notifier* nf = Parent::notifier();
1.344 if (capacity != 0) {
1.345 - Item it;
1.346 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.347 - int id = nf->id(it);
1.348 - allocator.destroy(&(values[id]));
1.349 - }
1.350 - allocator.deallocate(values, capacity);
1.351 - capacity = 0;
1.352 + Item it;
1.353 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.354 + int id = nf->id(it);
1.355 + allocator.destroy(&(values[id]));
1.356 + }
1.357 + allocator.deallocate(values, capacity);
1.358 + capacity = 0;
1.359 }
1.360 }
1.361
1.362 private:
1.363 -
1.364 +
1.365 void allocate_memory() {
1.366 int max_id = Parent::notifier()->maxId();
1.367 if (max_id == -1) {
1.368 - capacity = 0;
1.369 - values = 0;
1.370 - return;
1.371 + capacity = 0;
1.372 + values = 0;
1.373 + return;
1.374 }
1.375 capacity = 1;
1.376 while (capacity <= max_id) {
1.377 - capacity <<= 1;
1.378 + capacity <<= 1;
1.379 }
1.380 - values = allocator.allocate(capacity);
1.381 - }
1.382 + values = allocator.allocate(capacity);
1.383 + }
1.384
1.385 int capacity;
1.386 Value* values;
1.387 Allocator allocator;
1.388
1.389 - };
1.390 + };
1.391
1.392 }
1.393
1.394 -#endif
1.395 +#endif