COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/alteration_notifier.h @ 361:f58410582b9b

Last change on this file since 361:f58410582b9b was 361:f58410582b9b, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Doc improvements for the graph related tools in lemon/bits

File size: 15.2 KB
Line 
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-2008
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
31namespace 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      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      virtual ~ObserverBase() {
160        if (attached()) {
161          detach();
162        }
163      }
164
165      // \brief Attaches the observer into an AlterationNotifier.
166      //
167      // This member attaches the observer into an AlterationNotifier.
168      void attach(AlterationNotifier& nf) {
169        nf.attach(*this);
170      }
171
172      // \brief Detaches the observer into an AlterationNotifier.
173      //
174      // This member detaches the observer from an AlterationNotifier.
175      void detach() {
176        _notifier->detach(*this);
177      }
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      Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
185
186      // Gives back true when the observer is attached into a notifier.
187      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    AlterationNotifier()
263      : 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    ~AlterationNotifier() {
283      typename Observers::iterator it;
284      for (it = _observers.begin(); it != _observers.end(); ++it) {
285        (*it)->_notifier = 0;
286      }
287    }
288
289    // \brief Sets the container.
290    //
291    // Sets the container.
292    void setContainer(const Container& _container) {
293      container = &_container;
294    }
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    void first(Item& item) const {
307      container->first(item);
308    }
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    void next(Item& item) const {
315      container->next(item);
316    }
317
318    // \brief Returns the id of the item.
319    //
320    // Returns the id of the item provided by the container.
321    int id(const Item& item) const {
322      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    int maxId() const {
329      return container->maxId(Item());
330    }
331
332  protected:
333
334    void attach(ObserverBase& observer) {
335      observer._index = _observers.insert(_observers.begin(), &observer);
336      observer._notifier = this;
337    }
338
339    void detach(ObserverBase& observer) {
340      _observers.erase(observer._index);
341      observer._index = _observers.end();
342      observer._notifier = 0;
343    }
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    void add(const Item& item) {
353      typename Observers::reverse_iterator it;
354      try {
355        for (it = _observers.rbegin(); it != _observers.rend(); ++it) {
356          (*it)->add(item);
357        }
358      } catch (...) {
359        typename Observers::iterator jt;
360        for (jt = it.base(); jt != _observers.end(); ++jt) {
361          (*jt)->erase(item);
362        }
363        throw;
364      }
365    }
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    void erase(const Item& item) throw() {
393      typename Observers::iterator it = _observers.begin();
394      while (it != _observers.end()) {
395        try {
396          (*it)->erase(item);
397          ++it;
398        } catch (const ImmediateDetach&) {
399          (*it)->_index = _observers.end();
400          (*it)->_notifier = 0;
401          it = _observers.erase(it);
402        }
403      }
404    }
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    void clear() {
451      typename Observers::iterator it = _observers.begin();
452      while (it != _observers.end()) {
453        try {
454          (*it)->clear();
455          ++it;
456        } catch (const ImmediateDetach&) {
457          (*it)->_index = _observers.end();
458          (*it)->_notifier = 0;
459          it = _observers.erase(it);
460        }
461      }
462    }
463  };
464
465}
466
467#endif
Note: See TracBrowser for help on using the repository browser.