Changeset 314:2cc60866a0c9 in lemon-1.2 for lemon/bits/alteration_notifier.h
- Timestamp:
- 10/09/08 13:27:35 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/alteration_notifier.h
r313 r314 25 25 #include <lemon/core.h> 26 26 27 // /\ingroup graphbits28 // /\file29 // /\brief Observer notifier for graph alteration observers.27 //\ingroup graphbits 28 //\file 29 //\brief Observer notifier for graph alteration observers. 30 30 31 31 namespace lemon { 32 32 33 // /\ingroup graphbits34 // /35 // /\brief Notifier class to notify observes about alterations in36 // /a container.37 // /38 // /The simple graph's can be refered as two containers, one node container39 // /and one edge container. But they are not standard containers they40 // /does not store values directly they are just key continars for more41 // /value containers which are the node and edge maps.42 // /43 // /The graph's node and edge sets can be changed as we add or erase44 // /nodes and edges in the graph. LEMON would like to handle easily45 // /that the node and edge maps should contain values for all nodes or46 // /edges. If we want to check on every indicing if the map contains47 // /the current indicing key that cause a drawback in the performance48 // /in the library. We use another solution we notify all maps about49 // /an alteration in the graph, which cause only drawback on the50 // /alteration of the graph.51 // /52 // /This class provides an interface to the container. The \e first() and \e53 // /next() member functions make possible to iterate on the keys of the54 // /container. The \e id() function returns an integer id for each key.55 // /The \e maxId() function gives back an upper bound of the ids.56 // /57 // /For the proper functonality of this class, we should notify it58 // /about each alteration in the container. The alterations have four type59 // /as \e add(), \e erase(), \e build() and \e clear(). The \e add() and60 // /\e erase() signals that only one or few items added or erased to or61 // /from the graph. If all items are erased from the graph or from an empty62 // /graph a new graph is builded then it can be signaled with the63 // /clear() and build() members. Important rule that if we erase items64 // /from graph we should first signal the alteration and after that erase65 // /them from the container, on the other way on item addition we should66 // /first extend the container and just after that signal the alteration.67 // /68 // /The alteration can be observed with a class inherited from the69 // /\e ObserverBase nested class. The signals can be handled with70 // /overriding the virtual functions defined in the base class. The71 // /observer base can be attached to the notifier with the72 // /\e attach() member and can be detached with detach() function. The73 // /alteration handlers should not call any function which signals74 // /an other alteration in the same notifier and should not75 // /detach any observer from the notifier.76 // /77 // /Alteration observers try to be exception safe. If an \e add() or78 // /a \e clear() function throws an exception then the remaining79 // /observeres will not be notified and the fulfilled additions will80 // /be rolled back by calling the \e erase() or \e clear()81 // /functions. Thence the \e erase() and \e clear() should not throw82 // / exception. Actullay, it can be throw only \ref ImmediateDetach83 // /exception which detach the observer from the notifier.84 // /85 // /There are some place when the alteration observing is not completly86 // /reliable. If we want to carry out the node degree in the graph87 // /as in the \ref InDegMap and we use the reverseEdge that cause88 // /unreliable functionality. Because the alteration observing signals89 // /only erasing and adding but not the reversing it will stores bad90 // /degrees. The sub graph adaptors cannot signal the alterations because91 // /just a setting in the filter map can modify the graph and this cannot92 // /be watched in any way.93 // /94 // /\param _Container The container which is observed.95 // /\param _Item The item type which is obserbved.33 // \ingroup graphbits 34 // 35 // \brief Notifier class to notify observes about alterations in 36 // a container. 37 // 38 // The simple graph's can be refered as two containers, one node container 39 // and one edge container. But they are not standard containers they 40 // does not store values directly they are just key continars for more 41 // value containers which are the node and edge maps. 42 // 43 // The graph's node and edge sets can be changed as we add or erase 44 // nodes and edges in the graph. LEMON would like to handle easily 45 // that the node and edge maps should contain values for all nodes or 46 // edges. If we want to check on every indicing if the map contains 47 // the current indicing key that cause a drawback in the performance 48 // in the library. We use another solution we notify all maps about 49 // an alteration in the graph, which cause only drawback on the 50 // alteration of the graph. 51 // 52 // This class provides an interface to the container. The \e first() and \e 53 // next() member functions make possible to iterate on the keys of the 54 // container. The \e id() function returns an integer id for each key. 55 // The \e maxId() function gives back an upper bound of the ids. 56 // 57 // For the proper functonality of this class, we should notify it 58 // about each alteration in the container. The alterations have four type 59 // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and 60 // \e erase() signals that only one or few items added or erased to or 61 // from the graph. If all items are erased from the graph or from an empty 62 // graph a new graph is builded then it can be signaled with the 63 // clear() and build() members. Important rule that if we erase items 64 // from graph we should first signal the alteration and after that erase 65 // them from the container, on the other way on item addition we should 66 // first extend the container and just after that signal the alteration. 67 // 68 // The alteration can be observed with a class inherited from the 69 // \e ObserverBase nested class. The signals can be handled with 70 // overriding the virtual functions defined in the base class. The 71 // observer base can be attached to the notifier with the 72 // \e attach() member and can be detached with detach() function. The 73 // alteration handlers should not call any function which signals 74 // an other alteration in the same notifier and should not 75 // detach any observer from the notifier. 76 // 77 // Alteration observers try to be exception safe. If an \e add() or 78 // a \e clear() function throws an exception then the remaining 79 // observeres will not be notified and the fulfilled additions will 80 // be rolled back by calling the \e erase() or \e clear() 81 // functions. Thence the \e erase() and \e clear() should not throw 82 // exception. Actullay, it can be throw only \ref ImmediateDetach 83 // exception which detach the observer from the notifier. 84 // 85 // There are some place when the alteration observing is not completly 86 // reliable. If we want to carry out the node degree in the graph 87 // as in the \ref InDegMap and we use the reverseEdge that cause 88 // unreliable functionality. Because the alteration observing signals 89 // only erasing and adding but not the reversing it will stores bad 90 // degrees. The sub graph adaptors cannot signal the alterations because 91 // just a setting in the filter map can modify the graph and this cannot 92 // be watched in any way. 93 // 94 // \param _Container The container which is observed. 95 // \param _Item The item type which is obserbved. 96 96 97 97 template <typename _Container, typename _Item> … … 104 104 typedef _Item Item; 105 105 106 // /\brief Exception which can be called from \e clear() and107 // /\e erase().108 // /109 // /From the \e clear() and \e erase() function only this110 // /exception is allowed to throw. The exception immediatly111 // /detaches the current observer from the notifier. Because the112 // /\e clear() and \e erase() should not throw other exceptions113 // /it can be used to invalidate the observer.106 // \brief Exception which can be called from \e clear() and 107 // \e erase(). 108 // 109 // From the \e clear() and \e erase() function only this 110 // exception is allowed to throw. The exception immediatly 111 // detaches the current observer from the notifier. Because the 112 // \e clear() and \e erase() should not throw other exceptions 113 // it can be used to invalidate the observer. 114 114 struct ImmediateDetach {}; 115 115 116 /// \brief ObserverBase is the base class for the observers. 117 /// 118 /// ObserverBase is the abstract base class for the observers. 119 /// It will be notified about an item was inserted into or 120 /// erased from the graph. 121 /// 122 /// The observer interface contains some pure virtual functions 123 /// to override. The add() and erase() functions are 124 /// to notify the oberver when one item is added or 125 /// erased. 126 /// 127 /// The build() and clear() members are to notify the observer 128 /// about the container is built from an empty container or 129 /// is cleared to an empty container. 130 116 // \brief ObserverBase is the base class for the observers. 117 // 118 // ObserverBase is the abstract base class for the observers. 119 // It will be notified about an item was inserted into or 120 // erased from the graph. 121 // 122 // The observer interface contains some pure virtual functions 123 // to override. The add() and erase() functions are 124 // to notify the oberver when one item is added or 125 // erased. 126 // 127 // The build() and clear() members are to notify the observer 128 // about the container is built from an empty container or 129 // is cleared to an empty container. 131 130 class ObserverBase { 132 131 protected: … … 135 134 friend class AlterationNotifier; 136 135 137 /// \brief Default constructor. 138 /// 139 /// Default constructor for ObserverBase. 140 /// 136 // \brief Default constructor. 137 // 138 // Default constructor for ObserverBase. 141 139 ObserverBase() : _notifier(0) {} 142 140 143 // /\brief Constructor which attach the observer into notifier.144 // /145 // /Constructor which attach the observer into notifier.141 // \brief Constructor which attach the observer into notifier. 142 // 143 // Constructor which attach the observer into notifier. 146 144 ObserverBase(AlterationNotifier& nf) { 147 145 attach(nf); 148 146 } 149 147 150 // /\brief Constructor which attach the obserever to the same notifier.151 // /152 // /Constructor which attach the obserever to the same notifier as153 // /the other observer is attached to.148 // \brief Constructor which attach the obserever to the same notifier. 149 // 150 // Constructor which attach the obserever to the same notifier as 151 // the other observer is attached to. 154 152 ObserverBase(const ObserverBase& copy) { 155 153 if (copy.attached()) { … … 158 156 } 159 157 160 // /\brief Destructor158 // \brief Destructor 161 159 virtual ~ObserverBase() { 162 160 if (attached()) { … … 165 163 } 166 164 167 /// \brief Attaches the observer into an AlterationNotifier. 168 /// 169 /// This member attaches the observer into an AlterationNotifier. 170 /// 165 // \brief Attaches the observer into an AlterationNotifier. 166 // 167 // This member attaches the observer into an AlterationNotifier. 171 168 void attach(AlterationNotifier& nf) { 172 169 nf.attach(*this); 173 170 } 174 171 175 /// \brief Detaches the observer into an AlterationNotifier. 176 /// 177 /// This member detaches the observer from an AlterationNotifier. 178 /// 172 // \brief Detaches the observer into an AlterationNotifier. 173 // 174 // This member detaches the observer from an AlterationNotifier. 179 175 void detach() { 180 176 _notifier->detach(*this); 181 177 } 182 178 183 /// \brief Gives back a pointer to the notifier which the map 184 /// attached into. 185 /// 186 /// This function gives back a pointer to the notifier which the map 187 /// attached into. 188 /// 179 // \brief Gives back a pointer to the notifier which the map 180 // attached into. 181 // 182 // This function gives back a pointer to the notifier which the map 183 // attached into. 189 184 Notifier* notifier() const { return const_cast<Notifier*>(_notifier); } 190 185 191 // /Gives back true when the observer is attached into a notifier.186 // Gives back true when the observer is attached into a notifier. 192 187 bool attached() const { return _notifier != 0; } 193 188 … … 201 196 typename std::list<ObserverBase*>::iterator _index; 202 197 203 // /\brief The member function to notificate the observer about an204 // /item is added to the container.205 // /206 // /The add() member function notificates the observer about an item207 // /is added to the container. It have to be overrided in the208 // /subclasses.198 // \brief The member function to notificate the observer about an 199 // item is added to the container. 200 // 201 // The add() member function notificates the observer about an item 202 // is added to the container. It have to be overrided in the 203 // subclasses. 209 204 virtual void add(const Item&) = 0; 210 205 211 // /\brief The member function to notificate the observer about212 // /more item is added to the container.213 // /214 // /The add() member function notificates the observer about more item215 // /is added to the container. It have to be overrided in the216 // /subclasses.206 // \brief The member function to notificate the observer about 207 // more item is added to the container. 208 // 209 // The add() member function notificates the observer about more item 210 // is added to the container. It have to be overrided in the 211 // subclasses. 217 212 virtual void add(const std::vector<Item>& items) = 0; 218 213 219 // /\brief The member function to notificate the observer about an220 // /item is erased from the container.221 // /222 // /The erase() member function notificates the observer about an223 // /item is erased from the container. It have to be overrided in224 // /the subclasses.214 // \brief The member function to notificate the observer about an 215 // item is erased from the container. 216 // 217 // The erase() member function notificates the observer about an 218 // item is erased from the container. It have to be overrided in 219 // the subclasses. 225 220 virtual void erase(const Item&) = 0; 226 221 227 // /\brief The member function to notificate the observer about228 // /more item is erased from the container.229 // /230 // /The erase() member function notificates the observer about more item231 // /is erased from the container. It have to be overrided in the232 // /subclasses.222 // \brief The member function to notificate the observer about 223 // more item is erased from the container. 224 // 225 // The erase() member function notificates the observer about more item 226 // is erased from the container. It have to be overrided in the 227 // subclasses. 233 228 virtual void erase(const std::vector<Item>& items) = 0; 234 229 235 /// \brief The member function to notificate the observer about the 236 /// container is built. 237 /// 238 /// The build() member function notificates the observer about the 239 /// container is built from an empty container. It have to be 240 /// overrided in the subclasses. 241 230 // \brief The member function to notificate the observer about the 231 // container is built. 232 // 233 // The build() member function notificates the observer about the 234 // container is built from an empty container. It have to be 235 // overrided in the subclasses. 242 236 virtual void build() = 0; 243 237 244 // /\brief The member function to notificate the observer about all245 // /items are erased from the container.246 // /247 // /The clear() member function notificates the observer about all248 // /items are erased from the container. It have to be overrided in249 // /the subclasses.238 // \brief The member function to notificate the observer about all 239 // items are erased from the container. 240 // 241 // The clear() member function notificates the observer about all 242 // items are erased from the container. It have to be overrided in 243 // the subclasses. 250 244 virtual void clear() = 0; 251 245 … … 262 256 public: 263 257 264 // /\brief Default constructor.265 // /266 // /The default constructor of the AlterationNotifier.267 // /It creates an empty notifier.258 // \brief Default constructor. 259 // 260 // The default constructor of the AlterationNotifier. 261 // It creates an empty notifier. 268 262 AlterationNotifier() 269 263 : container(0) {} 270 264 271 // /\brief Constructor.272 // /273 // /Constructor with the observed container parameter.265 // \brief Constructor. 266 // 267 // Constructor with the observed container parameter. 274 268 AlterationNotifier(const Container& _container) 275 269 : container(&_container) {} 276 270 277 // /\brief Copy Constructor of the AlterationNotifier.278 // /279 // /Copy constructor of the AlterationNotifier.280 // /It creates only an empty notifier because the copiable281 // /notifier's observers have to be registered still into that notifier.271 // \brief Copy Constructor of the AlterationNotifier. 272 // 273 // Copy constructor of the AlterationNotifier. 274 // It creates only an empty notifier because the copiable 275 // notifier's observers have to be registered still into that notifier. 282 276 AlterationNotifier(const AlterationNotifier& _notifier) 283 277 : container(_notifier.container) {} 284 278 285 /// \brief Destructor. 286 /// 287 /// Destructor of the AlterationNotifier. 288 /// 279 // \brief Destructor. 280 // 281 // Destructor of the AlterationNotifier. 289 282 ~AlterationNotifier() { 290 283 typename Observers::iterator it; … … 294 287 } 295 288 296 // /\brief Sets the container.297 // /298 // /Sets the container.289 // \brief Sets the container. 290 // 291 // Sets the container. 299 292 void setContainer(const Container& _container) { 300 293 container = &_container; … … 307 300 public: 308 301 309 310 311 /// \brief First item in the container. 312 /// 313 /// Returns the first item in the container. It is 314 /// for start the iteration on the container. 302 // \brief First item in the container. 303 // 304 // Returns the first item in the container. It is 305 // for start the iteration on the container. 315 306 void first(Item& item) const { 316 307 container->first(item); 317 308 } 318 309 319 // /\brief Next item in the container.320 // /321 // /Returns the next item in the container. It is322 // /for iterate on the container.310 // \brief Next item in the container. 311 // 312 // Returns the next item in the container. It is 313 // for iterate on the container. 323 314 void next(Item& item) const { 324 315 container->next(item); 325 316 } 326 317 327 // /\brief Returns the id of the item.328 // /329 // /Returns the id of the item provided by the container.318 // \brief Returns the id of the item. 319 // 320 // Returns the id of the item provided by the container. 330 321 int id(const Item& item) const { 331 322 return container->id(item); 332 323 } 333 324 334 // /\brief Returns the maximum id of the container.335 // /336 // /Returns the maximum id of the container.325 // \brief Returns the maximum id of the container. 326 // 327 // Returns the maximum id of the container. 337 328 int maxId() const { 338 329 return container->maxId(Item()); … … 354 345 public: 355 346 356 /// \brief Notifies all the registed observers about an item added to 357 /// the container. 358 /// 359 /// It notifies all the registed observers about an item added to 360 /// the container. 361 /// 347 // \brief Notifies all the registed observers about an item added to 348 // the container. 349 // 350 // It notifies all the registed observers about an item added to 351 // the container. 362 352 void add(const Item& item) { 363 353 typename Observers::reverse_iterator it; … … 375 365 } 376 366 377 /// \brief Notifies all the registed observers about more item added to 378 /// the container. 379 /// 380 /// It notifies all the registed observers about more item added to 381 /// the container. 382 /// 367 // \brief Notifies all the registed observers about more item added to 368 // the container. 369 // 370 // It notifies all the registed observers about more item added to 371 // the container. 383 372 void add(const std::vector<Item>& items) { 384 373 typename Observers::reverse_iterator it; … … 396 385 } 397 386 398 /// \brief Notifies all the registed observers about an item erased from 399 /// the container. 400 /// 401 /// It notifies all the registed observers about an item erased from 402 /// the container. 403 /// 387 // \brief Notifies all the registed observers about an item erased from 388 // the container. 389 // 390 // It notifies all the registed observers about an item erased from 391 // the container. 404 392 void erase(const Item& item) throw() { 405 393 typename Observers::iterator it = _observers.begin(); … … 416 404 } 417 405 418 /// \brief Notifies all the registed observers about more item erased 419 /// from the container. 420 /// 421 /// It notifies all the registed observers about more item erased from 422 /// the container. 423 /// 406 // \brief Notifies all the registed observers about more item erased 407 // from the container. 408 // 409 // It notifies all the registed observers about more item erased from 410 // the container. 424 411 void erase(const std::vector<Item>& items) { 425 412 typename Observers::iterator it = _observers.begin(); … … 436 423 } 437 424 438 // /\brief Notifies all the registed observers about the container is439 // /built.440 // /441 // /Notifies all the registed observers about the container is built442 // /from an empty container.425 // \brief Notifies all the registed observers about the container is 426 // built. 427 // 428 // Notifies all the registed observers about the container is built 429 // from an empty container. 443 430 void build() { 444 431 typename Observers::reverse_iterator it; … … 456 443 } 457 444 458 // /\brief Notifies all the registed observers about all items are459 // /erased.460 // /461 // /Notifies all the registed observers about all items are erased462 // /from the container.445 // \brief Notifies all the registed observers about all items are 446 // erased. 447 // 448 // Notifies all the registed observers about all items are erased 449 // from the container. 463 450 void clear() { 464 451 typename Observers::iterator it = _observers.begin();
Note: See TracChangeset
for help on using the changeset viewer.