COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/alteration_notifier.h @ 1875:98698b69a902

Last change on this file since 1875:98698b69a902 was 1875:98698b69a902, checked in by Alpar Juttner, 14 years ago

Happy new year to LEMON

File size: 15.2 KB
Line 
1/* -*- C++ -*-
2 * lemon/notifier.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 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
402  template <typename _Base>
403  class AlterableEdgeSetExtender : public _Base {
404  public:
405
406    typedef AlterableEdgeSetExtender Graph;
407    typedef _Base Parent;
408
409    typedef typename Parent::Edge Edge;
410
411    /// The edge observer registry.
412    typedef AlterationNotifier<Edge> EdgeNotifier;
413
414  protected:
415
416    mutable EdgeNotifier edge_notifier;
417
418  public:
419
420    /// \brief Gives back the edge alteration notifier.
421    ///
422    /// Gives back the edge alteration notifier.
423    EdgeNotifier& getNotifier(Edge) const {
424      return edge_notifier;
425    }
426
427    ~AlterableEdgeSetExtender() {
428      edge_notifier.clear();
429    }
430   
431  };
432
433  /// \brief Class to extend an undirected graph with the functionality of
434  /// alteration observing.
435  ///
436  /// \todo Document.
437  ///
438  /// \sa AlterableGraphExtender
439  ///
440  /// \bug This should be done some other way. Possibilities: template
441  /// specialization (not very easy, if at all possible); some kind of
442  /// enable_if boost technique?
443
444  template <typename _Base>
445  class AlterableUndirGraphExtender
446    : public AlterableGraphExtender<_Base> {
447  public:
448
449    typedef AlterableUndirGraphExtender Graph;
450    typedef AlterableGraphExtender<_Base> Parent;
451
452    typedef typename Parent::UndirEdge UndirEdge;
453
454    /// The edge observer registry.
455    typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
456
457  protected:
458
459    mutable UndirEdgeNotifier undir_edge_notifier;
460
461  public:
462
463    using Parent::getNotifier;
464    UndirEdgeNotifier& getNotifier(UndirEdge) const {
465      return undir_edge_notifier;
466    }
467
468    ~AlterableUndirGraphExtender() {
469      undir_edge_notifier.clear();
470    }
471  };
472
473  template <typename _Base>
474  class AlterableUndirEdgeSetExtender
475    : public AlterableEdgeSetExtender<_Base> {
476  public:
477
478    typedef AlterableUndirEdgeSetExtender Graph;
479    typedef AlterableEdgeSetExtender<_Base> Parent;
480
481    typedef typename Parent::UndirEdge UndirEdge;
482
483    typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
484
485  protected:
486
487    mutable UndirEdgeNotifier undir_edge_notifier;
488
489  public:
490
491    using Parent::getNotifier;
492    UndirEdgeNotifier& getNotifier(UndirEdge) const {
493      return undir_edge_notifier;
494    }
495
496    ~AlterableUndirEdgeSetExtender() {
497      undir_edge_notifier.clear();
498    }
499  };
500
501
502
503  template <typename _Base>
504  class AlterableUndirBipartiteGraphExtender : public _Base {
505  public:
506
507    typedef _Base Parent;
508    typedef AlterableUndirBipartiteGraphExtender Graph;
509 
510    typedef typename Parent::Node Node;
511    typedef typename Parent::LowerNode LowerNode;
512    typedef typename Parent::UpperNode UpperNode;
513    typedef typename Parent::Edge Edge;
514    typedef typename Parent::UndirEdge UndirEdge;
515 
516 
517    typedef AlterationNotifier<Node> NodeNotifier;
518    typedef AlterationNotifier<LowerNode> LowerNodeNotifier;
519    typedef AlterationNotifier<UpperNode> UpperNodeNotifier;
520    typedef AlterationNotifier<Edge> EdgeNotifier;
521    typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
522
523  protected:
524
525    mutable NodeNotifier nodeNotifier;
526    mutable LowerNodeNotifier lowerNodeNotifier;
527    mutable UpperNodeNotifier upperNodeNotifier;
528    mutable EdgeNotifier edgeNotifier;
529    mutable UndirEdgeNotifier undirEdgeNotifier;
530
531  public:
532
533    NodeNotifier& getNotifier(Node) const {
534      return nodeNotifier;
535    }
536
537    LowerNodeNotifier& getNotifier(LowerNode) const {
538      return lowerNodeNotifier;
539    }
540
541    UpperNodeNotifier& getNotifier(UpperNode) const {
542      return upperNodeNotifier;
543    }
544
545    EdgeNotifier& getNotifier(Edge) const {
546      return edgeNotifier;
547    }
548
549    UndirEdgeNotifier& getNotifier(UndirEdge) const {
550      return undirEdgeNotifier;
551    }
552
553    ~AlterableUndirBipartiteGraphExtender() {
554      nodeNotifier.clear();
555      lowerNodeNotifier.clear();
556      upperNodeNotifier.clear();
557      edgeNotifier.clear();
558      undirEdgeNotifier.clear();
559    }
560
561  };
562 
563/// @}
564 
565
566}
567
568#endif
Note: See TracBrowser for help on using the repository browser.