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