RhodeCode

#include <functional>

#include <vector>

#include <lemon/bits/utility.h>

// #include <lemon/bits/traits.h>

///\file

///\ingroup maps

///\brief Miscellaneous property maps

///

#include <map>

namespace lemon {

  /// \addtogroup maps

  /// @{

  /// Base class of maps.

  /// Base class of maps.

  /// It provides the necessary <tt>typedef</tt>s required by the map concept.

  template<typename K, typename T>

  class MapBase {

  public:

    typedef K Key;

    typedef T Value;

  };

  /// Null map. (a.k.a. DoNothingMap)

  /// This map can be used if you have to provide a map only for

  /// its type definitions, or if you have to provide a writable map, 

  /// but data written to it is not required (i.e. it will be sent to 

  /// <tt>/dev/null</tt>).

  template<typename K, typename T>

  class NullMap : public MapBase<K, T> {

  public:

    typedef MapBase<K, T> Parent;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    /// Gives back a default constructed element.

    T operator[](const K&) const { return T(); }

    /// Absorbs the value.

    void set(const K&, const T&) {}

  };

  ///Returns a \c NullMap class

	return _value;

    }

    /// \e 

    void set(const Key &k, const T &t) {

      typename Map::iterator it = _map.lower_bound(k);

      if (it != _map.end() && !_map.key_comp()(k, it->first))

	it->second = t;

      else

	_map.insert(it, std::make_pair(k, t));

    }

    /// \e

    void setAll(const T &t) {

      _value = t;

      _map.clear();

    }    

    template <typename T1, typename C1 = std::less<T1> >

    struct rebind {

      typedef StdMap<Key, T1, C1> other;

    };

  };

  ///

  /// are stored in a \c std::vector<T>  container. It can be used with

  /// some data structures, for example \c UnionFind, \c BinHeap, when 

  /// the used items are small integer numbers. 

  ///

  /// \todo Revise its name

  template <typename T>

  class IntegerMap {

    template <typename T1>

    friend class IntegerMap;

  public:

    typedef True ReferenceMapTag;

    ///\e

    typedef int Key;

    ///\e

    typedef T Value;

    ///\e

    typedef T& Reference;

    ///\e

    typedef const T& ConstReference;

  private:

  template<typename M1, typename M2, typename F,

	   typename V = typename F::result_type> 

  class CombineMap : public MapBase<typename M1::Key, V> {

    const M1& m1;

    const M2& m2;

    F f;

  public:

    typedef MapBase<typename M1::Key, V> Parent;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    ///Constructor

    CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())

      : m1(_m1), m2(_m2), f(_f) {};

    /// \e

    Value operator[](Key k) const {return f(m1[k],m2[k]);}

  };

  ///Returns a \c CombineMap class

  ///This function just returns a \c CombineMap class.

  ///

  ///For example if \c m1 and \c m2 are both \c double valued maps, then 

  ///\code

  ///\endcode

  ///is equivalent to

  ///\code

  ///addMap(m1,m2)

  ///\endcode

  ///

  ///This function is specialized for adaptable binary function

  ///classes and C++ functions.

  ///

  ///\relates CombineMap

  template<typename M1, typename M2, typename F, typename V> 

  inline CombineMap<M1, M2, F, V> 

  combineMap(const M1& m1,const M2& m2, const F& f) {

    return CombineMap<M1, M2, F, V>(m1,m2,f);

  }

  template<typename M1, typename M2, typename F> 

  inline CombineMap<M1, M2, F, typename F::result_type> 

  combineMap(const M1& m1, const M2& m2, const F& f) {

    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);

  }

  template<typename M1, typename M2, typename K1, typename K2, typename V> 

  inline CombineMap<M1, M2, V (*)(K1, K2), V> 

    AbsMap(const M &_m) : m(_m) {};

    /// \e

    Value operator[](Key k) const {

      Value tmp = m[k]; 

      return tmp >= 0 ? tmp : -tmp;

    }

  };

  ///Returns an \c AbsMap class

  ///This function just returns an \c AbsMap class.

  ///\relates AbsMap

  template<typename M> 

  inline AbsMap<M> absMap(const M &m) {

    return AbsMap<M>(m);

  }

  ///Converts an STL style functor to a map

  ///This \c concepts::ReadMap "read only map" returns the value

  ///of a given functor.

  ///

  ///Template parameters \c K and \c V will become its

  ///

  ///Parameter \c F is the type of the used functor.

  ///

  ///\sa MapFunctor

  template<typename F, 

	   typename K = typename F::argument_type, 

	   typename V = typename F::result_type> 

  class FunctorMap : public MapBase<K, V> {

    F f;

  public:

    typedef MapBase<K, V> Parent;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    ///Constructor

    FunctorMap(const F &_f = F()) : f(_f) {}

    /// \e

    Value operator[](Key k) const { return f(k);}

  };

  ///Returns a \c FunctorMap class

  ///This function just returns a \c FunctorMap class.

  ///

  ///

  /// Writable bool map for logging each \c true assigned element, i.e it

  /// copies all the keys set to \c true to the given iterator.

  ///

  /// \note The container of the iterator should contain space 

  /// for each element.

  ///

  /// The following example shows how you can write the edges found by the Prim

  /// algorithm directly

  /// to the standard output.

  ///\code

  /// typedef IdMap<Graph, Edge> EdgeIdMap;

  /// EdgeIdMap edgeId(graph);

  ///

  /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;

  /// EdgeIdFunctor edgeIdFunctor(edgeId);

  ///

  /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor> 

  ///   writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);

  ///

  /// prim(graph, cost, writerMap);

  ///\endcode

  ///

  ///\sa BackInserterBoolMap 

  ///

  ///\todo Revise the name of this class and the related ones.

  template <typename _Iterator, 

            typename _Functor =

            _maps_bits::Identity<typename _maps_bits::

                                 IteratorTraits<_Iterator>::Value> >

  class StoreBoolMap {

  public:

    typedef _Iterator Iterator;

    typedef typename _Functor::argument_type Key;

    typedef bool Value;

    typedef _Functor Functor;

    /// Constructor

    StoreBoolMap(Iterator it, const Functor& functor = Functor()) 

      : _begin(it), _end(it), _functor(functor) {}

    /// Gives back the given iterator set for the first key

    Iterator begin() const {

      return _begin;

    }

  /// \brief Writable bool map for logging each \c true assigned element in 

  /// a back insertable container.

  ///

  /// Writable bool map for logging each \c true assigned element by pushing

  /// them into a back insertable container.

  /// It can be used to retrieve the items into a standard

  /// container. The next example shows how you can store the

  /// edges found by the Prim algorithm in a vector.

  ///

  ///\code

  /// vector<Edge> span_tree_edges;

  /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);

  /// prim(graph, cost, inserter_map);

  ///\endcode

  ///

  ///\sa StoreBoolMap

  ///\sa FrontInserterBoolMap

  ///\sa InserterBoolMap

  template <typename Container,

            typename Functor =

            _maps_bits::Identity<typename Container::value_type> >

  class BackInserterBoolMap {

  public:

    typedef bool Value;

    /// Constructor

    BackInserterBoolMap(Container& _container, 

                        const Functor& _functor = Functor()) 

      : container(_container), functor(_functor) {}

    /// The \c set function of the map

    void set(const Key& key, Value value) {

      if (value) {

	container.push_back(functor(key));

      }

    }

  private:

    Container& container;

    Functor functor;

  };

  /// \brief Writable bool map for logging each \c true assigned element in 

  /// a front insertable container.

  ///

  /// Writable bool map for logging each \c true assigned element by pushing

  /// them into a front insertable container.

  /// It can be used to retrieve the items into a standard

  /// container. For example see \ref BackInserterBoolMap.

  ///

  ///\sa BackInserterBoolMap

  ///\sa InserterBoolMap

  template <typename Container,

            typename Functor =

            _maps_bits::Identity<typename Container::value_type> >

  class FrontInserterBoolMap {

  public:

    typedef bool Value;

    /// Constructor

    FrontInserterBoolMap(Container& _container,

                         const Functor& _functor = Functor()) 

      : container(_container), functor(_functor) {}

    /// The \c set function of the map

    void set(const Key& key, Value value) {

      if (value) {

	container.push_front(functor(key));

      }

    }

  private:

    Container& container;    

    Functor functor;

  };

  /// \brief Writable bool map for storing each \c true assigned element in 

  /// an insertable container.

  ///

  /// Writable bool map for storing each \c true assigned element in an 

  /// insertable container. It will insert all the keys set to \c true into