# HG changeset patch # User Peter Kovacs # Date 2008-03-15 21:24:43 # Node ID 7ff1c348ae0cd01bcf99975f6caada00fc51da67 # Parent 15968e25ca0848cb75539af99ad7e177f98166f7 Remove maps having unclear purposes or little use - WrapMap (SimpleMap) - WrapWriteMap (SimpleWriteMap) - StoreBoolMap - BackInserterBoolMap - FrontInserterBoolMap - InserterBoolMap - FillBoolMap - SettingOrderBoolMap diff --git a/lemon/maps.h b/lemon/maps.h --- a/lemon/maps.h +++ b/lemon/maps.h @@ -773,78 +773,6 @@ } - /// 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 - class WrapMap : public MapBase { - const M &_m; - public: - typedef MapBase 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 - inline WrapMap wrapMap(const M &map) { - return WrapMap(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 - class WrapWriteMap : public MapBase { - M &_m; - public: - typedef MapBase 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 - inline WrapWriteMap wrapWriteMap(M &map) { - return WrapWriteMap(map); - } - - /// Sum of two maps /// This \ref concepts::ReadMap "read only map" returns the sum @@ -1463,382 +1391,6 @@ return NotWriteMap(m); } - - namespace _maps_bits { - - template - struct Identity { - typedef Value argument_type; - typedef Value result_type; - Value operator()(const Value& val) const { - return val; - } - }; - - template - struct IteratorTraits { - typedef typename std::iterator_traits<_Iterator>::value_type Value; - }; - - template - struct IteratorTraits<_Iterator, - typename exists::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 EdgeIdMap; - /// EdgeIdMap edgeId(graph); - /// - /// typedef MapToFunctor EdgeIdFunctor; - /// EdgeIdFunctor edgeIdFunctor(edgeId); - /// - /// StoreBoolMap, EdgeIdFunctor> - /// writerMap(ostream_iterator(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 ::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 span_tree_edges; - /// BackInserterBoolMap > inserter_map(span_tree_edges); - /// prim(graph, cost, inserter_map); - /// \endcode - /// - /// \sa StoreBoolMap - /// \sa FrontInserterBoolMap - /// \sa InserterBoolMap - template > - 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 > - 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 cut_arcs; - /// InserterBoolMap > inserter_map(cut_arcs); - /// stronglyConnectedCutArcs(digraph, cost, inserter_map); - /// \endcode - /// - /// \sa BackInserterBoolMap - /// \sa FrontInserterBoolMap - template > - 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 _container.end(). - /// \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 ComponentMap; - /// ComponentMap comp(graph); - /// typedef FillBoolMap > ComponentFillerMap; - /// ComponentFillerMap filler(comp, 0); - /// - /// Dfs::DefProcessedMap::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 - 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 OrderMap; - /// OrderMap order(digraph); - /// typedef SettingOrderBoolMap OrderSetterMap; - /// OrderSetterMap setter(order); - /// Dfs::DefProcessedMap::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 OrderMap; - /// OrderMap order(digraph); - /// typedef SettingOrderBoolMap OrderSetterMap; - /// OrderSetterMap setter(order); - /// typedef Digraph::NodeMap StoreMap; - /// StoreMap store(digraph); - /// - /// typedef ForkMap ReachedMap; - /// ReachedMap reached(store, setter); - /// - /// Dfs::DefReachedMap::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 - 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; - }; - /// @} }