# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1198326900 0
# Node ID 751cd8f9bb1c4bc2d28581ea7c66ef72e37b8da1
# Parent 4d461e9867da55e340da4353b59a73b1a1875451
Port general map related stuff from svn -r3424 + minor changes
- Do automatic name changes in lemon/maps.h (only affects doc)
- Do not use MapTraits in ComposeMap
diff -r 4d461e9867da -r 751cd8f9bb1c lemon/Makefile.am
--- a/lemon/Makefile.am Thu Dec 20 15:59:06 2007 +0000
+++ b/lemon/Makefile.am Sat Dec 22 12:35:00 2007 +0000
@@ -13,11 +13,14 @@
lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
lemon_HEADERS += \
+ lemon/concept_check.h \
lemon/list_graph.h \
+ lemon/maps.h \
lemon/tolerance.h
bits_HEADERS += \
lemon/bits/invalid.h \
lemon/bits/utility.h
-concept_HEADERS +=
+concept_HEADERS += \
+ lemon/concepts/maps.h
diff -r 4d461e9867da -r 751cd8f9bb1c lemon/concept_check.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/concept_check.h Sat Dec 22 12:35:00 2007 +0000
@@ -0,0 +1,105 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2007
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+// Modified for use in LEMON.
+// We should really consider using Boost...
+
+//
+// (C) Copyright Jeremy Siek 2000.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// Revision History:
+// 05 May 2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
+// 02 April 2001: Removed limits header altogether. (Jeremy Siek)
+// 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
+//
+
+// See http://www.boost.org/libs/concept_check for documentation.
+
+#ifndef LEMON_BOOST_CONCEPT_CHECKS_HPP
+#define LEMON_BOOST_CONCEPT_CHECKS_HPP
+
+namespace lemon {
+
+ /*
+ "inline" is used for ignore_unused_variable_warning()
+ and function_requires() to make sure there is no
+ overtarget with g++.
+ */
+
+ template <class T> inline void ignore_unused_variable_warning(const T&) { }
+
+ template <class Concept>
+ inline void function_requires()
+ {
+#if !defined(NDEBUG)
+ void (Concept::*x)() = & Concept::constraints;
+ ignore_unused_variable_warning(x);
+#endif
+ }
+
+ template <typename Concept, typename Type>
+ inline void checkConcept() {
+#if !defined(NDEBUG)
+ typedef typename Concept::template Constraints<Type> ConceptCheck;
+ void (ConceptCheck::*x)() = & ConceptCheck::constraints;
+ ignore_unused_variable_warning(x);
+#endif
+ }
+
+#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
+ typedef void (ns::concept <type_var>::* func##type_var##concept)(); \
+ template <func##type_var##concept Tp1_> \
+ struct concept_checking_##type_var##concept { }; \
+ typedef concept_checking_##type_var##concept< \
+ BOOST_FPTR ns::concept<type_var>::constraints> \
+ concept_checking_typedef_##type_var##concept
+
+#define BOOST_CLASS_REQUIRE2(type_var1, type_var2, ns, concept) \
+ typedef void (ns::concept <type_var1,type_var2>::* \
+ func##type_var1##type_var2##concept)(); \
+ template <func##type_var1##type_var2##concept Tp1_> \
+ struct concept_checking_##type_var1##type_var2##concept { }; \
+ typedef concept_checking_##type_var1##type_var2##concept< \
+ BOOST_FPTR ns::concept<type_var1,type_var2>::constraints> \
+ concept_checking_typedef_##type_var1##type_var2##concept
+
+#define BOOST_CLASS_REQUIRE3(tv1, tv2, tv3, ns, concept) \
+ typedef void (ns::concept <tv1,tv2,tv3>::* \
+ func##tv1##tv2##tv3##concept)(); \
+ template <func##tv1##tv2##tv3##concept Tp1_> \
+ struct concept_checking_##tv1##tv2##tv3##concept { }; \
+ typedef concept_checking_##tv1##tv2##tv3##concept< \
+ BOOST_FPTR ns::concept<tv1,tv2,tv3>::constraints> \
+ concept_checking_typedef_##tv1##tv2##tv3##concept
+
+#define BOOST_CLASS_REQUIRE4(tv1, tv2, tv3, tv4, ns, concept) \
+ typedef void (ns::concept <tv1,tv2,tv3,tv4>::* \
+ func##tv1##tv2##tv3##tv4##concept)(); \
+ template <func##tv1##tv2##tv3##tv4##concept Tp1_> \
+ struct concept_checking_##tv1##tv2##tv3##tv4##concept { }; \
+ typedef concept_checking_##tv1##tv2##tv3##tv4##concept< \
+ BOOST_FPTR ns::concept<tv1,tv2,tv3,tv4>::constraints> \
+ concept_checking_typedef_##tv1##tv2##tv3##tv4##concept
+
+
+} // namespace lemon
+
+#endif // LEMON_BOOST_CONCEPT_CHECKS_HPP
diff -r 4d461e9867da -r 751cd8f9bb1c lemon/concepts/maps.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/concepts/maps.h Sat Dec 22 12:35:00 2007 +0000
@@ -0,0 +1,194 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2007
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_CONCEPT_MAPS_H
+#define LEMON_CONCEPT_MAPS_H
+
+#include <lemon/bits/utility.h>
+#include <lemon/concept_check.h>
+
+///\ingroup concept
+///\file
+///\brief Map concepts checking classes for testing and documenting.
+
+namespace lemon {
+
+ namespace concepts {
+
+ /// \addtogroup concept
+ /// @{
+
+ /// Readable map concept
+ template<typename K, typename T>
+ class ReadMap
+ {
+ public:
+ /// Map's key type.
+ typedef K Key;
+ /// Map's value type. (The type of objects associated with the keys).
+ typedef T Value;
+
+ /// Returns the value associated with a key.
+
+ /// \bug Value should n't need to be default constructible.
+ ///
+ Value operator[](const Key &) const {return Value();}
+
+ template<typename _ReadMap>
+ struct Constraints {
+
+ void constraints() {
+ Value val = m[key];
+ val = m[key];
+ typename _ReadMap::Value own_val = m[own_key];
+ own_val = m[own_key];
+
+ ignore_unused_variable_warning(val);
+ ignore_unused_variable_warning(own_val);
+ ignore_unused_variable_warning(key);
+ }
+ Key& key;
+ typename _ReadMap::Key& own_key;
+ _ReadMap& m;
+ };
+
+ };
+
+
+ /// Writable map concept
+ template<typename K, typename T>
+ class WriteMap
+ {
+ public:
+ /// Map's key type.
+ typedef K Key;
+ /// Map's value type. (The type of objects associated with the keys).
+ typedef T Value;
+
+ /// Sets the value associated with a key.
+ void set(const Key &,const Value &) {}
+
+ ///Default constructor
+ WriteMap() {}
+
+ template <typename _WriteMap>
+ struct Constraints {
+ void constraints() {
+ // No constraints for constructor.
+ m.set(key, val);
+ m.set(own_key, own_val);
+ ignore_unused_variable_warning(key);
+ ignore_unused_variable_warning(val);
+ ignore_unused_variable_warning(own_key);
+ ignore_unused_variable_warning(own_val);
+ }
+
+ Value& val;
+ typename _WriteMap::Value own_val;
+ Key& key;
+ typename _WriteMap::Key& own_key;
+ _WriteMap& m;
+
+ };
+ };
+
+ ///Read/Writable map concept
+ template<typename K, typename T>
+ class ReadWriteMap : public ReadMap<K,T>,
+ public WriteMap<K,T>
+ {
+ public:
+ /// Map's key type.
+ typedef K Key;
+ /// Map's value type. (The type of objects associated with the keys).
+ typedef T Value;
+
+ /// Returns the value associated with a key.
+ Value operator[](const Key &) const {return Value();}
+ /// Sets the value associated with a key.
+ void set(const Key & ,const Value &) {}
+
+ template<typename _ReadWriteMap>
+ struct Constraints {
+ void constraints() {
+ checkConcept<ReadMap<K, T>, _ReadWriteMap >();
+ checkConcept<WriteMap<K, T>, _ReadWriteMap >();
+ }
+ };
+ };
+
+
+ ///Dereferable map concept
+ template<typename K, typename T, typename R, typename CR>
+ class ReferenceMap : public ReadWriteMap<K,T>
+ {
+ public:
+ /// Tag for reference maps.
+ typedef True ReferenceMapTag;
+ /// Map's key type.
+ typedef K Key;
+ /// Map's value type. (The type of objects associated with the keys).
+ typedef T Value;
+ /// Map's reference type.
+ typedef R Reference;
+ /// Map's const reference type.
+ typedef CR ConstReference;
+
+ protected:
+ Value tmp;
+ public:
+
+ ///Returns a reference to the value associated to a key.
+ Reference operator[](const Key &) { return tmp; }
+ ///Returns a const reference to the value associated to a key.
+ ConstReference operator[](const Key &) const
+ { return tmp; }
+ /// Sets the value associated with a key.
+ void set(const Key &k,const Value &t) { operator[](k)=t; }
+
+ // \todo rethink this concept
+ template<typename _ReferenceMap>
+ struct ReferenceMapConcept {
+
+ void constraints() {
+ checkConcept<ReadWriteMap, _ReferenceMap >();
+ m[key] = val;
+ val = m[key];
+ m[key] = ref;
+ ref = m[key];
+ m[own_key] = own_val;
+ own_val = m[own_key];
+ m[own_key] = own_ref;
+ own_ref = m[own_key];
+ }
+
+ typename _ReferenceMap::Key& own_key;
+ typename _ReferenceMap::Value& own_val;
+ typename _ReferenceMap::Reference& own_ref;
+ Key& key;
+ Value& val;
+ Reference& ref;
+ _ReferenceMap& m;
+ };
+ };
+
+ // @}
+
+ } //namespace concepts
+} //namespace lemon
+#endif // LEMON_CONCEPT_MAPS_H
diff -r 4d461e9867da -r 751cd8f9bb1c lemon/maps.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/maps.h Sat Dec 22 12:35:00 2007 +0000
@@ -0,0 +1,1511 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2007
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_MAPS_H
+#define LEMON_MAPS_H
+
+#include <iterator>
+#include <functional>
+#include <vector>
+
+#include <lemon/bits/utility.h>
+// #include <lemon/bits/traits.h>
+
+///\file
+///\ingroup maps
+///\brief Miscellaneous property maps
+///
+#include <map>
+
+namespace lemon {
+
+ /// \addtogroup maps
+ /// @{
+
+ /// Base class of maps.
+
+ /// Base class of maps.
+ /// It provides the necessary <tt>typedef</tt>s required by the map concept.
+ template<typename K, typename T>
+ class MapBase {
+ public:
+ ///\e
+ typedef K Key;
+ ///\e
+ typedef T Value;
+ };
+
+ /// Null map. (a.k.a. DoNothingMap)
+
+ /// If you have to provide a map only for its type definitions,
+ /// or if you have to provide a writable map, but
+ /// data written to it will sent to <tt>/dev/null</tt>...
+ template<typename K, typename T>
+ class NullMap : public MapBase<K, T> {
+ public:
+ typedef MapBase<K, T> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ /// Gives back a default constructed element.
+ T operator[](const K&) const { return T(); }
+ /// Absorbs the value.
+ void set(const K&, const T&) {}
+ };
+
+ template <typename K, typename V>
+ NullMap<K, V> nullMap() {
+ return NullMap<K, V>();
+ }
+
+
+ /// Constant map.
+
+ /// This is a readable map which assigns a specified value to each key.
+ /// In other aspects it is equivalent to the \c NullMap.
+ template<typename K, typename T>
+ class ConstMap : public MapBase<K, T> {
+ private:
+ T v;
+ public:
+
+ typedef MapBase<K, T> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ /// Default constructor
+
+ /// The value of the map will be uninitialized.
+ /// (More exactly it will be default constructed.)
+ ConstMap() {}
+ ///\e
+
+ /// \param _v The initial value of the map.
+ ///
+ ConstMap(const T &_v) : v(_v) {}
+
+ ///\e
+ T operator[](const K&) const { return v; }
+
+ ///\e
+ void setAll(const T &t) {
+ v = t;
+ }
+
+ template<typename T1>
+ struct rebind {
+ typedef ConstMap<K, T1> other;
+ };
+
+ template<typename T1>
+ ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
+ };
+
+ ///Returns a \c ConstMap class
+
+ ///This function just returns a \c ConstMap class.
+ ///\relates ConstMap
+ template<typename K, typename V>
+ inline ConstMap<K, V> constMap(const V &v) {
+ return ConstMap<K, V>(v);
+ }
+
+
+ template<typename T, T v>
+ struct Const { };
+
+ /// Constant map with inlined constant value.
+
+ /// This is a readable map which assigns a specified value to each key.
+ /// In other aspects it is equivalent to the \c NullMap.
+ template<typename K, typename V, V v>
+ class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
+ public:
+ typedef MapBase<K, V> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ConstMap() { }
+ ///\e
+ V operator[](const K&) const { return v; }
+ ///\e
+ void set(const K&, const V&) { }
+ };
+
+ ///Returns a \c ConstMap class
+
+ ///This function just returns a \c ConstMap class with inlined value.
+ ///\relates ConstMap
+ template<typename K, typename V, V v>
+ inline ConstMap<K, Const<V, v> > constMap() {
+ return ConstMap<K, Const<V, v> >();
+ }
+
+ ///Map based on std::map
+
+ ///This is essentially a wrapper for \c std::map. With addition that
+ ///you can specify a default value different from \c Value() .
+ template <typename K, typename T, typename Compare = std::less<K> >
+ class StdMap {
+ template <typename K1, typename T1, typename C1>
+ friend class StdMap;
+ public:
+
+ typedef True ReferenceMapTag;
+ ///\e
+ typedef K Key;
+ ///\e
+ typedef T Value;
+ ///\e
+ typedef T& Reference;
+ ///\e
+ typedef const T& ConstReference;
+
+ private:
+
+ typedef std::map<K, T, Compare> Map;
+ Value _value;
+ Map _map;
+
+ public:
+
+ /// Constructor with specified default value
+ StdMap(const T& value = T()) : _value(value) {}
+ /// \brief Constructs the map from an appropriate std::map, and explicitly
+ /// specifies a default value.
+ template <typename T1, typename Comp1>
+ StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
+ : _map(map.begin(), map.end()), _value(value) {}
+
+ /// \brief Constructs a map from an other StdMap.
+ template<typename T1, typename Comp1>
+ StdMap(const StdMap<Key, T1, Comp1> &c)
+ : _map(c._map.begin(), c._map.end()), _value(c._value) {}
+
+ private:
+
+ StdMap& operator=(const StdMap&);
+
+ public:
+
+ ///\e
+ Reference operator[](const Key &k) {
+ typename Map::iterator it = _map.lower_bound(k);
+ if (it != _map.end() && !_map.key_comp()(k, it->first))
+ return it->second;
+ else
+ return _map.insert(it, std::make_pair(k, _value))->second;
+ }
+
+ /// \e
+ ConstReference operator[](const Key &k) const {
+ typename Map::const_iterator it = _map.find(k);
+ if (it != _map.end())
+ return it->second;
+ else
+ return _value;
+ }
+
+ /// \e
+ void set(const Key &k, const T &t) {
+ typename Map::iterator it = _map.lower_bound(k);
+ if (it != _map.end() && !_map.key_comp()(k, it->first))
+ it->second = t;
+ else
+ _map.insert(it, std::make_pair(k, t));
+ }
+
+ /// \e
+ void setAll(const T &t) {
+ _value = t;
+ _map.clear();
+ }
+
+ template <typename T1, typename C1 = std::less<T1> >
+ struct rebind {
+ typedef StdMap<Key, T1, C1> other;
+ };
+ };
+
+ /// \brief Map for storing values for the range \c [0..size-1] range keys
+ ///
+ /// The current map has the \c [0..size-1] keyset and the values
+ /// are stored in a \c std::vector<T> container. It can be used with
+ /// some data structures, for example \c UnionFind, \c BinHeap, when
+ /// the used items are small integer numbers.
+ template <typename T>
+ class IntegerMap {
+
+ template <typename T1>
+ friend class IntegerMap;
+
+ public:
+
+ typedef True ReferenceMapTag;
+ ///\e
+ typedef int Key;
+ ///\e
+ typedef T Value;
+ ///\e
+ typedef T& Reference;
+ ///\e
+ typedef const T& ConstReference;
+
+ private:
+
+ typedef std::vector<T> Vector;
+ Vector _vector;
+
+ public:
+
+ /// Constructor with specified default value
+ IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
+
+ /// \brief Constructs the map from an appropriate std::vector.
+ template <typename T1>
+ IntegerMap(const std::vector<T1>& vector)
+ : _vector(vector.begin(), vector.end()) {}
+
+ /// \brief Constructs a map from an other IntegerMap.
+ template <typename T1>
+ IntegerMap(const IntegerMap<T1> &c)
+ : _vector(c._vector.begin(), c._vector.end()) {}
+
+ /// \brief Resize the container
+ void resize(int size, const T& value = T()) {
+ _vector.resize(size, value);
+ }
+
+ private:
+
+ IntegerMap& operator=(const IntegerMap&);
+
+ public:
+
+ ///\e
+ Reference operator[](Key k) {
+ return _vector[k];
+ }
+
+ /// \e
+ ConstReference operator[](Key k) const {
+ return _vector[k];
+ }
+
+ /// \e
+ void set(const Key &k, const T& t) {
+ _vector[k] = t;
+ }
+
+ };
+
+ /// @}
+
+ /// \addtogroup map_adaptors
+ /// @{
+
+ /// \brief Identity mapping.
+ ///
+ /// This mapping gives back the given key as value without any
+ /// modification.
+ template <typename T>
+ class IdentityMap : public MapBase<T, T> {
+ public:
+ typedef MapBase<T, T> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ /// \e
+ const T& operator[](const T& t) const {
+ return t;
+ }
+ };
+
+ ///Returns an \c IdentityMap class
+
+ ///This function just returns an \c IdentityMap class.
+ ///\relates IdentityMap
+ template<typename T>
+ inline IdentityMap<T> identityMap() {
+ return IdentityMap<T>();
+ }
+
+
+ ///Convert the \c Value of a map to another type.
+
+ ///This \c concepts::ReadMap "read only map"
+ ///converts the \c Value of a maps to type \c T.
+ ///Its \c Key is inherited from \c M.
+ template <typename M, typename T>
+ class ConvertMap : public MapBase<typename M::Key, T> {
+ const M& m;
+ public:
+ typedef MapBase<typename M::Key, T> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+
+ ///Constructor
+ ///\param _m is the underlying map
+ ConvertMap(const M &_m) : m(_m) {};
+
+ /// \brief The subscript operator.
+ ///
+ /// The subscript operator.
+ /// \param k The key
+ /// \return The target of the arc
+ Value operator[](const Key& k) const {return m[k];}
+ };
+
+ ///Returns an \c ConvertMap class
+
+ ///This function just returns an \c ConvertMap class.
+ ///\relates ConvertMap
+ template<typename T, typename M>
+ inline ConvertMap<M, T> convertMap(const M &m) {
+ return ConvertMap<M, T>(m);
+ }
+
+ ///Simple wrapping of the map
+
+ ///This \c concepts::ReadMap "read only map" returns the simple
+ ///wrapping of the given map. Sometimes the reference maps cannot be
+ ///combined with simple read maps. This map adaptor wraps the given
+ ///map to simple read map.
+ template<typename M>
+ class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
+ const M& m;
+
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ SimpleMap(const M &_m) : m(_m) {};
+ ///\e
+ Value operator[](Key k) const {return m[k];}
+ };
+
+ ///Simple writeable wrapping of the map
+
+ ///This \c concepts::ReadMap "read only map" returns the simple
+ ///wrapping of the given map. Sometimes the reference maps cannot be
+ ///combined with simple read-write maps. This map adaptor wraps the
+ ///given map to simple read-write map.
+ template<typename M>
+ class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
+ M& m;
+
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ SimpleWriteMap(M &_m) : m(_m) {};
+ ///\e
+ Value operator[](Key k) const {return m[k];}
+ ///\e
+ void set(Key k, const Value& c) { m.set(k, c); }
+ };
+
+ ///Sum of two maps
+
+ ///This \c concepts::ReadMap "read only map" returns the sum of the two
+ ///given maps. Its \c Key and \c Value will be inherited from \c M1.
+ ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
+
+ template<typename M1, typename M2>
+ class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
+ const M1& m1;
+ const M2& m2;
+
+ public:
+ typedef MapBase<typename M1::Key, typename M1::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
+ ///\e
+ Value operator[](Key k) const {return m1[k]+m2[k];}
+ };
+
+ ///Returns an \c AddMap class
+
+ ///This function just returns an \c AddMap class.
+ ///\todo How to call these type of functions?
+ ///
+ ///\relates AddMap
+ template<typename M1, typename M2>
+ inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
+ return AddMap<M1, M2>(m1,m2);
+ }
+
+ ///Shift a map with a constant.
+
+ ///This \c concepts::ReadMap "read only map" returns the sum of the
+ ///given map and a constant value.
+ ///Its \c Key and \c Value is inherited from \c M.
+ ///
+ ///Actually,
+ ///\code
+ /// ShiftMap<X> sh(x,v);
+ ///\endcode
+ ///is equivalent with
+ ///\code
+ /// ConstMap<X::Key, X::Value> c_tmp(v);
+ /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
+ ///\endcode
+ template<typename M, typename C = typename M::Value>
+ class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
+ const M& m;
+ C v;
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+
+ ///Constructor
+ ///\param _m is the undelying map
+ ///\param _v is the shift value
+ ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
+ ///\e
+ Value operator[](Key k) const {return m[k] + v;}
+ };
+
+ ///Shift a map with a constant.
+
+ ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
+ ///given map and a constant value. It makes also possible to write the map.
+ ///Its \c Key and \c Value is inherited from \c M.
+ ///
+ ///Actually,
+ ///\code
+ /// ShiftMap<X> sh(x,v);
+ ///\endcode
+ ///is equivalent with
+ ///\code
+ /// ConstMap<X::Key, X::Value> c_tmp(v);
+ /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
+ ///\endcode
+ template<typename M, typename C = typename M::Value>
+ class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
+ M& m;
+ C v;
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+
+ ///Constructor
+ ///\param _m is the undelying map
+ ///\param _v is the shift value
+ ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
+ /// \e
+ Value operator[](Key k) const {return m[k] + v;}
+ /// \e
+ void set(Key k, const Value& c) { m.set(k, c - v); }
+ };
+
+ ///Returns an \c ShiftMap class
+
+ ///This function just returns an \c ShiftMap class.
+ ///\relates ShiftMap
+ template<typename M, typename C>
+ inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
+ return ShiftMap<M, C>(m,v);
+ }
+
+ template<typename M, typename C>
+ inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
+ return ShiftWriteMap<M, C>(m,v);
+ }
+
+ ///Difference of two maps
+
+ ///This \c concepts::ReadMap "read only map" returns the difference
+ ///of the values of the two
+ ///given maps. Its \c Key and \c Value will be inherited from \c M1.
+ ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
+
+ template<typename M1, typename M2>
+ class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
+ const M1& m1;
+ const M2& m2;
+ public:
+ typedef MapBase<typename M1::Key, typename M1::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
+ /// \e
+ Value operator[](Key k) const {return m1[k]-m2[k];}
+ };
+
+ ///Returns a \c SubMap class
+
+ ///This function just returns a \c SubMap class.
+ ///
+ ///\relates SubMap
+ template<typename M1, typename M2>
+ inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
+ return SubMap<M1, M2>(m1, m2);
+ }
+
+ ///Product of two maps
+
+ ///This \c concepts::ReadMap "read only map" returns the product of the
+ ///values of the two
+ ///given
+ ///maps. Its \c Key and \c Value will be inherited from \c M1.
+ ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
+
+ template<typename M1, typename M2>
+ class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
+ const M1& m1;
+ const M2& m2;
+ public:
+ typedef MapBase<typename M1::Key, typename M1::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
+ /// \e
+ Value operator[](Key k) const {return m1[k]*m2[k];}
+ };
+
+ ///Returns a \c MulMap class
+
+ ///This function just returns a \c MulMap class.
+ ///\relates MulMap
+ template<typename M1, typename M2>
+ inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
+ return MulMap<M1, M2>(m1,m2);
+ }
+
+ ///Scales a maps with a constant.
+
+ ///This \c concepts::ReadMap "read only map" returns the value of the
+ ///given map multiplied from the left side with a constant value.
+ ///Its \c Key and \c Value is inherited from \c M.
+ ///
+ ///Actually,
+ ///\code
+ /// ScaleMap<X> sc(x,v);
+ ///\endcode
+ ///is equivalent with
+ ///\code
+ /// ConstMap<X::Key, X::Value> c_tmp(v);
+ /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
+ ///\endcode
+ template<typename M, typename C = typename M::Value>
+ class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
+ const M& m;
+ C v;
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+
+ ///Constructor
+ ///\param _m is the undelying map
+ ///\param _v is the scaling value
+ ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
+ /// \e
+ Value operator[](Key k) const {return v * m[k];}
+ };
+
+ ///Scales a maps with a constant.
+
+ ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
+ ///given map multiplied from the left side with a constant value. It can
+ ///be used as write map also if the given multiplier is not zero.
+ ///Its \c Key and \c Value is inherited from \c M.
+ template<typename M, typename C = typename M::Value>
+ class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
+ M& m;
+ C v;
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+
+ ///Constructor
+ ///\param _m is the undelying map
+ ///\param _v is the scaling value
+ ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
+ /// \e
+ Value operator[](Key k) const {return v * m[k];}
+ /// \e
+ void set(Key k, const Value& c) { m.set(k, c / v);}
+ };
+
+ ///Returns an \c ScaleMap class
+
+ ///This function just returns an \c ScaleMap class.
+ ///\relates ScaleMap
+ template<typename M, typename C>
+ inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
+ return ScaleMap<M, C>(m,v);
+ }
+
+ template<typename M, typename C>
+ inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
+ return ScaleWriteMap<M, C>(m,v);
+ }
+
+ ///Quotient of two maps
+
+ ///This \c concepts::ReadMap "read only map" returns the quotient of the
+ ///values of the two
+ ///given maps. Its \c Key and \c Value will be inherited from \c M1.
+ ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
+
+ template<typename M1, typename M2>
+ class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
+ const M1& m1;
+ const M2& m2;
+ public:
+ typedef MapBase<typename M1::Key, typename M1::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
+ /// \e
+ Value operator[](Key k) const {return m1[k]/m2[k];}
+ };
+
+ ///Returns a \c DivMap class
+
+ ///This function just returns a \c DivMap class.
+ ///\relates DivMap
+ template<typename M1, typename M2>
+ inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
+ return DivMap<M1, M2>(m1,m2);
+ }
+
+ ///Composition of two maps
+
+ ///This \c concepts::ReadMap "read only map" returns the composition of
+ ///two
+ ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
+ ///of \c M2,
+ ///then for
+ ///\code
+ /// ComposeMap<M1, M2> cm(m1,m2);
+ ///\endcode
+ /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
+ ///
+ ///Its \c Key is inherited from \c M2 and its \c Value is from
+ ///\c M1.
+ ///The \c M2::Value must be convertible to \c M1::Key.
+ ///\todo Check the requirements.
+ template <typename M1, typename M2>
+ class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
+ const M1& m1;
+ const M2& m2;
+ public:
+ typedef MapBase<typename M2::Key, typename M1::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
+
+ /// \e
+
+
+ /// \todo Use the MapTraits once it is ported.
+ ///
+
+ //typename MapTraits<M1>::ConstReturnValue
+ typename M1::Value
+ operator[](Key k) const {return m1[m2[k]];}
+ };
+ ///Returns a \c ComposeMap class
+
+ ///This function just returns a \c ComposeMap class.
+ ///
+ ///\relates ComposeMap
+ template <typename M1, typename M2>
+ inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
+ return ComposeMap<M1, M2>(m1,m2);
+ }
+
+ ///Combines of two maps using an STL (binary) functor.
+
+ ///Combines of two maps using an STL (binary) functor.
+ ///
+ ///
+ ///This \c concepts::ReadMap "read only map" takes two maps and a
+ ///binary functor and returns the composition of
+ ///the two
+ ///given maps unsing the functor.
+ ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
+ ///and \c f is of \c F,
+ ///then for
+ ///\code
+ /// CombineMap<M1, M2,F,V> cm(m1,m2,f);
+ ///\endcode
+ /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
+ ///
+ ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
+ ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
+ ///input parameter of \c F and the return type of \c F must be convertible
+ ///to \c V.
+ ///\todo Check the requirements.
+ template<typename M1, typename M2, typename F,
+ typename V = typename F::result_type>
+ class CombineMap : public MapBase<typename M1::Key, V> {
+ const M1& m1;
+ const M2& m2;
+ F f;
+ public:
+ typedef MapBase<typename M1::Key, V> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
+ : m1(_m1), m2(_m2), f(_f) {};
+ /// \e
+ Value operator[](Key k) const {return f(m1[k],m2[k]);}
+ };
+
+ ///Returns a \c CombineMap class
+
+ ///This function just returns a \c CombineMap class.
+ ///
+ ///For example if \c m1 and \c m2 are both \c double valued maps, then
+ ///\code
+ ///combineMap<double>(m1,m2,std::plus<double>())
+ ///\endcode
+ ///is equivalent with
+ ///\code
+ ///addMap(m1,m2)
+ ///\endcode
+ ///
+ ///This function is specialized for adaptable binary function
+ ///classes and c++ functions.
+ ///
+ ///\relates CombineMap
+ template<typename M1, typename M2, typename F, typename V>
+ inline CombineMap<M1, M2, F, V>
+ combineMap(const M1& m1,const M2& m2, const F& f) {
+ return CombineMap<M1, M2, F, V>(m1,m2,f);
+ }
+
+ template<typename M1, typename M2, typename F>
+ inline CombineMap<M1, M2, F, typename F::result_type>
+ combineMap(const M1& m1, const M2& m2, const F& f) {
+ return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
+ }
+
+ template<typename M1, typename M2, typename K1, typename K2, typename V>
+ inline CombineMap<M1, M2, V (*)(K1, K2), V>
+ combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
+ return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
+ }
+
+ ///Negative value of a map
+
+ ///This \c concepts::ReadMap "read only map" returns the negative
+ ///value of the
+ ///value returned by the
+ ///given map. Its \c Key and \c Value will be inherited from \c M.
+ ///The unary \c - operator must be defined for \c Value, of course.
+
+ template<typename M>
+ class NegMap : public MapBase<typename M::Key, typename M::Value> {
+ const M& m;
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ NegMap(const M &_m) : m(_m) {};
+ /// \e
+ Value operator[](Key k) const {return -m[k];}
+ };
+
+ ///Negative value of a map
+
+ ///This \c concepts::ReadWriteMap "read-write map" returns the negative
+ ///value of the value returned by the
+ ///given map. Its \c Key and \c Value will be inherited from \c M.
+ ///The unary \c - operator must be defined for \c Value, of course.
+
+ template<typename M>
+ class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
+ M& m;
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ NegWriteMap(M &_m) : m(_m) {};
+ /// \e
+ Value operator[](Key k) const {return -m[k];}
+ /// \e
+ void set(Key k, const Value& v) { m.set(k, -v); }
+ };
+
+ ///Returns a \c NegMap class
+
+ ///This function just returns a \c NegMap class.
+ ///\relates NegMap
+ template <typename M>
+ inline NegMap<M> negMap(const M &m) {
+ return NegMap<M>(m);
+ }
+
+ template <typename M>
+ inline NegWriteMap<M> negMap(M &m) {
+ return NegWriteMap<M>(m);
+ }
+
+ ///Absolute value of a map
+
+ ///This \c concepts::ReadMap "read only map" returns the absolute value
+ ///of the
+ ///value returned by the
+ ///given map. Its \c Key and \c Value will be inherited
+ ///from <tt>M</tt>. <tt>Value</tt>
+ ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
+ ///operator must be defined for it, of course.
+ ///
+ ///\bug We need a unified way to handle the situation below:
+ ///\code
+ /// struct _UnConvertible {};
+ /// template<class A> inline A t_abs(A a) {return _UnConvertible();}
+ /// template<> inline int t_abs<>(int n) {return abs(n);}
+ /// template<> inline long int t_abs<>(long int n) {return labs(n);}
+ /// template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
+ /// template<> inline float t_abs<>(float n) {return fabsf(n);}
+ /// template<> inline double t_abs<>(double n) {return fabs(n);}
+ /// template<> inline long double t_abs<>(long double n) {return fabsl(n);}
+ ///\endcode
+
+
+ template<typename M>
+ class AbsMap : public MapBase<typename M::Key, typename M::Value> {
+ const M& m;
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ AbsMap(const M &_m) : m(_m) {};
+ /// \e
+ Value operator[](Key k) const {
+ Value tmp = m[k];
+ return tmp >= 0 ? tmp : -tmp;
+ }
+
+ };
+
+ ///Returns a \c AbsMap class
+
+ ///This function just returns a \c AbsMap class.
+ ///\relates AbsMap
+ template<typename M>
+ inline AbsMap<M> absMap(const M &m) {
+ return AbsMap<M>(m);
+ }
+
+ ///Converts an STL style functor to a map
+
+ ///This \c concepts::ReadMap "read only map" returns the value
+ ///of a
+ ///given map.
+ ///
+ ///Template parameters \c K and \c V will become its
+ ///\c Key and \c Value. They must be given explicitely
+ ///because a functor does not provide such typedefs.
+ ///
+ ///Parameter \c F is the type of the used functor.
+ template<typename F,
+ typename K = typename F::argument_type,
+ typename V = typename F::result_type>
+ class FunctorMap : public MapBase<K, V> {
+ F f;
+ public:
+ typedef MapBase<K, V> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ FunctorMap(const F &_f = F()) : f(_f) {}
+ /// \e
+ Value operator[](Key k) const { return f(k);}
+ };
+
+ ///Returns a \c FunctorMap class
+
+ ///This function just returns a \c FunctorMap class.
+ ///
+ ///It is specialized for adaptable function classes and
+ ///c++ functions.
+ ///\relates FunctorMap
+ template<typename K, typename V, typename F> inline
+ FunctorMap<F, K, V> functorMap(const F &f) {
+ return FunctorMap<F, K, V>(f);
+ }
+
+ template <typename F> inline
+ FunctorMap<F, typename F::argument_type, typename F::result_type>
+ functorMap(const F &f) {
+ return FunctorMap<F, typename F::argument_type,
+ typename F::result_type>(f);
+ }
+
+ template <typename K, typename V> inline
+ FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
+ return FunctorMap<V (*)(K), K, V>(f);
+ }
+
+
+ ///Converts a map to an STL style (unary) functor
+
+ ///This class Converts a map to an STL style (unary) functor.
+ ///that is it provides an <tt>operator()</tt> to read its values.
+ ///
+ ///For the sake of convenience it also works as
+ ///a ususal \c concepts::ReadMap "readable map",
+ ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
+ template <typename M>
+ class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
+ const M& m;
+ public:
+ typedef MapBase<typename M::Key, typename M::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ typedef typename M::Key argument_type;
+ typedef typename M::Value result_type;
+
+ ///Constructor
+ MapFunctor(const M &_m) : m(_m) {};
+ ///\e
+ Value operator()(Key k) const {return m[k];}
+ ///\e
+ Value operator[](Key k) const {return m[k];}
+ };
+
+ ///Returns a \c MapFunctor class
+
+ ///This function just returns a \c MapFunctor class.
+ ///\relates MapFunctor
+ template<typename M>
+ inline MapFunctor<M> mapFunctor(const M &m) {
+ return MapFunctor<M>(m);
+ }
+
+ ///Applies all map setting operations to two maps
+
+ ///This map has two \c concepts::ReadMap "readable map"
+ ///parameters and each read request will be passed just to the
+ ///first map. This class is the just readable map type of the ForkWriteMap.
+ ///
+ ///The \c Key and \c Value will be inherited from \c M1.
+ ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
+ template<typename M1, typename M2>
+ class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
+ const M1& m1;
+ const M2& m2;
+ public:
+ typedef MapBase<typename M1::Key, typename M1::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
+ /// \e
+ Value operator[](Key k) const {return m1[k];}
+ };
+
+
+ ///Applies all map setting operations to two maps
+
+ ///This map has two \c concepts::WriteMap "writable map"
+ ///parameters and each write request will be passed to both of them.
+ ///If \c M1 is also \c concepts::ReadMap "readable",
+ ///then the read operations will return the
+ ///corresponding values of \c M1.
+ ///
+ ///The \c Key and \c Value will be inherited from \c M1.
+ ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
+ template<typename M1, typename M2>
+ class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
+ M1& m1;
+ M2& m2;
+ public:
+ typedef MapBase<typename M1::Key, typename M1::Value> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ ///Constructor
+ ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
+ ///\e
+ Value operator[](Key k) const {return m1[k];}
+ ///\e
+ void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
+ };
+
+ ///Returns an \c ForkMap class
+
+ ///This function just returns an \c ForkMap class.
+ ///
+ ///\relates ForkMap
+ template <typename M1, typename M2>
+ inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
+ return ForkMap<M1, M2>(m1,m2);
+ }
+
+ template <typename M1, typename M2>
+ inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
+ return ForkWriteMap<M1, M2>(m1,m2);
+ }
+
+
+
+ /* ************* BOOL MAPS ******************* */
+
+ ///Logical 'not' of a map
+
+ ///This bool \c concepts::ReadMap "read only map" returns the
+ ///logical negation of
+ ///value returned by the
+ ///given map. Its \c Key and will be inherited from \c M,
+ ///its Value is <tt>bool</tt>.
+ template <typename M>
+ class NotMap : public MapBase<typename M::Key, bool> {
+ const M& m;
+ public:
+ typedef MapBase<typename M::Key, bool> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ /// Constructor
+ NotMap(const M &_m) : m(_m) {};
+ ///\e
+ Value operator[](Key k) const {return !m[k];}
+ };
+
+ ///Logical 'not' of a map with writing possibility
+
+ ///This bool \c concepts::ReadWriteMap "read-write map" returns the
+ ///logical negation of value returned by the given map. When it is set,
+ ///the opposite value is set to the original map.
+ ///Its \c Key and will be inherited from \c M,
+ ///its Value is <tt>bool</tt>.
+ template <typename M>
+ class NotWriteMap : public MapBase<typename M::Key, bool> {
+ M& m;
+ public:
+ typedef MapBase<typename M::Key, bool> Parent;
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ /// Constructor
+ NotWriteMap(M &_m) : m(_m) {};
+ ///\e
+ Value operator[](Key k) const {return !m[k];}
+ ///\e
+ void set(Key k, bool v) { m.set(k, !v); }
+ };
+
+ ///Returns a \c NotMap class
+
+ ///This function just returns a \c NotMap class.
+ ///\relates NotMap
+ template <typename M>
+ inline NotMap<M> notMap(const M &m) {
+ return NotMap<M>(m);
+ }
+
+ template <typename M>
+ inline NotWriteMap<M> notMap(M &m) {
+ return NotWriteMap<M>(m);
+ }
+
+ namespace _maps_bits {
+
+ template <typename Value>
+ struct Identity {
+ typedef Value argument_type;
+ typedef Value result_type;
+ Value operator()(const Value& val) const {
+ return val;
+ }
+ };
+
+ template <typename _Iterator, typename Enable = void>
+ struct IteratorTraits {
+ typedef typename std::iterator_traits<_Iterator>::value_type Value;
+ };
+
+ template <typename _Iterator>
+ struct IteratorTraits<_Iterator,
+ typename exists<typename _Iterator::container_type>::type>
+ {
+ typedef typename _Iterator::container_type::value_type Value;
+ };
+
+ }
+
+
+ /// \brief Writable bool map for store each true assigned elements.
+ ///
+ /// Writable bool map to store each true assigned elements. It will
+ /// copies all the keys set to true to the given iterator.
+ ///
+ /// \note The container of the iterator should contain space
+ /// for each element.
+ ///
+ /// The next example shows how can you write the nodes directly
+ /// to the standard output.
+ ///\code
+ /// typedef IdMap<Graph, Edge> EdgeIdMap;
+ /// EdgeIdMap edgeId(graph);
+ ///
+ /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
+ /// EdgeIdFunctor edgeIdFunctor(edgeId);
+ ///
+ /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
+ /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
+ ///
+ /// prim(graph, cost, writerMap);
+ ///\endcode
+ template <typename _Iterator,
+ typename _Functor =
+ _maps_bits::Identity<typename _maps_bits::
+ IteratorTraits<_Iterator>::Value> >
+ class StoreBoolMap {
+ public:
+ typedef _Iterator Iterator;
+
+ typedef typename _Functor::argument_type Key;
+ typedef bool Value;
+
+ typedef _Functor Functor;
+
+ /// Constructor
+ StoreBoolMap(Iterator it, const Functor& functor = Functor())
+ : _begin(it), _end(it), _functor(functor) {}
+
+ /// Gives back the given iterator set for the first time.
+ Iterator begin() const {
+ return _begin;
+ }
+
+ /// Gives back the iterator after the last set operation.
+ Iterator end() const {
+ return _end;
+ }
+
+ /// Setter function of the map
+ void set(const Key& key, Value value) const {
+ if (value) {
+ *_end++ = _functor(key);
+ }
+ }
+
+ private:
+ Iterator _begin;
+ mutable Iterator _end;
+ Functor _functor;
+ };
+
+ /// \brief Writable bool map for store each true assigned elements in
+ /// a back insertable container.
+ ///
+ /// Writable bool map for store each true assigned elements in a back
+ /// insertable container. It will push back all the keys set to true into
+ /// the container. It can be used to retrieve the items into a standard
+ /// container. The next example shows how can you store the undirected
+ /// arcs in a vector with prim algorithm.
+ ///
+ ///\code
+ /// vector<Edge> span_tree_edges;
+ /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
+ /// prim(graph, cost, inserter_map);
+ ///\endcode
+ template <typename Container,
+ typename Functor =
+ _maps_bits::Identity<typename Container::value_type> >
+ class BackInserterBoolMap {
+ public:
+ typedef typename Container::value_type Key;
+ typedef bool Value;
+
+ /// Constructor
+ BackInserterBoolMap(Container& _container,
+ const Functor& _functor = Functor())
+ : container(_container), functor(_functor) {}
+
+ /// Setter function of the map
+ void set(const Key& key, Value value) {
+ if (value) {
+ container.push_back(functor(key));
+ }
+ }
+
+ private:
+ Container& container;
+ Functor functor;
+ };
+
+ /// \brief Writable bool map for store each true assigned elements in
+ /// a front insertable container.
+ ///
+ /// Writable bool map for store each true assigned elements in a front
+ /// insertable container. It will push front all the keys set to \c true into
+ /// the container. For example see the BackInserterBoolMap.
+ template <typename Container,
+ typename Functor =
+ _maps_bits::Identity<typename Container::value_type> >
+ class FrontInserterBoolMap {
+ public:
+ typedef typename Container::value_type Key;
+ typedef bool Value;
+
+ /// Constructor
+ FrontInserterBoolMap(Container& _container,
+ const Functor& _functor = Functor())
+ : container(_container), functor(_functor) {}
+
+ /// Setter function of the map
+ void set(const Key& key, Value value) {
+ if (value) {
+ container.push_front(key);
+ }
+ }
+
+ private:
+ Container& container;
+ Functor functor;
+ };
+
+ /// \brief Writable bool map for store each true assigned elements in
+ /// an insertable container.
+ ///
+ /// Writable bool map for store each true assigned elements in an
+ /// insertable container. It will insert all the keys set to \c true into
+ /// the container. If you want to store the cut arcs of the strongly
+ /// connected components in a set you can use the next code:
+ ///
+ ///\code
+ /// set<Arc> cut_arcs;
+ /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
+ /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
+ ///\endcode
+ template <typename Container,
+ typename Functor =
+ _maps_bits::Identity<typename Container::value_type> >
+ class InserterBoolMap {
+ public:
+ typedef typename Container::value_type Key;
+ typedef bool Value;
+
+ /// Constructor
+ InserterBoolMap(Container& _container, typename Container::iterator _it,
+ const Functor& _functor = Functor())
+ : container(_container), it(_it), functor(_functor) {}
+
+ /// Constructor
+ InserterBoolMap(Container& _container, const Functor& _functor = Functor())
+ : container(_container), it(_container.end()), functor(_functor) {}
+
+ /// Setter function of the map
+ void set(const Key& key, Value value) {
+ if (value) {
+ it = container.insert(it, key);
+ ++it;
+ }
+ }
+
+ private:
+ Container& container;
+ typename Container::iterator it;
+ Functor functor;
+ };
+
+ /// \brief Fill the true set elements with a given value.
+ ///
+ /// Writable bool map to fill the elements set to \c true with a given value.
+ /// The value can set
+ /// the container.
+ ///
+ /// The next code finds the connected components of the undirected digraph
+ /// and stores it in the \c comp map:
+ ///\code
+ /// typedef Graph::NodeMap<int> ComponentMap;
+ /// ComponentMap comp(graph);
+ /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
+ /// ComponentFillerMap filler(comp, 0);
+ ///
+ /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
+ /// dfs.processedMap(filler);
+ /// dfs.init();
+ /// for (NodeIt it(graph); it != INVALID; ++it) {
+ /// if (!dfs.reached(it)) {
+ /// dfs.addSource(it);
+ /// dfs.start();
+ /// ++filler.fillValue();
+ /// }
+ /// }
+ ///\endcode
+ template <typename Map>
+ class FillBoolMap {
+ public:
+ typedef typename Map::Key Key;
+ typedef bool Value;
+
+ /// Constructor
+ FillBoolMap(Map& _map, const typename Map::Value& _fill)
+ : map(_map), fill(_fill) {}
+
+ /// Constructor
+ FillBoolMap(Map& _map)
+ : map(_map), fill() {}
+
+ /// Gives back the current fill value
+ const typename Map::Value& fillValue() const {
+ return fill;
+ }
+
+ /// Gives back the current fill value
+ typename Map::Value& fillValue() {
+ return fill;
+ }
+
+ /// Sets the current fill value
+ void fillValue(const typename Map::Value& _fill) {
+ fill = _fill;
+ }
+
+ /// Setter function of the map
+ void set(const Key& key, Value value) {
+ if (value) {
+ map.set(key, fill);
+ }
+ }
+
+ private:
+ Map& map;
+ typename Map::Value fill;
+ };
+
+
+ /// \brief Writable bool map which stores for each true assigned elements
+ /// the setting order number.
+ ///
+ /// Writable bool map which stores for each true assigned elements
+ /// the setting order number. It make easy to calculate the leaving
+ /// order of the nodes in the \c Dfs algorithm.
+ ///
+ ///\code
+ /// typedef Digraph::NodeMap<int> OrderMap;
+ /// OrderMap order(digraph);
+ /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
+ /// OrderSetterMap setter(order);
+ /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
+ /// dfs.processedMap(setter);
+ /// dfs.init();
+ /// for (NodeIt it(digraph); it != INVALID; ++it) {
+ /// if (!dfs.reached(it)) {
+ /// dfs.addSource(it);
+ /// dfs.start();
+ /// }
+ /// }
+ ///\endcode
+ ///
+ /// The discovering order can be stored a little harder because the
+ /// ReachedMap should be readable in the dfs algorithm but the setting
+ /// order map is not readable. Now we should use the fork map:
+ ///
+ ///\code
+ /// typedef Digraph::NodeMap<int> OrderMap;
+ /// OrderMap order(digraph);
+ /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
+ /// OrderSetterMap setter(order);
+ /// typedef Digraph::NodeMap<bool> StoreMap;
+ /// StoreMap store(digraph);
+ ///
+ /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
+ /// ReachedMap reached(store, setter);
+ ///
+ /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
+ /// dfs.reachedMap(reached);
+ /// dfs.init();
+ /// for (NodeIt it(digraph); it != INVALID; ++it) {
+ /// if (!dfs.reached(it)) {
+ /// dfs.addSource(it);
+ /// dfs.start();
+ /// }
+ /// }
+ ///\endcode
+ template <typename Map>
+ class SettingOrderBoolMap {
+ public:
+ typedef typename Map::Key Key;
+ typedef bool Value;
+
+ /// Constructor
+ SettingOrderBoolMap(Map& _map)
+ : map(_map), counter(0) {}
+
+ /// Number of set operations.
+ int num() const {
+ return counter;
+ }
+
+ /// Setter function of the map
+ void set(const Key& key, Value value) {
+ if (value) {
+ map.set(key, counter++);
+ }
+ }
+
+ private:
+ Map& map;
+ int counter;
+ };
+
+ /// @}
+}
+
+#endif // LEMON_MAPS_H
diff -r 4d461e9867da -r 751cd8f9bb1c test/Makefile.am
--- a/test/Makefile.am Thu Dec 20 15:59:06 2007 +0000
+++ b/test/Makefile.am Sat Dec 22 12:35:00 2007 +0000
@@ -5,11 +5,13 @@
test/test_tools.h
check_PROGRAMS += \
+ test/maps_test \
test/test_tools_fail \
test/test_tools_pass
TESTS += $(check_PROGRAMS)
XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
+test_maps_test_SOURCES = test/maps_test.cc
test_test_tools_fail_SOURCES = test/test_tools_fail.cc
test_test_tools_pass_SOURCES = test/test_tools_pass.cc
diff -r 4d461e9867da -r 751cd8f9bb1c test/maps_test.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/maps_test.cc Sat Dec 22 12:35:00 2007 +0000
@@ -0,0 +1,108 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2007
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include <deque>
+#include <set>
+
+#include <lemon/concept_check.h>
+#include <lemon/concepts/maps.h>
+#include <lemon/maps.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+using namespace lemon::concepts;
+
+struct A {};
+inline bool operator<(A, A) { return true; }
+struct B {};
+
+class F {
+public:
+ typedef A argument_type;
+ typedef B result_type;
+
+ B operator()(const A &) const {return B();}
+};
+
+int func(A) {return 3;}
+
+int binc(int, B) {return 4;}
+
+typedef ReadMap<A,double> DoubleMap;
+typedef ReadWriteMap<A, double> WriteDoubleMap;
+
+typedef ReadMap<A,bool> BoolMap;
+typedef ReadWriteMap<A, bool> BoolWriteMap;
+
+int main()
+{ // checking graph components
+
+ checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
+ checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
+ checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
+ checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
+
+ checkConcept<ReadMap<A,double>, AddMap<DoubleMap,DoubleMap> >();
+ checkConcept<ReadMap<A,double>, SubMap<DoubleMap,DoubleMap> >();
+ checkConcept<ReadMap<A,double>, MulMap<DoubleMap,DoubleMap> >();
+ checkConcept<ReadMap<A,double>, DivMap<DoubleMap,DoubleMap> >();
+ checkConcept<ReadMap<A,double>, NegMap<DoubleMap> >();
+ checkConcept<ReadWriteMap<A,double>, NegWriteMap<WriteDoubleMap> >();
+ checkConcept<ReadMap<A,double>, AbsMap<DoubleMap> >();
+ checkConcept<ReadMap<A,double>, ShiftMap<DoubleMap> >();
+ checkConcept<ReadWriteMap<A,double>, ShiftWriteMap<WriteDoubleMap> >();
+ checkConcept<ReadMap<A,double>, ScaleMap<DoubleMap> >();
+ checkConcept<ReadWriteMap<A,double>, ScaleWriteMap<WriteDoubleMap> >();
+ checkConcept<ReadMap<A,double>, ForkMap<DoubleMap, DoubleMap> >();
+ checkConcept<ReadWriteMap<A,double>,
+ ForkWriteMap<WriteDoubleMap, WriteDoubleMap> >();
+
+ checkConcept<ReadMap<B,double>, ComposeMap<DoubleMap,ReadMap<B,A> > >();
+
+ checkConcept<ReadMap<A,B>, FunctorMap<F, A, B> >();
+
+ checkConcept<ReadMap<A, bool>, NotMap<BoolMap> >();
+ checkConcept<ReadWriteMap<A, bool>, NotWriteMap<BoolWriteMap> >();
+
+ checkConcept<WriteMap<A, bool>, StoreBoolMap<A*> >();
+ checkConcept<WriteMap<A, bool>, BackInserterBoolMap<std::deque<A> > >();
+ checkConcept<WriteMap<A, bool>, FrontInserterBoolMap<std::deque<A> > >();
+ checkConcept<WriteMap<A, bool>, InserterBoolMap<std::set<A> > >();
+ checkConcept<WriteMap<A, bool>, FillBoolMap<WriteMap<A, B> > >();
+ checkConcept<WriteMap<A, bool>, SettingOrderBoolMap<WriteMap<A, int> > >();
+
+ int a;
+
+ a=mapFunctor(constMap<A,int>(2))(A());
+ check(a==2,"Something is wrong with mapFunctor");
+
+ B b;
+ b=functorMap(F())[A()];
+
+ a=functorMap(&func)[A()];
+ check(a==3,"Something is wrong with functorMap");
+
+ a=combineMap(constMap<B, int, 1>(), identityMap<B>(), &binc)[B()];
+ check(a==4,"Something is wrong with combineMap");
+
+
+ std::cout << __FILE__ ": All tests passed.\n";
+
+ return 0;
+}