RhodeCode

  };

  /// Returns a \c LoggerBoolMap class

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

  ///

  /// The most important usage of it is storing certain nodes or arcs

  /// that were marked \c true by an algorithm.

  /// For example it makes easier to store the nodes in the processing

  /// order of Dfs algorithm, as the following examples show.

  /// \code

  ///   std::vector<Node> v;

  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();

  /// \endcode

  /// \code

  ///   std::vector<Node> v(countNodes(g));

  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();

  /// \endcode

  ///

  /// \note The container of the iterator must contain enough space

  /// for the elements or the iterator should be an inserter iterator.

  ///

  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so

  /// it cannot be used when a readable map is needed, for example as

  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.

  ///

  /// \relates LoggerBoolMap

  template<typename Iterator>

  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {

    return LoggerBoolMap<Iterator>(it);

  }

  /// @}

  /// \addtogroup graph_maps

  /// @{

  /// \brief Provides an immutable and unique id for each item in a graph.

  ///

  /// IdMap provides a unique and immutable id for each item of the

  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 

  ///  - \b unique: different items get different ids,

  ///  - \b immutable: the id of an item does not change (even if you

  ///    delete other nodes).

  ///

  /// Using this map you get access (i.e. can read) the inner id values of

  /// the items stored in the graph, which is returned by the \c id()

  /// function of the graph. This map can be inverted with its member

  ///

  /// \tparam GR The graph type.

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

  /// \c GR::Edge).

  ///

  /// \see RangeIdMap

  template <typename GR, typename K>

  class IdMap : public MapBase<K, int> {

  public:

    /// The graph type of IdMap.

    typedef GR Graph;

    typedef GR Digraph;

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

    typedef K Item;

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

    typedef K Key;

    /// The value type of IdMap.

    typedef int Value;

    /// \brief Constructor.

    ///

    /// Constructor of the map.

    explicit IdMap(const Graph& graph) : _graph(&graph) {}

    /// \brief Gives back the \e id of the item.

    ///

    /// Gives back the immutable and unique \e id of the item.

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

    /// \brief Gives back the \e item by its id.

    ///

    /// Gives back the \e item by its id.

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

  private:

    const Graph* _graph;

  public:

    /// \brief This class represents the inverse of its owner (IdMap).

    ///

    /// This class represents the inverse of its owner (IdMap).

    /// \see inverse()

    class InverseMap {

    public:

      /// \brief Constructor.

      ///

      return ValueIterator(_inv_map.begin());

    }

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

    ValueIterator endValue() const {

      return ValueIterator(_inv_map.end());

    }

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

      return Map::operator[](key);

    }

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

    ///

    /// This function gives back an item that is assigned to

    /// the given value or \c INVALID if no such item exists.

    /// If there are more items with the same associated value,

    /// only one of them is returned.

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

      typename Container::const_iterator it = _inv_map.find(val);

      return it != _inv_map.end() ? it->second : INVALID;

    }

  protected:

    /// \brief Erase the key from the map and the inverse map.

    ///

    /// Erase the key from the map and the inverse map. It is called by the

    /// \c AlterationNotifier.

    virtual void erase(const Key& key) {

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

      typename Container::iterator it;

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

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

        if (it->second == key) {

          _inv_map.erase(it);

          break;

        }

      }

      Map::erase(key);

    }

    /// \brief Erase more keys from the map and the inverse map.

    ///

    /// Erase more keys from the map and the inverse map. It is called by the

    /// \c AlterationNotifier.

    virtual void erase(const std::vector<Key>& keys) {

      for (int i = 0; i < int(keys.size()); ++i) {

        Value val = Map::operator[](keys[i]);

        typename Container::iterator it;

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

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

          if (it->second == keys[i]) {

            _inv_map.erase(it);

            break;

          }

        }

      }

      Map::erase(keys);

    }

    /// \brief Clear the keys from the map and the inverse map.

    ///

    /// Clear the keys from the map and the inverse map. It is called by the

    /// \c AlterationNotifier.

    virtual void clear() {

      _inv_map.clear();

      Map::clear();

    }

  public:

    /// \brief The inverse map type.

    ///

    /// The inverse of this map. The subscript operator of the map

    /// gives back the item that was last assigned to the value.

    class InverseMap {

    public:

      /// \brief Constructor

      ///

      /// Constructor of the InverseMap.

      explicit InverseMap(const CrossRefMap& inverted)

        : _inverted(inverted) {}

      /// The value type of the InverseMap.

      typedef typename CrossRefMap::Key Value;

      /// The key type of the InverseMap.

      typedef typename CrossRefMap::Value Key;

      /// \brief Subscript operator.

      ///

      /// Subscript operator. It gives back an item

      /// that is assigned to the given value or \c INVALID

      /// if no such item exists.

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

        return _inverted(key);

      }

    private:

      const CrossRefMap& _inverted;

    };

    /// \brief It gives back the read-only inverse map.

    ///

    /// It gives back the read-only inverse map.

    InverseMap inverse() const {

      return InverseMap(*this);

    }

  };

  /// items of a graph.

  ///

  /// RangeIdMap provides a unique and continuous

  /// \c Edge) in a graph. This id is

  ///  - \b unique: different items get different ids,

  ///  - \b continuous: the range of the ids is the set of integers

  ///    between 0 and \c n-1, where \c n is the number of the items of

  ///    this type (\c Node, \c Arc or \c Edge).

  ///  - So, the ids can change when deleting an item of the same type.

  ///

  /// Thus this id is not (necessarily) the same as what can get using

  /// the \c id() function of the graph or \ref IdMap.

  /// This map can be inverted with its member class \c InverseMap,

  ///

  /// \tparam GR The graph type.

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

  /// \c GR::Edge).

  ///

  /// \see IdMap

  template <typename GR, typename K>

  class RangeIdMap

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

    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;

  public:

    /// The graph type of RangeIdMap.

    typedef GR Graph;

    typedef GR Digraph;

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

    typedef K Item;

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

    typedef K Key;

    /// The value type of RangeIdMap.

    typedef int Value;

    /// \brief Constructor.

    ///

    /// Constructor.

    explicit RangeIdMap(const Graph& gr) : Map(gr) {

      Item it;

      const typename Map::Notifier* nf = Map::notifier();

      for (nf->first(it); it != INVALID; nf->next(it)) {

        Map::set(it, _inv_map.size());

        _inv_map.push_back(it);

      }

    }

  protected:

    /// \brief Adds a new key to the map.

    ///

    /// Add a new key to the map. It is called by the

    /// \c AlterationNotifier.

    virtual void add(const Item& item) {

      Map::add(item);

      Map::set(item, _inv_map.size());

      _inv_map.push_back(item);

    }

    /// \brief Add more new keys to the map.

    check(negWriteMap(id)[1] == -1.0 && negWriteMap(id)[-10] == 10.0,

          "Something is wrong with NegWriteMap");

    check(absMap(id)[1] == 1.0 && absMap(id)[-10] == 10.0,

          "Something is wrong with AbsMap");

  }

  // Logical maps:

  // - TrueMap, FalseMap

  // - AndMap, OrMap

  // - NotMap, NotWriteMap

  // - EqualMap, LessMap

  {

    checkConcept<BoolMap, TrueMap<A> >();

    checkConcept<BoolMap, FalseMap<A> >();

    checkConcept<BoolMap, AndMap<BoolMap,BoolMap> >();

    checkConcept<BoolMap, OrMap<BoolMap,BoolMap> >();

    checkConcept<BoolMap, NotMap<BoolMap> >();

    checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >();

    checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >();

    checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();

    TrueMap<int> tm;

    FalseMap<int> fm;

    RangeMap<bool> rm(2);

    rm[0] = true; rm[1] = false;

    check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] &&

          !andMap(fm,rm)[0] && !andMap(fm,rm)[1],

          "Something is wrong with AndMap");

    check(orMap(tm,rm)[0] && orMap(tm,rm)[1] &&

          orMap(fm,rm)[0] && !orMap(fm,rm)[1],

          "Something is wrong with OrMap");

    check(!notMap(rm)[0] && notMap(rm)[1],

          "Something is wrong with NotMap");

    check(!notWriteMap(rm)[0] && notWriteMap(rm)[1],

          "Something is wrong with NotWriteMap");

    ConstMap<int, double> cm(2.0);

    IdentityMap<int> im;

    ConvertMap<IdentityMap<int>, double> id(im);

    check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],

          "Something is wrong with LessMap");

    check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],

          "Something is wrong with EqualMap");

  }

  // LoggerBoolMap

  {

    typedef std::vector<int> vec;

    vec v1;

    vec v2(10);

    LoggerBoolMap<std::back_insert_iterator<vec> >

      map1(std::back_inserter(v1));

    LoggerBoolMap<vec::iterator> map2(v2.begin());

    map1.set(10, false);

    map1.set(20, true);   map2.set(20, true);

    map1.set(30, false);  map2.set(40, false);

    map1.set(50, true);   map2.set(50, true);

    map1.set(60, true);   map2.set(60, true);

    check(v1.size() == 3 && v2.size() == 10 &&

          v1[0]==20 && v1[1]==50 && v1[2]==60 &&

          v2[0]==20 && v2[1]==50 && v2[2]==60,

          "Something is wrong with LoggerBoolMap");

    int i = 0;

    for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();

          it != map2.end(); ++it )

      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");

  }

  // CrossRefMap

  {

    typedef ListDigraph Graph;

    DIGRAPH_TYPEDEFS(Graph);

    checkConcept<ReadWriteMap<Node, int>,

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

    Graph gr;

    typedef CrossRefMap<Graph, Node, char> CRMap;

    typedef CRMap::ValueIterator ValueIt;

    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');

    map.set(n2, 'A');

    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");

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

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

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

  }

  return 0;

}