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