COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/alteration_notifier.h @ 535:6a17a722b50e

Last change on this file since 535:6a17a722b50e was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 15 years ago

Happy New Year again

  • update the copyright headers + run the source unifier
File size: 15.2 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[57]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[57]4 *
[440]5 * Copyright (C) 2003-2009
[57]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
[220]25#include <lemon/core.h>
[57]26
[314]27//\ingroup graphbits
28//\file
29//\brief Observer notifier for graph alteration observers.
[57]30
31namespace lemon {
32
[314]33  // \ingroup graphbits
34  //
35  // \brief Notifier class to notify observes about alterations in
36  // a container.
37  //
[361]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.
[314]42  //
[361]43  // The node and edge sets of the graphs can be changed as we add or erase
[314]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
[361]48  // in the library. We use another solution: we notify all maps about
[314]49  // an alteration in the graph, which cause only drawback on the
50  // alteration of the graph.
51  //
[361]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.
[314]57  //
58  // For the proper functonality of this class, we should notify it
[361]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
[314]64  // clear() and build() members. Important rule that if we erase items
[361]65  // from graphs we should first signal the alteration and after that erase
[314]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
[361]70  // ObserverBase nested class. The signals can be handled with
[314]71  // overriding the virtual functions defined in the base class.  The
72  // observer base can be attached to the notifier with the
[361]73  // attach() member and can be detached with detach() function. The
[314]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  //
[361]78  // Alteration observers try to be exception safe. If an add() or
79  // a clear() function throws an exception then the remaining
[314]80  // observeres will not be notified and the fulfilled additions will
[361]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.
[314]85  //
[361]86  // There are some cases, when the alteration observing is not completly
[314]87  // reliable. If we want to carry out the node degree in the graph
[361]88  // as in the \ref InDegMap and we use the reverseArc(), then it cause
[314]89  // unreliable functionality. Because the alteration observing signals
[361]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.
[314]94  //
95  // \param _Container The container which is observed.
96  // \param _Item The item type which is obserbved.
[57]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
[361]107    // \brief Exception which can be called from clear() and
108    // erase().
[314]109    //
[361]110    // From the clear() and erase() function only this
[314]111    // exception is allowed to throw. The exception immediatly
112    // detaches the current observer from the notifier. Because the
[361]113    // clear() and erase() should not throw other exceptions
[314]114    // it can be used to invalidate the observer.
[57]115    struct ImmediateDetach {};
116
[314]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
[361]125    // to notify the oberver when one item is added or erased.
[314]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.
[57]130    class ObserverBase {
131    protected:
132      typedef AlterationNotifier Notifier;
133
134      friend class AlterationNotifier;
135
[314]136      // \brief Default constructor.
137      //
138      // Default constructor for ObserverBase.
[57]139      ObserverBase() : _notifier(0) {}
140
[314]141      // \brief Constructor which attach the observer into notifier.
142      //
143      // Constructor which attach the observer into notifier.
[57]144      ObserverBase(AlterationNotifier& nf) {
145        attach(nf);
146      }
147
[314]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.
[57]152      ObserverBase(const ObserverBase& copy) {
[209]153        if (copy.attached()) {
[57]154          attach(*copy.notifier());
[209]155        }
[57]156      }
[209]157
[314]158      // \brief Destructor
[57]159      virtual ~ObserverBase() {
160        if (attached()) {
161          detach();
162        }
163      }
164
[314]165      // \brief Attaches the observer into an AlterationNotifier.
166      //
167      // This member attaches the observer into an AlterationNotifier.
[57]168      void attach(AlterationNotifier& nf) {
[209]169        nf.attach(*this);
[57]170      }
[209]171
[314]172      // \brief Detaches the observer into an AlterationNotifier.
173      //
174      // This member detaches the observer from an AlterationNotifier.
[57]175      void detach() {
176        _notifier->detach(*this);
177      }
[209]178
[314]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.
[57]184      Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
[209]185
[314]186      // Gives back true when the observer is attached into a notifier.
[57]187      bool attached() const { return _notifier != 0; }
188
189    private:
190
191      ObserverBase& operator=(const ObserverBase& copy);
192
193    protected:
[209]194
[57]195      Notifier* _notifier;
196      typename std::list<ObserverBase*>::iterator _index;
197
[314]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.
[57]204      virtual void add(const Item&) = 0;
205
[314]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.
[57]212      virtual void add(const std::vector<Item>& items) = 0;
213
[314]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.
[57]220      virtual void erase(const Item&) = 0;
221
[314]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.
[57]228      virtual void erase(const std::vector<Item>& items) = 0;
229
[314]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.
[57]236      virtual void build() = 0;
237
[314]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.
[57]244      virtual void clear() = 0;
245
246    };
[209]247
[57]248  protected:
249
250    const Container* container;
251
[209]252    typedef std::list<ObserverBase*> Observers;
[57]253    Observers _observers;
254
[209]255
[57]256  public:
257
[314]258    // \brief Default constructor.
259    //
260    // The default constructor of the AlterationNotifier.
261    // It creates an empty notifier.
[209]262    AlterationNotifier()
[57]263      : container(0) {}
264
[314]265    // \brief Constructor.
266    //
267    // Constructor with the observed container parameter.
[209]268    AlterationNotifier(const Container& _container)
[57]269      : container(&_container) {}
270
[314]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.
[209]276    AlterationNotifier(const AlterationNotifier& _notifier)
[57]277      : container(_notifier.container) {}
278
[314]279    // \brief Destructor.
280    //
281    // Destructor of the AlterationNotifier.
[57]282    ~AlterationNotifier() {
283      typename Observers::iterator it;
284      for (it = _observers.begin(); it != _observers.end(); ++it) {
[209]285        (*it)->_notifier = 0;
[57]286      }
287    }
288
[314]289    // \brief Sets the container.
290    //
291    // Sets the container.
[57]292    void setContainer(const Container& _container) {
293      container = &_container;
294    }
295
296  protected:
297
298    AlterationNotifier& operator=(const AlterationNotifier&);
299
300  public:
301
[314]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.
[57]306    void first(Item& item) const {
307      container->first(item);
308    }
309
[314]310    // \brief Next item in the container.
311    //
312    // Returns the next item in the container. It is
313    // for iterate on the container.
[57]314    void next(Item& item) const {
315      container->next(item);
316    }
317
[314]318    // \brief Returns the id of the item.
319    //
320    // Returns the id of the item provided by the container.
[57]321    int id(const Item& item) const {
322      return container->id(item);
323    }
324
[314]325    // \brief Returns the maximum id of the container.
326    //
327    // Returns the maximum id of the container.
[57]328    int maxId() const {
329      return container->maxId(Item());
330    }
[209]331
[57]332  protected:
333
334    void attach(ObserverBase& observer) {
335      observer._index = _observers.insert(_observers.begin(), &observer);
336      observer._notifier = this;
[209]337    }
[57]338
339    void detach(ObserverBase& observer) {
340      _observers.erase(observer._index);
341      observer._index = _observers.end();
342      observer._notifier = 0;
343    }
344
345  public:
[209]346
[314]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.
[57]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      }
[209]365    }
[57]366
[314]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.
[57]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      }
[209]385    }
[57]386
[314]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.
[57]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;
[230]401          it = _observers.erase(it);
[57]402        }
403      }
404    }
405
[314]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.
[57]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;
[230]420          it = _observers.erase(it);
[57]421        }
422      }
423    }
424
[314]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.
[57]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
[314]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.
[57]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;
[230]459          it = _observers.erase(it);
[57]460        }
461      }
462    }
463  };
464
465}
466
467#endif
Note: See TracBrowser for help on using the repository browser.