1 | /* -*- C++ -*- |
---|
2 | * |
---|
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). |
---|
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 | |
---|
19 | #ifndef LEMON_BITS_ALTERATION_NOTIFIER_H |
---|
20 | #define LEMON_BITS_ALTERATION_NOTIFIER_H |
---|
21 | |
---|
22 | #include <vector> |
---|
23 | |
---|
24 | #include <lemon/bits/utility.h> |
---|
25 | |
---|
26 | ///\ingroup graphbits |
---|
27 | ///\file |
---|
28 | ///\brief Observer notifier for graph alteration observers. |
---|
29 | |
---|
30 | namespace lemon { |
---|
31 | |
---|
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 another 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. The |
---|
70 | /// observer base can be attached to the notifier with the |
---|
71 | /// \e attach() member and can be detached with detach() function. The |
---|
72 | /// alteration handlers should not call any function which signals |
---|
73 | /// an other alteration in the same notifier and should not |
---|
74 | /// detach any observer from the notifier. |
---|
75 | /// |
---|
76 | /// Alteration observers try to be exception safe. If an \e add() or |
---|
77 | /// a \e clear() function throws an exception then the remaining |
---|
78 | /// observeres will not be notified and the fulfilled additions will |
---|
79 | /// be rolled back by calling the \e erase() or \e clear() |
---|
80 | /// functions. Thence the \e erase() and \e clear() should not throw |
---|
81 | /// exception. Actullay, it can be throw only |
---|
82 | /// \ref AlterationObserver::ImmediateDetach 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 | /// |
---|
97 | /// \author Balazs Dezso |
---|
98 | |
---|
99 | template <typename _Container, typename _Item> |
---|
100 | class AlterationNotifier { |
---|
101 | public: |
---|
102 | |
---|
103 | typedef True Notifier; |
---|
104 | |
---|
105 | typedef _Container Container; |
---|
106 | typedef _Item Item; |
---|
107 | |
---|
108 | /// \brief Exception which can be called from \e clear() and |
---|
109 | /// \e erase(). |
---|
110 | /// |
---|
111 | /// From the \e clear() and \e erase() function only this |
---|
112 | /// exception is allowed to throw. The exception immediatly |
---|
113 | /// detaches the current observer from the notifier. Because the |
---|
114 | /// \e clear() and \e erase() should not throw other exceptions |
---|
115 | /// it can be used to invalidate the observer. |
---|
116 | struct ImmediateDetach {}; |
---|
117 | |
---|
118 | /// \brief ObserverBase is the base class for the observers. |
---|
119 | /// |
---|
120 | /// ObserverBase is the abstract base class for the observers. |
---|
121 | /// It will be notified about an item was inserted into or |
---|
122 | /// erased from the graph. |
---|
123 | /// |
---|
124 | /// The observer interface contains some pure virtual functions |
---|
125 | /// to override. The add() and erase() functions are |
---|
126 | /// to notify the oberver when one item is added or |
---|
127 | /// erased. |
---|
128 | /// |
---|
129 | /// The build() and clear() members are to notify the observer |
---|
130 | /// about the container is built from an empty container or |
---|
131 | /// is cleared to an empty container. |
---|
132 | /// |
---|
133 | /// \author Balazs Dezso |
---|
134 | |
---|
135 | class ObserverBase { |
---|
136 | protected: |
---|
137 | typedef AlterationNotifier Notifier; |
---|
138 | |
---|
139 | friend class AlterationNotifier; |
---|
140 | |
---|
141 | /// \brief Default constructor. |
---|
142 | /// |
---|
143 | /// Default constructor for ObserverBase. |
---|
144 | /// |
---|
145 | ObserverBase() : notifier(0) {} |
---|
146 | |
---|
147 | /// \brief Constructor which attach the observer into notifier. |
---|
148 | /// |
---|
149 | /// Constructor which attach the observer into notifier. |
---|
150 | ObserverBase(AlterationNotifier& _notifier) { |
---|
151 | attach(_notifier); |
---|
152 | } |
---|
153 | |
---|
154 | /// \brief Constructor which attach the obserever to the same notifier. |
---|
155 | /// |
---|
156 | /// Constructor which attach the obserever to the same notifier as |
---|
157 | /// the other observer is attached to. |
---|
158 | ObserverBase(const ObserverBase& copy) { |
---|
159 | if (copy.attached()) { |
---|
160 | attach(*copy.getNotifier()); |
---|
161 | } |
---|
162 | } |
---|
163 | |
---|
164 | /// \brief Destructor |
---|
165 | virtual ~ObserverBase() { |
---|
166 | if (attached()) { |
---|
167 | detach(); |
---|
168 | } |
---|
169 | } |
---|
170 | |
---|
171 | /// \brief Attaches the observer into an AlterationNotifier. |
---|
172 | /// |
---|
173 | /// This member attaches the observer into an AlterationNotifier. |
---|
174 | /// |
---|
175 | void attach(AlterationNotifier& _notifier) { |
---|
176 | notifier = &_notifier; |
---|
177 | notifier->attach(*this); |
---|
178 | } |
---|
179 | |
---|
180 | /// \brief Detaches the observer into an AlterationNotifier. |
---|
181 | /// |
---|
182 | /// This member detaches the observer from an AlterationNotifier. |
---|
183 | /// |
---|
184 | void detach() { |
---|
185 | notifier->detach(*this); |
---|
186 | } |
---|
187 | |
---|
188 | /// \brief Gives back a pointer to the notifier which the map |
---|
189 | /// attached into. |
---|
190 | /// |
---|
191 | /// This function gives back a pointer to the notifier which the map |
---|
192 | /// attached into. |
---|
193 | /// |
---|
194 | Notifier* getNotifier() const { return const_cast<Notifier*>(notifier); } |
---|
195 | |
---|
196 | /// Gives back true when the observer is attached into a notifier. |
---|
197 | bool attached() const { return notifier != 0; } |
---|
198 | |
---|
199 | private: |
---|
200 | |
---|
201 | ObserverBase& operator=(const ObserverBase& copy); |
---|
202 | |
---|
203 | protected: |
---|
204 | |
---|
205 | Notifier* notifier; |
---|
206 | int notifier_index; |
---|
207 | |
---|
208 | /// \brief The member function to notificate the observer about an |
---|
209 | /// item is added to the container. |
---|
210 | /// |
---|
211 | /// The add() member function notificates the observer about an item |
---|
212 | /// is added to the container. It have to be overrided in the |
---|
213 | /// subclasses. |
---|
214 | |
---|
215 | virtual void add(const Item&) = 0; |
---|
216 | |
---|
217 | /// \brief The member function to notificate the observer about |
---|
218 | /// more item is added to the container. |
---|
219 | /// |
---|
220 | /// The add() member function notificates the observer about more item |
---|
221 | /// is added to the container. It have to be overrided in the |
---|
222 | /// subclasses. |
---|
223 | |
---|
224 | virtual void add(const std::vector<Item>& items) { |
---|
225 | int i; |
---|
226 | try { |
---|
227 | for (i = 0; i < (int)items.size(); ++i) { |
---|
228 | add(items[i]); |
---|
229 | } |
---|
230 | } catch (...) { |
---|
231 | for (int j = 0; j < i; ++j) { |
---|
232 | add(items[j]); |
---|
233 | } |
---|
234 | throw; |
---|
235 | } |
---|
236 | } |
---|
237 | |
---|
238 | /// \brief The member function to notificate the observer about an |
---|
239 | /// item is erased from the container. |
---|
240 | /// |
---|
241 | /// The erase() member function notificates the observer about an |
---|
242 | /// item is erased from the container. It have to be overrided in |
---|
243 | /// the subclasses. |
---|
244 | |
---|
245 | virtual void erase(const Item&) = 0; |
---|
246 | |
---|
247 | /// \brief The member function to notificate the observer about |
---|
248 | /// more item is erased from the container. |
---|
249 | /// |
---|
250 | /// The erase() member function notificates the observer about more item |
---|
251 | /// is erased from the container. It have to be overrided in the |
---|
252 | /// subclasses. |
---|
253 | virtual void erase(const std::vector<Item>& items) { |
---|
254 | for (int i = 0; i < (int)items.size(); ++i) { |
---|
255 | erase(items[i]); |
---|
256 | } |
---|
257 | } |
---|
258 | |
---|
259 | /// \brief The member function to notificate the observer about the |
---|
260 | /// container is built. |
---|
261 | /// |
---|
262 | /// The build() member function notificates the observer about the |
---|
263 | /// container is built from an empty container. It have to be |
---|
264 | /// overrided in the subclasses. |
---|
265 | |
---|
266 | virtual void build() { |
---|
267 | Item it; |
---|
268 | try { |
---|
269 | for (notifier->first(it); it != INVALID; notifier->next(it)) { |
---|
270 | add(it); |
---|
271 | } |
---|
272 | } catch (...) { |
---|
273 | Item jt; |
---|
274 | for (notifier->first(jt); jt != it; notifier->next(jt)) { |
---|
275 | erase(jt); |
---|
276 | } |
---|
277 | throw; |
---|
278 | } |
---|
279 | } |
---|
280 | |
---|
281 | /// \brief The member function to notificate the observer about all |
---|
282 | /// items are erased from the container. |
---|
283 | /// |
---|
284 | /// The clear() member function notificates the observer about all |
---|
285 | /// items are erased from the container. It have to be overrided in |
---|
286 | /// the subclasses. |
---|
287 | virtual void clear() { |
---|
288 | Item it; |
---|
289 | for (notifier->first(it); it != INVALID; notifier->next(it)) { |
---|
290 | erase(it); |
---|
291 | } |
---|
292 | } |
---|
293 | |
---|
294 | }; |
---|
295 | |
---|
296 | protected: |
---|
297 | |
---|
298 | const Container* container; |
---|
299 | |
---|
300 | typedef std::vector<ObserverBase*> Observers; |
---|
301 | Observers observers; |
---|
302 | |
---|
303 | |
---|
304 | public: |
---|
305 | |
---|
306 | /// \brief Default constructor. |
---|
307 | /// |
---|
308 | /// The default constructor of the AlterationNotifier. |
---|
309 | /// It creates an empty notifier. |
---|
310 | AlterationNotifier() |
---|
311 | : container(0) {} |
---|
312 | |
---|
313 | /// \brief Constructor. |
---|
314 | /// |
---|
315 | /// Constructor with the observed container parameter. |
---|
316 | AlterationNotifier(const Container& _container) |
---|
317 | : container(&_container) {} |
---|
318 | |
---|
319 | /// \brief Copy Constructor of the AlterationNotifier. |
---|
320 | /// |
---|
321 | /// Copy constructor of the AlterationNotifier. |
---|
322 | /// It creates only an empty notifier because the copiable |
---|
323 | /// notifier's observers have to be registered still into that notifier. |
---|
324 | AlterationNotifier(const AlterationNotifier& _notifier) |
---|
325 | : container(_notifier.container) {} |
---|
326 | |
---|
327 | /// \brief Destructor. |
---|
328 | /// |
---|
329 | /// Destructor of the AlterationNotifier. |
---|
330 | /// |
---|
331 | ~AlterationNotifier() { |
---|
332 | typename Observers::iterator it; |
---|
333 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
334 | (*it)->notifier = 0; |
---|
335 | } |
---|
336 | } |
---|
337 | |
---|
338 | /// \brief Sets the container. |
---|
339 | /// |
---|
340 | /// Sets the container. |
---|
341 | void setContainer(const Container& _container) { |
---|
342 | container = &_container; |
---|
343 | } |
---|
344 | |
---|
345 | protected: |
---|
346 | |
---|
347 | AlterationNotifier& operator=(const AlterationNotifier&); |
---|
348 | |
---|
349 | public: |
---|
350 | |
---|
351 | |
---|
352 | |
---|
353 | /// \brief First item in the container. |
---|
354 | /// |
---|
355 | /// Returns the first item in the container. It is |
---|
356 | /// for start the iteration on the container. |
---|
357 | void first(Item& item) const { |
---|
358 | container->first(item); |
---|
359 | } |
---|
360 | |
---|
361 | /// \brief Next item in the container. |
---|
362 | /// |
---|
363 | /// Returns the next item in the container. It is |
---|
364 | /// for iterate on the container. |
---|
365 | void next(Item& item) const { |
---|
366 | container->next(item); |
---|
367 | } |
---|
368 | |
---|
369 | /// \brief Returns the id of the item. |
---|
370 | /// |
---|
371 | /// Returns the id of the item provided by the container. |
---|
372 | int id(const Item& item) const { |
---|
373 | return container->id(item); |
---|
374 | } |
---|
375 | |
---|
376 | /// \brief Returns the maximum id of the container. |
---|
377 | /// |
---|
378 | /// Returns the maximum id of the container. |
---|
379 | int maxId() const { |
---|
380 | return container->maxId(Item()); |
---|
381 | } |
---|
382 | |
---|
383 | protected: |
---|
384 | |
---|
385 | void attach(ObserverBase& observer) { |
---|
386 | observers.push_back(&observer); |
---|
387 | observer.notifier = this; |
---|
388 | observer.notifier_index = observers.size() - 1; |
---|
389 | } |
---|
390 | |
---|
391 | void detach(ObserverBase& observer) { |
---|
392 | observers.back()->notifier_index = observer.notifier_index; |
---|
393 | observers[observer.notifier_index] = observers.back(); |
---|
394 | observers.pop_back(); |
---|
395 | observer.notifier = 0; |
---|
396 | } |
---|
397 | |
---|
398 | public: |
---|
399 | |
---|
400 | /// \brief Notifies all the registed observers about an item added to |
---|
401 | /// the container. |
---|
402 | /// |
---|
403 | /// It notifies all the registed observers about an item added to |
---|
404 | /// the container. |
---|
405 | /// |
---|
406 | void add(const Item& item) { |
---|
407 | typename Observers::iterator it; |
---|
408 | try { |
---|
409 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
410 | (*it)->add(item); |
---|
411 | } |
---|
412 | } catch (...) { |
---|
413 | typename Observers::iterator jt; |
---|
414 | for (jt = observers.begin(); jt != it; ++jt) { |
---|
415 | (*it)->erase(item); |
---|
416 | } |
---|
417 | throw; |
---|
418 | } |
---|
419 | } |
---|
420 | |
---|
421 | /// \brief Notifies all the registed observers about more item added to |
---|
422 | /// the container. |
---|
423 | /// |
---|
424 | /// It notifies all the registed observers about more item added to |
---|
425 | /// the container. |
---|
426 | /// |
---|
427 | void add(const std::vector<Item>& items) { |
---|
428 | typename Observers::iterator it; |
---|
429 | try { |
---|
430 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
431 | (*it)->add(items); |
---|
432 | } |
---|
433 | } catch (...) { |
---|
434 | typename Observers::iterator jt; |
---|
435 | for (jt = observers.begin(); jt != it; ++jt) { |
---|
436 | (*it)->erase(items); |
---|
437 | } |
---|
438 | throw; |
---|
439 | } |
---|
440 | } |
---|
441 | |
---|
442 | /// \brief Notifies all the registed observers about an item erased from |
---|
443 | /// the container. |
---|
444 | /// |
---|
445 | /// It notifies all the registed observers about an item erased from |
---|
446 | /// the container. |
---|
447 | /// |
---|
448 | void erase(const Item& key) throw() { |
---|
449 | int i = 0; |
---|
450 | while (i != (int)observers.size()) { |
---|
451 | try { |
---|
452 | observers[i]->erase(key); |
---|
453 | ++i; |
---|
454 | } catch (const ImmediateDetach&) { |
---|
455 | observers[i]->detach(); |
---|
456 | } |
---|
457 | } |
---|
458 | } |
---|
459 | |
---|
460 | /// \brief Notifies all the registed observers about more item erased |
---|
461 | /// from the container. |
---|
462 | /// |
---|
463 | /// It notifies all the registed observers about more item erased from |
---|
464 | /// the container. |
---|
465 | /// |
---|
466 | void erase(const std::vector<Item>& items) { |
---|
467 | int i = 0; |
---|
468 | while (i != (int)observers.size()) { |
---|
469 | try { |
---|
470 | observers[i]->erase(items); |
---|
471 | ++i; |
---|
472 | } catch (const ImmediateDetach&) { |
---|
473 | observers[i]->detach(); |
---|
474 | } |
---|
475 | } |
---|
476 | } |
---|
477 | |
---|
478 | /// \brief Notifies all the registed observers about the container is |
---|
479 | /// built. |
---|
480 | /// |
---|
481 | /// Notifies all the registed observers about the container is built |
---|
482 | /// from an empty container. |
---|
483 | void build() { |
---|
484 | typename Observers::iterator it; |
---|
485 | try { |
---|
486 | for (it = observers.begin(); it != observers.end(); ++it) { |
---|
487 | (*it)->build(); |
---|
488 | } |
---|
489 | } catch (...) { |
---|
490 | typename Observers::iterator jt; |
---|
491 | for (jt = observers.begin(); jt != it; ++jt) { |
---|
492 | (*it)->clear(); |
---|
493 | } |
---|
494 | throw; |
---|
495 | } |
---|
496 | } |
---|
497 | |
---|
498 | /// \brief Notifies all the registed observers about all items are |
---|
499 | /// erased. |
---|
500 | /// |
---|
501 | /// Notifies all the registed observers about all items are erased |
---|
502 | /// from the container. |
---|
503 | void clear() { |
---|
504 | int i = 0; |
---|
505 | while (i != (int)observers.size()) { |
---|
506 | try { |
---|
507 | observers[i]->clear(); |
---|
508 | ++i; |
---|
509 | } catch (const ImmediateDetach&) { |
---|
510 | observers[i]->detach(); |
---|
511 | } |
---|
512 | } |
---|
513 | } |
---|
514 | }; |
---|
515 | |
---|
516 | } |
---|
517 | |
---|
518 | #endif |
---|