Changeset 1999:2ff283124dfc in lemon-0.x for lemon/bits/alteration_notifier.h
- Timestamp:
- 03/06/06 11:28:37 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2609
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/alteration_notifier.h
r1996 r1999 17 17 */ 18 18 19 #ifndef LEMON_ ALTERATION_NOTIFIER_H20 #define LEMON_ ALTERATION_NOTIFIER_H19 #ifndef LEMON_BITS_ALTERATION_NOTIFIER_H 20 #define LEMON_BITS_ALTERATION_NOTIFIER_H 21 21 22 22 #include <vector> 23 #include <algorithm> 23 24 #include <lemon/bits/utility.h> 24 25 25 26 ///\ingroup graphbits 26 27 ///\file 27 ///\brief Observer registryfor graph alteration observers.28 ///\brief Observer notifier for graph alteration observers. 28 29 29 30 namespace lemon { 30 31 31 /// \addtogroup graphbits 32 /// @{ 33 34 /// \brief Registry class to register objects observes alterations in 35 /// the graph. 36 /// 37 /// This class is a registry for the objects which observe the 38 /// alterations in a container. The alteration observers can be attached 39 /// to and detached from the registry. The observers have to inherit 40 /// from the \ref AlterationNotifier::ObserverBase and override 41 /// the virtual functions in that. 42 /// 43 /// The most important application of the alteration observing is the 44 /// dynamic map implementation. 45 /// 46 /// \param _Item The item type what the observers are observing, usually 47 /// edge or node. 32 /// \ingroup graphbits 33 /// 34 /// \brief Notifier class to notify observes about alterations in 35 /// a container. 36 /// 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. 41 /// 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. 48 90 /// 49 91 /// \author Balazs Dezso 50 92 51 template <typename _ Item>93 template <typename _Container, typename _Item> 52 94 class AlterationNotifier { 53 95 public: … … 55 97 typedef True Notifier; 56 98 99 typedef _Container Container; 57 100 typedef _Item Item; 58 101 59 /// ObserverBase is the base class for the observers.60 102 /// \brief ObserverBase is the base class for the observers. 103 /// 61 104 /// ObserverBase is the abstract base class for the observers. 62 105 /// It will be notified about an item was inserted into or … … 76 119 class ObserverBase { 77 120 protected: 78 typedef AlterationNotifier Registry;121 typedef AlterationNotifier Notifier; 79 122 80 123 friend class AlterationNotifier; … … 84 127 /// Default constructor for ObserverBase. 85 128 /// 86 ObserverBase() : registry(0) {} 87 129 ObserverBase() : notifier(0) {} 130 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. 88 142 ObserverBase(const ObserverBase& copy) { 89 143 if (copy.attached()) { 90 copy.getRegistry()->attach(*this);144 attach(*copy.getNotifier()); 91 145 } 92 146 } 93 147 94 virtual ~ObserverBase() {} 148 /// \brief Destructor 149 virtual ~ObserverBase() { 150 if (attached()) { 151 detach(); 152 } 153 } 95 154 96 155 /// \brief Attaches the observer into an AlterationNotifier. … … 98 157 /// This member attaches the observer into an AlterationNotifier. 99 158 /// 100 void attach(AlterationNotifier& r) {101 registry = &r;102 registry->attach(*this);159 void attach(AlterationNotifier& _notifier) { 160 notifier = &_notifier; 161 notifier->attach(*this); 103 162 } 104 163 … … 108 167 /// 109 168 void detach() { 110 if (registry) { 111 registry->detach(*this); 112 } 113 } 114 115 116 /// Gives back a pointer to the registry what the map attached into. 117 118 /// This function gives back a pointer to the registry what the map 169 notifier->detach(*this); 170 } 171 172 173 /// \brief Gives back a pointer to the notifier which the map 119 174 /// attached into. 120 175 /// 121 Registry* getRegistry() const { return const_cast<Registry*>(registry); } 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); } 122 180 123 /// Gives back true when the observer is attached into a registry.124 bool attached() const { return registry!= 0; }181 /// Gives back true when the observer is attached into a notifier. 182 bool attached() const { return notifier != 0; } 125 183 126 184 private: … … 130 188 protected: 131 189 132 Registry* registry;133 int registry_index;190 Notifier* notifier; 191 int notifier_index; 134 192 135 193 /// \brief The member function to notificate the observer about an … … 150 208 151 209 virtual void add(const std::vector<Item>& items) { 152 for (int i = 0; i < (int)items.size(); ++i) { 153 add(items[i]); 154 } 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 } 155 221 } 156 222 … … 171 237 /// subclasses. 172 238 virtual void erase(const std::vector<Item>& items) { 173 174 175 239 for (int i = 0; i < (int)items.size(); ++i) { 240 erase(items[i]); 241 } 176 242 } 177 243 … … 183 249 /// overrided in the subclasses. 184 250 185 virtual void build() = 0; 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 } 186 265 187 266 /// \brief The member function to notificate the observer about all … … 190 269 /// The clear() member function notificates the observer about all 191 270 /// items are erased from the container. It have to be overrided in 192 /// the subclasses. 193 194 virtual void clear() = 0; 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 } 195 278 196 279 }; 197 280 198 281 protected: 199 200 201 typedef std::vector<ObserverBase*> Container; 202 203 Container container;282 283 const Container* container; 284 285 typedef std::vector<ObserverBase*> Observers; 286 Observers observers; 204 287 205 288 206 289 public: 207 290 208 /// Default constructor. 209 291 /// \brief Default constructor. 210 292 /// 211 293 /// The default constructor of the AlterationNotifier. 212 /// It creates an empty registry. 213 AlterationNotifier() {} 214 215 /// Copy Constructor of the AlterationNotifier. 216 294 /// It creates an empty notifier. 295 AlterationNotifier() 296 : container(0) {} 297 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 /// 217 306 /// Copy constructor of the AlterationNotifier. 218 /// It creates only an empty registry because the copiable 219 /// registry's observers have to be registered still into that registry. 220 AlterationNotifier(const AlterationNotifier&) {} 221 222 /// Assign operator. 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) {} 311 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; 320 } 321 } 322 323 /// \brief Sets the container. 324 /// 325 /// Sets the container. 326 void setContainer(const Container& _container) { 327 container = &_container; 328 } 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 } 223 367 224 /// Assign operator for the AlterationNotifier.225 /// It makes the notifier only empty because the copiable226 /// notifier's observers have to be registered still into that registry.227 AlterationNotifier& operator=(const AlterationNotifier&) {228 typename Container::iterator it;229 for (it = container.begin(); it != container.end(); ++it) {230 (*it)->registry = 0;231 }232 }233 234 /// Destructor.235 236 /// Destructor of the AlterationNotifier.237 ///238 ~AlterationNotifier() {239 typename Container::iterator it;240 for (it = container.begin(); it != container.end(); ++it) {241 (*it)->registry = 0;242 }243 }244 245 246 368 protected: 247 369 248 370 void attach(ObserverBase& observer) { 249 container.push_back(&observer);250 observer. registry= this;251 observer. registry_index = container.size()-1;371 observers.push_back(&observer); 372 observer.notifier = this; 373 observer.notifier_index = observers.size() - 1; 252 374 } 253 375 254 void detach(ObserverBase& base) {255 container.back()->registry_index = base.registry_index;256 container[base.registry_index] = container.back();257 container.pop_back();258 base.registry= 0;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; 259 381 } 260 382 261 383 public: 262 384 263 /// \brief Notifies all the registe red observers about an Item added to264 /// the container. 265 /// 266 /// It notifies all the registe red observers about an Item added to385 /// \brief Notifies all the registed observers about an item added to 386 /// the container. 387 /// 388 /// It notifies all the registed observers about an item added to 267 389 /// the container. 268 390 /// 269 391 void add(const Item& item) { 270 typename Container::iterator it;392 typename Observers::iterator it; 271 393 try { 272 for (it = container.begin(); it != container.end(); ++it) {394 for (it = observers.begin(); it != observers.end(); ++it) { 273 395 (*it)->add(item); 274 396 } 275 397 } catch (...) { 276 typename Container::iterator jt;277 for (jt = container.begin(); jt != it; ++it) {398 typename Observers::iterator jt; 399 for (jt = observers.begin(); jt != it; ++jt) { 278 400 (*it)->erase(item); 279 401 } … … 282 404 } 283 405 284 /// \brief Notifies all the registe red observers about more Item added to285 /// the container. 286 /// 287 /// It notifies all the registe red observers about more Item added to406 /// \brief Notifies all the registed observers about more item added to 407 /// the container. 408 /// 409 /// It notifies all the registed observers about more item added to 288 410 /// the container. 289 411 /// 290 412 void add(const std::vector<Item>& items) { 291 typename Container::iterator it;413 typename Observers::iterator it; 292 414 try { 293 for (it = container.begin(); it != container.end(); ++it) {415 for (it = observers.begin(); it != observers.end(); ++it) { 294 416 (*it)->add(items); 295 417 } 296 418 } catch (...) { 297 typename Container::iterator jt;298 for (jt = container.begin(); jt != it; ++it) {419 typename Observers::iterator jt; 420 for (jt = observers.begin(); jt != it; ++jt) { 299 421 (*it)->erase(items); 300 422 } … … 303 425 } 304 426 305 /// \brief Notifies all the registe red observers about an Item erased from427 /// \brief Notifies all the registed observers about an item erased from 306 428 /// the container. 307 429 /// 308 /// It notifies all the registe red observers about an Item erased from430 /// It notifies all the registed observers about an item erased from 309 431 /// the container. 310 432 /// 311 433 void erase(const Item& key) { 312 typename Container::iterator it;313 for (it = container.begin(); it != container.end(); ++it) {434 typename Observers::iterator it; 435 for (it = observers.begin(); it != observers.end(); ++it) { 314 436 (*it)->erase(key); 315 437 } 316 438 } 317 439 318 /// \brief Notifies all the registe red observers about more Item erased440 /// \brief Notifies all the registed observers about more item erased 319 441 /// from the container. 320 442 /// 321 /// It notifies all the registe red observers about more Item erased from443 /// It notifies all the registed observers about more item erased from 322 444 /// the container. 323 445 /// 324 446 void erase(const std::vector<Item>& items) { 325 typename Container::iterator it;326 for (it = container.begin(); it != container.end(); ++it) {447 typename Observers::iterator it; 448 for (it = observers.begin(); it != observers.end(); ++it) { 327 449 (*it)->erase(items); 328 450 } 329 451 } 330 452 331 /// \brief Notifies all the registe red observers about the container is453 /// \brief Notifies all the registed observers about the container is 332 454 /// built. 333 455 /// 334 /// Notifies all the registe red observers about the container is built456 /// Notifies all the registed observers about the container is built 335 457 /// from an empty container. 336 458 void build() { 337 typename Container::iterator it;459 typename Observers::iterator it; 338 460 try { 339 for (it = container.begin(); it != container.end(); ++it) {461 for (it = observers.begin(); it != observers.end(); ++it) { 340 462 (*it)->build(); 341 463 } 342 464 } catch (...) { 343 typename Container::iterator jt;344 for (jt = container.begin(); jt != it; ++it) {465 typename Observers::iterator jt; 466 for (jt = observers.begin(); jt != it; ++jt) { 345 467 (*it)->clear(); 346 468 } … … 350 472 351 473 352 /// \brief Notifies all the registe red observers about all Items are474 /// \brief Notifies all the registed observers about all items are 353 475 /// erased. 354 476 /// 355 /// Notifies all the registe red observers about all Items are erased477 /// Notifies all the registed observers about all items are erased 356 478 /// from the container. 357 479 void clear() { 358 typename Container::iterator it;359 for (it = container.begin(); it != container.end(); ++it) {480 typename Observers::iterator it; 481 for (it = observers.begin(); it != observers.end(); ++it) { 360 482 (*it)->clear(); 361 483 } … … 363 485 }; 364 486 365 366 /// @}367 368 369 487 } 370 488
Note: See TracChangeset
for help on using the changeset viewer.