Branch data Line data Source code
1 : : /* -*- mode: C++; indent-tabs-mode: nil; -*-
2 : : *
3 : : * This file is a part of LEMON, a generic C++ optimization library.
4 : : *
5 : : * Copyright (C) 2003-2009
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 : : #include <list>
24 : :
25 : : #include <lemon/core.h>
26 : :
27 : : //\ingroup graphbits
28 : : //\file
29 : : //\brief Observer notifier for graph alteration observers.
30 : :
31 : : namespace lemon {
32 : :
33 : : // \ingroup graphbits
34 : : //
35 : : // \brief Notifier class to notify observes about alterations in
36 : : // a container.
37 : : //
38 : : // The simple graphs can be refered as two containers: a node container
39 : : // and an edge container. But they do not store values directly, they
40 : : // are just key continars for more value containers, which are the
41 : : // node and edge maps.
42 : : //
43 : : // The node and edge sets of the graphs 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 a node or edge container.
53 : : // The first() and next() member functions make possible
54 : : // to iterate on the keys of the container.
55 : : // The id() function returns an integer id for each key.
56 : : // The maxId() function gives back an upper bound of the ids.
57 : : //
58 : : // For the proper functonality of this class, we should notify it
59 : : // about each alteration in the container. The alterations have four type:
60 : : // add(), erase(), build() and clear(). The add() and
61 : : // erase() signal that only one or few items added or erased to or
62 : : // from the graph. If all items are erased from the graph or if a new graph
63 : : // is built from an empty graph, then it can be signaled with the
64 : : // clear() and build() members. Important rule that if we erase items
65 : : // from graphs we should first signal the alteration and after that erase
66 : : // them from the container, on the other way on item addition we should
67 : : // first extend the container and just after that signal the alteration.
68 : : //
69 : : // The alteration can be observed with a class inherited from the
70 : : // ObserverBase nested class. The signals can be handled with
71 : : // overriding the virtual functions defined in the base class. The
72 : : // observer base can be attached to the notifier with the
73 : : // attach() member and can be detached with detach() function. The
74 : : // alteration handlers should not call any function which signals
75 : : // an other alteration in the same notifier and should not
76 : : // detach any observer from the notifier.
77 : : //
78 : : // Alteration observers try to be exception safe. If an add() or
79 : : // a clear() function throws an exception then the remaining
80 : : // observeres will not be notified and the fulfilled additions will
81 : : // be rolled back by calling the erase() or clear() functions.
82 : : // Hence erase() and clear() should not throw exception.
83 : : // Actullay, they can throw only \ref ImmediateDetach exception,
84 : : // which detach the observer from the notifier.
85 : : //
86 : : // There are some cases, when the alteration observing is not completly
87 : : // reliable. If we want to carry out the node degree in the graph
88 : : // as in the \ref InDegMap and we use the reverseArc(), then it cause
89 : : // unreliable functionality. Because the alteration observing signals
90 : : // only erasing and adding but not the reversing, it will stores bad
91 : : // degrees. Apart form that the subgraph adaptors cannot even signal
92 : : // the alterations because just a setting in the filter map can modify
93 : : // the graph and this cannot be watched in any way.
94 : : //
95 : : // \param _Container The container which is observed.
96 : : // \param _Item The item type which is obserbved.
97 : :
98 : : template <typename _Container, typename _Item>
99 : : class AlterationNotifier {
100 : : public:
101 : :
102 : : typedef True Notifier;
103 : :
104 : : typedef _Container Container;
105 : : typedef _Item Item;
106 : :
107 : : // \brief Exception which can be called from clear() and
108 : : // erase().
109 : : //
110 : : // From the clear() and erase() function only this
111 : : // exception is allowed to throw. The exception immediatly
112 : : // detaches the current observer from the notifier. Because the
113 : : // clear() and erase() should not throw other exceptions
114 : : // it can be used to invalidate the observer.
115 : : struct ImmediateDetach {};
116 : :
117 : : // \brief ObserverBase is the base class for the observers.
118 : : //
119 : : // ObserverBase is the abstract base class for the observers.
120 : : // It will be notified about an item was inserted into or
121 : : // erased from the graph.
122 : : //
123 : : // The observer interface contains some pure virtual functions
124 : : // to override. The add() and erase() functions are
125 : : // to notify the oberver when one item is added or 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 : : class ObserverBase {
131 : : protected:
132 : : typedef AlterationNotifier Notifier;
133 : :
134 : : friend class AlterationNotifier;
135 : :
136 : : // \brief Default constructor.
137 : : //
138 : : // Default constructor for ObserverBase.
139 : 1966 : ObserverBase() : _notifier(0) {}
140 : :
141 : : // \brief Constructor which attach the observer into notifier.
142 : : //
143 : : // Constructor which attach the observer into notifier.
144 : : ObserverBase(AlterationNotifier& nf) {
145 : : attach(nf);
146 : : }
147 : :
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.
152 : : ObserverBase(const ObserverBase& copy) {
153 : : if (copy.attached()) {
154 : : attach(*copy.notifier());
155 : : }
156 : : }
157 : :
158 : : // \brief Destructor
159 : 966 : virtual ~ObserverBase() {
160 [ # # ][ + + ]: 966 : if (attached()) {
161 : 610 : detach();
162 : : }
163 [ # # ][ - + ]: 966 : }
164 : :
165 : : // \brief Attaches the observer into an AlterationNotifier.
166 : : //
167 : : // This member attaches the observer into an AlterationNotifier.
168 : 983 : void attach(AlterationNotifier& nf) {
169 : 983 : nf.attach(*this);
170 : 983 : }
171 : :
172 : : // \brief Detaches the observer into an AlterationNotifier.
173 : : //
174 : : // This member detaches the observer from an AlterationNotifier.
175 : 966 : void detach() {
176 : 966 : _notifier->detach(*this);
177 : 966 : }
178 : :
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.
184 : 53618 : Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
185 : :
186 : : // Gives back true when the observer is attached into a notifier.
187 : 2644 : bool attached() const { return _notifier != 0; }
188 : :
189 : : private:
190 : :
191 : : ObserverBase& operator=(const ObserverBase& copy);
192 : :
193 : : protected:
194 : :
195 : : Notifier* _notifier;
196 : : typename std::list<ObserverBase*>::iterator _index;
197 : :
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.
204 : : virtual void add(const Item&) = 0;
205 : :
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.
212 : : virtual void add(const std::vector<Item>& items) = 0;
213 : :
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.
220 : : virtual void erase(const Item&) = 0;
221 : :
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.
228 : : virtual void erase(const std::vector<Item>& items) = 0;
229 : :
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.
236 : : virtual void build() = 0;
237 : :
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.
244 : : virtual void clear() = 0;
245 : :
246 : : };
247 : :
248 : : protected:
249 : :
250 : : const Container* container;
251 : :
252 : : typedef std::list<ObserverBase*> Observers;
253 : : Observers _observers;
254 : :
255 : :
256 : : public:
257 : :
258 : : // \brief Default constructor.
259 : : //
260 : : // The default constructor of the AlterationNotifier.
261 : : // It creates an empty notifier.
262 : 76 : AlterationNotifier()
263 : 76 : : container(0) {}
264 : :
265 : : // \brief Constructor.
266 : : //
267 : : // Constructor with the observed container parameter.
268 : : AlterationNotifier(const Container& _container)
269 : : : container(&_container) {}
270 : :
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.
276 : : AlterationNotifier(const AlterationNotifier& _notifier)
277 : : : container(_notifier.container) {}
278 : :
279 : : // \brief Destructor.
280 : : //
281 : : // Destructor of the AlterationNotifier.
282 : 42 : ~AlterationNotifier() {
283 : 42 : typename Observers::iterator it;
284 [ - + ][ - + ]: 42 : for (it = _observers.begin(); it != _observers.end(); ++it) {
285 : 0 : (*it)->_notifier = 0;
286 : : }
287 : 42 : }
288 : :
289 : : // \brief Sets the container.
290 : : //
291 : : // Sets the container.
292 : 76 : void setContainer(const Container& _container) {
293 : 76 : container = &_container;
294 : 76 : }
295 : :
296 : : protected:
297 : :
298 : : AlterationNotifier& operator=(const AlterationNotifier&);
299 : :
300 : : public:
301 : :
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.
306 : 730 : void first(Item& item) const {
307 : 730 : container->first(item);
308 : 730 : }
309 : :
310 : : // \brief Next item in the container.
311 : : //
312 : : // Returns the next item in the container. It is
313 : : // for iterate on the container.
314 : 4741 : void next(Item& item) const {
315 : 4741 : container->next(item);
316 : 4741 : }
317 : :
318 : : // \brief Returns the id of the item.
319 : : //
320 : : // Returns the id of the item provided by the container.
321 : 29855 : int id(const Item& item) const {
322 : 29855 : return container->id(item);
323 : : }
324 : :
325 : : // \brief Returns the maximum id of the container.
326 : : //
327 : : // Returns the maximum id of the container.
328 : 983 : int maxId() const {
329 [ # # ][ + - ]: 983 : return container->maxId(Item());
330 : : }
331 : :
332 : : protected:
333 : :
334 : 983 : void attach(ObserverBase& observer) {
335 [ # # ][ + - ]: 983 : observer._index = _observers.insert(_observers.begin(), &observer);
336 : 983 : observer._notifier = this;
337 : 983 : }
338 : :
339 : 966 : void detach(ObserverBase& observer) {
340 : 966 : _observers.erase(observer._index);
341 : 966 : observer._index = _observers.end();
342 : 966 : observer._notifier = 0;
343 : 966 : }
344 : :
345 : : public:
346 : :
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.
352 : 894 : void add(const Item& item) {
353 [ + - ][ + - ]: 894 : typename Observers::reverse_iterator it;
354 : : try {
355 [ # # ][ + - ]: 1466 : for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
[ - + ][ + - ]
[ + - ][ + + ]
356 [ # # ][ # # ]: 572 : (*it)->add(item);
[ + - ][ + - ]
357 : : }
358 : 0 : } catch (...) {
359 [ # # # # ]: 0 : typename Observers::iterator jt;
360 [ # # # # : 0 : for (jt = it.base(); jt != _observers.end(); ++jt) {
# # # # #
# # # # #
# # ]
361 [ # # # # : 0 : (*jt)->erase(item);
# # # # ]
362 : : }
363 : 0 : throw;
364 : : }
365 : 894 : }
366 : :
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.
372 : : void add(const std::vector<Item>& items) {
373 : : typename Observers::reverse_iterator it;
374 : : try {
375 : : for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
376 : : (*it)->add(items);
377 : : }
378 : : } catch (...) {
379 : : typename Observers::iterator jt;
380 : : for (jt = it.base(); jt != _observers.end(); ++jt) {
381 : : (*jt)->erase(items);
382 : : }
383 : : throw;
384 : : }
385 : : }
386 : :
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.
392 : 792 : void erase(const Item& item) throw() {
393 : 792 : typename Observers::iterator it = _observers.begin();
394 [ + - ]: 951 : while (it != _observers.end()) {
[ - + # # ]
[ + - ]
[ + + # # ]
395 : : try {
396 [ # # ][ # # ]: 159 : (*it)->erase(item);
[ + - ][ + - ]
397 [ # # ][ + - ]: 159 : ++it;
398 [ # # # # ]: 0 : } catch (const ImmediateDetach&) {
399 [ # # # # ]: 0 : (*it)->_index = _observers.end();
400 [ # # # # ]: 0 : (*it)->_notifier = 0;
401 [ # # # # ]: 0 : it = _observers.erase(it);
402 : : }
403 : : }
404 : 792 : }
405 : :
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.
411 : : void erase(const std::vector<Item>& items) {
412 : : typename Observers::iterator it = _observers.begin();
413 : : while (it != _observers.end()) {
414 : : try {
415 : : (*it)->erase(items);
416 : : ++it;
417 : : } catch (const ImmediateDetach&) {
418 : : (*it)->_index = _observers.end();
419 : : (*it)->_notifier = 0;
420 : : it = _observers.erase(it);
421 : : }
422 : : }
423 : : }
424 : :
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.
430 : : void build() {
431 : : typename Observers::reverse_iterator it;
432 : : try {
433 : : for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
434 : : (*it)->build();
435 : : }
436 : : } catch (...) {
437 : : typename Observers::iterator jt;
438 : : for (jt = it.base(); jt != _observers.end(); ++jt) {
439 : : (*jt)->clear();
440 : : }
441 : : throw;
442 : : }
443 : : }
444 : :
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.
450 : 42 : void clear() {
451 : 42 : typename Observers::iterator it = _observers.begin();
452 [ + - ][ - + ]: 42 : while (it != _observers.end()) {
[ + - ][ - + ]
453 : : try {
454 [ # # ][ # # ]: 0 : (*it)->clear();
[ # # ][ # # ]
455 [ # # ][ # # ]: 0 : ++it;
456 [ # # # # ]: 0 : } catch (const ImmediateDetach&) {
457 [ # # # # ]: 0 : (*it)->_index = _observers.end();
458 [ # # # # ]: 0 : (*it)->_notifier = 0;
459 [ # # # # ]: 0 : it = _observers.erase(it);
460 : : }
461 : : }
462 : 42 : }
463 : : };
464 : :
465 : : }
466 : :
467 : : #endif
|
