COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/bits/alteration_notifier.h @ 322:8c4d380787cf

Last change on this file since 322:8c4d380787cf was 318:2cc60866a0c9, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Doc reorganization + improvements

  • Reorganize several tools (move them to other modules).
  • Add new module for map concepts.
  • Remove the doc of all tools in lemon/bits.
  • Improvements in groups.dox.
  • Fix some doxygen warnings.
File size: 15.3 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 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
97  template <typename _Container, typename _Item>
98  class AlterationNotifier {
99  public:
100
101    typedef True Notifier;
102
103    typedef _Container Container;
104    typedef _Item Item;
105
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    struct ImmediateDetach {};
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    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.