1.1 --- a/src/lemon/Makefile.am Tue Apr 05 09:49:01 2005 +0000
1.2 +++ b/src/lemon/Makefile.am Tue Apr 05 12:30:46 2005 +0000
1.3 @@ -10,16 +10,13 @@
1.4 lp_solver_skeleton.cc
1.5
1.6 pkginclude_HEADERS = \
1.7 - array_map.h \
1.8 - bezier.h \
1.9 + bezier.h \
1.10 bfs.h \
1.11 dfs.h \
1.12 bin_heap.h \
1.13 - default_map.h \
1.14 dijkstra.h \
1.15 dimacs.h \
1.16 error.h \
1.17 - extended_pair.h \
1.18 fib_heap.h \
1.19 full_graph.h \
1.20 graph_wrapper.h \
1.21 @@ -28,8 +25,6 @@
1.22 invalid.h \
1.23 kruskal.h \
1.24 list_graph.h \
1.25 - alteration_notifier.h \
1.26 - map_iterator.h \
1.27 maps.h \
1.28 max_matching.h \
1.29 min_cost_flow.h \
1.30 @@ -40,18 +35,23 @@
1.31 smart_graph.h \
1.32 time_measure.h \
1.33 unionfind.h \
1.34 - vector_map.h \
1.35 xy.h \
1.36 concept_check.h \
1.37 utility.h \
1.38 - iterable_graph_extender.h \
1.39 - extendable_graph_extender.h \
1.40 - clearable_graph_extender.h \
1.41 - erasable_graph_extender.h \
1.42 - undir_graph_extender.h \
1.43 graph_reader.h \
1.44 graph_writer.h \
1.45 - map_utils.h
1.46 + map_utils.h \
1.47 + bits/alteration_notifier.h \
1.48 + bits/map_iterator.h \
1.49 + bits/array_map.h \
1.50 + bits/default_map.h \
1.51 + bits/extended_pair.h \
1.52 + bits/vector_map.h \
1.53 + bits/iterable_graph_extender.h \
1.54 + bits/extendable_graph_extender.h \
1.55 + bits/clearable_graph_extender.h \
1.56 + bits/erasable_graph_extender.h \
1.57 + bits/undir_graph_extender.h
1.58
1.59 noinst_HEADERS = \
1.60 lp_base.h \
2.1 --- a/src/lemon/alteration_notifier.h Tue Apr 05 09:49:01 2005 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,390 +0,0 @@
2.4 -/* -*- C++ -*-
2.5 - * src/lemon/notifier.h - Part of LEMON, a generic C++ optimization library
2.6 - *
2.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
2.9 - *
2.10 - * Permission to use, modify and distribute this software is granted
2.11 - * provided that this copyright notice appears in all copies. For
2.12 - * precise terms see the accompanying LICENSE file.
2.13 - *
2.14 - * This software is provided "AS IS" with no warranty of any kind,
2.15 - * express or implied, and with no claim as to its suitability for any
2.16 - * purpose.
2.17 - *
2.18 - */
2.19 -
2.20 -#ifndef LEMON_ALTERATION_OBSERVER_REGISTRY_H
2.21 -#define LEMON_ALTERATION_OBSERVER_REGISTRY_H
2.22 -
2.23 -#include <vector>
2.24 -#include <algorithm>
2.25 -
2.26 -///\ingroup graphmaps
2.27 -///\file
2.28 -///\brief Observer registry for graph alteration observers.
2.29 -
2.30 -using namespace std;
2.31 -
2.32 -namespace lemon {
2.33 -
2.34 - /// \addtogroup graphmaps
2.35 - /// @{
2.36 -
2.37 - /// Registry class to register objects observes alterations in the graph.
2.38 -
2.39 - /// This class is a registry for the objects which observe the
2.40 - /// alterations in a container. The alteration observers can be attached
2.41 - /// to and detached from the registry. The observers have to inherit
2.42 - /// from the \ref AlterationNotifier::ObserverBase and override
2.43 - /// the virtual functions in that.
2.44 - ///
2.45 - /// The most important application of the alteration observing is the
2.46 - /// dynamic map implementation when the observers are observing the
2.47 - /// alterations in the graph.
2.48 - ///
2.49 - /// \param _Item The item type what the observers are observing, usually
2.50 - /// edge or node.
2.51 - ///
2.52 - /// \author Balazs Dezso
2.53 -
2.54 - template <typename _Item>
2.55 - class AlterationNotifier {
2.56 - public:
2.57 - typedef _Item Item;
2.58 -
2.59 - /// ObserverBase is the base class for the observers.
2.60 -
2.61 - /// ObserverBase is the abstract base class for the observers.
2.62 - /// It will be notified about an item was inserted into or
2.63 - /// erased from the graph.
2.64 - ///
2.65 - /// The observer interface contains some pure virtual functions
2.66 - /// to override. The add() and erase() functions are
2.67 - /// to notify the oberver when one item is added or
2.68 - /// erased.
2.69 - ///
2.70 - /// The build() and clear() members are to notify the observer
2.71 - /// about the container is built from an empty container or
2.72 - /// is cleared to an empty container.
2.73 - ///
2.74 - /// \author Balazs Dezso
2.75 -
2.76 - class ObserverBase {
2.77 - protected:
2.78 - typedef AlterationNotifier Registry;
2.79 -
2.80 - friend class AlterationNotifier;
2.81 -
2.82 - /// Default constructor.
2.83 -
2.84 - /// Default constructor for ObserverBase.
2.85 - ///
2.86 - ObserverBase() : registry(0) {}
2.87 -
2.88 - virtual ~ObserverBase() {}
2.89 -
2.90 - /// Attaches the observer into an AlterationNotifier.
2.91 -
2.92 - /// This member attaches the observer into an AlterationNotifier.
2.93 - ///
2.94 - void attach(AlterationNotifier& r) {
2.95 - registry = &r;
2.96 - registry->attach(*this);
2.97 - }
2.98 -
2.99 - /// Detaches the observer into an AlterationNotifier.
2.100 -
2.101 - /// This member detaches the observer from an AlterationNotifier.
2.102 - ///
2.103 - void detach() {
2.104 - if (registry) {
2.105 - registry->detach(*this);
2.106 - }
2.107 - }
2.108 -
2.109 -
2.110 - /// Gives back a pointer to the registry what the map attached into.
2.111 -
2.112 - /// This function gives back a pointer to the registry what the map
2.113 - /// attached into.
2.114 - ///
2.115 - Registry* getRegistry() const { return const_cast<Registry*>(registry); }
2.116 -
2.117 - /// Gives back true when the observer is attached into a registry.
2.118 - bool attached() const { return registry != 0; }
2.119 -
2.120 - private:
2.121 -
2.122 - ObserverBase(const ObserverBase& copy);
2.123 - ObserverBase& operator=(const ObserverBase& copy);
2.124 -
2.125 - protected:
2.126 -
2.127 - Registry* registry;
2.128 - int registry_index;
2.129 -
2.130 - public:
2.131 -
2.132 - /// \brief The member function to notificate the observer about an
2.133 - /// item is added to the container.
2.134 - ///
2.135 - /// The add() member function notificates the observer about an item
2.136 - /// is added to the container. It have to be overrided in the
2.137 - /// subclasses.
2.138 -
2.139 - virtual void add(const Item&) = 0;
2.140 -
2.141 -
2.142 - /// \brief The member function to notificate the observer about an
2.143 - /// item is erased from the container.
2.144 - ///
2.145 - /// The erase() member function notificates the observer about an
2.146 - /// item is erased from the container. It have to be overrided in
2.147 - /// the subclasses.
2.148 -
2.149 - virtual void erase(const Item&) = 0;
2.150 -
2.151 - /// \brief The member function to notificate the observer about the
2.152 - /// container is built.
2.153 - ///
2.154 - /// The build() member function notificates the observer about the
2.155 - /// container is built from an empty container. It have to be
2.156 - /// overrided in the subclasses.
2.157 -
2.158 - virtual void build() = 0;
2.159 -
2.160 - /// \brief The member function to notificate the observer about all
2.161 - /// items are erased from the container.
2.162 - ///
2.163 - /// The clear() member function notificates the observer about all
2.164 - /// items are erased from the container. It have to be overrided in
2.165 - /// the subclasses.
2.166 -
2.167 - virtual void clear() = 0;
2.168 -
2.169 - };
2.170 -
2.171 - protected:
2.172 -
2.173 -
2.174 - typedef std::vector<ObserverBase*> Container;
2.175 -
2.176 - Container container;
2.177 -
2.178 -
2.179 - public:
2.180 -
2.181 - /// Default constructor.
2.182 -
2.183 - ///
2.184 - /// The default constructor of the AlterationNotifier.
2.185 - /// It creates an empty registry.
2.186 - AlterationNotifier() {}
2.187 -
2.188 - /// Copy Constructor of the AlterationNotifier.
2.189 -
2.190 - /// Copy constructor of the AlterationNotifier.
2.191 - /// It creates only an empty registry because the copiable
2.192 - /// registry's observers have to be registered still into that registry.
2.193 - AlterationNotifier(const AlterationNotifier&) {}
2.194 -
2.195 - /// Assign operator.
2.196 -
2.197 - /// Assign operator for the AlterationNotifier.
2.198 - /// It makes the notifier only empty because the copiable
2.199 - /// notifier's observers have to be registered still into that registry.
2.200 - AlterationNotifier& operator=(const AlterationNotifier&) {
2.201 - typename Container::iterator it;
2.202 - for (it = container.begin(); it != container.end(); ++it) {
2.203 - (*it)->registry = 0;
2.204 - }
2.205 - }
2.206 -
2.207 - /// Destructor.
2.208 -
2.209 - /// Destructor of the AlterationNotifier.
2.210 - ///
2.211 - ~AlterationNotifier() {
2.212 - typename Container::iterator it;
2.213 - for (it = container.begin(); it != container.end(); ++it) {
2.214 - (*it)->registry = 0;
2.215 - }
2.216 - }
2.217 -
2.218 -
2.219 - protected:
2.220 -
2.221 - void attach(ObserverBase& observer) {
2.222 - container.push_back(&observer);
2.223 - observer.registry = this;
2.224 - observer.registry_index = container.size()-1;
2.225 - }
2.226 -
2.227 - void detach(ObserverBase& base) {
2.228 - container.back()->registry_index = base.registry_index;
2.229 - container[base.registry_index] = container.back();
2.230 - container.pop_back();
2.231 - base.registry = 0;
2.232 - }
2.233 -
2.234 - public:
2.235 -
2.236 - /// Notifies all the registered observers about an Item added to the container.
2.237 -
2.238 - /// It notifies all the registered observers about an Item added to the container.
2.239 - ///
2.240 - void add(const Item& key) {
2.241 - typename Container::iterator it;
2.242 - for (it = container.begin(); it != container.end(); ++it) {
2.243 - (*it)->add(key);
2.244 - }
2.245 - }
2.246 -
2.247 - /// Notifies all the registered observers about an Item erased from the container.
2.248 -
2.249 - /// It notifies all the registered observers about an Item erased from the container.
2.250 - ///
2.251 - void erase(const Item& key) {
2.252 - typename Container::iterator it;
2.253 - for (it = container.begin(); it != container.end(); ++it) {
2.254 - (*it)->erase(key);
2.255 - }
2.256 - }
2.257 -
2.258 -
2.259 - /// Notifies all the registered observers about the container is built.
2.260 -
2.261 - /// Notifies all the registered observers about the container is built
2.262 - /// from an empty container.
2.263 - void build() {
2.264 - typename Container::iterator it;
2.265 - for (it = container.begin(); it != container.end(); ++it) {
2.266 - (*it)->build();
2.267 - }
2.268 - }
2.269 -
2.270 -
2.271 - /// Notifies all the registered observers about all Items are erased.
2.272 -
2.273 - /// Notifies all the registered observers about all Items are erased
2.274 - /// from the container.
2.275 - void clear() {
2.276 - typename Container::iterator it;
2.277 - for (it = container.begin(); it != container.end(); ++it) {
2.278 - (*it)->clear();
2.279 - }
2.280 - }
2.281 - };
2.282 -
2.283 -
2.284 - /// \brief Class to extend a graph with the functionality of alteration
2.285 - /// observing.
2.286 - ///
2.287 - /// AlterableGraphExtender extends the _Base graphs functionality with
2.288 - /// the possibility of alteration observing. It defines two observer
2.289 - /// registrys for the nodes and mapes.
2.290 - ///
2.291 - /// \todo Document what "alteration observing" is. And probably find a
2.292 - /// better (shorter) name.
2.293 - ///
2.294 - /// \param _Base is the base class to extend.
2.295 - ///
2.296 - /// \pre _Base is conform to the BaseGraphComponent concept.
2.297 - ///
2.298 - /// \post AlterableGraphExtender<_Base> is conform to the
2.299 - /// AlterableGraphComponent concept.
2.300 - ///
2.301 - /// \author Balazs Dezso
2.302 -
2.303 - template <typename _Base>
2.304 - class AlterableGraphExtender : public _Base {
2.305 - public:
2.306 -
2.307 - typedef AlterableGraphExtender Graph;
2.308 - typedef _Base Parent;
2.309 -
2.310 - typedef typename Parent::Node Node;
2.311 - typedef typename Parent::Edge Edge;
2.312 -
2.313 - /// The edge observer registry.
2.314 - typedef AlterationNotifier<Edge> EdgeNotifier;
2.315 - /// The node observer registry.
2.316 - typedef AlterationNotifier<Node> NodeNotifier;
2.317 -
2.318 -
2.319 - protected:
2.320 -
2.321 - mutable EdgeNotifier edge_notifier;
2.322 -
2.323 - mutable NodeNotifier node_notifier;
2.324 -
2.325 - public:
2.326 -
2.327 - /// \brief Gives back the edge alteration notifier.
2.328 - ///
2.329 - /// Gives back the edge alteration notifier.
2.330 - EdgeNotifier& getNotifier(Edge) const {
2.331 - return edge_notifier;
2.332 - }
2.333 -
2.334 - /// \brief Gives back the node alteration notifier.
2.335 - ///
2.336 - /// Gives back the node alteration notifier.
2.337 - NodeNotifier& getNotifier(Node) const {
2.338 - return node_notifier;
2.339 - }
2.340 -
2.341 - ~AlterableGraphExtender() {
2.342 - node_notifier.clear();
2.343 - edge_notifier.clear();
2.344 - }
2.345 -
2.346 - };
2.347 -
2.348 - /// \brief Class to extend an undirected graph with the functionality of
2.349 - /// alteration observing.
2.350 - ///
2.351 - /// \todo Document.
2.352 - ///
2.353 - /// \sa AlterableGraphExtender
2.354 - ///
2.355 - /// \bug This should be done some other way. Possibilities: template
2.356 - /// specialization (not very easy, if at all possible); some kind of
2.357 - /// enable_if boost technique?
2.358 -
2.359 - template <typename _Base>
2.360 - class AlterableUndirGraphExtender
2.361 - : public AlterableGraphExtender<_Base> {
2.362 - public:
2.363 -
2.364 - typedef AlterableUndirGraphExtender Graph;
2.365 - typedef AlterableGraphExtender<_Base> Parent;
2.366 -
2.367 - typedef typename Parent::UndirEdge UndirEdge;
2.368 -
2.369 - /// The edge observer registry.
2.370 - typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
2.371 -
2.372 - protected:
2.373 -
2.374 - mutable UndirEdgeNotifier undir_edge_notifier;
2.375 -
2.376 - public:
2.377 -
2.378 - using Parent::getNotifier;
2.379 - UndirEdgeNotifier& getNotifier(UndirEdge) const {
2.380 - return undir_edge_notifier;
2.381 - }
2.382 -
2.383 - ~AlterableUndirGraphExtender() {
2.384 - undir_edge_notifier.clear();
2.385 - }
2.386 - };
2.387 -
2.388 -/// @}
2.389 -
2.390 -
2.391 -}
2.392 -
2.393 -#endif
3.1 --- a/src/lemon/array_map.h Tue Apr 05 09:49:01 2005 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,377 +0,0 @@
3.4 -/* -*- C++ -*-
3.5 - * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
3.6 - *
3.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
3.9 - *
3.10 - * Permission to use, modify and distribute this software is granted
3.11 - * provided that this copyright notice appears in all copies. For
3.12 - * precise terms see the accompanying LICENSE file.
3.13 - *
3.14 - * This software is provided "AS IS" with no warranty of any kind,
3.15 - * express or implied, and with no claim as to its suitability for any
3.16 - * purpose.
3.17 - *
3.18 - */
3.19 -
3.20 -#ifndef LEMON_ARRAY_MAP_H
3.21 -#define LEMON_ARRAY_MAP_H
3.22 -
3.23 -#include <memory>
3.24 -#include <lemon/map_iterator.h>
3.25 -
3.26 -///\ingroup graphmaps
3.27 -///\file
3.28 -///\brief Graph maps that construates and destruates
3.29 -///their elements dynamically.
3.30 -
3.31 -namespace lemon {
3.32 -
3.33 -
3.34 - /// \addtogroup graphmaps
3.35 - /// @{
3.36 -
3.37 - /** The ArrayMap template class is graph map structure what
3.38 - * automatically updates the map when a key is added to or erased from
3.39 - * the map. This map factory uses the allocators to implement
3.40 - * the container functionality.
3.41 - *
3.42 - * The template parameter is the AlterationNotifier that the maps
3.43 - * will belong to and the Value.
3.44 - */
3.45 -
3.46 - template <typename _Graph,
3.47 - typename _Item,
3.48 - typename _Value>
3.49 - class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
3.50 -
3.51 - typedef _Item Item;
3.52 - public:
3.53 -
3.54 - /// The graph type of the maps.
3.55 - typedef _Graph Graph;
3.56 - /// The key type of the maps.
3.57 - typedef _Item Key;
3.58 -
3.59 - typedef AlterationNotifier<_Item> Registry;
3.60 -
3.61 - /// The MapBase of the Map which imlements the core regisitry function.
3.62 - typedef typename Registry::ObserverBase Parent;
3.63 -
3.64 - /// The value type of the map.
3.65 - typedef _Value Value;
3.66 -
3.67 -
3.68 - private:
3.69 - typedef std::allocator<Value> Allocator;
3.70 -
3.71 -
3.72 - public:
3.73 -
3.74 - /** Graph and Registry initialized map constructor.
3.75 - */
3.76 - ArrayMap(const Graph& _g) : graph(&_g) {
3.77 - Item it;
3.78 - attach(_g.getNotifier(Item()));
3.79 - allocate_memory();
3.80 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.81 - int id = graph->id(it);;
3.82 - allocator.construct(&(values[id]), Value());
3.83 - }
3.84 - }
3.85 -
3.86 - /// Constructor to use default value to initialize the map.
3.87 -
3.88 - /// It constrates a map and initialize all of the the map.
3.89 -
3.90 - ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
3.91 - Item it;
3.92 - attach(_g.getNotifier(_Item()));
3.93 - allocate_memory();
3.94 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.95 - int id = graph->id(it);;
3.96 - allocator.construct(&(values[id]), _v);
3.97 - }
3.98 - }
3.99 -
3.100 - /** Constructor to copy a map of the same map type.
3.101 - */
3.102 - ArrayMap(const ArrayMap& copy) {
3.103 - if (copy.attached()) {
3.104 - attach(*copy.getRegistry());
3.105 - }
3.106 - capacity = copy.capacity;
3.107 - if (capacity == 0) return;
3.108 - values = allocator.allocate(capacity);
3.109 - Item it;
3.110 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.111 - int id = graph->id(it);;
3.112 - allocator.construct(&(values[id]), copy.values[id]);
3.113 - }
3.114 - }
3.115 -
3.116 - using Parent::attach;
3.117 - using Parent::detach;
3.118 - using Parent::attached;
3.119 -
3.120 - /** Assign operator to copy a map of the same map type.
3.121 - */
3.122 - ArrayMap& operator=(const ArrayMap& copy) {
3.123 - if (© == this) return *this;
3.124 -
3.125 - if (graph != copy.graph) {
3.126 - if (attached()) {
3.127 - clear();
3.128 - detach();
3.129 - }
3.130 - if (copy.attached()) {
3.131 - attach(*copy.getRegistry());
3.132 - }
3.133 - capacity = copy.capacity;
3.134 - if (capacity == 0) return *this;
3.135 - values = allocator.allocate(capacity);
3.136 - }
3.137 -
3.138 - Item it;
3.139 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.140 - int id = graph->id(it);;
3.141 - allocator.construct(&(values[id]), copy.values[id]);
3.142 - }
3.143 -
3.144 - return *this;
3.145 - }
3.146 -
3.147 - /** The destructor of the map.
3.148 - */
3.149 - virtual ~ArrayMap() {
3.150 - if (attached()) {
3.151 - clear();
3.152 - detach();
3.153 - }
3.154 - }
3.155 -
3.156 -
3.157 - /**
3.158 - * The subscript operator. The map can be subscripted by the
3.159 - * actual keys of the graph.
3.160 - */
3.161 - Value& operator[](const Key& key) {
3.162 - int id = graph->id(key);
3.163 - return values[id];
3.164 - }
3.165 -
3.166 - /**
3.167 - * The const subscript operator. The map can be subscripted by the
3.168 - * actual keys of the graph.
3.169 - */
3.170 - const Value& operator[](const Key& key) const {
3.171 - int id = graph->id(key);
3.172 - return values[id];
3.173 - }
3.174 -
3.175 - /** Setter function of the map. Equivalent with map[key] = val.
3.176 - * This is a compatibility feature with the not dereferable maps.
3.177 - */
3.178 - void set(const Key& key, const Value& val) {
3.179 - (*this)[key] = val;
3.180 - }
3.181 -
3.182 - /** Add a new key to the map. It called by the map registry.
3.183 - */
3.184 - void add(const Key& key) {
3.185 - int id = graph->id(key);
3.186 - if (id >= capacity) {
3.187 - int new_capacity = (capacity == 0 ? 1 : capacity);
3.188 - while (new_capacity <= id) {
3.189 - new_capacity <<= 1;
3.190 - }
3.191 - Value* new_values = allocator.allocate(new_capacity);
3.192 - Item it;
3.193 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.194 - int jd = graph->id(it);;
3.195 - if (id != jd) {
3.196 - allocator.construct(&(new_values[jd]), values[jd]);
3.197 - allocator.destroy(&(values[jd]));
3.198 - }
3.199 - }
3.200 - if (capacity != 0) allocator.deallocate(values, capacity);
3.201 - values = new_values;
3.202 - capacity = new_capacity;
3.203 - }
3.204 - allocator.construct(&(values[id]), Value());
3.205 - }
3.206 -
3.207 - /** Erase a key from the map. It called by the map registry.
3.208 - */
3.209 - void erase(const Key& key) {
3.210 - int id = graph->id(key);
3.211 - allocator.destroy(&(values[id]));
3.212 - }
3.213 -
3.214 - void build() {
3.215 - allocate_memory();
3.216 - Item it;
3.217 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.218 - int id = graph->id(it);;
3.219 - allocator.construct(&(values[id]), Value());
3.220 - }
3.221 - }
3.222 -
3.223 - void clear() {
3.224 - if (capacity != 0) {
3.225 - Item it;
3.226 - for (graph->first(it); it != INVALID; graph->next(it)) {
3.227 - int id = graph->id(it);;
3.228 - allocator.destroy(&(values[id]));
3.229 - }
3.230 - allocator.deallocate(values, capacity);
3.231 - capacity = 0;
3.232 - }
3.233 - }
3.234 -
3.235 - const Graph* getGraph() {
3.236 - return graph;
3.237 - }
3.238 -
3.239 -// /// The stl compatible pair iterator of the map.
3.240 -// typedef MapIterator<ArrayMap> Iterator;
3.241 -// /// The stl compatible const pair iterator of the map.
3.242 -// typedef MapConstIterator<ArrayMap> ConstIterator;
3.243 -
3.244 -// /** Returns the begin iterator of the map.
3.245 -// */
3.246 -// Iterator begin() {
3.247 -// return Iterator(*this, KeyIt(*MapBase::getGraph()));
3.248 -// }
3.249 -
3.250 -// /** Returns the end iterator of the map.
3.251 -// */
3.252 -// Iterator end() {
3.253 -// return Iterator(*this, INVALID);
3.254 -// }
3.255 -
3.256 -// /** Returns the begin ConstIterator of the map.
3.257 -// */
3.258 -// ConstIterator begin() const {
3.259 -// return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
3.260 -// }
3.261 -
3.262 -// /** Returns the end const_iterator of the map.
3.263 -// */
3.264 -// ConstIterator end() const {
3.265 -// return ConstIterator(*this, INVALID);
3.266 -// }
3.267 -
3.268 -// /// The KeySet of the Map.
3.269 -// typedef MapConstKeySet<ArrayMap> ConstKeySet;
3.270 -
3.271 -// /// KeySet getter function.
3.272 -// ConstKeySet keySet() const {
3.273 -// return ConstKeySet(*this);
3.274 -// }
3.275 -
3.276 -// /// The ConstValueSet of the Map.
3.277 -// typedef MapConstValueSet<ArrayMap> ConstValueSet;
3.278 -
3.279 -// /// ConstValueSet getter function.
3.280 -// ConstValueSet valueSet() const {
3.281 -// return ConstValueSet(*this);
3.282 -// }
3.283 -
3.284 -// /// The ValueSet of the Map.
3.285 -// typedef MapValueSet<ArrayMap> ValueSet;
3.286 -
3.287 -// /// ValueSet getter function.
3.288 -// ValueSet valueSet() {
3.289 -// return ValueSet(*this);
3.290 -// }
3.291 -
3.292 - private:
3.293 -
3.294 - void allocate_memory() {
3.295 - int max_id = graph->maxId(_Item());
3.296 - if (max_id == -1) {
3.297 - capacity = 0;
3.298 - values = 0;
3.299 - return;
3.300 - }
3.301 - capacity = 1;
3.302 - while (capacity <= max_id) {
3.303 - capacity <<= 1;
3.304 - }
3.305 - values = allocator.allocate(capacity);
3.306 - }
3.307 -
3.308 - const Graph* graph;
3.309 - int capacity;
3.310 - Value* values;
3.311 - Allocator allocator;
3.312 -
3.313 - };
3.314 -
3.315 - template <typename _Base>
3.316 - class ArrayMappableGraphExtender : public _Base {
3.317 - public:
3.318 -
3.319 - typedef ArrayMappableGraphExtender<_Base> Graph;
3.320 - typedef _Base Parent;
3.321 -
3.322 - typedef typename Parent::Node Node;
3.323 - typedef typename Parent::NodeIt NodeIt;
3.324 - typedef typename Parent::NodeNotifier NodeObserverRegistry;
3.325 -
3.326 - typedef typename Parent::Edge Edge;
3.327 - typedef typename Parent::EdgeIt EdgeIt;
3.328 - typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
3.329 -
3.330 -
3.331 -
3.332 - template <typename _Value>
3.333 - class NodeMap
3.334 - : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > {
3.335 - public:
3.336 - typedef ArrayMappableGraphExtender<_Base> Graph;
3.337 -
3.338 - typedef typename Graph::Node Node;
3.339 - typedef typename Graph::NodeIt NodeIt;
3.340 -
3.341 - typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent;
3.342 -
3.343 - //typedef typename Parent::Graph Graph;
3.344 - typedef typename Parent::Value Value;
3.345 -
3.346 - NodeMap(const Graph& g)
3.347 - : Parent(g) {}
3.348 - NodeMap(const Graph& g, const Value& v)
3.349 - : Parent(g, v) {}
3.350 -
3.351 - };
3.352 -
3.353 - template <typename _Value>
3.354 - class EdgeMap
3.355 - : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > {
3.356 - public:
3.357 - typedef ArrayMappableGraphExtender<_Base> Graph;
3.358 -
3.359 - typedef typename Graph::Edge Edge;
3.360 - typedef typename Graph::EdgeIt EdgeIt;
3.361 -
3.362 - typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent;
3.363 -
3.364 - //typedef typename Parent::Graph Graph;
3.365 - typedef typename Parent::Value Value;
3.366 -
3.367 - EdgeMap(const Graph& g)
3.368 - : Parent(g) {}
3.369 - EdgeMap(const Graph& g, const Value& v)
3.370 - : Parent(g, v) {}
3.371 -
3.372 - };
3.373 -
3.374 - };
3.375 -
3.376 -/// @}
3.377 -
3.378 -}
3.379 -
3.380 -#endif //LEMON_ARRAY_MAP_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/lemon/bits/alteration_notifier.h Tue Apr 05 12:30:46 2005 +0000
4.3 @@ -0,0 +1,390 @@
4.4 +/* -*- C++ -*-
4.5 + * src/lemon/notifier.h - Part of LEMON, a generic C++ optimization library
4.6 + *
4.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
4.9 + *
4.10 + * Permission to use, modify and distribute this software is granted
4.11 + * provided that this copyright notice appears in all copies. For
4.12 + * precise terms see the accompanying LICENSE file.
4.13 + *
4.14 + * This software is provided "AS IS" with no warranty of any kind,
4.15 + * express or implied, and with no claim as to its suitability for any
4.16 + * purpose.
4.17 + *
4.18 + */
4.19 +
4.20 +#ifndef LEMON_ALTERATION_OBSERVER_REGISTRY_H
4.21 +#define LEMON_ALTERATION_OBSERVER_REGISTRY_H
4.22 +
4.23 +#include <vector>
4.24 +#include <algorithm>
4.25 +
4.26 +///\ingroup graphmaps
4.27 +///\file
4.28 +///\brief Observer registry for graph alteration observers.
4.29 +
4.30 +using namespace std;
4.31 +
4.32 +namespace lemon {
4.33 +
4.34 + /// \addtogroup graphmaps
4.35 + /// @{
4.36 +
4.37 + /// Registry class to register objects observes alterations in the graph.
4.38 +
4.39 + /// This class is a registry for the objects which observe the
4.40 + /// alterations in a container. The alteration observers can be attached
4.41 + /// to and detached from the registry. The observers have to inherit
4.42 + /// from the \ref AlterationNotifier::ObserverBase and override
4.43 + /// the virtual functions in that.
4.44 + ///
4.45 + /// The most important application of the alteration observing is the
4.46 + /// dynamic map implementation when the observers are observing the
4.47 + /// alterations in the graph.
4.48 + ///
4.49 + /// \param _Item The item type what the observers are observing, usually
4.50 + /// edge or node.
4.51 + ///
4.52 + /// \author Balazs Dezso
4.53 +
4.54 + template <typename _Item>
4.55 + class AlterationNotifier {
4.56 + public:
4.57 + typedef _Item Item;
4.58 +
4.59 + /// ObserverBase is the base class for the observers.
4.60 +
4.61 + /// ObserverBase is the abstract base class for the observers.
4.62 + /// It will be notified about an item was inserted into or
4.63 + /// erased from the graph.
4.64 + ///
4.65 + /// The observer interface contains some pure virtual functions
4.66 + /// to override. The add() and erase() functions are
4.67 + /// to notify the oberver when one item is added or
4.68 + /// erased.
4.69 + ///
4.70 + /// The build() and clear() members are to notify the observer
4.71 + /// about the container is built from an empty container or
4.72 + /// is cleared to an empty container.
4.73 + ///
4.74 + /// \author Balazs Dezso
4.75 +
4.76 + class ObserverBase {
4.77 + protected:
4.78 + typedef AlterationNotifier Registry;
4.79 +
4.80 + friend class AlterationNotifier;
4.81 +
4.82 + /// Default constructor.
4.83 +
4.84 + /// Default constructor for ObserverBase.
4.85 + ///
4.86 + ObserverBase() : registry(0) {}
4.87 +
4.88 + virtual ~ObserverBase() {}
4.89 +
4.90 + /// Attaches the observer into an AlterationNotifier.
4.91 +
4.92 + /// This member attaches the observer into an AlterationNotifier.
4.93 + ///
4.94 + void attach(AlterationNotifier& r) {
4.95 + registry = &r;
4.96 + registry->attach(*this);
4.97 + }
4.98 +
4.99 + /// Detaches the observer into an AlterationNotifier.
4.100 +
4.101 + /// This member detaches the observer from an AlterationNotifier.
4.102 + ///
4.103 + void detach() {
4.104 + if (registry) {
4.105 + registry->detach(*this);
4.106 + }
4.107 + }
4.108 +
4.109 +
4.110 + /// Gives back a pointer to the registry what the map attached into.
4.111 +
4.112 + /// This function gives back a pointer to the registry what the map
4.113 + /// attached into.
4.114 + ///
4.115 + Registry* getRegistry() const { return const_cast<Registry*>(registry); }
4.116 +
4.117 + /// Gives back true when the observer is attached into a registry.
4.118 + bool attached() const { return registry != 0; }
4.119 +
4.120 + private:
4.121 +
4.122 + ObserverBase(const ObserverBase& copy);
4.123 + ObserverBase& operator=(const ObserverBase& copy);
4.124 +
4.125 + protected:
4.126 +
4.127 + Registry* registry;
4.128 + int registry_index;
4.129 +
4.130 + public:
4.131 +
4.132 + /// \brief The member function to notificate the observer about an
4.133 + /// item is added to the container.
4.134 + ///
4.135 + /// The add() member function notificates the observer about an item
4.136 + /// is added to the container. It have to be overrided in the
4.137 + /// subclasses.
4.138 +
4.139 + virtual void add(const Item&) = 0;
4.140 +
4.141 +
4.142 + /// \brief The member function to notificate the observer about an
4.143 + /// item is erased from the container.
4.144 + ///
4.145 + /// The erase() member function notificates the observer about an
4.146 + /// item is erased from the container. It have to be overrided in
4.147 + /// the subclasses.
4.148 +
4.149 + virtual void erase(const Item&) = 0;
4.150 +
4.151 + /// \brief The member function to notificate the observer about the
4.152 + /// container is built.
4.153 + ///
4.154 + /// The build() member function notificates the observer about the
4.155 + /// container is built from an empty container. It have to be
4.156 + /// overrided in the subclasses.
4.157 +
4.158 + virtual void build() = 0;
4.159 +
4.160 + /// \brief The member function to notificate the observer about all
4.161 + /// items are erased from the container.
4.162 + ///
4.163 + /// The clear() member function notificates the observer about all
4.164 + /// items are erased from the container. It have to be overrided in
4.165 + /// the subclasses.
4.166 +
4.167 + virtual void clear() = 0;
4.168 +
4.169 + };
4.170 +
4.171 + protected:
4.172 +
4.173 +
4.174 + typedef std::vector<ObserverBase*> Container;
4.175 +
4.176 + Container container;
4.177 +
4.178 +
4.179 + public:
4.180 +
4.181 + /// Default constructor.
4.182 +
4.183 + ///
4.184 + /// The default constructor of the AlterationNotifier.
4.185 + /// It creates an empty registry.
4.186 + AlterationNotifier() {}
4.187 +
4.188 + /// Copy Constructor of the AlterationNotifier.
4.189 +
4.190 + /// Copy constructor of the AlterationNotifier.
4.191 + /// It creates only an empty registry because the copiable
4.192 + /// registry's observers have to be registered still into that registry.
4.193 + AlterationNotifier(const AlterationNotifier&) {}
4.194 +
4.195 + /// Assign operator.
4.196 +
4.197 + /// Assign operator for the AlterationNotifier.
4.198 + /// It makes the notifier only empty because the copiable
4.199 + /// notifier's observers have to be registered still into that registry.
4.200 + AlterationNotifier& operator=(const AlterationNotifier&) {
4.201 + typename Container::iterator it;
4.202 + for (it = container.begin(); it != container.end(); ++it) {
4.203 + (*it)->registry = 0;
4.204 + }
4.205 + }
4.206 +
4.207 + /// Destructor.
4.208 +
4.209 + /// Destructor of the AlterationNotifier.
4.210 + ///
4.211 + ~AlterationNotifier() {
4.212 + typename Container::iterator it;
4.213 + for (it = container.begin(); it != container.end(); ++it) {
4.214 + (*it)->registry = 0;
4.215 + }
4.216 + }
4.217 +
4.218 +
4.219 + protected:
4.220 +
4.221 + void attach(ObserverBase& observer) {
4.222 + container.push_back(&observer);
4.223 + observer.registry = this;
4.224 + observer.registry_index = container.size()-1;
4.225 + }
4.226 +
4.227 + void detach(ObserverBase& base) {
4.228 + container.back()->registry_index = base.registry_index;
4.229 + container[base.registry_index] = container.back();
4.230 + container.pop_back();
4.231 + base.registry = 0;
4.232 + }
4.233 +
4.234 + public:
4.235 +
4.236 + /// Notifies all the registered observers about an Item added to the container.
4.237 +
4.238 + /// It notifies all the registered observers about an Item added to the container.
4.239 + ///
4.240 + void add(const Item& key) {
4.241 + typename Container::iterator it;
4.242 + for (it = container.begin(); it != container.end(); ++it) {
4.243 + (*it)->add(key);
4.244 + }
4.245 + }
4.246 +
4.247 + /// Notifies all the registered observers about an Item erased from the container.
4.248 +
4.249 + /// It notifies all the registered observers about an Item erased from the container.
4.250 + ///
4.251 + void erase(const Item& key) {
4.252 + typename Container::iterator it;
4.253 + for (it = container.begin(); it != container.end(); ++it) {
4.254 + (*it)->erase(key);
4.255 + }
4.256 + }
4.257 +
4.258 +
4.259 + /// Notifies all the registered observers about the container is built.
4.260 +
4.261 + /// Notifies all the registered observers about the container is built
4.262 + /// from an empty container.
4.263 + void build() {
4.264 + typename Container::iterator it;
4.265 + for (it = container.begin(); it != container.end(); ++it) {
4.266 + (*it)->build();
4.267 + }
4.268 + }
4.269 +
4.270 +
4.271 + /// Notifies all the registered observers about all Items are erased.
4.272 +
4.273 + /// Notifies all the registered observers about all Items are erased
4.274 + /// from the container.
4.275 + void clear() {
4.276 + typename Container::iterator it;
4.277 + for (it = container.begin(); it != container.end(); ++it) {
4.278 + (*it)->clear();
4.279 + }
4.280 + }
4.281 + };
4.282 +
4.283 +
4.284 + /// \brief Class to extend a graph with the functionality of alteration
4.285 + /// observing.
4.286 + ///
4.287 + /// AlterableGraphExtender extends the _Base graphs functionality with
4.288 + /// the possibility of alteration observing. It defines two observer
4.289 + /// registrys for the nodes and mapes.
4.290 + ///
4.291 + /// \todo Document what "alteration observing" is. And probably find a
4.292 + /// better (shorter) name.
4.293 + ///
4.294 + /// \param _Base is the base class to extend.
4.295 + ///
4.296 + /// \pre _Base is conform to the BaseGraphComponent concept.
4.297 + ///
4.298 + /// \post AlterableGraphExtender<_Base> is conform to the
4.299 + /// AlterableGraphComponent concept.
4.300 + ///
4.301 + /// \author Balazs Dezso
4.302 +
4.303 + template <typename _Base>
4.304 + class AlterableGraphExtender : public _Base {
4.305 + public:
4.306 +
4.307 + typedef AlterableGraphExtender Graph;
4.308 + typedef _Base Parent;
4.309 +
4.310 + typedef typename Parent::Node Node;
4.311 + typedef typename Parent::Edge Edge;
4.312 +
4.313 + /// The edge observer registry.
4.314 + typedef AlterationNotifier<Edge> EdgeNotifier;
4.315 + /// The node observer registry.
4.316 + typedef AlterationNotifier<Node> NodeNotifier;
4.317 +
4.318 +
4.319 + protected:
4.320 +
4.321 + mutable EdgeNotifier edge_notifier;
4.322 +
4.323 + mutable NodeNotifier node_notifier;
4.324 +
4.325 + public:
4.326 +
4.327 + /// \brief Gives back the edge alteration notifier.
4.328 + ///
4.329 + /// Gives back the edge alteration notifier.
4.330 + EdgeNotifier& getNotifier(Edge) const {
4.331 + return edge_notifier;
4.332 + }
4.333 +
4.334 + /// \brief Gives back the node alteration notifier.
4.335 + ///
4.336 + /// Gives back the node alteration notifier.
4.337 + NodeNotifier& getNotifier(Node) const {
4.338 + return node_notifier;
4.339 + }
4.340 +
4.341 + ~AlterableGraphExtender() {
4.342 + node_notifier.clear();
4.343 + edge_notifier.clear();
4.344 + }
4.345 +
4.346 + };
4.347 +
4.348 + /// \brief Class to extend an undirected graph with the functionality of
4.349 + /// alteration observing.
4.350 + ///
4.351 + /// \todo Document.
4.352 + ///
4.353 + /// \sa AlterableGraphExtender
4.354 + ///
4.355 + /// \bug This should be done some other way. Possibilities: template
4.356 + /// specialization (not very easy, if at all possible); some kind of
4.357 + /// enable_if boost technique?
4.358 +
4.359 + template <typename _Base>
4.360 + class AlterableUndirGraphExtender
4.361 + : public AlterableGraphExtender<_Base> {
4.362 + public:
4.363 +
4.364 + typedef AlterableUndirGraphExtender Graph;
4.365 + typedef AlterableGraphExtender<_Base> Parent;
4.366 +
4.367 + typedef typename Parent::UndirEdge UndirEdge;
4.368 +
4.369 + /// The edge observer registry.
4.370 + typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
4.371 +
4.372 + protected:
4.373 +
4.374 + mutable UndirEdgeNotifier undir_edge_notifier;
4.375 +
4.376 + public:
4.377 +
4.378 + using Parent::getNotifier;
4.379 + UndirEdgeNotifier& getNotifier(UndirEdge) const {
4.380 + return undir_edge_notifier;
4.381 + }
4.382 +
4.383 + ~AlterableUndirGraphExtender() {
4.384 + undir_edge_notifier.clear();
4.385 + }
4.386 + };
4.387 +
4.388 +/// @}
4.389 +
4.390 +
4.391 +}
4.392 +
4.393 +#endif
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/lemon/bits/array_map.h Tue Apr 05 12:30:46 2005 +0000
5.3 @@ -0,0 +1,377 @@
5.4 +/* -*- C++ -*-
5.5 + * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
5.6 + *
5.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
5.9 + *
5.10 + * Permission to use, modify and distribute this software is granted
5.11 + * provided that this copyright notice appears in all copies. For
5.12 + * precise terms see the accompanying LICENSE file.
5.13 + *
5.14 + * This software is provided "AS IS" with no warranty of any kind,
5.15 + * express or implied, and with no claim as to its suitability for any
5.16 + * purpose.
5.17 + *
5.18 + */
5.19 +
5.20 +#ifndef LEMON_ARRAY_MAP_H
5.21 +#define LEMON_ARRAY_MAP_H
5.22 +
5.23 +#include <memory>
5.24 +#include <lemon/bits/map_iterator.h>
5.25 +
5.26 +///\ingroup graphmaps
5.27 +///\file
5.28 +///\brief Graph maps that construates and destruates
5.29 +///their elements dynamically.
5.30 +
5.31 +namespace lemon {
5.32 +
5.33 +
5.34 + /// \addtogroup graphmaps
5.35 + /// @{
5.36 +
5.37 + /** The ArrayMap template class is graph map structure what
5.38 + * automatically updates the map when a key is added to or erased from
5.39 + * the map. This map factory uses the allocators to implement
5.40 + * the container functionality.
5.41 + *
5.42 + * The template parameter is the AlterationNotifier that the maps
5.43 + * will belong to and the Value.
5.44 + */
5.45 +
5.46 + template <typename _Graph,
5.47 + typename _Item,
5.48 + typename _Value>
5.49 + class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
5.50 +
5.51 + typedef _Item Item;
5.52 + public:
5.53 +
5.54 + /// The graph type of the maps.
5.55 + typedef _Graph Graph;
5.56 + /// The key type of the maps.
5.57 + typedef _Item Key;
5.58 +
5.59 + typedef AlterationNotifier<_Item> Registry;
5.60 +
5.61 + /// The MapBase of the Map which imlements the core regisitry function.
5.62 + typedef typename Registry::ObserverBase Parent;
5.63 +
5.64 + /// The value type of the map.
5.65 + typedef _Value Value;
5.66 +
5.67 +
5.68 + private:
5.69 + typedef std::allocator<Value> Allocator;
5.70 +
5.71 +
5.72 + public:
5.73 +
5.74 + /** Graph and Registry initialized map constructor.
5.75 + */
5.76 + ArrayMap(const Graph& _g) : graph(&_g) {
5.77 + Item it;
5.78 + attach(_g.getNotifier(Item()));
5.79 + allocate_memory();
5.80 + for (graph->first(it); it != INVALID; graph->next(it)) {
5.81 + int id = graph->id(it);;
5.82 + allocator.construct(&(values[id]), Value());
5.83 + }
5.84 + }
5.85 +
5.86 + /// Constructor to use default value to initialize the map.
5.87 +
5.88 + /// It constrates a map and initialize all of the the map.
5.89 +
5.90 + ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
5.91 + Item it;
5.92 + attach(_g.getNotifier(_Item()));
5.93 + allocate_memory();
5.94 + for (graph->first(it); it != INVALID; graph->next(it)) {
5.95 + int id = graph->id(it);;
5.96 + allocator.construct(&(values[id]), _v);
5.97 + }
5.98 + }
5.99 +
5.100 + /** Constructor to copy a map of the same map type.
5.101 + */
5.102 + ArrayMap(const ArrayMap& copy) {
5.103 + if (copy.attached()) {
5.104 + attach(*copy.getRegistry());
5.105 + }
5.106 + capacity = copy.capacity;
5.107 + if (capacity == 0) return;
5.108 + values = allocator.allocate(capacity);
5.109 + Item it;
5.110 + for (graph->first(it); it != INVALID; graph->next(it)) {
5.111 + int id = graph->id(it);;
5.112 + allocator.construct(&(values[id]), copy.values[id]);
5.113 + }
5.114 + }
5.115 +
5.116 + using Parent::attach;
5.117 + using Parent::detach;
5.118 + using Parent::attached;
5.119 +
5.120 + /** Assign operator to copy a map of the same map type.
5.121 + */
5.122 + ArrayMap& operator=(const ArrayMap& copy) {
5.123 + if (© == this) return *this;
5.124 +
5.125 + if (graph != copy.graph) {
5.126 + if (attached()) {
5.127 + clear();
5.128 + detach();
5.129 + }
5.130 + if (copy.attached()) {
5.131 + attach(*copy.getRegistry());
5.132 + }
5.133 + capacity = copy.capacity;
5.134 + if (capacity == 0) return *this;
5.135 + values = allocator.allocate(capacity);
5.136 + }
5.137 +
5.138 + Item it;
5.139 + for (graph->first(it); it != INVALID; graph->next(it)) {
5.140 + int id = graph->id(it);;
5.141 + allocator.construct(&(values[id]), copy.values[id]);
5.142 + }
5.143 +
5.144 + return *this;
5.145 + }
5.146 +
5.147 + /** The destructor of the map.
5.148 + */
5.149 + virtual ~ArrayMap() {
5.150 + if (attached()) {
5.151 + clear();
5.152 + detach();
5.153 + }
5.154 + }
5.155 +
5.156 +
5.157 + /**
5.158 + * The subscript operator. The map can be subscripted by the
5.159 + * actual keys of the graph.
5.160 + */
5.161 + Value& operator[](const Key& key) {
5.162 + int id = graph->id(key);
5.163 + return values[id];
5.164 + }
5.165 +
5.166 + /**
5.167 + * The const subscript operator. The map can be subscripted by the
5.168 + * actual keys of the graph.
5.169 + */
5.170 + const Value& operator[](const Key& key) const {
5.171 + int id = graph->id(key);
5.172 + return values[id];
5.173 + }
5.174 +
5.175 + /** Setter function of the map. Equivalent with map[key] = val.
5.176 + * This is a compatibility feature with the not dereferable maps.
5.177 + */
5.178 + void set(const Key& key, const Value& val) {
5.179 + (*this)[key] = val;
5.180 + }
5.181 +
5.182 + /** Add a new key to the map. It called by the map registry.
5.183 + */
5.184 + void add(const Key& key) {
5.185 + int id = graph->id(key);
5.186 + if (id >= capacity) {
5.187 + int new_capacity = (capacity == 0 ? 1 : capacity);
5.188 + while (new_capacity <= id) {
5.189 + new_capacity <<= 1;
5.190 + }
5.191 + Value* new_values = allocator.allocate(new_capacity);
5.192 + Item it;
5.193 + for (graph->first(it); it != INVALID; graph->next(it)) {
5.194 + int jd = graph->id(it);;
5.195 + if (id != jd) {
5.196 + allocator.construct(&(new_values[jd]), values[jd]);
5.197 + allocator.destroy(&(values[jd]));
5.198 + }
5.199 + }
5.200 + if (capacity != 0) allocator.deallocate(values, capacity);
5.201 + values = new_values;
5.202 + capacity = new_capacity;
5.203 + }
5.204 + allocator.construct(&(values[id]), Value());
5.205 + }
5.206 +
5.207 + /** Erase a key from the map. It called by the map registry.
5.208 + */
5.209 + void erase(const Key& key) {
5.210 + int id = graph->id(key);
5.211 + allocator.destroy(&(values[id]));
5.212 + }
5.213 +
5.214 + void build() {
5.215 + allocate_memory();
5.216 + Item it;
5.217 + for (graph->first(it); it != INVALID; graph->next(it)) {
5.218 + int id = graph->id(it);;
5.219 + allocator.construct(&(values[id]), Value());
5.220 + }
5.221 + }
5.222 +
5.223 + void clear() {
5.224 + if (capacity != 0) {
5.225 + Item it;
5.226 + for (graph->first(it); it != INVALID; graph->next(it)) {
5.227 + int id = graph->id(it);;
5.228 + allocator.destroy(&(values[id]));
5.229 + }
5.230 + allocator.deallocate(values, capacity);
5.231 + capacity = 0;
5.232 + }
5.233 + }
5.234 +
5.235 + const Graph* getGraph() {
5.236 + return graph;
5.237 + }
5.238 +
5.239 +// /// The stl compatible pair iterator of the map.
5.240 +// typedef MapIterator<ArrayMap> Iterator;
5.241 +// /// The stl compatible const pair iterator of the map.
5.242 +// typedef MapConstIterator<ArrayMap> ConstIterator;
5.243 +
5.244 +// /** Returns the begin iterator of the map.
5.245 +// */
5.246 +// Iterator begin() {
5.247 +// return Iterator(*this, KeyIt(*MapBase::getGraph()));
5.248 +// }
5.249 +
5.250 +// /** Returns the end iterator of the map.
5.251 +// */
5.252 +// Iterator end() {
5.253 +// return Iterator(*this, INVALID);
5.254 +// }
5.255 +
5.256 +// /** Returns the begin ConstIterator of the map.
5.257 +// */
5.258 +// ConstIterator begin() const {
5.259 +// return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
5.260 +// }
5.261 +
5.262 +// /** Returns the end const_iterator of the map.
5.263 +// */
5.264 +// ConstIterator end() const {
5.265 +// return ConstIterator(*this, INVALID);
5.266 +// }
5.267 +
5.268 +// /// The KeySet of the Map.
5.269 +// typedef MapConstKeySet<ArrayMap> ConstKeySet;
5.270 +
5.271 +// /// KeySet getter function.
5.272 +// ConstKeySet keySet() const {
5.273 +// return ConstKeySet(*this);
5.274 +// }
5.275 +
5.276 +// /// The ConstValueSet of the Map.
5.277 +// typedef MapConstValueSet<ArrayMap> ConstValueSet;
5.278 +
5.279 +// /// ConstValueSet getter function.
5.280 +// ConstValueSet valueSet() const {
5.281 +// return ConstValueSet(*this);
5.282 +// }
5.283 +
5.284 +// /// The ValueSet of the Map.
5.285 +// typedef MapValueSet<ArrayMap> ValueSet;
5.286 +
5.287 +// /// ValueSet getter function.
5.288 +// ValueSet valueSet() {
5.289 +// return ValueSet(*this);
5.290 +// }
5.291 +
5.292 + private:
5.293 +
5.294 + void allocate_memory() {
5.295 + int max_id = graph->maxId(_Item());
5.296 + if (max_id == -1) {
5.297 + capacity = 0;
5.298 + values = 0;
5.299 + return;
5.300 + }
5.301 + capacity = 1;
5.302 + while (capacity <= max_id) {
5.303 + capacity <<= 1;
5.304 + }
5.305 + values = allocator.allocate(capacity);
5.306 + }
5.307 +
5.308 + const Graph* graph;
5.309 + int capacity;
5.310 + Value* values;
5.311 + Allocator allocator;
5.312 +
5.313 + };
5.314 +
5.315 + template <typename _Base>
5.316 + class ArrayMappableGraphExtender : public _Base {
5.317 + public:
5.318 +
5.319 + typedef ArrayMappableGraphExtender<_Base> Graph;
5.320 + typedef _Base Parent;
5.321 +
5.322 + typedef typename Parent::Node Node;
5.323 + typedef typename Parent::NodeIt NodeIt;
5.324 + typedef typename Parent::NodeNotifier NodeObserverRegistry;
5.325 +
5.326 + typedef typename Parent::Edge Edge;
5.327 + typedef typename Parent::EdgeIt EdgeIt;
5.328 + typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
5.329 +
5.330 +
5.331 +
5.332 + template <typename _Value>
5.333 + class NodeMap
5.334 + : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > {
5.335 + public:
5.336 + typedef ArrayMappableGraphExtender<_Base> Graph;
5.337 +
5.338 + typedef typename Graph::Node Node;
5.339 + typedef typename Graph::NodeIt NodeIt;
5.340 +
5.341 + typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent;
5.342 +
5.343 + //typedef typename Parent::Graph Graph;
5.344 + typedef typename Parent::Value Value;
5.345 +
5.346 + NodeMap(const Graph& g)
5.347 + : Parent(g) {}
5.348 + NodeMap(const Graph& g, const Value& v)
5.349 + : Parent(g, v) {}
5.350 +
5.351 + };
5.352 +
5.353 + template <typename _Value>
5.354 + class EdgeMap
5.355 + : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > {
5.356 + public:
5.357 + typedef ArrayMappableGraphExtender<_Base> Graph;
5.358 +
5.359 + typedef typename Graph::Edge Edge;
5.360 + typedef typename Graph::EdgeIt EdgeIt;
5.361 +
5.362 + typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent;
5.363 +
5.364 + //typedef typename Parent::Graph Graph;
5.365 + typedef typename Parent::Value Value;
5.366 +
5.367 + EdgeMap(const Graph& g)
5.368 + : Parent(g) {}
5.369 + EdgeMap(const Graph& g, const Value& v)
5.370 + : Parent(g, v) {}
5.371 +
5.372 + };
5.373 +
5.374 + };
5.375 +
5.376 +/// @}
5.377 +
5.378 +}
5.379 +
5.380 +#endif //LEMON_ARRAY_MAP_H
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/lemon/bits/clearable_graph_extender.h Tue Apr 05 12:30:46 2005 +0000
6.3 @@ -0,0 +1,49 @@
6.4 +// -*- c++ -*-
6.5 +
6.6 +#ifndef LEMON_CLEARABLE_GRAPH_EXTENDER_H
6.7 +#define LEMON_CLEARABLE_GRAPH_EXTENDER_H
6.8 +
6.9 +#include <lemon/invalid.h>
6.10 +
6.11 +
6.12 +namespace lemon {
6.13 +
6.14 + template <typename _Base>
6.15 + class ClearableGraphExtender : public _Base {
6.16 + public:
6.17 +
6.18 + typedef ClearableGraphExtender Graph;
6.19 + typedef _Base Parent;
6.20 + typedef typename Parent::Node Node;
6.21 + typedef typename Parent::Edge Edge;
6.22 +
6.23 + void clear() {
6.24 + Parent::getNotifier(Node()).clear();
6.25 + Parent::getNotifier(Edge()).clear();
6.26 + Parent::clear();
6.27 + }
6.28 +
6.29 + };
6.30 +
6.31 + template <typename _Base>
6.32 + class ClearableUndirGraphExtender : public _Base {
6.33 + public:
6.34 +
6.35 + typedef ClearableUndirGraphExtender Graph;
6.36 + typedef _Base Parent;
6.37 + typedef typename Parent::Node Node;
6.38 + typedef typename Parent::UndirEdge UndirEdge;
6.39 + typedef typename Parent::Edge Edge;
6.40 +
6.41 + void clear() {
6.42 + Parent::getNotifier(Node()).clear();
6.43 + Parent::getNotifier(UndirEdge()).clear();
6.44 + Parent::getNotifier(Edge()).clear();
6.45 + Parent::clear();
6.46 + }
6.47 +
6.48 + };
6.49 +
6.50 +}
6.51 +
6.52 +#endif
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/lemon/bits/default_map.h Tue Apr 05 12:30:46 2005 +0000
7.3 @@ -0,0 +1,230 @@
7.4 +/* -*- C++ -*-
7.5 + * src/lemon/default_map.h - Part of LEMON, a generic C++ optimization library
7.6 + *
7.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
7.9 + *
7.10 + * Permission to use, modify and distribute this software is granted
7.11 + * provided that this copyright notice appears in all copies. For
7.12 + * precise terms see the accompanying LICENSE file.
7.13 + *
7.14 + * This software is provided "AS IS" with no warranty of any kind,
7.15 + * express or implied, and with no claim as to its suitability for any
7.16 + * purpose.
7.17 + *
7.18 + */
7.19 +
7.20 +#ifndef LEMON_DEFAULT_MAP_H
7.21 +#define LEMON_DEFAULT_MAP_H
7.22 +
7.23 +
7.24 +#include <lemon/bits/array_map.h>
7.25 +#include <lemon/bits/vector_map.h>
7.26 +
7.27 +///\ingroup graphmaps
7.28 +///\file
7.29 +///\brief Graph maps that construct and destruct
7.30 +///their elements dynamically.
7.31 +
7.32 +namespace lemon {
7.33 +
7.34 +/// \addtogroup graphmaps
7.35 +/// @{
7.36 +
7.37 + /** The ArrayMap template class is graph map structure what
7.38 + * automatically updates the map when a key is added to or erased from
7.39 + * the map. This map uses the VectorMap if the Value is a primitive
7.40 + * type and the ArrayMap for the other cases.
7.41 + *
7.42 + * The template parameter is the MapRegistry that the maps
7.43 + * will belong to and the Value.
7.44 + */
7.45 +
7.46 +
7.47 +
7.48 + template <typename _Graph, typename _Item, typename _Value>
7.49 + struct DefaultMapSelector {
7.50 + typedef ArrayMap<_Graph, _Item, _Value> Map;
7.51 + };
7.52 +
7.53 + // bool
7.54 + template <typename _Graph, typename _Item>
7.55 + struct DefaultMapSelector<_Graph, _Item, bool> {
7.56 + typedef VectorMap<_Graph, _Item, bool> Map;
7.57 + };
7.58 +
7.59 + // char
7.60 + template <typename _Graph, typename _Item>
7.61 + struct DefaultMapSelector<_Graph, _Item, char> {
7.62 + typedef VectorMap<_Graph, _Item, char> Map;
7.63 + };
7.64 +
7.65 + template <typename _Graph, typename _Item>
7.66 + struct DefaultMapSelector<_Graph, _Item, signed char> {
7.67 + typedef VectorMap<_Graph, _Item, signed char> Map;
7.68 + };
7.69 +
7.70 + template <typename _Graph, typename _Item>
7.71 + struct DefaultMapSelector<_Graph, _Item, unsigned char> {
7.72 + typedef VectorMap<_Graph, _Item, unsigned char> Map;
7.73 + };
7.74 +
7.75 +
7.76 + // int
7.77 + template <typename _Graph, typename _Item>
7.78 + struct DefaultMapSelector<_Graph, _Item, signed int> {
7.79 + typedef VectorMap<_Graph, _Item, signed int> Map;
7.80 + };
7.81 +
7.82 + template <typename _Graph, typename _Item>
7.83 + struct DefaultMapSelector<_Graph, _Item, unsigned int> {
7.84 + typedef VectorMap<_Graph, _Item, unsigned int> Map;
7.85 + };
7.86 +
7.87 +
7.88 + // short
7.89 + template <typename _Graph, typename _Item>
7.90 + struct DefaultMapSelector<_Graph, _Item, signed short> {
7.91 + typedef VectorMap<_Graph, _Item, signed short> Map;
7.92 + };
7.93 +
7.94 + template <typename _Graph, typename _Item>
7.95 + struct DefaultMapSelector<_Graph, _Item, unsigned short> {
7.96 + typedef VectorMap<_Graph, _Item, unsigned short> Map;
7.97 + };
7.98 +
7.99 +
7.100 + // long
7.101 + template <typename _Graph, typename _Item>
7.102 + struct DefaultMapSelector<_Graph, _Item, signed long> {
7.103 + typedef VectorMap<_Graph, _Item, signed long> Map;
7.104 + };
7.105 +
7.106 + template <typename _Graph, typename _Item>
7.107 + struct DefaultMapSelector<_Graph, _Item, unsigned long> {
7.108 + typedef VectorMap<_Graph, _Item, unsigned long> Map;
7.109 + };
7.110 +
7.111 + // \todo handling long long type
7.112 +
7.113 +
7.114 + // float
7.115 + template <typename _Graph, typename _Item>
7.116 + struct DefaultMapSelector<_Graph, _Item, float> {
7.117 + typedef VectorMap<_Graph, _Item, float> Map;
7.118 + };
7.119 +
7.120 +
7.121 + // double
7.122 + template <typename _Graph, typename _Item>
7.123 + struct DefaultMapSelector<_Graph, _Item, double> {
7.124 + typedef VectorMap<_Graph, _Item, double> Map;
7.125 + };
7.126 +
7.127 +
7.128 + // long double
7.129 + template <typename _Graph, typename _Item>
7.130 + struct DefaultMapSelector<_Graph, _Item, long double> {
7.131 + typedef VectorMap<_Graph, _Item, long double> Map;
7.132 + };
7.133 +
7.134 +
7.135 + // pointer
7.136 + template <typename _Graph, typename _Item, typename _Ptr>
7.137 + struct DefaultMapSelector<_Graph, _Item, _Ptr*> {
7.138 + typedef VectorMap<_Graph, _Item, _Ptr*> Map;
7.139 + };
7.140 +
7.141 +
7.142 +
7.143 + template <
7.144 + typename _Graph,
7.145 + typename _Item,
7.146 + typename _Value>
7.147 + class DefaultMap
7.148 + : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
7.149 + public:
7.150 + typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
7.151 + typedef DefaultMap<_Graph, _Item, _Value> Map;
7.152 +
7.153 + typedef typename Parent::Graph Graph;
7.154 + typedef typename Parent::Value Value;
7.155 +
7.156 + DefaultMap(const Graph& _g) : Parent(_g) {}
7.157 + DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {}
7.158 + };
7.159 +
7.160 +
7.161 +
7.162 + template <typename _Base>
7.163 + class DefaultMappableGraphExtender : public _Base {
7.164 + public:
7.165 +
7.166 + typedef DefaultMappableGraphExtender<_Base> Graph;
7.167 + typedef _Base Parent;
7.168 +
7.169 + typedef typename Parent::Node Node;
7.170 + typedef typename Parent::NodeIt NodeIt;
7.171 +
7.172 + typedef typename Parent::Edge Edge;
7.173 + typedef typename Parent::EdgeIt EdgeIt;
7.174 +
7.175 +
7.176 + template <typename _Value>
7.177 + class NodeMap
7.178 + : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
7.179 + public:
7.180 + typedef DefaultMappableGraphExtender Graph;
7.181 + typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
7.182 +
7.183 + NodeMap(const Graph& _g)
7.184 + : Parent(_g) {}
7.185 + NodeMap(const Graph& _g, const _Value& _v)
7.186 + : Parent(_g, _v) {}
7.187 + };
7.188 +
7.189 + template <typename _Value>
7.190 + class EdgeMap
7.191 + : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
7.192 + public:
7.193 + typedef DefaultMappableGraphExtender Graph;
7.194 + typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
7.195 +
7.196 + EdgeMap(const Graph& _g)
7.197 + : Parent(_g) {}
7.198 + EdgeMap(const Graph& _g, const _Value& _v)
7.199 + : Parent(_g, _v) {}
7.200 + };
7.201 +
7.202 + };
7.203 +
7.204 + template <typename _Base>
7.205 + class MappableUndirGraphExtender :
7.206 + public DefaultMappableGraphExtender<_Base> {
7.207 + public:
7.208 +
7.209 + typedef MappableUndirGraphExtender Graph;
7.210 + typedef DefaultMappableGraphExtender<_Base> Parent;
7.211 +
7.212 + typedef typename Parent::UndirEdge UndirEdge;
7.213 +
7.214 + template <typename _Value>
7.215 + class UndirEdgeMap
7.216 + : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
7.217 + public:
7.218 + typedef MappableUndirGraphExtender Graph;
7.219 + typedef IterableMapExtender<
7.220 + DefaultMap<Graph, UndirEdge, _Value> > Parent;
7.221 +
7.222 + UndirEdgeMap(const Graph& _g)
7.223 + : Parent(_g) {}
7.224 + UndirEdgeMap(const Graph& _g, const _Value& _v)
7.225 + : Parent(_g, _v) {}
7.226 + };
7.227 +
7.228 +
7.229 + };
7.230 +
7.231 +}
7.232 +
7.233 +#endif
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/src/lemon/bits/erasable_graph_extender.h Tue Apr 05 12:30:46 2005 +0000
8.3 @@ -0,0 +1,80 @@
8.4 +// -*- c++ -*-
8.5 +
8.6 +#ifndef LEMON_ERASABLE_GRAPH_EXTENDER_H
8.7 +#define LEMON_ERASABLE_GRAPH_EXTENDER_H
8.8 +
8.9 +#include <lemon/invalid.h>
8.10 +
8.11 +
8.12 +namespace lemon {
8.13 +
8.14 + template <typename _Base>
8.15 + class ErasableGraphExtender : public _Base {
8.16 + public:
8.17 +
8.18 + typedef ErasableGraphExtender Graph;
8.19 + typedef _Base Parent;
8.20 +
8.21 + typedef typename Parent::Node Node;
8.22 + typedef typename Parent::Edge Edge;
8.23 +
8.24 + void erase(const Node& node) {
8.25 + Edge edge;
8.26 + Parent::firstOut(edge, node);
8.27 + while (edge != INVALID ) {
8.28 + erase(edge);
8.29 + Parent::firstOut(edge, node);
8.30 + }
8.31 +
8.32 + Parent::firstIn(edge, node);
8.33 + while (edge != INVALID ) {
8.34 + erase(edge);
8.35 + Parent::firstIn(edge, node);
8.36 + }
8.37 +
8.38 + Parent::getNotifier(Node()).erase(node);
8.39 + Parent::erase(node);
8.40 + }
8.41 +
8.42 + void erase(const Edge& edge) {
8.43 + Parent::getNotifier(Edge()).erase(edge);
8.44 + Parent::erase(edge);
8.45 + }
8.46 +
8.47 + };
8.48 +
8.49 + template <typename _Base>
8.50 + class ErasableUndirGraphExtender : public _Base {
8.51 + public:
8.52 +
8.53 + typedef ErasableUndirGraphExtender Graph;
8.54 + typedef _Base Parent;
8.55 +
8.56 + typedef typename Parent::Node Node;
8.57 + typedef typename Parent::UndirEdge UndirEdge;
8.58 + typedef typename Parent::Edge Edge;
8.59 +
8.60 + void erase(const Node& node) {
8.61 + Edge edge;
8.62 + Parent::firstOut(edge, node);
8.63 + while (edge != INVALID ) {
8.64 + erase(edge);
8.65 + Parent::firstOut(edge, node);
8.66 + }
8.67 +
8.68 + Parent::getNotifier(Node()).erase(node);
8.69 + Parent::erase(node);
8.70 + }
8.71 +
8.72 + void erase(const UndirEdge& uedge) {
8.73 + Parent::getNotifier(Edge()).erase(Edge(uedge,true));
8.74 + Parent::getNotifier(Edge()).erase(Edge(uedge,false));
8.75 + Parent::getNotifier(UndirEdge()).erase(uedge);
8.76 + Parent::erase(uedge);
8.77 + }
8.78 +
8.79 + };
8.80 +
8.81 +}
8.82 +
8.83 +#endif
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/src/lemon/bits/extendable_graph_extender.h Tue Apr 05 12:30:46 2005 +0000
9.3 @@ -0,0 +1,65 @@
9.4 +// -*- c++ -*-
9.5 +
9.6 +#ifndef LEMON_EXTENDABLE_GRAPH_EXTENDER_H
9.7 +#define LEMON_EXTENDABLE_GRAPH_EXTENDER_H
9.8 +
9.9 +namespace lemon {
9.10 +
9.11 + template <typename _Base>
9.12 + class ExtendableGraphExtender : public _Base {
9.13 + public:
9.14 +
9.15 + typedef ExtendableGraphExtender Graph;
9.16 + typedef _Base Parent;
9.17 +
9.18 + typedef typename Parent::Node Node;
9.19 + typedef typename Parent::Edge Edge;
9.20 +
9.21 + Node addNode() {
9.22 + Node node = Parent::addNode();
9.23 + Parent::getNotifier(Node()).add(node);
9.24 + return node;
9.25 + }
9.26 +
9.27 + Edge addEdge(const Node& from, const Node& to) {
9.28 + Edge edge = Parent::addEdge(from, to);
9.29 + Parent::getNotifier(Edge()).add(edge);
9.30 + return edge;
9.31 + }
9.32 +
9.33 + };
9.34 +
9.35 + template <typename _Base>
9.36 + class ExtendableUndirGraphExtender : public _Base {
9.37 + public:
9.38 +
9.39 + typedef ExtendableUndirGraphExtender Graph;
9.40 + typedef _Base Parent;
9.41 +
9.42 + typedef typename Parent::Node Node;
9.43 + typedef typename Parent::Edge Edge;
9.44 + typedef typename Parent::UndirEdge UndirEdge;
9.45 +
9.46 + Node addNode() {
9.47 + Node node = Parent::addNode();
9.48 + Parent::getNotifier(Node()).add(node);
9.49 + return node;
9.50 + }
9.51 +
9.52 + UndirEdge addEdge(const Node& from, const Node& to) {
9.53 + UndirEdge uedge = Parent::addEdge(from, to);
9.54 + Parent::getNotifier(UndirEdge()).add(uedge);
9.55 +
9.56 + Edge edge_forward(uedge, true);
9.57 + Edge edge_backward(uedge, false);
9.58 + Parent::getNotifier(Edge()).add(edge_forward);
9.59 + Parent::getNotifier(Edge()).add(edge_backward);
9.60 +
9.61 + return uedge;
9.62 + }
9.63 +
9.64 + };
9.65 +
9.66 +}
9.67 +
9.68 +#endif
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/src/lemon/bits/extended_pair.h Tue Apr 05 12:30:46 2005 +0000
10.3 @@ -0,0 +1,80 @@
10.4 +/* -*- C++ -*-
10.5 + * src/lemon/extended_pair.h - Part of LEMON, a generic C++ optimization library
10.6 + *
10.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
10.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
10.9 + *
10.10 + * Permission to use, modify and distribute this software is granted
10.11 + * provided that this copyright notice appears in all copies. For
10.12 + * precise terms see the accompanying LICENSE file.
10.13 + *
10.14 + * This software is provided "AS IS" with no warranty of any kind,
10.15 + * express or implied, and with no claim as to its suitability for any
10.16 + * purpose.
10.17 + *
10.18 + */
10.19 +
10.20 +#ifndef LEMON_EXTENDED_PAIR_H
10.21 +#define LEMON_EXTENDED_PAIR_H
10.22 +
10.23 +template <typename T1, typename A1, typename T2, typename A2>
10.24 +struct extended_pair {
10.25 + typedef T1 first_type;
10.26 + typedef T2 second_type;
10.27 +
10.28 + extended_pair() : first(), second() {}
10.29 +
10.30 + extended_pair(A1 f, A2 s) : first(f), second(s) {}
10.31 +
10.32 + template <class Pair>
10.33 + extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {}
10.34 +
10.35 + T1 first;
10.36 + T2 second;
10.37 +};
10.38 +
10.39 +template <typename T1, typename T2,
10.40 + typename LA1, typename LA2, typename RA1, typename RA2>
10.41 +bool operator==(const extended_pair<T1, LA1, T2, LA2>& left,
10.42 + const extended_pair<T1, RA1, T2, RA2>& right) {
10.43 + return left.first == right.first && left.second == right.second;
10.44 +}
10.45 +
10.46 +template <typename T1, typename T2,
10.47 + typename LA1, typename LA2, typename RA1, typename RA2>
10.48 +bool operator!=(const extended_pair<T1, LA1, T2, LA2>& left,
10.49 + const extended_pair<T1, RA1, T2, RA2>& right) {
10.50 + return !(left == right);
10.51 +}
10.52 +
10.53 +template <typename T1, typename T2,
10.54 + typename LA1, typename LA2, typename RA1, typename RA2>
10.55 +bool operator<(const extended_pair<T1, LA1, T2, LA2>& left,
10.56 + const extended_pair<T1, RA1, T2, RA2>& right) {
10.57 + return left.first < right.first ||
10.58 + (!(right.first<left.first) && left.second < right.second);
10.59 +}
10.60 +
10.61 +template <typename T1, typename T2,
10.62 + typename LA1, typename LA2, typename RA1, typename RA2>
10.63 +bool operator>(const extended_pair<T1, LA1, T2, LA2>& left,
10.64 + const extended_pair<T1, RA1, T2, RA2>& right) {
10.65 + return right < left;
10.66 +}
10.67 +
10.68 +template <typename T1, typename T2,
10.69 + typename LA1, typename LA2, typename RA1, typename RA2>
10.70 +bool operator<=(const extended_pair<T1, LA1, T2, LA2>& left,
10.71 + const extended_pair<T1, RA1, T2, RA2>& right) {
10.72 + return !(right > left);
10.73 +}
10.74 +
10.75 +template <typename T1, typename T2,
10.76 + typename LA1, typename LA2, typename RA1, typename RA2>
10.77 +bool operator>=(const extended_pair<T1, LA1, T2, LA2>& left,
10.78 + const extended_pair<T1, RA1, T2, RA2>& right) {
10.79 + return !(right < left);
10.80 +}
10.81 +
10.82 +
10.83 +#endif
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/src/lemon/bits/iterable_graph_extender.h Tue Apr 05 12:30:46 2005 +0000
11.3 @@ -0,0 +1,250 @@
11.4 +// -*- c++ -*-
11.5 +#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
11.6 +#define LEMON_ITERABLE_GRAPH_EXTENDER_H
11.7 +
11.8 +#include <lemon/invalid.h>
11.9 +
11.10 +namespace lemon {
11.11 +
11.12 + template <typename _Base>
11.13 + class IterableGraphExtender : public _Base {
11.14 + public:
11.15 +
11.16 + typedef _Base Parent;
11.17 + typedef IterableGraphExtender<_Base> Graph;
11.18 +
11.19 + typedef typename Parent::Node Node;
11.20 + typedef typename Parent::Edge Edge;
11.21 +
11.22 +
11.23 + class NodeIt : public Node {
11.24 + const Graph* graph;
11.25 + public:
11.26 +
11.27 + NodeIt() {}
11.28 +
11.29 + NodeIt(Invalid i) : Node(i) { }
11.30 +
11.31 + explicit NodeIt(const Graph& _graph) : graph(&_graph) {
11.32 + _graph.first(*static_cast<Node*>(this));
11.33 + }
11.34 +
11.35 + NodeIt(const Graph& _graph, const Node& node)
11.36 + : Node(node), graph(&_graph) {}
11.37 +
11.38 + NodeIt& operator++() {
11.39 + graph->next(*this);
11.40 + return *this;
11.41 + }
11.42 +
11.43 + };
11.44 +
11.45 +
11.46 + class EdgeIt : public Edge {
11.47 + const Graph* graph;
11.48 + public:
11.49 +
11.50 + EdgeIt() { }
11.51 +
11.52 + EdgeIt(Invalid i) : Edge(i) { }
11.53 +
11.54 + explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
11.55 + _graph.first(*static_cast<Edge*>(this));
11.56 + }
11.57 +
11.58 + EdgeIt(const Graph& _graph, const Edge& e) :
11.59 + Edge(e), graph(&_graph) { }
11.60 +
11.61 + EdgeIt& operator++() {
11.62 + graph->next(*this);
11.63 + return *this;
11.64 + }
11.65 +
11.66 + };
11.67 +
11.68 +
11.69 + class OutEdgeIt : public Edge {
11.70 + const Graph* graph;
11.71 + public:
11.72 +
11.73 + OutEdgeIt() { }
11.74 +
11.75 + OutEdgeIt(Invalid i) : Edge(i) { }
11.76 +
11.77 + OutEdgeIt(const Graph& _graph, const Node& node)
11.78 + : graph(&_graph) {
11.79 + _graph.firstOut(*this, node);
11.80 + }
11.81 +
11.82 + OutEdgeIt(const Graph& _graph, const Edge& edge)
11.83 + : Edge(edge), graph(&_graph) {}
11.84 +
11.85 + OutEdgeIt& operator++() {
11.86 + graph->nextOut(*this);
11.87 + return *this;
11.88 + }
11.89 +
11.90 + };
11.91 +
11.92 +
11.93 + class InEdgeIt : public Edge {
11.94 + const Graph* graph;
11.95 + public:
11.96 +
11.97 + InEdgeIt() { }
11.98 +
11.99 + InEdgeIt(Invalid i) : Edge(i) { }
11.100 +
11.101 + InEdgeIt(const Graph& _graph, const Node& node)
11.102 + : graph(&_graph) {
11.103 + _graph.firstIn(*this, node);
11.104 + }
11.105 +
11.106 + InEdgeIt(const Graph& _graph, const Edge& edge) :
11.107 + Edge(edge), graph(&_graph) {}
11.108 +
11.109 + InEdgeIt& operator++() {
11.110 + graph->nextIn(*this);
11.111 + return *this;
11.112 + }
11.113 +
11.114 + };
11.115 +
11.116 + /// Base node of the iterator
11.117 + ///
11.118 + /// Returns the base node (ie. the source in this case) of the iterator
11.119 + ///
11.120 + /// \todo Document in the concept!
11.121 + Node baseNode(const OutEdgeIt &e) const {
11.122 + return source(e);
11.123 + }
11.124 + /// Running node of the iterator
11.125 + ///
11.126 + /// Returns the running node (ie. the target in this case) of the
11.127 + /// iterator
11.128 + ///
11.129 + /// \todo Document in the concept!
11.130 + Node runningNode(const OutEdgeIt &e) const {
11.131 + return target(e);
11.132 + }
11.133 +
11.134 + /// Base node of the iterator
11.135 + ///
11.136 + /// Returns the base node (ie. the target in this case) of the iterator
11.137 + ///
11.138 + /// \todo Document in the concept!
11.139 + Node baseNode(const InEdgeIt &e) const {
11.140 + return target(e);
11.141 + }
11.142 + /// Running node of the iterator
11.143 + ///
11.144 + /// Returns the running node (ie. the source in this case) of the
11.145 + /// iterator
11.146 + ///
11.147 + /// \todo Document in the concept!
11.148 + Node runningNode(const InEdgeIt &e) const {
11.149 + return source(e);
11.150 + }
11.151 +
11.152 + using Parent::first;
11.153 +
11.154 + private:
11.155 +
11.156 + // /// \todo When (and if) we change the iterators concept to use operator*,
11.157 + // /// then the following shadowed methods will become superfluous.
11.158 + // /// But for now these are important safety measures.
11.159 +
11.160 + // void first(NodeIt &) const;
11.161 + // void first(EdgeIt &) const;
11.162 + // void first(OutEdgeIt &) const;
11.163 + // void first(InEdgeIt &) const;
11.164 +
11.165 + };
11.166 +
11.167 +
11.168 +
11.169 +
11.170 +
11.171 +
11.172 + template <typename _Base>
11.173 + class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
11.174 + public:
11.175 +
11.176 + typedef IterableGraphExtender<_Base> Parent;
11.177 + typedef IterableUndirGraphExtender<_Base> Graph;
11.178 + typedef typename Parent::Node Node;
11.179 +
11.180 + typedef typename Parent::UndirEdge UndirEdge;
11.181 +
11.182 + class UndirEdgeIt : public Parent::UndirEdge {
11.183 + const Graph* graph;
11.184 + public:
11.185 +
11.186 + UndirEdgeIt() { }
11.187 +
11.188 + UndirEdgeIt(Invalid i) : UndirEdge(i) { }
11.189 +
11.190 + explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
11.191 + _graph.first(*static_cast<UndirEdge*>(this));
11.192 + }
11.193 +
11.194 + UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :
11.195 + UndirEdge(e), graph(&_graph) { }
11.196 +
11.197 + UndirEdgeIt& operator++() {
11.198 + graph->next(*this);
11.199 + return *this;
11.200 + }
11.201 +
11.202 + };
11.203 +
11.204 + class IncEdgeIt : public Parent::UndirEdge {
11.205 + const Graph* graph;
11.206 + bool forward;
11.207 + friend class IterableUndirGraphExtender;
11.208 + template <typename G>
11.209 + friend class UndirGraphExtender;
11.210 + public:
11.211 +
11.212 + IncEdgeIt() { }
11.213 +
11.214 + IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
11.215 +
11.216 + IncEdgeIt(const Graph& _graph, const Node &n)
11.217 + : graph(&_graph)
11.218 + {
11.219 + _graph._dirFirstOut(*this, n);
11.220 + }
11.221 +
11.222 + IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
11.223 + : graph(&_graph), UndirEdge(ue)
11.224 + {
11.225 + forward = (_graph.source(ue) == n);
11.226 + }
11.227 +
11.228 + IncEdgeIt& operator++() {
11.229 + graph->_dirNextOut(*this);
11.230 + return *this;
11.231 + }
11.232 + };
11.233 +
11.234 + using Parent::baseNode;
11.235 + using Parent::runningNode;
11.236 +
11.237 + /// Base node of the iterator
11.238 + ///
11.239 + /// Returns the base node of the iterator
11.240 + Node baseNode(const IncEdgeIt &e) const {
11.241 + return _dirSource(e);
11.242 + }
11.243 + /// Running node of the iterator
11.244 + ///
11.245 + /// Returns the running node of the iterator
11.246 + Node runningNode(const IncEdgeIt &e) const {
11.247 + return _dirTarget(e);
11.248 + }
11.249 +
11.250 + };
11.251 +}
11.252 +
11.253 +#endif // LEMON_GRAPH_EXTENDER_H
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/src/lemon/bits/map_iterator.h Tue Apr 05 12:30:46 2005 +0000
12.3 @@ -0,0 +1,855 @@
12.4 +/* -*- C++ -*-
12.5 + * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library
12.6 + *
12.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
12.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
12.9 + *
12.10 + * Permission to use, modify and distribute this software is granted
12.11 + * provided that this copyright notice appears in all copies. For
12.12 + * precise terms see the accompanying LICENSE file.
12.13 + *
12.14 + * This software is provided "AS IS" with no warranty of any kind,
12.15 + * express or implied, and with no claim as to its suitability for any
12.16 + * purpose.
12.17 + *
12.18 + */
12.19 +
12.20 +#ifndef LEMON_MAP_ITERATOR_H
12.21 +#define LEMON_MAP_ITERATOR_H
12.22 +
12.23 +#include <iterator>
12.24 +
12.25 +#include <lemon/bits/extended_pair.h>
12.26 +#include <lemon/map_utils.h>
12.27 +
12.28 +///\ingroup graphmaps
12.29 +///\file
12.30 +///\brief Iterators on the maps.
12.31 +
12.32 +namespace lemon {
12.33 +
12.34 + /// \addtogroup graphmaps
12.35 + /// @{
12.36 +
12.37 + /** The base class all of the map iterators.
12.38 + * The class defines the typedefs of the iterators,
12.39 + * simple step functions and equality operators.
12.40 + */
12.41 +
12.42 + template <
12.43 + typename _Graph,
12.44 + typename _Item>
12.45 + class MapIteratorBase {
12.46 +
12.47 + protected:
12.48 +
12.49 + /// The key type of the iterator.
12.50 + typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
12.51 +
12.52 + ItemIt it;
12.53 +
12.54 + /// Default constructor.
12.55 + MapIteratorBase() {}
12.56 +
12.57 + /// ItemIt initialized MapIteratorBase constructor.
12.58 + MapIteratorBase(const ItemIt _it) : it(_it) {}
12.59 +
12.60 + public:
12.61 +
12.62 + /// Stepping forward in the map.
12.63 + void increment() {
12.64 + ++it;
12.65 + }
12.66 +
12.67 + /// The equality operator of the map.
12.68 + bool operator==(const MapIteratorBase& _it) const {
12.69 + return _it.it == it;
12.70 + }
12.71 +
12.72 + /// The not-equality operator of the map.
12.73 + bool operator!=(const MapIteratorBase& _it) const {
12.74 + return !(*this == _it);
12.75 + }
12.76 + };
12.77 +
12.78 +
12.79 + template <
12.80 + typename _Graph,
12.81 + typename _Item,
12.82 + typename _Map>
12.83 + class MapConstIterator;
12.84 +
12.85 + /** Compatible iterator with the stl maps' iterators.
12.86 + * It iterates on pairs of a key and a value.
12.87 + */
12.88 + template <
12.89 + typename _Graph,
12.90 + typename _Item,
12.91 + typename _Map>
12.92 + class MapIterator : public MapIteratorBase<_Graph, _Item> {
12.93 +
12.94 + friend class MapConstIterator<_Graph, _Item, _Map>;
12.95 +
12.96 +
12.97 + public:
12.98 +
12.99 + /// The iterator base class.
12.100 + typedef MapIteratorBase<_Graph, _Item> Parent;
12.101 +
12.102 + typedef _Item Item;
12.103 + typedef _Map Map;
12.104 + typedef _Graph Graph;
12.105 +
12.106 + protected:
12.107 +
12.108 + typedef typename Parent::ItemIt ItemIt;
12.109 +
12.110 + typedef typename ReferenceMapTraits<_Map>::Value MapValue;
12.111 + typedef typename ReferenceMapTraits<_Map>::Reference MapReference;
12.112 +
12.113 + public:
12.114 +
12.115 + /// The value type of the iterator.
12.116 + typedef extended_pair<Item, const Item&,
12.117 + MapValue, const MapValue&> Value;
12.118 +
12.119 + /// The reference type of the iterator.
12.120 + typedef extended_pair<const Item&, const Item&,
12.121 + MapReference, MapReference> Reference;
12.122 +
12.123 + /// Default constructor.
12.124 + MapIterator() {}
12.125 +
12.126 + /// Constructor to initalize the iterators returned
12.127 + /// by the begin() and end().
12.128 + MapIterator(Map& _map, const ItemIt& _it)
12.129 + : Parent(_it), map(&_map) {}
12.130 +
12.131 + /// Dereference operator for the iterator.
12.132 + Reference operator*() {
12.133 + return Reference(Parent::it, (*map)[Parent::it]);
12.134 + }
12.135 +
12.136 + /// The pointer type of the iterator.
12.137 + class Pointer {
12.138 + friend class MapIterator;
12.139 + protected:
12.140 + Reference data;
12.141 + Pointer(const Item& item, MapReference val)
12.142 + : data(item, val) {}
12.143 + public:
12.144 + Reference* operator->() {return &data;}
12.145 + };
12.146 +
12.147 + /// Arrow operator for the iterator.
12.148 + Pointer operator->() {
12.149 + return Pointer(Parent::it, (*map)[Parent::it]);
12.150 + }
12.151 +
12.152 + /// The pre increment operator of the iterator.
12.153 + MapIterator& operator++() {
12.154 + Parent::increment();
12.155 + return *this;
12.156 + }
12.157 +
12.158 + /// The post increment operator of the iterator.
12.159 + MapIterator operator++(int) {
12.160 + MapIterator tmp(*this);
12.161 + Parent::increment();
12.162 + return tmp;
12.163 + }
12.164 +
12.165 + protected:
12.166 +
12.167 + Map* map;
12.168 +
12.169 + public:
12.170 + // STL compatibility typedefs.
12.171 + typedef std::forward_iterator_tag iterator_category;
12.172 + typedef int difference_type;
12.173 + typedef Value value_type;
12.174 + typedef Reference reference;
12.175 + typedef Pointer pointer;
12.176 + };
12.177 +
12.178 + /** Compatible iterator with the stl maps' iterators.
12.179 + * It iterates on pairs of a key and a value.
12.180 + */
12.181 + template <
12.182 + typename _Graph,
12.183 + typename _Item,
12.184 + typename _Map>
12.185 + class MapConstIterator : public MapIteratorBase<_Graph, _Item> {
12.186 +
12.187 + public:
12.188 +
12.189 + /// The iterator base class.
12.190 + typedef MapIteratorBase<_Graph, _Item> Parent;
12.191 +
12.192 + typedef _Graph Graph;
12.193 + typedef _Item Item;
12.194 + typedef _Map Map;
12.195 +
12.196 + protected:
12.197 +
12.198 + typedef typename Parent::ItemIt ItemIt;
12.199 +
12.200 + typedef typename ReferenceMapTraits<_Map>::Value MapValue;
12.201 + typedef typename ReferenceMapTraits<_Map>::ConstReference
12.202 + MapReference;
12.203 +
12.204 + public:
12.205 +
12.206 + /// The value type of the iterator.
12.207 + typedef extended_pair<Item, const Item&,
12.208 + MapValue, const MapValue&> Value;
12.209 +
12.210 + /// The reference type of the iterator.
12.211 + typedef extended_pair<const Item&, const Item&,
12.212 + MapReference, MapReference> Reference;
12.213 +
12.214 + /// Default constructor.
12.215 + MapConstIterator() {}
12.216 +
12.217 + /// Constructor to initalize the iterators returned
12.218 + /// by the begin() and end().
12.219 + MapConstIterator(const Map& _map, const ItemIt& _it)
12.220 + : Parent(_it), map(&_map) {}
12.221 +
12.222 + /// Dereference operator for the iterator.
12.223 + Reference operator*() {
12.224 + return Reference(Parent::it, (*map)[Parent::it]);
12.225 + }
12.226 +
12.227 + /// The pointer type of the iterator.
12.228 + class Pointer {
12.229 + friend class MapConstIterator;
12.230 + protected:
12.231 + Reference data;
12.232 + Pointer(const Item& item, MapReference val)
12.233 + : data(item, val) {}
12.234 + public:
12.235 + Reference* operator->() {return &data;}
12.236 + };
12.237 +
12.238 + /// Arrow operator for the iterator.
12.239 + Pointer operator->() {
12.240 + return Pointer(Parent::it, ((*map)[Parent::it]));
12.241 + }
12.242 +
12.243 + /// The pre increment operator of the iterator.
12.244 + MapConstIterator& operator++() {
12.245 + Parent::increment();
12.246 + return *this;
12.247 + }
12.248 +
12.249 + /// The post increment operator of the iterator.
12.250 + MapConstIterator operator++(int) {
12.251 + MapConstIterator tmp(*this);
12.252 + Parent::increment();
12.253 + return tmp;
12.254 + }
12.255 +
12.256 + protected:
12.257 + const Map* map;
12.258 +
12.259 + public:
12.260 + // STL compatibility typedefs.
12.261 + typedef std::forward_iterator_tag iterator_category;
12.262 + typedef int difference_type;
12.263 + typedef Value value_type;
12.264 + typedef Reference reference;
12.265 + typedef Pointer pointer;
12.266 + };
12.267 +
12.268 + /** The class makes the ItemIt to an stl compatible iterator
12.269 + * with dereferencing operator.
12.270 + */
12.271 + template <
12.272 + typename _Graph,
12.273 + typename _Item>
12.274 + class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {
12.275 +
12.276 + public:
12.277 +
12.278 + /// The iterator base class.
12.279 + typedef MapIteratorBase<_Graph, _Item> Parent;
12.280 +
12.281 + typedef _Graph Graph;
12.282 + typedef _Item Item;
12.283 +
12.284 + protected:
12.285 + /// The iterator to iterate on the keys.
12.286 + typedef typename Parent::ItemIt ItemIt;
12.287 +
12.288 + public:
12.289 +
12.290 + typedef Item Value;
12.291 + typedef const Item& Reference;
12.292 + typedef const Item* Pointer;
12.293 +
12.294 + /// Default constructor.
12.295 + MapConstKeyIterator() {}
12.296 +
12.297 + /// ItemIt initialized iterator.
12.298 + MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}
12.299 +
12.300 + /// The pre increment operator of the iterator.
12.301 + MapConstKeyIterator& operator++() {
12.302 + Parent::increment();
12.303 + return *this;
12.304 + }
12.305 +
12.306 + /// The post increment operator of the iterator.
12.307 + MapConstKeyIterator operator++(int) {
12.308 + MapConstKeyIterator tmp(*this);
12.309 + Parent::increment();
12.310 + return tmp;
12.311 + }
12.312 +
12.313 + /// The dereferencing operator of the iterator.
12.314 + Item operator*() const {
12.315 + return static_cast<Item>(Parent::it);
12.316 + }
12.317 +
12.318 + public:
12.319 + // STL compatibility typedefs.
12.320 + typedef std::input_iterator_tag iterator_category;
12.321 + typedef int difference_type;
12.322 + typedef Value value_type;
12.323 + typedef Reference reference;
12.324 + typedef Pointer pointer;
12.325 + };
12.326 +
12.327 + template <
12.328 + typename _Graph,
12.329 + typename _Item,
12.330 + typename _Map>
12.331 + class MapConstValueIterator;
12.332 +
12.333 + /** MapValueIterator creates an stl compatible iterator
12.334 + * for the values.
12.335 + */
12.336 + template <
12.337 + typename _Graph,
12.338 + typename _Item,
12.339 + typename _Map>
12.340 + class MapValueIterator : public MapIteratorBase<_Graph, _Item> {
12.341 +
12.342 + friend class MapConstValueIterator<_Graph, _Item, _Map>;
12.343 +
12.344 + public:
12.345 +
12.346 + /// The iterator base class.
12.347 + typedef MapIteratorBase<_Graph, _Item> Parent;
12.348 +
12.349 + typedef _Graph Graph;
12.350 + typedef _Item Item;
12.351 + typedef _Map Map;
12.352 +
12.353 + protected:
12.354 +
12.355 + /// The iterator to iterate on the keys.
12.356 + typedef typename Parent::ItemIt ItemIt;
12.357 +
12.358 + /// The value type of the iterator.
12.359 + typedef typename ReferenceMapTraits<Map>::Value MapValue;
12.360 + /// The reference type of the iterator.
12.361 + typedef typename ReferenceMapTraits<Map>::Reference MapReference;
12.362 + /// The pointer type of the iterator.
12.363 + typedef typename ReferenceMapTraits<Map>::Pointer MapPointer;
12.364 +
12.365 + public:
12.366 +
12.367 + typedef MapValue Value;
12.368 + typedef MapReference Reference;
12.369 + typedef MapPointer Pointer;
12.370 +
12.371 + /// Default constructor.
12.372 + MapValueIterator() {}
12.373 +
12.374 + /// Map and ItemIt initialized iterator.
12.375 + MapValueIterator(Map& _map, const ItemIt& _it)
12.376 + : Parent(_it), map(&_map) {}
12.377 +
12.378 +
12.379 + /// The pre increment operator of the iterator.
12.380 + MapValueIterator& operator++() {
12.381 + Parent::increment();
12.382 + return *this;
12.383 + }
12.384 +
12.385 + /// The post increment operator of the iterator.
12.386 + MapValueIterator operator++(int) {
12.387 + MapValueIterator tmp(*this);
12.388 + Parent::increment();
12.389 + return tmp;
12.390 + }
12.391 +
12.392 + /// The dereferencing operator of the iterator.
12.393 + Reference operator*() const {
12.394 + return (*map)[Parent::it];
12.395 + }
12.396 +
12.397 + /// The arrow operator of the iterator.
12.398 + Pointer operator->() const {
12.399 + return &(operator*());
12.400 + }
12.401 +
12.402 + protected:
12.403 +
12.404 + Map* map;
12.405 +
12.406 + public:
12.407 + // STL compatibility typedefs.
12.408 + typedef std::forward_iterator_tag iterator_category;
12.409 + typedef int difference_type;
12.410 + typedef Value value_type;
12.411 + typedef Reference reference;
12.412 + typedef Pointer pointer;
12.413 + };
12.414 +
12.415 + /** MapValueIterator creates an stl compatible iterator
12.416 + * for the values.
12.417 + */
12.418 + template <
12.419 + typename _Graph,
12.420 + typename _Item,
12.421 + typename _Map>
12.422 + class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {
12.423 +
12.424 + public:
12.425 +
12.426 + /// The iterator base class.
12.427 + typedef MapIteratorBase<_Graph, _Item> Parent;
12.428 +
12.429 + typedef _Graph Graph;
12.430 + typedef _Item Item;
12.431 + typedef _Map Map;
12.432 +
12.433 + protected:
12.434 +
12.435 + /// The iterator to iterate on the keys.
12.436 + typedef typename Parent::ItemIt ItemIt;
12.437 +
12.438 + /// The value type of the iterator.
12.439 + typedef typename ReferenceMapTraits<Map>::Value MapValue;
12.440 + /// The reference type of the iterator.
12.441 + typedef typename ReferenceMapTraits<Map>::ConstReference MapReference;
12.442 + /// The pointer type of the iterator.
12.443 + typedef typename ReferenceMapTraits<Map>::ConstPointer MapPointer;
12.444 +
12.445 + public:
12.446 +
12.447 + typedef MapValue Value;
12.448 + typedef MapReference Reference;
12.449 + typedef MapPointer Pointer;
12.450 +
12.451 + /// Default constructor.
12.452 + MapConstValueIterator() {}
12.453 +
12.454 + /// Map and ItemIt initialized iterator.
12.455 + MapConstValueIterator(const Map& _map, const ItemIt& _it)
12.456 + : Parent(_it), map(&_map) {}
12.457 +
12.458 +
12.459 + /// The pre increment operator of the iterator.
12.460 + MapConstValueIterator& operator++() {
12.461 + Parent::increment();
12.462 + return *this;
12.463 + }
12.464 +
12.465 + /// The post increment operator of the iterator.
12.466 + MapConstValueIterator operator++(int) {
12.467 + MapConstValueIterator tmp(*this);
12.468 + Parent::increment();
12.469 + return tmp;
12.470 + }
12.471 +
12.472 + /// The dereferencing operator of the iterator.
12.473 + Reference operator*() const {
12.474 + return (*map)[Parent::it];
12.475 + }
12.476 +
12.477 + /// The arrow operator of the iterator.
12.478 + Pointer operator->() const {
12.479 + return &(operator*());
12.480 + }
12.481 +
12.482 + protected:
12.483 +
12.484 + const Map* map;
12.485 +
12.486 + public:
12.487 + // STL compatibility typedefs.
12.488 + typedef std::forward_iterator_tag iterator_category;
12.489 + typedef int difference_type;
12.490 + typedef Value value_type;
12.491 + typedef Reference reference;
12.492 + typedef Pointer pointer;
12.493 + };
12.494 +
12.495 +
12.496 + /** This class makes from a map an iteratable set
12.497 + * which contains all the keys of the map.
12.498 + */
12.499 + template <typename _Graph, typename _Item>
12.500 + class MapConstKeySet {
12.501 +
12.502 + public:
12.503 +
12.504 + typedef _Graph Graph;
12.505 + /// The key type of the iterator.
12.506 + typedef _Item Item;
12.507 + /// The iterator to iterate on the keys.
12.508 +
12.509 + protected:
12.510 +
12.511 + typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
12.512 +
12.513 + public:
12.514 +
12.515 + /// The map initialized const key set.
12.516 + MapConstKeySet(const Graph& _graph) : graph(&_graph) {}
12.517 +
12.518 + /// The const iterator of the set.
12.519 + typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;
12.520 +
12.521 + typedef typename ConstIterator::Value Value;
12.522 + /// The reference type of the iterator.
12.523 + typedef typename ConstIterator::Reference ConstReference;
12.524 + /// The pointer type of the iterator.
12.525 + typedef typename ConstIterator::Pointer ConstPointer;
12.526 +
12.527 + /// It gives back the const iterator pointed to the first element.
12.528 + ConstIterator begin() const {
12.529 + return ConstIterator(ItemIt(*graph));
12.530 + }
12.531 +
12.532 + /// It gives back the const iterator pointed to the first ivalid element.
12.533 + ConstIterator end() const {
12.534 + return ConstIterator(ItemIt(INVALID));
12.535 + }
12.536 +
12.537 + protected:
12.538 +
12.539 + const Graph* graph;
12.540 +
12.541 + public:
12.542 + // STL compatibility typedefs.
12.543 + typedef Value value_type;
12.544 + typedef ConstIterator const_iterator;
12.545 + typedef ConstReference const_reference;
12.546 + typedef ConstPointer const_pointer;
12.547 + typedef int difference_type;
12.548 + };
12.549 +
12.550 + /** This class makes from a map an iteratable set
12.551 + * which contains all the values of the map.
12.552 + * The values cannot be modified.
12.553 + */
12.554 + template <typename _Graph, typename _Item, typename _Map>
12.555 + class MapConstValueSet {
12.556 +
12.557 + public:
12.558 +
12.559 + typedef _Graph Graph;
12.560 + typedef _Item Item;
12.561 + typedef _Map Map;
12.562 +
12.563 + protected:
12.564 +
12.565 + /// The iterator to iterate on the keys.
12.566 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
12.567 +
12.568 + public:
12.569 +
12.570 + /// The map initialized const value set.
12.571 + MapConstValueSet(const Graph& _graph, const Map& _map)
12.572 + : graph(&_graph), map(&_map) {}
12.573 +
12.574 + /// The const iterator of the set.
12.575 + typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
12.576 +
12.577 + typedef typename ConstIterator::Value Value;
12.578 + typedef typename ConstIterator::Reference ConstReference;
12.579 + typedef typename ConstIterator::Pointer ConstPointer;
12.580 +
12.581 + /// It gives back the const iterator pointed to the first element.
12.582 + ConstIterator begin() const {
12.583 + return ConstIterator(*map, ItemIt(*graph));
12.584 + }
12.585 +
12.586 + /// It gives back the const iterator pointed to the first invalid element.
12.587 + ConstIterator end() const {
12.588 + return ConstIterator(*map, ItemIt(INVALID));
12.589 + }
12.590 +
12.591 + protected:
12.592 +
12.593 + const Map* map;
12.594 + const Graph * graph;
12.595 +
12.596 + public:
12.597 + // STL compatibility typedefs.
12.598 + typedef Value value_type;
12.599 + typedef ConstIterator const_iterator;
12.600 + typedef ConstReference const_reference;
12.601 + typedef ConstPointer const_pointer;
12.602 + typedef int difference_type;
12.603 + };
12.604 +
12.605 +
12.606 + /** This class makes from a map an iteratable set
12.607 + * which contains all the values of the map.
12.608 + * The values can be modified.
12.609 + */
12.610 + template <typename _Graph, typename _Item, typename _Map>
12.611 + class MapValueSet {
12.612 +
12.613 + public:
12.614 +
12.615 + typedef _Graph Graph;
12.616 + typedef _Item Item;
12.617 + typedef _Map Map;
12.618 +
12.619 + protected:
12.620 +
12.621 + /// The iterator to iterate on the keys.
12.622 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
12.623 +
12.624 + public:
12.625 +
12.626 + /// The map initialized const value set.
12.627 + MapValueSet(const Graph& _graph, Map& _map)
12.628 + : map(&_map), graph(&_graph) {}
12.629 +
12.630 + /// The const iterator of the set.
12.631 + typedef MapValueIterator<_Graph, _Item, _Map> Iterator;
12.632 + /// The const iterator of the set.
12.633 + typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
12.634 +
12.635 + typedef typename ConstIterator::Value Value;
12.636 + typedef typename Iterator::Reference Reference;
12.637 + typedef typename Iterator::Pointer Pointer;
12.638 + typedef typename ConstIterator::Reference ConstReference;
12.639 + typedef typename ConstIterator::Pointer ConstPointer;
12.640 +
12.641 + /// It gives back the const iterator pointed to the first element.
12.642 + ConstIterator begin() const {
12.643 + return ConstIterator(*map, ItemIt(*graph));
12.644 + }
12.645 +
12.646 + /// It gives back the const iterator pointed to the first invalid element.
12.647 + ConstIterator end() const {
12.648 + return ConstIterator(*map, ItemIt(INVALID));
12.649 + }
12.650 +
12.651 + /// It gives back the iterator pointed to the first element.
12.652 + Iterator begin() {
12.653 + return Iterator(*map, ItemIt(*graph));
12.654 + }
12.655 +
12.656 + /// It gives back the iterator pointed to the first invalid element.
12.657 + Iterator end() {
12.658 + return Iterator(*map, ItemIt(INVALID));
12.659 + }
12.660 +
12.661 + protected:
12.662 +
12.663 + Map* map;
12.664 + const Graph * graph;
12.665 +
12.666 + public:
12.667 + // STL compatibility typedefs.
12.668 + typedef Value value_type;
12.669 + typedef Iterator iterator;
12.670 + typedef ConstIterator const_iterator;
12.671 + typedef Reference reference;
12.672 + typedef ConstReference const_reference;
12.673 + typedef Pointer pointer;
12.674 + typedef ConstPointer const_pointer;
12.675 + typedef int difference_type;
12.676 +
12.677 + };
12.678 +
12.679 + /** This class makes from a map an iteratable set
12.680 + * which contains all the values of the map.
12.681 + * The values can be modified.
12.682 + */
12.683 + template <
12.684 + typename _Graph,
12.685 + typename _Item,
12.686 + typename _Map
12.687 + >
12.688 + class MapSet {
12.689 + public:
12.690 +
12.691 + typedef _Graph Graph;
12.692 + typedef _Item Item;
12.693 + typedef _Map Map;
12.694 +
12.695 + protected:
12.696 +
12.697 + typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
12.698 +
12.699 + public:
12.700 +
12.701 + /// The map initialized value set.
12.702 + MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}
12.703 +
12.704 + /// The const iterator of the set.
12.705 + typedef MapIterator<_Graph, _Item, _Map> Iterator;
12.706 + typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
12.707 +
12.708 + typedef typename ConstIterator::Value Value;
12.709 + typedef typename Iterator::Reference Reference;
12.710 + typedef typename Iterator::Pointer Pointer;
12.711 + typedef typename ConstIterator::Reference ConstReference;
12.712 + typedef typename ConstIterator::Pointer ConstPointer;
12.713 +
12.714 +
12.715 + /// It gives back the const iterator pointed to the first element.
12.716 + ConstIterator begin() const {
12.717 + return ConstIterator(*map, ItemIt(*graph));
12.718 + }
12.719 +
12.720 + /// It gives back the const iterator pointed to the first invalid element.
12.721 + ConstIterator end() const {
12.722 + return ConstIterator(*map, ItemIt(INVALID));
12.723 + }
12.724 +
12.725 + /// The iterator of the set.
12.726 +
12.727 + /// It gives back the iterator pointed to the first element.
12.728 + Iterator begin() {
12.729 + return Iterator(*map, ItemIt(*graph));
12.730 + }
12.731 +
12.732 + /// It gives back the iterator pointed to the first invalid element.
12.733 + Iterator end() {
12.734 + return Iterator(*map, ItemIt(INVALID));
12.735 + }
12.736 +
12.737 + protected:
12.738 +
12.739 + const Graph* graph;
12.740 + Map* map;
12.741 +
12.742 + public:
12.743 + // STL compatibility typedefs.
12.744 + typedef Value value_type;
12.745 + typedef Iterator iterator;
12.746 + typedef ConstIterator const_iterator;
12.747 + typedef Reference reference;
12.748 + typedef ConstReference const_reference;
12.749 + typedef Pointer pointer;
12.750 + typedef ConstPointer const_pointer;
12.751 + typedef int difference_type;
12.752 +
12.753 + };
12.754 +
12.755 + template <
12.756 + typename _Graph,
12.757 + typename _Item,
12.758 + typename _Map
12.759 + >
12.760 + class ConstMapSet {
12.761 +
12.762 + typedef _Graph Graph;
12.763 + typedef _Map Map;
12.764 +
12.765 + const Graph* graph;
12.766 + const Map* map;
12.767 +
12.768 + public:
12.769 +
12.770 + typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
12.771 +
12.772 +
12.773 + /// The map initialized value set.
12.774 + ConstMapSet(const Graph& _graph, const Map& _map)
12.775 + : graph(&_graph), map(&_map) {}
12.776 +
12.777 + /// The const iterator of the set.
12.778 + typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
12.779 +
12.780 + typedef typename ConstIterator::Value Value;
12.781 + typedef typename ConstIterator::Reference ConstReference;
12.782 + typedef typename ConstIterator::Pointer ConstPointer;
12.783 +
12.784 +
12.785 + /// It gives back the const iterator pointed to the first element.
12.786 + ConstIterator begin() const {
12.787 + return ConstIterator(*map, ItemIt(*graph));
12.788 + }
12.789 +
12.790 + /// It gives back the const iterator pointed to the first invalid element.
12.791 + ConstIterator end() const {
12.792 + return ConstIterator(*map, ItemIt(INVALID));
12.793 + }
12.794 +
12.795 + public:
12.796 + // STL compatibility typedefs.
12.797 + typedef Value value_type;
12.798 + typedef ConstIterator const_iterator;
12.799 + typedef ConstReference const_reference;
12.800 + typedef ConstPointer const_pointer;
12.801 + typedef int difference_type;
12.802 +
12.803 + };
12.804 +
12.805 + template <typename _Map>
12.806 + class IterableMapExtender : public _Map {
12.807 + public:
12.808 +
12.809 + typedef _Map Parent;
12.810 + typedef Parent Map;
12.811 + typedef typename Map::Graph Graph;
12.812 + typedef typename Map::Key Item;
12.813 + typedef typename Map::Value Value;
12.814 +
12.815 + typedef MapSet<Graph, Item, Map> MapSet;
12.816 +
12.817 + IterableMapExtender() : Parent() {}
12.818 +
12.819 + IterableMapExtender(const Graph& graph) : Parent(graph) {}
12.820 +
12.821 + IterableMapExtender(const Graph& graph, const Value& value)
12.822 + : Parent(graph, value) {}
12.823 +
12.824 + MapSet mapSet() {
12.825 + return MapSet(*Parent::getGraph(), *this);
12.826 + }
12.827 +
12.828 + typedef ConstMapSet<Graph, Item, Map> ConstMapSet;
12.829 +
12.830 + ConstMapSet mapSet() const {
12.831 + return ConstMapSet(*Parent::getGraph(), *this);
12.832 + }
12.833 +
12.834 + typedef MapConstKeySet<Graph, Item> ConstKeySet;
12.835 +
12.836 + ConstKeySet keySet() const {
12.837 + return ConstKeySet(*Parent::getGraph());
12.838 + }
12.839 +
12.840 + typedef MapValueSet<Graph, Item, Map> ValueSet;
12.841 +
12.842 + ValueSet valueSet() {
12.843 + return ValueSet(*Parent::getGraph(), *this);
12.844 + }
12.845 +
12.846 + typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;
12.847 +
12.848 + ConstValueSet valueSet() const {
12.849 + return ConstValueSet(*Parent::getGraph(), *this);
12.850 + }
12.851 +
12.852 + };
12.853 +
12.854 + /// @}
12.855 +
12.856 +}
12.857 +
12.858 +#endif
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/src/lemon/bits/undir_graph_extender.h Tue Apr 05 12:30:46 2005 +0000
13.3 @@ -0,0 +1,278 @@
13.4 +/* -*- C++ -*-
13.5 + *
13.6 + * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++
13.7 + * optimization library
13.8 + *
13.9 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
13.10 + * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
13.11 + * EGRES).
13.12 + *
13.13 + * Permission to use, modify and distribute this software is granted
13.14 + * provided that this copyright notice appears in all copies. For
13.15 + * precise terms see the accompanying LICENSE file.
13.16 + *
13.17 + * This software is provided "AS IS" with no warranty of any kind,
13.18 + * express or implied, and with no claim as to its suitability for any
13.19 + * purpose.
13.20 + *
13.21 + */
13.22 +
13.23 +#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
13.24 +#define LEMON_UNDIR_GRAPH_EXTENDER_H
13.25 +
13.26 +#include <lemon/invalid.h>
13.27 +
13.28 +namespace lemon {
13.29 +
13.30 + template <typename _Base>
13.31 + class UndirGraphExtender : public _Base {
13.32 + typedef _Base Parent;
13.33 + typedef UndirGraphExtender Graph;
13.34 +
13.35 + public:
13.36 +
13.37 + typedef typename Parent::Edge UndirEdge;
13.38 + typedef typename Parent::Node Node;
13.39 +
13.40 + class Edge : public UndirEdge {
13.41 + friend class UndirGraphExtender;
13.42 +
13.43 + protected:
13.44 + // FIXME: Marci use opposite logic in his graph wrappers. It would
13.45 + // be reasonable to syncronize...
13.46 + bool forward;
13.47 +
13.48 + public:
13.49 + Edge() {}
13.50 +
13.51 + /// \brief Directed edge from undirected edge and a direction.
13.52 + ///
13.53 + /// This constructor is not a part of the concept interface of
13.54 + /// undirected graph, so please avoid using it if possible!
13.55 + Edge(const UndirEdge &ue, bool _forward) :
13.56 + UndirEdge(ue), forward(_forward) {}
13.57 +
13.58 + /// \brief Directed edge from undirected edge and a source node.
13.59 + ///
13.60 + /// Constructs a directed edge from undirected edge and a source node.
13.61 + ///
13.62 + /// \note You have to specify the graph for this constructor.
13.63 + Edge(const Graph &g, const UndirEdge &ue, const Node &n) :
13.64 + UndirEdge(ue) { forward = (g.source(ue) == n); }
13.65 +
13.66 + /// Invalid edge constructor
13.67 + Edge(Invalid i) : UndirEdge(i), forward(true) {}
13.68 +
13.69 + bool operator==(const Edge &that) const {
13.70 + return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
13.71 + }
13.72 + bool operator!=(const Edge &that) const {
13.73 + return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
13.74 + }
13.75 + bool operator<(const Edge &that) const {
13.76 + return forward<that.forward ||
13.77 + (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
13.78 + }
13.79 + };
13.80 +
13.81 +
13.82 + /// \brief Edge of opposite direction.
13.83 + ///
13.84 + /// Returns the Edge of opposite direction.
13.85 + Edge opposite(const Edge &e) const {
13.86 + return Edge(e,!e.forward);
13.87 + }
13.88 +
13.89 + protected:
13.90 +
13.91 + template <typename E>
13.92 + Node _dirSource(const E &e) const {
13.93 + return e.forward ? Parent::source(e) : Parent::target(e);
13.94 + }
13.95 +
13.96 + template <typename E>
13.97 + Node _dirTarget(const E &e) const {
13.98 + return e.forward ? Parent::target(e) : Parent::source(e);
13.99 + }
13.100 +
13.101 + public:
13.102 + /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
13.103 + /// or something???
13.104 + using Parent::source;
13.105 +
13.106 + /// Source of the given Edge.
13.107 + Node source(const Edge &e) const {
13.108 + return _dirSource(e);
13.109 + }
13.110 +
13.111 + /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
13.112 + /// or something???
13.113 + using Parent::target;
13.114 +
13.115 + /// Target of the given Edge.
13.116 + Node target(const Edge &e) const {
13.117 + return _dirTarget(e);
13.118 + }
13.119 +
13.120 + /// Returns whether the given directed edge is same orientation as the
13.121 + /// corresponding undirected edge.
13.122 + ///
13.123 + /// \todo reference to the corresponding point of the undirected graph
13.124 + /// concept. "What does the direction of an undirected edge mean?"
13.125 + bool forward(const Edge &e) const { return e.forward; }
13.126 +
13.127 + Node oppositeNode(const Node &n, const UndirEdge &e) const {
13.128 + if( n == Parent::source(e))
13.129 + return Parent::target(e);
13.130 + else if( n == Parent::target(e))
13.131 + return Parent::source(e);
13.132 + else
13.133 + return INVALID;
13.134 + }
13.135 +
13.136 + /// Directed edge from an undirected edge and a source node.
13.137 + ///
13.138 + /// Returns a (directed) Edge corresponding to the specified UndirEdge
13.139 + /// and source Node.
13.140 + ///
13.141 + ///\todo Do we need this?
13.142 + ///
13.143 + ///\todo Better name...
13.144 + Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
13.145 + return Edge(*this, ue, s);
13.146 + }
13.147 +
13.148 + using Parent::first;
13.149 + void first(Edge &e) const {
13.150 + Parent::first(e);
13.151 + e.forward=true;
13.152 + }
13.153 +
13.154 + using Parent::next;
13.155 + void next(Edge &e) const {
13.156 + if( e.forward ) {
13.157 + e.forward = false;
13.158 + }
13.159 + else {
13.160 + Parent::next(e);
13.161 + e.forward = true;
13.162 + }
13.163 + }
13.164 +
13.165 +
13.166 + protected:
13.167 +
13.168 + template <typename E>
13.169 + void _dirFirstOut(E &e, const Node &n) const {
13.170 + Parent::firstIn(e,n);
13.171 + if( UndirEdge(e) != INVALID ) {
13.172 + e.forward = false;
13.173 + }
13.174 + else {
13.175 + Parent::firstOut(e,n);
13.176 + e.forward = true;
13.177 + }
13.178 + }
13.179 + template <typename E>
13.180 + void _dirFirstIn(E &e, const Node &n) const {
13.181 + Parent::firstOut(e,n);
13.182 + if( UndirEdge(e) != INVALID ) {
13.183 + e.forward = false;
13.184 + }
13.185 + else {
13.186 + Parent::firstIn(e,n);
13.187 + e.forward = true;
13.188 + }
13.189 + }
13.190 +
13.191 + template <typename E>
13.192 + void _dirNextOut(E &e) const {
13.193 + if( ! e.forward ) {
13.194 + Node n = Parent::target(e);
13.195 + Parent::nextIn(e);
13.196 + if( UndirEdge(e) == INVALID ) {
13.197 + Parent::firstOut(e, n);
13.198 + e.forward = true;
13.199 + }
13.200 + }
13.201 + else {
13.202 + Parent::nextOut(e);
13.203 + }
13.204 + }
13.205 + template <typename E>
13.206 + void _dirNextIn(E &e) const {
13.207 + if( ! e.forward ) {
13.208 + Node n = Parent::source(e);
13.209 + Parent::nextOut(e);
13.210 + if( UndirEdge(e) == INVALID ) {
13.211 + Parent::firstIn(e, n);
13.212 + e.forward = true;
13.213 + }
13.214 + }
13.215 + else {
13.216 + Parent::nextIn(e);
13.217 + }
13.218 + }
13.219 +
13.220 + public:
13.221 +
13.222 + void firstOut(Edge &e, const Node &n) const {
13.223 + _dirFirstOut(e, n);
13.224 + }
13.225 + void firstIn(Edge &e, const Node &n) const {
13.226 + _dirFirstIn(e, n);
13.227 + }
13.228 +
13.229 + void nextOut(Edge &e) const {
13.230 + _dirNextOut(e);
13.231 + }
13.232 + void nextIn(Edge &e) const {
13.233 + _dirNextIn(e);
13.234 + }
13.235 +
13.236 + // Miscellaneous stuff:
13.237 +
13.238 + /// \todo these methods (id, maxEdgeId) should be moved into separate
13.239 + /// Extender
13.240 +
13.241 + // using Parent::id;
13.242 + // Using "using" is not a good idea, cause it could be that there is
13.243 + // no "id" in Parent...
13.244 +
13.245 + int id(const Node &n) const {
13.246 + return Parent::id(n);
13.247 + }
13.248 +
13.249 + int id(const UndirEdge &e) const {
13.250 + return Parent::id(e);
13.251 + }
13.252 +
13.253 + int id(const Edge &e) const {
13.254 + return 2 * Parent::id(e) + int(e.forward);
13.255 + }
13.256 +
13.257 +
13.258 + int maxId(Node) const {
13.259 + return Parent::maxId(Node());
13.260 + }
13.261 +
13.262 + int maxId(Edge) const {
13.263 + return 2 * Parent::maxId(typename Parent::Edge()) + 1;
13.264 + }
13.265 + int maxId(UndirEdge) const {
13.266 + return Parent::maxId(typename Parent::Edge());
13.267 + }
13.268 +
13.269 +
13.270 + int edgeNum() const {
13.271 + return 2 * Parent::edgeNum();
13.272 + }
13.273 + int undirEdgeNum() const {
13.274 + return Parent::edgeNum();
13.275 + }
13.276 +
13.277 + };
13.278 +
13.279 +}
13.280 +
13.281 +#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
14.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
14.2 +++ b/src/lemon/bits/vector_map.h Tue Apr 05 12:30:46 2005 +0000
14.3 @@ -0,0 +1,287 @@
14.4 +/* -*- C++ -*-
14.5 + * src/lemon/vector_map.h - Part of LEMON, a generic C++ optimization library
14.6 + *
14.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
14.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
14.9 + *
14.10 + * Permission to use, modify and distribute this software is granted
14.11 + * provided that this copyright notice appears in all copies. For
14.12 + * precise terms see the accompanying LICENSE file.
14.13 + *
14.14 + * This software is provided "AS IS" with no warranty of any kind,
14.15 + * express or implied, and with no claim as to its suitability for any
14.16 + * purpose.
14.17 + *
14.18 + */
14.19 +
14.20 +#ifndef LEMON_VECTOR_MAP_H
14.21 +#define LEMON_VECTOR_MAP_H
14.22 +
14.23 +#include <vector>
14.24 +#include <algorithm>
14.25 +
14.26 +#include <lemon/utility.h>
14.27 +#include <lemon/bits/map_iterator.h>
14.28 +#include <lemon/bits/alteration_notifier.h>
14.29 +
14.30 +///\ingroup graphmaps
14.31 +///\file
14.32 +///\brief Vector based graph maps.
14.33 +
14.34 +namespace lemon {
14.35 +
14.36 + /// \addtogroup graphmaps
14.37 + /// @{
14.38 +
14.39 + /// The VectorMap template class is graph map structure what
14.40 + /// automatically updates the map when a key is added to or erased from
14.41 + /// the map. This map factory uses the allocators to implement
14.42 + /// the container functionality. This map factory
14.43 + /// uses the std::vector to implement the container function.
14.44 + ///
14.45 + /// \param Registry The AlterationNotifier that will notify this map.
14.46 + /// \param IdMap The IdMap type of the graph items.
14.47 + /// \param Value The value type of the map.
14.48 + ///
14.49 + /// \author Balazs Dezso
14.50 +
14.51 +
14.52 + template <
14.53 + typename _Graph,
14.54 + typename _Item,
14.55 + typename _Value
14.56 + >
14.57 + class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
14.58 + public:
14.59 +
14.60 + /// The graph type of the map.
14.61 + typedef _Graph Graph;
14.62 + /// The key type of the map.
14.63 + typedef _Item Key;
14.64 + /// The id map type of the map.
14.65 + typedef AlterationNotifier<_Item> Registry;
14.66 + /// The value type of the map.
14.67 + typedef _Value Value;
14.68 +
14.69 + /// The map type.
14.70 + typedef VectorMap Map;
14.71 + /// The base class of the map.
14.72 + typedef typename Registry::ObserverBase Parent;
14.73 +
14.74 + private:
14.75 +
14.76 + /// The container type of the map.
14.77 + typedef std::vector<Value> Container;
14.78 +
14.79 + public:
14.80 +
14.81 + /// The reference type of the map;
14.82 + typedef typename Container::reference Reference;
14.83 + /// The pointer type of the map;
14.84 + typedef typename Container::pointer Pointer;
14.85 +
14.86 + /// The const value type of the map.
14.87 + typedef const Value ConstValue;
14.88 + /// The const reference type of the map;
14.89 + typedef typename Container::const_reference ConstReference;
14.90 + /// The pointer type of the map;
14.91 + typedef typename Container::const_pointer ConstPointer;
14.92 +
14.93 + typedef True FullTypeTag;
14.94 +
14.95 + /// Constructor to attach the new map into the registry.
14.96 +
14.97 + /// It construates a map and attachs it into the registry.
14.98 + /// It adds all the items of the graph to the map.
14.99 +
14.100 + VectorMap(const Graph& _g) : graph(&_g) {
14.101 + attach(_g.getNotifier(_Item()));
14.102 + build();
14.103 + }
14.104 +
14.105 + /// Constructor uses given value to initialize the map.
14.106 +
14.107 + /// It construates a map uses a given value to initialize the map.
14.108 + /// It adds all the items of the graph to the map.
14.109 +
14.110 + VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
14.111 + attach(_g.getNotifier(_Item()));
14.112 + container.resize(graph->maxId(_Item()) + 1, _v);
14.113 + }
14.114 +
14.115 + VectorMap(const VectorMap& _copy) : graph(_copy.getGraph()) {
14.116 + if (_copy.attached()) {
14.117 + attach(*_copy.getRegistry());
14.118 + container = _copy.container;
14.119 + }
14.120 + }
14.121 +
14.122 + using Parent::attach;
14.123 + using Parent::detach;
14.124 + using Parent::attached;
14.125 +
14.126 + /** Assign operator to copy a map of the same map type.
14.127 + */
14.128 + VectorMap& operator=(const VectorMap& copy) {
14.129 + if (© == this) return *this;
14.130 +
14.131 + if (graph != copy.graph) {
14.132 + if (attached()) {
14.133 + detach();
14.134 + }
14.135 + if (copy.attached()) {
14.136 + attach(*copy.getRegistry());
14.137 + }
14.138 + }
14.139 + container = copy.container;
14.140 +
14.141 + return *this;
14.142 + }
14.143 +
14.144 +
14.145 + virtual ~VectorMap() {
14.146 + if (attached()) {
14.147 + detach();
14.148 + }
14.149 + }
14.150 +
14.151 + const Graph* getGraph() const {
14.152 + return graph;
14.153 + }
14.154 +
14.155 + /// The subcript operator.
14.156 +
14.157 + /// The subscript operator. The map can be subscripted by the
14.158 + /// actual items of the graph.
14.159 +
14.160 + Reference operator[](const Key& key) {
14.161 + return container[graph->id(key)];
14.162 + }
14.163 +
14.164 + /// The const subcript operator.
14.165 +
14.166 + /// The const subscript operator. The map can be subscripted by the
14.167 + /// actual items of the graph.
14.168 +
14.169 + ConstReference operator[](const Key& key) const {
14.170 + return container[graph->id(key)];
14.171 + }
14.172 +
14.173 +
14.174 + /// The setter function of the map.
14.175 +
14.176 + /// It the same as operator[](key) = value expression.
14.177 + ///
14.178 +
14.179 + void set(const Key& key, const Value& value) {
14.180 + (*this)[key] = value;
14.181 + }
14.182 +
14.183 + /// Adds a new key to the map.
14.184 +
14.185 + /// It adds a new key to the map. It called by the observer registry
14.186 + /// and it overrides the add() member function of the observer base.
14.187 +
14.188 + void add(const Key& key) {
14.189 + int id = graph->id(key);
14.190 + if (id >= (int)container.size()) {
14.191 + container.resize(id + 1);
14.192 + }
14.193 + }
14.194 +
14.195 + /// Erases a key from the map.
14.196 +
14.197 + /// Erase a key from the map. It called by the observer registry
14.198 + /// and it overrides the erase() member function of the observer base.
14.199 + void erase(const Key&) {}
14.200 +
14.201 + /// Buildes the map.
14.202 +
14.203 + /// It buildes the map. It called by the observer registry
14.204 + /// and it overrides the build() member function of the observer base.
14.205 +
14.206 + void build() {
14.207 + container.resize(graph->maxId(_Item()) + 1);
14.208 + }
14.209 +
14.210 + /// Clear the map.
14.211 +
14.212 + /// It erase all items from the map. It called by the observer registry
14.213 + /// and it overrides the clear() member function of the observer base.
14.214 + void clear() {
14.215 + container.clear();
14.216 + }
14.217 +
14.218 + private:
14.219 +
14.220 + Container container;
14.221 + const Graph *graph;
14.222 +
14.223 + };
14.224 +
14.225 +
14.226 + template <typename _Base>
14.227 + class VectorMappableGraphExtender : public _Base {
14.228 + public:
14.229 +
14.230 + typedef VectorMappableGraphExtender<_Base> Graph;
14.231 + typedef _Base Parent;
14.232 +
14.233 + typedef typename Parent::Node Node;
14.234 + typedef typename Parent::NodeIt NodeIt;
14.235 + typedef typename Parent::NodeIdMap NodeIdMap;
14.236 + typedef typename Parent::NodeNotifier NodeObserverRegistry;
14.237 +
14.238 + typedef typename Parent::Edge Edge;
14.239 + typedef typename Parent::EdgeIt EdgeIt;
14.240 + typedef typename Parent::EdgeIdMap EdgeIdMap;
14.241 + typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
14.242 +
14.243 +
14.244 + template <typename _Value>
14.245 + class NodeMap :
14.246 + public IterableMapExtender<VectorMap<Graph, Node, _Value> > {
14.247 + public:
14.248 + typedef VectorMappableGraphExtender<_Base> Graph;
14.249 +
14.250 + typedef typename Graph::Node Node;
14.251 +
14.252 + typedef IterableMapExtender<VectorMap<Graph, Node, _Value> > Parent;
14.253 +
14.254 + //typedef typename Parent::Graph Graph;
14.255 + typedef typename Parent::Value Value;
14.256 +
14.257 + NodeMap(const Graph& g)
14.258 + : Parent(g) {}
14.259 + NodeMap(const Graph& g, const Value& v)
14.260 + : Parent(g, v) {}
14.261 +
14.262 + };
14.263 +
14.264 + template <typename _Value>
14.265 + class EdgeMap
14.266 + : public IterableMapExtender<VectorMap<Graph, Edge, _Value> > {
14.267 + public:
14.268 + typedef VectorMappableGraphExtender<_Base> Graph;
14.269 +
14.270 + typedef typename Graph::Edge Edge;
14.271 +
14.272 + typedef IterableMapExtender<VectorMap<Graph, Edge, _Value> > Parent;
14.273 +
14.274 + //typedef typename Parent::Graph Graph;
14.275 + typedef typename Parent::Value Value;
14.276 +
14.277 + EdgeMap(const Graph& g)
14.278 + : Parent(g) {}
14.279 + EdgeMap(const Graph& g, const Value& v)
14.280 + : Parent(g, v) {}
14.281 +
14.282 + };
14.283 +
14.284 + };
14.285 +
14.286 + /// @}
14.287 +
14.288 +}
14.289 +
14.290 +#endif
15.1 --- a/src/lemon/clearable_graph_extender.h Tue Apr 05 09:49:01 2005 +0000
15.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
15.3 @@ -1,49 +0,0 @@
15.4 -// -*- c++ -*-
15.5 -
15.6 -#ifndef LEMON_CLEARABLE_GRAPH_EXTENDER_H
15.7 -#define LEMON_CLEARABLE_GRAPH_EXTENDER_H
15.8 -
15.9 -#include <lemon/invalid.h>
15.10 -
15.11 -
15.12 -namespace lemon {
15.13 -
15.14 - template <typename _Base>
15.15 - class ClearableGraphExtender : public _Base {
15.16 - public:
15.17 -
15.18 - typedef ClearableGraphExtender Graph;
15.19 - typedef _Base Parent;
15.20 - typedef typename Parent::Node Node;
15.21 - typedef typename Parent::Edge Edge;
15.22 -
15.23 - void clear() {
15.24 - Parent::getNotifier(Node()).clear();
15.25 - Parent::getNotifier(Edge()).clear();
15.26 - Parent::clear();
15.27 - }
15.28 -
15.29 - };
15.30 -
15.31 - template <typename _Base>
15.32 - class ClearableUndirGraphExtender : public _Base {
15.33 - public:
15.34 -
15.35 - typedef ClearableUndirGraphExtender Graph;
15.36 - typedef _Base Parent;
15.37 - typedef typename Parent::Node Node;
15.38 - typedef typename Parent::UndirEdge UndirEdge;
15.39 - typedef typename Parent::Edge Edge;
15.40 -
15.41 - void clear() {
15.42 - Parent::getNotifier(Node()).clear();
15.43 - Parent::getNotifier(UndirEdge()).clear();
15.44 - Parent::getNotifier(Edge()).clear();
15.45 - Parent::clear();
15.46 - }
15.47 -
15.48 - };
15.49 -
15.50 -}
15.51 -
15.52 -#endif
16.1 --- a/src/lemon/concept/graph_component.h Tue Apr 05 09:49:01 2005 +0000
16.2 +++ b/src/lemon/concept/graph_component.h Tue Apr 05 12:30:46 2005 +0000
16.3 @@ -25,7 +25,7 @@
16.4 #include <lemon/invalid.h>
16.5 #include <lemon/concept/maps.h>
16.6
16.7 -#include <lemon/alteration_notifier.h>
16.8 +#include <lemon/bits/alteration_notifier.h>
16.9
16.10 namespace lemon {
16.11 namespace concept {
17.1 --- a/src/lemon/default_map.h Tue Apr 05 09:49:01 2005 +0000
17.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
17.3 @@ -1,230 +0,0 @@
17.4 -/* -*- C++ -*-
17.5 - * src/lemon/default_map.h - Part of LEMON, a generic C++ optimization library
17.6 - *
17.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
17.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
17.9 - *
17.10 - * Permission to use, modify and distribute this software is granted
17.11 - * provided that this copyright notice appears in all copies. For
17.12 - * precise terms see the accompanying LICENSE file.
17.13 - *
17.14 - * This software is provided "AS IS" with no warranty of any kind,
17.15 - * express or implied, and with no claim as to its suitability for any
17.16 - * purpose.
17.17 - *
17.18 - */
17.19 -
17.20 -#ifndef LEMON_DEFAULT_MAP_H
17.21 -#define LEMON_DEFAULT_MAP_H
17.22 -
17.23 -
17.24 -#include <lemon/array_map.h>
17.25 -#include <lemon/vector_map.h>
17.26 -
17.27 -///\ingroup graphmaps
17.28 -///\file
17.29 -///\brief Graph maps that construct and destruct
17.30 -///their elements dynamically.
17.31 -
17.32 -namespace lemon {
17.33 -
17.34 -/// \addtogroup graphmaps
17.35 -/// @{
17.36 -
17.37 - /** The ArrayMap template class is graph map structure what
17.38 - * automatically updates the map when a key is added to or erased from
17.39 - * the map. This map uses the VectorMap if the Value is a primitive
17.40 - * type and the ArrayMap for the other cases.
17.41 - *
17.42 - * The template parameter is the MapRegistry that the maps
17.43 - * will belong to and the Value.
17.44 - */
17.45 -
17.46 -
17.47 -
17.48 - template <typename _Graph, typename _Item, typename _Value>
17.49 - struct DefaultMapSelector {
17.50 - typedef ArrayMap<_Graph, _Item, _Value> Map;
17.51 - };
17.52 -
17.53 - // bool
17.54 - template <typename _Graph, typename _Item>
17.55 - struct DefaultMapSelector<_Graph, _Item, bool> {
17.56 - typedef VectorMap<_Graph, _Item, bool> Map;
17.57 - };
17.58 -
17.59 - // char
17.60 - template <typename _Graph, typename _Item>
17.61 - struct DefaultMapSelector<_Graph, _Item, char> {
17.62 - typedef VectorMap<_Graph, _Item, char> Map;
17.63 - };
17.64 -
17.65 - template <typename _Graph, typename _Item>
17.66 - struct DefaultMapSelector<_Graph, _Item, signed char> {
17.67 - typedef VectorMap<_Graph, _Item, signed char> Map;
17.68 - };
17.69 -
17.70 - template <typename _Graph, typename _Item>
17.71 - struct DefaultMapSelector<_Graph, _Item, unsigned char> {
17.72 - typedef VectorMap<_Graph, _Item, unsigned char> Map;
17.73 - };
17.74 -
17.75 -
17.76 - // int
17.77 - template <typename _Graph, typename _Item>
17.78 - struct DefaultMapSelector<_Graph, _Item, signed int> {
17.79 - typedef VectorMap<_Graph, _Item, signed int> Map;
17.80 - };
17.81 -
17.82 - template <typename _Graph, typename _Item>
17.83 - struct DefaultMapSelector<_Graph, _Item, unsigned int> {
17.84 - typedef VectorMap<_Graph, _Item, unsigned int> Map;
17.85 - };
17.86 -
17.87 -
17.88 - // short
17.89 - template <typename _Graph, typename _Item>
17.90 - struct DefaultMapSelector<_Graph, _Item, signed short> {
17.91 - typedef VectorMap<_Graph, _Item, signed short> Map;
17.92 - };
17.93 -
17.94 - template <typename _Graph, typename _Item>
17.95 - struct DefaultMapSelector<_Graph, _Item, unsigned short> {
17.96 - typedef VectorMap<_Graph, _Item, unsigned short> Map;
17.97 - };
17.98 -
17.99 -
17.100 - // long
17.101 - template <typename _Graph, typename _Item>
17.102 - struct DefaultMapSelector<_Graph, _Item, signed long> {
17.103 - typedef VectorMap<_Graph, _Item, signed long> Map;
17.104 - };
17.105 -
17.106 - template <typename _Graph, typename _Item>
17.107 - struct DefaultMapSelector<_Graph, _Item, unsigned long> {
17.108 - typedef VectorMap<_Graph, _Item, unsigned long> Map;
17.109 - };
17.110 -
17.111 - // \todo handling long long type
17.112 -
17.113 -
17.114 - // float
17.115 - template <typename _Graph, typename _Item>
17.116 - struct DefaultMapSelector<_Graph, _Item, float> {
17.117 - typedef VectorMap<_Graph, _Item, float> Map;
17.118 - };
17.119 -
17.120 -
17.121 - // double
17.122 - template <typename _Graph, typename _Item>
17.123 - struct DefaultMapSelector<_Graph, _Item, double> {
17.124 - typedef VectorMap<_Graph, _Item, double> Map;
17.125 - };
17.126 -
17.127 -
17.128 - // long double
17.129 - template <typename _Graph, typename _Item>
17.130 - struct DefaultMapSelector<_Graph, _Item, long double> {
17.131 - typedef VectorMap<_Graph, _Item, long double> Map;
17.132 - };
17.133 -
17.134 -
17.135 - // pointer
17.136 - template <typename _Graph, typename _Item, typename _Ptr>
17.137 - struct DefaultMapSelector<_Graph, _Item, _Ptr*> {
17.138 - typedef VectorMap<_Graph, _Item, _Ptr*> Map;
17.139 - };
17.140 -
17.141 -
17.142 -
17.143 - template <
17.144 - typename _Graph,
17.145 - typename _Item,
17.146 - typename _Value>
17.147 - class DefaultMap
17.148 - : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
17.149 - public:
17.150 - typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
17.151 - typedef DefaultMap<_Graph, _Item, _Value> Map;
17.152 -
17.153 - typedef typename Parent::Graph Graph;
17.154 - typedef typename Parent::Value Value;
17.155 -
17.156 - DefaultMap(const Graph& _g) : Parent(_g) {}
17.157 - DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {}
17.158 - };
17.159 -
17.160 -
17.161 -
17.162 - template <typename _Base>
17.163 - class DefaultMappableGraphExtender : public _Base {
17.164 - public:
17.165 -
17.166 - typedef DefaultMappableGraphExtender<_Base> Graph;
17.167 - typedef _Base Parent;
17.168 -
17.169 - typedef typename Parent::Node Node;
17.170 - typedef typename Parent::NodeIt NodeIt;
17.171 -
17.172 - typedef typename Parent::Edge Edge;
17.173 - typedef typename Parent::EdgeIt EdgeIt;
17.174 -
17.175 -
17.176 - template <typename _Value>
17.177 - class NodeMap
17.178 - : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
17.179 - public:
17.180 - typedef DefaultMappableGraphExtender Graph;
17.181 - typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
17.182 -
17.183 - NodeMap(const Graph& _g)
17.184 - : Parent(_g) {}
17.185 - NodeMap(const Graph& _g, const _Value& _v)
17.186 - : Parent(_g, _v) {}
17.187 - };
17.188 -
17.189 - template <typename _Value>
17.190 - class EdgeMap
17.191 - : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
17.192 - public:
17.193 - typedef DefaultMappableGraphExtender Graph;
17.194 - typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
17.195 -
17.196 - EdgeMap(const Graph& _g)
17.197 - : Parent(_g) {}
17.198 - EdgeMap(const Graph& _g, const _Value& _v)
17.199 - : Parent(_g, _v) {}
17.200 - };
17.201 -
17.202 - };
17.203 -
17.204 - template <typename _Base>
17.205 - class MappableUndirGraphExtender :
17.206 - public DefaultMappableGraphExtender<_Base> {
17.207 - public:
17.208 -
17.209 - typedef MappableUndirGraphExtender Graph;
17.210 - typedef DefaultMappableGraphExtender<_Base> Parent;
17.211 -
17.212 - typedef typename Parent::UndirEdge UndirEdge;
17.213 -
17.214 - template <typename _Value>
17.215 - class UndirEdgeMap
17.216 - : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
17.217 - public:
17.218 - typedef MappableUndirGraphExtender Graph;
17.219 - typedef IterableMapExtender<
17.220 - DefaultMap<Graph, UndirEdge, _Value> > Parent;
17.221 -
17.222 - UndirEdgeMap(const Graph& _g)
17.223 - : Parent(_g) {}
17.224 - UndirEdgeMap(const Graph& _g, const _Value& _v)
17.225 - : Parent(_g, _v) {}
17.226 - };
17.227 -
17.228 -
17.229 - };
17.230 -
17.231 -}
17.232 -
17.233 -#endif
18.1 --- a/src/lemon/erasable_graph_extender.h Tue Apr 05 09:49:01 2005 +0000
18.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
18.3 @@ -1,80 +0,0 @@
18.4 -// -*- c++ -*-
18.5 -
18.6 -#ifndef LEMON_ERASABLE_GRAPH_EXTENDER_H
18.7 -#define LEMON_ERASABLE_GRAPH_EXTENDER_H
18.8 -
18.9 -#include <lemon/invalid.h>
18.10 -
18.11 -
18.12 -namespace lemon {
18.13 -
18.14 - template <typename _Base>
18.15 - class ErasableGraphExtender : public _Base {
18.16 - public:
18.17 -
18.18 - typedef ErasableGraphExtender Graph;
18.19 - typedef _Base Parent;
18.20 -
18.21 - typedef typename Parent::Node Node;
18.22 - typedef typename Parent::Edge Edge;
18.23 -
18.24 - void erase(const Node& node) {
18.25 - Edge edge;
18.26 - Parent::firstOut(edge, node);
18.27 - while (edge != INVALID ) {
18.28 - erase(edge);
18.29 - Parent::firstOut(edge, node);
18.30 - }
18.31 -
18.32 - Parent::firstIn(edge, node);
18.33 - while (edge != INVALID ) {
18.34 - erase(edge);
18.35 - Parent::firstIn(edge, node);
18.36 - }
18.37 -
18.38 - Parent::getNotifier(Node()).erase(node);
18.39 - Parent::erase(node);
18.40 - }
18.41 -
18.42 - void erase(const Edge& edge) {
18.43 - Parent::getNotifier(Edge()).erase(edge);
18.44 - Parent::erase(edge);
18.45 - }
18.46 -
18.47 - };
18.48 -
18.49 - template <typename _Base>
18.50 - class ErasableUndirGraphExtender : public _Base {
18.51 - public:
18.52 -
18.53 - typedef ErasableUndirGraphExtender Graph;
18.54 - typedef _Base Parent;
18.55 -
18.56 - typedef typename Parent::Node Node;
18.57 - typedef typename Parent::UndirEdge UndirEdge;
18.58 - typedef typename Parent::Edge Edge;
18.59 -
18.60 - void erase(const Node& node) {
18.61 - Edge edge;
18.62 - Parent::firstOut(edge, node);
18.63 - while (edge != INVALID ) {
18.64 - erase(edge);
18.65 - Parent::firstOut(edge, node);
18.66 - }
18.67 -
18.68 - Parent::getNotifier(Node()).erase(node);
18.69 - Parent::erase(node);
18.70 - }
18.71 -
18.72 - void erase(const UndirEdge& uedge) {
18.73 - Parent::getNotifier(Edge()).erase(Edge(uedge,true));
18.74 - Parent::getNotifier(Edge()).erase(Edge(uedge,false));
18.75 - Parent::getNotifier(UndirEdge()).erase(uedge);
18.76 - Parent::erase(uedge);
18.77 - }
18.78 -
18.79 - };
18.80 -
18.81 -}
18.82 -
18.83 -#endif
19.1 --- a/src/lemon/extendable_graph_extender.h Tue Apr 05 09:49:01 2005 +0000
19.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
19.3 @@ -1,65 +0,0 @@
19.4 -// -*- c++ -*-
19.5 -
19.6 -#ifndef LEMON_EXTENDABLE_GRAPH_EXTENDER_H
19.7 -#define LEMON_EXTENDABLE_GRAPH_EXTENDER_H
19.8 -
19.9 -namespace lemon {
19.10 -
19.11 - template <typename _Base>
19.12 - class ExtendableGraphExtender : public _Base {
19.13 - public:
19.14 -
19.15 - typedef ExtendableGraphExtender Graph;
19.16 - typedef _Base Parent;
19.17 -
19.18 - typedef typename Parent::Node Node;
19.19 - typedef typename Parent::Edge Edge;
19.20 -
19.21 - Node addNode() {
19.22 - Node node = Parent::addNode();
19.23 - Parent::getNotifier(Node()).add(node);
19.24 - return node;
19.25 - }
19.26 -
19.27 - Edge addEdge(const Node& from, const Node& to) {
19.28 - Edge edge = Parent::addEdge(from, to);
19.29 - Parent::getNotifier(Edge()).add(edge);
19.30 - return edge;
19.31 - }
19.32 -
19.33 - };
19.34 -
19.35 - template <typename _Base>
19.36 - class ExtendableUndirGraphExtender : public _Base {
19.37 - public:
19.38 -
19.39 - typedef ExtendableUndirGraphExtender Graph;
19.40 - typedef _Base Parent;
19.41 -
19.42 - typedef typename Parent::Node Node;
19.43 - typedef typename Parent::Edge Edge;
19.44 - typedef typename Parent::UndirEdge UndirEdge;
19.45 -
19.46 - Node addNode() {
19.47 - Node node = Parent::addNode();
19.48 - Parent::getNotifier(Node()).add(node);
19.49 - return node;
19.50 - }
19.51 -
19.52 - UndirEdge addEdge(const Node& from, const Node& to) {
19.53 - UndirEdge uedge = Parent::addEdge(from, to);
19.54 - Parent::getNotifier(UndirEdge()).add(uedge);
19.55 -
19.56 - Edge edge_forward(uedge, true);
19.57 - Edge edge_backward(uedge, false);
19.58 - Parent::getNotifier(Edge()).add(edge_forward);
19.59 - Parent::getNotifier(Edge()).add(edge_backward);
19.60 -
19.61 - return uedge;
19.62 - }
19.63 -
19.64 - };
19.65 -
19.66 -}
19.67 -
19.68 -#endif
20.1 --- a/src/lemon/extended_pair.h Tue Apr 05 09:49:01 2005 +0000
20.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
20.3 @@ -1,80 +0,0 @@
20.4 -/* -*- C++ -*-
20.5 - * src/lemon/extended_pair.h - Part of LEMON, a generic C++ optimization library
20.6 - *
20.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
20.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
20.9 - *
20.10 - * Permission to use, modify and distribute this software is granted
20.11 - * provided that this copyright notice appears in all copies. For
20.12 - * precise terms see the accompanying LICENSE file.
20.13 - *
20.14 - * This software is provided "AS IS" with no warranty of any kind,
20.15 - * express or implied, and with no claim as to its suitability for any
20.16 - * purpose.
20.17 - *
20.18 - */
20.19 -
20.20 -#ifndef LEMON_EXTENDED_PAIR_H
20.21 -#define LEMON_EXTENDED_PAIR_H
20.22 -
20.23 -template <typename T1, typename A1, typename T2, typename A2>
20.24 -struct extended_pair {
20.25 - typedef T1 first_type;
20.26 - typedef T2 second_type;
20.27 -
20.28 - extended_pair() : first(), second() {}
20.29 -
20.30 - extended_pair(A1 f, A2 s) : first(f), second(s) {}
20.31 -
20.32 - template <class Pair>
20.33 - extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {}
20.34 -
20.35 - T1 first;
20.36 - T2 second;
20.37 -};
20.38 -
20.39 -template <typename T1, typename T2,
20.40 - typename LA1, typename LA2, typename RA1, typename RA2>
20.41 -bool operator==(const extended_pair<T1, LA1, T2, LA2>& left,
20.42 - const extended_pair<T1, RA1, T2, RA2>& right) {
20.43 - return left.first == right.first && left.second == right.second;
20.44 -}
20.45 -
20.46 -template <typename T1, typename T2,
20.47 - typename LA1, typename LA2, typename RA1, typename RA2>
20.48 -bool operator!=(const extended_pair<T1, LA1, T2, LA2>& left,
20.49 - const extended_pair<T1, RA1, T2, RA2>& right) {
20.50 - return !(left == right);
20.51 -}
20.52 -
20.53 -template <typename T1, typename T2,
20.54 - typename LA1, typename LA2, typename RA1, typename RA2>
20.55 -bool operator<(const extended_pair<T1, LA1, T2, LA2>& left,
20.56 - const extended_pair<T1, RA1, T2, RA2>& right) {
20.57 - return left.first < right.first ||
20.58 - (!(right.first<left.first) && left.second < right.second);
20.59 -}
20.60 -
20.61 -template <typename T1, typename T2,
20.62 - typename LA1, typename LA2, typename RA1, typename RA2>
20.63 -bool operator>(const extended_pair<T1, LA1, T2, LA2>& left,
20.64 - const extended_pair<T1, RA1, T2, RA2>& right) {
20.65 - return right < left;
20.66 -}
20.67 -
20.68 -template <typename T1, typename T2,
20.69 - typename LA1, typename LA2, typename RA1, typename RA2>
20.70 -bool operator<=(const extended_pair<T1, LA1, T2, LA2>& left,
20.71 - const extended_pair<T1, RA1, T2, RA2>& right) {
20.72 - return !(right > left);
20.73 -}
20.74 -
20.75 -template <typename T1, typename T2,
20.76 - typename LA1, typename LA2, typename RA1, typename RA2>
20.77 -bool operator>=(const extended_pair<T1, LA1, T2, LA2>& left,
20.78 - const extended_pair<T1, RA1, T2, RA2>& right) {
20.79 - return !(right < left);
20.80 -}
20.81 -
20.82 -
20.83 -#endif
21.1 --- a/src/lemon/full_graph.h Tue Apr 05 09:49:01 2005 +0000
21.2 +++ b/src/lemon/full_graph.h Tue Apr 05 12:30:46 2005 +0000
21.3 @@ -20,9 +20,9 @@
21.4 #include <cmath>
21.5
21.6
21.7 -#include <lemon/iterable_graph_extender.h>
21.8 -#include <lemon/alteration_notifier.h>
21.9 -#include <lemon/default_map.h>
21.10 +#include <lemon/bits/iterable_graph_extender.h>
21.11 +#include <lemon/bits/alteration_notifier.h>
21.12 +#include <lemon/bits/default_map.h>
21.13
21.14 #include <lemon/invalid.h>
21.15 #include <lemon/utility.h>
22.1 --- a/src/lemon/graph_wrapper.h Tue Apr 05 09:49:01 2005 +0000
22.2 +++ b/src/lemon/graph_wrapper.h Tue Apr 05 12:30:46 2005 +0000
22.3 @@ -27,7 +27,7 @@
22.4
22.5 #include <lemon/invalid.h>
22.6 #include <lemon/maps.h>
22.7 -#include <lemon/iterable_graph_extender.h>
22.8 +#include <lemon/bits/iterable_graph_extender.h>
22.9 #include <iostream>
22.10
22.11 namespace lemon {
23.1 --- a/src/lemon/iterable_graph_extender.h Tue Apr 05 09:49:01 2005 +0000
23.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
23.3 @@ -1,250 +0,0 @@
23.4 -// -*- c++ -*-
23.5 -#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
23.6 -#define LEMON_ITERABLE_GRAPH_EXTENDER_H
23.7 -
23.8 -#include <lemon/invalid.h>
23.9 -
23.10 -namespace lemon {
23.11 -
23.12 - template <typename _Base>
23.13 - class IterableGraphExtender : public _Base {
23.14 - public:
23.15 -
23.16 - typedef _Base Parent;
23.17 - typedef IterableGraphExtender<_Base> Graph;
23.18 -
23.19 - typedef typename Parent::Node Node;
23.20 - typedef typename Parent::Edge Edge;
23.21 -
23.22 -
23.23 - class NodeIt : public Node {
23.24 - const Graph* graph;
23.25 - public:
23.26 -
23.27 - NodeIt() {}
23.28 -
23.29 - NodeIt(Invalid i) : Node(i) { }
23.30 -
23.31 - explicit NodeIt(const Graph& _graph) : graph(&_graph) {
23.32 - _graph.first(*static_cast<Node*>(this));
23.33 - }
23.34 -
23.35 - NodeIt(const Graph& _graph, const Node& node)
23.36 - : Node(node), graph(&_graph) {}
23.37 -
23.38 - NodeIt& operator++() {
23.39 - graph->next(*this);
23.40 - return *this;
23.41 - }
23.42 -
23.43 - };
23.44 -
23.45 -
23.46 - class EdgeIt : public Edge {
23.47 - const Graph* graph;
23.48 - public:
23.49 -
23.50 - EdgeIt() { }
23.51 -
23.52 - EdgeIt(Invalid i) : Edge(i) { }
23.53 -
23.54 - explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
23.55 - _graph.first(*static_cast<Edge*>(this));
23.56 - }
23.57 -
23.58 - EdgeIt(const Graph& _graph, const Edge& e) :
23.59 - Edge(e), graph(&_graph) { }
23.60 -
23.61 - EdgeIt& operator++() {
23.62 - graph->next(*this);
23.63 - return *this;
23.64 - }
23.65 -
23.66 - };
23.67 -
23.68 -
23.69 - class OutEdgeIt : public Edge {
23.70 - const Graph* graph;
23.71 - public:
23.72 -
23.73 - OutEdgeIt() { }
23.74 -
23.75 - OutEdgeIt(Invalid i) : Edge(i) { }
23.76 -
23.77 - OutEdgeIt(const Graph& _graph, const Node& node)
23.78 - : graph(&_graph) {
23.79 - _graph.firstOut(*this, node);
23.80 - }
23.81 -
23.82 - OutEdgeIt(const Graph& _graph, const Edge& edge)
23.83 - : Edge(edge), graph(&_graph) {}
23.84 -
23.85 - OutEdgeIt& operator++() {
23.86 - graph->nextOut(*this);
23.87 - return *this;
23.88 - }
23.89 -
23.90 - };
23.91 -
23.92 -
23.93 - class InEdgeIt : public Edge {
23.94 - const Graph* graph;
23.95 - public:
23.96 -
23.97 - InEdgeIt() { }
23.98 -
23.99 - InEdgeIt(Invalid i) : Edge(i) { }
23.100 -
23.101 - InEdgeIt(const Graph& _graph, const Node& node)
23.102 - : graph(&_graph) {
23.103 - _graph.firstIn(*this, node);
23.104 - }
23.105 -
23.106 - InEdgeIt(const Graph& _graph, const Edge& edge) :
23.107 - Edge(edge), graph(&_graph) {}
23.108 -
23.109 - InEdgeIt& operator++() {
23.110 - graph->nextIn(*this);
23.111 - return *this;
23.112 - }
23.113 -
23.114 - };
23.115 -
23.116 - /// Base node of the iterator
23.117 - ///
23.118 - /// Returns the base node (ie. the source in this case) of the iterator
23.119 - ///
23.120 - /// \todo Document in the concept!
23.121 - Node baseNode(const OutEdgeIt &e) const {
23.122 - return source(e);
23.123 - }
23.124 - /// Running node of the iterator
23.125 - ///
23.126 - /// Returns the running node (ie. the target in this case) of the
23.127 - /// iterator
23.128 - ///
23.129 - /// \todo Document in the concept!
23.130 - Node runningNode(const OutEdgeIt &e) const {
23.131 - return target(e);
23.132 - }
23.133 -
23.134 - /// Base node of the iterator
23.135 - ///
23.136 - /// Returns the base node (ie. the target in this case) of the iterator
23.137 - ///
23.138 - /// \todo Document in the concept!
23.139 - Node baseNode(const InEdgeIt &e) const {
23.140 - return target(e);
23.141 - }
23.142 - /// Running node of the iterator
23.143 - ///
23.144 - /// Returns the running node (ie. the source in this case) of the
23.145 - /// iterator
23.146 - ///
23.147 - /// \todo Document in the concept!
23.148 - Node runningNode(const InEdgeIt &e) const {
23.149 - return source(e);
23.150 - }
23.151 -
23.152 - using Parent::first;
23.153 -
23.154 - private:
23.155 -
23.156 - // /// \todo When (and if) we change the iterators concept to use operator*,
23.157 - // /// then the following shadowed methods will become superfluous.
23.158 - // /// But for now these are important safety measures.
23.159 -
23.160 - // void first(NodeIt &) const;
23.161 - // void first(EdgeIt &) const;
23.162 - // void first(OutEdgeIt &) const;
23.163 - // void first(InEdgeIt &) const;
23.164 -
23.165 - };
23.166 -
23.167 -
23.168 -
23.169 -
23.170 -
23.171 -
23.172 - template <typename _Base>
23.173 - class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
23.174 - public:
23.175 -
23.176 - typedef IterableGraphExtender<_Base> Parent;
23.177 - typedef IterableUndirGraphExtender<_Base> Graph;
23.178 - typedef typename Parent::Node Node;
23.179 -
23.180 - typedef typename Parent::UndirEdge UndirEdge;
23.181 -
23.182 - class UndirEdgeIt : public Parent::UndirEdge {
23.183 - const Graph* graph;
23.184 - public:
23.185 -
23.186 - UndirEdgeIt() { }
23.187 -
23.188 - UndirEdgeIt(Invalid i) : UndirEdge(i) { }
23.189 -
23.190 - explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
23.191 - _graph.first(*static_cast<UndirEdge*>(this));
23.192 - }
23.193 -
23.194 - UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :
23.195 - UndirEdge(e), graph(&_graph) { }
23.196 -
23.197 - UndirEdgeIt& operator++() {
23.198 - graph->next(*this);
23.199 - return *this;
23.200 - }
23.201 -
23.202 - };
23.203 -
23.204 - class IncEdgeIt : public Parent::UndirEdge {
23.205 - const Graph* graph;
23.206 - bool forward;
23.207 - friend class IterableUndirGraphExtender;
23.208 - template <typename G>
23.209 - friend class UndirGraphExtender;
23.210 - public:
23.211 -
23.212 - IncEdgeIt() { }
23.213 -
23.214 - IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
23.215 -
23.216 - IncEdgeIt(const Graph& _graph, const Node &n)
23.217 - : graph(&_graph)
23.218 - {
23.219 - _graph._dirFirstOut(*this, n);
23.220 - }
23.221 -
23.222 - IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
23.223 - : graph(&_graph), UndirEdge(ue)
23.224 - {
23.225 - forward = (_graph.source(ue) == n);
23.226 - }
23.227 -
23.228 - IncEdgeIt& operator++() {
23.229 - graph->_dirNextOut(*this);
23.230 - return *this;
23.231 - }
23.232 - };
23.233 -
23.234 - using Parent::baseNode;
23.235 - using Parent::runningNode;
23.236 -
23.237 - /// Base node of the iterator
23.238 - ///
23.239 - /// Returns the base node of the iterator
23.240 - Node baseNode(const IncEdgeIt &e) const {
23.241 - return _dirSource(e);
23.242 - }
23.243 - /// Running node of the iterator
23.244 - ///
23.245 - /// Returns the running node of the iterator
23.246 - Node runningNode(const IncEdgeIt &e) const {
23.247 - return _dirTarget(e);
23.248 - }
23.249 -
23.250 - };
23.251 -}
23.252 -
23.253 -#endif // LEMON_GRAPH_EXTENDER_H
24.1 --- a/src/lemon/list_graph.h Tue Apr 05 09:49:01 2005 +0000
24.2 +++ b/src/lemon/list_graph.h Tue Apr 05 12:30:46 2005 +0000
24.3 @@ -21,14 +21,14 @@
24.4 ///\file
24.5 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
24.6
24.7 -#include <lemon/erasable_graph_extender.h>
24.8 -#include <lemon/clearable_graph_extender.h>
24.9 -#include <lemon/extendable_graph_extender.h>
24.10 -#include <lemon/iterable_graph_extender.h>
24.11 -#include <lemon/alteration_notifier.h>
24.12 -#include <lemon/default_map.h>
24.13 +#include <lemon/bits/erasable_graph_extender.h>
24.14 +#include <lemon/bits/clearable_graph_extender.h>
24.15 +#include <lemon/bits/extendable_graph_extender.h>
24.16 +#include <lemon/bits/iterable_graph_extender.h>
24.17 +#include <lemon/bits/alteration_notifier.h>
24.18 +#include <lemon/bits/default_map.h>
24.19
24.20 -#include <lemon/undir_graph_extender.h>
24.21 +#include <lemon/bits/undir_graph_extender.h>
24.22
24.23 #include <list>
24.24
25.1 --- a/src/lemon/map_iterator.h Tue Apr 05 09:49:01 2005 +0000
25.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
25.3 @@ -1,855 +0,0 @@
25.4 -/* -*- C++ -*-
25.5 - * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library
25.6 - *
25.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
25.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
25.9 - *
25.10 - * Permission to use, modify and distribute this software is granted
25.11 - * provided that this copyright notice appears in all copies. For
25.12 - * precise terms see the accompanying LICENSE file.
25.13 - *
25.14 - * This software is provided "AS IS" with no warranty of any kind,
25.15 - * express or implied, and with no claim as to its suitability for any
25.16 - * purpose.
25.17 - *
25.18 - */
25.19 -
25.20 -#ifndef LEMON_MAP_ITERATOR_H
25.21 -#define LEMON_MAP_ITERATOR_H
25.22 -
25.23 -#include <iterator>
25.24 -
25.25 -#include <lemon/extended_pair.h>
25.26 -#include <lemon/map_utils.h>
25.27 -
25.28 -///\ingroup graphmaps
25.29 -///\file
25.30 -///\brief Iterators on the maps.
25.31 -
25.32 -namespace lemon {
25.33 -
25.34 - /// \addtogroup graphmaps
25.35 - /// @{
25.36 -
25.37 - /** The base class all of the map iterators.
25.38 - * The class defines the typedefs of the iterators,
25.39 - * simple step functions and equality operators.
25.40 - */
25.41 -
25.42 - template <
25.43 - typename _Graph,
25.44 - typename _Item>
25.45 - class MapIteratorBase {
25.46 -
25.47 - protected:
25.48 -
25.49 - /// The key type of the iterator.
25.50 - typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
25.51 -
25.52 - ItemIt it;
25.53 -
25.54 - /// Default constructor.
25.55 - MapIteratorBase() {}
25.56 -
25.57 - /// ItemIt initialized MapIteratorBase constructor.
25.58 - MapIteratorBase(const ItemIt _it) : it(_it) {}
25.59 -
25.60 - public:
25.61 -
25.62 - /// Stepping forward in the map.
25.63 - void increment() {
25.64 - ++it;
25.65 - }
25.66 -
25.67 - /// The equality operator of the map.
25.68 - bool operator==(const MapIteratorBase& _it) const {
25.69 - return _it.it == it;
25.70 - }
25.71 -
25.72 - /// The not-equality operator of the map.
25.73 - bool operator!=(const MapIteratorBase& _it) const {
25.74 - return !(*this == _it);
25.75 - }
25.76 - };
25.77 -
25.78 -
25.79 - template <
25.80 - typename _Graph,
25.81 - typename _Item,
25.82 - typename _Map>
25.83 - class MapConstIterator;
25.84 -
25.85 - /** Compatible iterator with the stl maps' iterators.
25.86 - * It iterates on pairs of a key and a value.
25.87 - */
25.88 - template <
25.89 - typename _Graph,
25.90 - typename _Item,
25.91 - typename _Map>
25.92 - class MapIterator : public MapIteratorBase<_Graph, _Item> {
25.93 -
25.94 - friend class MapConstIterator<_Graph, _Item, _Map>;
25.95 -
25.96 -
25.97 - public:
25.98 -
25.99 - /// The iterator base class.
25.100 - typedef MapIteratorBase<_Graph, _Item> Parent;
25.101 -
25.102 - typedef _Item Item;
25.103 - typedef _Map Map;
25.104 - typedef _Graph Graph;
25.105 -
25.106 - protected:
25.107 -
25.108 - typedef typename Parent::ItemIt ItemIt;
25.109 -
25.110 - typedef typename ReferenceMapTraits<_Map>::Value MapValue;
25.111 - typedef typename ReferenceMapTraits<_Map>::Reference MapReference;
25.112 -
25.113 - public:
25.114 -
25.115 - /// The value type of the iterator.
25.116 - typedef extended_pair<Item, const Item&,
25.117 - MapValue, const MapValue&> Value;
25.118 -
25.119 - /// The reference type of the iterator.
25.120 - typedef extended_pair<const Item&, const Item&,
25.121 - MapReference, MapReference> Reference;
25.122 -
25.123 - /// Default constructor.
25.124 - MapIterator() {}
25.125 -
25.126 - /// Constructor to initalize the iterators returned
25.127 - /// by the begin() and end().
25.128 - MapIterator(Map& _map, const ItemIt& _it)
25.129 - : Parent(_it), map(&_map) {}
25.130 -
25.131 - /// Dereference operator for the iterator.
25.132 - Reference operator*() {
25.133 - return Reference(Parent::it, (*map)[Parent::it]);
25.134 - }
25.135 -
25.136 - /// The pointer type of the iterator.
25.137 - class Pointer {
25.138 - friend class MapIterator;
25.139 - protected:
25.140 - Reference data;
25.141 - Pointer(const Item& item, MapReference val)
25.142 - : data(item, val) {}
25.143 - public:
25.144 - Reference* operator->() {return &data;}
25.145 - };
25.146 -
25.147 - /// Arrow operator for the iterator.
25.148 - Pointer operator->() {
25.149 - return Pointer(Parent::it, (*map)[Parent::it]);
25.150 - }
25.151 -
25.152 - /// The pre increment operator of the iterator.
25.153 - MapIterator& operator++() {
25.154 - Parent::increment();
25.155 - return *this;
25.156 - }
25.157 -
25.158 - /// The post increment operator of the iterator.
25.159 - MapIterator operator++(int) {
25.160 - MapIterator tmp(*this);
25.161 - Parent::increment();
25.162 - return tmp;
25.163 - }
25.164 -
25.165 - protected:
25.166 -
25.167 - Map* map;
25.168 -
25.169 - public:
25.170 - // STL compatibility typedefs.
25.171 - typedef std::forward_iterator_tag iterator_category;
25.172 - typedef int difference_type;
25.173 - typedef Value value_type;
25.174 - typedef Reference reference;
25.175 - typedef Pointer pointer;
25.176 - };
25.177 -
25.178 - /** Compatible iterator with the stl maps' iterators.
25.179 - * It iterates on pairs of a key and a value.
25.180 - */
25.181 - template <
25.182 - typename _Graph,
25.183 - typename _Item,
25.184 - typename _Map>
25.185 - class MapConstIterator : public MapIteratorBase<_Graph, _Item> {
25.186 -
25.187 - public:
25.188 -
25.189 - /// The iterator base class.
25.190 - typedef MapIteratorBase<_Graph, _Item> Parent;
25.191 -
25.192 - typedef _Graph Graph;
25.193 - typedef _Item Item;
25.194 - typedef _Map Map;
25.195 -
25.196 - protected:
25.197 -
25.198 - typedef typename Parent::ItemIt ItemIt;
25.199 -
25.200 - typedef typename ReferenceMapTraits<_Map>::Value MapValue;
25.201 - typedef typename ReferenceMapTraits<_Map>::ConstReference
25.202 - MapReference;
25.203 -
25.204 - public:
25.205 -
25.206 - /// The value type of the iterator.
25.207 - typedef extended_pair<Item, const Item&,
25.208 - MapValue, const MapValue&> Value;
25.209 -
25.210 - /// The reference type of the iterator.
25.211 - typedef extended_pair<const Item&, const Item&,
25.212 - MapReference, MapReference> Reference;
25.213 -
25.214 - /// Default constructor.
25.215 - MapConstIterator() {}
25.216 -
25.217 - /// Constructor to initalize the iterators returned
25.218 - /// by the begin() and end().
25.219 - MapConstIterator(const Map& _map, const ItemIt& _it)
25.220 - : Parent(_it), map(&_map) {}
25.221 -
25.222 - /// Dereference operator for the iterator.
25.223 - Reference operator*() {
25.224 - return Reference(Parent::it, (*map)[Parent::it]);
25.225 - }
25.226 -
25.227 - /// The pointer type of the iterator.
25.228 - class Pointer {
25.229 - friend class MapConstIterator;
25.230 - protected:
25.231 - Reference data;
25.232 - Pointer(const Item& item, MapReference val)
25.233 - : data(item, val) {}
25.234 - public:
25.235 - Reference* operator->() {return &data;}
25.236 - };
25.237 -
25.238 - /// Arrow operator for the iterator.
25.239 - Pointer operator->() {
25.240 - return Pointer(Parent::it, ((*map)[Parent::it]));
25.241 - }
25.242 -
25.243 - /// The pre increment operator of the iterator.
25.244 - MapConstIterator& operator++() {
25.245 - Parent::increment();
25.246 - return *this;
25.247 - }
25.248 -
25.249 - /// The post increment operator of the iterator.
25.250 - MapConstIterator operator++(int) {
25.251 - MapConstIterator tmp(*this);
25.252 - Parent::increment();
25.253 - return tmp;
25.254 - }
25.255 -
25.256 - protected:
25.257 - const Map* map;
25.258 -
25.259 - public:
25.260 - // STL compatibility typedefs.
25.261 - typedef std::forward_iterator_tag iterator_category;
25.262 - typedef int difference_type;
25.263 - typedef Value value_type;
25.264 - typedef Reference reference;
25.265 - typedef Pointer pointer;
25.266 - };
25.267 -
25.268 - /** The class makes the ItemIt to an stl compatible iterator
25.269 - * with dereferencing operator.
25.270 - */
25.271 - template <
25.272 - typename _Graph,
25.273 - typename _Item>
25.274 - class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {
25.275 -
25.276 - public:
25.277 -
25.278 - /// The iterator base class.
25.279 - typedef MapIteratorBase<_Graph, _Item> Parent;
25.280 -
25.281 - typedef _Graph Graph;
25.282 - typedef _Item Item;
25.283 -
25.284 - protected:
25.285 - /// The iterator to iterate on the keys.
25.286 - typedef typename Parent::ItemIt ItemIt;
25.287 -
25.288 - public:
25.289 -
25.290 - typedef Item Value;
25.291 - typedef const Item& Reference;
25.292 - typedef const Item* Pointer;
25.293 -
25.294 - /// Default constructor.
25.295 - MapConstKeyIterator() {}
25.296 -
25.297 - /// ItemIt initialized iterator.
25.298 - MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}
25.299 -
25.300 - /// The pre increment operator of the iterator.
25.301 - MapConstKeyIterator& operator++() {
25.302 - Parent::increment();
25.303 - return *this;
25.304 - }
25.305 -
25.306 - /// The post increment operator of the iterator.
25.307 - MapConstKeyIterator operator++(int) {
25.308 - MapConstKeyIterator tmp(*this);
25.309 - Parent::increment();
25.310 - return tmp;
25.311 - }
25.312 -
25.313 - /// The dereferencing operator of the iterator.
25.314 - Item operator*() const {
25.315 - return static_cast<Item>(Parent::it);
25.316 - }
25.317 -
25.318 - public:
25.319 - // STL compatibility typedefs.
25.320 - typedef std::input_iterator_tag iterator_category;
25.321 - typedef int difference_type;
25.322 - typedef Value value_type;
25.323 - typedef Reference reference;
25.324 - typedef Pointer pointer;
25.325 - };
25.326 -
25.327 - template <
25.328 - typename _Graph,
25.329 - typename _Item,
25.330 - typename _Map>
25.331 - class MapConstValueIterator;
25.332 -
25.333 - /** MapValueIterator creates an stl compatible iterator
25.334 - * for the values.
25.335 - */
25.336 - template <
25.337 - typename _Graph,
25.338 - typename _Item,
25.339 - typename _Map>
25.340 - class MapValueIterator : public MapIteratorBase<_Graph, _Item> {
25.341 -
25.342 - friend class MapConstValueIterator<_Graph, _Item, _Map>;
25.343 -
25.344 - public:
25.345 -
25.346 - /// The iterator base class.
25.347 - typedef MapIteratorBase<_Graph, _Item> Parent;
25.348 -
25.349 - typedef _Graph Graph;
25.350 - typedef _Item Item;
25.351 - typedef _Map Map;
25.352 -
25.353 - protected:
25.354 -
25.355 - /// The iterator to iterate on the keys.
25.356 - typedef typename Parent::ItemIt ItemIt;
25.357 -
25.358 - /// The value type of the iterator.
25.359 - typedef typename ReferenceMapTraits<Map>::Value MapValue;
25.360 - /// The reference type of the iterator.
25.361 - typedef typename ReferenceMapTraits<Map>::Reference MapReference;
25.362 - /// The pointer type of the iterator.
25.363 - typedef typename ReferenceMapTraits<Map>::Pointer MapPointer;
25.364 -
25.365 - public:
25.366 -
25.367 - typedef MapValue Value;
25.368 - typedef MapReference Reference;
25.369 - typedef MapPointer Pointer;
25.370 -
25.371 - /// Default constructor.
25.372 - MapValueIterator() {}
25.373 -
25.374 - /// Map and ItemIt initialized iterator.
25.375 - MapValueIterator(Map& _map, const ItemIt& _it)
25.376 - : Parent(_it), map(&_map) {}
25.377 -
25.378 -
25.379 - /// The pre increment operator of the iterator.
25.380 - MapValueIterator& operator++() {
25.381 - Parent::increment();
25.382 - return *this;
25.383 - }
25.384 -
25.385 - /// The post increment operator of the iterator.
25.386 - MapValueIterator operator++(int) {
25.387 - MapValueIterator tmp(*this);
25.388 - Parent::increment();
25.389 - return tmp;
25.390 - }
25.391 -
25.392 - /// The dereferencing operator of the iterator.
25.393 - Reference operator*() const {
25.394 - return (*map)[Parent::it];
25.395 - }
25.396 -
25.397 - /// The arrow operator of the iterator.
25.398 - Pointer operator->() const {
25.399 - return &(operator*());
25.400 - }
25.401 -
25.402 - protected:
25.403 -
25.404 - Map* map;
25.405 -
25.406 - public:
25.407 - // STL compatibility typedefs.
25.408 - typedef std::forward_iterator_tag iterator_category;
25.409 - typedef int difference_type;
25.410 - typedef Value value_type;
25.411 - typedef Reference reference;
25.412 - typedef Pointer pointer;
25.413 - };
25.414 -
25.415 - /** MapValueIterator creates an stl compatible iterator
25.416 - * for the values.
25.417 - */
25.418 - template <
25.419 - typename _Graph,
25.420 - typename _Item,
25.421 - typename _Map>
25.422 - class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {
25.423 -
25.424 - public:
25.425 -
25.426 - /// The iterator base class.
25.427 - typedef MapIteratorBase<_Graph, _Item> Parent;
25.428 -
25.429 - typedef _Graph Graph;
25.430 - typedef _Item Item;
25.431 - typedef _Map Map;
25.432 -
25.433 - protected:
25.434 -
25.435 - /// The iterator to iterate on the keys.
25.436 - typedef typename Parent::ItemIt ItemIt;
25.437 -
25.438 - /// The value type of the iterator.
25.439 - typedef typename ReferenceMapTraits<Map>::Value MapValue;
25.440 - /// The reference type of the iterator.
25.441 - typedef typename ReferenceMapTraits<Map>::ConstReference MapReference;
25.442 - /// The pointer type of the iterator.
25.443 - typedef typename ReferenceMapTraits<Map>::ConstPointer MapPointer;
25.444 -
25.445 - public:
25.446 -
25.447 - typedef MapValue Value;
25.448 - typedef MapReference Reference;
25.449 - typedef MapPointer Pointer;
25.450 -
25.451 - /// Default constructor.
25.452 - MapConstValueIterator() {}
25.453 -
25.454 - /// Map and ItemIt initialized iterator.
25.455 - MapConstValueIterator(const Map& _map, const ItemIt& _it)
25.456 - : Parent(_it), map(&_map) {}
25.457 -
25.458 -
25.459 - /// The pre increment operator of the iterator.
25.460 - MapConstValueIterator& operator++() {
25.461 - Parent::increment();
25.462 - return *this;
25.463 - }
25.464 -
25.465 - /// The post increment operator of the iterator.
25.466 - MapConstValueIterator operator++(int) {
25.467 - MapConstValueIterator tmp(*this);
25.468 - Parent::increment();
25.469 - return tmp;
25.470 - }
25.471 -
25.472 - /// The dereferencing operator of the iterator.
25.473 - Reference operator*() const {
25.474 - return (*map)[Parent::it];
25.475 - }
25.476 -
25.477 - /// The arrow operator of the iterator.
25.478 - Pointer operator->() const {
25.479 - return &(operator*());
25.480 - }
25.481 -
25.482 - protected:
25.483 -
25.484 - const Map* map;
25.485 -
25.486 - public:
25.487 - // STL compatibility typedefs.
25.488 - typedef std::forward_iterator_tag iterator_category;
25.489 - typedef int difference_type;
25.490 - typedef Value value_type;
25.491 - typedef Reference reference;
25.492 - typedef Pointer pointer;
25.493 - };
25.494 -
25.495 -
25.496 - /** This class makes from a map an iteratable set
25.497 - * which contains all the keys of the map.
25.498 - */
25.499 - template <typename _Graph, typename _Item>
25.500 - class MapConstKeySet {
25.501 -
25.502 - public:
25.503 -
25.504 - typedef _Graph Graph;
25.505 - /// The key type of the iterator.
25.506 - typedef _Item Item;
25.507 - /// The iterator to iterate on the keys.
25.508 -
25.509 - protected:
25.510 -
25.511 - typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
25.512 -
25.513 - public:
25.514 -
25.515 - /// The map initialized const key set.
25.516 - MapConstKeySet(const Graph& _graph) : graph(&_graph) {}
25.517 -
25.518 - /// The const iterator of the set.
25.519 - typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;
25.520 -
25.521 - typedef typename ConstIterator::Value Value;
25.522 - /// The reference type of the iterator.
25.523 - typedef typename ConstIterator::Reference ConstReference;
25.524 - /// The pointer type of the iterator.
25.525 - typedef typename ConstIterator::Pointer ConstPointer;
25.526 -
25.527 - /// It gives back the const iterator pointed to the first element.
25.528 - ConstIterator begin() const {
25.529 - return ConstIterator(ItemIt(*graph));
25.530 - }
25.531 -
25.532 - /// It gives back the const iterator pointed to the first ivalid element.
25.533 - ConstIterator end() const {
25.534 - return ConstIterator(ItemIt(INVALID));
25.535 - }
25.536 -
25.537 - protected:
25.538 -
25.539 - const Graph* graph;
25.540 -
25.541 - public:
25.542 - // STL compatibility typedefs.
25.543 - typedef Value value_type;
25.544 - typedef ConstIterator const_iterator;
25.545 - typedef ConstReference const_reference;
25.546 - typedef ConstPointer const_pointer;
25.547 - typedef int difference_type;
25.548 - };
25.549 -
25.550 - /** This class makes from a map an iteratable set
25.551 - * which contains all the values of the map.
25.552 - * The values cannot be modified.
25.553 - */
25.554 - template <typename _Graph, typename _Item, typename _Map>
25.555 - class MapConstValueSet {
25.556 -
25.557 - public:
25.558 -
25.559 - typedef _Graph Graph;
25.560 - typedef _Item Item;
25.561 - typedef _Map Map;
25.562 -
25.563 - protected:
25.564 -
25.565 - /// The iterator to iterate on the keys.
25.566 - typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
25.567 -
25.568 - public:
25.569 -
25.570 - /// The map initialized const value set.
25.571 - MapConstValueSet(const Graph& _graph, const Map& _map)
25.572 - : graph(&_graph), map(&_map) {}
25.573 -
25.574 - /// The const iterator of the set.
25.575 - typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
25.576 -
25.577 - typedef typename ConstIterator::Value Value;
25.578 - typedef typename ConstIterator::Reference ConstReference;
25.579 - typedef typename ConstIterator::Pointer ConstPointer;
25.580 -
25.581 - /// It gives back the const iterator pointed to the first element.
25.582 - ConstIterator begin() const {
25.583 - return ConstIterator(*map, ItemIt(*graph));
25.584 - }
25.585 -
25.586 - /// It gives back the const iterator pointed to the first invalid element.
25.587 - ConstIterator end() const {
25.588 - return ConstIterator(*map, ItemIt(INVALID));
25.589 - }
25.590 -
25.591 - protected:
25.592 -
25.593 - const Map* map;
25.594 - const Graph * graph;
25.595 -
25.596 - public:
25.597 - // STL compatibility typedefs.
25.598 - typedef Value value_type;
25.599 - typedef ConstIterator const_iterator;
25.600 - typedef ConstReference const_reference;
25.601 - typedef ConstPointer const_pointer;
25.602 - typedef int difference_type;
25.603 - };
25.604 -
25.605 -
25.606 - /** This class makes from a map an iteratable set
25.607 - * which contains all the values of the map.
25.608 - * The values can be modified.
25.609 - */
25.610 - template <typename _Graph, typename _Item, typename _Map>
25.611 - class MapValueSet {
25.612 -
25.613 - public:
25.614 -
25.615 - typedef _Graph Graph;
25.616 - typedef _Item Item;
25.617 - typedef _Map Map;
25.618 -
25.619 - protected:
25.620 -
25.621 - /// The iterator to iterate on the keys.
25.622 - typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
25.623 -
25.624 - public:
25.625 -
25.626 - /// The map initialized const value set.
25.627 - MapValueSet(const Graph& _graph, Map& _map)
25.628 - : map(&_map), graph(&_graph) {}
25.629 -
25.630 - /// The const iterator of the set.
25.631 - typedef MapValueIterator<_Graph, _Item, _Map> Iterator;
25.632 - /// The const iterator of the set.
25.633 - typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
25.634 -
25.635 - typedef typename ConstIterator::Value Value;
25.636 - typedef typename Iterator::Reference Reference;
25.637 - typedef typename Iterator::Pointer Pointer;
25.638 - typedef typename ConstIterator::Reference ConstReference;
25.639 - typedef typename ConstIterator::Pointer ConstPointer;
25.640 -
25.641 - /// It gives back the const iterator pointed to the first element.
25.642 - ConstIterator begin() const {
25.643 - return ConstIterator(*map, ItemIt(*graph));
25.644 - }
25.645 -
25.646 - /// It gives back the const iterator pointed to the first invalid element.
25.647 - ConstIterator end() const {
25.648 - return ConstIterator(*map, ItemIt(INVALID));
25.649 - }
25.650 -
25.651 - /// It gives back the iterator pointed to the first element.
25.652 - Iterator begin() {
25.653 - return Iterator(*map, ItemIt(*graph));
25.654 - }
25.655 -
25.656 - /// It gives back the iterator pointed to the first invalid element.
25.657 - Iterator end() {
25.658 - return Iterator(*map, ItemIt(INVALID));
25.659 - }
25.660 -
25.661 - protected:
25.662 -
25.663 - Map* map;
25.664 - const Graph * graph;
25.665 -
25.666 - public:
25.667 - // STL compatibility typedefs.
25.668 - typedef Value value_type;
25.669 - typedef Iterator iterator;
25.670 - typedef ConstIterator const_iterator;
25.671 - typedef Reference reference;
25.672 - typedef ConstReference const_reference;
25.673 - typedef Pointer pointer;
25.674 - typedef ConstPointer const_pointer;
25.675 - typedef int difference_type;
25.676 -
25.677 - };
25.678 -
25.679 - /** This class makes from a map an iteratable set
25.680 - * which contains all the values of the map.
25.681 - * The values can be modified.
25.682 - */
25.683 - template <
25.684 - typename _Graph,
25.685 - typename _Item,
25.686 - typename _Map
25.687 - >
25.688 - class MapSet {
25.689 - public:
25.690 -
25.691 - typedef _Graph Graph;
25.692 - typedef _Item Item;
25.693 - typedef _Map Map;
25.694 -
25.695 - protected:
25.696 -
25.697 - typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
25.698 -
25.699 - public:
25.700 -
25.701 - /// The map initialized value set.
25.702 - MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}
25.703 -
25.704 - /// The const iterator of the set.
25.705 - typedef MapIterator<_Graph, _Item, _Map> Iterator;
25.706 - typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
25.707 -
25.708 - typedef typename ConstIterator::Value Value;
25.709 - typedef typename Iterator::Reference Reference;
25.710 - typedef typename Iterator::Pointer Pointer;
25.711 - typedef typename ConstIterator::Reference ConstReference;
25.712 - typedef typename ConstIterator::Pointer ConstPointer;
25.713 -
25.714 -
25.715 - /// It gives back the const iterator pointed to the first element.
25.716 - ConstIterator begin() const {
25.717 - return ConstIterator(*map, ItemIt(*graph));
25.718 - }
25.719 -
25.720 - /// It gives back the const iterator pointed to the first invalid element.
25.721 - ConstIterator end() const {
25.722 - return ConstIterator(*map, ItemIt(INVALID));
25.723 - }
25.724 -
25.725 - /// The iterator of the set.
25.726 -
25.727 - /// It gives back the iterator pointed to the first element.
25.728 - Iterator begin() {
25.729 - return Iterator(*map, ItemIt(*graph));
25.730 - }
25.731 -
25.732 - /// It gives back the iterator pointed to the first invalid element.
25.733 - Iterator end() {
25.734 - return Iterator(*map, ItemIt(INVALID));
25.735 - }
25.736 -
25.737 - protected:
25.738 -
25.739 - const Graph* graph;
25.740 - Map* map;
25.741 -
25.742 - public:
25.743 - // STL compatibility typedefs.
25.744 - typedef Value value_type;
25.745 - typedef Iterator iterator;
25.746 - typedef ConstIterator const_iterator;
25.747 - typedef Reference reference;
25.748 - typedef ConstReference const_reference;
25.749 - typedef Pointer pointer;
25.750 - typedef ConstPointer const_pointer;
25.751 - typedef int difference_type;
25.752 -
25.753 - };
25.754 -
25.755 - template <
25.756 - typename _Graph,
25.757 - typename _Item,
25.758 - typename _Map
25.759 - >
25.760 - class ConstMapSet {
25.761 -
25.762 - typedef _Graph Graph;
25.763 - typedef _Map Map;
25.764 -
25.765 - const Graph* graph;
25.766 - const Map* map;
25.767 -
25.768 - public:
25.769 -
25.770 - typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
25.771 -
25.772 -
25.773 - /// The map initialized value set.
25.774 - ConstMapSet(const Graph& _graph, const Map& _map)
25.775 - : graph(&_graph), map(&_map) {}
25.776 -
25.777 - /// The const iterator of the set.
25.778 - typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
25.779 -
25.780 - typedef typename ConstIterator::Value Value;
25.781 - typedef typename ConstIterator::Reference ConstReference;
25.782 - typedef typename ConstIterator::Pointer ConstPointer;
25.783 -
25.784 -
25.785 - /// It gives back the const iterator pointed to the first element.
25.786 - ConstIterator begin() const {
25.787 - return ConstIterator(*map, ItemIt(*graph));
25.788 - }
25.789 -
25.790 - /// It gives back the const iterator pointed to the first invalid element.
25.791 - ConstIterator end() const {
25.792 - return ConstIterator(*map, ItemIt(INVALID));
25.793 - }
25.794 -
25.795 - public:
25.796 - // STL compatibility typedefs.
25.797 - typedef Value value_type;
25.798 - typedef ConstIterator const_iterator;
25.799 - typedef ConstReference const_reference;
25.800 - typedef ConstPointer const_pointer;
25.801 - typedef int difference_type;
25.802 -
25.803 - };
25.804 -
25.805 - template <typename _Map>
25.806 - class IterableMapExtender : public _Map {
25.807 - public:
25.808 -
25.809 - typedef _Map Parent;
25.810 - typedef Parent Map;
25.811 - typedef typename Map::Graph Graph;
25.812 - typedef typename Map::Key Item;
25.813 - typedef typename Map::Value Value;
25.814 -
25.815 - typedef MapSet<Graph, Item, Map> MapSet;
25.816 -
25.817 - IterableMapExtender() : Parent() {}
25.818 -
25.819 - IterableMapExtender(const Graph& graph) : Parent(graph) {}
25.820 -
25.821 - IterableMapExtender(const Graph& graph, const Value& value)
25.822 - : Parent(graph, value) {}
25.823 -
25.824 - MapSet mapSet() {
25.825 - return MapSet(*Parent::getGraph(), *this);
25.826 - }
25.827 -
25.828 - typedef ConstMapSet<Graph, Item, Map> ConstMapSet;
25.829 -
25.830 - ConstMapSet mapSet() const {
25.831 - return ConstMapSet(*Parent::getGraph(), *this);
25.832 - }
25.833 -
25.834 - typedef MapConstKeySet<Graph, Item> ConstKeySet;
25.835 -
25.836 - ConstKeySet keySet() const {
25.837 - return ConstKeySet(*Parent::getGraph());
25.838 - }
25.839 -
25.840 - typedef MapValueSet<Graph, Item, Map> ValueSet;
25.841 -
25.842 - ValueSet valueSet() {
25.843 - return ValueSet(*Parent::getGraph(), *this);
25.844 - }
25.845 -
25.846 - typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;
25.847 -
25.848 - ConstValueSet valueSet() const {
25.849 - return ConstValueSet(*Parent::getGraph(), *this);
25.850 - }
25.851 -
25.852 - };
25.853 -
25.854 - /// @}
25.855 -
25.856 -}
25.857 -
25.858 -#endif
26.1 --- a/src/lemon/smart_graph.h Tue Apr 05 09:49:01 2005 +0000
26.2 +++ b/src/lemon/smart_graph.h Tue Apr 05 12:30:46 2005 +0000
26.3 @@ -25,13 +25,13 @@
26.4
26.5 #include <lemon/invalid.h>
26.6
26.7 -#include <lemon/clearable_graph_extender.h>
26.8 -#include <lemon/extendable_graph_extender.h>
26.9 -#include <lemon/iterable_graph_extender.h>
26.10 -#include <lemon/alteration_notifier.h>
26.11 -#include <lemon/default_map.h>
26.12 +#include <lemon/bits/clearable_graph_extender.h>
26.13 +#include <lemon/bits/extendable_graph_extender.h>
26.14 +#include <lemon/bits/iterable_graph_extender.h>
26.15 +#include <lemon/bits/alteration_notifier.h>
26.16 +#include <lemon/bits/default_map.h>
26.17
26.18 -#include <lemon/undir_graph_extender.h>
26.19 +#include <lemon/bits/undir_graph_extender.h>
26.20
26.21 #include <lemon/utility.h>
26.22
27.1 --- a/src/lemon/undir_graph_extender.h Tue Apr 05 09:49:01 2005 +0000
27.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
27.3 @@ -1,278 +0,0 @@
27.4 -/* -*- C++ -*-
27.5 - *
27.6 - * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++
27.7 - * optimization library
27.8 - *
27.9 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
27.10 - * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
27.11 - * EGRES).
27.12 - *
27.13 - * Permission to use, modify and distribute this software is granted
27.14 - * provided that this copyright notice appears in all copies. For
27.15 - * precise terms see the accompanying LICENSE file.
27.16 - *
27.17 - * This software is provided "AS IS" with no warranty of any kind,
27.18 - * express or implied, and with no claim as to its suitability for any
27.19 - * purpose.
27.20 - *
27.21 - */
27.22 -
27.23 -#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
27.24 -#define LEMON_UNDIR_GRAPH_EXTENDER_H
27.25 -
27.26 -#include <lemon/invalid.h>
27.27 -
27.28 -namespace lemon {
27.29 -
27.30 - template <typename _Base>
27.31 - class UndirGraphExtender : public _Base {
27.32 - typedef _Base Parent;
27.33 - typedef UndirGraphExtender Graph;
27.34 -
27.35 - public:
27.36 -
27.37 - typedef typename Parent::Edge UndirEdge;
27.38 - typedef typename Parent::Node Node;
27.39 -
27.40 - class Edge : public UndirEdge {
27.41 - friend class UndirGraphExtender;
27.42 -
27.43 - protected:
27.44 - // FIXME: Marci use opposite logic in his graph wrappers. It would
27.45 - // be reasonable to syncronize...
27.46 - bool forward;
27.47 -
27.48 - public:
27.49 - Edge() {}
27.50 -
27.51 - /// \brief Directed edge from undirected edge and a direction.
27.52 - ///
27.53 - /// This constructor is not a part of the concept interface of
27.54 - /// undirected graph, so please avoid using it if possible!
27.55 - Edge(const UndirEdge &ue, bool _forward) :
27.56 - UndirEdge(ue), forward(_forward) {}
27.57 -
27.58 - /// \brief Directed edge from undirected edge and a source node.
27.59 - ///
27.60 - /// Constructs a directed edge from undirected edge and a source node.
27.61 - ///
27.62 - /// \note You have to specify the graph for this constructor.
27.63 - Edge(const Graph &g, const UndirEdge &ue, const Node &n) :
27.64 - UndirEdge(ue) { forward = (g.source(ue) == n); }
27.65 -
27.66 - /// Invalid edge constructor
27.67 - Edge(Invalid i) : UndirEdge(i), forward(true) {}
27.68 -
27.69 - bool operator==(const Edge &that) const {
27.70 - return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
27.71 - }
27.72 - bool operator!=(const Edge &that) const {
27.73 - return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
27.74 - }
27.75 - bool operator<(const Edge &that) const {
27.76 - return forward<that.forward ||
27.77 - (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
27.78 - }
27.79 - };
27.80 -
27.81 -
27.82 - /// \brief Edge of opposite direction.
27.83 - ///
27.84 - /// Returns the Edge of opposite direction.
27.85 - Edge opposite(const Edge &e) const {
27.86 - return Edge(e,!e.forward);
27.87 - }
27.88 -
27.89 - protected:
27.90 -
27.91 - template <typename E>
27.92 - Node _dirSource(const E &e) const {
27.93 - return e.forward ? Parent::source(e) : Parent::target(e);
27.94 - }
27.95 -
27.96 - template <typename E>
27.97 - Node _dirTarget(const E &e) const {
27.98 - return e.forward ? Parent::target(e) : Parent::source(e);
27.99 - }
27.100 -
27.101 - public:
27.102 - /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
27.103 - /// or something???
27.104 - using Parent::source;
27.105 -
27.106 - /// Source of the given Edge.
27.107 - Node source(const Edge &e) const {
27.108 - return _dirSource(e);
27.109 - }
27.110 -
27.111 - /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
27.112 - /// or something???
27.113 - using Parent::target;
27.114 -
27.115 - /// Target of the given Edge.
27.116 - Node target(const Edge &e) const {
27.117 - return _dirTarget(e);
27.118 - }
27.119 -
27.120 - /// Returns whether the given directed edge is same orientation as the
27.121 - /// corresponding undirected edge.
27.122 - ///
27.123 - /// \todo reference to the corresponding point of the undirected graph
27.124 - /// concept. "What does the direction of an undirected edge mean?"
27.125 - bool forward(const Edge &e) const { return e.forward; }
27.126 -
27.127 - Node oppositeNode(const Node &n, const UndirEdge &e) const {
27.128 - if( n == Parent::source(e))
27.129 - return Parent::target(e);
27.130 - else if( n == Parent::target(e))
27.131 - return Parent::source(e);
27.132 - else
27.133 - return INVALID;
27.134 - }
27.135 -
27.136 - /// Directed edge from an undirected edge and a source node.
27.137 - ///
27.138 - /// Returns a (directed) Edge corresponding to the specified UndirEdge
27.139 - /// and source Node.
27.140 - ///
27.141 - ///\todo Do we need this?
27.142 - ///
27.143 - ///\todo Better name...
27.144 - Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
27.145 - return Edge(*this, ue, s);
27.146 - }
27.147 -
27.148 - using Parent::first;
27.149 - void first(Edge &e) const {
27.150 - Parent::first(e);
27.151 - e.forward=true;
27.152 - }
27.153 -
27.154 - using Parent::next;
27.155 - void next(Edge &e) const {
27.156 - if( e.forward ) {
27.157 - e.forward = false;
27.158 - }
27.159 - else {
27.160 - Parent::next(e);
27.161 - e.forward = true;
27.162 - }
27.163 - }
27.164 -
27.165 -
27.166 - protected:
27.167 -
27.168 - template <typename E>
27.169 - void _dirFirstOut(E &e, const Node &n) const {
27.170 - Parent::firstIn(e,n);
27.171 - if( UndirEdge(e) != INVALID ) {
27.172 - e.forward = false;
27.173 - }
27.174 - else {
27.175 - Parent::firstOut(e,n);
27.176 - e.forward = true;
27.177 - }
27.178 - }
27.179 - template <typename E>
27.180 - void _dirFirstIn(E &e, const Node &n) const {
27.181 - Parent::firstOut(e,n);
27.182 - if( UndirEdge(e) != INVALID ) {
27.183 - e.forward = false;
27.184 - }
27.185 - else {
27.186 - Parent::firstIn(e,n);
27.187 - e.forward = true;
27.188 - }
27.189 - }
27.190 -
27.191 - template <typename E>
27.192 - void _dirNextOut(E &e) const {
27.193 - if( ! e.forward ) {
27.194 - Node n = Parent::target(e);
27.195 - Parent::nextIn(e);
27.196 - if( UndirEdge(e) == INVALID ) {
27.197 - Parent::firstOut(e, n);
27.198 - e.forward = true;
27.199 - }
27.200 - }
27.201 - else {
27.202 - Parent::nextOut(e);
27.203 - }
27.204 - }
27.205 - template <typename E>
27.206 - void _dirNextIn(E &e) const {
27.207 - if( ! e.forward ) {
27.208 - Node n = Parent::source(e);
27.209 - Parent::nextOut(e);
27.210 - if( UndirEdge(e) == INVALID ) {
27.211 - Parent::firstIn(e, n);
27.212 - e.forward = true;
27.213 - }
27.214 - }
27.215 - else {
27.216 - Parent::nextIn(e);
27.217 - }
27.218 - }
27.219 -
27.220 - public:
27.221 -
27.222 - void firstOut(Edge &e, const Node &n) const {
27.223 - _dirFirstOut(e, n);
27.224 - }
27.225 - void firstIn(Edge &e, const Node &n) const {
27.226 - _dirFirstIn(e, n);
27.227 - }
27.228 -
27.229 - void nextOut(Edge &e) const {
27.230 - _dirNextOut(e);
27.231 - }
27.232 - void nextIn(Edge &e) const {
27.233 - _dirNextIn(e);
27.234 - }
27.235 -
27.236 - // Miscellaneous stuff:
27.237 -
27.238 - /// \todo these methods (id, maxEdgeId) should be moved into separate
27.239 - /// Extender
27.240 -
27.241 - // using Parent::id;
27.242 - // Using "using" is not a good idea, cause it could be that there is
27.243 - // no "id" in Parent...
27.244 -
27.245 - int id(const Node &n) const {
27.246 - return Parent::id(n);
27.247 - }
27.248 -
27.249 - int id(const UndirEdge &e) const {
27.250 - return Parent::id(e);
27.251 - }
27.252 -
27.253 - int id(const Edge &e) const {
27.254 - return 2 * Parent::id(e) + int(e.forward);
27.255 - }
27.256 -
27.257 -
27.258 - int maxId(Node) const {
27.259 - return Parent::maxId(Node());
27.260 - }
27.261 -
27.262 - int maxId(Edge) const {
27.263 - return 2 * Parent::maxId(typename Parent::Edge()) + 1;
27.264 - }
27.265 - int maxId(UndirEdge) const {
27.266 - return Parent::maxId(typename Parent::Edge());
27.267 - }
27.268 -
27.269 -
27.270 - int edgeNum() const {
27.271 - return 2 * Parent::edgeNum();
27.272 - }
27.273 - int undirEdgeNum() const {
27.274 - return Parent::edgeNum();
27.275 - }
27.276 -
27.277 - };
27.278 -
27.279 -}
27.280 -
27.281 -#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
28.1 --- a/src/lemon/vector_map.h Tue Apr 05 09:49:01 2005 +0000
28.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
28.3 @@ -1,287 +0,0 @@
28.4 -/* -*- C++ -*-
28.5 - * src/lemon/vector_map.h - Part of LEMON, a generic C++ optimization library
28.6 - *
28.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
28.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
28.9 - *
28.10 - * Permission to use, modify and distribute this software is granted
28.11 - * provided that this copyright notice appears in all copies. For
28.12 - * precise terms see the accompanying LICENSE file.
28.13 - *
28.14 - * This software is provided "AS IS" with no warranty of any kind,
28.15 - * express or implied, and with no claim as to its suitability for any
28.16 - * purpose.
28.17 - *
28.18 - */
28.19 -
28.20 -#ifndef LEMON_VECTOR_MAP_H
28.21 -#define LEMON_VECTOR_MAP_H
28.22 -
28.23 -#include <vector>
28.24 -#include <algorithm>
28.25 -
28.26 -#include <lemon/utility.h>
28.27 -#include <lemon/map_iterator.h>
28.28 -#include <lemon/alteration_notifier.h>
28.29 -
28.30 -///\ingroup graphmaps
28.31 -///\file
28.32 -///\brief Vector based graph maps.
28.33 -
28.34 -namespace lemon {
28.35 -
28.36 - /// \addtogroup graphmaps
28.37 - /// @{
28.38 -
28.39 - /// The VectorMap template class is graph map structure what
28.40 - /// automatically updates the map when a key is added to or erased from
28.41 - /// the map. This map factory uses the allocators to implement
28.42 - /// the container functionality. This map factory
28.43 - /// uses the std::vector to implement the container function.
28.44 - ///
28.45 - /// \param Registry The AlterationNotifier that will notify this map.
28.46 - /// \param IdMap The IdMap type of the graph items.
28.47 - /// \param Value The value type of the map.
28.48 - ///
28.49 - /// \author Balazs Dezso
28.50 -
28.51 -
28.52 - template <
28.53 - typename _Graph,
28.54 - typename _Item,
28.55 - typename _Value
28.56 - >
28.57 - class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
28.58 - public:
28.59 -
28.60 - /// The graph type of the map.
28.61 - typedef _Graph Graph;
28.62 - /// The key type of the map.
28.63 - typedef _Item Key;
28.64 - /// The id map type of the map.
28.65 - typedef AlterationNotifier<_Item> Registry;
28.66 - /// The value type of the map.
28.67 - typedef _Value Value;
28.68 -
28.69 - /// The map type.
28.70 - typedef VectorMap Map;
28.71 - /// The base class of the map.
28.72 - typedef typename Registry::ObserverBase Parent;
28.73 -
28.74 - private:
28.75 -
28.76 - /// The container type of the map.
28.77 - typedef std::vector<Value> Container;
28.78 -
28.79 - public:
28.80 -
28.81 - /// The reference type of the map;
28.82 - typedef typename Container::reference Reference;
28.83 - /// The pointer type of the map;
28.84 - typedef typename Container::pointer Pointer;
28.85 -
28.86 - /// The const value type of the map.
28.87 - typedef const Value ConstValue;
28.88 - /// The const reference type of the map;
28.89 - typedef typename Container::const_reference ConstReference;
28.90 - /// The pointer type of the map;
28.91 - typedef typename Container::const_pointer ConstPointer;
28.92 -
28.93 - typedef True FullTypeTag;
28.94 -
28.95 - /// Constructor to attach the new map into the registry.
28.96 -
28.97 - /// It construates a map and attachs it into the registry.
28.98 - /// It adds all the items of the graph to the map.
28.99 -
28.100 - VectorMap(const Graph& _g) : graph(&_g) {
28.101 - attach(_g.getNotifier(_Item()));
28.102 - build();
28.103 - }
28.104 -
28.105 - /// Constructor uses given value to initialize the map.
28.106 -
28.107 - /// It construates a map uses a given value to initialize the map.
28.108 - /// It adds all the items of the graph to the map.
28.109 -
28.110 - VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
28.111 - attach(_g.getNotifier(_Item()));
28.112 - container.resize(graph->maxId(_Item()) + 1, _v);
28.113 - }
28.114 -
28.115 - VectorMap(const VectorMap& _copy) : graph(_copy.getGraph()) {
28.116 - if (_copy.attached()) {
28.117 - attach(*_copy.getRegistry());
28.118 - container = _copy.container;
28.119 - }
28.120 - }
28.121 -
28.122 - using Parent::attach;
28.123 - using Parent::detach;
28.124 - using Parent::attached;
28.125 -
28.126 - /** Assign operator to copy a map of the same map type.
28.127 - */
28.128 - VectorMap& operator=(const VectorMap& copy) {
28.129 - if (© == this) return *this;
28.130 -
28.131 - if (graph != copy.graph) {
28.132 - if (attached()) {
28.133 - detach();
28.134 - }
28.135 - if (copy.attached()) {
28.136 - attach(*copy.getRegistry());
28.137 - }
28.138 - }
28.139 - container = copy.container;
28.140 -
28.141 - return *this;
28.142 - }
28.143 -
28.144 -
28.145 - virtual ~VectorMap() {
28.146 - if (attached()) {
28.147 - detach();
28.148 - }
28.149 - }
28.150 -
28.151 - const Graph* getGraph() const {
28.152 - return graph;
28.153 - }
28.154 -
28.155 - /// The subcript operator.
28.156 -
28.157 - /// The subscript operator. The map can be subscripted by the
28.158 - /// actual items of the graph.
28.159 -
28.160 - Reference operator[](const Key& key) {
28.161 - return container[graph->id(key)];
28.162 - }
28.163 -
28.164 - /// The const subcript operator.
28.165 -
28.166 - /// The const subscript operator. The map can be subscripted by the
28.167 - /// actual items of the graph.
28.168 -
28.169 - ConstReference operator[](const Key& key) const {
28.170 - return container[graph->id(key)];
28.171 - }
28.172 -
28.173 -
28.174 - /// The setter function of the map.
28.175 -
28.176 - /// It the same as operator[](key) = value expression.
28.177 - ///
28.178 -
28.179 - void set(const Key& key, const Value& value) {
28.180 - (*this)[key] = value;
28.181 - }
28.182 -
28.183 - /// Adds a new key to the map.
28.184 -
28.185 - /// It adds a new key to the map. It called by the observer registry
28.186 - /// and it overrides the add() member function of the observer base.
28.187 -
28.188 - void add(const Key& key) {
28.189 - int id = graph->id(key);
28.190 - if (id >= (int)container.size()) {
28.191 - container.resize(id + 1);
28.192 - }
28.193 - }
28.194 -
28.195 - /// Erases a key from the map.
28.196 -
28.197 - /// Erase a key from the map. It called by the observer registry
28.198 - /// and it overrides the erase() member function of the observer base.
28.199 - void erase(const Key&) {}
28.200 -
28.201 - /// Buildes the map.
28.202 -
28.203 - /// It buildes the map. It called by the observer registry
28.204 - /// and it overrides the build() member function of the observer base.
28.205 -
28.206 - void build() {
28.207 - container.resize(graph->maxId(_Item()) + 1);
28.208 - }
28.209 -
28.210 - /// Clear the map.
28.211 -
28.212 - /// It erase all items from the map. It called by the observer registry
28.213 - /// and it overrides the clear() member function of the observer base.
28.214 - void clear() {
28.215 - container.clear();
28.216 - }
28.217 -
28.218 - private:
28.219 -
28.220 - Container container;
28.221 - const Graph *graph;
28.222 -
28.223 - };
28.224 -
28.225 -
28.226 - template <typename _Base>
28.227 - class VectorMappableGraphExtender : public _Base {
28.228 - public:
28.229 -
28.230 - typedef VectorMappableGraphExtender<_Base> Graph;
28.231 - typedef _Base Parent;
28.232 -
28.233 - typedef typename Parent::Node Node;
28.234 - typedef typename Parent::NodeIt NodeIt;
28.235 - typedef typename Parent::NodeIdMap NodeIdMap;
28.236 - typedef typename Parent::NodeNotifier NodeObserverRegistry;
28.237 -
28.238 - typedef typename Parent::Edge Edge;
28.239 - typedef typename Parent::EdgeIt EdgeIt;
28.240 - typedef typename Parent::EdgeIdMap EdgeIdMap;
28.241 - typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
28.242 -
28.243 -
28.244 - template <typename _Value>
28.245 - class NodeMap :
28.246 - public IterableMapExtender<VectorMap<Graph, Node, _Value> > {
28.247 - public:
28.248 - typedef VectorMappableGraphExtender<_Base> Graph;
28.249 -
28.250 - typedef typename Graph::Node Node;
28.251 -
28.252 - typedef IterableMapExtender<VectorMap<Graph, Node, _Value> > Parent;
28.253 -
28.254 - //typedef typename Parent::Graph Graph;
28.255 - typedef typename Parent::Value Value;
28.256 -
28.257 - NodeMap(const Graph& g)
28.258 - : Parent(g) {}
28.259 - NodeMap(const Graph& g, const Value& v)
28.260 - : Parent(g, v) {}
28.261 -
28.262 - };
28.263 -
28.264 - template <typename _Value>
28.265 - class EdgeMap
28.266 - : public IterableMapExtender<VectorMap<Graph, Edge, _Value> > {
28.267 - public:
28.268 - typedef VectorMappableGraphExtender<_Base> Graph;
28.269 -
28.270 - typedef typename Graph::Edge Edge;
28.271 -
28.272 - typedef IterableMapExtender<VectorMap<Graph, Edge, _Value> > Parent;
28.273 -
28.274 - //typedef typename Parent::Graph Graph;
28.275 - typedef typename Parent::Value Value;
28.276 -
28.277 - EdgeMap(const Graph& g)
28.278 - : Parent(g) {}
28.279 - EdgeMap(const Graph& g, const Value& v)
28.280 - : Parent(g, v) {}
28.281 -
28.282 - };
28.283 -
28.284 - };
28.285 -
28.286 - /// @}
28.287 -
28.288 -}
28.289 -
28.290 -#endif
29.1 --- a/src/test/undir_graph_test.cc Tue Apr 05 09:49:01 2005 +0000
29.2 +++ b/src/test/undir_graph_test.cc Tue Apr 05 12:30:46 2005 +0000
29.3 @@ -1,6 +1,6 @@
29.4 // -*- C++ -*-
29.5
29.6 -#include <lemon/undir_graph_extender.h>
29.7 +#include <lemon/bits/undir_graph_extender.h>
29.8 #include <lemon/concept/undir_graph.h>
29.9 #include <lemon/list_graph.h>
29.10 #include <lemon/smart_graph.h>