lemon/maps.h
changeset 212 1ae84dea7d09
parent 167 d57ae6f0a335
child 220 a5d8c039f218
equal deleted inserted replaced
21:448562babf44 22:13fae95f3777
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
   402 
   402 
   403     ///\e
   403     ///\e
   404     Reference operator[](const Key &k) {
   404     Reference operator[](const Key &k) {
   405       typename Map::iterator it = _map.lower_bound(k);
   405       typename Map::iterator it = _map.lower_bound(k);
   406       if (it != _map.end() && !_map.key_comp()(k, it->first))
   406       if (it != _map.end() && !_map.key_comp()(k, it->first))
   407 	return it->second;
   407         return it->second;
   408       else
   408       else
   409 	return _map.insert(it, std::make_pair(k, _value))->second;
   409         return _map.insert(it, std::make_pair(k, _value))->second;
   410     }
   410     }
   411 
   411 
   412     ///\e
   412     ///\e
   413     ConstReference operator[](const Key &k) const {
   413     ConstReference operator[](const Key &k) const {
   414       typename Map::const_iterator it = _map.find(k);
   414       typename Map::const_iterator it = _map.find(k);
   415       if (it != _map.end())
   415       if (it != _map.end())
   416 	return it->second;
   416         return it->second;
   417       else
   417       else
   418 	return _value;
   418         return _value;
   419     }
   419     }
   420 
   420 
   421     ///\e
   421     ///\e
   422     void set(const Key &k, const Value &v) {
   422     void set(const Key &k, const Value &v) {
   423       typename Map::iterator it = _map.lower_bound(k);
   423       typename Map::iterator it = _map.lower_bound(k);
   424       if (it != _map.end() && !_map.key_comp()(k, it->first))
   424       if (it != _map.end() && !_map.key_comp()(k, it->first))
   425 	it->second = v;
   425         it->second = v;
   426       else
   426       else
   427 	_map.insert(it, std::make_pair(k, v));
   427         _map.insert(it, std::make_pair(k, v));
   428     }
   428     }
   429 
   429 
   430     ///\e
   430     ///\e
   431     void setAll(const Value &v) {
   431     void setAll(const Value &v) {
   432       _value = v;
   432       _value = v;
   542   ///
   542   ///
   543   /// \sa ComposeMap
   543   /// \sa ComposeMap
   544   ///
   544   ///
   545   /// \todo Check the requirements.
   545   /// \todo Check the requirements.
   546   template<typename M1, typename M2, typename F,
   546   template<typename M1, typename M2, typename F,
   547 	   typename V = typename F::result_type>
   547            typename V = typename F::result_type>
   548   class CombineMap : public MapBase<typename M1::Key, V> {
   548   class CombineMap : public MapBase<typename M1::Key, V> {
   549     const M1 &_m1;
   549     const M1 &_m1;
   550     const M2 &_m2;
   550     const M2 &_m2;
   551     F _f;
   551     F _f;
   552   public:
   552   public:
   613   /// The simplest way of using this map is through the functorToMap()
   613   /// The simplest way of using this map is through the functorToMap()
   614   /// function.
   614   /// function.
   615   ///
   615   ///
   616   /// \sa MapToFunctor
   616   /// \sa MapToFunctor
   617   template<typename F,
   617   template<typename F,
   618 	   typename K = typename F::argument_type,
   618            typename K = typename F::argument_type,
   619 	   typename V = typename F::result_type>
   619            typename V = typename F::result_type>
   620   class FunctorToMap : public MapBase<K, V> {
   620   class FunctorToMap : public MapBase<K, V> {
   621     F _f;
   621     F _f;
   622   public:
   622   public:
   623     typedef MapBase<K, V> Parent;
   623     typedef MapBase<K, V> Parent;
   624     typedef typename Parent::Key Key;
   624     typedef typename Parent::Key Key;
  1315   inline AbsMap<M> absMap(const M &m) {
  1315   inline AbsMap<M> absMap(const M &m) {
  1316     return AbsMap<M>(m);
  1316     return AbsMap<M>(m);
  1317   }
  1317   }
  1318 
  1318 
  1319   /// @}
  1319   /// @}
  1320   
  1320 
  1321   // Logical maps and map adaptors:
  1321   // Logical maps and map adaptors:
  1322 
  1322 
  1323   /// \addtogroup maps
  1323   /// \addtogroup maps
  1324   /// @{
  1324   /// @{
  1325 
  1325 
  1713   /// for the elements or the iterator should be an inserter iterator.
  1713   /// for the elements or the iterator should be an inserter iterator.
  1714 #ifdef DOXYGEN
  1714 #ifdef DOXYGEN
  1715   template <typename It, typename Ke>
  1715   template <typename It, typename Ke>
  1716 #else
  1716 #else
  1717   template <typename It,
  1717   template <typename It,
  1718 	    typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
  1718             typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
  1719 #endif
  1719 #endif
  1720   class LoggerBoolMap {
  1720   class LoggerBoolMap {
  1721   public:
  1721   public:
  1722     typedef It Iterator;
  1722     typedef It Iterator;
  1723 
  1723 
  1739     }
  1739     }
  1740 
  1740 
  1741     /// The set function of the map
  1741     /// The set function of the map
  1742     void set(const Key& key, Value value) {
  1742     void set(const Key& key, Value value) {
  1743       if (value) {
  1743       if (value) {
  1744 	*_end++ = key;
  1744         *_end++ = key;
  1745       }
  1745       }
  1746     }
  1746     }
  1747 
  1747 
  1748   private:
  1748   private:
  1749     Iterator _begin;
  1749     Iterator _begin;
  1750     Iterator _end;
  1750     Iterator _end;
  1751   };
  1751   };
  1752   
  1752 
  1753   /// Returns a \ref LoggerBoolMap class
  1753   /// Returns a \ref LoggerBoolMap class
  1754 
  1754 
  1755   /// This function just returns a \ref LoggerBoolMap class.
  1755   /// This function just returns a \ref LoggerBoolMap class.
  1756   ///
  1756   ///
  1757   /// The most important usage of it is storing certain nodes or arcs
  1757   /// The most important usage of it is storing certain nodes or arcs