COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/alteration_notifier.h @ 1832:d0c28d9c9141

Last change on this file since 1832:d0c28d9c9141 was 1832:d0c28d9c9141, checked in by Balazs Dezso, 18 years ago

Bug fix

File size: 13.9 KB
Line 
1/* -*- C++ -*-
2 * lemon/notifier.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_ALTERATION_OBSERVER_REGISTRY_H
18#define LEMON_ALTERATION_OBSERVER_REGISTRY_H
19
20#include <vector>
21#include <algorithm>
22
23///\ingroup graphmapfactory
24///\file
25///\brief Observer registry for graph alteration observers.
26
27namespace lemon {
28
29  /// \addtogroup graphmapfactory
30  /// @{
31
32  /// \brief Registry class to register objects observes alterations in
33  /// the graph.
34  ///
35  /// This class is a registry for the objects which observe the
36  /// alterations in a container. The alteration observers can be attached
37  /// to and detached from the registry. The observers have to inherit
38  /// from the \ref AlterationNotifier::ObserverBase and override
39  /// the virtual functions in that.
40  ///
41  /// The most important application of the alteration observing is the
42  /// dynamic map implementation.
43  ///
44  /// \param _Item The item type what the observers are observing, usually
45  /// edge or node.
46  ///
47  /// \author Balazs Dezso
48
49  template <typename _Item>
50  class AlterationNotifier {
51  public:
52    typedef _Item Item;
53
54    /// ObserverBase is the base class for the observers.
55       
56    /// ObserverBase is the abstract base class for the observers.
57    /// It will be notified about an item was inserted into or
58    /// erased from the graph.
59    ///
60    /// The observer interface contains some pure virtual functions
61    /// to override. The add() and erase() functions are
62    /// to notify the oberver when one item is added or
63    /// erased.
64    ///
65    /// The build() and clear() members are to notify the observer
66    /// about the container is built from an empty container or
67    /// is cleared to an empty container.
68    ///
69    /// \author Balazs Dezso
70
71    class ObserverBase {
72    protected:
73      typedef AlterationNotifier Registry;
74
75      friend class AlterationNotifier;
76
77      /// \brief Default constructor.
78      ///
79      /// Default constructor for ObserverBase.
80      ///
81      ObserverBase() : registry(0) {}
82
83      ObserverBase(const ObserverBase& copy) {
84        if (copy.attached()) {
85          copy.getRegistry()->attach(*this);
86        }
87      }
88       
89      virtual ~ObserverBase() {}
90
91      /// \brief Attaches the observer into an AlterationNotifier.
92      ///
93      /// This member attaches the observer into an AlterationNotifier.
94      ///
95      void attach(AlterationNotifier& r) {
96        registry = &r;
97        registry->attach(*this);
98      }
99
100      /// \brief Detaches the observer into an AlterationNotifier.
101      ///
102      /// This member detaches the observer from an AlterationNotifier.
103      ///
104      void detach() {
105        if (registry) {
106          registry->detach(*this);
107        }
108      }
109       
110
111      /// Gives back a pointer to the registry what the map attached into.
112
113      /// This function gives back a pointer to the registry what the map
114      /// attached into.
115      ///
116      Registry* getRegistry() const { return const_cast<Registry*>(registry); }
117     
118      /// Gives back true when the observer is attached into a registry.
119      bool attached() const { return registry != 0; }
120
121    private:
122
123      ObserverBase& operator=(const ObserverBase& copy);
124
125    protected:
126     
127      Registry* registry;
128      int registry_index;
129
130      /// \brief The member function to notificate the observer about an
131      /// item is added to the container.
132      ///
133      /// The add() member function notificates the observer about an item
134      /// is added to the container. It have to be overrided in the
135      /// subclasses.
136       
137      virtual void add(const Item&) = 0;
138
139      /// \brief The member function to notificate the observer about
140      /// more item is added to the container.
141      ///
142      /// The add() member function notificates the observer about more item
143      /// is added to the container. It have to be overrided in the
144      /// subclasses.
145
146      virtual void add(const std::vector<Item>& items) {
147        for (int i = 0; i < (int)items.size(); ++i) {
148          add(items[i]);
149        }
150      }
151
152      /// \brief The member function to notificate the observer about an
153      /// item is erased from the container.
154      ///
155      /// The erase() member function notificates the observer about an
156      /// item is erased from the container. It have to be overrided in
157      /// the subclasses.
158       
159      virtual void erase(const Item&) = 0;
160
161      /// \brief The member function to notificate the observer about
162      /// more item is erased from the container.
163      ///
164      /// The erase() member function notificates the observer about more item
165      /// is erased from the container. It have to be overrided in the
166      /// subclasses.
167      virtual void erase(const std::vector<Item>& items) {
168        for (int i = 0; i < (int)items.size(); ++i) {
169          erase(items[i]);
170        }
171      }
172
173      /// \brief The member function to notificate the observer about the
174      /// container is built.
175      ///
176      /// The build() member function notificates the observer about the
177      /// container is built from an empty container. It have to be
178      /// overrided in the subclasses.
179
180      virtual void build() = 0;
181
182      /// \brief The member function to notificate the observer about all
183      /// items are erased from the container.
184      ///
185      /// The clear() member function notificates the observer about all
186      /// items are erased from the container. It have to be overrided in
187      /// the subclasses.
188     
189      virtual void clear() = 0;
190
191    };
192       
193  protected:
194       
195
196    typedef std::vector<ObserverBase*> Container;
197
198    Container container;
199
200               
201  public:
202
203    /// Default constructor.
204       
205    ///
206    /// The default constructor of the AlterationNotifier.
207    /// It creates an empty registry.
208    AlterationNotifier() {}
209
210    /// Copy Constructor of the AlterationNotifier.
211       
212    /// Copy constructor of the AlterationNotifier.
213    /// It creates only an empty registry because the copiable
214    /// registry's observers have to be registered still into that registry.
215    AlterationNotifier(const AlterationNotifier&) {}
216
217    /// Assign operator.
218               
219    /// Assign operator for the AlterationNotifier.
220    /// It makes the notifier only empty because the copiable
221    /// notifier's observers have to be registered still into that registry.
222    AlterationNotifier& operator=(const AlterationNotifier&) {
223      typename Container::iterator it;
224      for (it = container.begin(); it != container.end(); ++it) {
225        (*it)->registry = 0;
226      }
227    }
228
229    /// Destructor.
230                               
231    /// Destructor of the AlterationNotifier.
232    ///
233    ~AlterationNotifier() {
234      typename Container::iterator it;
235      for (it = container.begin(); it != container.end(); ++it) {
236        (*it)->registry = 0;
237      }
238    }
239       
240       
241  protected:
242
243    void attach(ObserverBase& observer) {
244      container.push_back(&observer);
245      observer.registry = this;
246      observer.registry_index = container.size()-1;
247    }
248
249    void detach(ObserverBase& base) {
250      container.back()->registry_index = base.registry_index;
251      container[base.registry_index] = container.back();
252      container.pop_back();
253      base.registry = 0;
254    }
255
256  public:
257       
258    /// \brief Notifies all the registered observers about an Item added to
259    /// the container.
260    ///
261    /// It notifies all the registered observers about an Item added to
262    /// the container.
263    ///
264    void add(const Item& item) {
265      typename Container::iterator it;
266      for (it = container.begin(); it != container.end(); ++it) {
267        (*it)->add(item);
268      }
269    }   
270
271    /// \brief Notifies all the registered observers about more Item added to
272    /// the container.
273    ///
274    /// It notifies all the registered observers about more Item added to
275    /// the container.
276    ///
277    void add(const std::vector<Item>& items) {
278      typename Container::iterator it;
279      for (it = container.begin(); it != container.end(); ++it) {
280        (*it)->add(items);
281      }
282    }   
283
284    /// \brief Notifies all the registered observers about an Item erased from
285    /// the container.
286    ///
287    /// It notifies all the registered observers about an Item erased from
288    /// the container.
289    ///
290    void erase(const Item& key) {
291      typename Container::iterator it;
292      for (it = container.begin(); it != container.end(); ++it) {
293        (*it)->erase(key);
294      }
295    }
296
297    /// \brief Notifies all the registered observers about more Item erased 
298    /// from the container.
299    ///
300    /// It notifies all the registered observers about more Item erased from
301    /// the container.
302    ///
303    void erase(const std::vector<Item>& items) {
304      typename Container::iterator it;
305      for (it = container.begin(); it != container.end(); ++it) {
306        (*it)->erase(items);
307      }
308    }
309
310    /// \brief Notifies all the registered observers about the container is
311    /// built.
312    ///         
313    /// Notifies all the registered observers about the container is built
314    /// from an empty container.
315    void build() {
316      typename Container::iterator it;
317      for (it = container.begin(); it != container.end(); ++it) {
318        (*it)->build();
319      }
320    }
321
322
323    /// \brief Notifies all the registered observers about all Items are
324    /// erased.
325    ///
326    /// Notifies all the registered observers about all Items are erased
327    /// from the container.
328    void clear() {
329      typename Container::iterator it;
330      for (it = container.begin(); it != container.end(); ++it) {
331        (*it)->clear();
332      }
333    }
334  };
335
336
337  /// \brief Class to extend a graph with the functionality of alteration
338  /// observing.
339  ///
340  /// AlterableGraphExtender extends the _Base graphs functionality with
341  /// the possibility of alteration observing. It defines two observer
342  /// registrys for the nodes and mapes.
343  ///
344  /// \todo Document what "alteration observing" is. And probably find a
345  /// better (shorter) name.
346  ///
347  /// \param _Base is the base class to extend.
348  ///
349  /// \pre _Base is conform to the BaseGraphComponent concept.
350  ///
351  /// \post AlterableGraphExtender<_Base> is conform to the
352  /// AlterableGraphComponent concept.
353  ///
354  /// \author Balazs Dezso
355
356  template <typename _Base>
357  class AlterableGraphExtender : public _Base {
358  public:
359
360    typedef AlterableGraphExtender Graph;
361    typedef _Base Parent;
362
363    typedef typename Parent::Node Node;
364    typedef typename Parent::Edge Edge;
365
366    /// The edge observer registry.
367    typedef AlterationNotifier<Edge> EdgeNotifier;
368    /// The node observer registry.
369    typedef AlterationNotifier<Node> NodeNotifier;
370
371
372  protected:
373
374    mutable EdgeNotifier edge_notifier;
375
376    mutable NodeNotifier node_notifier;
377
378  public:
379
380    /// \brief Gives back the edge alteration notifier.
381    ///
382    /// Gives back the edge alteration notifier.
383    EdgeNotifier& getNotifier(Edge) const {
384      return edge_notifier;
385    }
386
387    /// \brief Gives back the node alteration notifier.
388    ///
389    /// Gives back the node alteration notifier.
390    NodeNotifier& getNotifier(Node) const {
391      return node_notifier;
392    }
393
394    ~AlterableGraphExtender() {
395      node_notifier.clear();
396      edge_notifier.clear();
397    }
398   
399  };
400
401  /// \brief Class to extend an undirected graph with the functionality of
402  /// alteration observing.
403  ///
404  /// \todo Document.
405  ///
406  /// \sa AlterableGraphExtender
407  ///
408  /// \bug This should be done some other way. Possibilities: template
409  /// specialization (not very easy, if at all possible); some kind of
410  /// enable_if boost technique?
411
412  template <typename _Base>
413  class AlterableUndirGraphExtender
414    : public AlterableGraphExtender<_Base> {
415  public:
416
417    typedef AlterableUndirGraphExtender Graph;
418    typedef AlterableGraphExtender<_Base> Parent;
419
420    typedef typename Parent::UndirEdge UndirEdge;
421
422    /// The edge observer registry.
423    typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
424
425  protected:
426
427    mutable UndirEdgeNotifier undir_edge_notifier;
428
429  public:
430
431    using Parent::getNotifier;
432    UndirEdgeNotifier& getNotifier(UndirEdge) const {
433      return undir_edge_notifier;
434    }
435
436    ~AlterableUndirGraphExtender() {
437      undir_edge_notifier.clear();
438    }
439  };
440
441
442  template <typename _Base>
443  class AlterableUndirBipartiteGraphExtender : public _Base {
444  public:
445
446    typedef _Base Parent;
447    typedef AlterableUndirBipartiteGraphExtender Graph;
448 
449    typedef typename Parent::Node Node;
450    typedef typename Parent::LowerNode LowerNode;
451    typedef typename Parent::UpperNode UpperNode;
452    typedef typename Parent::Edge Edge;
453    typedef typename Parent::UndirEdge UndirEdge;
454 
455 
456    typedef AlterationNotifier<Node> NodeNotifier;
457    typedef AlterationNotifier<LowerNode> LowerNodeNotifier;
458    typedef AlterationNotifier<UpperNode> UpperNodeNotifier;
459    typedef AlterationNotifier<Edge> EdgeNotifier;
460    typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
461
462  protected:
463
464    mutable NodeNotifier nodeNotifier;
465    mutable LowerNodeNotifier lowerNodeNotifier;
466    mutable UpperNodeNotifier upperNodeNotifier;
467    mutable EdgeNotifier edgeNotifier;
468    mutable UndirEdgeNotifier undirEdgeNotifier;
469
470  public:
471
472    NodeNotifier& getNotifier(Node) const {
473      return nodeNotifier;
474    }
475
476    LowerNodeNotifier& getNotifier(LowerNode) const {
477      return lowerNodeNotifier;
478    }
479
480    UpperNodeNotifier& getNotifier(UpperNode) const {
481      return upperNodeNotifier;
482    }
483
484    EdgeNotifier& getNotifier(Edge) const {
485      return edgeNotifier;
486    }
487
488    UndirEdgeNotifier& getNotifier(UndirEdge) const {
489      return undirEdgeNotifier;
490    }
491
492    ~AlterableUndirBipartiteGraphExtender() {
493      nodeNotifier.clear();
494      lowerNodeNotifier.clear();
495      upperNodeNotifier.clear();
496      edgeNotifier.clear();
497      undirEdgeNotifier.clear();
498    }
499
500  };
501 
502/// @}
503 
504
505}
506
507#endif
Note: See TracBrowser for help on using the repository browser.