1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/alteration_notifier.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,438 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/notifier.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_ALTERATION_OBSERVER_REGISTRY_H
1.21 +#define LEMON_ALTERATION_OBSERVER_REGISTRY_H
1.22 +
1.23 +#include <vector>
1.24 +#include <algorithm>
1.25 +
1.26 +///\ingroup graphmaps
1.27 +///\file
1.28 +///\brief Observer registry for graph alteration observers.
1.29 +
1.30 +namespace lemon {
1.31 +
1.32 + /// \addtogroup graphmaps
1.33 + /// @{
1.34 +
1.35 + /// \brief Registry class to register objects observes alterations in
1.36 + /// the graph.
1.37 + ///
1.38 + /// This class is a registry for the objects which observe the
1.39 + /// alterations in a container. The alteration observers can be attached
1.40 + /// to and detached from the registry. The observers have to inherit
1.41 + /// from the \ref AlterationNotifier::ObserverBase and override
1.42 + /// the virtual functions in that.
1.43 + ///
1.44 + /// The most important application of the alteration observing is the
1.45 + /// dynamic map implementation.
1.46 + ///
1.47 + /// \param _Item The item type what the observers are observing, usually
1.48 + /// edge or node.
1.49 + ///
1.50 + /// \author Balazs Dezso
1.51 +
1.52 + template <typename _Item>
1.53 + class AlterationNotifier {
1.54 + public:
1.55 + typedef _Item Item;
1.56 +
1.57 + /// ObserverBase is the base class for the observers.
1.58 +
1.59 + /// ObserverBase is the abstract base class for the observers.
1.60 + /// It will be notified about an item was inserted into or
1.61 + /// erased from the graph.
1.62 + ///
1.63 + /// The observer interface contains some pure virtual functions
1.64 + /// to override. The add() and erase() functions are
1.65 + /// to notify the oberver when one item is added or
1.66 + /// erased.
1.67 + ///
1.68 + /// The build() and clear() members are to notify the observer
1.69 + /// about the container is built from an empty container or
1.70 + /// is cleared to an empty container.
1.71 + ///
1.72 + /// \author Balazs Dezso
1.73 +
1.74 + class ObserverBase {
1.75 + protected:
1.76 + typedef AlterationNotifier Registry;
1.77 +
1.78 + friend class AlterationNotifier;
1.79 +
1.80 + /// \brief Default constructor.
1.81 + ///
1.82 + /// Default constructor for ObserverBase.
1.83 + ///
1.84 + ObserverBase() : registry(0) {}
1.85 +
1.86 + virtual ~ObserverBase() {}
1.87 +
1.88 + /// \brief Attaches the observer into an AlterationNotifier.
1.89 + ///
1.90 + /// This member attaches the observer into an AlterationNotifier.
1.91 + ///
1.92 + void attach(AlterationNotifier& r) {
1.93 + registry = &r;
1.94 + registry->attach(*this);
1.95 + }
1.96 +
1.97 + /// \brief Detaches the observer into an AlterationNotifier.
1.98 + ///
1.99 + /// This member detaches the observer from an AlterationNotifier.
1.100 + ///
1.101 + void detach() {
1.102 + if (registry) {
1.103 + registry->detach(*this);
1.104 + }
1.105 + }
1.106 +
1.107 +
1.108 + /// Gives back a pointer to the registry what the map attached into.
1.109 +
1.110 + /// This function gives back a pointer to the registry what the map
1.111 + /// attached into.
1.112 + ///
1.113 + Registry* getRegistry() const { return const_cast<Registry*>(registry); }
1.114 +
1.115 + /// Gives back true when the observer is attached into a registry.
1.116 + bool attached() const { return registry != 0; }
1.117 +
1.118 + private:
1.119 +
1.120 + ObserverBase(const ObserverBase& copy);
1.121 + ObserverBase& operator=(const ObserverBase& copy);
1.122 +
1.123 + protected:
1.124 +
1.125 + Registry* registry;
1.126 + int registry_index;
1.127 +
1.128 + public:
1.129 +
1.130 + /// \brief The member function to notificate the observer about an
1.131 + /// item is added to the container.
1.132 + ///
1.133 + /// The add() member function notificates the observer about an item
1.134 + /// is added to the container. It have to be overrided in the
1.135 + /// subclasses.
1.136 +
1.137 + virtual void add(const Item&) = 0;
1.138 +
1.139 + /// \brief The member function to notificate the observer about
1.140 + /// simulitem is added to the container.
1.141 + ///
1.142 + /// The add() member function notificates the observer about an item
1.143 + /// is added to the container. It have to be overrided in the
1.144 + /// subclasses.
1.145 +
1.146 + virtual void add(const std::vector<Item>& items) {
1.147 + for (int i = 0; i < (int)items.size(); ++i) {
1.148 + add(items[i]);
1.149 + }
1.150 + }
1.151 +
1.152 + /// \brief The member function to notificate the observer about an
1.153 + /// item is erased from the container.
1.154 + ///
1.155 + /// The erase() member function notificates the observer about an
1.156 + /// item is erased from the container. It have to be overrided in
1.157 + /// the subclasses.
1.158 +
1.159 + virtual void erase(const Item&) = 0;
1.160 +
1.161 + virtual void erase(const std::vector<Item>& items) {
1.162 + for (int i = 0; i < (int)items.size(); ++i) {
1.163 + add(items[i]);
1.164 + }
1.165 + }
1.166 +
1.167 + /// \brief The member function to notificate the observer about the
1.168 + /// container is built.
1.169 + ///
1.170 + /// The build() member function notificates the observer about the
1.171 + /// container is built from an empty container. It have to be
1.172 + /// overrided in the subclasses.
1.173 +
1.174 + virtual void build() = 0;
1.175 +
1.176 + /// \brief The member function to notificate the observer about all
1.177 + /// items are erased from the container.
1.178 + ///
1.179 + /// The clear() member function notificates the observer about all
1.180 + /// items are erased from the container. It have to be overrided in
1.181 + /// the subclasses.
1.182 +
1.183 + virtual void clear() = 0;
1.184 +
1.185 + };
1.186 +
1.187 + protected:
1.188 +
1.189 +
1.190 + typedef std::vector<ObserverBase*> Container;
1.191 +
1.192 + Container container;
1.193 +
1.194 +
1.195 + public:
1.196 +
1.197 + /// Default constructor.
1.198 +
1.199 + ///
1.200 + /// The default constructor of the AlterationNotifier.
1.201 + /// It creates an empty registry.
1.202 + AlterationNotifier() {}
1.203 +
1.204 + /// Copy Constructor of the AlterationNotifier.
1.205 +
1.206 + /// Copy constructor of the AlterationNotifier.
1.207 + /// It creates only an empty registry because the copiable
1.208 + /// registry's observers have to be registered still into that registry.
1.209 + AlterationNotifier(const AlterationNotifier&) {}
1.210 +
1.211 + /// Assign operator.
1.212 +
1.213 + /// Assign operator for the AlterationNotifier.
1.214 + /// It makes the notifier only empty because the copiable
1.215 + /// notifier's observers have to be registered still into that registry.
1.216 + AlterationNotifier& operator=(const AlterationNotifier&) {
1.217 + typename Container::iterator it;
1.218 + for (it = container.begin(); it != container.end(); ++it) {
1.219 + (*it)->registry = 0;
1.220 + }
1.221 + }
1.222 +
1.223 + /// Destructor.
1.224 +
1.225 + /// Destructor of the AlterationNotifier.
1.226 + ///
1.227 + ~AlterationNotifier() {
1.228 + typename Container::iterator it;
1.229 + for (it = container.begin(); it != container.end(); ++it) {
1.230 + (*it)->registry = 0;
1.231 + }
1.232 + }
1.233 +
1.234 +
1.235 + protected:
1.236 +
1.237 + void attach(ObserverBase& observer) {
1.238 + container.push_back(&observer);
1.239 + observer.registry = this;
1.240 + observer.registry_index = container.size()-1;
1.241 + }
1.242 +
1.243 + void detach(ObserverBase& base) {
1.244 + container.back()->registry_index = base.registry_index;
1.245 + container[base.registry_index] = container.back();
1.246 + container.pop_back();
1.247 + base.registry = 0;
1.248 + }
1.249 +
1.250 + public:
1.251 +
1.252 + /// \brief Notifies all the registered observers about an Item added to
1.253 + /// the container.
1.254 + ///
1.255 + /// It notifies all the registered observers about an Item added to
1.256 + /// the container.
1.257 + ///
1.258 + void add(const Item& item) {
1.259 + typename Container::iterator it;
1.260 + for (it = container.begin(); it != container.end(); ++it) {
1.261 + (*it)->add(item);
1.262 + }
1.263 + }
1.264 +
1.265 + /// \brief Notifies all the registered observers about more Item added to
1.266 + /// the container.
1.267 + ///
1.268 + /// It notifies all the registered observers about more Item added to
1.269 + /// the container.
1.270 + ///
1.271 + void add(const std::vector<Item>& items) {
1.272 + typename Container::iterator it;
1.273 + for (it = container.begin(); it != container.end(); ++it) {
1.274 + (*it)->add(items);
1.275 + }
1.276 + }
1.277 +
1.278 + /// \brief Notifies all the registered observers about an Item erased from
1.279 + /// the container.
1.280 + ///
1.281 + /// It notifies all the registered observers about an Item erased from
1.282 + /// the container.
1.283 + ///
1.284 + void erase(const Item& key) {
1.285 + typename Container::iterator it;
1.286 + for (it = container.begin(); it != container.end(); ++it) {
1.287 + (*it)->erase(key);
1.288 + }
1.289 + }
1.290 +
1.291 + /// \brief Notifies all the registered observers about more Item erased
1.292 + /// from the container.
1.293 + ///
1.294 + /// It notifies all the registered observers about more Item erased from
1.295 + /// the container.
1.296 + ///
1.297 + void erase(const std::vector<Item>& items) {
1.298 + typename Container::iterator it;
1.299 + for (it = container.begin(); it != container.end(); ++it) {
1.300 + (*it)->erase(items);
1.301 + }
1.302 + }
1.303 +
1.304 +
1.305 + /// \brief Notifies all the registered observers about the container is
1.306 + /// built.
1.307 + ///
1.308 + /// Notifies all the registered observers about the container is built
1.309 + /// from an empty container.
1.310 + void build() {
1.311 + typename Container::iterator it;
1.312 + for (it = container.begin(); it != container.end(); ++it) {
1.313 + (*it)->build();
1.314 + }
1.315 + }
1.316 +
1.317 +
1.318 + /// \brief Notifies all the registered observers about all Items are
1.319 + /// erased.
1.320 + ///
1.321 + /// Notifies all the registered observers about all Items are erased
1.322 + /// from the container.
1.323 + void clear() {
1.324 + typename Container::iterator it;
1.325 + for (it = container.begin(); it != container.end(); ++it) {
1.326 + (*it)->clear();
1.327 + }
1.328 + }
1.329 + };
1.330 +
1.331 +
1.332 + /// \brief Class to extend a graph with the functionality of alteration
1.333 + /// observing.
1.334 + ///
1.335 + /// AlterableGraphExtender extends the _Base graphs functionality with
1.336 + /// the possibility of alteration observing. It defines two observer
1.337 + /// registrys for the nodes and mapes.
1.338 + ///
1.339 + /// \todo Document what "alteration observing" is. And probably find a
1.340 + /// better (shorter) name.
1.341 + ///
1.342 + /// \param _Base is the base class to extend.
1.343 + ///
1.344 + /// \pre _Base is conform to the BaseGraphComponent concept.
1.345 + ///
1.346 + /// \post AlterableGraphExtender<_Base> is conform to the
1.347 + /// AlterableGraphComponent concept.
1.348 + ///
1.349 + /// \author Balazs Dezso
1.350 +
1.351 + template <typename _Base>
1.352 + class AlterableGraphExtender : public _Base {
1.353 + public:
1.354 +
1.355 + typedef AlterableGraphExtender Graph;
1.356 + typedef _Base Parent;
1.357 +
1.358 + typedef typename Parent::Node Node;
1.359 + typedef typename Parent::Edge Edge;
1.360 +
1.361 + /// The edge observer registry.
1.362 + typedef AlterationNotifier<Edge> EdgeNotifier;
1.363 + /// The node observer registry.
1.364 + typedef AlterationNotifier<Node> NodeNotifier;
1.365 +
1.366 +
1.367 + protected:
1.368 +
1.369 + mutable EdgeNotifier edge_notifier;
1.370 +
1.371 + mutable NodeNotifier node_notifier;
1.372 +
1.373 + public:
1.374 +
1.375 + /// \brief Gives back the edge alteration notifier.
1.376 + ///
1.377 + /// Gives back the edge alteration notifier.
1.378 + EdgeNotifier& getNotifier(Edge) const {
1.379 + return edge_notifier;
1.380 + }
1.381 +
1.382 + /// \brief Gives back the node alteration notifier.
1.383 + ///
1.384 + /// Gives back the node alteration notifier.
1.385 + NodeNotifier& getNotifier(Node) const {
1.386 + return node_notifier;
1.387 + }
1.388 +
1.389 + ~AlterableGraphExtender() {
1.390 + node_notifier.clear();
1.391 + edge_notifier.clear();
1.392 + }
1.393 +
1.394 + };
1.395 +
1.396 + /// \brief Class to extend an undirected graph with the functionality of
1.397 + /// alteration observing.
1.398 + ///
1.399 + /// \todo Document.
1.400 + ///
1.401 + /// \sa AlterableGraphExtender
1.402 + ///
1.403 + /// \bug This should be done some other way. Possibilities: template
1.404 + /// specialization (not very easy, if at all possible); some kind of
1.405 + /// enable_if boost technique?
1.406 +
1.407 + template <typename _Base>
1.408 + class AlterableUndirGraphExtender
1.409 + : public AlterableGraphExtender<_Base> {
1.410 + public:
1.411 +
1.412 + typedef AlterableUndirGraphExtender Graph;
1.413 + typedef AlterableGraphExtender<_Base> Parent;
1.414 +
1.415 + typedef typename Parent::UndirEdge UndirEdge;
1.416 +
1.417 + /// The edge observer registry.
1.418 + typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
1.419 +
1.420 + protected:
1.421 +
1.422 + mutable UndirEdgeNotifier undir_edge_notifier;
1.423 +
1.424 + public:
1.425 +
1.426 + using Parent::getNotifier;
1.427 + UndirEdgeNotifier& getNotifier(UndirEdge) const {
1.428 + return undir_edge_notifier;
1.429 + }
1.430 +
1.431 + ~AlterableUndirGraphExtender() {
1.432 + undir_edge_notifier.clear();
1.433 + }
1.434 + };
1.435 +
1.436 +/// @}
1.437 +
1.438 +
1.439 +}
1.440 +
1.441 +#endif