RhodeCode

      /// \brief Gives back an item by its id.

      ///

      /// Gives back an item by its id.

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

    private:

      const Graph* _graph;

    };

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

    ///

    /// Gives back the inverse of the IdMap.

    InverseMap inverse() const { return InverseMap(*_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.

  /// The graph items can be accessed by their values either using

  /// \c InverseMap or \c operator()(), and the values of the map can be

  /// 

  /// This map is intended to be used when all associated values are

  /// different (the map is actually invertable) or there are only a few

  /// items with the same value.

  /// Otherwise consider to use \c IterableValueMap, which is more 

  /// suitable and more efficient for such cases. It provides iterators

  /// to traverse the items with the same associated value, however

  /// it does not have \c InverseMap.

  ///

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

  /// \c GR::Edge).

  /// \tparam V The value type of the map.

  ///

  /// \see IterableValueMap

  template <typename GR, typename K, typename V>

  class CrossRefMap

    : protected ItemSetTraits<GR, K>::template Map<V>::Type {

  private:

    typedef typename ItemSetTraits<GR, K>::

  public:

    /// The graph type of CrossRefMap.

    typedef GR Graph;

    typedef GR Digraph;

    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).

    typedef K Item;

    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).

    typedef K Key;

    /// The value type of CrossRefMap.

    typedef V Value;

    /// \brief Constructor.

    ///

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

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

    /// \brief Forward iterator for values.

    ///

    /// This iterator is an STL compatible forward

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

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

      friend class CrossRefMap;

    private:

        : it(_it) {}

    public:

      /// Constructor

      /// \e

      /// \e

        operator++();

        return tmp;

      }

      /// \e

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

      /// \e

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

      /// \e

      /// \e

    private:

      typename Container::const_iterator it;

    };

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

    ///

    /// Returns an STL compatible iterator to the

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

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

    /// range.

    }

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

    ///

    /// Returns an STL compatible iterator after the

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

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

    /// range.

    }

    /// \brief Sets the value associated with the given key.

    ///

    /// Sets the value associated with the given key.

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

      Value oldval = Map::operator[](key);

      typename Container::iterator it;

      for (it = _inv_map.equal_range(oldval).first;

           it != _inv_map.equal_range(oldval).second; ++it) {

        if (it->second == key) {

          _inv_map.erase(it);

          break;

        }

      }

      _inv_map.insert(std::make_pair(val, key));

      Map::set(key, val);

    }

    /// \brief Returns the value associated with the given key.

    ///

    /// Returns the value associated with the given key.

    typename MapTraits<Map>::ConstReturnValue

    operator[](const Key& key) const {

    virtual void clear() {

      _first.clear();

      Parent::clear();

    }

  private:

    std::vector<Key> _first;

  };

  namespace _maps_bits {

    template <typename Item, typename Value>

    struct IterableValueMapNode {

      IterableValueMapNode(Value _value = Value()) : value(_value) {}

      Item prev, next;

      Value value;

    };

  }

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

  ///

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

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

  /// the value (\c ItemIt), and the values of the map can be accessed

  /// The map stores a linked list for each value, which contains

  /// the items mapped to the value, and the used values are stored

  /// in balanced binary tree (\c std::map).

  ///

  /// \ref IterableBoolMap and \ref IterableIntMap are similar classes

  /// specialized for \c bool and \c int values, respectively.

  ///

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

  /// \c GR::Edge).

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

  /// value type.

  ///

  /// \see IterableBoolMap, IterableIntMap

  /// \see CrossRefMap

  template <typename GR, typename K, typename V>

  class IterableValueMap

    : protected ItemSetTraits<GR, K>::

        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {

  public:

    typedef typename ItemSetTraits<GR, K>::

    void lace(const Key& key) {

      typename Parent::Value& node = Parent::operator[](key);

      typename std::map<Value, Key>::iterator it = _first.find(node.value);

      if (it == _first.end()) {

        node.prev = node.next = INVALID;

        _first.insert(std::make_pair(node.value, key));

      } else {

        node.prev = INVALID;

        node.next = it->second;

        if (node.next != INVALID) {

          Parent::operator[](node.next).prev = key;

        }

        it->second = key;

      }

    }

  public:

    /// \brief Forward iterator for values.

    ///

    /// This iterator is an STL compatible forward

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

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

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

      friend class IterableValueMap;

    private:

        : it(_it) {}

    public:

      /// Constructor

      /// \e

      /// \e

        operator++();

        return tmp;

      }

      /// \e

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

      /// \e

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

      /// \e

      /// \e

    private:

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

    };

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

    ///

    /// Returns an STL compatible iterator to the

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

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

    /// range.

    }

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

    ///

    /// Returns an STL compatible iterator after the

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

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

    /// range.

    }

    /// \brief Set operation of the map.

    ///

    /// Set operation of the map.

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

      unlace(key);

      Parent::operator[](key).value = value;

      lace(key);

    }

    /// \brief Const subscript operator of the map.

    ///

    /// Const subscript operator of the map.

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

      return Parent::operator[](key).value;

    }

    /// \brief Iterator for the keys with the same value.

    ///

    /// Iterator for the keys with the same value. It works

    /// like a graph item iterator, it can be converted to

    /// the item type of the map, incremented with \c ++ operator, and

    /// if the iterator leaves the last valid item, it will be equal to

      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {

        lace(it);

      }

    }

    virtual void clear() {

      _first.clear();

      Parent::clear();

    }

  private:

    std::map<Value, Key> _first;

  };

  /// \brief Map of the source nodes of arcs in a digraph.

  ///

  /// SourceMap provides access for the source node of each arc in a digraph,

  /// which is returned by the \c source() function of the digraph.

  /// \tparam GR The digraph type.

  /// \see TargetMap

  template <typename GR>

  class SourceMap {

  public:

    typedef typename GR::Arc Key;

    typedef typename GR::Node Value;

    /// \brief Constructor

    ///

    /// Constructor.

    /// \param digraph The digraph that the map belongs to.

    explicit SourceMap(const GR& digraph) : _graph(digraph) {}

    /// \brief Returns the source node of the given arc.

    ///

    /// Returns the source node of the given arc.

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

      return _graph.source(arc);

    }

  private:

    const GR& _graph;

  };

  /// \brief Returns a \c SourceMap class.

  ///

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

  /// \relates SourceMap

  template <typename GR>

  inline SourceMap<GR> sourceMap(const GR& graph) {

    return SourceMap<GR>(graph);

  }

  /// \brief Map of the target nodes of arcs in a digraph.

  ///

  /// TargetMap provides access for the target node of each arc in a digraph,

  /// which is returned by the \c target() function of the digraph.

  /// \tparam GR The digraph type.

  /// \see SourceMap

  template <typename GR>

  class TargetMap {

  public:

    typedef typename GR::Arc Key;

    typedef typename GR::Node Value;

    /// \brief Constructor

    ///

    /// Constructor.

    /// \param digraph The digraph that the map belongs to.

    explicit TargetMap(const GR& digraph) : _graph(digraph) {}

    /// \brief Returns the target node of the given arc.

    ///

    /// Returns the target node of the given arc.

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

      return _graph.target(e);

    }

  private:

    const GR& _graph;

  };

  /// \brief Returns a \c TargetMap class.

  ///

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

  /// \relates TargetMap

  template <typename GR>

  inline TargetMap<GR> targetMap(const GR& graph) {

    return TargetMap<GR>(graph);

  }

  /// \brief Map of the "forward" directed arc view of edges in a graph.

  ///

  /// ForwardMap provides access for the "forward" directed arc view of

  /// each edge in a graph, which is returned by the \c direct() function

  /// of the graph with \c true parameter.

  /// \tparam GR The graph type.

  /// \see BackwardMap

  template <typename GR>

  class ForwardMap {

  public:

    typedef typename GR::Arc Value;

    /// \brief Constructor

    ///

    /// Constructor.

    /// \param graph The graph that the map belongs to.

    explicit ForwardMap(const GR& graph) : _graph(graph) {}

    /// \brief Returns the "forward" directed arc view of the given edge.

    ///

    /// Returns the "forward" directed arc view of the given edge.

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

      return _graph.direct(key, true);

    }

  private:

    const GR& _graph;

  };

  /// \brief Returns a \c ForwardMap class.

  ///

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

  /// \relates ForwardMap

  template <typename GR>

  inline ForwardMap<GR> forwardMap(const GR& graph) {

    return ForwardMap<GR>(graph);

  }

  /// \brief Map of the "backward" directed arc view of edges in a graph.

  ///

  /// BackwardMap provides access for the "backward" directed arc view of

  /// each edge in a graph, which is returned by the \c direct() function

  /// of the graph with \c false parameter.

  /// \tparam GR The graph type.

  /// \see ForwardMap

  template <typename GR>

  class BackwardMap {

  public:

    typedef typename GR::Arc Value;

    /// \brief Constructor

    ///

    /// Constructor.

    /// \param graph The graph that the map belongs to.

    explicit BackwardMap(const GR& graph) : _graph(graph) {}

    /// \brief Returns the "backward" directed arc view of the given edge.

    ///

    /// Returns the "backward" directed arc view of the given edge.

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

      return _graph.direct(key, false);

    }

  private:

    const GR& _graph;

  };

  /// \brief Returns a \c BackwardMap class

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

  /// \relates BackwardMap

  template <typename GR>

  inline BackwardMap<GR> backwardMap(const GR& graph) {

    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");

    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");

    gr.addEdge(n2, n0);

    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");

    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");

  }

  // CrossRefMap

  {

    typedef ListDigraph Graph;

    DIGRAPH_TYPEDEFS(Graph);

    checkConcept<ReadWriteMap<Node, int>,

                 CrossRefMap<Graph, Node, int> >();

    checkConcept<ReadWriteMap<Node, bool>,

                 CrossRefMap<Graph, Node, bool> >();

    checkConcept<ReadWriteMap<Node, double>,

                 CrossRefMap<Graph, Node, double> >();

    Graph gr;

    typedef CrossRefMap<Graph, Node, char> CRMap;

    CRMap map(gr);

    Node n0 = gr.addNode();

    Node n1 = gr.addNode();

    Node n2 = gr.addNode();

    map.set(n0, 'A');

    map.set(n1, 'B');

    map.set(n2, 'C');

    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,

          "Wrong CrossRefMap");

    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,

          "Wrong CrossRefMap");

    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,

          "Wrong CrossRefMap");

    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,

          "Wrong CrossRefMap::count()");

    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&

          it == map.endValue(), "Wrong value iterator");

    map.set(n2, 'A');

    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',

          "Wrong CrossRefMap");

    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");

    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");

    check(map('C') == INVALID && map.inverse()['C'] == INVALID,

          "Wrong CrossRefMap");

    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,

          "Wrong CrossRefMap::count()");

    it = map.beginValue();

    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&

          it == map.endValue(), "Wrong value iterator");

    map.set(n0, 'C');

    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',

          "Wrong CrossRefMap");

    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");

    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");

    const int num = 10;

    Graph g;

    std::vector<Item> items;

    for (int i = 0; i < num; ++i) {

      items.push_back(g.addNode());

    }

    Ivm map1(g, 0.0);

    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");

    check(*map1.beginValue() == 0.0, "Wrong value");

    for (int i = 0; i < num; ++i) {

      map1.set(items[i], static_cast<double>(i));

    }

    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");

    for (int i = 0; i < num; ++i) {

      Ivm::ItemIt it(map1, static_cast<double>(i));

      check(static_cast<Item>(it) == items[i], "Wrong value");

      ++it;

      check(static_cast<Item>(it) == INVALID, "Wrong value");

    }

         vit != map1.endValue(); ++vit) {

      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,

    }

    for (int i = 0; i < num; ++i) {

      map1.set(items[i], static_cast<double>(i % 2));

    }

    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");

    int n = 0;

    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {

      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");

      ++n;

    }

    check(n == (num + 1) / 2, "Wrong number");

    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {

      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");

      ++n;

    }

    check(n == num, "Wrong number");

  }

  return 0;

}