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