1.1 --- a/lemon/Makefile.am Thu Dec 20 15:59:06 2007 +0000
1.2 +++ b/lemon/Makefile.am Sat Dec 22 12:35:00 2007 +0000
1.3 @@ -13,11 +13,14 @@
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/list_graph.h \
1.9 + lemon/maps.h \
1.10 lemon/tolerance.h
1.11
1.12 bits_HEADERS += \
1.13 lemon/bits/invalid.h \
1.14 lemon/bits/utility.h
1.15
1.16 -concept_HEADERS +=
1.17 +concept_HEADERS += \
1.18 + lemon/concepts/maps.h
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/concept_check.h Sat Dec 22 12:35:00 2007 +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 +// Modified for use in LEMON.
2.23 +// We should really consider using Boost...
2.24 +
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_BOOST_CONCEPT_CHECKS_HPP
2.40 +#define LEMON_BOOST_CONCEPT_CHECKS_HPP
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_BOOST_CONCEPT_CHECKS_HPP
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/concepts/maps.h Sat Dec 22 12:35:00 2007 +0000
3.3 @@ -0,0 +1,194 @@
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 + template<typename K, typename T>
3.41 + class ReadMap
3.42 + {
3.43 + public:
3.44 + /// Map's key type.
3.45 + typedef K Key;
3.46 + /// Map's value type. (The type of objects associated with the keys).
3.47 + typedef T Value;
3.48 +
3.49 + /// Returns the value associated with a key.
3.50 +
3.51 + /// \bug Value should n't need to be default constructible.
3.52 + ///
3.53 + Value operator[](const Key &) const {return Value();}
3.54 +
3.55 + template<typename _ReadMap>
3.56 + struct Constraints {
3.57 +
3.58 + void constraints() {
3.59 + Value val = m[key];
3.60 + val = m[key];
3.61 + typename _ReadMap::Value own_val = m[own_key];
3.62 + own_val = m[own_key];
3.63 +
3.64 + ignore_unused_variable_warning(val);
3.65 + ignore_unused_variable_warning(own_val);
3.66 + ignore_unused_variable_warning(key);
3.67 + }
3.68 + Key& key;
3.69 + typename _ReadMap::Key& own_key;
3.70 + _ReadMap& m;
3.71 + };
3.72 +
3.73 + };
3.74 +
3.75 +
3.76 + /// Writable map concept
3.77 + template<typename K, typename T>
3.78 + class WriteMap
3.79 + {
3.80 + public:
3.81 + /// Map's key type.
3.82 + typedef K Key;
3.83 + /// Map's value type. (The type of objects associated with the keys).
3.84 + typedef T Value;
3.85 +
3.86 + /// Sets the value associated with a key.
3.87 + void set(const Key &,const Value &) {}
3.88 +
3.89 + ///Default constructor
3.90 + WriteMap() {}
3.91 +
3.92 + template <typename _WriteMap>
3.93 + struct Constraints {
3.94 + void constraints() {
3.95 + // No constraints for constructor.
3.96 + m.set(key, val);
3.97 + m.set(own_key, own_val);
3.98 + ignore_unused_variable_warning(key);
3.99 + ignore_unused_variable_warning(val);
3.100 + ignore_unused_variable_warning(own_key);
3.101 + ignore_unused_variable_warning(own_val);
3.102 + }
3.103 +
3.104 + Value& val;
3.105 + typename _WriteMap::Value own_val;
3.106 + Key& key;
3.107 + typename _WriteMap::Key& own_key;
3.108 + _WriteMap& m;
3.109 +
3.110 + };
3.111 + };
3.112 +
3.113 + ///Read/Writable map concept
3.114 + template<typename K, typename T>
3.115 + class ReadWriteMap : public ReadMap<K,T>,
3.116 + public WriteMap<K,T>
3.117 + {
3.118 + public:
3.119 + /// Map's key type.
3.120 + typedef K Key;
3.121 + /// Map's value type. (The type of objects associated with the keys).
3.122 + typedef T Value;
3.123 +
3.124 + /// Returns the value associated with a key.
3.125 + Value operator[](const Key &) const {return Value();}
3.126 + /// Sets the value associated with a key.
3.127 + void set(const Key & ,const Value &) {}
3.128 +
3.129 + template<typename _ReadWriteMap>
3.130 + struct Constraints {
3.131 + void constraints() {
3.132 + checkConcept<ReadMap<K, T>, _ReadWriteMap >();
3.133 + checkConcept<WriteMap<K, T>, _ReadWriteMap >();
3.134 + }
3.135 + };
3.136 + };
3.137 +
3.138 +
3.139 + ///Dereferable map concept
3.140 + template<typename K, typename T, typename R, typename CR>
3.141 + class ReferenceMap : public ReadWriteMap<K,T>
3.142 + {
3.143 + public:
3.144 + /// Tag for reference maps.
3.145 + typedef True ReferenceMapTag;
3.146 + /// Map's key type.
3.147 + typedef K Key;
3.148 + /// Map's value type. (The type of objects associated with the keys).
3.149 + typedef T Value;
3.150 + /// Map's reference type.
3.151 + typedef R Reference;
3.152 + /// Map's const reference type.
3.153 + typedef CR ConstReference;
3.154 +
3.155 + protected:
3.156 + Value tmp;
3.157 + public:
3.158 +
3.159 + ///Returns a reference to the value associated to a key.
3.160 + Reference operator[](const Key &) { return tmp; }
3.161 + ///Returns a const reference to the value associated to a key.
3.162 + ConstReference operator[](const Key &) const
3.163 + { return tmp; }
3.164 + /// Sets the value associated with a key.
3.165 + void set(const Key &k,const Value &t) { operator[](k)=t; }
3.166 +
3.167 + // \todo rethink this concept
3.168 + template<typename _ReferenceMap>
3.169 + struct ReferenceMapConcept {
3.170 +
3.171 + void constraints() {
3.172 + checkConcept<ReadWriteMap, _ReferenceMap >();
3.173 + m[key] = val;
3.174 + val = m[key];
3.175 + m[key] = ref;
3.176 + ref = m[key];
3.177 + m[own_key] = own_val;
3.178 + own_val = m[own_key];
3.179 + m[own_key] = own_ref;
3.180 + own_ref = m[own_key];
3.181 + }
3.182 +
3.183 + typename _ReferenceMap::Key& own_key;
3.184 + typename _ReferenceMap::Value& own_val;
3.185 + typename _ReferenceMap::Reference& own_ref;
3.186 + Key& key;
3.187 + Value& val;
3.188 + Reference& ref;
3.189 + _ReferenceMap& m;
3.190 + };
3.191 + };
3.192 +
3.193 + // @}
3.194 +
3.195 + } //namespace concepts
3.196 +} //namespace lemon
3.197 +#endif // LEMON_CONCEPT_MAPS_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/maps.h Sat Dec 22 12:35:00 2007 +0000
4.3 @@ -0,0 +1,1511 @@
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 + /// If you have to provide a map only for its type definitions,
4.59 + /// or if you have to provide a writable map, but
4.60 + /// data written to it will sent to <tt>/dev/null</tt>...
4.61 + template<typename K, typename T>
4.62 + class NullMap : public MapBase<K, T> {
4.63 + public:
4.64 + typedef MapBase<K, T> Parent;
4.65 + typedef typename Parent::Key Key;
4.66 + typedef typename Parent::Value Value;
4.67 +
4.68 + /// Gives back a default constructed element.
4.69 + T operator[](const K&) const { return T(); }
4.70 + /// Absorbs the value.
4.71 + void set(const K&, const T&) {}
4.72 + };
4.73 +
4.74 + template <typename K, typename V>
4.75 + NullMap<K, V> nullMap() {
4.76 + return NullMap<K, V>();
4.77 + }
4.78 +
4.79 +
4.80 + /// Constant map.
4.81 +
4.82 + /// This is a readable map which assigns a specified value to each key.
4.83 + /// In other aspects it is equivalent to the \c NullMap.
4.84 + template<typename K, typename T>
4.85 + class ConstMap : public MapBase<K, T> {
4.86 + private:
4.87 + T v;
4.88 + public:
4.89 +
4.90 + typedef MapBase<K, T> Parent;
4.91 + typedef typename Parent::Key Key;
4.92 + typedef typename Parent::Value Value;
4.93 +
4.94 + /// Default constructor
4.95 +
4.96 + /// The value of the map will be uninitialized.
4.97 + /// (More exactly it will be default constructed.)
4.98 + ConstMap() {}
4.99 + ///\e
4.100 +
4.101 + /// \param _v The initial value of the map.
4.102 + ///
4.103 + ConstMap(const T &_v) : v(_v) {}
4.104 +
4.105 + ///\e
4.106 + T operator[](const K&) const { return v; }
4.107 +
4.108 + ///\e
4.109 + void setAll(const T &t) {
4.110 + v = t;
4.111 + }
4.112 +
4.113 + template<typename T1>
4.114 + struct rebind {
4.115 + typedef ConstMap<K, T1> other;
4.116 + };
4.117 +
4.118 + template<typename T1>
4.119 + ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
4.120 + };
4.121 +
4.122 + ///Returns a \c ConstMap class
4.123 +
4.124 + ///This function just returns a \c ConstMap class.
4.125 + ///\relates ConstMap
4.126 + template<typename K, typename V>
4.127 + inline ConstMap<K, V> constMap(const V &v) {
4.128 + return ConstMap<K, V>(v);
4.129 + }
4.130 +
4.131 +
4.132 + template<typename T, T v>
4.133 + struct Const { };
4.134 +
4.135 + /// Constant map with inlined constant value.
4.136 +
4.137 + /// This is a readable map which assigns a specified value to each key.
4.138 + /// In other aspects it is equivalent to the \c NullMap.
4.139 + template<typename K, typename V, V v>
4.140 + class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
4.141 + public:
4.142 + typedef MapBase<K, V> Parent;
4.143 + typedef typename Parent::Key Key;
4.144 + typedef typename Parent::Value Value;
4.145 +
4.146 + ConstMap() { }
4.147 + ///\e
4.148 + V operator[](const K&) const { return v; }
4.149 + ///\e
4.150 + void set(const K&, const V&) { }
4.151 + };
4.152 +
4.153 + ///Returns a \c ConstMap class
4.154 +
4.155 + ///This function just returns a \c ConstMap class with inlined value.
4.156 + ///\relates ConstMap
4.157 + template<typename K, typename V, V v>
4.158 + inline ConstMap<K, Const<V, v> > constMap() {
4.159 + return ConstMap<K, Const<V, v> >();
4.160 + }
4.161 +
4.162 + ///Map based on std::map
4.163 +
4.164 + ///This is essentially a wrapper for \c std::map. With addition that
4.165 + ///you can specify a default value different from \c Value() .
4.166 + template <typename K, typename T, typename Compare = std::less<K> >
4.167 + class StdMap {
4.168 + template <typename K1, typename T1, typename C1>
4.169 + friend class StdMap;
4.170 + public:
4.171 +
4.172 + typedef True ReferenceMapTag;
4.173 + ///\e
4.174 + typedef K Key;
4.175 + ///\e
4.176 + typedef T Value;
4.177 + ///\e
4.178 + typedef T& Reference;
4.179 + ///\e
4.180 + typedef const T& ConstReference;
4.181 +
4.182 + private:
4.183 +
4.184 + typedef std::map<K, T, Compare> Map;
4.185 + Value _value;
4.186 + Map _map;
4.187 +
4.188 + public:
4.189 +
4.190 + /// Constructor with specified default value
4.191 + StdMap(const T& value = T()) : _value(value) {}
4.192 + /// \brief Constructs the map from an appropriate std::map, and explicitly
4.193 + /// specifies a default value.
4.194 + template <typename T1, typename Comp1>
4.195 + StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
4.196 + : _map(map.begin(), map.end()), _value(value) {}
4.197 +
4.198 + /// \brief Constructs a map from an other StdMap.
4.199 + template<typename T1, typename Comp1>
4.200 + StdMap(const StdMap<Key, T1, Comp1> &c)
4.201 + : _map(c._map.begin(), c._map.end()), _value(c._value) {}
4.202 +
4.203 + private:
4.204 +
4.205 + StdMap& operator=(const StdMap&);
4.206 +
4.207 + public:
4.208 +
4.209 + ///\e
4.210 + Reference operator[](const Key &k) {
4.211 + typename Map::iterator it = _map.lower_bound(k);
4.212 + if (it != _map.end() && !_map.key_comp()(k, it->first))
4.213 + return it->second;
4.214 + else
4.215 + return _map.insert(it, std::make_pair(k, _value))->second;
4.216 + }
4.217 +
4.218 + /// \e
4.219 + ConstReference operator[](const Key &k) const {
4.220 + typename Map::const_iterator it = _map.find(k);
4.221 + if (it != _map.end())
4.222 + return it->second;
4.223 + else
4.224 + return _value;
4.225 + }
4.226 +
4.227 + /// \e
4.228 + void set(const Key &k, const T &t) {
4.229 + typename Map::iterator it = _map.lower_bound(k);
4.230 + if (it != _map.end() && !_map.key_comp()(k, it->first))
4.231 + it->second = t;
4.232 + else
4.233 + _map.insert(it, std::make_pair(k, t));
4.234 + }
4.235 +
4.236 + /// \e
4.237 + void setAll(const T &t) {
4.238 + _value = t;
4.239 + _map.clear();
4.240 + }
4.241 +
4.242 + template <typename T1, typename C1 = std::less<T1> >
4.243 + struct rebind {
4.244 + typedef StdMap<Key, T1, C1> other;
4.245 + };
4.246 + };
4.247 +
4.248 + /// \brief Map for storing values for the range \c [0..size-1] range keys
4.249 + ///
4.250 + /// The current map has the \c [0..size-1] keyset and the values
4.251 + /// are stored in a \c std::vector<T> container. It can be used with
4.252 + /// some data structures, for example \c UnionFind, \c BinHeap, when
4.253 + /// the used items are small integer numbers.
4.254 + template <typename T>
4.255 + class IntegerMap {
4.256 +
4.257 + template <typename T1>
4.258 + friend class IntegerMap;
4.259 +
4.260 + public:
4.261 +
4.262 + typedef True ReferenceMapTag;
4.263 + ///\e
4.264 + typedef int Key;
4.265 + ///\e
4.266 + typedef T Value;
4.267 + ///\e
4.268 + typedef T& Reference;
4.269 + ///\e
4.270 + typedef const T& ConstReference;
4.271 +
4.272 + private:
4.273 +
4.274 + typedef std::vector<T> Vector;
4.275 + Vector _vector;
4.276 +
4.277 + public:
4.278 +
4.279 + /// Constructor with specified default value
4.280 + IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
4.281 +
4.282 + /// \brief Constructs the map from an appropriate std::vector.
4.283 + template <typename T1>
4.284 + IntegerMap(const std::vector<T1>& vector)
4.285 + : _vector(vector.begin(), vector.end()) {}
4.286 +
4.287 + /// \brief Constructs a map from an other IntegerMap.
4.288 + template <typename T1>
4.289 + IntegerMap(const IntegerMap<T1> &c)
4.290 + : _vector(c._vector.begin(), c._vector.end()) {}
4.291 +
4.292 + /// \brief Resize the container
4.293 + void resize(int size, const T& value = T()) {
4.294 + _vector.resize(size, value);
4.295 + }
4.296 +
4.297 + private:
4.298 +
4.299 + IntegerMap& operator=(const IntegerMap&);
4.300 +
4.301 + public:
4.302 +
4.303 + ///\e
4.304 + Reference operator[](Key k) {
4.305 + return _vector[k];
4.306 + }
4.307 +
4.308 + /// \e
4.309 + ConstReference operator[](Key k) const {
4.310 + return _vector[k];
4.311 + }
4.312 +
4.313 + /// \e
4.314 + void set(const Key &k, const T& t) {
4.315 + _vector[k] = t;
4.316 + }
4.317 +
4.318 + };
4.319 +
4.320 + /// @}
4.321 +
4.322 + /// \addtogroup map_adaptors
4.323 + /// @{
4.324 +
4.325 + /// \brief Identity mapping.
4.326 + ///
4.327 + /// This mapping gives back the given key as value without any
4.328 + /// modification.
4.329 + template <typename T>
4.330 + class IdentityMap : public MapBase<T, T> {
4.331 + public:
4.332 + typedef MapBase<T, T> Parent;
4.333 + typedef typename Parent::Key Key;
4.334 + typedef typename Parent::Value Value;
4.335 +
4.336 + /// \e
4.337 + const T& operator[](const T& t) const {
4.338 + return t;
4.339 + }
4.340 + };
4.341 +
4.342 + ///Returns an \c IdentityMap class
4.343 +
4.344 + ///This function just returns an \c IdentityMap class.
4.345 + ///\relates IdentityMap
4.346 + template<typename T>
4.347 + inline IdentityMap<T> identityMap() {
4.348 + return IdentityMap<T>();
4.349 + }
4.350 +
4.351 +
4.352 + ///Convert the \c Value of a map to another type.
4.353 +
4.354 + ///This \c concepts::ReadMap "read only map"
4.355 + ///converts the \c Value of a maps to type \c T.
4.356 + ///Its \c Key is inherited from \c M.
4.357 + template <typename M, typename T>
4.358 + class ConvertMap : public MapBase<typename M::Key, T> {
4.359 + const M& m;
4.360 + public:
4.361 + typedef MapBase<typename M::Key, T> Parent;
4.362 + typedef typename Parent::Key Key;
4.363 + typedef typename Parent::Value Value;
4.364 +
4.365 + ///Constructor
4.366 +
4.367 + ///Constructor
4.368 + ///\param _m is the underlying map
4.369 + ConvertMap(const M &_m) : m(_m) {};
4.370 +
4.371 + /// \brief The subscript operator.
4.372 + ///
4.373 + /// The subscript operator.
4.374 + /// \param k The key
4.375 + /// \return The target of the arc
4.376 + Value operator[](const Key& k) const {return m[k];}
4.377 + };
4.378 +
4.379 + ///Returns an \c ConvertMap class
4.380 +
4.381 + ///This function just returns an \c ConvertMap class.
4.382 + ///\relates ConvertMap
4.383 + template<typename T, typename M>
4.384 + inline ConvertMap<M, T> convertMap(const M &m) {
4.385 + return ConvertMap<M, T>(m);
4.386 + }
4.387 +
4.388 + ///Simple wrapping of the map
4.389 +
4.390 + ///This \c concepts::ReadMap "read only map" returns the simple
4.391 + ///wrapping of the given map. Sometimes the reference maps cannot be
4.392 + ///combined with simple read maps. This map adaptor wraps the given
4.393 + ///map to simple read map.
4.394 + template<typename M>
4.395 + class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
4.396 + const M& m;
4.397 +
4.398 + public:
4.399 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.400 + typedef typename Parent::Key Key;
4.401 + typedef typename Parent::Value Value;
4.402 +
4.403 + ///Constructor
4.404 + SimpleMap(const M &_m) : m(_m) {};
4.405 + ///\e
4.406 + Value operator[](Key k) const {return m[k];}
4.407 + };
4.408 +
4.409 + ///Simple writeable wrapping of the map
4.410 +
4.411 + ///This \c concepts::ReadMap "read only map" returns the simple
4.412 + ///wrapping of the given map. Sometimes the reference maps cannot be
4.413 + ///combined with simple read-write maps. This map adaptor wraps the
4.414 + ///given map to simple read-write map.
4.415 + template<typename M>
4.416 + class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
4.417 + M& m;
4.418 +
4.419 + public:
4.420 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.421 + typedef typename Parent::Key Key;
4.422 + typedef typename Parent::Value Value;
4.423 +
4.424 + ///Constructor
4.425 + SimpleWriteMap(M &_m) : m(_m) {};
4.426 + ///\e
4.427 + Value operator[](Key k) const {return m[k];}
4.428 + ///\e
4.429 + void set(Key k, const Value& c) { m.set(k, c); }
4.430 + };
4.431 +
4.432 + ///Sum of two maps
4.433 +
4.434 + ///This \c concepts::ReadMap "read only map" returns the sum of the two
4.435 + ///given maps. Its \c Key and \c Value will be inherited from \c M1.
4.436 + ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
4.437 +
4.438 + template<typename M1, typename M2>
4.439 + class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
4.440 + const M1& m1;
4.441 + const M2& m2;
4.442 +
4.443 + public:
4.444 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.445 + typedef typename Parent::Key Key;
4.446 + typedef typename Parent::Value Value;
4.447 +
4.448 + ///Constructor
4.449 + AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.450 + ///\e
4.451 + Value operator[](Key k) const {return m1[k]+m2[k];}
4.452 + };
4.453 +
4.454 + ///Returns an \c AddMap class
4.455 +
4.456 + ///This function just returns an \c AddMap class.
4.457 + ///\todo How to call these type of functions?
4.458 + ///
4.459 + ///\relates AddMap
4.460 + template<typename M1, typename M2>
4.461 + inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
4.462 + return AddMap<M1, M2>(m1,m2);
4.463 + }
4.464 +
4.465 + ///Shift a map with a constant.
4.466 +
4.467 + ///This \c concepts::ReadMap "read only map" returns the sum of the
4.468 + ///given map and a constant value.
4.469 + ///Its \c Key and \c Value is inherited from \c M.
4.470 + ///
4.471 + ///Actually,
4.472 + ///\code
4.473 + /// ShiftMap<X> sh(x,v);
4.474 + ///\endcode
4.475 + ///is equivalent with
4.476 + ///\code
4.477 + /// ConstMap<X::Key, X::Value> c_tmp(v);
4.478 + /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
4.479 + ///\endcode
4.480 + template<typename M, typename C = typename M::Value>
4.481 + class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
4.482 + const M& m;
4.483 + C v;
4.484 + public:
4.485 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.486 + typedef typename Parent::Key Key;
4.487 + typedef typename Parent::Value Value;
4.488 +
4.489 + ///Constructor
4.490 +
4.491 + ///Constructor
4.492 + ///\param _m is the undelying map
4.493 + ///\param _v is the shift value
4.494 + ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
4.495 + ///\e
4.496 + Value operator[](Key k) const {return m[k] + v;}
4.497 + };
4.498 +
4.499 + ///Shift a map with a constant.
4.500 +
4.501 + ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
4.502 + ///given map and a constant value. It makes also possible to write the map.
4.503 + ///Its \c Key and \c Value is inherited from \c M.
4.504 + ///
4.505 + ///Actually,
4.506 + ///\code
4.507 + /// ShiftMap<X> sh(x,v);
4.508 + ///\endcode
4.509 + ///is equivalent with
4.510 + ///\code
4.511 + /// ConstMap<X::Key, X::Value> c_tmp(v);
4.512 + /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
4.513 + ///\endcode
4.514 + template<typename M, typename C = typename M::Value>
4.515 + class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
4.516 + M& m;
4.517 + C v;
4.518 + public:
4.519 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.520 + typedef typename Parent::Key Key;
4.521 + typedef typename Parent::Value Value;
4.522 +
4.523 + ///Constructor
4.524 +
4.525 + ///Constructor
4.526 + ///\param _m is the undelying map
4.527 + ///\param _v is the shift value
4.528 + ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
4.529 + /// \e
4.530 + Value operator[](Key k) const {return m[k] + v;}
4.531 + /// \e
4.532 + void set(Key k, const Value& c) { m.set(k, c - v); }
4.533 + };
4.534 +
4.535 + ///Returns an \c ShiftMap class
4.536 +
4.537 + ///This function just returns an \c ShiftMap class.
4.538 + ///\relates ShiftMap
4.539 + template<typename M, typename C>
4.540 + inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
4.541 + return ShiftMap<M, C>(m,v);
4.542 + }
4.543 +
4.544 + template<typename M, typename C>
4.545 + inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
4.546 + return ShiftWriteMap<M, C>(m,v);
4.547 + }
4.548 +
4.549 + ///Difference of two maps
4.550 +
4.551 + ///This \c concepts::ReadMap "read only map" returns the difference
4.552 + ///of the values of the two
4.553 + ///given maps. Its \c Key and \c Value will be inherited from \c M1.
4.554 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
4.555 +
4.556 + template<typename M1, typename M2>
4.557 + class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
4.558 + const M1& m1;
4.559 + const M2& m2;
4.560 + public:
4.561 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.562 + typedef typename Parent::Key Key;
4.563 + typedef typename Parent::Value Value;
4.564 +
4.565 + ///Constructor
4.566 + SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.567 + /// \e
4.568 + Value operator[](Key k) const {return m1[k]-m2[k];}
4.569 + };
4.570 +
4.571 + ///Returns a \c SubMap class
4.572 +
4.573 + ///This function just returns a \c SubMap class.
4.574 + ///
4.575 + ///\relates SubMap
4.576 + template<typename M1, typename M2>
4.577 + inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
4.578 + return SubMap<M1, M2>(m1, m2);
4.579 + }
4.580 +
4.581 + ///Product of two maps
4.582 +
4.583 + ///This \c concepts::ReadMap "read only map" returns the product of the
4.584 + ///values of the two
4.585 + ///given
4.586 + ///maps. Its \c Key and \c Value will be inherited from \c M1.
4.587 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
4.588 +
4.589 + template<typename M1, typename M2>
4.590 + class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
4.591 + const M1& m1;
4.592 + const M2& m2;
4.593 + public:
4.594 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.595 + typedef typename Parent::Key Key;
4.596 + typedef typename Parent::Value Value;
4.597 +
4.598 + ///Constructor
4.599 + MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.600 + /// \e
4.601 + Value operator[](Key k) const {return m1[k]*m2[k];}
4.602 + };
4.603 +
4.604 + ///Returns a \c MulMap class
4.605 +
4.606 + ///This function just returns a \c MulMap class.
4.607 + ///\relates MulMap
4.608 + template<typename M1, typename M2>
4.609 + inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
4.610 + return MulMap<M1, M2>(m1,m2);
4.611 + }
4.612 +
4.613 + ///Scales a maps with a constant.
4.614 +
4.615 + ///This \c concepts::ReadMap "read only map" returns the value of the
4.616 + ///given map multiplied from the left side with a constant value.
4.617 + ///Its \c Key and \c Value is inherited from \c M.
4.618 + ///
4.619 + ///Actually,
4.620 + ///\code
4.621 + /// ScaleMap<X> sc(x,v);
4.622 + ///\endcode
4.623 + ///is equivalent with
4.624 + ///\code
4.625 + /// ConstMap<X::Key, X::Value> c_tmp(v);
4.626 + /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
4.627 + ///\endcode
4.628 + template<typename M, typename C = typename M::Value>
4.629 + class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
4.630 + const M& m;
4.631 + C v;
4.632 + public:
4.633 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.634 + typedef typename Parent::Key Key;
4.635 + typedef typename Parent::Value Value;
4.636 +
4.637 + ///Constructor
4.638 +
4.639 + ///Constructor
4.640 + ///\param _m is the undelying map
4.641 + ///\param _v is the scaling value
4.642 + ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
4.643 + /// \e
4.644 + Value operator[](Key k) const {return v * m[k];}
4.645 + };
4.646 +
4.647 + ///Scales a maps with a constant.
4.648 +
4.649 + ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
4.650 + ///given map multiplied from the left side with a constant value. It can
4.651 + ///be used as write map also if the given multiplier is not zero.
4.652 + ///Its \c Key and \c Value is inherited from \c M.
4.653 + template<typename M, typename C = typename M::Value>
4.654 + class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
4.655 + M& m;
4.656 + C v;
4.657 + public:
4.658 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.659 + typedef typename Parent::Key Key;
4.660 + typedef typename Parent::Value Value;
4.661 +
4.662 + ///Constructor
4.663 +
4.664 + ///Constructor
4.665 + ///\param _m is the undelying map
4.666 + ///\param _v is the scaling value
4.667 + ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
4.668 + /// \e
4.669 + Value operator[](Key k) const {return v * m[k];}
4.670 + /// \e
4.671 + void set(Key k, const Value& c) { m.set(k, c / v);}
4.672 + };
4.673 +
4.674 + ///Returns an \c ScaleMap class
4.675 +
4.676 + ///This function just returns an \c ScaleMap class.
4.677 + ///\relates ScaleMap
4.678 + template<typename M, typename C>
4.679 + inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
4.680 + return ScaleMap<M, C>(m,v);
4.681 + }
4.682 +
4.683 + template<typename M, typename C>
4.684 + inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
4.685 + return ScaleWriteMap<M, C>(m,v);
4.686 + }
4.687 +
4.688 + ///Quotient of two maps
4.689 +
4.690 + ///This \c concepts::ReadMap "read only map" returns the quotient of the
4.691 + ///values of the two
4.692 + ///given maps. Its \c Key and \c Value will be inherited from \c M1.
4.693 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
4.694 +
4.695 + template<typename M1, typename M2>
4.696 + class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
4.697 + const M1& m1;
4.698 + const M2& m2;
4.699 + public:
4.700 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.701 + typedef typename Parent::Key Key;
4.702 + typedef typename Parent::Value Value;
4.703 +
4.704 + ///Constructor
4.705 + DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.706 + /// \e
4.707 + Value operator[](Key k) const {return m1[k]/m2[k];}
4.708 + };
4.709 +
4.710 + ///Returns a \c DivMap class
4.711 +
4.712 + ///This function just returns a \c DivMap class.
4.713 + ///\relates DivMap
4.714 + template<typename M1, typename M2>
4.715 + inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
4.716 + return DivMap<M1, M2>(m1,m2);
4.717 + }
4.718 +
4.719 + ///Composition of two maps
4.720 +
4.721 + ///This \c concepts::ReadMap "read only map" returns the composition of
4.722 + ///two
4.723 + ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
4.724 + ///of \c M2,
4.725 + ///then for
4.726 + ///\code
4.727 + /// ComposeMap<M1, M2> cm(m1,m2);
4.728 + ///\endcode
4.729 + /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
4.730 + ///
4.731 + ///Its \c Key is inherited from \c M2 and its \c Value is from
4.732 + ///\c M1.
4.733 + ///The \c M2::Value must be convertible to \c M1::Key.
4.734 + ///\todo Check the requirements.
4.735 + template <typename M1, typename M2>
4.736 + class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
4.737 + const M1& m1;
4.738 + const M2& m2;
4.739 + public:
4.740 + typedef MapBase<typename M2::Key, typename M1::Value> Parent;
4.741 + typedef typename Parent::Key Key;
4.742 + typedef typename Parent::Value Value;
4.743 +
4.744 + ///Constructor
4.745 + ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
4.746 +
4.747 + /// \e
4.748 +
4.749 +
4.750 + /// \todo Use the MapTraits once it is ported.
4.751 + ///
4.752 +
4.753 + //typename MapTraits<M1>::ConstReturnValue
4.754 + typename M1::Value
4.755 + operator[](Key k) const {return m1[m2[k]];}
4.756 + };
4.757 + ///Returns a \c ComposeMap class
4.758 +
4.759 + ///This function just returns a \c ComposeMap class.
4.760 + ///
4.761 + ///\relates ComposeMap
4.762 + template <typename M1, typename M2>
4.763 + inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
4.764 + return ComposeMap<M1, M2>(m1,m2);
4.765 + }
4.766 +
4.767 + ///Combines of two maps using an STL (binary) functor.
4.768 +
4.769 + ///Combines of two maps using an STL (binary) functor.
4.770 + ///
4.771 + ///
4.772 + ///This \c concepts::ReadMap "read only map" takes two maps and a
4.773 + ///binary functor and returns the composition of
4.774 + ///the two
4.775 + ///given maps unsing the functor.
4.776 + ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
4.777 + ///and \c f is of \c F,
4.778 + ///then for
4.779 + ///\code
4.780 + /// CombineMap<M1, M2,F,V> cm(m1,m2,f);
4.781 + ///\endcode
4.782 + /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
4.783 + ///
4.784 + ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
4.785 + ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
4.786 + ///input parameter of \c F and the return type of \c F must be convertible
4.787 + ///to \c V.
4.788 + ///\todo Check the requirements.
4.789 + template<typename M1, typename M2, typename F,
4.790 + typename V = typename F::result_type>
4.791 + class CombineMap : public MapBase<typename M1::Key, V> {
4.792 + const M1& m1;
4.793 + const M2& m2;
4.794 + F f;
4.795 + public:
4.796 + typedef MapBase<typename M1::Key, V> Parent;
4.797 + typedef typename Parent::Key Key;
4.798 + typedef typename Parent::Value Value;
4.799 +
4.800 + ///Constructor
4.801 + CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
4.802 + : m1(_m1), m2(_m2), f(_f) {};
4.803 + /// \e
4.804 + Value operator[](Key k) const {return f(m1[k],m2[k]);}
4.805 + };
4.806 +
4.807 + ///Returns a \c CombineMap class
4.808 +
4.809 + ///This function just returns a \c CombineMap class.
4.810 + ///
4.811 + ///For example if \c m1 and \c m2 are both \c double valued maps, then
4.812 + ///\code
4.813 + ///combineMap<double>(m1,m2,std::plus<double>())
4.814 + ///\endcode
4.815 + ///is equivalent with
4.816 + ///\code
4.817 + ///addMap(m1,m2)
4.818 + ///\endcode
4.819 + ///
4.820 + ///This function is specialized for adaptable binary function
4.821 + ///classes and c++ functions.
4.822 + ///
4.823 + ///\relates CombineMap
4.824 + template<typename M1, typename M2, typename F, typename V>
4.825 + inline CombineMap<M1, M2, F, V>
4.826 + combineMap(const M1& m1,const M2& m2, const F& f) {
4.827 + return CombineMap<M1, M2, F, V>(m1,m2,f);
4.828 + }
4.829 +
4.830 + template<typename M1, typename M2, typename F>
4.831 + inline CombineMap<M1, M2, F, typename F::result_type>
4.832 + combineMap(const M1& m1, const M2& m2, const F& f) {
4.833 + return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
4.834 + }
4.835 +
4.836 + template<typename M1, typename M2, typename K1, typename K2, typename V>
4.837 + inline CombineMap<M1, M2, V (*)(K1, K2), V>
4.838 + combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
4.839 + return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
4.840 + }
4.841 +
4.842 + ///Negative value of a map
4.843 +
4.844 + ///This \c concepts::ReadMap "read only map" returns the negative
4.845 + ///value of the
4.846 + ///value returned by the
4.847 + ///given map. Its \c Key and \c Value will be inherited from \c M.
4.848 + ///The unary \c - operator must be defined for \c Value, of course.
4.849 +
4.850 + template<typename M>
4.851 + class NegMap : public MapBase<typename M::Key, typename M::Value> {
4.852 + const M& m;
4.853 + public:
4.854 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.855 + typedef typename Parent::Key Key;
4.856 + typedef typename Parent::Value Value;
4.857 +
4.858 + ///Constructor
4.859 + NegMap(const M &_m) : m(_m) {};
4.860 + /// \e
4.861 + Value operator[](Key k) const {return -m[k];}
4.862 + };
4.863 +
4.864 + ///Negative value of a map
4.865 +
4.866 + ///This \c concepts::ReadWriteMap "read-write map" returns the negative
4.867 + ///value of the value returned by the
4.868 + ///given map. Its \c Key and \c Value will be inherited from \c M.
4.869 + ///The unary \c - operator must be defined for \c Value, of course.
4.870 +
4.871 + template<typename M>
4.872 + class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
4.873 + M& m;
4.874 + public:
4.875 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.876 + typedef typename Parent::Key Key;
4.877 + typedef typename Parent::Value Value;
4.878 +
4.879 + ///Constructor
4.880 + NegWriteMap(M &_m) : m(_m) {};
4.881 + /// \e
4.882 + Value operator[](Key k) const {return -m[k];}
4.883 + /// \e
4.884 + void set(Key k, const Value& v) { m.set(k, -v); }
4.885 + };
4.886 +
4.887 + ///Returns a \c NegMap class
4.888 +
4.889 + ///This function just returns a \c NegMap class.
4.890 + ///\relates NegMap
4.891 + template <typename M>
4.892 + inline NegMap<M> negMap(const M &m) {
4.893 + return NegMap<M>(m);
4.894 + }
4.895 +
4.896 + template <typename M>
4.897 + inline NegWriteMap<M> negMap(M &m) {
4.898 + return NegWriteMap<M>(m);
4.899 + }
4.900 +
4.901 + ///Absolute value of a map
4.902 +
4.903 + ///This \c concepts::ReadMap "read only map" returns the absolute value
4.904 + ///of the
4.905 + ///value returned by the
4.906 + ///given map. Its \c Key and \c Value will be inherited
4.907 + ///from <tt>M</tt>. <tt>Value</tt>
4.908 + ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
4.909 + ///operator must be defined for it, of course.
4.910 + ///
4.911 + ///\bug We need a unified way to handle the situation below:
4.912 + ///\code
4.913 + /// struct _UnConvertible {};
4.914 + /// template<class A> inline A t_abs(A a) {return _UnConvertible();}
4.915 + /// template<> inline int t_abs<>(int n) {return abs(n);}
4.916 + /// template<> inline long int t_abs<>(long int n) {return labs(n);}
4.917 + /// template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
4.918 + /// template<> inline float t_abs<>(float n) {return fabsf(n);}
4.919 + /// template<> inline double t_abs<>(double n) {return fabs(n);}
4.920 + /// template<> inline long double t_abs<>(long double n) {return fabsl(n);}
4.921 + ///\endcode
4.922 +
4.923 +
4.924 + template<typename M>
4.925 + class AbsMap : public MapBase<typename M::Key, typename M::Value> {
4.926 + const M& m;
4.927 + public:
4.928 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.929 + typedef typename Parent::Key Key;
4.930 + typedef typename Parent::Value Value;
4.931 +
4.932 + ///Constructor
4.933 + AbsMap(const M &_m) : m(_m) {};
4.934 + /// \e
4.935 + Value operator[](Key k) const {
4.936 + Value tmp = m[k];
4.937 + return tmp >= 0 ? tmp : -tmp;
4.938 + }
4.939 +
4.940 + };
4.941 +
4.942 + ///Returns a \c AbsMap class
4.943 +
4.944 + ///This function just returns a \c AbsMap class.
4.945 + ///\relates AbsMap
4.946 + template<typename M>
4.947 + inline AbsMap<M> absMap(const M &m) {
4.948 + return AbsMap<M>(m);
4.949 + }
4.950 +
4.951 + ///Converts an STL style functor to a map
4.952 +
4.953 + ///This \c concepts::ReadMap "read only map" returns the value
4.954 + ///of a
4.955 + ///given map.
4.956 + ///
4.957 + ///Template parameters \c K and \c V will become its
4.958 + ///\c Key and \c Value. They must be given explicitely
4.959 + ///because a functor does not provide such typedefs.
4.960 + ///
4.961 + ///Parameter \c F is the type of the used functor.
4.962 + template<typename F,
4.963 + typename K = typename F::argument_type,
4.964 + typename V = typename F::result_type>
4.965 + class FunctorMap : public MapBase<K, V> {
4.966 + F f;
4.967 + public:
4.968 + typedef MapBase<K, V> Parent;
4.969 + typedef typename Parent::Key Key;
4.970 + typedef typename Parent::Value Value;
4.971 +
4.972 + ///Constructor
4.973 + FunctorMap(const F &_f = F()) : f(_f) {}
4.974 + /// \e
4.975 + Value operator[](Key k) const { return f(k);}
4.976 + };
4.977 +
4.978 + ///Returns a \c FunctorMap class
4.979 +
4.980 + ///This function just returns a \c FunctorMap class.
4.981 + ///
4.982 + ///It is specialized for adaptable function classes and
4.983 + ///c++ functions.
4.984 + ///\relates FunctorMap
4.985 + template<typename K, typename V, typename F> inline
4.986 + FunctorMap<F, K, V> functorMap(const F &f) {
4.987 + return FunctorMap<F, K, V>(f);
4.988 + }
4.989 +
4.990 + template <typename F> inline
4.991 + FunctorMap<F, typename F::argument_type, typename F::result_type>
4.992 + functorMap(const F &f) {
4.993 + return FunctorMap<F, typename F::argument_type,
4.994 + typename F::result_type>(f);
4.995 + }
4.996 +
4.997 + template <typename K, typename V> inline
4.998 + FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
4.999 + return FunctorMap<V (*)(K), K, V>(f);
4.1000 + }
4.1001 +
4.1002 +
4.1003 + ///Converts a map to an STL style (unary) functor
4.1004 +
4.1005 + ///This class Converts a map to an STL style (unary) functor.
4.1006 + ///that is it provides an <tt>operator()</tt> to read its values.
4.1007 + ///
4.1008 + ///For the sake of convenience it also works as
4.1009 + ///a ususal \c concepts::ReadMap "readable map",
4.1010 + ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
4.1011 + template <typename M>
4.1012 + class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
4.1013 + const M& m;
4.1014 + public:
4.1015 + typedef MapBase<typename M::Key, typename M::Value> Parent;
4.1016 + typedef typename Parent::Key Key;
4.1017 + typedef typename Parent::Value Value;
4.1018 +
4.1019 + typedef typename M::Key argument_type;
4.1020 + typedef typename M::Value result_type;
4.1021 +
4.1022 + ///Constructor
4.1023 + MapFunctor(const M &_m) : m(_m) {};
4.1024 + ///\e
4.1025 + Value operator()(Key k) const {return m[k];}
4.1026 + ///\e
4.1027 + Value operator[](Key k) const {return m[k];}
4.1028 + };
4.1029 +
4.1030 + ///Returns a \c MapFunctor class
4.1031 +
4.1032 + ///This function just returns a \c MapFunctor class.
4.1033 + ///\relates MapFunctor
4.1034 + template<typename M>
4.1035 + inline MapFunctor<M> mapFunctor(const M &m) {
4.1036 + return MapFunctor<M>(m);
4.1037 + }
4.1038 +
4.1039 + ///Applies all map setting operations to two maps
4.1040 +
4.1041 + ///This map has two \c concepts::ReadMap "readable map"
4.1042 + ///parameters and each read request will be passed just to the
4.1043 + ///first map. This class is the just readable map type of the ForkWriteMap.
4.1044 + ///
4.1045 + ///The \c Key and \c Value will be inherited from \c M1.
4.1046 + ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
4.1047 + template<typename M1, typename M2>
4.1048 + class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
4.1049 + const M1& m1;
4.1050 + const M2& m2;
4.1051 + public:
4.1052 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.1053 + typedef typename Parent::Key Key;
4.1054 + typedef typename Parent::Value Value;
4.1055 +
4.1056 + ///Constructor
4.1057 + ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
4.1058 + /// \e
4.1059 + Value operator[](Key k) const {return m1[k];}
4.1060 + };
4.1061 +
4.1062 +
4.1063 + ///Applies all map setting operations to two maps
4.1064 +
4.1065 + ///This map has two \c concepts::WriteMap "writable map"
4.1066 + ///parameters and each write request will be passed to both of them.
4.1067 + ///If \c M1 is also \c concepts::ReadMap "readable",
4.1068 + ///then the read operations will return the
4.1069 + ///corresponding values of \c M1.
4.1070 + ///
4.1071 + ///The \c Key and \c Value will be inherited from \c M1.
4.1072 + ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
4.1073 + template<typename M1, typename M2>
4.1074 + class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
4.1075 + M1& m1;
4.1076 + M2& m2;
4.1077 + public:
4.1078 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
4.1079 + typedef typename Parent::Key Key;
4.1080 + typedef typename Parent::Value Value;
4.1081 +
4.1082 + ///Constructor
4.1083 + ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
4.1084 + ///\e
4.1085 + Value operator[](Key k) const {return m1[k];}
4.1086 + ///\e
4.1087 + void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
4.1088 + };
4.1089 +
4.1090 + ///Returns an \c ForkMap class
4.1091 +
4.1092 + ///This function just returns an \c ForkMap class.
4.1093 + ///
4.1094 + ///\relates ForkMap
4.1095 + template <typename M1, typename M2>
4.1096 + inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
4.1097 + return ForkMap<M1, M2>(m1,m2);
4.1098 + }
4.1099 +
4.1100 + template <typename M1, typename M2>
4.1101 + inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
4.1102 + return ForkWriteMap<M1, M2>(m1,m2);
4.1103 + }
4.1104 +
4.1105 +
4.1106 +
4.1107 + /* ************* BOOL MAPS ******************* */
4.1108 +
4.1109 + ///Logical 'not' of a map
4.1110 +
4.1111 + ///This bool \c concepts::ReadMap "read only map" returns the
4.1112 + ///logical negation of
4.1113 + ///value returned by the
4.1114 + ///given map. Its \c Key and will be inherited from \c M,
4.1115 + ///its Value is <tt>bool</tt>.
4.1116 + template <typename M>
4.1117 + class NotMap : public MapBase<typename M::Key, bool> {
4.1118 + const M& m;
4.1119 + public:
4.1120 + typedef MapBase<typename M::Key, bool> Parent;
4.1121 + typedef typename Parent::Key Key;
4.1122 + typedef typename Parent::Value Value;
4.1123 +
4.1124 + /// Constructor
4.1125 + NotMap(const M &_m) : m(_m) {};
4.1126 + ///\e
4.1127 + Value operator[](Key k) const {return !m[k];}
4.1128 + };
4.1129 +
4.1130 + ///Logical 'not' of a map with writing possibility
4.1131 +
4.1132 + ///This bool \c concepts::ReadWriteMap "read-write map" returns the
4.1133 + ///logical negation of value returned by the given map. When it is set,
4.1134 + ///the opposite value is set to the original map.
4.1135 + ///Its \c Key and will be inherited from \c M,
4.1136 + ///its Value is <tt>bool</tt>.
4.1137 + template <typename M>
4.1138 + class NotWriteMap : public MapBase<typename M::Key, bool> {
4.1139 + M& m;
4.1140 + public:
4.1141 + typedef MapBase<typename M::Key, bool> Parent;
4.1142 + typedef typename Parent::Key Key;
4.1143 + typedef typename Parent::Value Value;
4.1144 +
4.1145 + /// Constructor
4.1146 + NotWriteMap(M &_m) : m(_m) {};
4.1147 + ///\e
4.1148 + Value operator[](Key k) const {return !m[k];}
4.1149 + ///\e
4.1150 + void set(Key k, bool v) { m.set(k, !v); }
4.1151 + };
4.1152 +
4.1153 + ///Returns a \c NotMap class
4.1154 +
4.1155 + ///This function just returns a \c NotMap class.
4.1156 + ///\relates NotMap
4.1157 + template <typename M>
4.1158 + inline NotMap<M> notMap(const M &m) {
4.1159 + return NotMap<M>(m);
4.1160 + }
4.1161 +
4.1162 + template <typename M>
4.1163 + inline NotWriteMap<M> notMap(M &m) {
4.1164 + return NotWriteMap<M>(m);
4.1165 + }
4.1166 +
4.1167 + namespace _maps_bits {
4.1168 +
4.1169 + template <typename Value>
4.1170 + struct Identity {
4.1171 + typedef Value argument_type;
4.1172 + typedef Value result_type;
4.1173 + Value operator()(const Value& val) const {
4.1174 + return val;
4.1175 + }
4.1176 + };
4.1177 +
4.1178 + template <typename _Iterator, typename Enable = void>
4.1179 + struct IteratorTraits {
4.1180 + typedef typename std::iterator_traits<_Iterator>::value_type Value;
4.1181 + };
4.1182 +
4.1183 + template <typename _Iterator>
4.1184 + struct IteratorTraits<_Iterator,
4.1185 + typename exists<typename _Iterator::container_type>::type>
4.1186 + {
4.1187 + typedef typename _Iterator::container_type::value_type Value;
4.1188 + };
4.1189 +
4.1190 + }
4.1191 +
4.1192 +
4.1193 + /// \brief Writable bool map for store each true assigned elements.
4.1194 + ///
4.1195 + /// Writable bool map to store each true assigned elements. It will
4.1196 + /// copies all the keys set to true to the given iterator.
4.1197 + ///
4.1198 + /// \note The container of the iterator should contain space
4.1199 + /// for each element.
4.1200 + ///
4.1201 + /// The next example shows how can you write the nodes directly
4.1202 + /// to the standard output.
4.1203 + ///\code
4.1204 + /// typedef IdMap<Graph, Edge> EdgeIdMap;
4.1205 + /// EdgeIdMap edgeId(graph);
4.1206 + ///
4.1207 + /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
4.1208 + /// EdgeIdFunctor edgeIdFunctor(edgeId);
4.1209 + ///
4.1210 + /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
4.1211 + /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
4.1212 + ///
4.1213 + /// prim(graph, cost, writerMap);
4.1214 + ///\endcode
4.1215 + template <typename _Iterator,
4.1216 + typename _Functor =
4.1217 + _maps_bits::Identity<typename _maps_bits::
4.1218 + IteratorTraits<_Iterator>::Value> >
4.1219 + class StoreBoolMap {
4.1220 + public:
4.1221 + typedef _Iterator Iterator;
4.1222 +
4.1223 + typedef typename _Functor::argument_type Key;
4.1224 + typedef bool Value;
4.1225 +
4.1226 + typedef _Functor Functor;
4.1227 +
4.1228 + /// Constructor
4.1229 + StoreBoolMap(Iterator it, const Functor& functor = Functor())
4.1230 + : _begin(it), _end(it), _functor(functor) {}
4.1231 +
4.1232 + /// Gives back the given iterator set for the first time.
4.1233 + Iterator begin() const {
4.1234 + return _begin;
4.1235 + }
4.1236 +
4.1237 + /// Gives back the iterator after the last set operation.
4.1238 + Iterator end() const {
4.1239 + return _end;
4.1240 + }
4.1241 +
4.1242 + /// Setter function of the map
4.1243 + void set(const Key& key, Value value) const {
4.1244 + if (value) {
4.1245 + *_end++ = _functor(key);
4.1246 + }
4.1247 + }
4.1248 +
4.1249 + private:
4.1250 + Iterator _begin;
4.1251 + mutable Iterator _end;
4.1252 + Functor _functor;
4.1253 + };
4.1254 +
4.1255 + /// \brief Writable bool map for store each true assigned elements in
4.1256 + /// a back insertable container.
4.1257 + ///
4.1258 + /// Writable bool map for store each true assigned elements in a back
4.1259 + /// insertable container. It will push back all the keys set to true into
4.1260 + /// the container. It can be used to retrieve the items into a standard
4.1261 + /// container. The next example shows how can you store the undirected
4.1262 + /// arcs in a vector with prim algorithm.
4.1263 + ///
4.1264 + ///\code
4.1265 + /// vector<Edge> span_tree_edges;
4.1266 + /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
4.1267 + /// prim(graph, cost, inserter_map);
4.1268 + ///\endcode
4.1269 + template <typename Container,
4.1270 + typename Functor =
4.1271 + _maps_bits::Identity<typename Container::value_type> >
4.1272 + class BackInserterBoolMap {
4.1273 + public:
4.1274 + typedef typename Container::value_type Key;
4.1275 + typedef bool Value;
4.1276 +
4.1277 + /// Constructor
4.1278 + BackInserterBoolMap(Container& _container,
4.1279 + const Functor& _functor = Functor())
4.1280 + : container(_container), functor(_functor) {}
4.1281 +
4.1282 + /// Setter function of the map
4.1283 + void set(const Key& key, Value value) {
4.1284 + if (value) {
4.1285 + container.push_back(functor(key));
4.1286 + }
4.1287 + }
4.1288 +
4.1289 + private:
4.1290 + Container& container;
4.1291 + Functor functor;
4.1292 + };
4.1293 +
4.1294 + /// \brief Writable bool map for store each true assigned elements in
4.1295 + /// a front insertable container.
4.1296 + ///
4.1297 + /// Writable bool map for store each true assigned elements in a front
4.1298 + /// insertable container. It will push front all the keys set to \c true into
4.1299 + /// the container. For example see the BackInserterBoolMap.
4.1300 + template <typename Container,
4.1301 + typename Functor =
4.1302 + _maps_bits::Identity<typename Container::value_type> >
4.1303 + class FrontInserterBoolMap {
4.1304 + public:
4.1305 + typedef typename Container::value_type Key;
4.1306 + typedef bool Value;
4.1307 +
4.1308 + /// Constructor
4.1309 + FrontInserterBoolMap(Container& _container,
4.1310 + const Functor& _functor = Functor())
4.1311 + : container(_container), functor(_functor) {}
4.1312 +
4.1313 + /// Setter function of the map
4.1314 + void set(const Key& key, Value value) {
4.1315 + if (value) {
4.1316 + container.push_front(key);
4.1317 + }
4.1318 + }
4.1319 +
4.1320 + private:
4.1321 + Container& container;
4.1322 + Functor functor;
4.1323 + };
4.1324 +
4.1325 + /// \brief Writable bool map for store each true assigned elements in
4.1326 + /// an insertable container.
4.1327 + ///
4.1328 + /// Writable bool map for store each true assigned elements in an
4.1329 + /// insertable container. It will insert all the keys set to \c true into
4.1330 + /// the container. If you want to store the cut arcs of the strongly
4.1331 + /// connected components in a set you can use the next code:
4.1332 + ///
4.1333 + ///\code
4.1334 + /// set<Arc> cut_arcs;
4.1335 + /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
4.1336 + /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
4.1337 + ///\endcode
4.1338 + template <typename Container,
4.1339 + typename Functor =
4.1340 + _maps_bits::Identity<typename Container::value_type> >
4.1341 + class InserterBoolMap {
4.1342 + public:
4.1343 + typedef typename Container::value_type Key;
4.1344 + typedef bool Value;
4.1345 +
4.1346 + /// Constructor
4.1347 + InserterBoolMap(Container& _container, typename Container::iterator _it,
4.1348 + const Functor& _functor = Functor())
4.1349 + : container(_container), it(_it), functor(_functor) {}
4.1350 +
4.1351 + /// Constructor
4.1352 + InserterBoolMap(Container& _container, const Functor& _functor = Functor())
4.1353 + : container(_container), it(_container.end()), functor(_functor) {}
4.1354 +
4.1355 + /// Setter function of the map
4.1356 + void set(const Key& key, Value value) {
4.1357 + if (value) {
4.1358 + it = container.insert(it, key);
4.1359 + ++it;
4.1360 + }
4.1361 + }
4.1362 +
4.1363 + private:
4.1364 + Container& container;
4.1365 + typename Container::iterator it;
4.1366 + Functor functor;
4.1367 + };
4.1368 +
4.1369 + /// \brief Fill the true set elements with a given value.
4.1370 + ///
4.1371 + /// Writable bool map to fill the elements set to \c true with a given value.
4.1372 + /// The value can set
4.1373 + /// the container.
4.1374 + ///
4.1375 + /// The next code finds the connected components of the undirected digraph
4.1376 + /// and stores it in the \c comp map:
4.1377 + ///\code
4.1378 + /// typedef Graph::NodeMap<int> ComponentMap;
4.1379 + /// ComponentMap comp(graph);
4.1380 + /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
4.1381 + /// ComponentFillerMap filler(comp, 0);
4.1382 + ///
4.1383 + /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
4.1384 + /// dfs.processedMap(filler);
4.1385 + /// dfs.init();
4.1386 + /// for (NodeIt it(graph); it != INVALID; ++it) {
4.1387 + /// if (!dfs.reached(it)) {
4.1388 + /// dfs.addSource(it);
4.1389 + /// dfs.start();
4.1390 + /// ++filler.fillValue();
4.1391 + /// }
4.1392 + /// }
4.1393 + ///\endcode
4.1394 + template <typename Map>
4.1395 + class FillBoolMap {
4.1396 + public:
4.1397 + typedef typename Map::Key Key;
4.1398 + typedef bool Value;
4.1399 +
4.1400 + /// Constructor
4.1401 + FillBoolMap(Map& _map, const typename Map::Value& _fill)
4.1402 + : map(_map), fill(_fill) {}
4.1403 +
4.1404 + /// Constructor
4.1405 + FillBoolMap(Map& _map)
4.1406 + : map(_map), fill() {}
4.1407 +
4.1408 + /// Gives back the current fill value
4.1409 + const typename Map::Value& fillValue() const {
4.1410 + return fill;
4.1411 + }
4.1412 +
4.1413 + /// Gives back the current fill value
4.1414 + typename Map::Value& fillValue() {
4.1415 + return fill;
4.1416 + }
4.1417 +
4.1418 + /// Sets the current fill value
4.1419 + void fillValue(const typename Map::Value& _fill) {
4.1420 + fill = _fill;
4.1421 + }
4.1422 +
4.1423 + /// Setter function of the map
4.1424 + void set(const Key& key, Value value) {
4.1425 + if (value) {
4.1426 + map.set(key, fill);
4.1427 + }
4.1428 + }
4.1429 +
4.1430 + private:
4.1431 + Map& map;
4.1432 + typename Map::Value fill;
4.1433 + };
4.1434 +
4.1435 +
4.1436 + /// \brief Writable bool map which stores for each true assigned elements
4.1437 + /// the setting order number.
4.1438 + ///
4.1439 + /// Writable bool map which stores for each true assigned elements
4.1440 + /// the setting order number. It make easy to calculate the leaving
4.1441 + /// order of the nodes in the \c Dfs algorithm.
4.1442 + ///
4.1443 + ///\code
4.1444 + /// typedef Digraph::NodeMap<int> OrderMap;
4.1445 + /// OrderMap order(digraph);
4.1446 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
4.1447 + /// OrderSetterMap setter(order);
4.1448 + /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
4.1449 + /// dfs.processedMap(setter);
4.1450 + /// dfs.init();
4.1451 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
4.1452 + /// if (!dfs.reached(it)) {
4.1453 + /// dfs.addSource(it);
4.1454 + /// dfs.start();
4.1455 + /// }
4.1456 + /// }
4.1457 + ///\endcode
4.1458 + ///
4.1459 + /// The discovering order can be stored a little harder because the
4.1460 + /// ReachedMap should be readable in the dfs algorithm but the setting
4.1461 + /// order map is not readable. Now we should use the fork map:
4.1462 + ///
4.1463 + ///\code
4.1464 + /// typedef Digraph::NodeMap<int> OrderMap;
4.1465 + /// OrderMap order(digraph);
4.1466 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
4.1467 + /// OrderSetterMap setter(order);
4.1468 + /// typedef Digraph::NodeMap<bool> StoreMap;
4.1469 + /// StoreMap store(digraph);
4.1470 + ///
4.1471 + /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
4.1472 + /// ReachedMap reached(store, setter);
4.1473 + ///
4.1474 + /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
4.1475 + /// dfs.reachedMap(reached);
4.1476 + /// dfs.init();
4.1477 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
4.1478 + /// if (!dfs.reached(it)) {
4.1479 + /// dfs.addSource(it);
4.1480 + /// dfs.start();
4.1481 + /// }
4.1482 + /// }
4.1483 + ///\endcode
4.1484 + template <typename Map>
4.1485 + class SettingOrderBoolMap {
4.1486 + public:
4.1487 + typedef typename Map::Key Key;
4.1488 + typedef bool Value;
4.1489 +
4.1490 + /// Constructor
4.1491 + SettingOrderBoolMap(Map& _map)
4.1492 + : map(_map), counter(0) {}
4.1493 +
4.1494 + /// Number of set operations.
4.1495 + int num() const {
4.1496 + return counter;
4.1497 + }
4.1498 +
4.1499 + /// Setter function of the map
4.1500 + void set(const Key& key, Value value) {
4.1501 + if (value) {
4.1502 + map.set(key, counter++);
4.1503 + }
4.1504 + }
4.1505 +
4.1506 + private:
4.1507 + Map& map;
4.1508 + int counter;
4.1509 + };
4.1510 +
4.1511 + /// @}
4.1512 +}
4.1513 +
4.1514 +#endif // LEMON_MAPS_H
5.1 --- a/test/Makefile.am Thu Dec 20 15:59:06 2007 +0000
5.2 +++ b/test/Makefile.am Sat Dec 22 12:35:00 2007 +0000
5.3 @@ -5,11 +5,13 @@
5.4 test/test_tools.h
5.5
5.6 check_PROGRAMS += \
5.7 + test/maps_test \
5.8 test/test_tools_fail \
5.9 test/test_tools_pass
5.10
5.11 TESTS += $(check_PROGRAMS)
5.12 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
5.13
5.14 +test_maps_test_SOURCES = test/maps_test.cc
5.15 test_test_tools_fail_SOURCES = test/test_tools_fail.cc
5.16 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 Sat Dec 22 12:35:00 2007 +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 +}