RhodeCode

  /// 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>).

  ///

  /// \sa ConstMap

  template<typename K, typename V>

  class NullMap : public MapBase<K, V> {

  public:

    ///\e

  /// Constant map.

  /// This \ref concepts::ReadMap "readable map" assigns a specified

  /// value to each key.

  ///

  /// In other aspects it is equivalent to \c NullMap.

  /// concept, but it absorbs the data written to it.

  ///

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

  /// function.

  ///

  /// \sa NullMap

  /// Constant map with inlined constant value.

  /// This \ref concepts::ReadMap "readable map" assigns a specified

  /// value to each key.

  ///

  /// In other aspects it is equivalent to \c NullMap.

  /// concept, but it absorbs the data written to it.

  ///

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

  /// function.

  ///

  /// \sa NullMap

  /// <tt>[0..size-1]</tt>.

  ///

  /// This map is essentially a wrapper for \c std::vector. It assigns

  /// values to integer keys from the range <tt>[0..size-1]</tt>.

  /// It can be used with some data structures, for example

  /// \c UnionFind, \c BinHeap, when the used items are small

  /// "ReferenceMap" concept.

  ///

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

  /// function.

  template <typename V>

  class RangeMap : public MapBase<int, V> {

  /// Map type based on \c std::map

  /// This map is essentially a wrapper for \c std::map with addition

  /// that you can specify a default value for the keys that are not

  /// stored actually. This value can be different from the default

  /// contructed value (i.e. \c %Value()).

  /// concept.

  ///

  /// This map is useful if a default value should be assigned to most of

  /// the keys and different values should be assigned only to a few

  /// keys (i.e. the map is "sparse").

  /// The name of this type also refers to this important usage.

  /// another type using the default conversion.

  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap

  /// "readable map" to another type using the default conversion.

  /// The \c Key type of it is inherited from \c M and the \c Value

  /// type is \c V.

  ///

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

  /// function.

  template <typename M, typename V>

  class ConvertMap : public MapBase<typename M::Key, V> {

    const M &_m;

  private:

    const Graph* _graph;

  public:

    ///

    /// \see inverse()

    class InverseMap {

    public:

      /// \brief Constructor.

      ///

      /// \brief Constructor.

      ///

      /// Constructor for creating an id-to-item map.

      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}

      ///

      Item operator[](int id) const { return _graph->fromId(id, Item());}

    private:

      const Graph* _graph;

    };

  /// \brief General cross reference graph map type.

  /// This class provides simple invertable graph maps.

  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)

  /// and if a key is set to a new value, then stores it in the inverse map.

  ///

  /// This type is not reference map, so it cannot be modified with

  /// the subscript operator.

  ///

  /// \tparam GR The graph type.

  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or

    ///

    /// Construct a new CrossRefMap for the given graph.

    explicit CrossRefMap(const Graph& graph) : Map(graph) {}

    /// \brief Forward iterator for values.

    ///

    /// iterator on the values of the map. The values can

    /// be accessed in the <tt>[beginValue, endValue)</tt> range.

    /// They are considered with multiplicity, so each value is

    /// traversed for each item it is assigned to.

    class ValueIterator

      : public std::iterator<std::forward_iterator_tag, Value> {

      friend class CrossRefMap;

    private:

      ValueIterator(typename Container::const_iterator _it)

        : it(_it) {}

    public:

      ValueIterator() {}

      ValueIterator& operator++() { ++it; return *this; }

      ValueIterator operator++(int) {

        ValueIterator tmp(*this);

        operator++();

        return tmp;

      }

      const Value& operator*() const { return it->first; }

      const Value* operator->() const { return &(it->first); }

      bool operator==(ValueIterator jt) const { return it == jt.it; }

      bool operator!=(ValueIterator jt) const { return it != jt.it; }

    private:

      typename Container::const_iterator it;

    };

    /// \brief Returns an iterator to the first value.

    ///

    /// first value of the map. The values of the

    /// map can be accessed in the <tt>[beginValue, endValue)</tt>

    /// range.

    ValueIterator beginValue() const {

      return ValueIterator(_inv_map.begin());

    }

    /// \brief Returns an iterator after the last value.

    ///

    /// last value of the map. The values of the

    /// map can be accessed in the <tt>[beginValue, endValue)</tt>

    /// range.

    ValueIterator endValue() const {

      return ValueIterator(_inv_map.end());

    }

      _inv_map.clear();

      Map::clear();

    }

  public:

    ///

    class InverseMap {

    public:

      /// \brief Constructor

      ///

      /// Constructor of the InverseMap.

      explicit InverseMap(const CrossRefMap& inverted)

      }

    private:

      const CrossRefMap& _inverted;

    };

    ///

    InverseMap inverse() const {

      return InverseMap(*this);

    }

  };

      Map::set(p, qi);

      _inv_map[qi] = p;

      Map::set(q, pi);

      _inv_map[pi] = q;

    }

    ///

    int operator[](const Item& item) const {

      return Map::operator[](item);

    }

    ///

    Item operator()(int id) const {

      return _inv_map[id];

    }

  private:

    Container _inv_map;

  public:

    /// \brief The inverse map type of RangeIdMap.

    ///

    class InverseMap {

    public:

      /// \brief Constructor

      ///

      /// Constructor of the InverseMap.

      explicit InverseMap(const RangeIdMap& inverted)

      /// The key type of the InverseMap.

      typedef typename RangeIdMap::Value Key;

      /// \brief Subscript operator.

      ///

      /// Subscript operator. It gives back the item

      Value operator[](const Key& key) const {

        return _inverted(key);

      }

      /// \brief Size of the map.

      ///

    private:

      const RangeIdMap& _inverted;

    };

    /// \brief Gives back the inverse of the map.

    ///

    const InverseMap inverse() const {

      return InverseMap(*this);

    }

  };

  /// \brief Dynamic iterable \c bool map.

  ///

  /// This class provides a special graph map type which can store a

  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).

  /// For both \c true and \c false values it is possible to iterate on

  ///

  /// This type is a reference map, so it can be modified with the

  ///

  /// \tparam GR The graph type.

  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or

  /// \c GR::Edge).

  ///

  /// \see IterableIntMap, IterableValueMap

  ///

  /// This class provides a special graph map type which can store an

  /// integer value for graph items (\c Node, \c Arc or \c Edge).

  /// For each non-negative value it is possible to iterate on the keys

  /// mapped to the value.

  ///

  /// This type is a reference map, so it can be modified with the

  ///

  /// \note The size of the data structure depends on the largest

  /// value in the map.

  ///

  /// \tparam GR The graph type.

  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or

      Value value;

    };

  }

  /// \brief Dynamic iterable map for comparable values.

  ///

  /// comparable value for graph items (\c Node, \c Arc or \c Edge).

  /// For each value it is possible to iterate on the keys mapped to

  ///

  ///

  /// This type is not reference map, so it cannot be modified with

  ///

  /// \tparam GR The graph type.

  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or

  /// \c GR::Edge).

  /// \tparam V The value type of the map. It can be any comparable

  /// value type.

    }

  public:

    /// \brief Forward iterator for values.

    ///

    /// iterator on the values of the map. The values can

    /// be accessed in the <tt>[beginValue, endValue)</tt> range.

    class ValueIterator

      : public std::iterator<std::forward_iterator_tag, Value> {

      friend class IterableValueMap;

    private:

      ValueIterator(typename std::map<Value, Key>::const_iterator _it)

        : it(_it) {}

    public:

      ValueIterator() {}

      ValueIterator& operator++() { ++it; return *this; }

      ValueIterator operator++(int) {

        ValueIterator tmp(*this);

        operator++();

        return tmp;

      }

      const Value& operator*() const { return it->first; }

      const Value* operator->() const { return &(it->first); }

      bool operator==(ValueIterator jt) const { return it == jt.it; }

      bool operator!=(ValueIterator jt) const { return it != jt.it; }

    private:

      typename std::map<Value, Key>::const_iterator it;

    };

    /// \brief Returns an iterator to the first value.

    ///

    /// first value of the map. The values of the

    /// map can be accessed in the <tt>[beginValue, endValue)</tt>

    /// range.

    ValueIterator beginValue() const {

      return ValueIterator(_first.begin());

    }

    /// \brief Returns an iterator after the last value.

    ///

    /// last value of the map. The values of the

    /// map can be accessed in the <tt>[beginValue, endValue)</tt>

    /// range.

    ValueIterator endValue() const {

      return ValueIterator(_first.end());

    }