1.1 --- a/lemon/maps.h	Wed Nov 14 15:36:37 2007 +0000
     1.2 +++ b/lemon/maps.h	Wed Nov 14 17:42:48 2007 +0000
     1.3 @@ -21,6 +21,7 @@
     1.4  
     1.5  #include <iterator>
     1.6  #include <functional>
     1.7 +#include <vector>
     1.8  
     1.9  #include <lemon/bits/utility.h>
    1.10  #include <lemon/bits/traits.h>
    1.11 @@ -241,6 +242,78 @@
    1.12      };
    1.13    };
    1.14  
    1.15 +  /// \brief Map for storing values for the range \c [0..size-1] range keys
    1.16 +  ///
    1.17 +  /// The current map has the \c [0..size-1] keyset and the values
    1.18 +  /// are stored in a \c std::vector<T>  container. It can be used with
    1.19 +  /// some data structures, for example \c UnionFind, \c BinHeap, when 
    1.20 +  /// the used items are small integer numbers.
    1.21 +  template <typename T>
    1.22 +  class IntegerMap {
    1.23 +
    1.24 +    template <typename T1>
    1.25 +    friend class IntegerMap;
    1.26 +
    1.27 +  public:
    1.28 +
    1.29 +    typedef True ReferenceMapTag;
    1.30 +    ///\e
    1.31 +    typedef int Key;
    1.32 +    ///\e
    1.33 +    typedef T Value;
    1.34 +    ///\e
    1.35 +    typedef T& Reference;
    1.36 +    ///\e
    1.37 +    typedef const T& ConstReference;
    1.38 +
    1.39 +  private:
    1.40 +    
    1.41 +    typedef std::vector<T> Vector;
    1.42 +    Vector _vector;
    1.43 +
    1.44 +  public:
    1.45 +
    1.46 +    /// Constructor with specified default value
    1.47 +    IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
    1.48 +
    1.49 +    /// \brief Constructs the map from an appropriate std::vector.
    1.50 +    template <typename T1>
    1.51 +    IntegerMap(const std::vector<T1>& vector) 
    1.52 +      : _vector(vector.begin(), vector.end()) {}
    1.53 +    
    1.54 +    /// \brief Constructs a map from an other IntegerMap.
    1.55 +    template <typename T1>
    1.56 +    IntegerMap(const IntegerMap<T1> &c) 
    1.57 +      : _vector(c._vector.begin(), c._vector.end()) {}
    1.58 +
    1.59 +    /// \brief Resize the container
    1.60 +    void resize(int size, const T& value = T()) {
    1.61 +      _vector.resize(size, value);
    1.62 +    }
    1.63 +
    1.64 +  private:
    1.65 +
    1.66 +    IntegerMap& operator=(const IntegerMap&);
    1.67 +
    1.68 +  public:
    1.69 +
    1.70 +    ///\e
    1.71 +    Reference operator[](Key k) {
    1.72 +      return _vector[k];
    1.73 +    }
    1.74 +
    1.75 +    /// \e 
    1.76 +    ConstReference operator[](Key k) const {
    1.77 +      return _vector[k];
    1.78 +    }
    1.79 +
    1.80 +    /// \e 
    1.81 +    void set(const Key &k, const T& t) {
    1.82 +      _vector[k] = t;
    1.83 +    }
    1.84 +
    1.85 +  };
    1.86 +
    1.87    /// @}
    1.88  
    1.89    /// \addtogroup map_adaptors