src/lemon/alteration_notifier.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 1134 56b07afdbf8d
child 1204 c3e29c6ae4e4
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
klao@946
     1
/* -*- C++ -*-
deba@1038
     2
 * src/lemon/notifier.h - Part of LEMON, a generic C++ optimization library
klao@946
     3
 *
alpar@1164
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
klao@946
     5
 * (Egervary Combinatorial Optimization Research Group, EGRES).
klao@946
     6
 *
klao@946
     7
 * Permission to use, modify and distribute this software is granted
klao@946
     8
 * provided that this copyright notice appears in all copies. For
klao@946
     9
 * precise terms see the accompanying LICENSE file.
klao@946
    10
 *
klao@946
    11
 * This software is provided "AS IS" with no warranty of any kind,
klao@946
    12
 * express or implied, and with no claim as to its suitability for any
klao@946
    13
 * purpose.
klao@946
    14
 *
klao@946
    15
 */
klao@946
    16
klao@946
    17
#ifndef LEMON_ALTERATION_OBSERVER_REGISTRY_H
klao@946
    18
#define LEMON_ALTERATION_OBSERVER_REGISTRY_H
klao@946
    19
klao@946
    20
#include <vector>
klao@946
    21
#include <algorithm>
klao@946
    22
klao@946
    23
///\ingroup graphmaps
klao@946
    24
///\file
klao@946
    25
///\brief Observer registry for graph alteration observers.
klao@946
    26
klao@946
    27
using namespace std;
klao@946
    28
klao@946
    29
namespace lemon {
klao@946
    30
klao@946
    31
  /// \addtogroup graphmaps
klao@946
    32
  /// @{
klao@946
    33
klao@946
    34
  /// Registry class to register objects observes alterations in the graph.
klao@946
    35
klao@946
    36
  /// This class is a registry for the objects which observe the
klao@946
    37
  /// alterations in a container. The alteration observers can be attached
klao@946
    38
  /// to and detached from the registry. The observers have to inherit
deba@1038
    39
  /// from the \ref AlterationNotifier::ObserverBase and override
klao@946
    40
  /// the virtual functions in that.
klao@946
    41
  ///
klao@946
    42
  /// The most important application of the alteration observing is the
klao@946
    43
  /// dynamic map implementation when the observers are observing the
klao@946
    44
  /// alterations in the graph.
klao@946
    45
  ///
klao@946
    46
  /// \param _Item The item type what the observers are observing, usually
klao@946
    47
  /// edge or node.
klao@946
    48
  ///
klao@946
    49
  /// \author Balazs Dezso
klao@946
    50
klao@946
    51
  template <typename _Item>
deba@1038
    52
  class AlterationNotifier {
klao@946
    53
  public:
klao@946
    54
    typedef _Item Item;
klao@946
    55
klao@946
    56
    /// ObserverBase is the base class for the observers.
klao@946
    57
	
klao@946
    58
    /// ObserverBase is the abstract base class for the observers.
klao@946
    59
    /// It will be notified about an item was inserted into or
klao@946
    60
    /// erased from the graph.
klao@946
    61
    ///
klao@946
    62
    /// The observer interface contains some pure virtual functions
klao@946
    63
    /// to override. The add() and erase() functions are
klao@946
    64
    /// to notify the oberver when one item is added or
klao@946
    65
    /// erased.
klao@946
    66
    ///
klao@946
    67
    /// The build() and clear() members are to notify the observer
klao@946
    68
    /// about the container is builded from an empty container or
klao@946
    69
    /// is cleared to an empty container. 
klao@946
    70
    /// 
klao@946
    71
    /// \author Balazs Dezso
klao@946
    72
klao@946
    73
    class ObserverBase {
klao@946
    74
    protected:
deba@1038
    75
      typedef AlterationNotifier Registry;
klao@946
    76
deba@1038
    77
      friend class AlterationNotifier;
klao@946
    78
klao@946
    79
      /// Default constructor.
klao@946
    80
klao@946
    81
      /// Default constructor for ObserverBase.
klao@946
    82
      /// 
klao@946
    83
      ObserverBase() : registry(0) {}
klao@946
    84
klao@946
    85
      virtual ~ObserverBase() {}
klao@946
    86
deba@1038
    87
      /// Attaches the observer into an AlterationNotifier.
klao@946
    88
deba@1038
    89
      /// This member attaches the observer into an AlterationNotifier.
klao@946
    90
      ///
deba@1038
    91
      void attach(AlterationNotifier& r) {
klao@946
    92
	registry = &r;
klao@946
    93
	registry->attach(*this);
klao@946
    94
      }
klao@946
    95
deba@1038
    96
      /// Detaches the observer into an AlterationNotifier.
klao@946
    97
deba@1038
    98
      /// This member detaches the observer from an AlterationNotifier.
klao@946
    99
      ///
klao@946
   100
      void detach() {
klao@946
   101
	if (registry) {
klao@946
   102
	  registry->detach(*this);
klao@946
   103
	}
klao@946
   104
      }
klao@946
   105
	
klao@946
   106
klao@946
   107
      /// Gives back a pointer to the registry what the map attached into.
klao@946
   108
klao@946
   109
      /// This function gives back a pointer to the registry what the map
klao@946
   110
      /// attached into.
klao@946
   111
      ///
klao@946
   112
      Registry* getRegistry() const { return const_cast<Registry*>(registry); }
klao@946
   113
      
klao@946
   114
      /// Gives back true when the observer is attached into a registry.
klao@946
   115
      bool attached() const { return registry != 0; }
klao@946
   116
	
klao@946
   117
    private:
klao@946
   118
klao@946
   119
      ObserverBase(const ObserverBase& copy);
klao@946
   120
      ObserverBase& operator=(const ObserverBase& copy);
klao@946
   121
klao@946
   122
    protected:
klao@946
   123
      
klao@946
   124
      Registry* registry;
klao@946
   125
      int registry_index;
klao@946
   126
klao@946
   127
    public:
klao@946
   128
klao@946
   129
      /// \brief The member function to notificate the observer about an
klao@946
   130
      /// item is added to the container.
klao@946
   131
      ///
klao@946
   132
      /// The add() member function notificates the observer about an item
klao@946
   133
      /// is added to the container. It have to be overrided in the
klao@946
   134
      /// subclasses.
klao@946
   135
	
klao@946
   136
      virtual void add(const Item&) = 0;	
klao@946
   137
klao@946
   138
klao@946
   139
      /// \brief The member function to notificate the observer about an
klao@946
   140
      /// item is erased from the container.
klao@946
   141
      ///
klao@946
   142
      /// The erase() member function notificates the observer about an
klao@946
   143
      /// item is erased from the container. It have to be overrided in
klao@946
   144
      /// the subclasses.
klao@946
   145
	
klao@946
   146
      virtual void erase(const Item&) = 0;
klao@946
   147
klao@946
   148
      /// \brief The member function to notificate the observer about the
klao@946
   149
      /// container is builded.
klao@946
   150
      ///
klao@946
   151
      /// The build() member function notificates the observer about the
klao@946
   152
      /// container is builded from an empty container. It have to be
klao@946
   153
      /// overrided in the subclasses.
klao@946
   154
klao@946
   155
      virtual void build() = 0;
klao@946
   156
klao@946
   157
      /// \brief The member function to notificate the observer about all
klao@946
   158
      /// items are erased from the container.
klao@946
   159
      ///
klao@946
   160
      /// The clear() member function notificates the observer about all
klao@946
   161
      /// items are erased from the container. It have to be overrided in
klao@946
   162
      /// the subclasses.
klao@946
   163
      
klao@946
   164
      virtual void clear() = 0;
klao@946
   165
klao@946
   166
    };
klao@946
   167
	
klao@946
   168
  protected:
klao@946
   169
	
klao@946
   170
klao@946
   171
    typedef std::vector<ObserverBase*> Container; 
klao@946
   172
klao@946
   173
    Container container;
klao@946
   174
klao@946
   175
		
klao@946
   176
  public:
klao@946
   177
klao@946
   178
    /// Default constructor.
klao@946
   179
	
klao@946
   180
    ///
deba@1038
   181
    /// The default constructor of the AlterationNotifier. 
klao@946
   182
    /// It creates an empty registry.
deba@1038
   183
    AlterationNotifier() {}
klao@946
   184
deba@1038
   185
    /// Copy Constructor of the AlterationNotifier. 
klao@946
   186
	
deba@1038
   187
    /// Copy constructor of the AlterationNotifier. 
klao@946
   188
    /// It creates only an empty registry because the copiable
klao@946
   189
    /// registry's observers have to be registered still into that registry.
deba@1039
   190
    AlterationNotifier(const AlterationNotifier&) {}
klao@946
   191
klao@946
   192
    /// Assign operator.
klao@946
   193
		
deba@1038
   194
    /// Assign operator for the AlterationNotifier. 
deba@1040
   195
    /// It makes the notifier only empty because the copiable
deba@1040
   196
    /// notifier's observers have to be registered still into that registry.
deba@1039
   197
    AlterationNotifier& operator=(const AlterationNotifier&) {
klao@946
   198
      typename Container::iterator it;
klao@946
   199
      for (it = container.begin(); it != container.end(); ++it) {
klao@946
   200
	(*it)->registry = 0;
klao@946
   201
      }
klao@946
   202
    }
klao@946
   203
klao@946
   204
    /// Destructor.
klao@946
   205
				
deba@1038
   206
    /// Destructor of the AlterationNotifier.
klao@946
   207
    ///
deba@1038
   208
    ~AlterationNotifier() {
klao@946
   209
      typename Container::iterator it;
klao@946
   210
      for (it = container.begin(); it != container.end(); ++it) {
klao@946
   211
	(*it)->registry = 0;
klao@946
   212
      }
klao@946
   213
    }
klao@946
   214
	
klao@946
   215
	
klao@946
   216
  protected:
klao@946
   217
klao@946
   218
    void attach(ObserverBase& observer) {
klao@946
   219
      container.push_back(&observer);
klao@946
   220
      observer.registry = this;
klao@946
   221
      observer.registry_index = container.size()-1;
klao@946
   222
    } 
klao@946
   223
klao@946
   224
    void detach(ObserverBase& base) {
klao@946
   225
      container.back()->registry_index = base.registry_index; 
klao@946
   226
      container[base.registry_index] = container.back();
klao@946
   227
      container.pop_back();
klao@946
   228
      base.registry = 0;
klao@946
   229
    }
klao@946
   230
klao@946
   231
  public:
klao@946
   232
	
klao@946
   233
    /// Notifies all the registered observers about an Item added to the container.
klao@946
   234
		
klao@946
   235
    /// It notifies all the registered observers about an Item added to the container.
klao@946
   236
    /// 
klao@946
   237
    void add(const Item& key) {
klao@946
   238
      typename Container::iterator it;
klao@946
   239
      for (it = container.begin(); it != container.end(); ++it) {
klao@946
   240
	(*it)->add(key);
klao@946
   241
      }
klao@946
   242
    }	
klao@946
   243
klao@946
   244
    /// Notifies all the registered observers about an Item erased from the container.
klao@946
   245
		
klao@946
   246
    /// It notifies all the registered observers about an Item erased from the container.
klao@946
   247
    /// 
klao@946
   248
    void erase(const Item& key) {
klao@946
   249
      typename Container::iterator it;
klao@946
   250
      for (it = container.begin(); it != container.end(); ++it) {
klao@946
   251
	(*it)->erase(key);
klao@946
   252
      }
klao@946
   253
    }
klao@946
   254
    
klao@946
   255
klao@946
   256
    /// Notifies all the registered observers about the container is builded.
klao@946
   257
		
klao@946
   258
    /// Notifies all the registered observers about the container is builded
klao@946
   259
    /// from an empty container.
klao@946
   260
    void build() {
klao@946
   261
      typename Container::iterator it;
klao@946
   262
      for (it = container.begin(); it != container.end(); ++it) {
klao@946
   263
	(*it)->build();
klao@946
   264
      }
klao@946
   265
    }
klao@946
   266
klao@946
   267
klao@946
   268
    /// Notifies all the registered observers about all Items are erased.
klao@946
   269
klao@946
   270
    /// Notifies all the registered observers about all Items are erased
klao@946
   271
    /// from the container.
klao@946
   272
    void clear() {
klao@946
   273
      typename Container::iterator it;
klao@946
   274
      for (it = container.begin(); it != container.end(); ++it) {
klao@946
   275
	(*it)->clear();
klao@946
   276
      }
klao@946
   277
    }
klao@946
   278
  };
klao@946
   279
klao@946
   280
klao@962
   281
  /// \brief Class to extend a graph with the functionality of alteration
klao@962
   282
  /// observing.
klao@962
   283
  ///
klao@962
   284
  /// AlterableGraphExtender extends the _Base graphs functionality with
klao@962
   285
  /// the possibility of alteration observing. It defines two observer
klao@962
   286
  /// registrys for the nodes and mapes.
klao@962
   287
  /// 
klao@962
   288
  /// \todo Document what "alteration observing" is. And probably find a
klao@962
   289
  /// better (shorter) name.
klao@946
   290
  ///
klao@946
   291
  /// \param _Base is the base class to extend.
klao@946
   292
  ///
klao@946
   293
  /// \pre _Base is conform to the BaseGraphComponent concept.
klao@946
   294
  ///
klao@962
   295
  /// \post AlterableGraphExtender<_Base> is conform to the
klao@962
   296
  /// AlterableGraphComponent concept.
klao@946
   297
  ///
klao@946
   298
  /// \author Balazs Dezso
klao@946
   299
klao@946
   300
  template <typename _Base> 
klao@946
   301
  class AlterableGraphExtender : public _Base {
klao@946
   302
  public:
klao@946
   303
klao@946
   304
    typedef AlterableGraphExtender Graph;
klao@946
   305
    typedef _Base Parent;
klao@946
   306
klao@946
   307
    typedef typename Parent::Node Node;
klao@946
   308
    typedef typename Parent::Edge Edge;
klao@946
   309
klao@962
   310
    /// The edge observer registry.
deba@1039
   311
    typedef AlterationNotifier<Edge> EdgeNotifier;
klao@946
   312
    /// The node observer registry.
deba@1039
   313
    typedef AlterationNotifier<Node> NodeNotifier;
klao@946
   314
klao@946
   315
klao@946
   316
  protected:
klao@946
   317
deba@1040
   318
    mutable EdgeNotifier edge_notifier;
klao@946
   319
deba@1040
   320
    mutable NodeNotifier node_notifier;
klao@946
   321
klao@946
   322
  public:
klao@946
   323
deba@1134
   324
    /// \brief Gives back the edge alteration notifier.
deba@1134
   325
    ///
deba@1134
   326
    /// Gives back the edge alteration notifier.
deba@1134
   327
    EdgeNotifier& getNotifier(Edge) const {
deba@1040
   328
      return edge_notifier;
klao@946
   329
    }
klao@946
   330
deba@1134
   331
    /// \brief Gives back the node alteration notifier.
deba@1134
   332
    ///
deba@1134
   333
    /// Gives back the node alteration notifier.
deba@1134
   334
    NodeNotifier& getNotifier(Node) const {
deba@1040
   335
      return node_notifier;
klao@946
   336
    }
klao@946
   337
klao@946
   338
    ~AlterableGraphExtender() {
deba@1040
   339
      node_notifier.clear();
deba@1040
   340
      edge_notifier.clear();
klao@946
   341
    }
klao@946
   342
    
klao@946
   343
  };
klao@946
   344
klao@962
   345
  /// \brief Class to extend an undirected graph with the functionality of
klao@962
   346
  /// alteration observing.
klao@962
   347
  ///
klao@962
   348
  /// \todo Document.
klao@962
   349
  ///
klao@962
   350
  /// \sa AlterableGraphExtender
klao@962
   351
  ///
klao@962
   352
  /// \bug This should be done some other way. Possibilities: template
klao@962
   353
  /// specialization (not very easy, if at all possible); some kind of
klao@962
   354
  /// enable_if boost technique?
klao@962
   355
klao@962
   356
  template <typename _Base> 
klao@962
   357
  class AlterableUndirGraphExtender
klao@962
   358
    : public AlterableGraphExtender<_Base> {
klao@962
   359
  public:
klao@962
   360
klao@962
   361
    typedef AlterableUndirGraphExtender Graph;
klao@962
   362
    typedef AlterableGraphExtender<_Base> Parent;
klao@962
   363
klao@962
   364
    typedef typename Parent::UndirEdge UndirEdge;
klao@962
   365
klao@962
   366
    /// The edge observer registry.
deba@1039
   367
    typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
klao@962
   368
klao@962
   369
  protected:
klao@962
   370
deba@1040
   371
    mutable UndirEdgeNotifier undir_edge_notifier;
klao@962
   372
klao@1022
   373
  public:
klao@1022
   374
deba@1038
   375
    using Parent::getNotifier;
deba@1039
   376
    UndirEdgeNotifier& getNotifier(UndirEdge) const {
deba@1040
   377
      return undir_edge_notifier;
klao@962
   378
    }
klao@962
   379
klao@962
   380
    ~AlterableUndirGraphExtender() {
deba@1040
   381
      undir_edge_notifier.clear();
klao@962
   382
    }
klao@962
   383
  };
klao@946
   384
  
klao@946
   385
/// @}
klao@946
   386
  
klao@946
   387
klao@946
   388
}
klao@946
   389
klao@946
   390
#endif