Mercuriallemon-1.3 / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/maps.h
changeset 724 d8073df341f6
parent 722 b52189c479fb
child 725 11404088d1a5
equal deleted inserted replaced
41:28a4de500635 42:7b6a52e36e5f 
  1905   /// This class provides simple invertable graph maps.
 
  1905   /// This class provides simple invertable graph maps.
 
  1906   /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
 
  1906   /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
 
  1907   /// and if a key is set to a new value, then stores it in the inverse map.
 
  1907   /// and if a key is set to a new value, then stores it in the inverse map.
 
  1908   /// The graph items can be accessed by their values either using
 
  1908   /// The graph items can be accessed by their values either using
 
  1909   /// \c InverseMap or \c operator()(), and the values of the map can be
 
  1909   /// \c InverseMap or \c operator()(), and the values of the map can be
 
  1910   /// accessed with an STL compatible forward iterator (\c ValueIterator).
 
  1910   /// accessed with an STL compatible forward iterator (\c ValueIt).
 
  1911   /// 
  1911   /// 
  1912   /// This map is intended to be used when all associated values are
 
  1912   /// This map is intended to be used when all associated values are
 
  1913   /// different (the map is actually invertable) or there are only a few
 
  1913   /// different (the map is actually invertable) or there are only a few
 
  1914   /// items with the same value.
 
  1914   /// items with the same value.
 
  1915   /// Otherwise consider to use \c IterableValueMap, which is more 
  1915   /// Otherwise consider to use \c IterableValueMap, which is more 
  1959     /// This iterator is an STL compatible forward
 
  1959     /// This iterator is an STL compatible forward
 
  1960     /// iterator on the values of the map. The values can
 
  1960     /// iterator on the values of the map. The values can
 
  1961     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
 
  1961     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
 
  1962     /// They are considered with multiplicity, so each value is
 
  1962     /// They are considered with multiplicity, so each value is
 
  1963     /// traversed for each item it is assigned to.
 
  1963     /// traversed for each item it is assigned to.
 
  1964     class ValueIterator
 
  1964     class ValueIt
 
  1965       : public std::iterator<std::forward_iterator_tag, Value> {
 
  1965       : public std::iterator<std::forward_iterator_tag, Value> {
 
  1966       friend class CrossRefMap;
 
  1966       friend class CrossRefMap;
 
  1967     private:
 
  1967     private:
 
  1968       ValueIterator(typename Container::const_iterator _it)
 
  1968       ValueIt(typename Container::const_iterator _it)
 
  1969         : it(_it) {}
 
  1969         : it(_it) {}
 
  1970     public:
 
  1970     public:
 
  1971 
  1971 
  1972       /// Constructor
 
  1972       /// Constructor
 
  1973       ValueIterator() {}
 
  1973       ValueIt() {}
 
  1974 
  1974 
  1975       /// \e
 
  1975       /// \e
 
  1976       ValueIterator& operator++() { ++it; return *this; }
 
  1976       ValueIt& operator++() { ++it; return *this; }
 
  1977       /// \e
 
  1977       /// \e
 
  1978       ValueIterator operator++(int) {
 
  1978       ValueIt operator++(int) {
 
  1979         ValueIterator tmp(*this);
 
  1979         ValueIt tmp(*this);
 
  1980         operator++();
 
  1980         operator++();
 
  1981         return tmp;
 
  1981         return tmp;
 
  1982       }
 
  1982       }
 
  1983 
  1983 
  1984       /// \e
 
  1984       /// \e
 
  1985       const Value& operator*() const { return it->first; }
 
  1985       const Value& operator*() const { return it->first; }
 
  1986       /// \e
 
  1986       /// \e
 
  1987       const Value* operator->() const { return &(it->first); }
 
  1987       const Value* operator->() const { return &(it->first); }
 
  1988 
  1988 
  1989       /// \e
 
  1989       /// \e
 
  1990       bool operator==(ValueIterator jt) const { return it == jt.it; }
 
  1990       bool operator==(ValueIt jt) const { return it == jt.it; }
 
  1991       /// \e
 
  1991       /// \e
 
  1992       bool operator!=(ValueIterator jt) const { return it != jt.it; }
 
  1992       bool operator!=(ValueIt jt) const { return it != jt.it; }
 
  1993 
  1993 
  1994     private:
 
  1994     private:
 
  1995       typename Container::const_iterator it;
 
  1995       typename Container::const_iterator it;
 
  1996     };
 
  1996     };
 
       
  1997     
       
  1998     /// Alias for \c ValueIt
 
       
  1999     typedef ValueIt ValueIterator;
 
  1997 
  2000 
  1998     /// \brief Returns an iterator to the first value.
 
  2001     /// \brief Returns an iterator to the first value.
 
  1999     ///
 
  2002     ///
 
  2000     /// Returns an STL compatible iterator to the
 
  2003     /// Returns an STL compatible iterator to the
 
  2001     /// first value of the map. The values of the
 
  2004     /// first value of the map. The values of the
 
  2002     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 
  2005     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 
  2003     /// range.
 
  2006     /// range.
 
  2004     ValueIterator beginValue() const {
 
  2007     ValueIt beginValue() const {
 
  2005       return ValueIterator(_inv_map.begin());
 
  2008       return ValueIt(_inv_map.begin());
 
  2006     }
 
  2009     }
 
  2007 
  2010 
  2008     /// \brief Returns an iterator after the last value.
 
  2011     /// \brief Returns an iterator after the last value.
 
  2009     ///
 
  2012     ///
 
  2010     /// Returns an STL compatible iterator after the
 
  2013     /// Returns an STL compatible iterator after the
 
  2011     /// last value of the map. The values of the
 
  2014     /// last value of the map. The values of the
 
  2012     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 
  2015     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 
  2013     /// range.
 
  2016     /// range.
 
  2014     ValueIterator endValue() const {
 
  2017     ValueIt endValue() const {
 
  2015       return ValueIterator(_inv_map.end());
 
  2018       return ValueIt(_inv_map.end());
 
  2016     }
 
  2019     }
 
  2017 
  2020 
  2018     /// \brief Sets the value associated with the given key.
 
  2021     /// \brief Sets the value associated with the given key.
 
  2019     ///
 
  2022     ///
 
  2020     /// Sets the value associated with the given key.
 
  2023     /// Sets the value associated with the given key.
 
  3021   ///
 
  3024   ///
 
  3022   /// This class provides a special graph map type which can store a
 
  3025   /// This class provides a special graph map type which can store a
 
  3023   /// comparable value for graph items (\c Node, \c Arc or \c Edge).
 
  3026   /// comparable value for graph items (\c Node, \c Arc or \c Edge).
 
  3024   /// For each value it is possible to iterate on the keys mapped to
 
  3027   /// For each value it is possible to iterate on the keys mapped to
 
  3025   /// the value (\c ItemIt), and the values of the map can be accessed
 
  3028   /// the value (\c ItemIt), and the values of the map can be accessed
 
  3026   /// with an STL compatible forward iterator (\c ValueIterator).
 
  3029   /// with an STL compatible forward iterator (\c ValueIt).
 
  3027   /// The map stores a linked list for each value, which contains
 
  3030   /// The map stores a linked list for each value, which contains
 
  3028   /// the items mapped to the value, and the used values are stored
 
  3031   /// the items mapped to the value, and the used values are stored
 
  3029   /// in balanced binary tree (\c std::map).
 
  3032   /// in balanced binary tree (\c std::map).
 
  3030   ///
 
  3033   ///
 
  3031   /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
 
  3034   /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
 
  3109     /// \brief Forward iterator for values.
 
  3112     /// \brief Forward iterator for values.
 
  3110     ///
 
  3113     ///
 
  3111     /// This iterator is an STL compatible forward
 
  3114     /// This iterator is an STL compatible forward
 
  3112     /// iterator on the values of the map. The values can
 
  3115     /// iterator on the values of the map. The values can
 
  3113     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
 
  3116     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
 
  3114     class ValueIterator
 
  3117     class ValueIt
 
  3115       : public std::iterator<std::forward_iterator_tag, Value> {
 
  3118       : public std::iterator<std::forward_iterator_tag, Value> {
 
  3116       friend class IterableValueMap;
 
  3119       friend class IterableValueMap;
 
  3117     private:
 
  3120     private:
 
  3118       ValueIterator(typename std::map<Value, Key>::const_iterator _it)
 
  3121       ValueIt(typename std::map<Value, Key>::const_iterator _it)
 
  3119         : it(_it) {}
 
  3122         : it(_it) {}
 
  3120     public:
 
  3123     public:
 
  3121 
  3124 
  3122       /// Constructor
 
  3125       /// Constructor
 
  3123       ValueIterator() {}
 
  3126       ValueIt() {}
 
  3124 
  3127 
  3125       /// \e
 
  3128       /// \e
 
  3126       ValueIterator& operator++() { ++it; return *this; }
 
  3129       ValueIt& operator++() { ++it; return *this; }
 
  3127       /// \e
 
  3130       /// \e
 
  3128       ValueIterator operator++(int) {
 
  3131       ValueIt operator++(int) {
 
  3129         ValueIterator tmp(*this);
 
  3132         ValueIt tmp(*this);
 
  3130         operator++();
 
  3133         operator++();
 
  3131         return tmp;
 
  3134         return tmp;
 
  3132       }
 
  3135       }
 
  3133 
  3136 
  3134       /// \e
 
  3137       /// \e
 
  3135       const Value& operator*() const { return it->first; }
 
  3138       const Value& operator*() const { return it->first; }
 
  3136       /// \e
 
  3139       /// \e
 
  3137       const Value* operator->() const { return &(it->first); }
 
  3140       const Value* operator->() const { return &(it->first); }
 
  3138 
  3141 
  3139       /// \e
 
  3142       /// \e
 
  3140       bool operator==(ValueIterator jt) const { return it == jt.it; }
 
  3143       bool operator==(ValueIt jt) const { return it == jt.it; }
 
  3141       /// \e
 
  3144       /// \e
 
  3142       bool operator!=(ValueIterator jt) const { return it != jt.it; }
 
  3145       bool operator!=(ValueIt jt) const { return it != jt.it; }
 
  3143 
  3146 
  3144     private:
 
  3147     private:
 
  3145       typename std::map<Value, Key>::const_iterator it;
 
  3148       typename std::map<Value, Key>::const_iterator it;
 
  3146     };
 
  3149     };
 
  3147 
  3150 
  3149     ///
 
  3152     ///
 
  3150     /// Returns an STL compatible iterator to the
 
  3153     /// Returns an STL compatible iterator to the
 
  3151     /// first value of the map. The values of the
 
  3154     /// first value of the map. The values of the
 
  3152     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 
  3155     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 
  3153     /// range.
 
  3156     /// range.
 
  3154     ValueIterator beginValue() const {
 
  3157     ValueIt beginValue() const {
 
  3155       return ValueIterator(_first.begin());
 
  3158       return ValueIt(_first.begin());
 
  3156     }
 
  3159     }
 
  3157 
  3160 
  3158     /// \brief Returns an iterator after the last value.
 
  3161     /// \brief Returns an iterator after the last value.
 
  3159     ///
 
  3162     ///
 
  3160     /// Returns an STL compatible iterator after the
 
  3163     /// Returns an STL compatible iterator after the
 
  3161     /// last value of the map. The values of the
 
  3164     /// last value of the map. The values of the
 
  3162     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 
  3165     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 
  3163     /// range.
 
  3166     /// range.
 
  3164     ValueIterator endValue() const {
 
  3167     ValueIt endValue() const {
 
  3165       return ValueIterator(_first.end());
 
  3168       return ValueIt(_first.end());
 
  3166     }
 
  3169     }
 
  3167 
  3170 
  3168     /// \brief Set operation of the map.
 
  3171     /// \brief Set operation of the map.
 
  3169     ///
 
  3172     ///
 
  3170     /// Set operation of the map.
 
  3173     /// Set operation of the map.
 
  3278   /// \see TargetMap
 
  3281   /// \see TargetMap
 
  3279   template <typename GR>
 
  3282   template <typename GR>
 
  3280   class SourceMap {
 
  3283   class SourceMap {
 
  3281   public:
 
  3284   public:
 
  3282 
  3285 
  3283     ///\e
 
  3286     /// The key type (the \c Arc type of the digraph).
 
  3284     typedef typename GR::Arc Key;
 
  3287     typedef typename GR::Arc Key;
 
  3285     ///\e
 
  3288     /// The value type (the \c Node type of the digraph).
 
  3286     typedef typename GR::Node Value;
 
  3289     typedef typename GR::Node Value;
 
  3287 
  3290 
  3288     /// \brief Constructor
 
  3291     /// \brief Constructor
 
  3289     ///
 
  3292     ///
 
  3290     /// Constructor.
 
  3293     /// Constructor.
 
  3319   /// \see SourceMap
 
  3322   /// \see SourceMap
 
  3320   template <typename GR>
 
  3323   template <typename GR>
 
  3321   class TargetMap {
 
  3324   class TargetMap {
 
  3322   public:
 
  3325   public:
 
  3323 
  3326 
  3324     ///\e
 
  3327     /// The key type (the \c Arc type of the digraph).
 
  3325     typedef typename GR::Arc Key;
 
  3328     typedef typename GR::Arc Key;
 
  3326     ///\e
 
  3329     /// The value type (the \c Node type of the digraph).
 
  3327     typedef typename GR::Node Value;
 
  3330     typedef typename GR::Node Value;
 
  3328 
  3331 
  3329     /// \brief Constructor
 
  3332     /// \brief Constructor
 
  3330     ///
 
  3333     ///
 
  3331     /// Constructor.
 
  3334     /// Constructor.
 
  3361   /// \see BackwardMap
 
  3364   /// \see BackwardMap
 
  3362   template <typename GR>
 
  3365   template <typename GR>
 
  3363   class ForwardMap {
 
  3366   class ForwardMap {
 
  3364   public:
 
  3367   public:
 
  3365 
  3368 
       
  3369     /// The key type (the \c Edge type of the digraph).
 
       
  3370     typedef typename GR::Edge Key;
 
       
  3371     /// The value type (the \c Arc type of the digraph).
 
  3366     typedef typename GR::Arc Value;
 
  3372     typedef typename GR::Arc Value;
 
  3367     typedef typename GR::Edge Key;
 
       
  3368 
  3373 
  3369     /// \brief Constructor
 
  3374     /// \brief Constructor
 
  3370     ///
 
  3375     ///
 
  3371     /// Constructor.
 
  3376     /// Constructor.
 
  3372     /// \param graph The graph that the map belongs to.
 
  3377     /// \param graph The graph that the map belongs to.
 
  3401   /// \see ForwardMap
 
  3406   /// \see ForwardMap
 
  3402   template <typename GR>
 
  3407   template <typename GR>
 
  3403   class BackwardMap {
 
  3408   class BackwardMap {
 
  3404   public:
 
  3409   public:
 
  3405 
  3410 
       
  3411     /// The key type (the \c Edge type of the digraph).
 
       
  3412     typedef typename GR::Edge Key;
 
       
  3413     /// The value type (the \c Arc type of the digraph).
 
  3406     typedef typename GR::Arc Value;
 
  3414     typedef typename GR::Arc Value;
 
  3407     typedef typename GR::Edge Key;
 
       
  3408 
  3415 
  3409     /// \brief Constructor
 
  3416     /// \brief Constructor
 
  3410     ///
 
  3417     ///
 
  3411     /// Constructor.
 
  3418     /// Constructor.
 
  3412     /// \param graph The graph that the map belongs to.
 
  3419     /// \param graph The graph that the map belongs to.
lemon-1.3