author | deba |
Wed, 13 Jul 2005 14:17:13 +0000 | |
changeset 1554 | 572bc7d0d3e2 |
parent 1414 | 01d9d6bc1284 |
child 1587 | 8f1c317ebeb4 |
permissions | -rw-r--r-- |
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 |
|
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 |
namespace lemon { |
klao@946 | 28 |
|
klao@946 | 29 |
/// \addtogroup graphmaps |
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 |