author | alpar |
Sat, 19 Mar 2005 09:44:27 +0000 | |
changeset 1228 | 0a7719037acb |
parent 1164 | 80bb73097736 |
permissions | -rw-r--r-- |
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 |
alpar@1204 | 68 |
/// about the container is built 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 |
alpar@1204 | 149 |
/// container is built. |
klao@946 | 150 |
/// |
klao@946 | 151 |
/// The build() member function notificates the observer about the |
alpar@1204 | 152 |
/// container is built 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 |
|
alpar@1204 | 256 |
/// Notifies all the registered observers about the container is built. |
klao@946 | 257 |
|
alpar@1204 | 258 |
/// Notifies all the registered observers about the container is built |
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 |