1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concept_check.h Fri Jan 04 21:45:55 2008 +0100
1.3 @@ -0,0 +1,105 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2007
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +// This file contains a modified version of the concept checking
1.23 +// utility from BOOST.
1.24 +// See the appropriate copyright notice below.
1.25 +
1.26 +// (C) Copyright Jeremy Siek 2000.
1.27 +// Distributed under the Boost Software License, Version 1.0. (See
1.28 +// accompanying file LICENSE_1_0.txt or copy at
1.29 +// http://www.boost.org/LICENSE_1_0.txt)
1.30 +//
1.31 +// Revision History:
1.32 +// 05 May 2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
1.33 +// 02 April 2001: Removed limits header altogether. (Jeremy Siek)
1.34 +// 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
1.35 +//
1.36 +
1.37 +// See http://www.boost.org/libs/concept_check for documentation.
1.38 +
1.39 +#ifndef LEMON_CONCEPT_CHECKS_H
1.40 +#define LEMON_CONCEPT_CHECKS_H
1.41 +
1.42 +namespace lemon {
1.43 +
1.44 + /*
1.45 + "inline" is used for ignore_unused_variable_warning()
1.46 + and function_requires() to make sure there is no
1.47 + overtarget with g++.
1.48 + */
1.49 +
1.50 + template <class T> inline void ignore_unused_variable_warning(const T&) { }
1.51 +
1.52 + template <class Concept>
1.53 + inline void function_requires()
1.54 + {
1.55 +#if !defined(NDEBUG)
1.56 + void (Concept::*x)() = & Concept::constraints;
1.57 + ignore_unused_variable_warning(x);
1.58 +#endif
1.59 + }
1.60 +
1.61 + template <typename Concept, typename Type>
1.62 + inline void checkConcept() {
1.63 +#if !defined(NDEBUG)
1.64 + typedef typename Concept::template Constraints<Type> ConceptCheck;
1.65 + void (ConceptCheck::*x)() = & ConceptCheck::constraints;
1.66 + ignore_unused_variable_warning(x);
1.67 +#endif
1.68 + }
1.69 +
1.70 +#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
1.71 + typedef void (ns::concept <type_var>::* func##type_var##concept)(); \
1.72 + template <func##type_var##concept Tp1_> \
1.73 + struct concept_checking_##type_var##concept { }; \
1.74 + typedef concept_checking_##type_var##concept< \
1.75 + BOOST_FPTR ns::concept<type_var>::constraints> \
1.76 + concept_checking_typedef_##type_var##concept
1.77 +
1.78 +#define BOOST_CLASS_REQUIRE2(type_var1, type_var2, ns, concept) \
1.79 + typedef void (ns::concept <type_var1,type_var2>::* \
1.80 + func##type_var1##type_var2##concept)(); \
1.81 + template <func##type_var1##type_var2##concept Tp1_> \
1.82 + struct concept_checking_##type_var1##type_var2##concept { }; \
1.83 + typedef concept_checking_##type_var1##type_var2##concept< \
1.84 + BOOST_FPTR ns::concept<type_var1,type_var2>::constraints> \
1.85 + concept_checking_typedef_##type_var1##type_var2##concept
1.86 +
1.87 +#define BOOST_CLASS_REQUIRE3(tv1, tv2, tv3, ns, concept) \
1.88 + typedef void (ns::concept <tv1,tv2,tv3>::* \
1.89 + func##tv1##tv2##tv3##concept)(); \
1.90 + template <func##tv1##tv2##tv3##concept Tp1_> \
1.91 + struct concept_checking_##tv1##tv2##tv3##concept { }; \
1.92 + typedef concept_checking_##tv1##tv2##tv3##concept< \
1.93 + BOOST_FPTR ns::concept<tv1,tv2,tv3>::constraints> \
1.94 + concept_checking_typedef_##tv1##tv2##tv3##concept
1.95 +
1.96 +#define BOOST_CLASS_REQUIRE4(tv1, tv2, tv3, tv4, ns, concept) \
1.97 + typedef void (ns::concept <tv1,tv2,tv3,tv4>::* \
1.98 + func##tv1##tv2##tv3##tv4##concept)(); \
1.99 + template <func##tv1##tv2##tv3##tv4##concept Tp1_> \
1.100 + struct concept_checking_##tv1##tv2##tv3##tv4##concept { }; \
1.101 + typedef concept_checking_##tv1##tv2##tv3##tv4##concept< \
1.102 + BOOST_FPTR ns::concept<tv1,tv2,tv3,tv4>::constraints> \
1.103 + concept_checking_typedef_##tv1##tv2##tv3##tv4##concept
1.104 +
1.105 +
1.106 +} // namespace lemon
1.107 +
1.108 +#endif // LEMON_CONCEPT_CHECKS_H
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/concepts/maps.h Fri Jan 04 21:45:55 2008 +0100
2.3 @@ -0,0 +1,207 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2007
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_CONCEPT_MAPS_H
2.23 +#define LEMON_CONCEPT_MAPS_H
2.24 +
2.25 +#include <lemon/bits/utility.h>
2.26 +#include <lemon/concept_check.h>
2.27 +
2.28 +///\ingroup concept
2.29 +///\file
2.30 +///\brief Map concepts checking classes for testing and documenting.
2.31 +
2.32 +namespace lemon {
2.33 +
2.34 + namespace concepts {
2.35 +
2.36 + /// \addtogroup concept
2.37 + /// @{
2.38 +
2.39 + /// Readable map concept
2.40 +
2.41 + /// Readable map concept.
2.42 + ///
2.43 + template<typename K, typename T>
2.44 + class ReadMap
2.45 + {
2.46 + public:
2.47 + /// Map's key type.
2.48 + typedef K Key;
2.49 + /// Map's value type. (The type of objects associated with the keys).
2.50 + typedef T Value;
2.51 +
2.52 + /// Returns the value associated with a key.
2.53 +
2.54 + /// \bug Value shouldn't need to be default constructible.
2.55 + ///
2.56 + Value operator[](const Key &) const {return Value();}
2.57 +
2.58 + template<typename _ReadMap>
2.59 + struct Constraints {
2.60 +
2.61 + void constraints() {
2.62 + Value val = m[key];
2.63 + val = m[key];
2.64 + typename _ReadMap::Value own_val = m[own_key];
2.65 + own_val = m[own_key];
2.66 +
2.67 + ignore_unused_variable_warning(val);
2.68 + ignore_unused_variable_warning(own_val);
2.69 + ignore_unused_variable_warning(key);
2.70 + }
2.71 + Key& key;
2.72 + typename _ReadMap::Key& own_key;
2.73 + _ReadMap& m;
2.74 + };
2.75 +
2.76 + };
2.77 +
2.78 +
2.79 + /// Writable map concept
2.80 +
2.81 + /// Writable map concept.
2.82 + ///
2.83 + template<typename K, typename T>
2.84 + class WriteMap
2.85 + {
2.86 + public:
2.87 + /// Map's key type.
2.88 + typedef K Key;
2.89 + /// Map's value type. (The type of objects associated with the keys).
2.90 + typedef T Value;
2.91 +
2.92 + /// Sets the value associated with a key.
2.93 + void set(const Key &,const Value &) {}
2.94 +
2.95 + ///Default constructor
2.96 + WriteMap() {}
2.97 +
2.98 + template <typename _WriteMap>
2.99 + struct Constraints {
2.100 + void constraints() {
2.101 + // No constraints for constructor.
2.102 + m.set(key, val);
2.103 + m.set(own_key, own_val);
2.104 + ignore_unused_variable_warning(key);
2.105 + ignore_unused_variable_warning(val);
2.106 + ignore_unused_variable_warning(own_key);
2.107 + ignore_unused_variable_warning(own_val);
2.108 + }
2.109 +
2.110 + Value& val;
2.111 + typename _WriteMap::Value own_val;
2.112 + Key& key;
2.113 + typename _WriteMap::Key& own_key;
2.114 + _WriteMap& m;
2.115 +
2.116 + };
2.117 + };
2.118 +
2.119 + /// Read/Writable map concept
2.120 +
2.121 + /// Read/writable map concept.
2.122 + ///
2.123 + template<typename K, typename T>
2.124 + class ReadWriteMap : public ReadMap<K,T>,
2.125 + public WriteMap<K,T>
2.126 + {
2.127 + public:
2.128 + /// Map's key type.
2.129 + typedef K Key;
2.130 + /// Map's value type. (The type of objects associated with the keys).
2.131 + typedef T Value;
2.132 +
2.133 + /// Returns the value associated with a key.
2.134 + Value operator[](const Key &) const {return Value();}
2.135 + /// Sets the value associated with a key.
2.136 + void set(const Key & ,const Value &) {}
2.137 +
2.138 + template<typename _ReadWriteMap>
2.139 + struct Constraints {
2.140 + void constraints() {
2.141 + checkConcept<ReadMap<K, T>, _ReadWriteMap >();
2.142 + checkConcept<WriteMap<K, T>, _ReadWriteMap >();
2.143 + }
2.144 + };
2.145 + };
2.146 +
2.147 +
2.148 + /// Dereferable map concept
2.149 +
2.150 + /// Dereferable map concept.
2.151 + ///
2.152 + template<typename K, typename T, typename R, typename CR>
2.153 + class ReferenceMap : public ReadWriteMap<K,T>
2.154 + {
2.155 + public:
2.156 + /// Tag for reference maps.
2.157 + typedef True ReferenceMapTag;
2.158 + /// Map's key type.
2.159 + typedef K Key;
2.160 + /// Map's value type. (The type of objects associated with the keys).
2.161 + typedef T Value;
2.162 + /// Map's reference type.
2.163 + typedef R Reference;
2.164 + /// Map's const reference type.
2.165 + typedef CR ConstReference;
2.166 +
2.167 + protected:
2.168 + Value tmp;
2.169 + public:
2.170 +
2.171 + ///Returns a reference to the value associated to a key.
2.172 + Reference operator[](const Key &) { return tmp; }
2.173 + ///Returns a const reference to the value associated to a key.
2.174 + ConstReference operator[](const Key &) const { return tmp; }
2.175 + /// Sets the value associated with a key.
2.176 + void set(const Key &k,const Value &t) { operator[](k)=t; }
2.177 +
2.178 + /// \todo Rethink this concept.
2.179 + template<typename _ReferenceMap>
2.180 + struct ReferenceMapConcept {
2.181 +
2.182 + void constraints() {
2.183 + checkConcept<ReadWriteMap, _ReferenceMap >();
2.184 + m[key] = val;
2.185 + val = m[key];
2.186 + m[key] = ref;
2.187 + ref = m[key];
2.188 + m[own_key] = own_val;
2.189 + own_val = m[own_key];
2.190 + m[own_key] = own_ref;
2.191 + own_ref = m[own_key];
2.192 + }
2.193 +
2.194 + typename _ReferenceMap::Key& own_key;
2.195 + typename _ReferenceMap::Value& own_val;
2.196 + typename _ReferenceMap::Reference& own_ref;
2.197 + Key& key;
2.198 + Value& val;
2.199 + Reference& ref;
2.200 + _ReferenceMap& m;
2.201 + };
2.202 + };
2.203 +
2.204 + // @}
2.205 +
2.206 + } //namespace concepts
2.207 +
2.208 +} //namespace lemon
2.209 +
2.210 +#endif // LEMON_CONCEPT_MAPS_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/maps.h Fri Jan 04 21:45:55 2008 +0100
3.3 @@ -0,0 +1,1568 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2007
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#ifndef LEMON_MAPS_H
3.23 +#define LEMON_MAPS_H
3.24 +
3.25 +#include <iterator>
3.26 +#include <functional>
3.27 +#include <vector>
3.28 +
3.29 +#include <lemon/bits/utility.h>
3.30 +// #include <lemon/bits/traits.h>
3.31 +
3.32 +///\file
3.33 +///\ingroup maps
3.34 +///\brief Miscellaneous property maps
3.35 +///
3.36 +#include <map>
3.37 +
3.38 +namespace lemon {
3.39 +
3.40 + /// \addtogroup maps
3.41 + /// @{
3.42 +
3.43 + /// Base class of maps.
3.44 +
3.45 + /// Base class of maps.
3.46 + /// It provides the necessary <tt>typedef</tt>s required by the map concept.
3.47 + template<typename K, typename T>
3.48 + class MapBase {
3.49 + public:
3.50 + ///\e
3.51 + typedef K Key;
3.52 + ///\e
3.53 + typedef T Value;
3.54 + };
3.55 +
3.56 + /// Null map. (a.k.a. DoNothingMap)
3.57 +
3.58 + /// This map can be used if you have to provide a map only for
3.59 + /// its type definitions, or if you have to provide a writable map,
3.60 + /// but data written to it is not required (i.e. it will be sent to
3.61 + /// <tt>/dev/null</tt>).
3.62 + template<typename K, typename T>
3.63 + class NullMap : public MapBase<K, T> {
3.64 + public:
3.65 + typedef MapBase<K, T> Parent;
3.66 + typedef typename Parent::Key Key;
3.67 + typedef typename Parent::Value Value;
3.68 +
3.69 + /// Gives back a default constructed element.
3.70 + T operator[](const K&) const { return T(); }
3.71 + /// Absorbs the value.
3.72 + void set(const K&, const T&) {}
3.73 + };
3.74 +
3.75 + ///Returns a \c NullMap class
3.76 +
3.77 + ///This function just returns a \c NullMap class.
3.78 + ///\relates NullMap
3.79 + template <typename K, typename V>
3.80 + NullMap<K, V> nullMap() {
3.81 + return NullMap<K, V>();
3.82 + }
3.83 +
3.84 +
3.85 + /// Constant map.
3.86 +
3.87 + /// This is a readable map which assigns a specified value to each key.
3.88 + /// In other aspects it is equivalent to the \c NullMap.
3.89 + template<typename K, typename T>
3.90 + class ConstMap : public MapBase<K, T> {
3.91 + private:
3.92 + T v;
3.93 + public:
3.94 +
3.95 + typedef MapBase<K, T> Parent;
3.96 + typedef typename Parent::Key Key;
3.97 + typedef typename Parent::Value Value;
3.98 +
3.99 + /// Default constructor
3.100 +
3.101 + /// Default constructor.
3.102 + /// The value of the map will be uninitialized.
3.103 + /// (More exactly it will be default constructed.)
3.104 + ConstMap() {}
3.105 +
3.106 + /// Constructor with specified initial value
3.107 +
3.108 + /// Constructor with specified initial value.
3.109 + /// \param _v is the initial value of the map.
3.110 + ConstMap(const T &_v) : v(_v) {}
3.111 +
3.112 + ///\e
3.113 + T operator[](const K&) const { return v; }
3.114 +
3.115 + ///\e
3.116 + void setAll(const T &t) {
3.117 + v = t;
3.118 + }
3.119 +
3.120 + template<typename T1>
3.121 + struct rebind {
3.122 + typedef ConstMap<K, T1> other;
3.123 + };
3.124 +
3.125 + template<typename T1>
3.126 + ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
3.127 + };
3.128 +
3.129 + ///Returns a \c ConstMap class
3.130 +
3.131 + ///This function just returns a \c ConstMap class.
3.132 + ///\relates ConstMap
3.133 + template<typename K, typename V>
3.134 + inline ConstMap<K, V> constMap(const V &v) {
3.135 + return ConstMap<K, V>(v);
3.136 + }
3.137 +
3.138 +
3.139 + template<typename T, T v>
3.140 + struct Const { };
3.141 +
3.142 + /// Constant map with inlined constant value.
3.143 +
3.144 + /// This is a readable map which assigns a specified value to each key.
3.145 + /// In other aspects it is equivalent to the \c NullMap.
3.146 + template<typename K, typename V, V v>
3.147 + class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
3.148 + public:
3.149 + typedef MapBase<K, V> Parent;
3.150 + typedef typename Parent::Key Key;
3.151 + typedef typename Parent::Value Value;
3.152 +
3.153 + ConstMap() { }
3.154 + ///\e
3.155 + V operator[](const K&) const { return v; }
3.156 + ///\e
3.157 + void set(const K&, const V&) { }
3.158 + };
3.159 +
3.160 + ///Returns a \c ConstMap class
3.161 +
3.162 + ///This function just returns a \c ConstMap class with inlined value.
3.163 + ///\relates ConstMap
3.164 + template<typename K, typename V, V v>
3.165 + inline ConstMap<K, Const<V, v> > constMap() {
3.166 + return ConstMap<K, Const<V, v> >();
3.167 + }
3.168 +
3.169 + ///Map based on std::map
3.170 +
3.171 + ///This is essentially a wrapper for \c std::map with addition that
3.172 + ///you can specify a default value different from \c Value().
3.173 + template <typename K, typename T, typename Compare = std::less<K> >
3.174 + class StdMap {
3.175 + template <typename K1, typename T1, typename C1>
3.176 + friend class StdMap;
3.177 + public:
3.178 +
3.179 + typedef True ReferenceMapTag;
3.180 + ///\e
3.181 + typedef K Key;
3.182 + ///\e
3.183 + typedef T Value;
3.184 + ///\e
3.185 + typedef T& Reference;
3.186 + ///\e
3.187 + typedef const T& ConstReference;
3.188 +
3.189 + private:
3.190 +
3.191 + typedef std::map<K, T, Compare> Map;
3.192 + Value _value;
3.193 + Map _map;
3.194 +
3.195 + public:
3.196 +
3.197 + /// Constructor with specified default value
3.198 + StdMap(const T& value = T()) : _value(value) {}
3.199 + /// \brief Constructs the map from an appropriate std::map, and explicitly
3.200 + /// specifies a default value.
3.201 + template <typename T1, typename Comp1>
3.202 + StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
3.203 + : _map(map.begin(), map.end()), _value(value) {}
3.204 +
3.205 + /// \brief Constructs a map from an other StdMap.
3.206 + template<typename T1, typename Comp1>
3.207 + StdMap(const StdMap<Key, T1, Comp1> &c)
3.208 + : _map(c._map.begin(), c._map.end()), _value(c._value) {}
3.209 +
3.210 + private:
3.211 +
3.212 + StdMap& operator=(const StdMap&);
3.213 +
3.214 + public:
3.215 +
3.216 + ///\e
3.217 + Reference operator[](const Key &k) {
3.218 + typename Map::iterator it = _map.lower_bound(k);
3.219 + if (it != _map.end() && !_map.key_comp()(k, it->first))
3.220 + return it->second;
3.221 + else
3.222 + return _map.insert(it, std::make_pair(k, _value))->second;
3.223 + }
3.224 +
3.225 + /// \e
3.226 + ConstReference operator[](const Key &k) const {
3.227 + typename Map::const_iterator it = _map.find(k);
3.228 + if (it != _map.end())
3.229 + return it->second;
3.230 + else
3.231 + return _value;
3.232 + }
3.233 +
3.234 + /// \e
3.235 + void set(const Key &k, const T &t) {
3.236 + typename Map::iterator it = _map.lower_bound(k);
3.237 + if (it != _map.end() && !_map.key_comp()(k, it->first))
3.238 + it->second = t;
3.239 + else
3.240 + _map.insert(it, std::make_pair(k, t));
3.241 + }
3.242 +
3.243 + /// \e
3.244 + void setAll(const T &t) {
3.245 + _value = t;
3.246 + _map.clear();
3.247 + }
3.248 +
3.249 + template <typename T1, typename C1 = std::less<T1> >
3.250 + struct rebind {
3.251 + typedef StdMap<Key, T1, C1> other;
3.252 + };
3.253 + };
3.254 +
3.255 + /// \brief Map for storing values for the range \c [0..size-1] range keys
3.256 + ///
3.257 + /// The current map has the \c [0..size-1] keyset and the values
3.258 + /// are stored in a \c std::vector<T> container. It can be used with
3.259 + /// some data structures, for example \c UnionFind, \c BinHeap, when
3.260 + /// the used items are small integer numbers.
3.261 + ///
3.262 + /// \todo Revise its name
3.263 + template <typename T>
3.264 + class IntegerMap {
3.265 +
3.266 + template <typename T1>
3.267 + friend class IntegerMap;
3.268 +
3.269 + public:
3.270 +
3.271 + typedef True ReferenceMapTag;
3.272 + ///\e
3.273 + typedef int Key;
3.274 + ///\e
3.275 + typedef T Value;
3.276 + ///\e
3.277 + typedef T& Reference;
3.278 + ///\e
3.279 + typedef const T& ConstReference;
3.280 +
3.281 + private:
3.282 +
3.283 + typedef std::vector<T> Vector;
3.284 + Vector _vector;
3.285 +
3.286 + public:
3.287 +
3.288 + /// Constructor with specified default value
3.289 + IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
3.290 +
3.291 + /// \brief Constructs the map from an appropriate std::vector.
3.292 + template <typename T1>
3.293 + IntegerMap(const std::vector<T1>& vector)
3.294 + : _vector(vector.begin(), vector.end()) {}
3.295 +
3.296 + /// \brief Constructs a map from an other IntegerMap.
3.297 + template <typename T1>
3.298 + IntegerMap(const IntegerMap<T1> &c)
3.299 + : _vector(c._vector.begin(), c._vector.end()) {}
3.300 +
3.301 + /// \brief Resize the container
3.302 + void resize(int size, const T& value = T()) {
3.303 + _vector.resize(size, value);
3.304 + }
3.305 +
3.306 + private:
3.307 +
3.308 + IntegerMap& operator=(const IntegerMap&);
3.309 +
3.310 + public:
3.311 +
3.312 + ///\e
3.313 + Reference operator[](Key k) {
3.314 + return _vector[k];
3.315 + }
3.316 +
3.317 + /// \e
3.318 + ConstReference operator[](Key k) const {
3.319 + return _vector[k];
3.320 + }
3.321 +
3.322 + /// \e
3.323 + void set(const Key &k, const T& t) {
3.324 + _vector[k] = t;
3.325 + }
3.326 +
3.327 + };
3.328 +
3.329 + /// @}
3.330 +
3.331 + /// \addtogroup map_adaptors
3.332 + /// @{
3.333 +
3.334 + /// \brief Identity map.
3.335 + ///
3.336 + /// This map gives back the given key as value without any
3.337 + /// modification.
3.338 + template <typename T>
3.339 + class IdentityMap : public MapBase<T, T> {
3.340 + public:
3.341 + typedef MapBase<T, T> Parent;
3.342 + typedef typename Parent::Key Key;
3.343 + typedef typename Parent::Value Value;
3.344 +
3.345 + /// \e
3.346 + const T& operator[](const T& t) const {
3.347 + return t;
3.348 + }
3.349 + };
3.350 +
3.351 + ///Returns an \c IdentityMap class
3.352 +
3.353 + ///This function just returns an \c IdentityMap class.
3.354 + ///\relates IdentityMap
3.355 + template<typename T>
3.356 + inline IdentityMap<T> identityMap() {
3.357 + return IdentityMap<T>();
3.358 + }
3.359 +
3.360 +
3.361 + ///\brief Convert the \c Value of a map to another type using
3.362 + ///the default conversion.
3.363 + ///
3.364 + ///This \c concepts::ReadMap "read only map"
3.365 + ///converts the \c Value of a map to type \c T.
3.366 + ///Its \c Key is inherited from \c M.
3.367 + template <typename M, typename T>
3.368 + class ConvertMap : public MapBase<typename M::Key, T> {
3.369 + const M& m;
3.370 + public:
3.371 + typedef MapBase<typename M::Key, T> Parent;
3.372 + typedef typename Parent::Key Key;
3.373 + typedef typename Parent::Value Value;
3.374 +
3.375 + ///Constructor
3.376 +
3.377 + ///Constructor.
3.378 + ///\param _m is the underlying map.
3.379 + ConvertMap(const M &_m) : m(_m) {};
3.380 +
3.381 + /// \brief The subscript operator.
3.382 + ///
3.383 + /// The subscript operator.
3.384 + Value operator[](const Key& k) const {return m[k];}
3.385 + };
3.386 +
3.387 + ///Returns a \c ConvertMap class
3.388 +
3.389 + ///This function just returns a \c ConvertMap class.
3.390 + ///\relates ConvertMap
3.391 + template<typename T, typename M>
3.392 + inline ConvertMap<M, T> convertMap(const M &m) {
3.393 + return ConvertMap<M, T>(m);
3.394 + }
3.395 +
3.396 + ///Simple wrapping of a map
3.397 +
3.398 + ///This \c concepts::ReadMap "read only map" returns the simple
3.399 + ///wrapping of the given map. Sometimes the reference maps cannot be
3.400 + ///combined with simple read maps. This map adaptor wraps the given
3.401 + ///map to simple read map.
3.402 + ///
3.403 + ///\sa SimpleWriteMap
3.404 + ///
3.405 + /// \todo Revise the misleading name
3.406 + template<typename M>
3.407 + class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
3.408 + const M& m;
3.409 +
3.410 + public:
3.411 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.412 + typedef typename Parent::Key Key;
3.413 + typedef typename Parent::Value Value;
3.414 +
3.415 + ///Constructor
3.416 + SimpleMap(const M &_m) : m(_m) {};
3.417 + ///\e
3.418 + Value operator[](Key k) const {return m[k];}
3.419 + };
3.420 +
3.421 + ///Simple writable wrapping of the map
3.422 +
3.423 + ///This \c concepts::WriteMap "write map" returns the simple
3.424 + ///wrapping of the given map. Sometimes the reference maps cannot be
3.425 + ///combined with simple read-write maps. This map adaptor wraps the
3.426 + ///given map to simple read-write map.
3.427 + ///
3.428 + ///\sa SimpleMap
3.429 + ///
3.430 + /// \todo Revise the misleading name
3.431 + template<typename M>
3.432 + class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
3.433 + M& m;
3.434 +
3.435 + public:
3.436 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.437 + typedef typename Parent::Key Key;
3.438 + typedef typename Parent::Value Value;
3.439 +
3.440 + ///Constructor
3.441 + SimpleWriteMap(M &_m) : m(_m) {};
3.442 + ///\e
3.443 + Value operator[](Key k) const {return m[k];}
3.444 + ///\e
3.445 + void set(Key k, const Value& c) { m.set(k, c); }
3.446 + };
3.447 +
3.448 + ///Sum of two maps
3.449 +
3.450 + ///This \c concepts::ReadMap "read only map" returns the sum of the two
3.451 + ///given maps.
3.452 + ///Its \c Key and \c Value are inherited from \c M1.
3.453 + ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
3.454 + template<typename M1, typename M2>
3.455 + class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
3.456 + const M1& m1;
3.457 + const M2& m2;
3.458 +
3.459 + public:
3.460 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
3.461 + typedef typename Parent::Key Key;
3.462 + typedef typename Parent::Value Value;
3.463 +
3.464 + ///Constructor
3.465 + AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
3.466 + ///\e
3.467 + Value operator[](Key k) const {return m1[k]+m2[k];}
3.468 + };
3.469 +
3.470 + ///Returns an \c AddMap class
3.471 +
3.472 + ///This function just returns an \c AddMap class.
3.473 + ///\todo How to call these type of functions?
3.474 + ///
3.475 + ///\relates AddMap
3.476 + template<typename M1, typename M2>
3.477 + inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
3.478 + return AddMap<M1, M2>(m1,m2);
3.479 + }
3.480 +
3.481 + ///Shift a map with a constant.
3.482 +
3.483 + ///This \c concepts::ReadMap "read only map" returns the sum of the
3.484 + ///given map and a constant value.
3.485 + ///Its \c Key and \c Value are inherited from \c M.
3.486 + ///
3.487 + ///Actually,
3.488 + ///\code
3.489 + /// ShiftMap<X> sh(x,v);
3.490 + ///\endcode
3.491 + ///is equivalent to
3.492 + ///\code
3.493 + /// ConstMap<X::Key, X::Value> c_tmp(v);
3.494 + /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
3.495 + ///\endcode
3.496 + ///
3.497 + ///\sa ShiftWriteMap
3.498 + template<typename M, typename C = typename M::Value>
3.499 + class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
3.500 + const M& m;
3.501 + C v;
3.502 + public:
3.503 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.504 + typedef typename Parent::Key Key;
3.505 + typedef typename Parent::Value Value;
3.506 +
3.507 + ///Constructor
3.508 +
3.509 + ///Constructor.
3.510 + ///\param _m is the undelying map.
3.511 + ///\param _v is the shift value.
3.512 + ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
3.513 + ///\e
3.514 + Value operator[](Key k) const {return m[k] + v;}
3.515 + };
3.516 +
3.517 + ///Shift a map with a constant (ReadWrite version).
3.518 +
3.519 + ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
3.520 + ///given map and a constant value. It makes also possible to write the map.
3.521 + ///Its \c Key and \c Value are inherited from \c M.
3.522 + ///
3.523 + ///\sa ShiftMap
3.524 + template<typename M, typename C = typename M::Value>
3.525 + class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
3.526 + M& m;
3.527 + C v;
3.528 + public:
3.529 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.530 + typedef typename Parent::Key Key;
3.531 + typedef typename Parent::Value Value;
3.532 +
3.533 + ///Constructor
3.534 +
3.535 + ///Constructor.
3.536 + ///\param _m is the undelying map.
3.537 + ///\param _v is the shift value.
3.538 + ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
3.539 + /// \e
3.540 + Value operator[](Key k) const {return m[k] + v;}
3.541 + /// \e
3.542 + void set(Key k, const Value& c) { m.set(k, c - v); }
3.543 + };
3.544 +
3.545 + ///Returns a \c ShiftMap class
3.546 +
3.547 + ///This function just returns a \c ShiftMap class.
3.548 + ///\relates ShiftMap
3.549 + template<typename M, typename C>
3.550 + inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
3.551 + return ShiftMap<M, C>(m,v);
3.552 + }
3.553 +
3.554 + ///Returns a \c ShiftWriteMap class
3.555 +
3.556 + ///This function just returns a \c ShiftWriteMap class.
3.557 + ///\relates ShiftWriteMap
3.558 + template<typename M, typename C>
3.559 + inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
3.560 + return ShiftWriteMap<M, C>(m,v);
3.561 + }
3.562 +
3.563 + ///Difference of two maps
3.564 +
3.565 + ///This \c concepts::ReadMap "read only map" returns the difference
3.566 + ///of the values of the two given maps.
3.567 + ///Its \c Key and \c Value are inherited from \c M1.
3.568 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
3.569 + ///
3.570 + /// \todo Revise the misleading name
3.571 + template<typename M1, typename M2>
3.572 + class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
3.573 + const M1& m1;
3.574 + const M2& m2;
3.575 + public:
3.576 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
3.577 + typedef typename Parent::Key Key;
3.578 + typedef typename Parent::Value Value;
3.579 +
3.580 + ///Constructor
3.581 + SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
3.582 + /// \e
3.583 + Value operator[](Key k) const {return m1[k]-m2[k];}
3.584 + };
3.585 +
3.586 + ///Returns a \c SubMap class
3.587 +
3.588 + ///This function just returns a \c SubMap class.
3.589 + ///
3.590 + ///\relates SubMap
3.591 + template<typename M1, typename M2>
3.592 + inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
3.593 + return SubMap<M1, M2>(m1, m2);
3.594 + }
3.595 +
3.596 + ///Product of two maps
3.597 +
3.598 + ///This \c concepts::ReadMap "read only map" returns the product of the
3.599 + ///values of the two given maps.
3.600 + ///Its \c Key and \c Value are inherited from \c M1.
3.601 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
3.602 + template<typename M1, typename M2>
3.603 + class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
3.604 + const M1& m1;
3.605 + const M2& m2;
3.606 + public:
3.607 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
3.608 + typedef typename Parent::Key Key;
3.609 + typedef typename Parent::Value Value;
3.610 +
3.611 + ///Constructor
3.612 + MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
3.613 + /// \e
3.614 + Value operator[](Key k) const {return m1[k]*m2[k];}
3.615 + };
3.616 +
3.617 + ///Returns a \c MulMap class
3.618 +
3.619 + ///This function just returns a \c MulMap class.
3.620 + ///\relates MulMap
3.621 + template<typename M1, typename M2>
3.622 + inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
3.623 + return MulMap<M1, M2>(m1,m2);
3.624 + }
3.625 +
3.626 + ///Scales a map with a constant.
3.627 +
3.628 + ///This \c concepts::ReadMap "read only map" returns the value of the
3.629 + ///given map multiplied from the left side with a constant value.
3.630 + ///Its \c Key and \c Value are inherited from \c M.
3.631 + ///
3.632 + ///Actually,
3.633 + ///\code
3.634 + /// ScaleMap<X> sc(x,v);
3.635 + ///\endcode
3.636 + ///is equivalent to
3.637 + ///\code
3.638 + /// ConstMap<X::Key, X::Value> c_tmp(v);
3.639 + /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
3.640 + ///\endcode
3.641 + ///
3.642 + ///\sa ScaleWriteMap
3.643 + template<typename M, typename C = typename M::Value>
3.644 + class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
3.645 + const M& m;
3.646 + C v;
3.647 + public:
3.648 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.649 + typedef typename Parent::Key Key;
3.650 + typedef typename Parent::Value Value;
3.651 +
3.652 + ///Constructor
3.653 +
3.654 + ///Constructor.
3.655 + ///\param _m is the undelying map.
3.656 + ///\param _v is the scaling value.
3.657 + ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
3.658 + /// \e
3.659 + Value operator[](Key k) const {return v * m[k];}
3.660 + };
3.661 +
3.662 + ///Scales a map with a constant (ReadWrite version).
3.663 +
3.664 + ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
3.665 + ///given map multiplied from the left side with a constant value. It can
3.666 + ///also be used as write map if the \c / operator is defined between
3.667 + ///\c Value and \c C and the given multiplier is not zero.
3.668 + ///Its \c Key and \c Value are inherited from \c M.
3.669 + ///
3.670 + ///\sa ScaleMap
3.671 + template<typename M, typename C = typename M::Value>
3.672 + class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
3.673 + M& m;
3.674 + C v;
3.675 + public:
3.676 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.677 + typedef typename Parent::Key Key;
3.678 + typedef typename Parent::Value Value;
3.679 +
3.680 + ///Constructor
3.681 +
3.682 + ///Constructor.
3.683 + ///\param _m is the undelying map.
3.684 + ///\param _v is the scaling value.
3.685 + ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
3.686 + /// \e
3.687 + Value operator[](Key k) const {return v * m[k];}
3.688 + /// \e
3.689 + void set(Key k, const Value& c) { m.set(k, c / v);}
3.690 + };
3.691 +
3.692 + ///Returns a \c ScaleMap class
3.693 +
3.694 + ///This function just returns a \c ScaleMap class.
3.695 + ///\relates ScaleMap
3.696 + template<typename M, typename C>
3.697 + inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
3.698 + return ScaleMap<M, C>(m,v);
3.699 + }
3.700 +
3.701 + ///Returns a \c ScaleWriteMap class
3.702 +
3.703 + ///This function just returns a \c ScaleWriteMap class.
3.704 + ///\relates ScaleWriteMap
3.705 + template<typename M, typename C>
3.706 + inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
3.707 + return ScaleWriteMap<M, C>(m,v);
3.708 + }
3.709 +
3.710 + ///Quotient of two maps
3.711 +
3.712 + ///This \c concepts::ReadMap "read only map" returns the quotient of the
3.713 + ///values of the two given maps.
3.714 + ///Its \c Key and \c Value are inherited from \c M1.
3.715 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
3.716 + template<typename M1, typename M2>
3.717 + class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
3.718 + const M1& m1;
3.719 + const M2& m2;
3.720 + public:
3.721 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
3.722 + typedef typename Parent::Key Key;
3.723 + typedef typename Parent::Value Value;
3.724 +
3.725 + ///Constructor
3.726 + DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
3.727 + /// \e
3.728 + Value operator[](Key k) const {return m1[k]/m2[k];}
3.729 + };
3.730 +
3.731 + ///Returns a \c DivMap class
3.732 +
3.733 + ///This function just returns a \c DivMap class.
3.734 + ///\relates DivMap
3.735 + template<typename M1, typename M2>
3.736 + inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
3.737 + return DivMap<M1, M2>(m1,m2);
3.738 + }
3.739 +
3.740 + ///Composition of two maps
3.741 +
3.742 + ///This \c concepts::ReadMap "read only map" returns the composition of
3.743 + ///two given maps.
3.744 + ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
3.745 + ///then for
3.746 + ///\code
3.747 + /// ComposeMap<M1, M2> cm(m1,m2);
3.748 + ///\endcode
3.749 + /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
3.750 + ///
3.751 + ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
3.752 + ///\c M2::Value must be convertible to \c M1::Key.
3.753 + ///
3.754 + ///\sa CombineMap
3.755 + ///
3.756 + ///\todo Check the requirements.
3.757 + template <typename M1, typename M2>
3.758 + class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
3.759 + const M1& m1;
3.760 + const M2& m2;
3.761 + public:
3.762 + typedef MapBase<typename M2::Key, typename M1::Value> Parent;
3.763 + typedef typename Parent::Key Key;
3.764 + typedef typename Parent::Value Value;
3.765 +
3.766 + ///Constructor
3.767 + ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
3.768 +
3.769 + /// \e
3.770 +
3.771 +
3.772 + /// \todo Use the MapTraits once it is ported.
3.773 + ///
3.774 +
3.775 + //typename MapTraits<M1>::ConstReturnValue
3.776 + typename M1::Value
3.777 + operator[](Key k) const {return m1[m2[k]];}
3.778 + };
3.779 +
3.780 + ///Returns a \c ComposeMap class
3.781 +
3.782 + ///This function just returns a \c ComposeMap class.
3.783 + ///\relates ComposeMap
3.784 + template <typename M1, typename M2>
3.785 + inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
3.786 + return ComposeMap<M1, M2>(m1,m2);
3.787 + }
3.788 +
3.789 + ///Combine of two maps using an STL (binary) functor.
3.790 +
3.791 + ///Combine of two maps using an STL (binary) functor.
3.792 + ///
3.793 + ///This \c concepts::ReadMap "read only map" takes two maps and a
3.794 + ///binary functor and returns the composition of the two
3.795 + ///given maps unsing the functor.
3.796 + ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
3.797 + ///and \c f is of \c F, then for
3.798 + ///\code
3.799 + /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
3.800 + ///\endcode
3.801 + /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
3.802 + ///
3.803 + ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
3.804 + ///\c M2::Value and \c M1::Value must be convertible to the corresponding
3.805 + ///input parameter of \c F and the return type of \c F must be convertible
3.806 + ///to \c V.
3.807 + ///
3.808 + ///\sa ComposeMap
3.809 + ///
3.810 + ///\todo Check the requirements.
3.811 + template<typename M1, typename M2, typename F,
3.812 + typename V = typename F::result_type>
3.813 + class CombineMap : public MapBase<typename M1::Key, V> {
3.814 + const M1& m1;
3.815 + const M2& m2;
3.816 + F f;
3.817 + public:
3.818 + typedef MapBase<typename M1::Key, V> Parent;
3.819 + typedef typename Parent::Key Key;
3.820 + typedef typename Parent::Value Value;
3.821 +
3.822 + ///Constructor
3.823 + CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
3.824 + : m1(_m1), m2(_m2), f(_f) {};
3.825 + /// \e
3.826 + Value operator[](Key k) const {return f(m1[k],m2[k]);}
3.827 + };
3.828 +
3.829 + ///Returns a \c CombineMap class
3.830 +
3.831 + ///This function just returns a \c CombineMap class.
3.832 + ///
3.833 + ///For example if \c m1 and \c m2 are both \c double valued maps, then
3.834 + ///\code
3.835 + ///combineMap<double>(m1,m2,std::plus<double>())
3.836 + ///\endcode
3.837 + ///is equivalent to
3.838 + ///\code
3.839 + ///addMap(m1,m2)
3.840 + ///\endcode
3.841 + ///
3.842 + ///This function is specialized for adaptable binary function
3.843 + ///classes and C++ functions.
3.844 + ///
3.845 + ///\relates CombineMap
3.846 + template<typename M1, typename M2, typename F, typename V>
3.847 + inline CombineMap<M1, M2, F, V>
3.848 + combineMap(const M1& m1,const M2& m2, const F& f) {
3.849 + return CombineMap<M1, M2, F, V>(m1,m2,f);
3.850 + }
3.851 +
3.852 + template<typename M1, typename M2, typename F>
3.853 + inline CombineMap<M1, M2, F, typename F::result_type>
3.854 + combineMap(const M1& m1, const M2& m2, const F& f) {
3.855 + return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
3.856 + }
3.857 +
3.858 + template<typename M1, typename M2, typename K1, typename K2, typename V>
3.859 + inline CombineMap<M1, M2, V (*)(K1, K2), V>
3.860 + combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
3.861 + return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
3.862 + }
3.863 +
3.864 + ///Negative value of a map
3.865 +
3.866 + ///This \c concepts::ReadMap "read only map" returns the negative
3.867 + ///value of the value returned by the given map.
3.868 + ///Its \c Key and \c Value are inherited from \c M.
3.869 + ///The unary \c - operator must be defined for \c Value, of course.
3.870 + ///
3.871 + ///\sa NegWriteMap
3.872 + template<typename M>
3.873 + class NegMap : public MapBase<typename M::Key, typename M::Value> {
3.874 + const M& m;
3.875 + public:
3.876 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.877 + typedef typename Parent::Key Key;
3.878 + typedef typename Parent::Value Value;
3.879 +
3.880 + ///Constructor
3.881 + NegMap(const M &_m) : m(_m) {};
3.882 + /// \e
3.883 + Value operator[](Key k) const {return -m[k];}
3.884 + };
3.885 +
3.886 + ///Negative value of a map (ReadWrite version)
3.887 +
3.888 + ///This \c concepts::ReadWriteMap "read-write map" returns the negative
3.889 + ///value of the value returned by the given map.
3.890 + ///Its \c Key and \c Value are inherited from \c M.
3.891 + ///The unary \c - operator must be defined for \c Value, of course.
3.892 + ///
3.893 + /// \sa NegMap
3.894 + template<typename M>
3.895 + class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
3.896 + M& m;
3.897 + public:
3.898 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.899 + typedef typename Parent::Key Key;
3.900 + typedef typename Parent::Value Value;
3.901 +
3.902 + ///Constructor
3.903 + NegWriteMap(M &_m) : m(_m) {};
3.904 + /// \e
3.905 + Value operator[](Key k) const {return -m[k];}
3.906 + /// \e
3.907 + void set(Key k, const Value& v) { m.set(k, -v); }
3.908 + };
3.909 +
3.910 + ///Returns a \c NegMap class
3.911 +
3.912 + ///This function just returns a \c NegMap class.
3.913 + ///\relates NegMap
3.914 + template <typename M>
3.915 + inline NegMap<M> negMap(const M &m) {
3.916 + return NegMap<M>(m);
3.917 + }
3.918 +
3.919 + ///Returns a \c NegWriteMap class
3.920 +
3.921 + ///This function just returns a \c NegWriteMap class.
3.922 + ///\relates NegWriteMap
3.923 + template <typename M>
3.924 + inline NegWriteMap<M> negMap(M &m) {
3.925 + return NegWriteMap<M>(m);
3.926 + }
3.927 +
3.928 + ///Absolute value of a map
3.929 +
3.930 + ///This \c concepts::ReadMap "read only map" returns the absolute value
3.931 + ///of the value returned by the given map.
3.932 + ///Its \c Key and \c Value are inherited from \c M.
3.933 + ///\c Value must be comparable to \c 0 and the unary \c -
3.934 + ///operator must be defined for it, of course.
3.935 + template<typename M>
3.936 + class AbsMap : public MapBase<typename M::Key, typename M::Value> {
3.937 + const M& m;
3.938 + public:
3.939 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.940 + typedef typename Parent::Key Key;
3.941 + typedef typename Parent::Value Value;
3.942 +
3.943 + ///Constructor
3.944 + AbsMap(const M &_m) : m(_m) {};
3.945 + /// \e
3.946 + Value operator[](Key k) const {
3.947 + Value tmp = m[k];
3.948 + return tmp >= 0 ? tmp : -tmp;
3.949 + }
3.950 +
3.951 + };
3.952 +
3.953 + ///Returns an \c AbsMap class
3.954 +
3.955 + ///This function just returns an \c AbsMap class.
3.956 + ///\relates AbsMap
3.957 + template<typename M>
3.958 + inline AbsMap<M> absMap(const M &m) {
3.959 + return AbsMap<M>(m);
3.960 + }
3.961 +
3.962 + ///Converts an STL style functor to a map
3.963 +
3.964 + ///This \c concepts::ReadMap "read only map" returns the value
3.965 + ///of a given functor.
3.966 + ///
3.967 + ///Template parameters \c K and \c V will become its
3.968 + ///\c Key and \c Value. They must be given explicitly
3.969 + ///because a functor does not provide such typedefs.
3.970 + ///
3.971 + ///Parameter \c F is the type of the used functor.
3.972 + ///
3.973 + ///\sa MapFunctor
3.974 + template<typename F,
3.975 + typename K = typename F::argument_type,
3.976 + typename V = typename F::result_type>
3.977 + class FunctorMap : public MapBase<K, V> {
3.978 + F f;
3.979 + public:
3.980 + typedef MapBase<K, V> Parent;
3.981 + typedef typename Parent::Key Key;
3.982 + typedef typename Parent::Value Value;
3.983 +
3.984 + ///Constructor
3.985 + FunctorMap(const F &_f = F()) : f(_f) {}
3.986 + /// \e
3.987 + Value operator[](Key k) const { return f(k);}
3.988 + };
3.989 +
3.990 + ///Returns a \c FunctorMap class
3.991 +
3.992 + ///This function just returns a \c FunctorMap class.
3.993 + ///
3.994 + ///It is specialized for adaptable function classes and
3.995 + ///C++ functions.
3.996 + ///\relates FunctorMap
3.997 + template<typename K, typename V, typename F> inline
3.998 + FunctorMap<F, K, V> functorMap(const F &f) {
3.999 + return FunctorMap<F, K, V>(f);
3.1000 + }
3.1001 +
3.1002 + template <typename F> inline
3.1003 + FunctorMap<F, typename F::argument_type, typename F::result_type>
3.1004 + functorMap(const F &f) {
3.1005 + return FunctorMap<F, typename F::argument_type,
3.1006 + typename F::result_type>(f);
3.1007 + }
3.1008 +
3.1009 + template <typename K, typename V> inline
3.1010 + FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
3.1011 + return FunctorMap<V (*)(K), K, V>(f);
3.1012 + }
3.1013 +
3.1014 +
3.1015 + ///Converts a map to an STL style (unary) functor
3.1016 +
3.1017 + ///This class Converts a map to an STL style (unary) functor.
3.1018 + ///that is it provides an <tt>operator()</tt> to read its values.
3.1019 + ///
3.1020 + ///For the sake of convenience it also works as
3.1021 + ///a ususal \c concepts::ReadMap "readable map",
3.1022 + ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
3.1023 + ///
3.1024 + ///\sa FunctorMap
3.1025 + template <typename M>
3.1026 + class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
3.1027 + const M& m;
3.1028 + public:
3.1029 + typedef MapBase<typename M::Key, typename M::Value> Parent;
3.1030 + typedef typename Parent::Key Key;
3.1031 + typedef typename Parent::Value Value;
3.1032 +
3.1033 + typedef typename M::Key argument_type;
3.1034 + typedef typename M::Value result_type;
3.1035 +
3.1036 + ///Constructor
3.1037 + MapFunctor(const M &_m) : m(_m) {};
3.1038 + ///\e
3.1039 + Value operator()(Key k) const {return m[k];}
3.1040 + ///\e
3.1041 + Value operator[](Key k) const {return m[k];}
3.1042 + };
3.1043 +
3.1044 + ///Returns a \c MapFunctor class
3.1045 +
3.1046 + ///This function just returns a \c MapFunctor class.
3.1047 + ///\relates MapFunctor
3.1048 + template<typename M>
3.1049 + inline MapFunctor<M> mapFunctor(const M &m) {
3.1050 + return MapFunctor<M>(m);
3.1051 + }
3.1052 +
3.1053 + ///Applies all map setting operations to two maps
3.1054 +
3.1055 + ///This map has two \c concepts::ReadMap "readable map"
3.1056 + ///parameters and each read request will be passed just to the
3.1057 + ///first map. This class is the just readable map type of the ForkWriteMap.
3.1058 + ///
3.1059 + ///The \c Key and \c Value are inherited from \c M1.
3.1060 + ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
3.1061 + ///
3.1062 + ///\sa ForkWriteMap
3.1063 + ///
3.1064 + /// \todo Why is it needed?
3.1065 + template<typename M1, typename M2>
3.1066 + class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
3.1067 + const M1& m1;
3.1068 + const M2& m2;
3.1069 + public:
3.1070 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
3.1071 + typedef typename Parent::Key Key;
3.1072 + typedef typename Parent::Value Value;
3.1073 +
3.1074 + ///Constructor
3.1075 + ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
3.1076 + /// \e
3.1077 + Value operator[](Key k) const {return m1[k];}
3.1078 + };
3.1079 +
3.1080 +
3.1081 + ///Applies all map setting operations to two maps
3.1082 +
3.1083 + ///This map has two \c concepts::WriteMap "writable map"
3.1084 + ///parameters and each write request will be passed to both of them.
3.1085 + ///If \c M1 is also \c concepts::ReadMap "readable",
3.1086 + ///then the read operations will return the
3.1087 + ///corresponding values of \c M1.
3.1088 + ///
3.1089 + ///The \c Key and \c Value are inherited from \c M1.
3.1090 + ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
3.1091 + ///
3.1092 + ///\sa ForkMap
3.1093 + template<typename M1, typename M2>
3.1094 + class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
3.1095 + M1& m1;
3.1096 + M2& m2;
3.1097 + public:
3.1098 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
3.1099 + typedef typename Parent::Key Key;
3.1100 + typedef typename Parent::Value Value;
3.1101 +
3.1102 + ///Constructor
3.1103 + ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
3.1104 + ///\e
3.1105 + Value operator[](Key k) const {return m1[k];}
3.1106 + ///\e
3.1107 + void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
3.1108 + };
3.1109 +
3.1110 + ///Returns a \c ForkMap class
3.1111 +
3.1112 + ///This function just returns a \c ForkMap class.
3.1113 + ///\relates ForkMap
3.1114 + template <typename M1, typename M2>
3.1115 + inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
3.1116 + return ForkMap<M1, M2>(m1,m2);
3.1117 + }
3.1118 +
3.1119 + ///Returns a \c ForkWriteMap class
3.1120 +
3.1121 + ///This function just returns a \c ForkWriteMap class.
3.1122 + ///\relates ForkWriteMap
3.1123 + template <typename M1, typename M2>
3.1124 + inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
3.1125 + return ForkWriteMap<M1, M2>(m1,m2);
3.1126 + }
3.1127 +
3.1128 +
3.1129 +
3.1130 + /* ************* BOOL MAPS ******************* */
3.1131 +
3.1132 + ///Logical 'not' of a map
3.1133 +
3.1134 + ///This bool \c concepts::ReadMap "read only map" returns the
3.1135 + ///logical negation of the value returned by the given map.
3.1136 + ///Its \c Key is inherited from \c M, its Value is \c bool.
3.1137 + ///
3.1138 + ///\sa NotWriteMap
3.1139 + template <typename M>
3.1140 + class NotMap : public MapBase<typename M::Key, bool> {
3.1141 + const M& m;
3.1142 + public:
3.1143 + typedef MapBase<typename M::Key, bool> Parent;
3.1144 + typedef typename Parent::Key Key;
3.1145 + typedef typename Parent::Value Value;
3.1146 +
3.1147 + /// Constructor
3.1148 + NotMap(const M &_m) : m(_m) {};
3.1149 + ///\e
3.1150 + Value operator[](Key k) const {return !m[k];}
3.1151 + };
3.1152 +
3.1153 + ///Logical 'not' of a map (ReadWrie version)
3.1154 +
3.1155 + ///This bool \c concepts::ReadWriteMap "read-write map" returns the
3.1156 + ///logical negation of the value returned by the given map. When it is set,
3.1157 + ///the opposite value is set to the original map.
3.1158 + ///Its \c Key is inherited from \c M, its Value is \c bool.
3.1159 + ///
3.1160 + ///\sa NotMap
3.1161 + template <typename M>
3.1162 + class NotWriteMap : public MapBase<typename M::Key, bool> {
3.1163 + M& m;
3.1164 + public:
3.1165 + typedef MapBase<typename M::Key, bool> Parent;
3.1166 + typedef typename Parent::Key Key;
3.1167 + typedef typename Parent::Value Value;
3.1168 +
3.1169 + /// Constructor
3.1170 + NotWriteMap(M &_m) : m(_m) {};
3.1171 + ///\e
3.1172 + Value operator[](Key k) const {return !m[k];}
3.1173 + ///\e
3.1174 + void set(Key k, bool v) { m.set(k, !v); }
3.1175 + };
3.1176 +
3.1177 + ///Returns a \c NotMap class
3.1178 +
3.1179 + ///This function just returns a \c NotMap class.
3.1180 + ///\relates NotMap
3.1181 + template <typename M>
3.1182 + inline NotMap<M> notMap(const M &m) {
3.1183 + return NotMap<M>(m);
3.1184 + }
3.1185 +
3.1186 + ///Returns a \c NotWriteMap class
3.1187 +
3.1188 + ///This function just returns a \c NotWriteMap class.
3.1189 + ///\relates NotWriteMap
3.1190 + template <typename M>
3.1191 + inline NotWriteMap<M> notMap(M &m) {
3.1192 + return NotWriteMap<M>(m);
3.1193 + }
3.1194 +
3.1195 + namespace _maps_bits {
3.1196 +
3.1197 + template <typename Value>
3.1198 + struct Identity {
3.1199 + typedef Value argument_type;
3.1200 + typedef Value result_type;
3.1201 + Value operator()(const Value& val) const {
3.1202 + return val;
3.1203 + }
3.1204 + };
3.1205 +
3.1206 + template <typename _Iterator, typename Enable = void>
3.1207 + struct IteratorTraits {
3.1208 + typedef typename std::iterator_traits<_Iterator>::value_type Value;
3.1209 + };
3.1210 +
3.1211 + template <typename _Iterator>
3.1212 + struct IteratorTraits<_Iterator,
3.1213 + typename exists<typename _Iterator::container_type>::type>
3.1214 + {
3.1215 + typedef typename _Iterator::container_type::value_type Value;
3.1216 + };
3.1217 +
3.1218 + }
3.1219 +
3.1220 +
3.1221 + /// \brief Writable bool map for logging each \c true assigned element
3.1222 + ///
3.1223 + /// Writable bool map for logging each \c true assigned element, i.e it
3.1224 + /// copies all the keys set to \c true to the given iterator.
3.1225 + ///
3.1226 + /// \note The container of the iterator should contain space
3.1227 + /// for each element.
3.1228 + ///
3.1229 + /// The following example shows how you can write the edges found by the Prim
3.1230 + /// algorithm directly
3.1231 + /// to the standard output.
3.1232 + ///\code
3.1233 + /// typedef IdMap<Graph, Edge> EdgeIdMap;
3.1234 + /// EdgeIdMap edgeId(graph);
3.1235 + ///
3.1236 + /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
3.1237 + /// EdgeIdFunctor edgeIdFunctor(edgeId);
3.1238 + ///
3.1239 + /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
3.1240 + /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
3.1241 + ///
3.1242 + /// prim(graph, cost, writerMap);
3.1243 + ///\endcode
3.1244 + ///
3.1245 + ///\sa BackInserterBoolMap
3.1246 + ///
3.1247 + ///\todo Revise the name of this class and the related ones.
3.1248 + template <typename _Iterator,
3.1249 + typename _Functor =
3.1250 + _maps_bits::Identity<typename _maps_bits::
3.1251 + IteratorTraits<_Iterator>::Value> >
3.1252 + class StoreBoolMap {
3.1253 + public:
3.1254 + typedef _Iterator Iterator;
3.1255 +
3.1256 + typedef typename _Functor::argument_type Key;
3.1257 + typedef bool Value;
3.1258 +
3.1259 + typedef _Functor Functor;
3.1260 +
3.1261 + /// Constructor
3.1262 + StoreBoolMap(Iterator it, const Functor& functor = Functor())
3.1263 + : _begin(it), _end(it), _functor(functor) {}
3.1264 +
3.1265 + /// Gives back the given iterator set for the first key
3.1266 + Iterator begin() const {
3.1267 + return _begin;
3.1268 + }
3.1269 +
3.1270 + /// Gives back the the 'after the last' iterator
3.1271 + Iterator end() const {
3.1272 + return _end;
3.1273 + }
3.1274 +
3.1275 + /// The \c set function of the map
3.1276 + void set(const Key& key, Value value) const {
3.1277 + if (value) {
3.1278 + *_end++ = _functor(key);
3.1279 + }
3.1280 + }
3.1281 +
3.1282 + private:
3.1283 + Iterator _begin;
3.1284 + mutable Iterator _end;
3.1285 + Functor _functor;
3.1286 + };
3.1287 +
3.1288 + /// \brief Writable bool map for logging each \c true assigned element in
3.1289 + /// a back insertable container.
3.1290 + ///
3.1291 + /// Writable bool map for logging each \c true assigned element by pushing
3.1292 + /// them into a back insertable container.
3.1293 + /// It can be used to retrieve the items into a standard
3.1294 + /// container. The next example shows how you can store the
3.1295 + /// edges found by the Prim algorithm in a vector.
3.1296 + ///
3.1297 + ///\code
3.1298 + /// vector<Edge> span_tree_edges;
3.1299 + /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
3.1300 + /// prim(graph, cost, inserter_map);
3.1301 + ///\endcode
3.1302 + ///
3.1303 + ///\sa StoreBoolMap
3.1304 + ///\sa FrontInserterBoolMap
3.1305 + ///\sa InserterBoolMap
3.1306 + template <typename Container,
3.1307 + typename Functor =
3.1308 + _maps_bits::Identity<typename Container::value_type> >
3.1309 + class BackInserterBoolMap {
3.1310 + public:
3.1311 + typedef typename Container::value_type Key;
3.1312 + typedef bool Value;
3.1313 +
3.1314 + /// Constructor
3.1315 + BackInserterBoolMap(Container& _container,
3.1316 + const Functor& _functor = Functor())
3.1317 + : container(_container), functor(_functor) {}
3.1318 +
3.1319 + /// The \c set function of the map
3.1320 + void set(const Key& key, Value value) {
3.1321 + if (value) {
3.1322 + container.push_back(functor(key));
3.1323 + }
3.1324 + }
3.1325 +
3.1326 + private:
3.1327 + Container& container;
3.1328 + Functor functor;
3.1329 + };
3.1330 +
3.1331 + /// \brief Writable bool map for logging each \c true assigned element in
3.1332 + /// a front insertable container.
3.1333 + ///
3.1334 + /// Writable bool map for logging each \c true assigned element by pushing
3.1335 + /// them into a front insertable container.
3.1336 + /// It can be used to retrieve the items into a standard
3.1337 + /// container. For example see \ref BackInserterBoolMap.
3.1338 + ///
3.1339 + ///\sa BackInserterBoolMap
3.1340 + ///\sa InserterBoolMap
3.1341 + template <typename Container,
3.1342 + typename Functor =
3.1343 + _maps_bits::Identity<typename Container::value_type> >
3.1344 + class FrontInserterBoolMap {
3.1345 + public:
3.1346 + typedef typename Container::value_type Key;
3.1347 + typedef bool Value;
3.1348 +
3.1349 + /// Constructor
3.1350 + FrontInserterBoolMap(Container& _container,
3.1351 + const Functor& _functor = Functor())
3.1352 + : container(_container), functor(_functor) {}
3.1353 +
3.1354 + /// The \c set function of the map
3.1355 + void set(const Key& key, Value value) {
3.1356 + if (value) {
3.1357 + container.push_front(functor(key));
3.1358 + }
3.1359 + }
3.1360 +
3.1361 + private:
3.1362 + Container& container;
3.1363 + Functor functor;
3.1364 + };
3.1365 +
3.1366 + /// \brief Writable bool map for storing each \c true assigned element in
3.1367 + /// an insertable container.
3.1368 + ///
3.1369 + /// Writable bool map for storing each \c true assigned element in an
3.1370 + /// insertable container. It will insert all the keys set to \c true into
3.1371 + /// the container.
3.1372 + ///
3.1373 + /// For example, if you want to store the cut arcs of the strongly
3.1374 + /// connected components in a set you can use the next code:
3.1375 + ///
3.1376 + ///\code
3.1377 + /// set<Arc> cut_arcs;
3.1378 + /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
3.1379 + /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
3.1380 + ///\endcode
3.1381 + ///
3.1382 + ///\sa BackInserterBoolMap
3.1383 + ///\sa FrontInserterBoolMap
3.1384 + template <typename Container,
3.1385 + typename Functor =
3.1386 + _maps_bits::Identity<typename Container::value_type> >
3.1387 + class InserterBoolMap {
3.1388 + public:
3.1389 + typedef typename Container::value_type Key;
3.1390 + typedef bool Value;
3.1391 +
3.1392 + /// Constructor with specified iterator
3.1393 +
3.1394 + /// Constructor with specified iterator.
3.1395 + /// \param _container The container for storing the elements.
3.1396 + /// \param _it The elements will be inserted before this iterator.
3.1397 + /// \param _functor The functor that is used when an element is stored.
3.1398 + InserterBoolMap(Container& _container, typename Container::iterator _it,
3.1399 + const Functor& _functor = Functor())
3.1400 + : container(_container), it(_it), functor(_functor) {}
3.1401 +
3.1402 + /// Constructor
3.1403 +
3.1404 + /// Constructor without specified iterator.
3.1405 + /// The elements will be inserted before <tt>_container.end()</tt>.
3.1406 + /// \param _container The container for storing the elements.
3.1407 + /// \param _functor The functor that is used when an element is stored.
3.1408 + InserterBoolMap(Container& _container, const Functor& _functor = Functor())
3.1409 + : container(_container), it(_container.end()), functor(_functor) {}
3.1410 +
3.1411 + /// The \c set function of the map
3.1412 + void set(const Key& key, Value value) {
3.1413 + if (value) {
3.1414 + it = container.insert(it, functor(key));
3.1415 + ++it;
3.1416 + }
3.1417 + }
3.1418 +
3.1419 + private:
3.1420 + Container& container;
3.1421 + typename Container::iterator it;
3.1422 + Functor functor;
3.1423 + };
3.1424 +
3.1425 + /// \brief Writable bool map for filling each \c true assigned element with a
3.1426 + /// given value.
3.1427 + ///
3.1428 + /// Writable bool map for filling each \c true assigned element with a
3.1429 + /// given value. The value can set the container.
3.1430 + ///
3.1431 + /// The following code finds the connected components of a graph
3.1432 + /// and stores it in the \c comp map:
3.1433 + ///\code
3.1434 + /// typedef Graph::NodeMap<int> ComponentMap;
3.1435 + /// ComponentMap comp(graph);
3.1436 + /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
3.1437 + /// ComponentFillerMap filler(comp, 0);
3.1438 + ///
3.1439 + /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
3.1440 + /// dfs.processedMap(filler);
3.1441 + /// dfs.init();
3.1442 + /// for (NodeIt it(graph); it != INVALID; ++it) {
3.1443 + /// if (!dfs.reached(it)) {
3.1444 + /// dfs.addSource(it);
3.1445 + /// dfs.start();
3.1446 + /// ++filler.fillValue();
3.1447 + /// }
3.1448 + /// }
3.1449 + ///\endcode
3.1450 + template <typename Map>
3.1451 + class FillBoolMap {
3.1452 + public:
3.1453 + typedef typename Map::Key Key;
3.1454 + typedef bool Value;
3.1455 +
3.1456 + /// Constructor
3.1457 + FillBoolMap(Map& _map, const typename Map::Value& _fill)
3.1458 + : map(_map), fill(_fill) {}
3.1459 +
3.1460 + /// Constructor
3.1461 + FillBoolMap(Map& _map)
3.1462 + : map(_map), fill() {}
3.1463 +
3.1464 + /// Gives back the current fill value
3.1465 + const typename Map::Value& fillValue() const {
3.1466 + return fill;
3.1467 + }
3.1468 +
3.1469 + /// Gives back the current fill value
3.1470 + typename Map::Value& fillValue() {
3.1471 + return fill;
3.1472 + }
3.1473 +
3.1474 + /// Sets the current fill value
3.1475 + void fillValue(const typename Map::Value& _fill) {
3.1476 + fill = _fill;
3.1477 + }
3.1478 +
3.1479 + /// The \c set function of the map
3.1480 + void set(const Key& key, Value value) {
3.1481 + if (value) {
3.1482 + map.set(key, fill);
3.1483 + }
3.1484 + }
3.1485 +
3.1486 + private:
3.1487 + Map& map;
3.1488 + typename Map::Value fill;
3.1489 + };
3.1490 +
3.1491 +
3.1492 + /// \brief Writable bool map for storing the sequence number of
3.1493 + /// \c true assignments.
3.1494 + ///
3.1495 + /// Writable bool map that stores for each \c true assigned elements
3.1496 + /// the sequence number of this setting.
3.1497 + /// It makes it easy to calculate the leaving
3.1498 + /// order of the nodes in the \c Dfs algorithm.
3.1499 + ///
3.1500 + ///\code
3.1501 + /// typedef Digraph::NodeMap<int> OrderMap;
3.1502 + /// OrderMap order(digraph);
3.1503 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
3.1504 + /// OrderSetterMap setter(order);
3.1505 + /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
3.1506 + /// dfs.processedMap(setter);
3.1507 + /// dfs.init();
3.1508 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
3.1509 + /// if (!dfs.reached(it)) {
3.1510 + /// dfs.addSource(it);
3.1511 + /// dfs.start();
3.1512 + /// }
3.1513 + /// }
3.1514 + ///\endcode
3.1515 + ///
3.1516 + /// The storing of the discovering order is more difficult because the
3.1517 + /// ReachedMap should be readable in the dfs algorithm but the setting
3.1518 + /// order map is not readable. Thus we must use the fork map:
3.1519 + ///
3.1520 + ///\code
3.1521 + /// typedef Digraph::NodeMap<int> OrderMap;
3.1522 + /// OrderMap order(digraph);
3.1523 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
3.1524 + /// OrderSetterMap setter(order);
3.1525 + /// typedef Digraph::NodeMap<bool> StoreMap;
3.1526 + /// StoreMap store(digraph);
3.1527 + ///
3.1528 + /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
3.1529 + /// ReachedMap reached(store, setter);
3.1530 + ///
3.1531 + /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
3.1532 + /// dfs.reachedMap(reached);
3.1533 + /// dfs.init();
3.1534 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
3.1535 + /// if (!dfs.reached(it)) {
3.1536 + /// dfs.addSource(it);
3.1537 + /// dfs.start();
3.1538 + /// }
3.1539 + /// }
3.1540 + ///\endcode
3.1541 + template <typename Map>
3.1542 + class SettingOrderBoolMap {
3.1543 + public:
3.1544 + typedef typename Map::Key Key;
3.1545 + typedef bool Value;
3.1546 +
3.1547 + /// Constructor
3.1548 + SettingOrderBoolMap(Map& _map)
3.1549 + : map(_map), counter(0) {}
3.1550 +
3.1551 + /// Number of set operations.
3.1552 + int num() const {
3.1553 + return counter;
3.1554 + }
3.1555 +
3.1556 + /// Setter function of the map
3.1557 + void set(const Key& key, Value value) {
3.1558 + if (value) {
3.1559 + map.set(key, counter++);
3.1560 + }
3.1561 + }
3.1562 +
3.1563 + private:
3.1564 + Map& map;
3.1565 + int counter;
3.1566 + };
3.1567 +
3.1568 + /// @}
3.1569 +}
3.1570 +
3.1571 +#endif // LEMON_MAPS_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/test/maps_test.cc Fri Jan 04 21:45:55 2008 +0100
4.3 @@ -0,0 +1,108 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2007
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#include <deque>
4.23 +#include <set>
4.24 +
4.25 +#include <lemon/concept_check.h>
4.26 +#include <lemon/concepts/maps.h>
4.27 +#include <lemon/maps.h>
4.28 +
4.29 +#include "test_tools.h"
4.30 +
4.31 +using namespace lemon;
4.32 +using namespace lemon::concepts;
4.33 +
4.34 +struct A {};
4.35 +inline bool operator<(A, A) { return true; }
4.36 +struct B {};
4.37 +
4.38 +class F {
4.39 +public:
4.40 + typedef A argument_type;
4.41 + typedef B result_type;
4.42 +
4.43 + B operator()(const A &) const {return B();}
4.44 +};
4.45 +
4.46 +int func(A) {return 3;}
4.47 +
4.48 +int binc(int, B) {return 4;}
4.49 +
4.50 +typedef ReadMap<A,double> DoubleMap;
4.51 +typedef ReadWriteMap<A, double> WriteDoubleMap;
4.52 +
4.53 +typedef ReadMap<A,bool> BoolMap;
4.54 +typedef ReadWriteMap<A, bool> BoolWriteMap;
4.55 +
4.56 +int main()
4.57 +{ // checking graph components
4.58 +
4.59 + checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
4.60 + checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
4.61 + checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
4.62 + checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
4.63 +
4.64 + checkConcept<ReadMap<A,double>, AddMap<DoubleMap,DoubleMap> >();
4.65 + checkConcept<ReadMap<A,double>, SubMap<DoubleMap,DoubleMap> >();
4.66 + checkConcept<ReadMap<A,double>, MulMap<DoubleMap,DoubleMap> >();
4.67 + checkConcept<ReadMap<A,double>, DivMap<DoubleMap,DoubleMap> >();
4.68 + checkConcept<ReadMap<A,double>, NegMap<DoubleMap> >();
4.69 + checkConcept<ReadWriteMap<A,double>, NegWriteMap<WriteDoubleMap> >();
4.70 + checkConcept<ReadMap<A,double>, AbsMap<DoubleMap> >();
4.71 + checkConcept<ReadMap<A,double>, ShiftMap<DoubleMap> >();
4.72 + checkConcept<ReadWriteMap<A,double>, ShiftWriteMap<WriteDoubleMap> >();
4.73 + checkConcept<ReadMap<A,double>, ScaleMap<DoubleMap> >();
4.74 + checkConcept<ReadWriteMap<A,double>, ScaleWriteMap<WriteDoubleMap> >();
4.75 + checkConcept<ReadMap<A,double>, ForkMap<DoubleMap, DoubleMap> >();
4.76 + checkConcept<ReadWriteMap<A,double>,
4.77 + ForkWriteMap<WriteDoubleMap, WriteDoubleMap> >();
4.78 +
4.79 + checkConcept<ReadMap<B,double>, ComposeMap<DoubleMap,ReadMap<B,A> > >();
4.80 +
4.81 + checkConcept<ReadMap<A,B>, FunctorMap<F, A, B> >();
4.82 +
4.83 + checkConcept<ReadMap<A, bool>, NotMap<BoolMap> >();
4.84 + checkConcept<ReadWriteMap<A, bool>, NotWriteMap<BoolWriteMap> >();
4.85 +
4.86 + checkConcept<WriteMap<A, bool>, StoreBoolMap<A*> >();
4.87 + checkConcept<WriteMap<A, bool>, BackInserterBoolMap<std::deque<A> > >();
4.88 + checkConcept<WriteMap<A, bool>, FrontInserterBoolMap<std::deque<A> > >();
4.89 + checkConcept<WriteMap<A, bool>, InserterBoolMap<std::set<A> > >();
4.90 + checkConcept<WriteMap<A, bool>, FillBoolMap<WriteMap<A, B> > >();
4.91 + checkConcept<WriteMap<A, bool>, SettingOrderBoolMap<WriteMap<A, int> > >();
4.92 +
4.93 + int a;
4.94 +
4.95 + a=mapFunctor(constMap<A,int>(2))(A());
4.96 + check(a==2,"Something is wrong with mapFunctor");
4.97 +
4.98 + B b;
4.99 + b=functorMap(F())[A()];
4.100 +
4.101 + a=functorMap(&func)[A()];
4.102 + check(a==3,"Something is wrong with functorMap");
4.103 +
4.104 + a=combineMap(constMap<B, int, 1>(), identityMap<B>(), &binc)[B()];
4.105 + check(a==4,"Something is wrong with combineMap");
4.106 +
4.107 +
4.108 + std::cout << __FILE__ ": All tests passed.\n";
4.109 +
4.110 + return 0;
4.111 +}