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