1.1 --- a/lemon/Makefile.am Mon Mar 06 09:38:19 2006 +0000
1.2 +++ b/lemon/Makefile.am Mon Mar 06 10:28:37 2006 +0000
1.3 @@ -84,8 +84,8 @@
1.4 tolerance.h \
1.5 bits/alteration_notifier.h \
1.6 bits/array_map.h \
1.7 + bits/base_extender.h \
1.8 bits/default_map.h \
1.9 - bits/static_map.h \
1.10 bits/vector_map.h \
1.11 bits/map_extender.h \
1.12 bits/graph_extender.h \
2.1 --- a/lemon/bits/alteration_notifier.h Mon Mar 06 09:38:19 2006 +0000
2.2 +++ b/lemon/bits/alteration_notifier.h Mon Mar 06 10:28:37 2006 +0000
2.3 @@ -16,48 +16,91 @@
2.4 *
2.5 */
2.6
2.7 -#ifndef LEMON_ALTERATION_NOTIFIER_H
2.8 -#define LEMON_ALTERATION_NOTIFIER_H
2.9 +#ifndef LEMON_BITS_ALTERATION_NOTIFIER_H
2.10 +#define LEMON_BITS_ALTERATION_NOTIFIER_H
2.11
2.12 #include <vector>
2.13 -#include <algorithm>
2.14 +
2.15 +#include <lemon/bits/utility.h>
2.16
2.17 ///\ingroup graphbits
2.18 ///\file
2.19 -///\brief Observer registry for graph alteration observers.
2.20 +///\brief Observer notifier for graph alteration observers.
2.21
2.22 namespace lemon {
2.23
2.24 - /// \addtogroup graphbits
2.25 - /// @{
2.26 -
2.27 - /// \brief Registry class to register objects observes alterations in
2.28 - /// the graph.
2.29 + /// \ingroup graphbits
2.30 ///
2.31 - /// This class is a registry for the objects which observe the
2.32 - /// alterations in a container. The alteration observers can be attached
2.33 - /// to and detached from the registry. The observers have to inherit
2.34 - /// from the \ref AlterationNotifier::ObserverBase and override
2.35 - /// the virtual functions in that.
2.36 + /// \brief Notifier class to notify observes about alterations in
2.37 + /// a container.
2.38 ///
2.39 - /// The most important application of the alteration observing is the
2.40 - /// dynamic map implementation.
2.41 + /// The simple graph's can be refered as two containers, one node container
2.42 + /// and one edge container. But they are not standard containers they
2.43 + /// does not store values directly they are just key continars for more
2.44 + /// value containers which are the node and edge maps.
2.45 ///
2.46 - /// \param _Item The item type what the observers are observing, usually
2.47 - /// edge or node.
2.48 + /// The graph's node and edge sets can be changed as we add or erase
2.49 + /// nodes and edges in the graph. Lemon would like to handle easily
2.50 + /// that the node and edge maps should contain values for all nodes or
2.51 + /// edges. If we want to check on every indicing if the map contains
2.52 + /// the current indicing key that cause a drawback in the performance
2.53 + /// in the library. We use an other solution we notify all maps about
2.54 + /// an alteration in the graph, which cause only drawback on the
2.55 + /// alteration of the graph.
2.56 + ///
2.57 + /// This class provides an interface to the container. The \e first() and \e
2.58 + /// next() member functions make possible to iterate on the keys of the
2.59 + /// container. The \e id() function returns an integer id for each key.
2.60 + /// The \e maxId() function gives back an upper bound of the ids.
2.61 + ///
2.62 + /// For the proper functonality of this class, we should notify it
2.63 + /// about each alteration in the container. The alterations have four type
2.64 + /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
2.65 + /// \e erase() signals that only one or few items added or erased to or
2.66 + /// from the graph. If all items are erased from the graph or from an empty
2.67 + /// graph a new graph is builded then it can be signaled with the
2.68 + /// clear() and build() members. Important rule that if we erase items
2.69 + /// from graph we should first signal the alteration and after that erase
2.70 + /// them from the container, on the other way on item addition we should
2.71 + /// first extend the container and just after that signal the alteration.
2.72 + ///
2.73 + /// The alteration can be observed with a class inherited from the
2.74 + /// \e ObserverBase nested class. The signals can be handled with
2.75 + /// overriding the virtual functions defined in the base class.
2.76 + /// The observer base can be attached to the notifier with the
2.77 + /// \e attach() member and can be detached with detach() function.
2.78 + ///
2.79 + /// Alteration observers try to be exception safe. This can be achived
2.80 + /// when the observers does not throw exception on \e erase() and
2.81 + /// \e clear(). Less strict condition is that the \e erase() should
2.82 + /// not throw exception after an \e add() with the same parameter and
2.83 + /// the \e clear() should not throw exception after a \e build().
2.84 + ///
2.85 + /// There are some place when the alteration observing is not completly
2.86 + /// reliable. If we want to carry out the node degree in the graph
2.87 + /// as in the \ref InDegMap and we use the reverseEdge that cause
2.88 + /// unreliable functionality. Because the alteration observing signals
2.89 + /// only erasing and adding but not the reversing it will stores bad
2.90 + /// degrees. The sub graph adaptors cannot signal the alterations because
2.91 + /// just a setting in the filter map can modify the graph and this cannot
2.92 + /// be watched in any way.
2.93 + ///
2.94 + /// \param _Container The container which is observed.
2.95 + /// \param _Item The item type which is obserbved.
2.96 ///
2.97 /// \author Balazs Dezso
2.98
2.99 - template <typename _Item>
2.100 + template <typename _Container, typename _Item>
2.101 class AlterationNotifier {
2.102 public:
2.103
2.104 typedef True Notifier;
2.105
2.106 + typedef _Container Container;
2.107 typedef _Item Item;
2.108
2.109 - /// ObserverBase is the base class for the observers.
2.110 -
2.111 + /// \brief ObserverBase is the base class for the observers.
2.112 + ///
2.113 /// ObserverBase is the abstract base class for the observers.
2.114 /// It will be notified about an item was inserted into or
2.115 /// erased from the graph.
2.116 @@ -75,7 +118,7 @@
2.117
2.118 class ObserverBase {
2.119 protected:
2.120 - typedef AlterationNotifier Registry;
2.121 + typedef AlterationNotifier Notifier;
2.122
2.123 friend class AlterationNotifier;
2.124
2.125 @@ -83,23 +126,39 @@
2.126 ///
2.127 /// Default constructor for ObserverBase.
2.128 ///
2.129 - ObserverBase() : registry(0) {}
2.130 + ObserverBase() : notifier(0) {}
2.131
2.132 + /// \brief Constructor which attach the observer into notifier.
2.133 + ///
2.134 + /// Constructor which attach the observer into notifier.
2.135 + ObserverBase(AlterationNotifier& _notifier) {
2.136 + attach(_notifier);
2.137 + }
2.138 +
2.139 + /// \brief Constructor which attach the obserever to the same notifier.
2.140 + ///
2.141 + /// Constructor which attach the obserever to the same notifier as
2.142 + /// the other observer is attached to.
2.143 ObserverBase(const ObserverBase& copy) {
2.144 if (copy.attached()) {
2.145 - copy.getRegistry()->attach(*this);
2.146 + attach(*copy.getNotifier());
2.147 }
2.148 }
2.149
2.150 - virtual ~ObserverBase() {}
2.151 + /// \brief Destructor
2.152 + virtual ~ObserverBase() {
2.153 + if (attached()) {
2.154 + detach();
2.155 + }
2.156 + }
2.157
2.158 /// \brief Attaches the observer into an AlterationNotifier.
2.159 ///
2.160 /// This member attaches the observer into an AlterationNotifier.
2.161 ///
2.162 - void attach(AlterationNotifier& r) {
2.163 - registry = &r;
2.164 - registry->attach(*this);
2.165 + void attach(AlterationNotifier& _notifier) {
2.166 + notifier = &_notifier;
2.167 + notifier->attach(*this);
2.168 }
2.169
2.170 /// \brief Detaches the observer into an AlterationNotifier.
2.171 @@ -107,21 +166,20 @@
2.172 /// This member detaches the observer from an AlterationNotifier.
2.173 ///
2.174 void detach() {
2.175 - if (registry) {
2.176 - registry->detach(*this);
2.177 - }
2.178 + notifier->detach(*this);
2.179 }
2.180
2.181
2.182 - /// Gives back a pointer to the registry what the map attached into.
2.183 -
2.184 - /// This function gives back a pointer to the registry what the map
2.185 + /// \brief Gives back a pointer to the notifier which the map
2.186 /// attached into.
2.187 ///
2.188 - Registry* getRegistry() const { return const_cast<Registry*>(registry); }
2.189 + /// This function gives back a pointer to the notifier which the map
2.190 + /// attached into.
2.191 + ///
2.192 + Notifier* getNotifier() const { return const_cast<Notifier*>(notifier); }
2.193
2.194 - /// Gives back true when the observer is attached into a registry.
2.195 - bool attached() const { return registry != 0; }
2.196 + /// Gives back true when the observer is attached into a notifier.
2.197 + bool attached() const { return notifier != 0; }
2.198
2.199 private:
2.200
2.201 @@ -129,8 +187,8 @@
2.202
2.203 protected:
2.204
2.205 - Registry* registry;
2.206 - int registry_index;
2.207 + Notifier* notifier;
2.208 + int notifier_index;
2.209
2.210 /// \brief The member function to notificate the observer about an
2.211 /// item is added to the container.
2.212 @@ -149,9 +207,17 @@
2.213 /// subclasses.
2.214
2.215 virtual void add(const std::vector<Item>& items) {
2.216 - for (int i = 0; i < (int)items.size(); ++i) {
2.217 - add(items[i]);
2.218 - }
2.219 + int i;
2.220 + try {
2.221 + for (i = 0; i < (int)items.size(); ++i) {
2.222 + add(items[i]);
2.223 + }
2.224 + } catch (...) {
2.225 + for (int j = 0; j < i; ++j) {
2.226 + add(items[j]);
2.227 + }
2.228 + throw;
2.229 + }
2.230 }
2.231
2.232 /// \brief The member function to notificate the observer about an
2.233 @@ -170,9 +236,9 @@
2.234 /// is erased from the container. It have to be overrided in the
2.235 /// subclasses.
2.236 virtual void erase(const std::vector<Item>& items) {
2.237 - for (int i = 0; i < (int)items.size(); ++i) {
2.238 - erase(items[i]);
2.239 - }
2.240 + for (int i = 0; i < (int)items.size(); ++i) {
2.241 + erase(items[i]);
2.242 + }
2.243 }
2.244
2.245 /// \brief The member function to notificate the observer about the
2.246 @@ -182,166 +248,222 @@
2.247 /// container is built from an empty container. It have to be
2.248 /// overrided in the subclasses.
2.249
2.250 - virtual void build() = 0;
2.251 + virtual void build() {
2.252 + Item it;
2.253 + try {
2.254 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
2.255 + add(it);
2.256 + }
2.257 + } catch (...) {
2.258 + Item jt;
2.259 + for (notifier->first(jt); jt != it; notifier->next(jt)) {
2.260 + erase(jt);
2.261 + }
2.262 + throw;
2.263 + }
2.264 + }
2.265
2.266 /// \brief The member function to notificate the observer about all
2.267 /// items are erased from the container.
2.268 ///
2.269 /// The clear() member function notificates the observer about all
2.270 /// items are erased from the container. It have to be overrided in
2.271 - /// the subclasses.
2.272 -
2.273 - virtual void clear() = 0;
2.274 + /// the subclasses.
2.275 + virtual void clear() {
2.276 + Item it;
2.277 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
2.278 + erase(it);
2.279 + }
2.280 + }
2.281
2.282 };
2.283
2.284 protected:
2.285 -
2.286
2.287 - typedef std::vector<ObserverBase*> Container;
2.288 + const Container* container;
2.289
2.290 - Container container;
2.291 + typedef std::vector<ObserverBase*> Observers;
2.292 + Observers observers;
2.293
2.294
2.295 public:
2.296
2.297 - /// Default constructor.
2.298 -
2.299 + /// \brief Default constructor.
2.300 ///
2.301 /// The default constructor of the AlterationNotifier.
2.302 - /// It creates an empty registry.
2.303 - AlterationNotifier() {}
2.304 + /// It creates an empty notifier.
2.305 + AlterationNotifier()
2.306 + : container(0) {}
2.307
2.308 - /// Copy Constructor of the AlterationNotifier.
2.309 -
2.310 + /// \brief Constructor.
2.311 + ///
2.312 + /// Constructor with the observed container parameter.
2.313 + AlterationNotifier(const Container& _container)
2.314 + : container(&_container) {}
2.315 +
2.316 + /// \brief Copy Constructor of the AlterationNotifier.
2.317 + ///
2.318 /// Copy constructor of the AlterationNotifier.
2.319 - /// It creates only an empty registry because the copiable
2.320 - /// registry's observers have to be registered still into that registry.
2.321 - AlterationNotifier(const AlterationNotifier&) {}
2.322 + /// It creates only an empty notifier because the copiable
2.323 + /// notifier's observers have to be registered still into that notifier.
2.324 + AlterationNotifier(const AlterationNotifier& _notifier)
2.325 + : container(_notifier.container) {}
2.326
2.327 - /// Assign operator.
2.328 -
2.329 - /// Assign operator for the AlterationNotifier.
2.330 - /// It makes the notifier only empty because the copiable
2.331 - /// notifier's observers have to be registered still into that registry.
2.332 - AlterationNotifier& operator=(const AlterationNotifier&) {
2.333 - typename Container::iterator it;
2.334 - for (it = container.begin(); it != container.end(); ++it) {
2.335 - (*it)->registry = 0;
2.336 + /// \brief Destructor.
2.337 + ///
2.338 + /// Destructor of the AlterationNotifier.
2.339 + ///
2.340 + ~AlterationNotifier() {
2.341 + typename Observers::iterator it;
2.342 + for (it = observers.begin(); it != observers.end(); ++it) {
2.343 + (*it)->notifier = 0;
2.344 }
2.345 }
2.346
2.347 - /// Destructor.
2.348 -
2.349 - /// Destructor of the AlterationNotifier.
2.350 + /// \brief Sets the container.
2.351 ///
2.352 - ~AlterationNotifier() {
2.353 - typename Container::iterator it;
2.354 - for (it = container.begin(); it != container.end(); ++it) {
2.355 - (*it)->registry = 0;
2.356 - }
2.357 + /// Sets the container.
2.358 + void setContainer(const Container& _container) {
2.359 + container = &_container;
2.360 }
2.361 -
2.362 -
2.363 +
2.364 + protected:
2.365 +
2.366 + AlterationNotifier& operator=(const AlterationNotifier&);
2.367 +
2.368 + public:
2.369 +
2.370 +
2.371 +
2.372 + /// \brief First item in the container.
2.373 + ///
2.374 + /// Returns the first item in the container. It is
2.375 + /// for start the iteration on the container.
2.376 + void first(Item& item) const {
2.377 + container->first(item);
2.378 + }
2.379 +
2.380 + /// \brief Next item in the container.
2.381 + ///
2.382 + /// Returns the next item in the container. It is
2.383 + /// for iterate on the container.
2.384 + void next(Item& item) const {
2.385 + container->next(item);
2.386 + }
2.387 +
2.388 + /// \brief Returns the id of the item.
2.389 + ///
2.390 + /// Returns the id of the item provided by the container.
2.391 + int id(const Item& item) const {
2.392 + return container->id(item);
2.393 + }
2.394 +
2.395 + /// \brief Returns the maximum id of the container.
2.396 + ///
2.397 + /// Returns the maximum id of the container.
2.398 + int maxId() const {
2.399 + return container->maxId(Item());
2.400 + }
2.401 +
2.402 protected:
2.403
2.404 void attach(ObserverBase& observer) {
2.405 - container.push_back(&observer);
2.406 - observer.registry = this;
2.407 - observer.registry_index = container.size()-1;
2.408 + observers.push_back(&observer);
2.409 + observer.notifier = this;
2.410 + observer.notifier_index = observers.size() - 1;
2.411 }
2.412
2.413 - void detach(ObserverBase& base) {
2.414 - container.back()->registry_index = base.registry_index;
2.415 - container[base.registry_index] = container.back();
2.416 - container.pop_back();
2.417 - base.registry = 0;
2.418 + void detach(ObserverBase& observer) {
2.419 + observers.back()->notifier_index = observer.notifier_index;
2.420 + observers[observer.notifier_index] = observers.back();
2.421 + observers.pop_back();
2.422 + observer.notifier = 0;
2.423 }
2.424
2.425 public:
2.426
2.427 - /// \brief Notifies all the registered observers about an Item added to
2.428 + /// \brief Notifies all the registed observers about an item added to
2.429 /// the container.
2.430 ///
2.431 - /// It notifies all the registered observers about an Item added to
2.432 + /// It notifies all the registed observers about an item added to
2.433 /// the container.
2.434 ///
2.435 void add(const Item& item) {
2.436 - typename Container::iterator it;
2.437 + typename Observers::iterator it;
2.438 try {
2.439 - for (it = container.begin(); it != container.end(); ++it) {
2.440 + for (it = observers.begin(); it != observers.end(); ++it) {
2.441 (*it)->add(item);
2.442 }
2.443 } catch (...) {
2.444 - typename Container::iterator jt;
2.445 - for (jt = container.begin(); jt != it; ++it) {
2.446 + typename Observers::iterator jt;
2.447 + for (jt = observers.begin(); jt != it; ++jt) {
2.448 (*it)->erase(item);
2.449 }
2.450 throw;
2.451 }
2.452 }
2.453
2.454 - /// \brief Notifies all the registered observers about more Item added to
2.455 + /// \brief Notifies all the registed observers about more item added to
2.456 /// the container.
2.457 ///
2.458 - /// It notifies all the registered observers about more Item added to
2.459 + /// It notifies all the registed observers about more item added to
2.460 /// the container.
2.461 ///
2.462 void add(const std::vector<Item>& items) {
2.463 - typename Container::iterator it;
2.464 + typename Observers::iterator it;
2.465 try {
2.466 - for (it = container.begin(); it != container.end(); ++it) {
2.467 + for (it = observers.begin(); it != observers.end(); ++it) {
2.468 (*it)->add(items);
2.469 }
2.470 } catch (...) {
2.471 - typename Container::iterator jt;
2.472 - for (jt = container.begin(); jt != it; ++it) {
2.473 + typename Observers::iterator jt;
2.474 + for (jt = observers.begin(); jt != it; ++jt) {
2.475 (*it)->erase(items);
2.476 }
2.477 throw;
2.478 }
2.479 }
2.480
2.481 - /// \brief Notifies all the registered observers about an Item erased from
2.482 + /// \brief Notifies all the registed observers about an item erased from
2.483 /// the container.
2.484 ///
2.485 - /// It notifies all the registered observers about an Item erased from
2.486 + /// It notifies all the registed observers about an item erased from
2.487 /// the container.
2.488 ///
2.489 void erase(const Item& key) {
2.490 - typename Container::iterator it;
2.491 - for (it = container.begin(); it != container.end(); ++it) {
2.492 + typename Observers::iterator it;
2.493 + for (it = observers.begin(); it != observers.end(); ++it) {
2.494 (*it)->erase(key);
2.495 }
2.496 }
2.497
2.498 - /// \brief Notifies all the registered observers about more Item erased
2.499 + /// \brief Notifies all the registed observers about more item erased
2.500 /// from the container.
2.501 ///
2.502 - /// It notifies all the registered observers about more Item erased from
2.503 + /// It notifies all the registed observers about more item erased from
2.504 /// the container.
2.505 ///
2.506 void erase(const std::vector<Item>& items) {
2.507 - typename Container::iterator it;
2.508 - for (it = container.begin(); it != container.end(); ++it) {
2.509 + typename Observers::iterator it;
2.510 + for (it = observers.begin(); it != observers.end(); ++it) {
2.511 (*it)->erase(items);
2.512 }
2.513 }
2.514
2.515 - /// \brief Notifies all the registered observers about the container is
2.516 + /// \brief Notifies all the registed observers about the container is
2.517 /// built.
2.518 ///
2.519 - /// Notifies all the registered observers about the container is built
2.520 + /// Notifies all the registed observers about the container is built
2.521 /// from an empty container.
2.522 void build() {
2.523 - typename Container::iterator it;
2.524 + typename Observers::iterator it;
2.525 try {
2.526 - for (it = container.begin(); it != container.end(); ++it) {
2.527 + for (it = observers.begin(); it != observers.end(); ++it) {
2.528 (*it)->build();
2.529 }
2.530 } catch (...) {
2.531 - typename Container::iterator jt;
2.532 - for (jt = container.begin(); jt != it; ++it) {
2.533 + typename Observers::iterator jt;
2.534 + for (jt = observers.begin(); jt != it; ++jt) {
2.535 (*it)->clear();
2.536 }
2.537 throw;
2.538 @@ -349,23 +471,19 @@
2.539 }
2.540
2.541
2.542 - /// \brief Notifies all the registered observers about all Items are
2.543 + /// \brief Notifies all the registed observers about all items are
2.544 /// erased.
2.545 ///
2.546 - /// Notifies all the registered observers about all Items are erased
2.547 + /// Notifies all the registed observers about all items are erased
2.548 /// from the container.
2.549 void clear() {
2.550 - typename Container::iterator it;
2.551 - for (it = container.begin(); it != container.end(); ++it) {
2.552 + typename Observers::iterator it;
2.553 + for (it = observers.begin(); it != observers.end(); ++it) {
2.554 (*it)->clear();
2.555 }
2.556 }
2.557 };
2.558
2.559 -
2.560 -/// @}
2.561 -
2.562 -
2.563 }
2.564
2.565 #endif
3.1 --- a/lemon/bits/array_map.h Mon Mar 06 09:38:19 2006 +0000
3.2 +++ b/lemon/bits/array_map.h Mon Mar 06 10:28:37 2006 +0000
3.3 @@ -20,15 +20,13 @@
3.4 #define LEMON_BITS_ARRAY_MAP_H
3.5
3.6 #include <memory>
3.7 -#include <lemon/bits/map_extender.h>
3.8 +
3.9 +#include <lemon/bits/traits.h>
3.10 #include <lemon/bits/alteration_notifier.h>
3.11 -#include <lemon/concept_check.h>
3.12 -#include <lemon/concept/maps.h>
3.13
3.14 /// \ingroup graphbits
3.15 /// \file
3.16 -/// \brief Graph maps that construct and destruct
3.17 -/// their elements dynamically.
3.18 +/// \brief Graph map based on the array storage.
3.19
3.20 namespace lemon {
3.21
3.22 @@ -37,22 +35,20 @@
3.23 /// \brief Graph map based on the array storage.
3.24 ///
3.25 /// The ArrayMap template class is graph map structure what
3.26 - /// automatically indates the map when a key is added to or erased from
3.27 + /// automatically updates the map when a key is added to or erased from
3.28 /// the map. This map uses the allocators to implement
3.29 /// the container functionality.
3.30 ///
3.31 - /// The template parameter is the AlterationNotifier that the maps
3.32 - /// will belong to and the Value.
3.33 -
3.34 - template <typename _Graph,
3.35 - typename _Item,
3.36 - typename _Value>
3.37 - class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
3.38 -
3.39 - typedef _Item Item;
3.40 + /// The template parameter is the Graph the current Item type and
3.41 + /// the Value type of the map.
3.42 + template <typename _Graph, typename _Item, typename _Value>
3.43 + class ArrayMap
3.44 + : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
3.45 public:
3.46 /// The graph type of the maps.
3.47 typedef _Graph Graph;
3.48 + /// The item type of the map.
3.49 + typedef _Item Item;
3.50 /// The reference map tag.
3.51 typedef True ReferenceMapTag;
3.52
3.53 @@ -60,37 +56,33 @@
3.54 typedef _Item Key;
3.55 /// The value type of the map.
3.56 typedef _Value Value;
3.57 +
3.58 /// The const reference type of the map.
3.59 typedef const _Value& ConstReference;
3.60 /// The reference type of the map.
3.61 typedef _Value& Reference;
3.62
3.63 - typedef const Value ConstValue;
3.64 - typedef Value* Pointer;
3.65 - typedef const Value* ConstPointer;
3.66 -
3.67 - typedef AlterationNotifier<_Item> Registry;
3.68 + /// The notifier type.
3.69 + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
3.70
3.71 /// The MapBase of the Map which imlements the core regisitry function.
3.72 - typedef typename Registry::ObserverBase Parent;
3.73 + typedef typename Notifier::ObserverBase Parent;
3.74
3.75 -
3.76 -
3.77 private:
3.78 typedef std::allocator<Value> Allocator;
3.79
3.80 -
3.81 public:
3.82
3.83 /// \brief Graph initialized map constructor.
3.84 ///
3.85 /// Graph initialized map constructor.
3.86 - ArrayMap(const Graph& _g) : graph(&_g) {
3.87 + ArrayMap(const Graph& graph) {
3.88 + Parent::attach(graph.getNotifier(Item()));
3.89 + allocate_memory();
3.90 + Notifier* notifier = Parent::getNotifier();
3.91 Item it;
3.92 - attach(_g.getNotifier(Item()));
3.93 - allocate_memory();
3.94 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.95 - int id = graph->id(it);;
3.96 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.97 + int id = notifier->id(it);;
3.98 allocator.construct(&(values[id]), Value());
3.99 }
3.100 }
3.101 @@ -98,29 +90,31 @@
3.102 /// \brief Constructor to use default value to initialize the map.
3.103 ///
3.104 /// It constructs a map and initialize all of the the map.
3.105 - ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
3.106 + ArrayMap(const Graph& graph, const Value& value) {
3.107 + Parent::attach(graph.getNotifier(Item()));
3.108 + allocate_memory();
3.109 + Notifier* notifier = Parent::getNotifier();
3.110 Item it;
3.111 - attach(_g.getNotifier(_Item()));
3.112 - allocate_memory();
3.113 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.114 - int id = graph->id(it);;
3.115 - allocator.construct(&(values[id]), _v);
3.116 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.117 + int id = notifier->id(it);;
3.118 + allocator.construct(&(values[id]), value);
3.119 }
3.120 }
3.121
3.122 /// \brief Constructor to copy a map of the same map type.
3.123 ///
3.124 /// Constructor to copy a map of the same map type.
3.125 - ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
3.126 + ArrayMap(const ArrayMap& copy) : Parent() {
3.127 if (copy.attached()) {
3.128 - attach(*copy.getRegistry());
3.129 + attach(*copy.getNotifier());
3.130 }
3.131 capacity = copy.capacity;
3.132 if (capacity == 0) return;
3.133 values = allocator.allocate(capacity);
3.134 + Notifier* notifier = Parent::getNotifier();
3.135 Item it;
3.136 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.137 - int id = graph->id(it);;
3.138 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.139 + int id = notifier->id(it);;
3.140 allocator.construct(&(values[id]), copy.values[id]);
3.141 }
3.142 }
3.143 @@ -145,11 +139,6 @@
3.144 using Parent::detach;
3.145 using Parent::attached;
3.146
3.147 - const Graph* getGraph() {
3.148 - return graph;
3.149 - }
3.150 -
3.151 -
3.152 public:
3.153
3.154 /// \brief The subscript operator.
3.155 @@ -157,7 +146,7 @@
3.156 /// The subscript operator. The map can be subscripted by the
3.157 /// actual keys of the graph.
3.158 Value& operator[](const Key& key) {
3.159 - int id = graph->id(key);
3.160 + int id = Parent::getNotifier()->id(key);
3.161 return values[id];
3.162 }
3.163
3.164 @@ -166,7 +155,7 @@
3.165 /// The const subscript operator. The map can be subscripted by the
3.166 /// actual keys of the graph.
3.167 const Value& operator[](const Key& key) const {
3.168 - int id = graph->id(key);
3.169 + int id = Parent::getNotifier()->id(key);
3.170 return values[id];
3.171 }
3.172
3.173 @@ -180,10 +169,13 @@
3.174
3.175 protected:
3.176
3.177 - /// Add a new key to the map. It called by the map registry.
3.178 -
3.179 + /// \brief Adds a new key to the map.
3.180 + ///
3.181 + /// It adds a new key to the map. It called by the observer notifier
3.182 + /// and it overrides the add() member function of the observer base.
3.183 virtual void add(const Key& key) {
3.184 - int id = graph->id(key);
3.185 + Notifier* notifier = Parent::getNotifier();
3.186 + int id = notifier->id(key);
3.187 if (id >= capacity) {
3.188 int new_capacity = (capacity == 0 ? 1 : capacity);
3.189 while (new_capacity <= id) {
3.190 @@ -191,8 +183,8 @@
3.191 }
3.192 Value* new_values = allocator.allocate(new_capacity);
3.193 Item it;
3.194 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.195 - int jd = graph->id(it);;
3.196 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.197 + int jd = notifier->id(it);;
3.198 if (id != jd) {
3.199 allocator.construct(&(new_values[jd]), values[jd]);
3.200 allocator.destroy(&(values[jd]));
3.201 @@ -205,10 +197,15 @@
3.202 allocator.construct(&(values[id]), Value());
3.203 }
3.204
3.205 + /// \brief Adds more new keys to the map.
3.206 + ///
3.207 + /// It adds more new keys to the map. It called by the observer notifier
3.208 + /// and it overrides the add() member function of the observer base.
3.209 virtual void add(const std::vector<Key>& keys) {
3.210 + Notifier* notifier = Parent::getNotifier();
3.211 int max_id = -1;
3.212 for (int i = 0; i < (int)keys.size(); ++i) {
3.213 - int id = graph->id(keys[i]);
3.214 + int id = notifier->id(keys[i]);
3.215 if (id > max_id) {
3.216 max_id = id;
3.217 }
3.218 @@ -220,11 +217,11 @@
3.219 }
3.220 Value* new_values = allocator.allocate(new_capacity);
3.221 Item it;
3.222 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.223 - int id = graph->id(it);
3.224 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.225 + int id = notifier->id(it);
3.226 bool found = false;
3.227 for (int i = 0; i < (int)keys.size(); ++i) {
3.228 - int jd = graph->id(keys[i]);
3.229 + int jd = notifier->id(keys[i]);
3.230 if (id == jd) {
3.231 found = true;
3.232 break;
3.233 @@ -239,39 +236,55 @@
3.234 capacity = new_capacity;
3.235 }
3.236 for (int i = 0; i < (int)keys.size(); ++i) {
3.237 - int id = graph->id(keys[i]);
3.238 + int id = notifier->id(keys[i]);
3.239 allocator.construct(&(values[id]), Value());
3.240 }
3.241 }
3.242
3.243 - /// Erase a key from the map. It called by the map registry.
3.244 -
3.245 + /// \brief Erase a key from the map.
3.246 + ///
3.247 + /// Erase a key from the map. It called by the observer notifier
3.248 + /// and it overrides the erase() member function of the observer base.
3.249 virtual void erase(const Key& key) {
3.250 - int id = graph->id(key);
3.251 + int id = Parent::getNotifier()->id(key);
3.252 allocator.destroy(&(values[id]));
3.253 }
3.254
3.255 + /// \brief Erase more keys from the map.
3.256 + ///
3.257 + /// Erase more keys from the map. It called by the observer notifier
3.258 + /// and it overrides the erase() member function of the observer base.
3.259 virtual void erase(const std::vector<Key>& keys) {
3.260 for (int i = 0; i < (int)keys.size(); ++i) {
3.261 - int id = graph->id(keys[i]);
3.262 + int id = Parent::getNotifier()->id(keys[i]);
3.263 allocator.destroy(&(values[id]));
3.264 }
3.265 }
3.266
3.267 + /// \brief Buildes the map.
3.268 + ///
3.269 + /// It buildes the map. It called by the observer notifier
3.270 + /// and it overrides the build() member function of the observer base.
3.271 virtual void build() {
3.272 + Notifier* notifier = Parent::getNotifier();
3.273 allocate_memory();
3.274 Item it;
3.275 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.276 - int id = graph->id(it);;
3.277 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.278 + int id = notifier->id(it);;
3.279 allocator.construct(&(values[id]), Value());
3.280 }
3.281 }
3.282
3.283 + /// \brief Clear the map.
3.284 + ///
3.285 + /// It erase all items from the map. It called by the observer notifier
3.286 + /// and it overrides the clear() member function of the observer base.
3.287 virtual void clear() {
3.288 + Notifier* notifier = Parent::getNotifier();
3.289 if (capacity != 0) {
3.290 Item it;
3.291 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.292 - int id = graph->id(it);
3.293 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.294 + int id = notifier->id(it);
3.295 allocator.destroy(&(values[id]));
3.296 }
3.297 allocator.deallocate(values, capacity);
3.298 @@ -282,7 +295,7 @@
3.299 private:
3.300
3.301 void allocate_memory() {
3.302 - int max_id = graph->maxId(_Item());
3.303 + int max_id = Parent::getNotifier()->maxId();
3.304 if (max_id == -1) {
3.305 capacity = 0;
3.306 values = 0;
3.307 @@ -295,7 +308,6 @@
3.308 values = allocator.allocate(capacity);
3.309 }
3.310
3.311 - const Graph* graph;
3.312 int capacity;
3.313 Value* values;
3.314 Allocator allocator;
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/bits/base_extender.h Mon Mar 06 10:28:37 2006 +0000
4.3 @@ -0,0 +1,473 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2006
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_BITS_BASE_EXTENDER_H
4.23 +#define LEMON_BITS_BASE_EXTENDER_H
4.24 +
4.25 +#include <lemon/bits/invalid.h>
4.26 +#include <lemon/error.h>
4.27 +
4.28 +#include <lemon/bits/map_extender.h>
4.29 +#include <lemon/bits/default_map.h>
4.30 +
4.31 +#include <lemon/concept_check.h>
4.32 +#include <lemon/concept/maps.h>
4.33 +
4.34 +///\ingroup graphbits
4.35 +///\file
4.36 +///\brief Extenders for the graph types
4.37 +namespace lemon {
4.38 +
4.39 + /// \ingroup graphbits
4.40 + ///
4.41 + /// \brief BaseExtender for the UGraphs
4.42 + template <typename Base>
4.43 + class UGraphBaseExtender : public Base {
4.44 +
4.45 + public:
4.46 +
4.47 + typedef Base Parent;
4.48 + typedef typename Parent::Edge UEdge;
4.49 + typedef typename Parent::Node Node;
4.50 +
4.51 + typedef True UndirectedTag;
4.52 +
4.53 + class Edge : public UEdge {
4.54 + friend class UGraphBaseExtender;
4.55 +
4.56 + protected:
4.57 + bool forward;
4.58 +
4.59 + Edge(const UEdge &ue, bool _forward) :
4.60 + UEdge(ue), forward(_forward) {}
4.61 +
4.62 + public:
4.63 + Edge() {}
4.64 +
4.65 + /// Invalid edge constructor
4.66 + Edge(Invalid i) : UEdge(i), forward(true) {}
4.67 +
4.68 + bool operator==(const Edge &that) const {
4.69 + return forward==that.forward && UEdge(*this)==UEdge(that);
4.70 + }
4.71 + bool operator!=(const Edge &that) const {
4.72 + return forward!=that.forward || UEdge(*this)!=UEdge(that);
4.73 + }
4.74 + bool operator<(const Edge &that) const {
4.75 + return forward<that.forward ||
4.76 + (!(that.forward<forward) && UEdge(*this)<UEdge(that));
4.77 + }
4.78 + };
4.79 +
4.80 +
4.81 +
4.82 + using Parent::source;
4.83 +
4.84 + /// Source of the given Edge.
4.85 + Node source(const Edge &e) const {
4.86 + return e.forward ? Parent::source(e) : Parent::target(e);
4.87 + }
4.88 +
4.89 + using Parent::target;
4.90 +
4.91 + /// Target of the given Edge.
4.92 + Node target(const Edge &e) const {
4.93 + return e.forward ? Parent::target(e) : Parent::source(e);
4.94 + }
4.95 +
4.96 + /// \brief Directed edge from an undirected edge.
4.97 + ///
4.98 + /// Returns a directed edge corresponding to the specified UEdge.
4.99 + /// If the given bool is true the given undirected edge and the
4.100 + /// returned edge have the same source node.
4.101 + static Edge direct(const UEdge &ue, bool d) {
4.102 + return Edge(ue, d);
4.103 + }
4.104 +
4.105 + /// Returns whether the given directed edge is same orientation as the
4.106 + /// corresponding undirected edge.
4.107 + ///
4.108 + /// \todo reference to the corresponding point of the undirected graph
4.109 + /// concept. "What does the direction of an undirected edge mean?"
4.110 + static bool direction(const Edge &e) { return e.forward; }
4.111 +
4.112 +
4.113 + using Parent::first;
4.114 + using Parent::next;
4.115 +
4.116 + void first(Edge &e) const {
4.117 + Parent::first(e);
4.118 + e.forward=true;
4.119 + }
4.120 +
4.121 + void next(Edge &e) const {
4.122 + if( e.forward ) {
4.123 + e.forward = false;
4.124 + }
4.125 + else {
4.126 + Parent::next(e);
4.127 + e.forward = true;
4.128 + }
4.129 + }
4.130 +
4.131 + void firstOut(Edge &e, const Node &n) const {
4.132 + Parent::firstIn(e,n);
4.133 + if( UEdge(e) != INVALID ) {
4.134 + e.forward = false;
4.135 + }
4.136 + else {
4.137 + Parent::firstOut(e,n);
4.138 + e.forward = true;
4.139 + }
4.140 + }
4.141 + void nextOut(Edge &e) const {
4.142 + if( ! e.forward ) {
4.143 + Node n = Parent::target(e);
4.144 + Parent::nextIn(e);
4.145 + if( UEdge(e) == INVALID ) {
4.146 + Parent::firstOut(e, n);
4.147 + e.forward = true;
4.148 + }
4.149 + }
4.150 + else {
4.151 + Parent::nextOut(e);
4.152 + }
4.153 + }
4.154 +
4.155 + void firstIn(Edge &e, const Node &n) const {
4.156 + Parent::firstOut(e,n);
4.157 + if( UEdge(e) != INVALID ) {
4.158 + e.forward = false;
4.159 + }
4.160 + else {
4.161 + Parent::firstIn(e,n);
4.162 + e.forward = true;
4.163 + }
4.164 + }
4.165 + void nextIn(Edge &e) const {
4.166 + if( ! e.forward ) {
4.167 + Node n = Parent::source(e);
4.168 + Parent::nextOut(e);
4.169 + if( UEdge(e) == INVALID ) {
4.170 + Parent::firstIn(e, n);
4.171 + e.forward = true;
4.172 + }
4.173 + }
4.174 + else {
4.175 + Parent::nextIn(e);
4.176 + }
4.177 + }
4.178 +
4.179 + void firstInc(UEdge &e, bool &d, const Node &n) const {
4.180 + d = true;
4.181 + Parent::firstOut(e, n);
4.182 + if (e != INVALID) return;
4.183 + d = false;
4.184 + Parent::firstIn(e, n);
4.185 + }
4.186 +
4.187 + void nextInc(UEdge &e, bool &d) const {
4.188 + if (d) {
4.189 + Node s = Parent::source(e);
4.190 + Parent::nextOut(e);
4.191 + if (e != INVALID) return;
4.192 + d = false;
4.193 + Parent::firstIn(e, s);
4.194 + } else {
4.195 + Parent::nextIn(e);
4.196 + }
4.197 + }
4.198 +
4.199 + Node nodeFromId(int id) const {
4.200 + return Parent::nodeFromId(id);
4.201 + }
4.202 +
4.203 + Edge edgeFromId(int id) const {
4.204 + return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
4.205 + }
4.206 +
4.207 + UEdge uEdgeFromId(int id) const {
4.208 + return Parent::edgeFromId(id >> 1);
4.209 + }
4.210 +
4.211 + int id(const Node &n) const {
4.212 + return Parent::id(n);
4.213 + }
4.214 +
4.215 + int id(const UEdge &e) const {
4.216 + return Parent::id(e);
4.217 + }
4.218 +
4.219 + int id(const Edge &e) const {
4.220 + return 2 * Parent::id(e) + int(e.forward);
4.221 + }
4.222 +
4.223 + int maxNodeId() const {
4.224 + return Parent::maxNodeId();
4.225 + }
4.226 +
4.227 + int maxEdgeId() const {
4.228 + return 2 * Parent::maxEdgeId() + 1;
4.229 + }
4.230 +
4.231 + int maxUEdgeId() const {
4.232 + return Parent::maxEdgeId();
4.233 + }
4.234 +
4.235 +
4.236 + int edgeNum() const {
4.237 + return 2 * Parent::edgeNum();
4.238 + }
4.239 +
4.240 + int uEdgeNum() const {
4.241 + return Parent::edgeNum();
4.242 + }
4.243 +
4.244 + Edge findEdge(Node source, Node target, Edge prev) const {
4.245 + if (prev == INVALID) {
4.246 + UEdge edge = Parent::findEdge(source, target);
4.247 + if (edge != INVALID) return direct(edge, true);
4.248 + edge = Parent::findEdge(target, source);
4.249 + if (edge != INVALID) return direct(edge, false);
4.250 + } else if (direction(prev)) {
4.251 + UEdge edge = Parent::findEdge(source, target, prev);
4.252 + if (edge != INVALID) return direct(edge, true);
4.253 + edge = Parent::findEdge(target, source);
4.254 + if (edge != INVALID) return direct(edge, false);
4.255 + } else {
4.256 + UEdge edge = Parent::findEdge(target, source, prev);
4.257 + if (edge != INVALID) return direct(edge, false);
4.258 + }
4.259 + return INVALID;
4.260 + }
4.261 +
4.262 + UEdge findUEdge(Node source, Node target, UEdge prev) const {
4.263 + if (prev == INVALID) {
4.264 + UEdge edge = Parent::findEdge(source, target);
4.265 + if (edge != INVALID) return edge;
4.266 + edge = Parent::findEdge(target, source);
4.267 + if (edge != INVALID) return edge;
4.268 + } else if (Parent::source(prev) == source) {
4.269 + UEdge edge = Parent::findEdge(source, target, prev);
4.270 + if (edge != INVALID) return edge;
4.271 + edge = Parent::findEdge(target, source);
4.272 + if (edge != INVALID) return edge;
4.273 + } else {
4.274 + UEdge edge = Parent::findEdge(target, source, prev);
4.275 + if (edge != INVALID) return edge;
4.276 + }
4.277 + return INVALID;
4.278 + }
4.279 + };
4.280 +
4.281 +
4.282 + /// \ingroup graphbits
4.283 + ///
4.284 + /// \brief BaseExtender for the BpUGraphs
4.285 + template <typename Base>
4.286 + class BpUGraphBaseExtender : public Base {
4.287 + public:
4.288 + typedef Base Parent;
4.289 + typedef BpUGraphBaseExtender Graph;
4.290 +
4.291 + typedef typename Parent::Node Node;
4.292 + typedef typename Parent::Edge UEdge;
4.293 +
4.294 +
4.295 + using Parent::first;
4.296 + using Parent::next;
4.297 +
4.298 + using Parent::id;
4.299 +
4.300 + class ANode : public Node {
4.301 + friend class BpUGraphBaseExtender;
4.302 + public:
4.303 + ANode() {}
4.304 + ANode(const Node& node) : Node(node) {
4.305 + LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
4.306 + typename Parent::NodeSetError());
4.307 + }
4.308 + ANode(Invalid) : Node(INVALID) {}
4.309 + };
4.310 +
4.311 + void first(ANode& node) const {
4.312 + Parent::firstANode(static_cast<Node&>(node));
4.313 + }
4.314 + void next(ANode& node) const {
4.315 + Parent::nextANode(static_cast<Node&>(node));
4.316 + }
4.317 +
4.318 + int id(const ANode& node) const {
4.319 + return Parent::aNodeId(node);
4.320 + }
4.321 +
4.322 + class BNode : public Node {
4.323 + friend class BpUGraphBaseExtender;
4.324 + public:
4.325 + BNode() {}
4.326 + BNode(const Node& node) : Node(node) {
4.327 + LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
4.328 + typename Parent::NodeSetError());
4.329 + }
4.330 + BNode(Invalid) : Node(INVALID) {}
4.331 + };
4.332 +
4.333 + void first(BNode& node) const {
4.334 + Parent::firstBNode(static_cast<Node&>(node));
4.335 + }
4.336 + void next(BNode& node) const {
4.337 + Parent::nextBNode(static_cast<Node&>(node));
4.338 + }
4.339 +
4.340 + int id(const BNode& node) const {
4.341 + return Parent::aNodeId(node);
4.342 + }
4.343 +
4.344 + Node source(const UEdge& edge) const {
4.345 + return aNode(edge);
4.346 + }
4.347 + Node target(const UEdge& edge) const {
4.348 + return bNode(edge);
4.349 + }
4.350 +
4.351 + void firstInc(UEdge& edge, bool& direction, const Node& node) const {
4.352 + if (Parent::aNode(node)) {
4.353 + Parent::firstOut(edge, node);
4.354 + direction = true;
4.355 + } else {
4.356 + Parent::firstIn(edge, node);
4.357 + direction = static_cast<UEdge&>(edge) == INVALID;
4.358 + }
4.359 + }
4.360 + void nextInc(UEdge& edge, bool& direction) const {
4.361 + if (direction) {
4.362 + Parent::nextOut(edge);
4.363 + } else {
4.364 + Parent::nextIn(edge);
4.365 + if (edge == INVALID) direction = true;
4.366 + }
4.367 + }
4.368 +
4.369 + int maxUEdgeId() const {
4.370 + return Parent::maxEdgeId();
4.371 + }
4.372 +
4.373 + UEdge uEdgeFromId(int id) const {
4.374 + return Parent::edgeFromId(id);
4.375 + }
4.376 +
4.377 + class Edge : public UEdge {
4.378 + friend class BpUGraphBaseExtender;
4.379 + protected:
4.380 + bool forward;
4.381 +
4.382 + Edge(const UEdge& edge, bool _forward)
4.383 + : UEdge(edge), forward(_forward) {}
4.384 +
4.385 + public:
4.386 + Edge() {}
4.387 + Edge (Invalid) : UEdge(INVALID), forward(true) {}
4.388 + bool operator==(const Edge& i) const {
4.389 + return UEdge::operator==(i) && forward == i.forward;
4.390 + }
4.391 + bool operator!=(const Edge& i) const {
4.392 + return UEdge::operator!=(i) || forward != i.forward;
4.393 + }
4.394 + bool operator<(const Edge& i) const {
4.395 + return UEdge::operator<(i) ||
4.396 + (!(i.forward<forward) && UEdge(*this)<UEdge(i));
4.397 + }
4.398 + };
4.399 +
4.400 + void first(Edge& edge) const {
4.401 + Parent::first(static_cast<UEdge&>(edge));
4.402 + edge.forward = true;
4.403 + }
4.404 +
4.405 + void next(Edge& edge) const {
4.406 + if (!edge.forward) {
4.407 + Parent::next(static_cast<UEdge&>(edge));
4.408 + }
4.409 + edge.forward = !edge.forward;
4.410 + }
4.411 +
4.412 + void firstOut(Edge& edge, const Node& node) const {
4.413 + if (Parent::aNode(node)) {
4.414 + Parent::firstOut(edge, node);
4.415 + edge.forward = true;
4.416 + } else {
4.417 + Parent::firstIn(edge, node);
4.418 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
4.419 + }
4.420 + }
4.421 + void nextOut(Edge& edge) const {
4.422 + if (edge.forward) {
4.423 + Parent::nextOut(edge);
4.424 + } else {
4.425 + Parent::nextIn(edge);
4.426 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
4.427 + }
4.428 + }
4.429 +
4.430 + void firstIn(Edge& edge, const Node& node) const {
4.431 + if (Parent::bNode(node)) {
4.432 + Parent::firstIn(edge, node);
4.433 + edge.forward = true;
4.434 + } else {
4.435 + Parent::firstOut(edge, node);
4.436 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
4.437 + }
4.438 + }
4.439 + void nextIn(Edge& edge) const {
4.440 + if (edge.forward) {
4.441 + Parent::nextIn(edge);
4.442 + } else {
4.443 + Parent::nextOut(edge);
4.444 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
4.445 + }
4.446 + }
4.447 +
4.448 + Node source(const Edge& edge) const {
4.449 + return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
4.450 + }
4.451 + Node target(const Edge& edge) const {
4.452 + return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
4.453 + }
4.454 +
4.455 + int id(const Edge& edge) const {
4.456 + return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
4.457 + }
4.458 + Edge edgeFromId(int id) const {
4.459 + return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
4.460 + }
4.461 + int maxEdgeId() const {
4.462 + return (Parent::maxId(UEdge()) << 1) + 1;
4.463 + }
4.464 +
4.465 + bool direction(const Edge& edge) const {
4.466 + return edge.forward;
4.467 + }
4.468 +
4.469 + Edge direct(const UEdge& edge, bool direction) const {
4.470 + return Edge(edge, direction);
4.471 + }
4.472 + };
4.473 +
4.474 +}
4.475 +
4.476 +#endif
5.1 --- a/lemon/bits/default_map.h Mon Mar 06 09:38:19 2006 +0000
5.2 +++ b/lemon/bits/default_map.h Mon Mar 06 10:28:37 2006 +0000
5.3 @@ -16,18 +16,16 @@
5.4 *
5.5 */
5.6
5.7 -#ifndef LEMON_DEFAULT_MAP_H
5.8 -#define LEMON_DEFAULT_MAP_H
5.9 +#ifndef LEMON_BITS_DEFAULT_MAP_H
5.10 +#define LEMON_BITS_DEFAULT_MAP_H
5.11
5.12
5.13 #include <lemon/bits/array_map.h>
5.14 #include <lemon/bits/vector_map.h>
5.15 -#include <lemon/bits/static_map.h>
5.16
5.17 ///\ingroup graphbits
5.18 ///\file
5.19 -///\brief Graph maps that construct and destruct
5.20 -///their elements dynamically.
5.21 +///\brief Graph maps that construct and destruct their elements dynamically.
5.22
5.23 namespace lemon {
5.24
5.25 @@ -151,10 +149,7 @@
5.26 };
5.27
5.28 /// \e
5.29 - template <
5.30 - typename _Graph,
5.31 - typename _Item,
5.32 - typename _Value>
5.33 + template <typename _Graph, typename _Item, typename _Value>
5.34 class DefaultMap
5.35 : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
5.36 public:
5.37 @@ -164,8 +159,9 @@
5.38 typedef typename Parent::Graph Graph;
5.39 typedef typename Parent::Value Value;
5.40
5.41 - DefaultMap(const Graph& _g) : Parent(_g) {}
5.42 - DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {}
5.43 + DefaultMap(const Graph& graph) : Parent(graph) {}
5.44 + DefaultMap(const Graph& graph, const Value& value)
5.45 + : Parent(graph, value) {}
5.46
5.47 };
5.48
6.1 --- a/lemon/bits/edge_set_extender.h Mon Mar 06 09:38:19 2006 +0000
6.2 +++ b/lemon/bits/edge_set_extender.h Mon Mar 06 10:28:37 2006 +0000
6.3 @@ -73,7 +73,7 @@
6.4 // Alteration notifier extensions
6.5
6.6 /// The edge observer registry.
6.7 - typedef AlterationNotifier<Edge> EdgeNotifier;
6.8 + typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
6.9
6.10 protected:
6.11
6.12 @@ -219,10 +219,10 @@
6.13
6.14 template <typename _Value>
6.15 class EdgeMap
6.16 - : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
6.17 + : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
6.18 public:
6.19 typedef EdgeSetExtender Graph;
6.20 - typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
6.21 + typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
6.22
6.23 EdgeMap(const Graph& _g)
6.24 : Parent(_g) {}
6.25 @@ -264,6 +264,9 @@
6.26 Parent::erase(edge);
6.27 }
6.28
6.29 + EdgeSetExtender() {
6.30 + edge_notifier.setContainer(*this);
6.31 + }
6.32
6.33 ~EdgeSetExtender() {
6.34 edge_notifier.clear();
6.35 @@ -330,8 +333,8 @@
6.36 return Parent::direct(ue, Parent::source(ue) == s);
6.37 }
6.38
6.39 - typedef AlterationNotifier<Edge> EdgeNotifier;
6.40 - typedef AlterationNotifier<UEdge> UEdgeNotifier;
6.41 + typedef AlterationNotifier<UEdgeSetExtender, Edge> EdgeNotifier;
6.42 + typedef AlterationNotifier<UEdgeSetExtender, UEdge> UEdgeNotifier;
6.43
6.44
6.45 protected:
6.46 @@ -537,10 +540,10 @@
6.47
6.48 template <typename _Value>
6.49 class EdgeMap
6.50 - : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
6.51 + : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
6.52 public:
6.53 typedef UEdgeSetExtender Graph;
6.54 - typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
6.55 + typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
6.56
6.57 EdgeMap(const Graph& _g)
6.58 : Parent(_g) {}
6.59 @@ -566,10 +569,10 @@
6.60
6.61 template <typename _Value>
6.62 class UEdgeMap
6.63 - : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
6.64 + : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
6.65 public:
6.66 typedef UEdgeSetExtender Graph;
6.67 - typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
6.68 + typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
6.69
6.70 UEdgeMap(const Graph& _g)
6.71 : Parent(_g) {}
6.72 @@ -617,9 +620,14 @@
6.73 }
6.74
6.75
6.76 + UEdgeSetExtender() {
6.77 + edge_notifier.setContainer(*this);
6.78 + uedge_notifier.setContainer(*this);
6.79 + }
6.80 +
6.81 ~UEdgeSetExtender() {
6.82 - getNotifier(Edge()).clear();
6.83 - getNotifier(UEdge()).clear();
6.84 + uedge_notifier.clear();
6.85 + edge_notifier.clear();
6.86 }
6.87
6.88 };
7.1 --- a/lemon/bits/graph_extender.h Mon Mar 06 09:38:19 2006 +0000
7.2 +++ b/lemon/bits/graph_extender.h Mon Mar 06 10:28:37 2006 +0000
7.3 @@ -22,8 +22,12 @@
7.4 #include <lemon/bits/invalid.h>
7.5 #include <lemon/error.h>
7.6
7.7 +#include <lemon/bits/map_extender.h>
7.8 #include <lemon/bits/default_map.h>
7.9
7.10 +#include <lemon/concept_check.h>
7.11 +#include <lemon/concept/maps.h>
7.12 +
7.13 ///\ingroup graphbits
7.14 ///\file
7.15 ///\brief Extenders for the graph types
7.16 @@ -71,8 +75,8 @@
7.17
7.18 // Alterable extension
7.19
7.20 - typedef AlterationNotifier<Node> NodeNotifier;
7.21 - typedef AlterationNotifier<Edge> EdgeNotifier;
7.22 + typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
7.23 + typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
7.24
7.25
7.26 protected:
7.27 @@ -214,15 +218,15 @@
7.28
7.29 template <typename _Value>
7.30 class NodeMap
7.31 - : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
7.32 + : public MapExtender<DefaultMap<Graph, Node, _Value> > {
7.33 public:
7.34 typedef GraphExtender Graph;
7.35 - typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
7.36 + typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
7.37
7.38 - NodeMap(const Graph& _g)
7.39 - : Parent(_g) {}
7.40 - NodeMap(const Graph& _g, const _Value& _v)
7.41 - : Parent(_g, _v) {}
7.42 + NodeMap(const Graph& graph)
7.43 + : Parent(graph) {}
7.44 + NodeMap(const Graph& graph, const _Value& value)
7.45 + : Parent(graph, value) {}
7.46
7.47 NodeMap& operator=(const NodeMap& cmap) {
7.48 return operator=<NodeMap>(cmap);
7.49 @@ -238,9 +242,9 @@
7.50 template <typename CMap>
7.51 NodeMap& operator=(const CMap& cmap) {
7.52 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
7.53 - const typename Parent::Graph* graph = Parent::getGraph();
7.54 + const typename Parent::Notifier* notifier = Parent::getNotifier();
7.55 Node it;
7.56 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.57 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.58 Parent::set(it, cmap[it]);
7.59 }
7.60 return *this;
7.61 @@ -250,15 +254,15 @@
7.62
7.63 template <typename _Value>
7.64 class EdgeMap
7.65 - : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
7.66 + : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
7.67 public:
7.68 typedef GraphExtender Graph;
7.69 - typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
7.70 + typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
7.71
7.72 - EdgeMap(const Graph& _g)
7.73 - : Parent(_g) {}
7.74 - EdgeMap(const Graph& _g, const _Value& _v)
7.75 - : Parent(_g, _v) {}
7.76 + EdgeMap(const Graph& graph)
7.77 + : Parent(graph) {}
7.78 + EdgeMap(const Graph& graph, const _Value& value)
7.79 + : Parent(graph, value) {}
7.80
7.81 EdgeMap& operator=(const EdgeMap& cmap) {
7.82 return operator=<EdgeMap>(cmap);
7.83 @@ -267,9 +271,9 @@
7.84 template <typename CMap>
7.85 EdgeMap& operator=(const CMap& cmap) {
7.86 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
7.87 - const typename Parent::Graph* graph = Parent::getGraph();
7.88 + const typename Parent::Notifier* notifier = Parent::getNotifier();
7.89 Edge it;
7.90 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.91 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.92 Parent::set(it, cmap[it]);
7.93 }
7.94 return *this;
7.95 @@ -319,258 +323,20 @@
7.96 Parent::erase(edge);
7.97 }
7.98
7.99 + GraphExtender() {
7.100 + node_notifier.setContainer(*this);
7.101 + edge_notifier.setContainer(*this);
7.102 + }
7.103 +
7.104
7.105 ~GraphExtender() {
7.106 - getNotifier(Edge()).clear();
7.107 - getNotifier(Node()).clear();
7.108 + edge_notifier.clear();
7.109 + node_notifier.clear();
7.110 }
7.111 };
7.112
7.113 /// \ingroup graphbits
7.114 ///
7.115 - /// \brief BaseExtender for the UGraphs
7.116 - template <typename Base>
7.117 - class UGraphBaseExtender : public Base {
7.118 -
7.119 - public:
7.120 -
7.121 - typedef Base Parent;
7.122 - typedef typename Parent::Edge UEdge;
7.123 - typedef typename Parent::Node Node;
7.124 -
7.125 - typedef True UndirectedTag;
7.126 -
7.127 - class Edge : public UEdge {
7.128 - friend class UGraphBaseExtender;
7.129 -
7.130 - protected:
7.131 - bool forward;
7.132 -
7.133 - Edge(const UEdge &ue, bool _forward) :
7.134 - UEdge(ue), forward(_forward) {}
7.135 -
7.136 - public:
7.137 - Edge() {}
7.138 -
7.139 - /// Invalid edge constructor
7.140 - Edge(Invalid i) : UEdge(i), forward(true) {}
7.141 -
7.142 - bool operator==(const Edge &that) const {
7.143 - return forward==that.forward && UEdge(*this)==UEdge(that);
7.144 - }
7.145 - bool operator!=(const Edge &that) const {
7.146 - return forward!=that.forward || UEdge(*this)!=UEdge(that);
7.147 - }
7.148 - bool operator<(const Edge &that) const {
7.149 - return forward<that.forward ||
7.150 - (!(that.forward<forward) && UEdge(*this)<UEdge(that));
7.151 - }
7.152 - };
7.153 -
7.154 -
7.155 -
7.156 - using Parent::source;
7.157 -
7.158 - /// Source of the given Edge.
7.159 - Node source(const Edge &e) const {
7.160 - return e.forward ? Parent::source(e) : Parent::target(e);
7.161 - }
7.162 -
7.163 - using Parent::target;
7.164 -
7.165 - /// Target of the given Edge.
7.166 - Node target(const Edge &e) const {
7.167 - return e.forward ? Parent::target(e) : Parent::source(e);
7.168 - }
7.169 -
7.170 - /// \brief Directed edge from an undirected edge.
7.171 - ///
7.172 - /// Returns a directed edge corresponding to the specified UEdge.
7.173 - /// If the given bool is true the given undirected edge and the
7.174 - /// returned edge have the same source node.
7.175 - static Edge direct(const UEdge &ue, bool d) {
7.176 - return Edge(ue, d);
7.177 - }
7.178 -
7.179 - /// Returns whether the given directed edge is same orientation as the
7.180 - /// corresponding undirected edge.
7.181 - ///
7.182 - /// \todo reference to the corresponding point of the undirected graph
7.183 - /// concept. "What does the direction of an undirected edge mean?"
7.184 - static bool direction(const Edge &e) { return e.forward; }
7.185 -
7.186 -
7.187 - using Parent::first;
7.188 - using Parent::next;
7.189 -
7.190 - void first(Edge &e) const {
7.191 - Parent::first(e);
7.192 - e.forward=true;
7.193 - }
7.194 -
7.195 - void next(Edge &e) const {
7.196 - if( e.forward ) {
7.197 - e.forward = false;
7.198 - }
7.199 - else {
7.200 - Parent::next(e);
7.201 - e.forward = true;
7.202 - }
7.203 - }
7.204 -
7.205 - void firstOut(Edge &e, const Node &n) const {
7.206 - Parent::firstIn(e,n);
7.207 - if( UEdge(e) != INVALID ) {
7.208 - e.forward = false;
7.209 - }
7.210 - else {
7.211 - Parent::firstOut(e,n);
7.212 - e.forward = true;
7.213 - }
7.214 - }
7.215 - void nextOut(Edge &e) const {
7.216 - if( ! e.forward ) {
7.217 - Node n = Parent::target(e);
7.218 - Parent::nextIn(e);
7.219 - if( UEdge(e) == INVALID ) {
7.220 - Parent::firstOut(e, n);
7.221 - e.forward = true;
7.222 - }
7.223 - }
7.224 - else {
7.225 - Parent::nextOut(e);
7.226 - }
7.227 - }
7.228 -
7.229 - void firstIn(Edge &e, const Node &n) const {
7.230 - Parent::firstOut(e,n);
7.231 - if( UEdge(e) != INVALID ) {
7.232 - e.forward = false;
7.233 - }
7.234 - else {
7.235 - Parent::firstIn(e,n);
7.236 - e.forward = true;
7.237 - }
7.238 - }
7.239 - void nextIn(Edge &e) const {
7.240 - if( ! e.forward ) {
7.241 - Node n = Parent::source(e);
7.242 - Parent::nextOut(e);
7.243 - if( UEdge(e) == INVALID ) {
7.244 - Parent::firstIn(e, n);
7.245 - e.forward = true;
7.246 - }
7.247 - }
7.248 - else {
7.249 - Parent::nextIn(e);
7.250 - }
7.251 - }
7.252 -
7.253 - void firstInc(UEdge &e, bool &d, const Node &n) const {
7.254 - d = true;
7.255 - Parent::firstOut(e, n);
7.256 - if (e != INVALID) return;
7.257 - d = false;
7.258 - Parent::firstIn(e, n);
7.259 - }
7.260 -
7.261 - void nextInc(UEdge &e, bool &d) const {
7.262 - if (d) {
7.263 - Node s = Parent::source(e);
7.264 - Parent::nextOut(e);
7.265 - if (e != INVALID) return;
7.266 - d = false;
7.267 - Parent::firstIn(e, s);
7.268 - } else {
7.269 - Parent::nextIn(e);
7.270 - }
7.271 - }
7.272 -
7.273 - Node nodeFromId(int id) const {
7.274 - return Parent::nodeFromId(id);
7.275 - }
7.276 -
7.277 - Edge edgeFromId(int id) const {
7.278 - return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
7.279 - }
7.280 -
7.281 - UEdge uEdgeFromId(int id) const {
7.282 - return Parent::edgeFromId(id >> 1);
7.283 - }
7.284 -
7.285 - int id(const Node &n) const {
7.286 - return Parent::id(n);
7.287 - }
7.288 -
7.289 - int id(const UEdge &e) const {
7.290 - return Parent::id(e);
7.291 - }
7.292 -
7.293 - int id(const Edge &e) const {
7.294 - return 2 * Parent::id(e) + int(e.forward);
7.295 - }
7.296 -
7.297 - int maxNodeId() const {
7.298 - return Parent::maxNodeId();
7.299 - }
7.300 -
7.301 - int maxEdgeId() const {
7.302 - return 2 * Parent::maxEdgeId() + 1;
7.303 - }
7.304 -
7.305 - int maxUEdgeId() const {
7.306 - return Parent::maxEdgeId();
7.307 - }
7.308 -
7.309 -
7.310 - int edgeNum() const {
7.311 - return 2 * Parent::edgeNum();
7.312 - }
7.313 -
7.314 - int uEdgeNum() const {
7.315 - return Parent::edgeNum();
7.316 - }
7.317 -
7.318 - Edge findEdge(Node source, Node target, Edge prev) const {
7.319 - if (prev == INVALID) {
7.320 - UEdge edge = Parent::findEdge(source, target);
7.321 - if (edge != INVALID) return direct(edge, true);
7.322 - edge = Parent::findEdge(target, source);
7.323 - if (edge != INVALID) return direct(edge, false);
7.324 - } else if (direction(prev)) {
7.325 - UEdge edge = Parent::findEdge(source, target, prev);
7.326 - if (edge != INVALID) return direct(edge, true);
7.327 - edge = Parent::findEdge(target, source);
7.328 - if (edge != INVALID) return direct(edge, false);
7.329 - } else {
7.330 - UEdge edge = Parent::findEdge(target, source, prev);
7.331 - if (edge != INVALID) return direct(edge, false);
7.332 - }
7.333 - return INVALID;
7.334 - }
7.335 -
7.336 - UEdge findUEdge(Node source, Node target, UEdge prev) const {
7.337 - if (prev == INVALID) {
7.338 - UEdge edge = Parent::findEdge(source, target);
7.339 - if (edge != INVALID) return edge;
7.340 - edge = Parent::findEdge(target, source);
7.341 - if (edge != INVALID) return edge;
7.342 - } else if (Parent::source(prev) == source) {
7.343 - UEdge edge = Parent::findEdge(source, target, prev);
7.344 - if (edge != INVALID) return edge;
7.345 - edge = Parent::findEdge(target, source);
7.346 - if (edge != INVALID) return edge;
7.347 - } else {
7.348 - UEdge edge = Parent::findEdge(target, source, prev);
7.349 - if (edge != INVALID) return edge;
7.350 - }
7.351 - return INVALID;
7.352 - }
7.353 - };
7.354 -
7.355 -
7.356 - /// \ingroup graphbits
7.357 - ///
7.358 /// \brief Extender for the UGraphs
7.359 template <typename Base>
7.360 class UGraphExtender : public Base {
7.361 @@ -629,9 +395,9 @@
7.362
7.363 // Alterable extension
7.364
7.365 - typedef AlterationNotifier<Node> NodeNotifier;
7.366 - typedef AlterationNotifier<Edge> EdgeNotifier;
7.367 - typedef AlterationNotifier<UEdge> UEdgeNotifier;
7.368 + typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
7.369 + typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
7.370 + typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
7.371
7.372
7.373 protected:
7.374 @@ -842,15 +608,15 @@
7.375
7.376 template <typename _Value>
7.377 class NodeMap
7.378 - : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
7.379 + : public MapExtender<DefaultMap<Graph, Node, _Value> > {
7.380 public:
7.381 typedef UGraphExtender Graph;
7.382 - typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
7.383 + typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
7.384
7.385 - NodeMap(const Graph& _g)
7.386 - : Parent(_g) {}
7.387 - NodeMap(const Graph& _g, const _Value& _v)
7.388 - : Parent(_g, _v) {}
7.389 + NodeMap(const Graph& graph)
7.390 + : Parent(graph) {}
7.391 + NodeMap(const Graph& graph, const _Value& value)
7.392 + : Parent(graph, value) {}
7.393
7.394 NodeMap& operator=(const NodeMap& cmap) {
7.395 return operator=<NodeMap>(cmap);
7.396 @@ -866,9 +632,9 @@
7.397 template <typename CMap>
7.398 NodeMap& operator=(const CMap& cmap) {
7.399 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
7.400 - const typename Parent::Graph* graph = Parent::getGraph();
7.401 + const typename Parent::Notifier* notifier = Parent::getNotifier();
7.402 Node it;
7.403 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.404 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.405 Parent::set(it, cmap[it]);
7.406 }
7.407 return *this;
7.408 @@ -878,15 +644,15 @@
7.409
7.410 template <typename _Value>
7.411 class EdgeMap
7.412 - : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
7.413 + : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
7.414 public:
7.415 typedef UGraphExtender Graph;
7.416 - typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
7.417 + typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
7.418
7.419 - EdgeMap(const Graph& _g)
7.420 - : Parent(_g) {}
7.421 - EdgeMap(const Graph& _g, const _Value& _v)
7.422 - : Parent(_g, _v) {}
7.423 + EdgeMap(const Graph& graph)
7.424 + : Parent(graph) {}
7.425 + EdgeMap(const Graph& graph, const _Value& value)
7.426 + : Parent(graph, value) {}
7.427
7.428 EdgeMap& operator=(const EdgeMap& cmap) {
7.429 return operator=<EdgeMap>(cmap);
7.430 @@ -895,9 +661,9 @@
7.431 template <typename CMap>
7.432 EdgeMap& operator=(const CMap& cmap) {
7.433 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
7.434 - const typename Parent::Graph* graph = Parent::getGraph();
7.435 + const typename Parent::Notifier* notifier = Parent::getNotifier();
7.436 Edge it;
7.437 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.438 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.439 Parent::set(it, cmap[it]);
7.440 }
7.441 return *this;
7.442 @@ -907,15 +673,15 @@
7.443
7.444 template <typename _Value>
7.445 class UEdgeMap
7.446 - : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
7.447 + : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
7.448 public:
7.449 typedef UGraphExtender Graph;
7.450 - typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
7.451 + typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
7.452
7.453 - UEdgeMap(const Graph& _g)
7.454 - : Parent(_g) {}
7.455 - UEdgeMap(const Graph& _g, const _Value& _v)
7.456 - : Parent(_g, _v) {}
7.457 + UEdgeMap(const Graph& graph)
7.458 + : Parent(graph) {}
7.459 + UEdgeMap(const Graph& graph, const _Value& value)
7.460 + : Parent(graph, value) {}
7.461
7.462 UEdgeMap& operator=(const UEdgeMap& cmap) {
7.463 return operator=<UEdgeMap>(cmap);
7.464 @@ -924,9 +690,9 @@
7.465 template <typename CMap>
7.466 UEdgeMap& operator=(const CMap& cmap) {
7.467 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
7.468 - const typename Parent::Graph* graph = Parent::getGraph();
7.469 - UEdge it;
7.470 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.471 + const typename Parent::Notifier* notifier = Parent::getNotifier();
7.472 + Edge it;
7.473 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.474 Parent::set(it, cmap[it]);
7.475 }
7.476 return *this;
7.477 @@ -981,207 +747,20 @@
7.478 Parent::erase(uedge);
7.479 }
7.480
7.481 + UGraphExtender() {
7.482 + node_notifier.setContainer(*this);
7.483 + edge_notifier.setContainer(*this);
7.484 + uedge_notifier.setContainer(*this);
7.485 + }
7.486 +
7.487 ~UGraphExtender() {
7.488 - getNotifier(Edge()).clear();
7.489 - getNotifier(UEdge()).clear();
7.490 - getNotifier(Node()).clear();
7.491 - }
7.492 + uedge_notifier.clear();
7.493 + edge_notifier.clear();
7.494 + node_notifier.clear();
7.495 + }
7.496
7.497 };
7.498
7.499 -
7.500 - /// \ingroup graphbits
7.501 - ///
7.502 - /// \brief BaseExtender for the BpUGraphs
7.503 - template <typename Base>
7.504 - class BpUGraphBaseExtender : public Base {
7.505 - public:
7.506 - typedef Base Parent;
7.507 - typedef BpUGraphBaseExtender Graph;
7.508 -
7.509 - typedef typename Parent::Node Node;
7.510 - typedef typename Parent::Edge UEdge;
7.511 -
7.512 -
7.513 - using Parent::first;
7.514 - using Parent::next;
7.515 -
7.516 - using Parent::id;
7.517 -
7.518 - class ANode : public Node {
7.519 - friend class BpUGraphBaseExtender;
7.520 - public:
7.521 - ANode() {}
7.522 - ANode(const Node& node) : Node(node) {
7.523 - LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
7.524 - typename Parent::NodeSetError());
7.525 - }
7.526 - ANode(Invalid) : Node(INVALID) {}
7.527 - };
7.528 -
7.529 - void first(ANode& node) const {
7.530 - Parent::firstANode(static_cast<Node&>(node));
7.531 - }
7.532 - void next(ANode& node) const {
7.533 - Parent::nextANode(static_cast<Node&>(node));
7.534 - }
7.535 -
7.536 - int id(const ANode& node) const {
7.537 - return Parent::aNodeId(node);
7.538 - }
7.539 -
7.540 - class BNode : public Node {
7.541 - friend class BpUGraphBaseExtender;
7.542 - public:
7.543 - BNode() {}
7.544 - BNode(const Node& node) : Node(node) {
7.545 - LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
7.546 - typename Parent::NodeSetError());
7.547 - }
7.548 - BNode(Invalid) : Node(INVALID) {}
7.549 - };
7.550 -
7.551 - void first(BNode& node) const {
7.552 - Parent::firstBNode(static_cast<Node&>(node));
7.553 - }
7.554 - void next(BNode& node) const {
7.555 - Parent::nextBNode(static_cast<Node&>(node));
7.556 - }
7.557 -
7.558 - int id(const BNode& node) const {
7.559 - return Parent::aNodeId(node);
7.560 - }
7.561 -
7.562 - Node source(const UEdge& edge) const {
7.563 - return aNode(edge);
7.564 - }
7.565 - Node target(const UEdge& edge) const {
7.566 - return bNode(edge);
7.567 - }
7.568 -
7.569 - void firstInc(UEdge& edge, bool& direction, const Node& node) const {
7.570 - if (Parent::aNode(node)) {
7.571 - Parent::firstOut(edge, node);
7.572 - direction = true;
7.573 - } else {
7.574 - Parent::firstIn(edge, node);
7.575 - direction = static_cast<UEdge&>(edge) == INVALID;
7.576 - }
7.577 - }
7.578 - void nextInc(UEdge& edge, bool& direction) const {
7.579 - if (direction) {
7.580 - Parent::nextOut(edge);
7.581 - } else {
7.582 - Parent::nextIn(edge);
7.583 - if (edge == INVALID) direction = true;
7.584 - }
7.585 - }
7.586 -
7.587 - int maxUEdgeId() const {
7.588 - return Parent::maxEdgeId();
7.589 - }
7.590 -
7.591 - UEdge uEdgeFromId(int id) const {
7.592 - return Parent::edgeFromId(id);
7.593 - }
7.594 -
7.595 - class Edge : public UEdge {
7.596 - friend class BpUGraphBaseExtender;
7.597 - protected:
7.598 - bool forward;
7.599 -
7.600 - Edge(const UEdge& edge, bool _forward)
7.601 - : UEdge(edge), forward(_forward) {}
7.602 -
7.603 - public:
7.604 - Edge() {}
7.605 - Edge (Invalid) : UEdge(INVALID), forward(true) {}
7.606 - bool operator==(const Edge& i) const {
7.607 - return UEdge::operator==(i) && forward == i.forward;
7.608 - }
7.609 - bool operator!=(const Edge& i) const {
7.610 - return UEdge::operator!=(i) || forward != i.forward;
7.611 - }
7.612 - bool operator<(const Edge& i) const {
7.613 - return UEdge::operator<(i) ||
7.614 - (!(i.forward<forward) && UEdge(*this)<UEdge(i));
7.615 - }
7.616 - };
7.617 -
7.618 - void first(Edge& edge) const {
7.619 - Parent::first(static_cast<UEdge&>(edge));
7.620 - edge.forward = true;
7.621 - }
7.622 -
7.623 - void next(Edge& edge) const {
7.624 - if (!edge.forward) {
7.625 - Parent::next(static_cast<UEdge&>(edge));
7.626 - }
7.627 - edge.forward = !edge.forward;
7.628 - }
7.629 -
7.630 - void firstOut(Edge& edge, const Node& node) const {
7.631 - if (Parent::aNode(node)) {
7.632 - Parent::firstOut(edge, node);
7.633 - edge.forward = true;
7.634 - } else {
7.635 - Parent::firstIn(edge, node);
7.636 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
7.637 - }
7.638 - }
7.639 - void nextOut(Edge& edge) const {
7.640 - if (edge.forward) {
7.641 - Parent::nextOut(edge);
7.642 - } else {
7.643 - Parent::nextIn(edge);
7.644 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
7.645 - }
7.646 - }
7.647 -
7.648 - void firstIn(Edge& edge, const Node& node) const {
7.649 - if (Parent::bNode(node)) {
7.650 - Parent::firstIn(edge, node);
7.651 - edge.forward = true;
7.652 - } else {
7.653 - Parent::firstOut(edge, node);
7.654 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
7.655 - }
7.656 - }
7.657 - void nextIn(Edge& edge) const {
7.658 - if (edge.forward) {
7.659 - Parent::nextIn(edge);
7.660 - } else {
7.661 - Parent::nextOut(edge);
7.662 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
7.663 - }
7.664 - }
7.665 -
7.666 - Node source(const Edge& edge) const {
7.667 - return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
7.668 - }
7.669 - Node target(const Edge& edge) const {
7.670 - return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
7.671 - }
7.672 -
7.673 - int id(const Edge& edge) const {
7.674 - return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
7.675 - }
7.676 - Edge edgeFromId(int id) const {
7.677 - return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
7.678 - }
7.679 - int maxEdgeId() const {
7.680 - return (Parent::maxId(UEdge()) << 1) + 1;
7.681 - }
7.682 -
7.683 - bool direction(const Edge& edge) const {
7.684 - return edge.forward;
7.685 - }
7.686 -
7.687 - Edge direct(const UEdge& edge, bool direction) const {
7.688 - return Edge(edge, direction);
7.689 - }
7.690 - };
7.691 -
7.692 /// \ingroup graphbits
7.693 ///
7.694 /// \brief Extender for the BpUGraphs
7.695 @@ -1245,40 +824,40 @@
7.696 return Parent::uEdgeFromId(id);
7.697 }
7.698
7.699 - typedef AlterationNotifier<Node> NodeNotifier;
7.700 - typedef AlterationNotifier<BNode> BNodeNotifier;
7.701 - typedef AlterationNotifier<ANode> ANodeNotifier;
7.702 - typedef AlterationNotifier<Edge> EdgeNotifier;
7.703 - typedef AlterationNotifier<UEdge> UEdgeNotifier;
7.704 + typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
7.705 + typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
7.706 + typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
7.707 + typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
7.708 + typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
7.709
7.710 protected:
7.711
7.712 - mutable NodeNotifier nodeNotifier;
7.713 - mutable BNodeNotifier bNodeNotifier;
7.714 - mutable ANodeNotifier aNodeNotifier;
7.715 - mutable EdgeNotifier edgeNotifier;
7.716 - mutable UEdgeNotifier uEdgeNotifier;
7.717 + mutable ANodeNotifier anode_notifier;
7.718 + mutable BNodeNotifier bnode_notifier;
7.719 + mutable NodeNotifier node_notifier;
7.720 + mutable EdgeNotifier edge_notifier;
7.721 + mutable UEdgeNotifier uedge_notifier;
7.722
7.723 public:
7.724
7.725 NodeNotifier& getNotifier(Node) const {
7.726 - return nodeNotifier;
7.727 + return node_notifier;
7.728 + }
7.729 +
7.730 + ANodeNotifier& getNotifier(ANode) const {
7.731 + return anode_notifier;
7.732 }
7.733
7.734 BNodeNotifier& getNotifier(BNode) const {
7.735 - return bNodeNotifier;
7.736 - }
7.737 -
7.738 - ANodeNotifier& getNotifier(ANode) const {
7.739 - return aNodeNotifier;
7.740 + return bnode_notifier;
7.741 }
7.742
7.743 EdgeNotifier& getNotifier(Edge) const {
7.744 - return edgeNotifier;
7.745 + return edge_notifier;
7.746 }
7.747
7.748 UEdgeNotifier& getNotifier(UEdge) const {
7.749 - return uEdgeNotifier;
7.750 + return uedge_notifier;
7.751 }
7.752
7.753 class NodeIt : public Node {
7.754 @@ -1511,16 +1090,15 @@
7.755
7.756 template <typename _Value>
7.757 class ANodeMap
7.758 - : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
7.759 + : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
7.760 public:
7.761 typedef BpUGraphExtender Graph;
7.762 - typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
7.763 - Parent;
7.764 + typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
7.765
7.766 - ANodeMap(const Graph& _g)
7.767 - : Parent(_g) {}
7.768 - ANodeMap(const Graph& _g, const _Value& _v)
7.769 - : Parent(_g, _v) {}
7.770 + ANodeMap(const Graph& graph)
7.771 + : Parent(graph) {}
7.772 + ANodeMap(const Graph& graph, const _Value& value)
7.773 + : Parent(graph, value) {}
7.774
7.775 ANodeMap& operator=(const ANodeMap& cmap) {
7.776 return operator=<ANodeMap>(cmap);
7.777 @@ -1548,16 +1126,15 @@
7.778
7.779 template <typename _Value>
7.780 class BNodeMap
7.781 - : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
7.782 + : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
7.783 public:
7.784 typedef BpUGraphExtender Graph;
7.785 - typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
7.786 - Parent;
7.787 + typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
7.788
7.789 - BNodeMap(const Graph& _g)
7.790 - : Parent(_g) {}
7.791 - BNodeMap(const Graph& _g, const _Value& _v)
7.792 - : Parent(_g, _v) {}
7.793 + BNodeMap(const Graph& graph)
7.794 + : Parent(graph) {}
7.795 + BNodeMap(const Graph& graph, const _Value& value)
7.796 + : Parent(graph, value) {}
7.797
7.798 BNodeMap& operator=(const BNodeMap& cmap) {
7.799 return operator=<BNodeMap>(cmap);
7.800 @@ -1594,23 +1171,16 @@
7.801 typedef _Value Value;
7.802
7.803 /// The reference type of the map;
7.804 - typedef typename BNodeMap<_Value>::Reference Reference;
7.805 - /// The pointer type of the map;
7.806 - typedef typename BNodeMap<_Value>::Pointer Pointer;
7.807 -
7.808 - /// The const value type of the map.
7.809 - typedef const Value ConstValue;
7.810 + typedef typename ANodeMap<_Value>::Reference Reference;
7.811 /// The const reference type of the map;
7.812 - typedef typename BNodeMap<_Value>::ConstReference ConstReference;
7.813 - /// The pointer type of the map;
7.814 - typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
7.815 + typedef typename ANodeMap<_Value>::ConstReference ConstReference;
7.816
7.817 typedef True ReferenceMapTag;
7.818
7.819 - NodeMapBase(const Graph& _g)
7.820 - : aNodeMap(_g), bNodeMap(_g) {}
7.821 - NodeMapBase(const Graph& _g, const _Value& _v)
7.822 - : aNodeMap(_g, _v), bNodeMap(_g, _v) {}
7.823 + NodeMapBase(const Graph& graph)
7.824 + : aNodeMap(graph), bNodeMap(graph) {}
7.825 + NodeMapBase(const Graph& graph, const _Value& value)
7.826 + : aNodeMap(graph, value), bNodeMap(graph, value) {}
7.827
7.828 ConstReference operator[](const Key& node) const {
7.829 if (Parent::aNode(node)) {
7.830 @@ -1649,15 +1219,15 @@
7.831
7.832 template <typename _Value>
7.833 class NodeMap
7.834 - : public IterableMapExtender<NodeMapBase<_Value> > {
7.835 + : public MapExtender<NodeMapBase<_Value> > {
7.836 public:
7.837 typedef BpUGraphExtender Graph;
7.838 - typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
7.839 + typedef MapExtender< NodeMapBase<_Value> > Parent;
7.840
7.841 - NodeMap(const Graph& _g)
7.842 - : Parent(_g) {}
7.843 - NodeMap(const Graph& _g, const _Value& _v)
7.844 - : Parent(_g, _v) {}
7.845 + NodeMap(const Graph& graph)
7.846 + : Parent(graph) {}
7.847 + NodeMap(const Graph& graph, const _Value& value)
7.848 + : Parent(graph, value) {}
7.849
7.850 NodeMap& operator=(const NodeMap& cmap) {
7.851 return operator=<NodeMap>(cmap);
7.852 @@ -1673,9 +1243,9 @@
7.853 template <typename CMap>
7.854 NodeMap& operator=(const CMap& cmap) {
7.855 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
7.856 - const typename Parent::Graph* graph = Parent::getGraph();
7.857 - Node it;
7.858 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.859 + const typename Parent::Notifier* notifier = Parent::getNotifier();
7.860 + Edge it;
7.861 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.862 Parent::set(it, cmap[it]);
7.863 }
7.864 return *this;
7.865 @@ -1687,15 +1257,15 @@
7.866
7.867 template <typename _Value>
7.868 class EdgeMap
7.869 - : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
7.870 + : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
7.871 public:
7.872 typedef BpUGraphExtender Graph;
7.873 - typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
7.874 + typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
7.875
7.876 - EdgeMap(const Graph& _g)
7.877 - : Parent(_g) {}
7.878 - EdgeMap(const Graph& _g, const _Value& _v)
7.879 - : Parent(_g, _v) {}
7.880 + EdgeMap(const Graph& graph)
7.881 + : Parent(graph) {}
7.882 + EdgeMap(const Graph& graph, const _Value& value)
7.883 + : Parent(graph, value) {}
7.884
7.885 EdgeMap& operator=(const EdgeMap& cmap) {
7.886 return operator=<EdgeMap>(cmap);
7.887 @@ -1704,9 +1274,9 @@
7.888 template <typename CMap>
7.889 EdgeMap& operator=(const CMap& cmap) {
7.890 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
7.891 - const typename Parent::Graph* graph = Parent::getGraph();
7.892 + const typename Parent::Notifier* notifier = Parent::getNotifier();
7.893 Edge it;
7.894 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.895 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.896 Parent::set(it, cmap[it]);
7.897 }
7.898 return *this;
7.899 @@ -1715,16 +1285,15 @@
7.900
7.901 template <typename _Value>
7.902 class UEdgeMap
7.903 - : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
7.904 + : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
7.905 public:
7.906 typedef BpUGraphExtender Graph;
7.907 - typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
7.908 - Parent;
7.909 + typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
7.910
7.911 - UEdgeMap(const Graph& _g)
7.912 - : Parent(_g) {}
7.913 - UEdgeMap(const Graph& _g, const _Value& _v)
7.914 - : Parent(_g, _v) {}
7.915 + UEdgeMap(const Graph& graph)
7.916 + : Parent(graph) {}
7.917 + UEdgeMap(const Graph& graph, const _Value& value)
7.918 + : Parent(graph, value) {}
7.919
7.920 UEdgeMap& operator=(const UEdgeMap& cmap) {
7.921 return operator=<UEdgeMap>(cmap);
7.922 @@ -1733,9 +1302,9 @@
7.923 template <typename CMap>
7.924 UEdgeMap& operator=(const CMap& cmap) {
7.925 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
7.926 - const typename Parent::Graph* graph = Parent::getGraph();
7.927 - UEdge it;
7.928 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.929 + const typename Parent::Notifier* notifier = Parent::getNotifier();
7.930 + Edge it;
7.931 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.932 Parent::set(it, cmap[it]);
7.933 }
7.934 return *this;
7.935 @@ -1801,12 +1370,20 @@
7.936 }
7.937
7.938
7.939 + BpUGraphExtender() {
7.940 + anode_notifier.setContainer(*this);
7.941 + bnode_notifier.setContainer(*this);
7.942 + node_notifier.setContainer(*this);
7.943 + edge_notifier.setContainer(*this);
7.944 + uedge_notifier.setContainer(*this);
7.945 + }
7.946 +
7.947 ~BpUGraphExtender() {
7.948 - getNotifier(Edge()).clear();
7.949 - getNotifier(UEdge()).clear();
7.950 - getNotifier(Node()).clear();
7.951 - getNotifier(BNode()).clear();
7.952 - getNotifier(ANode()).clear();
7.953 + uedge_notifier.clear();
7.954 + edge_notifier.clear();
7.955 + node_notifier.clear();
7.956 + anode_notifier.clear();
7.957 + bnode_notifier.clear();
7.958 }
7.959
7.960
8.1 --- a/lemon/bits/map_extender.h Mon Mar 06 09:38:19 2006 +0000
8.2 +++ b/lemon/bits/map_extender.h Mon Mar 06 10:28:37 2006 +0000
8.3 @@ -29,12 +29,14 @@
8.4 namespace lemon {
8.5
8.6 /// \ingroup graphbits
8.7 + ///
8.8 + /// \brief Extender for maps
8.9 template <typename _Map>
8.10 - class IterableMapExtender : public _Map {
8.11 + class MapExtender : public _Map {
8.12 public:
8.13
8.14 typedef _Map Parent;
8.15 - typedef IterableMapExtender Map;
8.16 + typedef MapExtender Map;
8.17
8.18
8.19 typedef typename Parent::Graph Graph;
8.20 @@ -49,26 +51,36 @@
8.21 friend class MapIt;
8.22 friend class ConstMapIt;
8.23
8.24 - protected:
8.25 -
8.26 - using Parent::getGraph;
8.27 -
8.28 public:
8.29
8.30 - IterableMapExtender(const Graph& graph) : Parent(graph) {}
8.31 + MapExtender(const Graph& graph)
8.32 + : Parent(graph) {}
8.33
8.34 - IterableMapExtender(const Graph& graph, const Value& value)
8.35 + MapExtender(const Graph& graph, const Value& value)
8.36 : Parent(graph, value) {}
8.37
8.38
8.39 - class MapIt : public ItemSetTraits<Graph, Item>::ItemIt {
8.40 + class MapIt : public Item {
8.41 public:
8.42
8.43 - typedef typename ItemSetTraits<Graph, Item>::ItemIt Parent;
8.44 -
8.45 + typedef Item Parent;
8.46 typedef typename Map::Value Value;
8.47
8.48 - MapIt(Map& _map) : Parent(*_map.getGraph()), map(_map) {}
8.49 + MapIt() {}
8.50 +
8.51 + MapIt(Invalid i) : Parent(i) { }
8.52 +
8.53 + explicit MapIt(Map& _map) : map(_map) {
8.54 + map.getNotifier()->first(*this);
8.55 + }
8.56 +
8.57 + MapIt(const Map& _map, const Item& item)
8.58 + : Parent(item), map(_map) {}
8.59 +
8.60 + MapIt& operator++() {
8.61 + map.getNotifier()->next(*this);
8.62 + return *this;
8.63 + }
8.64
8.65 typename MapTraits<Map>::ConstReturnValue operator*() const {
8.66 return map[*this];
8.67 @@ -87,28 +99,60 @@
8.68
8.69 };
8.70
8.71 - class ConstMapIt : public ItemSetTraits<Graph, Key>::ItemIt {
8.72 + class ConstMapIt : public Item {
8.73 public:
8.74
8.75 - typedef typename ItemSetTraits<Graph, Key>::ItemIt Parent;
8.76 + typedef Item Parent;
8.77
8.78 typedef typename Map::Value Value;
8.79 +
8.80 + ConstMapIt() {}
8.81
8.82 - ConstMapIt(const Map& _map) : Parent(*_map.getGraph()), map(_map) {}
8.83 + ConstMapIt(Invalid i) : Parent(i) { }
8.84 +
8.85 + explicit ConstMapIt(Map& _map) : map(_map) {
8.86 + map.getNotifier()->first(*this);
8.87 + }
8.88 +
8.89 + ConstMapIt(const Map& _map, const Item& item)
8.90 + : Parent(item), map(_map) {}
8.91 +
8.92 + ConstMapIt& operator++() {
8.93 + map.getNotifier()->next(*this);
8.94 + return *this;
8.95 + }
8.96
8.97 typename MapTraits<Map>::ConstReturnValue operator*() const {
8.98 return map[*this];
8.99 }
8.100 +
8.101 protected:
8.102 const Map& map;
8.103 };
8.104
8.105 - class ItemIt : public ItemSetTraits<Graph, Key>::ItemIt {
8.106 + class ItemIt : Item {
8.107 public:
8.108
8.109 - typedef typename ItemSetTraits<Graph, Key>::ItemIt Parent;
8.110 + typedef Item Parent;
8.111 +
8.112 + ItemIt() {}
8.113
8.114 - ItemIt(Map& _map) : Parent(*_map.getGraph()) {}
8.115 + ItemIt(Invalid i) : Parent(i) { }
8.116 +
8.117 + explicit ItemIt(Map& _map) : map(_map) {
8.118 + map->getNotifier()->first(*this);
8.119 + }
8.120 +
8.121 + ItemIt(const Map& _map, const Item& item)
8.122 + : Parent(item), map(_map) {}
8.123 +
8.124 + ItemIt& operator++() {
8.125 + map.getNotifier()->next(*this);
8.126 + return *this;
8.127 + }
8.128 +
8.129 + protected:
8.130 + const Map& map;
8.131
8.132 };
8.133 };
9.1 --- a/lemon/bits/static_map.h Mon Mar 06 09:38:19 2006 +0000
9.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
9.3 @@ -1,229 +0,0 @@
9.4 -/* -*- C++ -*-
9.5 - *
9.6 - * This file is a part of LEMON, a generic C++ optimization library
9.7 - *
9.8 - * Copyright (C) 2003-2006
9.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
9.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
9.11 - *
9.12 - * Permission to use, modify and distribute this software is granted
9.13 - * provided that this copyright notice appears in all copies. For
9.14 - * precise terms see the accompanying LICENSE file.
9.15 - *
9.16 - * This software is provided "AS IS" with no warranty of any kind,
9.17 - * express or implied, and with no claim as to its suitability for any
9.18 - * purpose.
9.19 - *
9.20 - */
9.21 -
9.22 -#ifndef LEMON_STATIC_MAP_H
9.23 -#define LEMON_STATIC_MAP_H
9.24 -
9.25 -#include <algorithm>
9.26 -#include <iostream>
9.27 -
9.28 -#include <lemon/bits/utility.h>
9.29 -#include <lemon/bits/map_extender.h>
9.30 -#include <lemon/bits/alteration_notifier.h>
9.31 -#include <lemon/error.h>
9.32 -#include <lemon/concept_check.h>
9.33 -#include <lemon/concept/maps.h>
9.34 -
9.35 -/// \ingroup graphmaps
9.36 -///
9.37 -///\file
9.38 -///\brief Static sized graph maps.
9.39 -
9.40 -namespace lemon {
9.41 -
9.42 - /// \ingroup graphmaps
9.43 - ///
9.44 - /// \brief Graph map with static sized storage.
9.45 - ///
9.46 - /// The StaticMap template class is graph map structure what
9.47 - /// does not indate automatically the map when a key is added to or
9.48 - /// erased from the map rather it throws an exception. This map factory
9.49 - /// uses the allocators to implement the container functionality.
9.50 - ///
9.51 - /// \param Registry The AlterationNotifier that will notify this map.
9.52 - /// \param Item The item type of the graph items.
9.53 - /// \param Value The value type of the map.
9.54 - ///
9.55 - /// \author Balazs Dezso
9.56 -
9.57 -
9.58 - template <typename _Graph, typename _Item, typename _Value>
9.59 - class StaticMap : public AlterationNotifier<_Item>::ObserverBase {
9.60 - public:
9.61 -
9.62 - /// \brief Exception class for unsupported exceptions.
9.63 - class UnsupportedOperation : public lemon::LogicError {
9.64 - public:
9.65 - virtual const char* exceptionName() const {
9.66 - return "lemon::StaticMap::UnsupportedOperation";
9.67 - }
9.68 - };
9.69 -
9.70 - private:
9.71 -
9.72 - typedef std::vector<_Value> Container;
9.73 -
9.74 - public:
9.75 -
9.76 - /// The graph type of the map.
9.77 - typedef _Graph Graph;
9.78 - /// The reference map tag.
9.79 - typedef True ReferenceMapTag;
9.80 -
9.81 - /// The key type of the map.
9.82 - typedef _Item Key;
9.83 - /// The value type of the map.
9.84 - typedef _Value Value;
9.85 - /// The const reference type of the map.
9.86 - typedef typename Container::const_reference ConstReference;
9.87 - /// The reference type of the map.
9.88 - typedef typename Container::reference Reference;
9.89 -
9.90 - typedef const Value ConstValue;
9.91 - typedef Value* Pointer;
9.92 - typedef const Value* ConstPointer;
9.93 -
9.94 - typedef AlterationNotifier<_Item> Registry;
9.95 -
9.96 - /// The map type.
9.97 - typedef StaticMap Map;
9.98 - /// The base class of the map.
9.99 - typedef typename Registry::ObserverBase Parent;
9.100 -
9.101 - /// \brief Constructor to attach the new map into the registry.
9.102 - ///
9.103 - /// It constructs a map and attachs it into the registry.
9.104 - /// It adds all the items of the graph to the map.
9.105 - StaticMap(const Graph& _g) : graph(&_g) {
9.106 - attach(_g.getNotifier(_Item()));
9.107 - build();
9.108 - }
9.109 -
9.110 - /// \brief Constructor uses given value to initialize the map.
9.111 - ///
9.112 - /// It constructs a map uses a given value to initialize the map.
9.113 - /// It adds all the items of the graph to the map.
9.114 - StaticMap(const Graph& _g, const Value& _v) : graph(&_g) {
9.115 - attach(_g.getNotifier(_Item()));
9.116 - unsigned size = graph->maxId(_Item()) + 1;
9.117 - container.reserve(size);
9.118 - container.resize(size, _v);
9.119 - }
9.120 -
9.121 - /// \brief Copy constructor
9.122 - ///
9.123 - /// Copy constructor.
9.124 - StaticMap(const StaticMap& _copy) : Parent(), graph(_copy.getGraph()) {
9.125 - if (_copy.attached()) {
9.126 - attach(*_copy.getRegistry());
9.127 - container = _copy.container;
9.128 - }
9.129 - }
9.130 -
9.131 - /// \brief Destrcutor
9.132 - ///
9.133 - /// Destructor.
9.134 - virtual ~StaticMap() {
9.135 - clear();
9.136 - if (attached()) {
9.137 - detach();
9.138 - }
9.139 - }
9.140 -
9.141 -
9.142 - private:
9.143 -
9.144 - StaticMap& operator=(const StaticMap&);
9.145 -
9.146 - protected:
9.147 -
9.148 - using Parent::attach;
9.149 - using Parent::detach;
9.150 - using Parent::attached;
9.151 -
9.152 - const Graph* getGraph() const {
9.153 - return graph;
9.154 - }
9.155 -
9.156 - public:
9.157 -
9.158 - /// \brief The subcript operator.
9.159 - ///
9.160 - /// The subscript operator. The map can be subscripted by the
9.161 - /// actual items of the graph.
9.162 -
9.163 - Reference operator[](const Key& key) {
9.164 - return container[graph->id(key)];
9.165 - }
9.166 -
9.167 - /// \brief The const subcript operator.
9.168 - ///
9.169 - /// The const subscript operator. The map can be subscripted by the
9.170 - /// actual items of the graph.
9.171 -
9.172 - ConstReference operator[](const Key& key) const {
9.173 - return container[graph->id(key)];
9.174 - }
9.175 -
9.176 -
9.177 - /// \brief The setter function of the map.
9.178 - ///
9.179 - /// It the same as operator[](key) = value expression.
9.180 - ///
9.181 - void set(const Key& key, const Value& value) {
9.182 - (*this)[key] = value;
9.183 - }
9.184 -
9.185 - protected:
9.186 -
9.187 - /// \brief Adds a new key to the map.
9.188 - ///
9.189 - /// It adds a new key to the map. It called by the observer registry
9.190 - /// and it overrides the add() member function of the observer base.
9.191 -
9.192 - void add(const Key&) {
9.193 - throw UnsupportedOperation();
9.194 - }
9.195 -
9.196 - /// \brief Erases a key from the map.
9.197 - ///
9.198 - /// Erase a key from the map. It called by the observer registry
9.199 - /// and it overrides the erase() member function of the observer base.
9.200 - void erase(const Key&) {
9.201 - throw UnsupportedOperation();
9.202 - }
9.203 -
9.204 - /// Buildes the map.
9.205 -
9.206 - /// It buildes the map. It called by the observer registry
9.207 - /// and it overrides the build() member function of the observer base.
9.208 -
9.209 - void build() {
9.210 - int size = graph->maxId(_Item()) + 1;
9.211 - container.reserve(size);
9.212 - container.resize(size);
9.213 - }
9.214 -
9.215 - /// Clear the map.
9.216 -
9.217 - /// It erase all items from the map. It called by the observer registry
9.218 - /// and it overrides the clear() member function of the observer base.
9.219 - void clear() {
9.220 - container.clear();
9.221 - }
9.222 -
9.223 - private:
9.224 -
9.225 - Container container;
9.226 - const Graph *graph;
9.227 -
9.228 - };
9.229 -
9.230 -}
9.231 -
9.232 -#endif
10.1 --- a/lemon/bits/vector_map.h Mon Mar 06 09:38:19 2006 +0000
10.2 +++ b/lemon/bits/vector_map.h Mon Mar 06 10:28:37 2006 +0000
10.3 @@ -16,23 +16,21 @@
10.4 *
10.5 */
10.6
10.7 -#ifndef LEMON_VECTOR_MAP_H
10.8 -#define LEMON_VECTOR_MAP_H
10.9 +#ifndef LEMON_BITS_VECTOR_MAP_H
10.10 +#define LEMON_BITS_VECTOR_MAP_H
10.11
10.12 #include <vector>
10.13 #include <algorithm>
10.14
10.15 +#include <lemon/bits/traits.h>
10.16 #include <lemon/bits/utility.h>
10.17 -#include <lemon/bits/map_extender.h>
10.18 +
10.19 #include <lemon/bits/alteration_notifier.h>
10.20 -#include <lemon/concept_check.h>
10.21 -#include <lemon/concept/maps.h>
10.22
10.23 -/// \ingroup graphbits
10.24 +///\ingroup graphbits
10.25 ///
10.26 ///\file
10.27 ///\brief Vector based graph maps.
10.28 -
10.29 namespace lemon {
10.30
10.31 /// \ingroup graphbits
10.32 @@ -40,23 +38,19 @@
10.33 /// \brief Graph map based on the std::vector storage.
10.34 ///
10.35 /// The VectorMap template class is graph map structure what
10.36 - /// automatically indates the map when a key is added to or erased from
10.37 + /// automatically updates the map when a key is added to or erased from
10.38 /// the map. This map factory uses the allocators to implement
10.39 /// the container functionality. This map factory
10.40 /// uses the std::vector to implement the container function.
10.41 ///
10.42 - /// \param Registry The AlterationNotifier that will notify this map.
10.43 + /// \param Notifier The AlterationNotifier that will notify this map.
10.44 /// \param Item The item type of the graph items.
10.45 /// \param Value The value type of the map.
10.46 ///
10.47 - /// \author Balazs Dezso
10.48 -
10.49 - template <
10.50 - typename _Graph,
10.51 - typename _Item,
10.52 - typename _Value
10.53 - >
10.54 - class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
10.55 + /// \author Balazs Dezso
10.56 + template <typename _Graph, typename _Item, typename _Value>
10.57 + class VectorMap
10.58 + : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
10.59 private:
10.60
10.61 /// The container type of the map.
10.62 @@ -66,6 +60,8 @@
10.63
10.64 /// The graph type of the map.
10.65 typedef _Graph Graph;
10.66 + /// The item type of the map.
10.67 + typedef _Item Item;
10.68 /// The reference map tag.
10.69 typedef True ReferenceMapTag;
10.70
10.71 @@ -74,79 +70,52 @@
10.72 /// The value type of the map.
10.73 typedef _Value Value;
10.74
10.75 - typedef AlterationNotifier<_Item> Registry;
10.76 + /// The notifier type.
10.77 + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
10.78
10.79 /// The map type.
10.80 typedef VectorMap Map;
10.81 /// The base class of the map.
10.82 - typedef typename Registry::ObserverBase Parent;
10.83 + typedef typename Notifier::ObserverBase Parent;
10.84
10.85 /// The reference type of the map;
10.86 typedef typename Container::reference Reference;
10.87 - /// The pointer type of the map;
10.88 - typedef typename Container::pointer Pointer;
10.89 -
10.90 - /// The const value type of the map.
10.91 - typedef const Value ConstValue;
10.92 /// The const reference type of the map;
10.93 typedef typename Container::const_reference ConstReference;
10.94 - /// The pointer type of the map;
10.95 - typedef typename Container::const_pointer ConstPointer;
10.96
10.97
10.98 - /// \brief Constructor to attach the new map into the registry.
10.99 + /// \brief Constructor to attach the new map into the notifier.
10.100 ///
10.101 - /// It constructs a map and attachs it into the registry.
10.102 + /// It constructs a map and attachs it into the notifier.
10.103 /// It adds all the items of the graph to the map.
10.104 - VectorMap(const Graph& _g) : graph(&_g) {
10.105 - attach(_g.getNotifier(_Item()));
10.106 - build();
10.107 + VectorMap(const Graph& graph) {
10.108 + Parent::attach(graph.getNotifier(Item()));
10.109 + container.resize(Parent::getNotifier()->maxId() + 1);
10.110 }
10.111
10.112 /// \brief Constructor uses given value to initialize the map.
10.113 ///
10.114 /// It constructs a map uses a given value to initialize the map.
10.115 /// It adds all the items of the graph to the map.
10.116 - VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
10.117 - attach(_g.getNotifier(_Item()));
10.118 - container.resize(graph->maxId(_Item()) + 1, _v);
10.119 + VectorMap(const Graph& graph, const Value& value) {
10.120 + Parent::attach(graph.getNotifier(Item()));
10.121 + container.resize(Parent::getNotifier()->maxId() + 1, value);
10.122 }
10.123
10.124 /// \brief Copy constructor
10.125 ///
10.126 /// Copy constructor.
10.127 - VectorMap(const VectorMap& _copy)
10.128 - : Parent(), graph(_copy.getGraph()) {
10.129 + VectorMap(const VectorMap& _copy) : Parent() {
10.130 if (_copy.attached()) {
10.131 - attach(*_copy.getRegistry());
10.132 + Parent::attach(*_copy.getNotifier());
10.133 container = _copy.container;
10.134 }
10.135 }
10.136
10.137 - /// \brief Destrcutor
10.138 - ///
10.139 - /// Destructor.
10.140 - virtual ~VectorMap() {
10.141 - if (attached()) {
10.142 - detach();
10.143 - }
10.144 - }
10.145 -
10.146 -
10.147 private:
10.148
10.149 VectorMap& operator=(const VectorMap&);
10.150
10.151 - protected:
10.152 -
10.153 - using Parent::attach;
10.154 - using Parent::detach;
10.155 - using Parent::attached;
10.156 -
10.157 - const Graph* getGraph() const {
10.158 - return graph;
10.159 - }
10.160 -
10.161 public:
10.162
10.163 /// \brief The subcript operator.
10.164 @@ -154,7 +123,7 @@
10.165 /// The subscript operator. The map can be subscripted by the
10.166 /// actual items of the graph.
10.167 Reference operator[](const Key& key) {
10.168 - return container[graph->id(key)];
10.169 + return container[Parent::getNotifier()->id(key)];
10.170 }
10.171
10.172 /// \brief The const subcript operator.
10.173 @@ -162,7 +131,7 @@
10.174 /// The const subscript operator. The map can be subscripted by the
10.175 /// actual items of the graph.
10.176 ConstReference operator[](const Key& key) const {
10.177 - return container[graph->id(key)];
10.178 + return container[Parent::getNotifier()->id(key)];
10.179 }
10.180
10.181
10.182 @@ -177,10 +146,10 @@
10.183
10.184 /// \brief Adds a new key to the map.
10.185 ///
10.186 - /// It adds a new key to the map. It called by the observer registry
10.187 + /// It adds a new key to the map. It called by the observer notifier
10.188 /// and it overrides the add() member function of the observer base.
10.189 virtual void add(const Key& key) {
10.190 - int id = graph->id(key);
10.191 + int id = Parent::getNotifier()->id(key);
10.192 if (id >= (int)container.size()) {
10.193 container.resize(id + 1);
10.194 }
10.195 @@ -188,37 +157,50 @@
10.196
10.197 /// \brief Adds more new keys to the map.
10.198 ///
10.199 - /// It adds more new keys to the map. It called by the observer registry
10.200 + /// It adds more new keys to the map. It called by the observer notifier
10.201 /// and it overrides the add() member function of the observer base.
10.202 virtual void add(const std::vector<Key>& keys) {
10.203 + int max = container.size() - 1;
10.204 for (int i = 0; i < (int)keys.size(); ++i) {
10.205 - add(keys[i]);
10.206 + int id = Parent::getNotifier()->id(keys[i]);
10.207 + if (id >= max) {
10.208 + max = id;
10.209 + }
10.210 }
10.211 + container.resize(max + 1);
10.212 }
10.213
10.214 /// \brief Erase a key from the map.
10.215 ///
10.216 - /// Erase a key from the map. It called by the observer registry
10.217 + /// Erase a key from the map. It called by the observer notifier
10.218 /// and it overrides the erase() member function of the observer base.
10.219 - virtual void erase(const Key&) {}
10.220 + virtual void erase(const Key& key) {
10.221 + container[Parent::getNotifier()->id(key)] = Value();
10.222 + }
10.223
10.224 /// \brief Erase more keys from the map.
10.225 ///
10.226 - /// Erase more keys from the map. It called by the observer registry
10.227 + /// Erase more keys from the map. It called by the observer notifier
10.228 /// and it overrides the erase() member function of the observer base.
10.229 - virtual void erase(const std::vector<Key>&) {}
10.230 + virtual void erase(const std::vector<Key>& keys) {
10.231 + for (int i = 0; i < (int)keys.size(); ++i) {
10.232 + container[Parent::getNotifier()->id(keys[i])] = Value();
10.233 + }
10.234 + }
10.235
10.236 /// \brief Buildes the map.
10.237 ///
10.238 - /// It buildes the map. It called by the observer registry
10.239 + /// It buildes the map. It called by the observer notifier
10.240 /// and it overrides the build() member function of the observer base.
10.241 virtual void build() {
10.242 - container.resize(graph->maxId(_Item()) + 1);
10.243 + int size = Parent::getNotifier()->maxId() + 1;
10.244 + container.reserve(size);
10.245 + container.resize(size);
10.246 }
10.247
10.248 /// \brief Clear the map.
10.249 ///
10.250 - /// It erase all items from the map. It called by the observer registry
10.251 + /// It erase all items from the map. It called by the observer notifier
10.252 /// and it overrides the clear() member function of the observer base.
10.253 virtual void clear() {
10.254 container.clear();
10.255 @@ -227,7 +209,6 @@
10.256 private:
10.257
10.258 Container container;
10.259 - const Graph *graph;
10.260
10.261 };
10.262
11.1 --- a/lemon/concept/graph_component.h Mon Mar 06 09:38:19 2006 +0000
11.2 +++ b/lemon/concept/graph_component.h Mon Mar 06 10:28:37 2006 +0000
11.3 @@ -737,13 +737,15 @@
11.4 /// This is an observer-notifier pattern. More Obsevers can
11.5 /// be registered into the notifier and whenever an alteration
11.6 /// occured in the graph all the observers will notified about it.
11.7 - class AlterableGraphComponent : virtual public BaseGraphComponent {
11.8 + class AlterableGraphComponent : virtual public BaseIterableGraphComponent {
11.9 public:
11.10
11.11 /// The edge observer registry.
11.12 - typedef AlterationNotifier<Edge> EdgeNotifier;
11.13 + typedef AlterationNotifier<AlterableGraphComponent, Edge>
11.14 + EdgeNotifier;
11.15 /// The node observer registry.
11.16 - typedef AlterationNotifier<Node> NodeNotifier;
11.17 + typedef AlterationNotifier<AlterableGraphComponent, Node>
11.18 + NodeNotifier;
11.19
11.20 /// \brief Gives back the edge alteration notifier.
11.21 ///
12.1 --- a/lemon/dag_shortest_path.h Mon Mar 06 09:38:19 2006 +0000
12.2 +++ b/lemon/dag_shortest_path.h Mon Mar 06 10:28:37 2006 +0000
12.3 @@ -329,7 +329,7 @@
12.4 /// \brief The operation traits.
12.5 typedef typename _Traits::OperationTraits OperationTraits;
12.6 /// \brief The Node weight map.
12.7 - typedef typename Graph::NodeMap<Value> WeightMap;
12.8 + typedef typename Graph::template NodeMap<Value> WeightMap;
12.9 private:
12.10 /// Pointer to the underlying graph
12.11 const Graph *graph;
13.1 --- a/lemon/edge_set.h Mon Mar 06 09:38:19 2006 +0000
13.2 +++ b/lemon/edge_set.h Mon Mar 06 10:28:37 2006 +0000
13.3 @@ -571,7 +571,11 @@
13.4
13.5 typedef typename Parent::NodesImplBase NodesImplBase;
13.6
13.7 - void eraseNode(const Node&) {
13.8 + void eraseNode(const Node& node) {
13.9 + if (Parent::InEdgeIt(*this, node) == INVALID &&
13.10 + Parent::OutEdgeIt(*this, node) == INVALID) {
13.11 + return;
13.12 + }
13.13 throw UnsupportedOperation();
13.14 }
13.15
13.16 @@ -662,7 +666,10 @@
13.17
13.18 typedef typename Parent::NodesImplBase NodesImplBase;
13.19
13.20 - void eraseNode(const Node&) {
13.21 + void eraseNode(const Node& node) {
13.22 + if (Parent::IncEdgeIt(*this, node) == INVALID) {
13.23 + return;
13.24 + }
13.25 throw UnsupportedOperation();
13.26 }
13.27
14.1 --- a/lemon/full_graph.h Mon Mar 06 09:38:19 2006 +0000
14.2 +++ b/lemon/full_graph.h Mon Mar 06 10:28:37 2006 +0000
14.3 @@ -21,10 +21,9 @@
14.4
14.5 #include <cmath>
14.6
14.7 -
14.8 +#include <lemon/bits/base_extender.h>
14.9 #include <lemon/bits/graph_extender.h>
14.10
14.11 -
14.12 #include <lemon/bits/invalid.h>
14.13 #include <lemon/bits/utility.h>
14.14
15.1 --- a/lemon/graph_adaptor.h Mon Mar 06 09:38:19 2006 +0000
15.2 +++ b/lemon/graph_adaptor.h Mon Mar 06 10:28:37 2006 +0000
15.3 @@ -30,6 +30,7 @@
15.4 #include <lemon/bits/invalid.h>
15.5 #include <lemon/maps.h>
15.6
15.7 +#include <lemon/bits/base_extender.h>
15.8 #include <lemon/bits/graph_adaptor_extender.h>
15.9 #include <lemon/bits/graph_extender.h>
15.10
15.11 @@ -937,7 +938,7 @@
15.12 protected:
15.13
15.14 UndirGraphAdaptorBase()
15.15 - : Parent(), edge_notifier(), edge_notifier_proxy(edge_notifier) {}
15.16 + : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}
15.17
15.18 void setGraph(_Graph& graph) {
15.19 Parent::setGraph(graph);
15.20 @@ -947,7 +948,11 @@
15.21 public:
15.22
15.23 ~UndirGraphAdaptorBase() {
15.24 - getNotifier(Edge()).clear();
15.25 + edge_notifier.clear();
15.26 + }
15.27 +
15.28 + int maxId(typename Parent::Edge) const {
15.29 + return Parent::maxEdgeId();
15.30 }
15.31
15.32
15.33 @@ -958,7 +963,7 @@
15.34
15.35 using Parent::getNotifier;
15.36
15.37 - typedef AlterationNotifier<Edge> EdgeNotifier;
15.38 + typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
15.39 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
15.40
15.41 protected:
16.1 --- a/lemon/graph_utils.h Mon Mar 06 09:38:19 2006 +0000
16.2 +++ b/lemon/graph_utils.h Mon Mar 06 10:28:37 2006 +0000
16.3 @@ -1189,8 +1189,8 @@
16.4 virtual void build() {
16.5 Map::build();
16.6 Item it;
16.7 - const typename Map::Graph* graph = Map::getGraph();
16.8 - for (graph->first(it); it != INVALID; graph->next(it)) {
16.9 + const typename Map::Notifier* notifier = Map::getNotifier();
16.10 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
16.11 Map::set(it, invMap.size());
16.12 invMap.push_back(it);
16.13 }
16.14 @@ -1497,7 +1497,8 @@
16.15
16.16 template <typename _Graph>
16.17 class InDegMap
16.18 - : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
16.19 + : protected ItemSetTraits<_Graph, typename _Graph::Edge>
16.20 + ::ItemNotifier::ObserverBase {
16.21
16.22 public:
16.23
16.24 @@ -1505,6 +1506,9 @@
16.25 typedef int Value;
16.26 typedef typename Graph::Node Key;
16.27
16.28 + typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
16.29 + ::ItemNotifier::ObserverBase Parent;
16.30 +
16.31 private:
16.32
16.33 class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
16.34 @@ -1533,18 +1537,12 @@
16.35 ///
16.36 /// Constructor for creating in-degree map.
16.37 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
16.38 - AlterationNotifier<typename _Graph::Edge>
16.39 - ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
16.40 + Parent::attach(graph.getNotifier(typename _Graph::Edge()));
16.41
16.42 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
16.43 deg[it] = countInEdges(graph, it);
16.44 }
16.45 }
16.46 -
16.47 - virtual ~InDegMap() {
16.48 - AlterationNotifier<typename _Graph::Edge>::
16.49 - ObserverBase::detach();
16.50 - }
16.51
16.52 /// Gives back the in-degree of a Node.
16.53 int operator[](const Key& key) const {
16.54 @@ -1611,9 +1609,13 @@
16.55
16.56 template <typename _Graph>
16.57 class OutDegMap
16.58 - : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
16.59 + : protected ItemSetTraits<_Graph, typename _Graph::Edge>
16.60 + ::ItemNotifier::ObserverBase {
16.61
16.62 public:
16.63 +
16.64 + typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
16.65 + ::ItemNotifier::ObserverBase Parent;
16.66
16.67 typedef _Graph Graph;
16.68 typedef int Value;
16.69 @@ -1646,19 +1648,13 @@
16.70 ///
16.71 /// Constructor for creating out-degree map.
16.72 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
16.73 - AlterationNotifier<typename _Graph::Edge>
16.74 - ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
16.75 + Parent::attach(graph.getNotifier(typename _Graph::Edge()));
16.76
16.77 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
16.78 deg[it] = countOutEdges(graph, it);
16.79 }
16.80 }
16.81
16.82 - virtual ~OutDegMap() {
16.83 - AlterationNotifier<typename _Graph::Edge>::
16.84 - ObserverBase::detach();
16.85 - }
16.86 -
16.87 /// Gives back the out-degree of a Node.
16.88 int operator[](const Key& key) const {
16.89 return deg[key];
17.1 --- a/lemon/grid_ugraph.h Mon Mar 06 09:38:19 2006 +0000
17.2 +++ b/lemon/grid_ugraph.h Mon Mar 06 10:28:37 2006 +0000
17.3 @@ -23,6 +23,7 @@
17.4 #include <lemon/bits/invalid.h>
17.5 #include <lemon/bits/utility.h>
17.6
17.7 +#include <lemon/bits/base_extender.h>
17.8 #include <lemon/bits/graph_extender.h>
17.9
17.10 #include <lemon/xy.h>
18.1 --- a/lemon/list_graph.h Mon Mar 06 09:38:19 2006 +0000
18.2 +++ b/lemon/list_graph.h Mon Mar 06 10:28:37 2006 +0000
18.3 @@ -23,6 +23,7 @@
18.4 ///\file
18.5 ///\brief ListGraph, ListUGraph classes.
18.6
18.7 +#include <lemon/bits/base_extender.h>
18.8 #include <lemon/bits/graph_extender.h>
18.9
18.10 #include <lemon/error.h>
18.11 @@ -320,9 +321,11 @@
18.12 ///it also provides several additional useful extra functionalities.
18.13 ///\sa concept::ErasableGraph.
18.14
18.15 - class ListGraph : public ExtendedListGraphBase
18.16 - {
18.17 + class ListGraph : public ExtendedListGraphBase {
18.18 public:
18.19 +
18.20 + typedef ExtendedListGraphBase Parent;
18.21 +
18.22 /// Changes the target of \c e to \c n
18.23
18.24 /// Changes the target of \c e to \c n
18.25 @@ -446,8 +449,8 @@
18.26 ///
18.27 ///\warning Edge and node deletions cannot be restored.
18.28 ///\warning Snapshots cannot be nested.
18.29 - class Snapshot : protected AlterationNotifier<Node>::ObserverBase,
18.30 - protected AlterationNotifier<Edge>::ObserverBase
18.31 + class Snapshot : protected Parent::NodeNotifier::ObserverBase,
18.32 + protected Parent::EdgeNotifier::ObserverBase
18.33 {
18.34 public:
18.35
18.36 @@ -459,7 +462,7 @@
18.37 };
18.38
18.39
18.40 - protected:
18.41 + protected:
18.42
18.43 ListGraph *g;
18.44 std::list<Node> added_nodes;
18.45 @@ -490,17 +493,13 @@
18.46
18.47 void regist(ListGraph &_g) {
18.48 g=&_g;
18.49 - AlterationNotifier<Node>::ObserverBase::
18.50 - attach(g->getNotifier(Node()));
18.51 - AlterationNotifier<Edge>::ObserverBase::
18.52 - attach(g->getNotifier(Edge()));
18.53 + Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node()));
18.54 + Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge()));
18.55 }
18.56
18.57 void deregist() {
18.58 - AlterationNotifier<Node>::ObserverBase::
18.59 - detach();
18.60 - AlterationNotifier<Edge>::ObserverBase::
18.61 - detach();
18.62 + Parent::NodeNotifier::ObserverBase::detach();
18.63 + Parent::EdgeNotifier::ObserverBase::detach();
18.64 g=0;
18.65 }
18.66
19.1 --- a/lemon/matrix_maps.h Mon Mar 06 09:38:19 2006 +0000
19.2 +++ b/lemon/matrix_maps.h Mon Mar 06 10:28:37 2006 +0000
19.3 @@ -209,9 +209,10 @@
19.4 /// it is needed.
19.5 template <typename _Graph, typename _Item, typename _Value>
19.6 class DynamicMatrixMap
19.7 - : protected AlterationNotifier<_Item>::ObserverBase {
19.8 + : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
19.9 public:
19.10 - typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
19.11 + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase
19.12 + Parent;
19.13
19.14 typedef _Graph Graph;
19.15 typedef _Item Key;
19.16 @@ -235,8 +236,8 @@
19.17 ///
19.18 /// Creates an item matrix for the given graph.
19.19 DynamicMatrixMap(const Graph& _graph)
19.20 - : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
19.21 - Parent::attach(graph.getNotifier(Key()));
19.22 + : values(size(_graph.maxId(Key()) + 1)) {
19.23 + Parent::attach(_graph.getNotifier(Key()));
19.24 }
19.25
19.26 /// \brief Creates an item matrix for the given graph
19.27 @@ -244,14 +245,8 @@
19.28 /// Creates an item matrix for the given graph and assigns for each
19.29 /// pairs of keys the given parameter.
19.30 DynamicMatrixMap(const Graph& _graph, const Value& _val)
19.31 - : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
19.32 - Parent::attach(graph.getNotifier(Key()));
19.33 - }
19.34 -
19.35 - ~DynamicMatrixMap() {
19.36 - if (Parent::attached()) {
19.37 - Parent::detach();
19.38 - }
19.39 + : values(size(_graph.maxId(Key()) + 1), _val) {
19.40 + Parent::attach(_graph.getNotifier(Key()));
19.41 }
19.42
19.43 /// \brief Gives back the value assigned to the \c first - \c second
19.44 @@ -259,7 +254,8 @@
19.45 ///
19.46 /// Gives back the value assigned to the \c first - \c second ordered pair.
19.47 ConstReference operator()(const Key& first, const Key& second) const {
19.48 - return values[index(graph.id(first), graph.id(second))];
19.49 + return values[index(Parent::getNotifier()->id(first),
19.50 + Parent::getNotifier()->id(second))];
19.51 }
19.52
19.53 /// \brief Gives back the value assigned to the \c first - \c second
19.54 @@ -267,14 +263,16 @@
19.55 ///
19.56 /// Gives back the value assigned to the \c first - \c second ordered pair.
19.57 Reference operator()(const Key& first, const Key& second) {
19.58 - return values[index(graph.id(first), graph.id(second))];
19.59 + return values[index(Parent::getNotifier()->id(first),
19.60 + Parent::getNotifier()->id(second))];
19.61 }
19.62
19.63 /// \brief Setter function for the matrix map.
19.64 ///
19.65 /// Setter function for the matrix map.
19.66 void set(const Key& first, const Key& second, const Value& val) {
19.67 - values[index(graph.id(first), graph.id(second))] = val;
19.68 + values[index(Parent::getNotifier()->id(first),
19.69 + Parent::getNotifier()->id(second))] = val;
19.70 }
19.71
19.72 protected:
19.73 @@ -292,15 +290,15 @@
19.74 }
19.75
19.76 virtual void add(const Key& key) {
19.77 - if (size(graph.id(key) + 1) >= (int)values.size()) {
19.78 - values.resize(size(graph.id(key) + 1));
19.79 + if (size(Parent::getNotifier()->id(key) + 1) >= (int)values.size()) {
19.80 + values.resize(size(Parent::getNotifier()->id(key) + 1));
19.81 }
19.82 }
19.83
19.84 virtual void erase(const Key&) {}
19.85
19.86 virtual void build() {
19.87 - values.resize(size(graph.maxId(Key()) + 1));
19.88 + values.resize(size(Parent::getNotifier()->maxId() + 1));
19.89 }
19.90
19.91 virtual void clear() {
19.92 @@ -308,7 +306,6 @@
19.93 }
19.94
19.95 private:
19.96 - const Graph& graph;
19.97 std::vector<Value> values;
19.98 };
19.99
19.100 @@ -320,9 +317,10 @@
19.101 /// it is needed.
19.102 template <typename _Graph, typename _Item, typename _Value>
19.103 class DynamicSymMatrixMap
19.104 - : protected AlterationNotifier<_Item>::ObserverBase {
19.105 + : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
19.106 public:
19.107 - typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
19.108 + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase
19.109 + Parent;
19.110
19.111 typedef _Graph Graph;
19.112 typedef _Item Key;
19.113 @@ -346,8 +344,8 @@
19.114 ///
19.115 /// Creates an item matrix for the given graph.
19.116 DynamicSymMatrixMap(const Graph& _graph)
19.117 - : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
19.118 - Parent::attach(graph.getNotifier(Key()));
19.119 + : values(size(_graph.maxId(Key()) + 1)) {
19.120 + Parent::attach(_graph.getNotifier(Key()));
19.121 }
19.122
19.123 /// \brief Creates an item matrix for the given graph
19.124 @@ -355,14 +353,8 @@
19.125 /// Creates an item matrix for the given graph and assigns for each
19.126 /// pairs of keys the given parameter.
19.127 DynamicSymMatrixMap(const Graph& _graph, const Value& _val)
19.128 - : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
19.129 - Parent::attach(graph.getNotifier(Key()));
19.130 - }
19.131 -
19.132 - ~DynamicSymMatrixMap() {
19.133 - if (Parent::attached()) {
19.134 - Parent::detach();
19.135 - }
19.136 + : values(size(_graph.maxId(Key()) + 1), _val) {
19.137 + Parent::attach(_graph.getNotifier(Key()));
19.138 }
19.139
19.140 /// \brief Gives back the value assigned to the \c first - \c second
19.141 @@ -371,7 +363,8 @@
19.142 /// Gives back the value assigned to the \c first - \c second unordered
19.143 /// pair.
19.144 ConstReference operator()(const Key& first, const Key& second) const {
19.145 - return values[index(graph.id(first), graph.id(second))];
19.146 + return values[index(Parent::getNotifier()->id(first),
19.147 + Parent::getNotifier()->id(second))];
19.148 }
19.149
19.150 /// \brief Gives back the value assigned to the \c first - \c second
19.151 @@ -380,14 +373,16 @@
19.152 /// Gives back the value assigned to the \c first - \c second unordered
19.153 /// pair.
19.154 Reference operator()(const Key& first, const Key& second) {
19.155 - return values[index(graph.id(first), graph.id(second))];
19.156 + return values[index(Parent::getNotifier()->id(first),
19.157 + Parent::getNotifier()->id(second))];
19.158 }
19.159
19.160 /// \brief Setter function for the matrix map.
19.161 ///
19.162 /// Setter function for the matrix map.
19.163 void set(const Key& first, const Key& second, const Value& val) {
19.164 - values[index(graph.id(first), graph.id(second))] = val;
19.165 + values[index(Parent::getNotifier()->id(first),
19.166 + Parent::getNotifier()->id(second))] = val;
19.167 }
19.168
19.169 protected:
19.170 @@ -405,15 +400,15 @@
19.171 }
19.172
19.173 virtual void add(const Key& key) {
19.174 - if (size(graph.id(key) + 1) >= (int)values.size()) {
19.175 - values.resize(size(graph.id(key) + 1));
19.176 + if (size(Parent::getNotifier()->id(key) + 1) >= (int)values.size()) {
19.177 + values.resize(size(Parent::getNotifier()->id(key) + 1));
19.178 }
19.179 }
19.180
19.181 virtual void erase(const Key&) {}
19.182
19.183 virtual void build() {
19.184 - values.resize(size(graph.maxId(Key()) + 1));
19.185 + values.resize(size(Parent::getNotifier()->maxId() + 1));
19.186 }
19.187
19.188 virtual void clear() {
19.189 @@ -421,7 +416,6 @@
19.190 }
19.191
19.192 private:
19.193 - const Graph& graph;
19.194 std::vector<Value> values;
19.195 };
19.196
20.1 --- a/lemon/smart_graph.h Mon Mar 06 09:38:19 2006 +0000
20.2 +++ b/lemon/smart_graph.h Mon Mar 06 10:28:37 2006 +0000
20.3 @@ -27,6 +27,7 @@
20.4
20.5 #include <lemon/bits/invalid.h>
20.6
20.7 +#include <lemon/bits/base_extender.h>
20.8 #include <lemon/bits/graph_extender.h>
20.9
20.10 #include <lemon/bits/utility.h>
21.1 --- a/lemon/xy.h Mon Mar 06 09:38:19 2006 +0000
21.2 +++ b/lemon/xy.h Mon Mar 06 10:28:37 2006 +0000
21.3 @@ -151,6 +151,15 @@
21.4
21.5 };
21.6
21.7 + ///Returns an xy
21.8 +
21.9 + ///Returns an xy
21.10 + ///\relates xy
21.11 + template <typename T>
21.12 + inline xy<T> make_xy(const T& x, const T& y) {
21.13 + return xy<T>(x, y);
21.14 + }
21.15 +
21.16 ///Returns a vector multiplied by a scalar
21.17
21.18 ///Returns a vector multiplied by a scalar