COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/alteration_notifier.h @ 2254:50cb2b90daa9

Last change on this file since 2254:50cb2b90daa9 was 2188:984870a2dde4, checked in by Balazs Dezso, 13 years ago

Improvment in exception handling
The erase and clear handlers have to be exception safe.
These can throw only one exception which detach the observer
from the notifier

File size: 16.2 KB
Line 
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
30namespace 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
Note: See TracBrowser for help on using the repository browser.