1.1 --- a/lemon/Makefile.am Thu Jan 03 14:58:42 2008 +0100
1.2 +++ b/lemon/Makefile.am Wed Feb 06 10:52:58 2008 +0000
1.3 @@ -15,13 +15,16 @@
1.4 lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
1.5
1.6 lemon_HEADERS += \
1.7 + lemon/concept_check.h \
1.8 lemon/dim2.h \
1.9 lemon/random.h \
1.10 lemon/list_graph.h \
1.11 + lemon/maps.h \
1.12 lemon/tolerance.h
1.13
1.14 bits_HEADERS += \
1.15 lemon/bits/invalid.h \
1.16 lemon/bits/utility.h
1.17
1.18 -concept_HEADERS +=
1.19 +concept_HEADERS += \
1.20 + lemon/concepts/maps.h
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/concept_check.h Wed Feb 06 10:52:58 2008 +0000
2.3 @@ -0,0 +1,105 @@
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 +// This file contains a modified version of the concept checking
2.23 +// utility from BOOST.
2.24 +// See the appropriate copyright notice below.
2.25 +
2.26 +// (C) Copyright Jeremy Siek 2000.
2.27 +// Distributed under the Boost Software License, Version 1.0. (See
2.28 +// accompanying file LICENSE_1_0.txt or copy at
2.29 +// http://www.boost.org/LICENSE_1_0.txt)
2.30 +//
2.31 +// Revision History:
2.32 +// 05 May 2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
2.33 +// 02 April 2001: Removed limits header altogether. (Jeremy Siek)
2.34 +// 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
2.35 +//
2.36 +
2.37 +// See http://www.boost.org/libs/concept_check for documentation.
2.38 +
2.39 +#ifndef LEMON_CONCEPT_CHECKS_H
2.40 +#define LEMON_CONCEPT_CHECKS_H
2.41 +
2.42 +namespace lemon {
2.43 +
2.44 + /*
2.45 + "inline" is used for ignore_unused_variable_warning()
2.46 + and function_requires() to make sure there is no
2.47 + overtarget with g++.
2.48 + */
2.49 +
2.50 + template <class T> inline void ignore_unused_variable_warning(const T&) { }
2.51 +
2.52 + template <class Concept>
2.53 + inline void function_requires()
2.54 + {
2.55 +#if !defined(NDEBUG)
2.56 + void (Concept::*x)() = & Concept::constraints;
2.57 + ignore_unused_variable_warning(x);
2.58 +#endif
2.59 + }
2.60 +
2.61 + template <typename Concept, typename Type>
2.62 + inline void checkConcept() {
2.63 +#if !defined(NDEBUG)
2.64 + typedef typename Concept::template Constraints<Type> ConceptCheck;
2.65 + void (ConceptCheck::*x)() = & ConceptCheck::constraints;
2.66 + ignore_unused_variable_warning(x);
2.67 +#endif
2.68 + }
2.69 +
2.70 +#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
2.71 + typedef void (ns::concept <type_var>::* func##type_var##concept)(); \
2.72 + template <func##type_var##concept Tp1_> \
2.73 + struct concept_checking_##type_var##concept { }; \
2.74 + typedef concept_checking_##type_var##concept< \
2.75 + BOOST_FPTR ns::concept<type_var>::constraints> \
2.76 + concept_checking_typedef_##type_var##concept
2.77 +
2.78 +#define BOOST_CLASS_REQUIRE2(type_var1, type_var2, ns, concept) \
2.79 + typedef void (ns::concept <type_var1,type_var2>::* \
2.80 + func##type_var1##type_var2##concept)(); \
2.81 + template <func##type_var1##type_var2##concept Tp1_> \
2.82 + struct concept_checking_##type_var1##type_var2##concept { }; \
2.83 + typedef concept_checking_##type_var1##type_var2##concept< \
2.84 + BOOST_FPTR ns::concept<type_var1,type_var2>::constraints> \
2.85 + concept_checking_typedef_##type_var1##type_var2##concept
2.86 +
2.87 +#define BOOST_CLASS_REQUIRE3(tv1, tv2, tv3, ns, concept) \
2.88 + typedef void (ns::concept <tv1,tv2,tv3>::* \
2.89 + func##tv1##tv2##tv3##concept)(); \
2.90 + template <func##tv1##tv2##tv3##concept Tp1_> \
2.91 + struct concept_checking_##tv1##tv2##tv3##concept { }; \
2.92 + typedef concept_checking_##tv1##tv2##tv3##concept< \
2.93 + BOOST_FPTR ns::concept<tv1,tv2,tv3>::constraints> \
2.94 + concept_checking_typedef_##tv1##tv2##tv3##concept
2.95 +
2.96 +#define BOOST_CLASS_REQUIRE4(tv1, tv2, tv3, tv4, ns, concept) \
2.97 + typedef void (ns::concept <tv1,tv2,tv3,tv4>::* \
2.98 + func##tv1##tv2##tv3##tv4##concept)(); \
2.99 + template <func##tv1##tv2##tv3##tv4##concept Tp1_> \
2.100 + struct concept_checking_##tv1##tv2##tv3##tv4##concept { }; \
2.101 + typedef concept_checking_##tv1##tv2##tv3##tv4##concept< \
2.102 + BOOST_FPTR ns::concept<tv1,tv2,tv3,tv4>::constraints> \
2.103 + concept_checking_typedef_##tv1##tv2##tv3##tv4##concept
2.104 +
2.105 +
2.106 +} // namespace lemon
2.107 +
2.108 +#endif // LEMON_CONCEPT_CHECKS_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/concepts/maps.h Wed Feb 06 10:52:58 2008 +0000
3.3 @@ -0,0 +1,207 @@
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_CONCEPT_MAPS_H
3.23 +#define LEMON_CONCEPT_MAPS_H
3.24 +
3.25 +#include <lemon/bits/utility.h>
3.26 +#include <lemon/concept_check.h>
3.27 +
3.28 +///\ingroup concept
3.29 +///\file
3.30 +///\brief Map concepts checking classes for testing and documenting.
3.31 +
3.32 +namespace lemon {
3.33 +
3.34 + namespace concepts {
3.35 +
3.36 + /// \addtogroup concept
3.37 + /// @{
3.38 +
3.39 + /// Readable map concept
3.40 +
3.41 + /// Readable map concept.
3.42 + ///
3.43 + template<typename K, typename T>
3.44 + class ReadMap
3.45 + {
3.46 + public:
3.47 + /// Map's key type.
3.48 + typedef K Key;
3.49 + /// Map's value type. (The type of objects associated with the keys).
3.50 + typedef T Value;
3.51 +
3.52 + /// Returns the value associated with a key.
3.53 +
3.54 + /// \bug Value shouldn't need to be default constructible.
3.55 + ///
3.56 + Value operator[](const Key &) const {return Value();}
3.57 +
3.58 + template<typename _ReadMap>
3.59 + struct Constraints {
3.60 +
3.61 + void constraints() {
3.62 + Value val = m[key];
3.63 + val = m[key];
3.64 + typename _ReadMap::Value own_val = m[own_key];
3.65 + own_val = m[own_key];
3.66 +
3.67 + ignore_unused_variable_warning(val);
3.68 + ignore_unused_variable_warning(own_val);
3.69 + ignore_unused_variable_warning(key);
3.70 + }
3.71 + Key& key;
3.72 + typename _ReadMap::Key& own_key;
3.73 + _ReadMap& m;
3.74 + };
3.75 +
3.76 + };
3.77 +
3.78 +
3.79 + /// Writable map concept
3.80 +
3.81 + /// Writable map concept.
3.82 + ///
3.83 + template<typename K, typename T>
3.84 + class WriteMap
3.85 + {
3.86 + public:
3.87 + /// Map's key type.
3.88 + typedef K Key;
3.89 + /// Map's value type. (The type of objects associated with the keys).
3.90 + typedef T Value;
3.91 +
3.92 + /// Sets the value associated with a key.
3.93 + void set(const Key &,const Value &) {}
3.94 +
3.95 + ///Default constructor
3.96 + WriteMap() {}
3.97 +
3.98 + template <typename _WriteMap>
3.99 + struct Constraints {
3.100 + void constraints() {
3.101 + // No constraints for constructor.
3.102 + m.set(key, val);
3.103 + m.set(own_key, own_val);
3.104 + ignore_unused_variable_warning(key);
3.105 + ignore_unused_variable_warning(val);
3.106 + ignore_unused_variable_warning(own_key);
3.107 + ignore_unused_variable_warning(own_val);
3.108 + }
3.109 +
3.110 + Value& val;
3.111 + typename _WriteMap::Value own_val;
3.112 + Key& key;
3.113 + typename _WriteMap::Key& own_key;
3.114 + _WriteMap& m;
3.115 +
3.116 + };
3.117 + };
3.118 +
3.119 + /// Read/Writable map concept
3.120 +
3.121 + /// Read/writable map concept.
3.122 + ///
3.123 + template<typename K, typename T>
3.124 + class ReadWriteMap : public ReadMap<K,T>,
3.125 + public WriteMap<K,T>
3.126 + {
3.127 + public:
3.128 + /// Map's key type.
3.129 + typedef K Key;
3.130 + /// Map's value type. (The type of objects associated with the keys).
3.131 + typedef T Value;
3.132 +
3.133 + /// Returns the value associated with a key.
3.134 + Value operator[](const Key &) const {return Value();}
3.135 + /// Sets the value associated with a key.
3.136 + void set(const Key & ,const Value &) {}
3.137 +
3.138 + template<typename _ReadWriteMap>
3.139 + struct Constraints {
3.140 + void constraints() {
3.141 + checkConcept<ReadMap<K, T>, _ReadWriteMap >();
3.142 + checkConcept<WriteMap<K, T>, _ReadWriteMap >();
3.143 + }
3.144 + };
3.145 + };
3.146 +
3.147 +
3.148 + /// Dereferable map concept
3.149 +
3.150 + /// Dereferable map concept.
3.151 + ///
3.152 + template<typename K, typename T, typename R, typename CR>
3.153 + class ReferenceMap : public ReadWriteMap<K,T>
3.154 + {
3.155 + public:
3.156 + /// Tag for reference maps.
3.157 + typedef True ReferenceMapTag;
3.158 + /// Map's key type.
3.159 + typedef K Key;
3.160 + /// Map's value type. (The type of objects associated with the keys).
3.161 + typedef T Value;
3.162 + /// Map's reference type.
3.163 + typedef R Reference;
3.164 + /// Map's const reference type.
3.165 + typedef CR ConstReference;
3.166 +
3.167 + protected:
3.168 + Value tmp;
3.169 + public:
3.170 +
3.171 + ///Returns a reference to the value associated to a key.
3.172 + Reference operator[](const Key &) { return tmp; }
3.173 + ///Returns a const reference to the value associated to a key.
3.174 + ConstReference operator[](const Key &) const { return tmp; }
3.175 + /// Sets the value associated with a key.
3.176 + void set(const Key &k,const Value &t) { operator[](k)=t; }
3.177 +
3.178 + /// \todo Rethink this concept.
3.179 + template<typename _ReferenceMap>
3.180 + struct ReferenceMapConcept {
3.181 +
3.182 + void constraints() {
3.183 + checkConcept<ReadWriteMap, _ReferenceMap >();
3.184 + m[key] = val;
3.185 + val = m[key];
3.186 + m[key] = ref;
3.187 + ref = m[key];
3.188 + m[own_key] = own_val;
3.189 + own_val = m[own_key];
3.190 + m[own_key] = own_ref;
3.191 + own_ref = m[own_key];
3.192 + }
3.193 +
3.194 + typename _ReferenceMap::Key& own_key;
3.195 + typename _ReferenceMap::Value& own_val;
3.196 + typename _ReferenceMap::Reference& own_ref;
3.197 + Key& key;
3.198 + Value& val;
3.199 + Reference& ref;
3.200 + _ReferenceMap& m;
3.201 + };
3.202 + };
3.203 +
3.204 + // @}
3.205 +
3.206 + } //namespace concepts
3.207 +
3.208 +} //namespace lemon
3.209 +
3.210 +#endif // LEMON_CONCEPT_MAPS_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/maps.h Wed Feb 06 10:52:58 2008 +0000
4.3 @@ -0,0 +1,1568 @@
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 +#ifndef LEMON_MAPS_H
4.23 +#define LEMON_MAPS_H
4.24 +
4.25 +#include <iterator>
4.26 +#include <functional>
4.27 +#include <vector>
4.28 +
4.29 +#include <lemon/bits/utility.h>
4.30 +// #include <lemon/bits/traits.h>
4.31 +
4.32 +///\file
4.33 +///\ingroup maps
4.34 +///\brief Miscellaneous property maps
4.35 +///
4.36 +#include <map>
4.37 +
4.38 +namespace lemon {
4.39 +
4.40 + /// \addtogroup maps
4.41 + /// @{
4.42 +
4.43 + /// Base class of maps.
4.44 +
4.45 + /// Base class of maps.
4.46 + /// It provides the necessary <tt>typedef</tt>s required by the map concept.
4.47 + template<typename K, typename T>
4.48 + class MapBase {
4.49 + public:
4.50 + ///\e
4.51 + typedef K Key;
4.52 + ///\e
4.53 + typedef T Value;
4.54 + };
4.55 +
4.56 + /// Null map. (a.k.a. DoNothingMap)
4.57 +
4.58 + /// This map can be used if you have to provide a map only for
4.59 + /// its type definitions, or if you have to provide a writable map,
4.60 + /// but data written to it is not required (i.e. it will be sent to
4.61 + /// <tt>/dev/null</tt>).
4.62 + template<typename K, typename T>
4.63 + class NullMap : public MapBase<K, T> {
4.64 + public:
4.65 + typedef MapBase<K, T> Parent;
4.66 + typedef typename Parent::Key Key;
4.67 + typedef typename Parent::Value Value;
4.68 +
4.69 + /// Gives back a default constructed element.
4.70 + T operator[](const K&) const { return T(); }
4.71 + /// Absorbs the value.
4.72 + void set(const K&, const T&) {}
4.73 + };
4.74 +
4.75 + ///Returns a \c NullMap class
4.76 +
4.77 + ///This function just returns a \c NullMap class.
4.78 + ///\relates NullMap
4.79 + template <typename K, typename V>
4.80 + NullMap<K, V> nullMap() {
4.81 + return NullMap<K, V>();
4.82 + }
4.83 +
4.84 +
4.85 + /// Constant map.
4.86 +
4.87 + /// This is a readable map which assigns a specified value to each key.
4.88 + /// In other aspects it is equivalent to the \c NullMap.
4.89 + template<typename K, typename T>
4.90 + class ConstMap : public MapBase<K, T> {
4.91 + private:
4.92 + T v;
4.93 + public:
4.94 +
4.95 + typedef MapBase<K, T> Parent;
4.96 + typedef typename Parent::Key Key;
4.97 + typedef typename Parent::Value Value;
4.98 +
4.99 + /// Default constructor
4.100 +
4.101 + /// Default constructor.
4.102 + /// The value of the map will be uninitialized.
4.103 + /// (More exactly it will be default constructed.)
4.104 + ConstMap() {}
4.105 +
4.106 + /// Constructor with specified initial value
4.107 +
4.108 + /// Constructor with specified initial value.
4.109 + /// \param _v is the initial value of the map.
4.110 + ConstMap(const T &_v) : v(_v) {}
4.111 +
4.112 + ///\e
4.113 + T operator[](const K&) const { return v; }
4.114 +
4.115 + ///\e
4.116 + void setAll(const T &t) {
4.117 + v = t;
4.118 + }
4.119 +
4.120 + template<typename T1>
4.121 + struct rebind {
4.122 + typedef ConstMap<K, T1> other;
4.123 + };
4.124 +
4.125 + template<typename T1>
4.126 + ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
4.127 + };
4.128 +
4.129 + ///Returns a \c ConstMap class
4.130 +
4.131 + ///This function just returns a \c ConstMap class.
4.132 + ///\relates ConstMap
4.133 + template<typename K, typename V>
4.134 + inline ConstMap<K, V> constMap(const V &v) {
4.135 + return ConstMap<K, V>(v);
4.136 + }
4.137 +
4.138 +
4.139 + template<typename T, T v>
4.140 + struct Const { };
4.141 +
4.142 + /// Constant map with inlined constant value.
4.143 +
4.144 + /// This is a readable map which assigns a specified value to each key.
4.145 + /// In other aspects it is equivalent to the \c NullMap.
4.146 + template<typename K, typename V, V v>
4.147 + class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
4.148 + public:
4.149 + typedef MapBase<K, V> Parent;
4.150 + typedef typename Parent::Key Key;
4.151 + typedef typename Parent::Value Value;
4.152 +
4.153 + ConstMap() { }
4.154 + ///\e
4.155 + V operator[](const K&) const { return v; }
4.156 + ///\e
4.157 + void set(const K&, const V&) { }
4.158 + };
4.159 +
4.160 + ///Returns a \c ConstMap class
4.161 +
4.162 + ///This function just returns a \c ConstMap class with inlined value.
4.163 + ///\relates ConstMap
4.164 + template<typename K, typename V, V v>
4.165 + inline ConstMap<K, Const<V, v> > constMap() {
4.166 + return ConstMap<K, Const<V, v> >();
4.167 + }
4.168 +
4.169 + ///Map based on std::map
4.170 +
4.171 + ///This is essentially a wrapper for \c std::map with addition that
4.172 + ///you can specify a default value different from \c Value().
4.173 + template <typename K, typename T, typename Compare = std::less<K> >
4.174 + class StdMap {
4.175 + template <typename K1, typename T1, typename C1>
4.176 + friend class StdMap;
4.177 + public:
4.178 +
4.179 + typedef True ReferenceMapTag;
4.180 + ///\e
4.181 + typedef K Key;
4.182 + ///\e
4.183 + typedef T Value;
4.184 + ///\e
4.185 + typedef T& Reference;
4.186 + ///\e
4.187 + typedef const T& ConstReference;
4.188 +
4.189 + private:
4.190 +
4.191 + typedef std::map<K, T, Compare> Map;
4.192 + Value _value;
4.193 + Map _map;
4.194 +
4.195 + public:
4.196 +
4.197 + /// Constructor with specified default value
4.198 + StdMap(const T& value = T()) : _value(value) {}
4.199 + /// \brief Constructs the map from an appropriate std::map, and explicitly
4.200 + /// specifies a default value.
4.201 + template <typename T1, typename Comp1>
4.202 + StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
4.203 + : _map(map.begin(), map.end()), _value(value) {}
4.204 +
4.205 + /// \brief Constructs a map from an other StdMap.
4.206 + template<typename T1, typename Comp1>
4.207 + StdMap(const StdMap<Key, T1, Comp1> &c)
4.208 + : _map(c._map.begin(), c._map.end()), _value(c._value) {}
4.209 +
4.210 + private:
4.211 +
4.212 + StdMap& operator=(const StdMap&);
4.213 +
4.214 + public:
4.215 +
4.216 + ///\e
4.217 + Reference operator[](const Key &k) {
4.218 + typename Map::iterator it = _map.lower_bound(k);
4.219 + if (it != _map.end() && !_map.key_comp()(k, it->first))
4.220 + return it->second;
4.221 + else
4.222 + return _map.insert(it, std::make_pair(k, _value))->second;
4.223 + }
4.224 +
4.225 + /// \e
4.226 + ConstReference operator[](const Key &k) const {
4.227 + typename Map::const_iterator it = _map.find(k);
4.228 + if (it != _map.end())
4.229 + return it->second;
4.230 + else
4.231 + return _value;
4.232 + }
4.233 +
4.234 + /// \e
4.235 + void set(const Key &k, const T &t) {
4.236 + typename Map::iterator it = _map.lower_bound(k);
4.237 + if (it != _map.end() && !_map.key_comp()(k, it->first))
4.238 + it->second = t;
4.239 + else
4.240 + _map.insert(it, std::make_pair(k, t));
4.241 + }
4.242 +
4.243 + /// \e
4.244 + void setAll(const T &t) {
4.245 + _value = t;
4.246 + _map.clear();
4.247 + }
4.248 +
4.249 + template <typename T1, typename C1 = std::less<T1> >
4.250 + struct rebind {
4.251 + typedef StdMap<Key, T1, C1> other;
4.252 + };
4.253 + };
4.254 +
4.255 + /// \brief Map for storing values for the range \c [0..size-1] range keys
4.256 + ///
4.257 + /// The current map has the \c [0..size-1] keyset and the values
4.258 + /// are stored in a \c std::vector<T> container. It can be used with
4.259 + /// some data structures, for example \c UnionFind, \c BinHeap, when
4.260 + /// the used items are small integer numbers.
4.261 + ///
4.262 + /// \todo Revise its name
4.263 + template <typename T>
4.264 + class IntegerMap {
4.265 +
4.266 + template <typename T1>
4.267 + friend class IntegerMap;
4.268 +
4.269 + public:
4.270 +
4.271 + typedef True ReferenceMapTag;
4.272 + ///\e
4.273 + typedef int Key;
4.274 + ///\e
4.275 + typedef T Value;
4.276 + ///\e
4.277 + typedef T& Reference;
4.278 + ///\e
4.279 + typedef const T& ConstReference;
4.280 +
4.281 + private:
4.282 +
4.283 + typedef std::vector<T> Vector;
4.284 + Vector _vector;
4.285 +
4.286 + public:
4.287 +
4.288 + /// Constructor with specified default value
4.289 + IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
4.290 +
4.291 + /// \brief Constructs the map from an appropriate std::vector.
4.292 + template <typename T1>
4.293 + IntegerMap(const std::vector<T1>& vector)
4.294 + : _vector(vector.begin(), vector.end()) {}
4.295 +
4.296 + /// \brief Constructs a map from an other IntegerMap.
4.297 + template <typename T1>
4.298 + IntegerMap(const IntegerMap<T1> &c)
4.299 + : _vector(c._vector.begin(), c._vector.end()) {}
4.300 +
4.301 + /// \brief Resize the container
4.302 + void resize(int size, const T& value = T()) {
4.303 + _vector.resize(size, value);
4.304 + }
4.305 +
4.306 + private:
4.307 +
4.308 + IntegerMap& operator=(const IntegerMap&);
4.309 +
4.310 + public:
4.311 +
4.312 + ///\e
4.313 + Reference operator[](Key k) {
4.314 + return _vector[k];
4.315 + }
4.316 +
4.317 + /// \e
4.318 + ConstReference operator[](Key k) const {
4.319 + return _vector[k];
4.320 + }
4.321 +
4.322 + /// \e
4.323 + void set(const Key &k, const T& t) {
4.324 + _vector[k] = t;
4.325 + }
4.326 +
4.327 + };
4.328 +
4.329 + /// @}
4.330 +
4.331 + /// \addtogroup map_adaptors
4.332 + /// @{
4.333 +
4.334 + /// \brief Identity map.
4.335 + ///
4.336 + /// This map gives back the given key as value without any
4.337 + /// modification.
4.338 + template <typename T>
4.339 + class IdentityMap : public MapBase<T, T> {
4.340 + public:
4.341 + typedef MapBase<T, T> Parent;
4.342 + typedef typename Parent::Key Key;
4.343 + typedef typename Parent::Value Value;
4.344 +
4.345 + /// \e
4.346 + const T& operator[](const T& t) const {
4.347 + return t;
4.348 + }
4.349 + };
4.350 +
4.351 + ///Returns an \c IdentityMap class
4.352 +
4.353 + ///This function just returns an \c IdentityMap class.
4.354 + ///\relates IdentityMap
4.355 + template<typename T>
4.356 + inline IdentityMap<T> identityMap() {
4.357 + return IdentityMap<T>();
4.358 + }
4.359 +
4.360 +
4.361 + ///\brief Convert the \c Value of a map to another type using
4.362 + ///the default conversion.
4.363 + ///
4.364 + ///This \c concepts::ReadMap "read only map"
4.365 + ///converts the \c Value of a map to type \c T.
4.366 + ///Its \c Key is inherited from \c M.
4.367 + template <typename M, typename T>
4.368 + class ConvertMap : public MapBase<typename M::Key, T> {
4.369 + const M& m;
4.370 + public:
4.371 + typedef MapBase<typename M::Key, T> Parent;
4.372 + typedef typename Parent::Key Key;
4.373 + typedef typename Parent::Value Value;
4.374 +
4.375 + ///Constructor
4.376 +
4.377 + ///Constructor.
4.378 + ///\param _m is the underlying map.
4.379 + ConvertMap(const M &_m) : m(_m) {};
4.380 +
4.381 + /// \brief The subscript operator.
4.382 + ///
4.383 + /// The subscript operator.
4.384 + Value operator[](const Key& k) const {return m[k];}
4.385 + };
4.386 +
4.387 + ///Returns a \c ConvertMap class
4.388 +
4.389 + ///This function just returns a \c ConvertMap class.
4.390 + ///\relates ConvertMap
4.391 + template<typename T, typename M>
4.392 + inline ConvertMap<M, T> convertMap(const M &m) {
4.393 + return ConvertMap<M, T>(m);
4.394 + }
4.395 +
4.396 + ///Simple wrapping of a map
4.397 +
4.398 + ///This \c concepts::ReadMap "read only map" returns the simple
4.399 + ///wrapping of the given map. Sometimes the reference maps cannot be
4.400 + ///combined with simple read maps. This map adaptor wraps the given
4.401 + ///map to simple read map.
4.402 + ///
4.403 + ///\sa SimpleWriteMap
4.404 + ///
4.405 + /// \todo Revise the misleading name
4.406 + template<typename M>
4.407 + class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
4.408 + const M& m;
4.409 +
4.410 + public:
4.411 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.412 + typedef typename Parent::Key Key;
4.413 + typedef typename Parent::Value Value;
4.414 +
4.415 + ///Constructor
4.416 + SimpleMap(const M &_m) : m(_m) {};
4.417 + ///\e
4.418 + Value operator[](Key k) const {return m[k];}
4.419 + };
4.420 +
4.421 + ///Simple writable wrapping of the map
4.422 +
4.423 + ///This \c concepts::WriteMap "write map" returns the simple
4.424 + ///wrapping of the given map. Sometimes the reference maps cannot be
4.425 + ///combined with simple read-write maps. This map adaptor wraps the
4.426 + ///given map to simple read-write map.
4.427 + ///
4.428 + ///\sa SimpleMap
4.429 + ///
4.430 + /// \todo Revise the misleading name
4.431 + template<typename M>
4.432 + class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
4.433 + M& m;
4.434 +
4.435 + public:
4.436 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.437 + typedef typename Parent::Key Key;
4.438 + typedef typename Parent::Value Value;
4.439 +
4.440 + ///Constructor
4.441 + SimpleWriteMap(M &_m) : m(_m) {};
4.442 + ///\e
4.443 + Value operator[](Key k) const {return m[k];}
4.444 + ///\e
4.445 + void set(Key k, const Value& c) { m.set(k, c); }
4.446 + };
4.447 +
4.448 + ///Sum of two maps
4.449 +
4.450 + ///This \c concepts::ReadMap "read only map" returns the sum of the two
4.451 + ///given maps.
4.452 + ///Its \c Key and \c Value are inherited from \c M1.
4.453 + ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
4.454 + template<typename M1, typename M2>
4.455 + class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
4.456 + const M1& m1;
4.457 + const M2& m2;
4.458 +
4.459 + public:
4.460 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.461 + typedef typename Parent::Key Key;
4.462 + typedef typename Parent::Value Value;
4.463 +
4.464 + ///Constructor
4.465 + AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.466 + ///\e
4.467 + Value operator[](Key k) const {return m1[k]+m2[k];}
4.468 + };
4.469 +
4.470 + ///Returns an \c AddMap class
4.471 +
4.472 + ///This function just returns an \c AddMap class.
4.473 + ///\todo How to call these type of functions?
4.474 + ///
4.475 + ///\relates AddMap
4.476 + template<typename M1, typename M2>
4.477 + inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
4.478 + return AddMap<M1, M2>(m1,m2);
4.479 + }
4.480 +
4.481 + ///Shift a map with a constant.
4.482 +
4.483 + ///This \c concepts::ReadMap "read only map" returns the sum of the
4.484 + ///given map and a constant value.
4.485 + ///Its \c Key and \c Value are inherited from \c M.
4.486 + ///
4.487 + ///Actually,
4.488 + ///\code
4.489 + /// ShiftMap<X> sh(x,v);
4.490 + ///\endcode
4.491 + ///is equivalent to
4.492 + ///\code
4.493 + /// ConstMap<X::Key, X::Value> c_tmp(v);
4.494 + /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
4.495 + ///\endcode
4.496 + ///
4.497 + ///\sa ShiftWriteMap
4.498 + template<typename M, typename C = typename M::Value>
4.499 + class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
4.500 + const M& m;
4.501 + C v;
4.502 + public:
4.503 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.504 + typedef typename Parent::Key Key;
4.505 + typedef typename Parent::Value Value;
4.506 +
4.507 + ///Constructor
4.508 +
4.509 + ///Constructor.
4.510 + ///\param _m is the undelying map.
4.511 + ///\param _v is the shift value.
4.512 + ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
4.513 + ///\e
4.514 + Value operator[](Key k) const {return m[k] + v;}
4.515 + };
4.516 +
4.517 + ///Shift a map with a constant (ReadWrite version).
4.518 +
4.519 + ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
4.520 + ///given map and a constant value. It makes also possible to write the map.
4.521 + ///Its \c Key and \c Value are inherited from \c M.
4.522 + ///
4.523 + ///\sa ShiftMap
4.524 + template<typename M, typename C = typename M::Value>
4.525 + class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
4.526 + M& m;
4.527 + C v;
4.528 + public:
4.529 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.530 + typedef typename Parent::Key Key;
4.531 + typedef typename Parent::Value Value;
4.532 +
4.533 + ///Constructor
4.534 +
4.535 + ///Constructor.
4.536 + ///\param _m is the undelying map.
4.537 + ///\param _v is the shift value.
4.538 + ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
4.539 + /// \e
4.540 + Value operator[](Key k) const {return m[k] + v;}
4.541 + /// \e
4.542 + void set(Key k, const Value& c) { m.set(k, c - v); }
4.543 + };
4.544 +
4.545 + ///Returns a \c ShiftMap class
4.546 +
4.547 + ///This function just returns a \c ShiftMap class.
4.548 + ///\relates ShiftMap
4.549 + template<typename M, typename C>
4.550 + inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
4.551 + return ShiftMap<M, C>(m,v);
4.552 + }
4.553 +
4.554 + ///Returns a \c ShiftWriteMap class
4.555 +
4.556 + ///This function just returns a \c ShiftWriteMap class.
4.557 + ///\relates ShiftWriteMap
4.558 + template<typename M, typename C>
4.559 + inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
4.560 + return ShiftWriteMap<M, C>(m,v);
4.561 + }
4.562 +
4.563 + ///Difference of two maps
4.564 +
4.565 + ///This \c concepts::ReadMap "read only map" returns the difference
4.566 + ///of the values of the two given maps.
4.567 + ///Its \c Key and \c Value are inherited from \c M1.
4.568 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
4.569 + ///
4.570 + /// \todo Revise the misleading name
4.571 + template<typename M1, typename M2>
4.572 + class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
4.573 + const M1& m1;
4.574 + const M2& m2;
4.575 + public:
4.576 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.577 + typedef typename Parent::Key Key;
4.578 + typedef typename Parent::Value Value;
4.579 +
4.580 + ///Constructor
4.581 + SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.582 + /// \e
4.583 + Value operator[](Key k) const {return m1[k]-m2[k];}
4.584 + };
4.585 +
4.586 + ///Returns a \c SubMap class
4.587 +
4.588 + ///This function just returns a \c SubMap class.
4.589 + ///
4.590 + ///\relates SubMap
4.591 + template<typename M1, typename M2>
4.592 + inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
4.593 + return SubMap<M1, M2>(m1, m2);
4.594 + }
4.595 +
4.596 + ///Product of two maps
4.597 +
4.598 + ///This \c concepts::ReadMap "read only map" returns the product of the
4.599 + ///values of the two given maps.
4.600 + ///Its \c Key and \c Value are inherited from \c M1.
4.601 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
4.602 + template<typename M1, typename M2>
4.603 + class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
4.604 + const M1& m1;
4.605 + const M2& m2;
4.606 + public:
4.607 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.608 + typedef typename Parent::Key Key;
4.609 + typedef typename Parent::Value Value;
4.610 +
4.611 + ///Constructor
4.612 + MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.613 + /// \e
4.614 + Value operator[](Key k) const {return m1[k]*m2[k];}
4.615 + };
4.616 +
4.617 + ///Returns a \c MulMap class
4.618 +
4.619 + ///This function just returns a \c MulMap class.
4.620 + ///\relates MulMap
4.621 + template<typename M1, typename M2>
4.622 + inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
4.623 + return MulMap<M1, M2>(m1,m2);
4.624 + }
4.625 +
4.626 + ///Scales a map with a constant.
4.627 +
4.628 + ///This \c concepts::ReadMap "read only map" returns the value of the
4.629 + ///given map multiplied from the left side with a constant value.
4.630 + ///Its \c Key and \c Value are inherited from \c M.
4.631 + ///
4.632 + ///Actually,
4.633 + ///\code
4.634 + /// ScaleMap<X> sc(x,v);
4.635 + ///\endcode
4.636 + ///is equivalent to
4.637 + ///\code
4.638 + /// ConstMap<X::Key, X::Value> c_tmp(v);
4.639 + /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
4.640 + ///\endcode
4.641 + ///
4.642 + ///\sa ScaleWriteMap
4.643 + template<typename M, typename C = typename M::Value>
4.644 + class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
4.645 + const M& m;
4.646 + C v;
4.647 + public:
4.648 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.649 + typedef typename Parent::Key Key;
4.650 + typedef typename Parent::Value Value;
4.651 +
4.652 + ///Constructor
4.653 +
4.654 + ///Constructor.
4.655 + ///\param _m is the undelying map.
4.656 + ///\param _v is the scaling value.
4.657 + ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
4.658 + /// \e
4.659 + Value operator[](Key k) const {return v * m[k];}
4.660 + };
4.661 +
4.662 + ///Scales a map with a constant (ReadWrite version).
4.663 +
4.664 + ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
4.665 + ///given map multiplied from the left side with a constant value. It can
4.666 + ///also be used as write map if the \c / operator is defined between
4.667 + ///\c Value and \c C and the given multiplier is not zero.
4.668 + ///Its \c Key and \c Value are inherited from \c M.
4.669 + ///
4.670 + ///\sa ScaleMap
4.671 + template<typename M, typename C = typename M::Value>
4.672 + class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
4.673 + M& m;
4.674 + C v;
4.675 + public:
4.676 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.677 + typedef typename Parent::Key Key;
4.678 + typedef typename Parent::Value Value;
4.679 +
4.680 + ///Constructor
4.681 +
4.682 + ///Constructor.
4.683 + ///\param _m is the undelying map.
4.684 + ///\param _v is the scaling value.
4.685 + ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
4.686 + /// \e
4.687 + Value operator[](Key k) const {return v * m[k];}
4.688 + /// \e
4.689 + void set(Key k, const Value& c) { m.set(k, c / v);}
4.690 + };
4.691 +
4.692 + ///Returns a \c ScaleMap class
4.693 +
4.694 + ///This function just returns a \c ScaleMap class.
4.695 + ///\relates ScaleMap
4.696 + template<typename M, typename C>
4.697 + inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
4.698 + return ScaleMap<M, C>(m,v);
4.699 + }
4.700 +
4.701 + ///Returns a \c ScaleWriteMap class
4.702 +
4.703 + ///This function just returns a \c ScaleWriteMap class.
4.704 + ///\relates ScaleWriteMap
4.705 + template<typename M, typename C>
4.706 + inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
4.707 + return ScaleWriteMap<M, C>(m,v);
4.708 + }
4.709 +
4.710 + ///Quotient of two maps
4.711 +
4.712 + ///This \c concepts::ReadMap "read only map" returns the quotient of the
4.713 + ///values of the two given maps.
4.714 + ///Its \c Key and \c Value are inherited from \c M1.
4.715 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
4.716 + template<typename M1, typename M2>
4.717 + class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
4.718 + const M1& m1;
4.719 + const M2& m2;
4.720 + public:
4.721 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.722 + typedef typename Parent::Key Key;
4.723 + typedef typename Parent::Value Value;
4.724 +
4.725 + ///Constructor
4.726 + DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.727 + /// \e
4.728 + Value operator[](Key k) const {return m1[k]/m2[k];}
4.729 + };
4.730 +
4.731 + ///Returns a \c DivMap class
4.732 +
4.733 + ///This function just returns a \c DivMap class.
4.734 + ///\relates DivMap
4.735 + template<typename M1, typename M2>
4.736 + inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
4.737 + return DivMap<M1, M2>(m1,m2);
4.738 + }
4.739 +
4.740 + ///Composition of two maps
4.741 +
4.742 + ///This \c concepts::ReadMap "read only map" returns the composition of
4.743 + ///two given maps.
4.744 + ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
4.745 + ///then for
4.746 + ///\code
4.747 + /// ComposeMap<M1, M2> cm(m1,m2);
4.748 + ///\endcode
4.749 + /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
4.750 + ///
4.751 + ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
4.752 + ///\c M2::Value must be convertible to \c M1::Key.
4.753 + ///
4.754 + ///\sa CombineMap
4.755 + ///
4.756 + ///\todo Check the requirements.
4.757 + template <typename M1, typename M2>
4.758 + class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
4.759 + const M1& m1;
4.760 + const M2& m2;
4.761 + public:
4.762 + typedef MapBase<typename M2::Key, typename M1::Value> Parent;
4.763 + typedef typename Parent::Key Key;
4.764 + typedef typename Parent::Value Value;
4.765 +
4.766 + ///Constructor
4.767 + ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.768 +
4.769 + /// \e
4.770 +
4.771 +
4.772 + /// \todo Use the MapTraits once it is ported.
4.773 + ///
4.774 +
4.775 + //typename MapTraits<M1>::ConstReturnValue
4.776 + typename M1::Value
4.777 + operator[](Key k) const {return m1[m2[k]];}
4.778 + };
4.779 +
4.780 + ///Returns a \c ComposeMap class
4.781 +
4.782 + ///This function just returns a \c ComposeMap class.
4.783 + ///\relates ComposeMap
4.784 + template <typename M1, typename M2>
4.785 + inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
4.786 + return ComposeMap<M1, M2>(m1,m2);
4.787 + }
4.788 +
4.789 + ///Combine of two maps using an STL (binary) functor.
4.790 +
4.791 + ///Combine of two maps using an STL (binary) functor.
4.792 + ///
4.793 + ///This \c concepts::ReadMap "read only map" takes two maps and a
4.794 + ///binary functor and returns the composition of the two
4.795 + ///given maps unsing the functor.
4.796 + ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
4.797 + ///and \c f is of \c F, then for
4.798 + ///\code
4.799 + /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
4.800 + ///\endcode
4.801 + /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
4.802 + ///
4.803 + ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
4.804 + ///\c M2::Value and \c M1::Value must be convertible to the corresponding
4.805 + ///input parameter of \c F and the return type of \c F must be convertible
4.806 + ///to \c V.
4.807 + ///
4.808 + ///\sa ComposeMap
4.809 + ///
4.810 + ///\todo Check the requirements.
4.811 + template<typename M1, typename M2, typename F,
4.812 + typename V = typename F::result_type>
4.813 + class CombineMap : public MapBase<typename M1::Key, V> {
4.814 + const M1& m1;
4.815 + const M2& m2;
4.816 + F f;
4.817 + public:
4.818 + typedef MapBase<typename M1::Key, V> Parent;
4.819 + typedef typename Parent::Key Key;
4.820 + typedef typename Parent::Value Value;
4.821 +
4.822 + ///Constructor
4.823 + CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
4.824 + : m1(_m1), m2(_m2), f(_f) {};
4.825 + /// \e
4.826 + Value operator[](Key k) const {return f(m1[k],m2[k]);}
4.827 + };
4.828 +
4.829 + ///Returns a \c CombineMap class
4.830 +
4.831 + ///This function just returns a \c CombineMap class.
4.832 + ///
4.833 + ///For example if \c m1 and \c m2 are both \c double valued maps, then
4.834 + ///\code
4.835 + ///combineMap<double>(m1,m2,std::plus<double>())
4.836 + ///\endcode
4.837 + ///is equivalent to
4.838 + ///\code
4.839 + ///addMap(m1,m2)
4.840 + ///\endcode
4.841 + ///
4.842 + ///This function is specialized for adaptable binary function
4.843 + ///classes and C++ functions.
4.844 + ///
4.845 + ///\relates CombineMap
4.846 + template<typename M1, typename M2, typename F, typename V>
4.847 + inline CombineMap<M1, M2, F, V>
4.848 + combineMap(const M1& m1,const M2& m2, const F& f) {
4.849 + return CombineMap<M1, M2, F, V>(m1,m2,f);
4.850 + }
4.851 +
4.852 + template<typename M1, typename M2, typename F>
4.853 + inline CombineMap<M1, M2, F, typename F::result_type>
4.854 + combineMap(const M1& m1, const M2& m2, const F& f) {
4.855 + return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
4.856 + }
4.857 +
4.858 + template<typename M1, typename M2, typename K1, typename K2, typename V>
4.859 + inline CombineMap<M1, M2, V (*)(K1, K2), V>
4.860 + combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
4.861 + return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
4.862 + }
4.863 +
4.864 + ///Negative value of a map
4.865 +
4.866 + ///This \c concepts::ReadMap "read only map" returns the negative
4.867 + ///value of the value returned by the given map.
4.868 + ///Its \c Key and \c Value are inherited from \c M.
4.869 + ///The unary \c - operator must be defined for \c Value, of course.
4.870 + ///
4.871 + ///\sa NegWriteMap
4.872 + template<typename M>
4.873 + class NegMap : public MapBase<typename M::Key, typename M::Value> {
4.874 + const M& m;
4.875 + public:
4.876 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.877 + typedef typename Parent::Key Key;
4.878 + typedef typename Parent::Value Value;
4.879 +
4.880 + ///Constructor
4.881 + NegMap(const M &_m) : m(_m) {};
4.882 + /// \e
4.883 + Value operator[](Key k) const {return -m[k];}
4.884 + };
4.885 +
4.886 + ///Negative value of a map (ReadWrite version)
4.887 +
4.888 + ///This \c concepts::ReadWriteMap "read-write map" returns the negative
4.889 + ///value of the value returned by the given map.
4.890 + ///Its \c Key and \c Value are inherited from \c M.
4.891 + ///The unary \c - operator must be defined for \c Value, of course.
4.892 + ///
4.893 + /// \sa NegMap
4.894 + template<typename M>
4.895 + class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
4.896 + M& m;
4.897 + public:
4.898 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.899 + typedef typename Parent::Key Key;
4.900 + typedef typename Parent::Value Value;
4.901 +
4.902 + ///Constructor
4.903 + NegWriteMap(M &_m) : m(_m) {};
4.904 + /// \e
4.905 + Value operator[](Key k) const {return -m[k];}
4.906 + /// \e
4.907 + void set(Key k, const Value& v) { m.set(k, -v); }
4.908 + };
4.909 +
4.910 + ///Returns a \c NegMap class
4.911 +
4.912 + ///This function just returns a \c NegMap class.
4.913 + ///\relates NegMap
4.914 + template <typename M>
4.915 + inline NegMap<M> negMap(const M &m) {
4.916 + return NegMap<M>(m);
4.917 + }
4.918 +
4.919 + ///Returns a \c NegWriteMap class
4.920 +
4.921 + ///This function just returns a \c NegWriteMap class.
4.922 + ///\relates NegWriteMap
4.923 + template <typename M>
4.924 + inline NegWriteMap<M> negMap(M &m) {
4.925 + return NegWriteMap<M>(m);
4.926 + }
4.927 +
4.928 + ///Absolute value of a map
4.929 +
4.930 + ///This \c concepts::ReadMap "read only map" returns the absolute value
4.931 + ///of the value returned by the given map.
4.932 + ///Its \c Key and \c Value are inherited from \c M.
4.933 + ///\c Value must be comparable to \c 0 and the unary \c -
4.934 + ///operator must be defined for it, of course.
4.935 + template<typename M>
4.936 + class AbsMap : public MapBase<typename M::Key, typename M::Value> {
4.937 + const M& m;
4.938 + public:
4.939 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.940 + typedef typename Parent::Key Key;
4.941 + typedef typename Parent::Value Value;
4.942 +
4.943 + ///Constructor
4.944 + AbsMap(const M &_m) : m(_m) {};
4.945 + /// \e
4.946 + Value operator[](Key k) const {
4.947 + Value tmp = m[k];
4.948 + return tmp >= 0 ? tmp : -tmp;
4.949 + }
4.950 +
4.951 + };
4.952 +
4.953 + ///Returns an \c AbsMap class
4.954 +
4.955 + ///This function just returns an \c AbsMap class.
4.956 + ///\relates AbsMap
4.957 + template<typename M>
4.958 + inline AbsMap<M> absMap(const M &m) {
4.959 + return AbsMap<M>(m);
4.960 + }
4.961 +
4.962 + ///Converts an STL style functor to a map
4.963 +
4.964 + ///This \c concepts::ReadMap "read only map" returns the value
4.965 + ///of a given functor.
4.966 + ///
4.967 + ///Template parameters \c K and \c V will become its
4.968 + ///\c Key and \c Value. They must be given explicitly
4.969 + ///because a functor does not provide such typedefs.
4.970 + ///
4.971 + ///Parameter \c F is the type of the used functor.
4.972 + ///
4.973 + ///\sa MapFunctor
4.974 + template<typename F,
4.975 + typename K = typename F::argument_type,
4.976 + typename V = typename F::result_type>
4.977 + class FunctorMap : public MapBase<K, V> {
4.978 + F f;
4.979 + public:
4.980 + typedef MapBase<K, V> Parent;
4.981 + typedef typename Parent::Key Key;
4.982 + typedef typename Parent::Value Value;
4.983 +
4.984 + ///Constructor
4.985 + FunctorMap(const F &_f = F()) : f(_f) {}
4.986 + /// \e
4.987 + Value operator[](Key k) const { return f(k);}
4.988 + };
4.989 +
4.990 + ///Returns a \c FunctorMap class
4.991 +
4.992 + ///This function just returns a \c FunctorMap class.
4.993 + ///
4.994 + ///It is specialized for adaptable function classes and
4.995 + ///C++ functions.
4.996 + ///\relates FunctorMap
4.997 + template<typename K, typename V, typename F> inline
4.998 + FunctorMap<F, K, V> functorMap(const F &f) {
4.999 + return FunctorMap<F, K, V>(f);
4.1000 + }
4.1001 +
4.1002 + template <typename F> inline
4.1003 + FunctorMap<F, typename F::argument_type, typename F::result_type>
4.1004 + functorMap(const F &f) {
4.1005 + return FunctorMap<F, typename F::argument_type,
4.1006 + typename F::result_type>(f);
4.1007 + }
4.1008 +
4.1009 + template <typename K, typename V> inline
4.1010 + FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
4.1011 + return FunctorMap<V (*)(K), K, V>(f);
4.1012 + }
4.1013 +
4.1014 +
4.1015 + ///Converts a map to an STL style (unary) functor
4.1016 +
4.1017 + ///This class Converts a map to an STL style (unary) functor.
4.1018 + ///that is it provides an <tt>operator()</tt> to read its values.
4.1019 + ///
4.1020 + ///For the sake of convenience it also works as
4.1021 + ///a ususal \c concepts::ReadMap "readable map",
4.1022 + ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
4.1023 + ///
4.1024 + ///\sa FunctorMap
4.1025 + template <typename M>
4.1026 + class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
4.1027 + const M& m;
4.1028 + public:
4.1029 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.1030 + typedef typename Parent::Key Key;
4.1031 + typedef typename Parent::Value Value;
4.1032 +
4.1033 + typedef typename M::Key argument_type;
4.1034 + typedef typename M::Value result_type;
4.1035 +
4.1036 + ///Constructor
4.1037 + MapFunctor(const M &_m) : m(_m) {};
4.1038 + ///\e
4.1039 + Value operator()(Key k) const {return m[k];}
4.1040 + ///\e
4.1041 + Value operator[](Key k) const {return m[k];}
4.1042 + };
4.1043 +
4.1044 + ///Returns a \c MapFunctor class
4.1045 +
4.1046 + ///This function just returns a \c MapFunctor class.
4.1047 + ///\relates MapFunctor
4.1048 + template<typename M>
4.1049 + inline MapFunctor<M> mapFunctor(const M &m) {
4.1050 + return MapFunctor<M>(m);
4.1051 + }
4.1052 +
4.1053 + ///Applies all map setting operations to two maps
4.1054 +
4.1055 + ///This map has two \c concepts::ReadMap "readable map"
4.1056 + ///parameters and each read request will be passed just to the
4.1057 + ///first map. This class is the just readable map type of the ForkWriteMap.
4.1058 + ///
4.1059 + ///The \c Key and \c Value are inherited from \c M1.
4.1060 + ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
4.1061 + ///
4.1062 + ///\sa ForkWriteMap
4.1063 + ///
4.1064 + /// \todo Why is it needed?
4.1065 + template<typename M1, typename M2>
4.1066 + class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
4.1067 + const M1& m1;
4.1068 + const M2& m2;
4.1069 + public:
4.1070 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.1071 + typedef typename Parent::Key Key;
4.1072 + typedef typename Parent::Value Value;
4.1073 +
4.1074 + ///Constructor
4.1075 + ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
4.1076 + /// \e
4.1077 + Value operator[](Key k) const {return m1[k];}
4.1078 + };
4.1079 +
4.1080 +
4.1081 + ///Applies all map setting operations to two maps
4.1082 +
4.1083 + ///This map has two \c concepts::WriteMap "writable map"
4.1084 + ///parameters and each write request will be passed to both of them.
4.1085 + ///If \c M1 is also \c concepts::ReadMap "readable",
4.1086 + ///then the read operations will return the
4.1087 + ///corresponding values of \c M1.
4.1088 + ///
4.1089 + ///The \c Key and \c Value are inherited from \c M1.
4.1090 + ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
4.1091 + ///
4.1092 + ///\sa ForkMap
4.1093 + template<typename M1, typename M2>
4.1094 + class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
4.1095 + M1& m1;
4.1096 + M2& m2;
4.1097 + public:
4.1098 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.1099 + typedef typename Parent::Key Key;
4.1100 + typedef typename Parent::Value Value;
4.1101 +
4.1102 + ///Constructor
4.1103 + ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
4.1104 + ///\e
4.1105 + Value operator[](Key k) const {return m1[k];}
4.1106 + ///\e
4.1107 + void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
4.1108 + };
4.1109 +
4.1110 + ///Returns a \c ForkMap class
4.1111 +
4.1112 + ///This function just returns a \c ForkMap class.
4.1113 + ///\relates ForkMap
4.1114 + template <typename M1, typename M2>
4.1115 + inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
4.1116 + return ForkMap<M1, M2>(m1,m2);
4.1117 + }
4.1118 +
4.1119 + ///Returns a \c ForkWriteMap class
4.1120 +
4.1121 + ///This function just returns a \c ForkWriteMap class.
4.1122 + ///\relates ForkWriteMap
4.1123 + template <typename M1, typename M2>
4.1124 + inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
4.1125 + return ForkWriteMap<M1, M2>(m1,m2);
4.1126 + }
4.1127 +
4.1128 +
4.1129 +
4.1130 + /* ************* BOOL MAPS ******************* */
4.1131 +
4.1132 + ///Logical 'not' of a map
4.1133 +
4.1134 + ///This bool \c concepts::ReadMap "read only map" returns the
4.1135 + ///logical negation of the value returned by the given map.
4.1136 + ///Its \c Key is inherited from \c M, its Value is \c bool.
4.1137 + ///
4.1138 + ///\sa NotWriteMap
4.1139 + template <typename M>
4.1140 + class NotMap : public MapBase<typename M::Key, bool> {
4.1141 + const M& m;
4.1142 + public:
4.1143 + typedef MapBase<typename M::Key, bool> Parent;
4.1144 + typedef typename Parent::Key Key;
4.1145 + typedef typename Parent::Value Value;
4.1146 +
4.1147 + /// Constructor
4.1148 + NotMap(const M &_m) : m(_m) {};
4.1149 + ///\e
4.1150 + Value operator[](Key k) const {return !m[k];}
4.1151 + };
4.1152 +
4.1153 + ///Logical 'not' of a map (ReadWrie version)
4.1154 +
4.1155 + ///This bool \c concepts::ReadWriteMap "read-write map" returns the
4.1156 + ///logical negation of the value returned by the given map. When it is set,
4.1157 + ///the opposite value is set to the original map.
4.1158 + ///Its \c Key is inherited from \c M, its Value is \c bool.
4.1159 + ///
4.1160 + ///\sa NotMap
4.1161 + template <typename M>
4.1162 + class NotWriteMap : public MapBase<typename M::Key, bool> {
4.1163 + M& m;
4.1164 + public:
4.1165 + typedef MapBase<typename M::Key, bool> Parent;
4.1166 + typedef typename Parent::Key Key;
4.1167 + typedef typename Parent::Value Value;
4.1168 +
4.1169 + /// Constructor
4.1170 + NotWriteMap(M &_m) : m(_m) {};
4.1171 + ///\e
4.1172 + Value operator[](Key k) const {return !m[k];}
4.1173 + ///\e
4.1174 + void set(Key k, bool v) { m.set(k, !v); }
4.1175 + };
4.1176 +
4.1177 + ///Returns a \c NotMap class
4.1178 +
4.1179 + ///This function just returns a \c NotMap class.
4.1180 + ///\relates NotMap
4.1181 + template <typename M>
4.1182 + inline NotMap<M> notMap(const M &m) {
4.1183 + return NotMap<M>(m);
4.1184 + }
4.1185 +
4.1186 + ///Returns a \c NotWriteMap class
4.1187 +
4.1188 + ///This function just returns a \c NotWriteMap class.
4.1189 + ///\relates NotWriteMap
4.1190 + template <typename M>
4.1191 + inline NotWriteMap<M> notMap(M &m) {
4.1192 + return NotWriteMap<M>(m);
4.1193 + }
4.1194 +
4.1195 + namespace _maps_bits {
4.1196 +
4.1197 + template <typename Value>
4.1198 + struct Identity {
4.1199 + typedef Value argument_type;
4.1200 + typedef Value result_type;
4.1201 + Value operator()(const Value& val) const {
4.1202 + return val;
4.1203 + }
4.1204 + };
4.1205 +
4.1206 + template <typename _Iterator, typename Enable = void>
4.1207 + struct IteratorTraits {
4.1208 + typedef typename std::iterator_traits<_Iterator>::value_type Value;
4.1209 + };
4.1210 +
4.1211 + template <typename _Iterator>
4.1212 + struct IteratorTraits<_Iterator,
4.1213 + typename exists<typename _Iterator::container_type>::type>
4.1214 + {
4.1215 + typedef typename _Iterator::container_type::value_type Value;
4.1216 + };
4.1217 +
4.1218 + }
4.1219 +
4.1220 +
4.1221 + /// \brief Writable bool map for logging each \c true assigned element
4.1222 + ///
4.1223 + /// Writable bool map for logging each \c true assigned element, i.e it
4.1224 + /// copies all the keys set to \c true to the given iterator.
4.1225 + ///
4.1226 + /// \note The container of the iterator should contain space
4.1227 + /// for each element.
4.1228 + ///
4.1229 + /// The following example shows how you can write the edges found by the Prim
4.1230 + /// algorithm directly
4.1231 + /// to the standard output.
4.1232 + ///\code
4.1233 + /// typedef IdMap<Graph, Edge> EdgeIdMap;
4.1234 + /// EdgeIdMap edgeId(graph);
4.1235 + ///
4.1236 + /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
4.1237 + /// EdgeIdFunctor edgeIdFunctor(edgeId);
4.1238 + ///
4.1239 + /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
4.1240 + /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
4.1241 + ///
4.1242 + /// prim(graph, cost, writerMap);
4.1243 + ///\endcode
4.1244 + ///
4.1245 + ///\sa BackInserterBoolMap
4.1246 + ///
4.1247 + ///\todo Revise the name of this class and the related ones.
4.1248 + template <typename _Iterator,
4.1249 + typename _Functor =
4.1250 + _maps_bits::Identity<typename _maps_bits::
4.1251 + IteratorTraits<_Iterator>::Value> >
4.1252 + class StoreBoolMap {
4.1253 + public:
4.1254 + typedef _Iterator Iterator;
4.1255 +
4.1256 + typedef typename _Functor::argument_type Key;
4.1257 + typedef bool Value;
4.1258 +
4.1259 + typedef _Functor Functor;
4.1260 +
4.1261 + /// Constructor
4.1262 + StoreBoolMap(Iterator it, const Functor& functor = Functor())
4.1263 + : _begin(it), _end(it), _functor(functor) {}
4.1264 +
4.1265 + /// Gives back the given iterator set for the first key
4.1266 + Iterator begin() const {
4.1267 + return _begin;
4.1268 + }
4.1269 +
4.1270 + /// Gives back the the 'after the last' iterator
4.1271 + Iterator end() const {
4.1272 + return _end;
4.1273 + }
4.1274 +
4.1275 + /// The \c set function of the map
4.1276 + void set(const Key& key, Value value) const {
4.1277 + if (value) {
4.1278 + *_end++ = _functor(key);
4.1279 + }
4.1280 + }
4.1281 +
4.1282 + private:
4.1283 + Iterator _begin;
4.1284 + mutable Iterator _end;
4.1285 + Functor _functor;
4.1286 + };
4.1287 +
4.1288 + /// \brief Writable bool map for logging each \c true assigned element in
4.1289 + /// a back insertable container.
4.1290 + ///
4.1291 + /// Writable bool map for logging each \c true assigned element by pushing
4.1292 + /// them into a back insertable container.
4.1293 + /// It can be used to retrieve the items into a standard
4.1294 + /// container. The next example shows how you can store the
4.1295 + /// edges found by the Prim algorithm in a vector.
4.1296 + ///
4.1297 + ///\code
4.1298 + /// vector<Edge> span_tree_edges;
4.1299 + /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
4.1300 + /// prim(graph, cost, inserter_map);
4.1301 + ///\endcode
4.1302 + ///
4.1303 + ///\sa StoreBoolMap
4.1304 + ///\sa FrontInserterBoolMap
4.1305 + ///\sa InserterBoolMap
4.1306 + template <typename Container,
4.1307 + typename Functor =
4.1308 + _maps_bits::Identity<typename Container::value_type> >
4.1309 + class BackInserterBoolMap {
4.1310 + public:
4.1311 + typedef typename Container::value_type Key;
4.1312 + typedef bool Value;
4.1313 +
4.1314 + /// Constructor
4.1315 + BackInserterBoolMap(Container& _container,
4.1316 + const Functor& _functor = Functor())
4.1317 + : container(_container), functor(_functor) {}
4.1318 +
4.1319 + /// The \c set function of the map
4.1320 + void set(const Key& key, Value value) {
4.1321 + if (value) {
4.1322 + container.push_back(functor(key));
4.1323 + }
4.1324 + }
4.1325 +
4.1326 + private:
4.1327 + Container& container;
4.1328 + Functor functor;
4.1329 + };
4.1330 +
4.1331 + /// \brief Writable bool map for logging each \c true assigned element in
4.1332 + /// a front insertable container.
4.1333 + ///
4.1334 + /// Writable bool map for logging each \c true assigned element by pushing
4.1335 + /// them into a front insertable container.
4.1336 + /// It can be used to retrieve the items into a standard
4.1337 + /// container. For example see \ref BackInserterBoolMap.
4.1338 + ///
4.1339 + ///\sa BackInserterBoolMap
4.1340 + ///\sa InserterBoolMap
4.1341 + template <typename Container,
4.1342 + typename Functor =
4.1343 + _maps_bits::Identity<typename Container::value_type> >
4.1344 + class FrontInserterBoolMap {
4.1345 + public:
4.1346 + typedef typename Container::value_type Key;
4.1347 + typedef bool Value;
4.1348 +
4.1349 + /// Constructor
4.1350 + FrontInserterBoolMap(Container& _container,
4.1351 + const Functor& _functor = Functor())
4.1352 + : container(_container), functor(_functor) {}
4.1353 +
4.1354 + /// The \c set function of the map
4.1355 + void set(const Key& key, Value value) {
4.1356 + if (value) {
4.1357 + container.push_front(functor(key));
4.1358 + }
4.1359 + }
4.1360 +
4.1361 + private:
4.1362 + Container& container;
4.1363 + Functor functor;
4.1364 + };
4.1365 +
4.1366 + /// \brief Writable bool map for storing each \c true assigned element in
4.1367 + /// an insertable container.
4.1368 + ///
4.1369 + /// Writable bool map for storing each \c true assigned element in an
4.1370 + /// insertable container. It will insert all the keys set to \c true into
4.1371 + /// the container.
4.1372 + ///
4.1373 + /// For example, if you want to store the cut arcs of the strongly
4.1374 + /// connected components in a set you can use the next code:
4.1375 + ///
4.1376 + ///\code
4.1377 + /// set<Arc> cut_arcs;
4.1378 + /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
4.1379 + /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
4.1380 + ///\endcode
4.1381 + ///
4.1382 + ///\sa BackInserterBoolMap
4.1383 + ///\sa FrontInserterBoolMap
4.1384 + template <typename Container,
4.1385 + typename Functor =
4.1386 + _maps_bits::Identity<typename Container::value_type> >
4.1387 + class InserterBoolMap {
4.1388 + public:
4.1389 + typedef typename Container::value_type Key;
4.1390 + typedef bool Value;
4.1391 +
4.1392 + /// Constructor with specified iterator
4.1393 +
4.1394 + /// Constructor with specified iterator.
4.1395 + /// \param _container The container for storing the elements.
4.1396 + /// \param _it The elements will be inserted before this iterator.
4.1397 + /// \param _functor The functor that is used when an element is stored.
4.1398 + InserterBoolMap(Container& _container, typename Container::iterator _it,
4.1399 + const Functor& _functor = Functor())
4.1400 + : container(_container), it(_it), functor(_functor) {}
4.1401 +
4.1402 + /// Constructor
4.1403 +
4.1404 + /// Constructor without specified iterator.
4.1405 + /// The elements will be inserted before <tt>_container.end()</tt>.
4.1406 + /// \param _container The container for storing the elements.
4.1407 + /// \param _functor The functor that is used when an element is stored.
4.1408 + InserterBoolMap(Container& _container, const Functor& _functor = Functor())
4.1409 + : container(_container), it(_container.end()), functor(_functor) {}
4.1410 +
4.1411 + /// The \c set function of the map
4.1412 + void set(const Key& key, Value value) {
4.1413 + if (value) {
4.1414 + it = container.insert(it, functor(key));
4.1415 + ++it;
4.1416 + }
4.1417 + }
4.1418 +
4.1419 + private:
4.1420 + Container& container;
4.1421 + typename Container::iterator it;
4.1422 + Functor functor;
4.1423 + };
4.1424 +
4.1425 + /// \brief Writable bool map for filling each \c true assigned element with a
4.1426 + /// given value.
4.1427 + ///
4.1428 + /// Writable bool map for filling each \c true assigned element with a
4.1429 + /// given value. The value can set the container.
4.1430 + ///
4.1431 + /// The following code finds the connected components of a graph
4.1432 + /// and stores it in the \c comp map:
4.1433 + ///\code
4.1434 + /// typedef Graph::NodeMap<int> ComponentMap;
4.1435 + /// ComponentMap comp(graph);
4.1436 + /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
4.1437 + /// ComponentFillerMap filler(comp, 0);
4.1438 + ///
4.1439 + /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
4.1440 + /// dfs.processedMap(filler);
4.1441 + /// dfs.init();
4.1442 + /// for (NodeIt it(graph); it != INVALID; ++it) {
4.1443 + /// if (!dfs.reached(it)) {
4.1444 + /// dfs.addSource(it);
4.1445 + /// dfs.start();
4.1446 + /// ++filler.fillValue();
4.1447 + /// }
4.1448 + /// }
4.1449 + ///\endcode
4.1450 + template <typename Map>
4.1451 + class FillBoolMap {
4.1452 + public:
4.1453 + typedef typename Map::Key Key;
4.1454 + typedef bool Value;
4.1455 +
4.1456 + /// Constructor
4.1457 + FillBoolMap(Map& _map, const typename Map::Value& _fill)
4.1458 + : map(_map), fill(_fill) {}
4.1459 +
4.1460 + /// Constructor
4.1461 + FillBoolMap(Map& _map)
4.1462 + : map(_map), fill() {}
4.1463 +
4.1464 + /// Gives back the current fill value
4.1465 + const typename Map::Value& fillValue() const {
4.1466 + return fill;
4.1467 + }
4.1468 +
4.1469 + /// Gives back the current fill value
4.1470 + typename Map::Value& fillValue() {
4.1471 + return fill;
4.1472 + }
4.1473 +
4.1474 + /// Sets the current fill value
4.1475 + void fillValue(const typename Map::Value& _fill) {
4.1476 + fill = _fill;
4.1477 + }
4.1478 +
4.1479 + /// The \c set function of the map
4.1480 + void set(const Key& key, Value value) {
4.1481 + if (value) {
4.1482 + map.set(key, fill);
4.1483 + }
4.1484 + }
4.1485 +
4.1486 + private:
4.1487 + Map& map;
4.1488 + typename Map::Value fill;
4.1489 + };
4.1490 +
4.1491 +
4.1492 + /// \brief Writable bool map for storing the sequence number of
4.1493 + /// \c true assignments.
4.1494 + ///
4.1495 + /// Writable bool map that stores for each \c true assigned elements
4.1496 + /// the sequence number of this setting.
4.1497 + /// It makes it easy to calculate the leaving
4.1498 + /// order of the nodes in the \c Dfs algorithm.
4.1499 + ///
4.1500 + ///\code
4.1501 + /// typedef Digraph::NodeMap<int> OrderMap;
4.1502 + /// OrderMap order(digraph);
4.1503 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
4.1504 + /// OrderSetterMap setter(order);
4.1505 + /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
4.1506 + /// dfs.processedMap(setter);
4.1507 + /// dfs.init();
4.1508 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
4.1509 + /// if (!dfs.reached(it)) {
4.1510 + /// dfs.addSource(it);
4.1511 + /// dfs.start();
4.1512 + /// }
4.1513 + /// }
4.1514 + ///\endcode
4.1515 + ///
4.1516 + /// The storing of the discovering order is more difficult because the
4.1517 + /// ReachedMap should be readable in the dfs algorithm but the setting
4.1518 + /// order map is not readable. Thus we must use the fork map:
4.1519 + ///
4.1520 + ///\code
4.1521 + /// typedef Digraph::NodeMap<int> OrderMap;
4.1522 + /// OrderMap order(digraph);
4.1523 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
4.1524 + /// OrderSetterMap setter(order);
4.1525 + /// typedef Digraph::NodeMap<bool> StoreMap;
4.1526 + /// StoreMap store(digraph);
4.1527 + ///
4.1528 + /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
4.1529 + /// ReachedMap reached(store, setter);
4.1530 + ///
4.1531 + /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
4.1532 + /// dfs.reachedMap(reached);
4.1533 + /// dfs.init();
4.1534 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
4.1535 + /// if (!dfs.reached(it)) {
4.1536 + /// dfs.addSource(it);
4.1537 + /// dfs.start();
4.1538 + /// }
4.1539 + /// }
4.1540 + ///\endcode
4.1541 + template <typename Map>
4.1542 + class SettingOrderBoolMap {
4.1543 + public:
4.1544 + typedef typename Map::Key Key;
4.1545 + typedef bool Value;
4.1546 +
4.1547 + /// Constructor
4.1548 + SettingOrderBoolMap(Map& _map)
4.1549 + : map(_map), counter(0) {}
4.1550 +
4.1551 + /// Number of set operations.
4.1552 + int num() const {
4.1553 + return counter;
4.1554 + }
4.1555 +
4.1556 + /// Setter function of the map
4.1557 + void set(const Key& key, Value value) {
4.1558 + if (value) {
4.1559 + map.set(key, counter++);
4.1560 + }
4.1561 + }
4.1562 +
4.1563 + private:
4.1564 + Map& map;
4.1565 + int counter;
4.1566 + };
4.1567 +
4.1568 + /// @}
4.1569 +}
4.1570 +
4.1571 +#endif // LEMON_MAPS_H
5.1 --- a/test/Makefile.am Thu Jan 03 14:58:42 2008 +0100
5.2 +++ b/test/Makefile.am Wed Feb 06 10:52:58 2008 +0000
5.3 @@ -6,6 +6,7 @@
5.4
5.5 check_PROGRAMS += \
5.6 test/dim_test \
5.7 + test/maps_test \
5.8 test/random_test \
5.9 test/test_tools_fail \
5.10 test/test_tools_pass
5.11 @@ -14,6 +15,7 @@
5.12 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
5.13
5.14 test_dim_test_SOURCES = test/dim_test.cc
5.15 +test_maps_test_SOURCES = test/maps_test.cc
5.16 test_random_test_SOURCES = test/random_test.cc
5.17 test_test_tools_fail_SOURCES = test/test_tools_fail.cc
5.18 test_test_tools_pass_SOURCES = test/test_tools_pass.cc
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/test/maps_test.cc Wed Feb 06 10:52:58 2008 +0000
6.3 @@ -0,0 +1,108 @@
6.4 +/* -*- C++ -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library
6.7 + *
6.8 + * Copyright (C) 2003-2007
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +#include <deque>
6.23 +#include <set>
6.24 +
6.25 +#include <lemon/concept_check.h>
6.26 +#include <lemon/concepts/maps.h>
6.27 +#include <lemon/maps.h>
6.28 +
6.29 +#include "test_tools.h"
6.30 +
6.31 +using namespace lemon;
6.32 +using namespace lemon::concepts;
6.33 +
6.34 +struct A {};
6.35 +inline bool operator<(A, A) { return true; }
6.36 +struct B {};
6.37 +
6.38 +class F {
6.39 +public:
6.40 + typedef A argument_type;
6.41 + typedef B result_type;
6.42 +
6.43 + B operator()(const A &) const {return B();}
6.44 +};
6.45 +
6.46 +int func(A) {return 3;}
6.47 +
6.48 +int binc(int, B) {return 4;}
6.49 +
6.50 +typedef ReadMap<A,double> DoubleMap;
6.51 +typedef ReadWriteMap<A, double> WriteDoubleMap;
6.52 +
6.53 +typedef ReadMap<A,bool> BoolMap;
6.54 +typedef ReadWriteMap<A, bool> BoolWriteMap;
6.55 +
6.56 +int main()
6.57 +{ // checking graph components
6.58 +
6.59 + checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
6.60 + checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
6.61 + checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
6.62 + checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
6.63 +
6.64 + checkConcept<ReadMap<A,double>, AddMap<DoubleMap,DoubleMap> >();
6.65 + checkConcept<ReadMap<A,double>, SubMap<DoubleMap,DoubleMap> >();
6.66 + checkConcept<ReadMap<A,double>, MulMap<DoubleMap,DoubleMap> >();
6.67 + checkConcept<ReadMap<A,double>, DivMap<DoubleMap,DoubleMap> >();
6.68 + checkConcept<ReadMap<A,double>, NegMap<DoubleMap> >();
6.69 + checkConcept<ReadWriteMap<A,double>, NegWriteMap<WriteDoubleMap> >();
6.70 + checkConcept<ReadMap<A,double>, AbsMap<DoubleMap> >();
6.71 + checkConcept<ReadMap<A,double>, ShiftMap<DoubleMap> >();
6.72 + checkConcept<ReadWriteMap<A,double>, ShiftWriteMap<WriteDoubleMap> >();
6.73 + checkConcept<ReadMap<A,double>, ScaleMap<DoubleMap> >();
6.74 + checkConcept<ReadWriteMap<A,double>, ScaleWriteMap<WriteDoubleMap> >();
6.75 + checkConcept<ReadMap<A,double>, ForkMap<DoubleMap, DoubleMap> >();
6.76 + checkConcept<ReadWriteMap<A,double>,
6.77 + ForkWriteMap<WriteDoubleMap, WriteDoubleMap> >();
6.78 +
6.79 + checkConcept<ReadMap<B,double>, ComposeMap<DoubleMap,ReadMap<B,A> > >();
6.80 +
6.81 + checkConcept<ReadMap<A,B>, FunctorMap<F, A, B> >();
6.82 +
6.83 + checkConcept<ReadMap<A, bool>, NotMap<BoolMap> >();
6.84 + checkConcept<ReadWriteMap<A, bool>, NotWriteMap<BoolWriteMap> >();
6.85 +
6.86 + checkConcept<WriteMap<A, bool>, StoreBoolMap<A*> >();
6.87 + checkConcept<WriteMap<A, bool>, BackInserterBoolMap<std::deque<A> > >();
6.88 + checkConcept<WriteMap<A, bool>, FrontInserterBoolMap<std::deque<A> > >();
6.89 + checkConcept<WriteMap<A, bool>, InserterBoolMap<std::set<A> > >();
6.90 + checkConcept<WriteMap<A, bool>, FillBoolMap<WriteMap<A, B> > >();
6.91 + checkConcept<WriteMap<A, bool>, SettingOrderBoolMap<WriteMap<A, int> > >();
6.92 +
6.93 + int a;
6.94 +
6.95 + a=mapFunctor(constMap<A,int>(2))(A());
6.96 + check(a==2,"Something is wrong with mapFunctor");
6.97 +
6.98 + B b;
6.99 + b=functorMap(F())[A()];
6.100 +
6.101 + a=functorMap(&func)[A()];
6.102 + check(a==3,"Something is wrong with functorMap");
6.103 +
6.104 + a=combineMap(constMap<B, int, 1>(), identityMap<B>(), &binc)[B()];
6.105 + check(a==4,"Something is wrong with combineMap");
6.106 +
6.107 +
6.108 + std::cout << __FILE__ ": All tests passed.\n";
6.109 +
6.110 + return 0;
6.111 +}