[946] | 1 | /* -*- C++ -*- |
---|
| 2 | * |
---|
[1956] | 3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
| 4 | * |
---|
| 5 | * Copyright (C) 2003-2006 |
---|
| 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
[946] | 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
[1999] | 19 | #ifndef LEMON_BITS_ALTERATION_NOTIFIER_H |
---|
| 20 | #define LEMON_BITS_ALTERATION_NOTIFIER_H |
---|
[946] | 21 | |
---|
| 22 | #include <vector> |
---|
[1999] | 23 | |
---|
| 24 | #include <lemon/bits/utility.h> |
---|
[946] | 25 | |
---|
[1996] | 26 | ///\ingroup graphbits |
---|
[946] | 27 | ///\file |
---|
[1999] | 28 | ///\brief Observer notifier for graph alteration observers. |
---|
[946] | 29 | |
---|
| 30 | namespace lemon { |
---|
| 31 | |
---|
[1999] | 32 | /// \ingroup graphbits |
---|
[1414] | 33 | /// |
---|
[1999] | 34 | /// \brief Notifier class to notify observes about alterations in |
---|
| 35 | /// a container. |
---|
[946] | 36 | /// |
---|
[1999] | 37 | /// The simple graph's can be refered as two containers, one node container |
---|
| 38 | /// and one edge container. But they are not standard containers they |
---|
| 39 | /// does not store values directly they are just key continars for more |
---|
| 40 | /// value containers which are the node and edge maps. |
---|
[946] | 41 | /// |
---|
[1999] | 42 | /// The graph's node and edge sets can be changed as we add or erase |
---|
| 43 | /// nodes and edges in the graph. Lemon would like to handle easily |
---|
| 44 | /// that the node and edge maps should contain values for all nodes or |
---|
| 45 | /// edges. If we want to check on every indicing if the map contains |
---|
| 46 | /// the current indicing key that cause a drawback in the performance |
---|
| 47 | /// in the library. We use an other solution we notify all maps about |
---|
| 48 | /// an alteration in the graph, which cause only drawback on the |
---|
| 49 | /// alteration of the graph. |
---|
| 50 | /// |
---|
| 51 | /// This class provides an interface to the container. The \e first() and \e |
---|
| 52 | /// next() member functions make possible to iterate on the keys of the |
---|
| 53 | /// container. The \e id() function returns an integer id for each key. |
---|
| 54 | /// The \e maxId() function gives back an upper bound of the ids. |
---|
| 55 | /// |
---|
| 56 | /// For the proper functonality of this class, we should notify it |
---|
| 57 | /// about each alteration in the container. The alterations have four type |
---|
| 58 | /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and |
---|
| 59 | /// \e erase() signals that only one or few items added or erased to or |
---|
| 60 | /// from the graph. If all items are erased from the graph or from an empty |
---|
| 61 | /// graph a new graph is builded then it can be signaled with the |
---|
| 62 | /// clear() and build() members. Important rule that if we erase items |
---|
| 63 | /// from graph we should first signal the alteration and after that erase |
---|
| 64 | /// them from the container, on the other way on item addition we should |
---|
| 65 | /// first extend the container and just after that signal the alteration. |
---|
| 66 | /// |
---|
| 67 | /// The alteration can be observed with a class inherited from the |
---|
| 68 | /// \e ObserverBase nested class. The signals can be handled with |
---|
| 69 | /// overriding the virtual functions defined in the base class. |
---|
| 70 | /// The observer base can be attached to the notifier with the |
---|
| 71 | /// \e attach() member and can be detached with detach() function. |
---|
| 72 | /// |
---|
| 73 | /// Alteration observers try to be exception safe. This can be achived |
---|
| 74 | /// when the observers does not throw exception on \e erase() and |
---|
| 75 | /// \e clear(). Less strict condition is that the \e erase() should |
---|
| 76 | /// not throw exception after an \e add() with the same parameter and |
---|
| 77 | /// the \e clear() should not throw exception after a \e build(). |
---|
| 78 | /// |
---|
| 79 | /// There are some place when the alteration observing is not completly |
---|
| 80 | /// reliable. If we want to carry out the node degree in the graph |
---|
| 81 | /// as in the \ref InDegMap and we use the reverseEdge that cause |
---|
| 82 | /// unreliable functionality. Because the alteration observing signals |
---|
| 83 | /// only erasing and adding but not the reversing it will stores bad |
---|
| 84 | /// degrees. The sub graph adaptors cannot signal the alterations because |
---|
| 85 | /// just a setting in the filter map can modify the graph and this cannot |
---|
| 86 | /// be watched in any way. |
---|
| 87 | /// |
---|
| 88 | /// \param _Container The container which is observed. |
---|
| 89 | /// \param _Item The item type which is obserbved. |
---|
[946] | 90 | /// |
---|
| 91 | /// \author Balazs Dezso |
---|
| 92 | |
---|
[1999] | 93 | template <typename _Container, typename _Item> |
---|
[1038] | 94 | class AlterationNotifier { |
---|
[946] | 95 | public: |
---|
[1989] | 96 | |
---|
| 97 | typedef True Notifier; |
---|
| 98 | |
---|
[1999] | 99 | typedef _Container Container; |
---|
[946] | 100 | typedef _Item Item; |
---|
| 101 | |
---|
[1999] | 102 | /// \brief ObserverBase is the base class for the observers. |
---|
| 103 | /// |
---|
[946] | 104 | /// ObserverBase is the abstract base class for the observers. |
---|
| 105 | /// It will be notified about an item was inserted into or |
---|
| 106 | /// erased from the graph. |
---|
| 107 | /// |
---|
| 108 | /// The observer interface contains some pure virtual functions |
---|
| 109 | /// to override. The add() and erase() functions are |
---|
| 110 | /// to notify the oberver when one item is added or |
---|
| 111 | /// erased. |
---|
| 112 | /// |
---|
| 113 | /// The build() and clear() members are to notify the observer |
---|
[1204] | 114 | /// about the container is built from an empty container or |
---|
[946] | 115 | /// is cleared to an empty container. |
---|
| 116 | /// |
---|
| 117 | /// \author Balazs Dezso |
---|
| 118 | |
---|
| 119 | class ObserverBase { |
---|
| 120 | protected: |
---|
[1999] | 121 | typedef AlterationNotifier Notifier; |
---|
[946] | 122 | |
---|
[1038] | 123 | friend class AlterationNotifier; |
---|
[946] | 124 | |
---|
[1414] | 125 | /// \brief Default constructor. |
---|
| 126 | /// |
---|
[946] | 127 | /// Default constructor for ObserverBase. |
---|
| 128 | /// |
---|
[1999] | 129 | ObserverBase() : notifier(0) {} |
---|
[946] | 130 | |
---|
[1999] | 131 | /// \brief Constructor which attach the observer into notifier. |
---|
| 132 | /// |
---|
| 133 | /// Constructor which attach the observer into notifier. |
---|
| 134 | ObserverBase(AlterationNotifier& _notifier) { |
---|
| 135 | attach(_notifier); |
---|
| 136 | } |
---|
| 137 | |
---|
| 138 | /// \brief Constructor which attach the obserever to the same notifier. |
---|
| 139 | /// |
---|
| 140 | /// Constructor which attach the obserever to the same notifier as |
---|
| 141 | /// the other observer is attached to. |
---|
[1685] | 142 | ObserverBase(const ObserverBase& copy) { |
---|
| 143 | if (copy.attached()) { |
---|
[1999] | 144 | attach(*copy.getNotifier()); |
---|
[1685] | 145 | } |
---|
| 146 | } |
---|
| 147 | |
---|
[1999] | 148 | /// \brief Destructor |
---|
| 149 | virtual ~ObserverBase() { |
---|
| 150 | if (attached()) { |
---|
| 151 | detach(); |
---|
| 152 | } |
---|
| 153 | } |
---|
[946] | 154 | |
---|
[1414] | 155 | /// \brief Attaches the observer into an AlterationNotifier. |
---|
| 156 | /// |
---|
[1038] | 157 | /// This member attaches the observer into an AlterationNotifier. |
---|
[946] | 158 | /// |
---|
[1999] | 159 | void attach(AlterationNotifier& _notifier) { |
---|
| 160 | notifier = &_notifier; |
---|
| 161 | notifier->attach(*this); |
---|
[946] | 162 | } |
---|
| 163 | |
---|
[1414] | 164 | /// \brief Detaches the observer into an AlterationNotifier. |
---|
| 165 | /// |
---|
[1038] | 166 | /// This member detaches the observer from an AlterationNotifier. |
---|
[946] | 167 | /// |
---|
| 168 | void detach() { |
---|
[1999] | 169 | notifier->detach(*this); |
---|
[946] | 170 | } |
---|
| 171 | |
---|
| 172 | |
---|
[1999] | 173 | /// \brief Gives back a pointer to the notifier which the map |
---|
[946] | 174 | /// attached into. |
---|
| 175 | /// |
---|
[1999] | 176 | /// This function gives back a pointer to the notifier which the map |
---|
| 177 | /// attached into. |
---|
| 178 | /// |
---|
| 179 | Notifier* getNotifier() const { return const_cast<Notifier*>(notifier); } |
---|
[946] | 180 | |
---|
[1999] | 181 | /// Gives back true when the observer is attached into a notifier. |
---|
| 182 | bool attached() const { return notifier != 0; } |
---|
[1685] | 183 | |
---|
[946] | 184 | private: |
---|
| 185 | |
---|
| 186 | ObserverBase& operator=(const ObserverBase& copy); |
---|
| 187 | |
---|
| 188 | protected: |
---|
| 189 | |
---|
[1999] | 190 | Notifier* notifier; |
---|
| 191 | int notifier_index; |
---|
[946] | 192 | |
---|
| 193 | /// \brief The member function to notificate the observer about an |
---|
| 194 | /// item is added to the container. |
---|
| 195 | /// |
---|
| 196 | /// The add() member function notificates the observer about an item |
---|
| 197 | /// is added to the container. It have to be overrided in the |
---|
| 198 | /// subclasses. |
---|
| 199 | |
---|
[1414] | 200 | virtual void add(const Item&) = 0; |
---|
[946] | 201 | |
---|
[1414] | 202 | /// \brief The member function to notificate the observer about |
---|
[1718] | 203 | /// more item is added to the container. |
---|
[1414] | 204 | /// |
---|
[1718] | 205 | /// The add() member function notificates the observer about more item |
---|
[1414] | 206 | /// is added to the container. It have to be overrided in the |
---|
| 207 | /// subclasses. |
---|
| 208 | |
---|
| 209 | virtual void add(const std::vector<Item>& items) { |
---|
[1999] | 210 | int i; |
---|
| 211 | try { |
---|
| 212 | for (i = 0; i < (int)items.size(); ++i) { |
---|
| 213 | add(items[i]); |
---|
| 214 | } |
---|
| 215 | } catch (...) { |
---|
| 216 | for (int j = 0; j < i; ++j) { |
---|
| 217 | add(items[j]); |
---|
| 218 | } |
---|
| 219 | throw; |
---|
| 220 | } |
---|
[1414] | 221 | } |
---|
[946] | 222 | |
---|
| 223 | /// \brief The member function to notificate the observer about an |
---|
| 224 | /// item is erased from the container. |
---|
| 225 | /// |
---|
| 226 | /// The erase() member function notificates the observer about an |
---|
| 227 | /// item is erased from the container. It have to be overrided in |
---|
| 228 | /// the subclasses. |
---|
| 229 | |
---|
| 230 | virtual void erase(const Item&) = 0; |
---|
| 231 | |
---|
[1718] | 232 | /// \brief The member function to notificate the observer about |
---|
| 233 | /// more item is erased from the container. |
---|
| 234 | /// |
---|
| 235 | /// The erase() member function notificates the observer about more item |
---|
| 236 | /// is erased from the container. It have to be overrided in the |
---|
| 237 | /// subclasses. |
---|
[1414] | 238 | virtual void erase(const std::vector<Item>& items) { |
---|
[1999] | 239 | for (int i = 0; i < (int)items.size(); ++i) { |
---|
| 240 | erase(items[i]); |
---|
| 241 | } |
---|
[1414] | 242 | } |
---|
| 243 | |
---|
[946] | 244 | /// \brief The member function to notificate the observer about the |
---|
[1204] | 245 | /// container is built. |
---|
[946] | 246 | /// |
---|
| 247 | /// The build() member function notificates the observer about the |
---|
[1204] | 248 | /// container is built from an empty container. It have to be |
---|
[946] | 249 | /// overrided in the subclasses. |
---|
| 250 | |
---|
[1999] | 251 | virtual void build() { |
---|
| 252 | Item it; |
---|
| 253 | try { |
---|
| 254 | for (notifier->first(it); it != INVALID; notifier->next(it)) { |
---|
| 255 | add(it); |
---|
| 256 | } |
---|
| 257 | } catch (...) { |
---|
| 258 | Item jt; |
---|
| 259 | for (notifier->first(jt); jt != it; notifier->next(jt)) { |
---|
| 260 | erase(jt); |
---|
| 261 | } |
---|
| 262 | throw; |
---|
| 263 | } |
---|
| 264 | } |
---|
[946] | 265 | |
---|
| 266 | /// \brief The member function to notificate the observer about all |
---|
| 267 | /// items are erased from the container. |
---|
| 268 | /// |
---|
| 269 | /// The clear() member function notificates the observer about all |
---|
| 270 | /// items are erased from the container. It have to be overrided in |
---|
[1999] | 271 | /// the subclasses. |
---|
| 272 | virtual void clear() { |
---|
| 273 | Item it; |
---|
| 274 | for (notifier->first(it); it != INVALID; notifier->next(it)) { |
---|
| 275 | erase(it); |
---|
| 276 | } |
---|
| 277 | } |
---|
[946] | 278 | |
---|
| 279 | }; |
---|
| 280 | |
---|
| 281 | protected: |
---|
| 282 | |
---|
[1999] | 283 | const Container* container; |
---|
[946] | 284 | |
---|
[1999] | 285 | typedef std::vector<ObserverBase*> Observers; |
---|
| 286 | Observers observers; |
---|
[946] | 287 | |
---|
| 288 | |
---|
| 289 | public: |
---|
| 290 | |
---|
[1999] | 291 | /// \brief Default constructor. |
---|
[946] | 292 | /// |
---|
[1038] | 293 | /// The default constructor of the AlterationNotifier. |
---|
[1999] | 294 | /// It creates an empty notifier. |
---|
| 295 | AlterationNotifier() |
---|
| 296 | : container(0) {} |
---|
[946] | 297 | |
---|
[1999] | 298 | /// \brief Constructor. |
---|
| 299 | /// |
---|
| 300 | /// Constructor with the observed container parameter. |
---|
| 301 | AlterationNotifier(const Container& _container) |
---|
| 302 | : container(&_container) {} |
---|
| 303 | |
---|
| 304 | /// \brief Copy Constructor of the AlterationNotifier. |
---|
| 305 | /// |
---|
[1038] | 306 | /// Copy constructor of the AlterationNotifier. |
---|
[1999] | 307 | /// It creates only an empty notifier because the copiable |
---|
| 308 | /// notifier's observers have to be registered still into that notifier. |
---|
| 309 | AlterationNotifier(const AlterationNotifier& _notifier) |
---|
| 310 | : container(_notifier.container) {} |
---|
[946] | 311 | |
---|
[1999] | 312 | /// \brief Destructor. |
---|
| 313 | /// |
---|
| 314 | /// Destructor of the AlterationNotifier. |
---|
| 315 | /// |
---|
| 316 | ~AlterationNotifier() { |
---|
| 317 | typename Observers::iterator it; |
---|
| 318 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
| 319 | (*it)->notifier = 0; |
---|
[946] | 320 | } |
---|
| 321 | } |
---|
| 322 | |
---|
[1999] | 323 | /// \brief Sets the container. |
---|
[946] | 324 | /// |
---|
[1999] | 325 | /// Sets the container. |
---|
| 326 | void setContainer(const Container& _container) { |
---|
| 327 | container = &_container; |
---|
[946] | 328 | } |
---|
[1999] | 329 | |
---|
| 330 | protected: |
---|
| 331 | |
---|
| 332 | AlterationNotifier& operator=(const AlterationNotifier&); |
---|
| 333 | |
---|
| 334 | public: |
---|
| 335 | |
---|
| 336 | |
---|
| 337 | |
---|
| 338 | /// \brief First item in the container. |
---|
| 339 | /// |
---|
| 340 | /// Returns the first item in the container. It is |
---|
| 341 | /// for start the iteration on the container. |
---|
| 342 | void first(Item& item) const { |
---|
| 343 | container->first(item); |
---|
| 344 | } |
---|
| 345 | |
---|
| 346 | /// \brief Next item in the container. |
---|
| 347 | /// |
---|
| 348 | /// Returns the next item in the container. It is |
---|
| 349 | /// for iterate on the container. |
---|
| 350 | void next(Item& item) const { |
---|
| 351 | container->next(item); |
---|
| 352 | } |
---|
| 353 | |
---|
| 354 | /// \brief Returns the id of the item. |
---|
| 355 | /// |
---|
| 356 | /// Returns the id of the item provided by the container. |
---|
| 357 | int id(const Item& item) const { |
---|
| 358 | return container->id(item); |
---|
| 359 | } |
---|
| 360 | |
---|
| 361 | /// \brief Returns the maximum id of the container. |
---|
| 362 | /// |
---|
| 363 | /// Returns the maximum id of the container. |
---|
| 364 | int maxId() const { |
---|
| 365 | return container->maxId(Item()); |
---|
| 366 | } |
---|
| 367 | |
---|
[946] | 368 | protected: |
---|
| 369 | |
---|
| 370 | void attach(ObserverBase& observer) { |
---|
[1999] | 371 | observers.push_back(&observer); |
---|
| 372 | observer.notifier = this; |
---|
| 373 | observer.notifier_index = observers.size() - 1; |
---|
[946] | 374 | } |
---|
| 375 | |
---|
[1999] | 376 | void detach(ObserverBase& observer) { |
---|
| 377 | observers.back()->notifier_index = observer.notifier_index; |
---|
| 378 | observers[observer.notifier_index] = observers.back(); |
---|
| 379 | observers.pop_back(); |
---|
| 380 | observer.notifier = 0; |
---|
[946] | 381 | } |
---|
| 382 | |
---|
| 383 | public: |
---|
| 384 | |
---|
[1999] | 385 | /// \brief Notifies all the registed observers about an item added to |
---|
[1414] | 386 | /// the container. |
---|
| 387 | /// |
---|
[1999] | 388 | /// It notifies all the registed observers about an item added to |
---|
[1414] | 389 | /// the container. |
---|
[946] | 390 | /// |
---|
[1414] | 391 | void add(const Item& item) { |
---|
[1999] | 392 | typename Observers::iterator it; |
---|
[1979] | 393 | try { |
---|
[1999] | 394 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
[1979] | 395 | (*it)->add(item); |
---|
| 396 | } |
---|
| 397 | } catch (...) { |
---|
[1999] | 398 | typename Observers::iterator jt; |
---|
| 399 | for (jt = observers.begin(); jt != it; ++jt) { |
---|
[1979] | 400 | (*it)->erase(item); |
---|
| 401 | } |
---|
| 402 | throw; |
---|
[946] | 403 | } |
---|
| 404 | } |
---|
| 405 | |
---|
[1999] | 406 | /// \brief Notifies all the registed observers about more item added to |
---|
[1414] | 407 | /// the container. |
---|
| 408 | /// |
---|
[1999] | 409 | /// It notifies all the registed observers about more item added to |
---|
[1414] | 410 | /// the container. |
---|
| 411 | /// |
---|
| 412 | void add(const std::vector<Item>& items) { |
---|
[1999] | 413 | typename Observers::iterator it; |
---|
[1979] | 414 | try { |
---|
[1999] | 415 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
[1979] | 416 | (*it)->add(items); |
---|
| 417 | } |
---|
| 418 | } catch (...) { |
---|
[1999] | 419 | typename Observers::iterator jt; |
---|
| 420 | for (jt = observers.begin(); jt != it; ++jt) { |
---|
[1979] | 421 | (*it)->erase(items); |
---|
| 422 | } |
---|
| 423 | throw; |
---|
[1414] | 424 | } |
---|
| 425 | } |
---|
| 426 | |
---|
[1999] | 427 | /// \brief Notifies all the registed observers about an item erased from |
---|
[1414] | 428 | /// the container. |
---|
| 429 | /// |
---|
[1999] | 430 | /// It notifies all the registed observers about an item erased from |
---|
[1414] | 431 | /// the container. |
---|
[946] | 432 | /// |
---|
| 433 | void erase(const Item& key) { |
---|
[1999] | 434 | typename Observers::iterator it; |
---|
| 435 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
[946] | 436 | (*it)->erase(key); |
---|
| 437 | } |
---|
| 438 | } |
---|
[1414] | 439 | |
---|
[1999] | 440 | /// \brief Notifies all the registed observers about more item erased |
---|
[1414] | 441 | /// from the container. |
---|
| 442 | /// |
---|
[1999] | 443 | /// It notifies all the registed observers about more item erased from |
---|
[1414] | 444 | /// the container. |
---|
| 445 | /// |
---|
| 446 | void erase(const std::vector<Item>& items) { |
---|
[1999] | 447 | typename Observers::iterator it; |
---|
| 448 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
[1414] | 449 | (*it)->erase(items); |
---|
| 450 | } |
---|
| 451 | } |
---|
[946] | 452 | |
---|
[1999] | 453 | /// \brief Notifies all the registed observers about the container is |
---|
[1414] | 454 | /// built. |
---|
| 455 | /// |
---|
[1999] | 456 | /// Notifies all the registed observers about the container is built |
---|
[946] | 457 | /// from an empty container. |
---|
| 458 | void build() { |
---|
[1999] | 459 | typename Observers::iterator it; |
---|
[1979] | 460 | try { |
---|
[1999] | 461 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
[1979] | 462 | (*it)->build(); |
---|
| 463 | } |
---|
| 464 | } catch (...) { |
---|
[1999] | 465 | typename Observers::iterator jt; |
---|
| 466 | for (jt = observers.begin(); jt != it; ++jt) { |
---|
[1979] | 467 | (*it)->clear(); |
---|
| 468 | } |
---|
| 469 | throw; |
---|
[946] | 470 | } |
---|
| 471 | } |
---|
| 472 | |
---|
| 473 | |
---|
[1999] | 474 | /// \brief Notifies all the registed observers about all items are |
---|
[1414] | 475 | /// erased. |
---|
| 476 | /// |
---|
[1999] | 477 | /// Notifies all the registed observers about all items are erased |
---|
[946] | 478 | /// from the container. |
---|
| 479 | void clear() { |
---|
[1999] | 480 | typename Observers::iterator it; |
---|
| 481 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
[946] | 482 | (*it)->clear(); |
---|
| 483 | } |
---|
| 484 | } |
---|
| 485 | }; |
---|
| 486 | |
---|
| 487 | } |
---|
| 488 | |
---|
| 489 | #endif |
---|