RhodeCode

  /// Simple wrapping of a map

  /// This \ref concepts::ReadMap "read only map" returns the simple

  /// wrapping of the given map. Sometimes the reference maps cannot be

  /// combined with simple read maps. This map adaptor wraps the given

  /// map to simple read map.

  ///

  /// The simplest way of using this map is through the wrapMap()

  /// function.

  ///

  /// \sa WrapWriteMap

  template<typename M>

  class WrapMap : public MapBase<typename M::Key, typename M::Value> {

    const M &_m;

  public:

    typedef MapBase<typename M::Key, typename M::Value> Parent;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    /// Constructor

    WrapMap(const M &m) : _m(m) {}

    /// \e

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

  };

  /// Returns a \ref WrapMap class

  /// This function just returns a \ref WrapMap class.

  /// \relates WrapMap

  template<typename M>

  inline WrapMap<M> wrapMap(const M &map) {

    return WrapMap<M>(map);

  }

  /// Simple writable wrapping of a map

  /// This \ref concepts::ReadWriteMap "read-write map" returns the simple

  /// wrapping of the given map. Sometimes the reference maps cannot be

  /// combined with simple read-write maps. This map adaptor wraps the

  /// given map to simple read-write map.

  ///

  /// The simplest way of using this map is through the wrapWriteMap()

  /// function.

  ///

  /// \sa WrapMap

  template<typename M>

  class WrapWriteMap : public MapBase<typename M::Key, typename M::Value> {

    M &_m;

  public:

    typedef MapBase<typename M::Key, typename M::Value> Parent;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    /// Constructor

    WrapWriteMap(M &m) : _m(m) {}

    /// \e

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

    /// \e

    void set(const Key &k, const Value &c) { _m.set(k, c); }

  };

  ///Returns a \ref WrapWriteMap class

  ///This function just returns a \ref WrapWriteMap class.

  ///\relates WrapWriteMap

  template<typename M>

  inline WrapWriteMap<M> wrapWriteMap(M &map) {

    return WrapWriteMap<M>(map);

  }

  namespace _maps_bits {

    template <typename Value>

    struct Identity {

      typedef Value argument_type;

      typedef Value result_type;

      Value operator()(const Value& val) const {

	return val;

      }

    };

    template <typename _Iterator, typename Enable = void>

    struct IteratorTraits {

      typedef typename std::iterator_traits<_Iterator>::value_type Value;

    };

    template <typename _Iterator>

    struct IteratorTraits<_Iterator,

      typename exists<typename _Iterator::container_type>::type>

    {

      typedef typename _Iterator::container_type::value_type Value;

    };

  }

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

  ///

  /// A \ref concepts::ReadWriteMap "read-write" 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 \ref Prim algorithm directly to the standard output.

  /// \code

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

  ///   EdgeIdMap edgeId(graph);

  ///

  ///   typedef MapToFunctor<EdgeIdMap> EdgeIdFunctor;

  ///   EdgeIdFunctor edgeIdFunctor(edgeId);

  ///

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

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

  ///

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

  /// \endcode

  ///

  /// \sa BackInserterBoolMap

  /// \sa FrontInserterBoolMap

  /// \sa InserterBoolMap

  ///

  /// \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;

    }

    /// Gives back the the 'after the last' iterator

    Iterator end() const {

      return _end;

    }

    /// The set function of the map

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

      if (value) {

	*_end++ = _functor(key);

      }

    }

  private:

    Iterator _begin;

    mutable Iterator _end;

    Functor _functor;

  };

  /// \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 typename Functor::argument_type Key;

    typedef bool Value;

    /// Constructor

    BackInserterBoolMap(Container& _container,

                        const Functor& _functor = Functor())

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

    /// The 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 typename Functor::argument_type Key;

    typedef bool Value;

    /// Constructor

    FrontInserterBoolMap(Container& _container,

                         const Functor& _functor = Functor())

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

    /// The 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

  /// the container.

  ///

  /// For example, if you want to store the cut arcs of the strongly

  /// connected components in a set you can use the next code:

  ///

  /// \code

  ///   set<Arc> cut_arcs;

  ///   InserterBoolMap<set<Arc> > inserter_map(cut_arcs);

  ///   stronglyConnectedCutArcs(digraph, cost, inserter_map);

  /// \endcode

  ///

  /// \sa BackInserterBoolMap

  /// \sa FrontInserterBoolMap

  template <typename Container,

            typename Functor =

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

  class InserterBoolMap {

  public:

    typedef typename Container::value_type Key;

    typedef bool Value;

    /// Constructor with specified iterator

    /// Constructor with specified iterator.

    /// \param _container The container for storing the elements.

    /// \param _it The elements will be inserted before this iterator.

    /// \param _functor The functor that is used when an element is stored.

    InserterBoolMap(Container& _container, typename Container::iterator _it,

                    const Functor& _functor = Functor())

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

    /// Constructor

    /// Constructor without specified iterator.

    /// The elements will be inserted before <tt>_container.end()</tt>.

    /// \param _container The container for storing the elements.

    /// \param _functor The functor that is used when an element is stored.

    InserterBoolMap(Container& _container, const Functor& _functor = Functor())

      : container(_container), it(_container.end()), functor(_functor) {}

    /// The set function of the map

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

      if (value) {

	it = container.insert(it, functor(key));

        ++it;

      }

    }

  private:

    Container& container;

    typename Container::iterator it;

    Functor functor;

  };

  /// \brief Writable bool map for filling each \c true assigned element with a

  /// given value.

  ///

  /// Writable bool map for filling each \c true assigned element with a

  /// given value. The value can set the container.

  ///

  /// The following code finds the connected components of a graph

  /// and stores it in the \c comp map:

  /// \code

  ///   typedef Graph::NodeMap<int> ComponentMap;

  ///   ComponentMap comp(graph);

  ///   typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;

  ///   ComponentFillerMap filler(comp, 0);

  ///

  ///   Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);

  ///   dfs.processedMap(filler);

  ///   dfs.init();

  ///   for (NodeIt it(graph); it != INVALID; ++it) {

  ///     if (!dfs.reached(it)) {

  ///       dfs.addSource(it);

  ///       dfs.start();

  ///       ++filler.fillValue();

  ///     }

  ///   }

  /// \endcode

  template <typename Map>

  class FillBoolMap {

  public:

    typedef typename Map::Key Key;

    typedef bool Value;

    /// Constructor

    FillBoolMap(Map& _map, const typename Map::Value& _fill)

      : map(_map), fill(_fill) {}

    /// Constructor

    FillBoolMap(Map& _map)

      : map(_map), fill() {}

    /// Gives back the current fill value

    const typename Map::Value& fillValue() const {

      return fill;

    }

    /// Gives back the current fill value

    typename Map::Value& fillValue() {

      return fill;

    }

    /// Sets the current fill value

    void fillValue(const typename Map::Value& _fill) {

      fill = _fill;

    }

    /// The set function of the map

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

      if (value) {

	map.set(key, fill);

      }

    }

  private:

    Map& map;

    typename Map::Value fill;

  };

  /// \brief Writable bool map for storing the sequence number of

  /// \c true assignments.

  ///

  /// Writable bool map that stores for each \c true assigned elements

  /// the sequence number of this setting.

  /// It makes it easy to calculate the leaving

  /// order of the nodes in the \ref Dfs algorithm.

  ///

  /// \code

  ///   typedef Digraph::NodeMap<int> OrderMap;

  ///   OrderMap order(digraph);

  ///   typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;

  ///   OrderSetterMap setter(order);

  ///   Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);

  ///   dfs.processedMap(setter);

  ///   dfs.init();

  ///   for (NodeIt it(digraph); it != INVALID; ++it) {

  ///     if (!dfs.reached(it)) {

  ///       dfs.addSource(it);

  ///       dfs.start();

  ///     }

  ///   }

  /// \endcode

  ///

  /// The storing of the discovering order is more difficult because the

  /// ReachedMap should be readable in the dfs algorithm but the setting

  /// order map is not readable. Thus we must use the fork map:

  ///

  /// \code

  ///   typedef Digraph::NodeMap<int> OrderMap;

  ///   OrderMap order(digraph);

  ///   typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;

  ///   OrderSetterMap setter(order);

  ///   typedef Digraph::NodeMap<bool> StoreMap;

  ///   StoreMap store(digraph);

  ///

  ///   typedef ForkMap<StoreMap, OrderSetterMap> ReachedMap;

  ///   ReachedMap reached(store, setter);

  ///

  ///   Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);

  ///   dfs.reachedMap(reached);

  ///   dfs.init();

  ///   for (NodeIt it(digraph); it != INVALID; ++it) {

  ///     if (!dfs.reached(it)) {

  ///       dfs.addSource(it);

  ///       dfs.start();

  ///     }

  ///   }

  /// \endcode

  template <typename Map>

  class SettingOrderBoolMap {

  public:

    typedef typename Map::Key Key;

    typedef bool Value;

    /// Constructor

    SettingOrderBoolMap(Map& _map)

      : map(_map), counter(0) {}

    /// Number of set operations.

    int num() const {

      return counter;

    }

    /// The set function of the map

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

      if (value) {

	map.set(key, counter++);

      }

    }

  private:

    Map& map;

    int counter;

  };