RhodeCode

      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {

	_graph.firstInc(*this, direction, n);

      }

      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)

	: graph(&_graph), Edge(ue) {

	direction = (_graph.source(ue) == n);

      }

      IncEdgeIt& operator++() {

	graph->nextInc(*this, direction);

	return *this; 

      }

    };

    // \brief Base node of the iterator

    //

    // Returns the base node (ie. the source in this case) of the iterator

    Node baseNode(const OutArcIt &e) const {

      return Parent::source(static_cast<const Arc&>(e));

    }

    // \brief Running node of the iterator

    //

    // Returns the running node (ie. the target in this case) of the

    // iterator

    Node runningNode(const OutArcIt &e) const {

      return Parent::target(static_cast<const Arc&>(e));

    }

    // \brief Base node of the iterator

    //

    // Returns the base node (ie. the target in this case) of the iterator

    Node baseNode(const InArcIt &e) const {

      return Parent::target(static_cast<const Arc&>(e));

    }

    // \brief Running node of the iterator

    //

    // Returns the running node (ie. the source in this case) of the

    // iterator

    Node runningNode(const InArcIt &e) const {

      return Parent::source(static_cast<const Arc&>(e));

    }

    // Base node of the iterator

    //

    // Returns the base node of the iterator

    Node baseNode(const IncEdgeIt &e) const {

      return e.direction ? u(e) : v(e);

    }

    // Running node of the iterator

    //

    // Returns the running node of the iterator

    Node runningNode(const IncEdgeIt &e) const {

      return e.direction ? v(e) : u(e);

    }

    template <typename _Value>

    class ArcMap 

      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {

      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;

    public:

	: Parent(_g) {}

      ArcMap(const Graph& _g, const _Value& _v) 

	: Parent(_g, _v) {}

      ArcMap& operator=(const ArcMap& cmap) {

	return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

	return *this;

      }

    };

    template <typename _Value>

    class EdgeMap 

      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {

      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

    public:

	: Parent(_g) {}

      EdgeMap(const Graph& _g, const _Value& _v) 

	: Parent(_g, _v) {}

      EdgeMap& operator=(const EdgeMap& cmap) {

	return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

	return *this;

      }

    };

    // Alteration extension

    Edge addEdge(const Node& from, const Node& to) {

      Edge edge = Parent::addEdge(from, to);

      notifier(Edge()).add(edge);

      std::vector<Arc> arcs;

      arcs.push_back(Parent::direct(edge, true));

      arcs.push_back(Parent::direct(edge, false));

      notifier(Arc()).add(arcs);

      return edge;

    }

    void clear() {

      notifier(Arc()).clear();

      notifier(Edge()).clear();

      Parent::clear();

    }

    void erase(const Edge& edge) {

      std::vector<Arc> arcs;

      arcs.push_back(Parent::direct(edge, true));

      arcs.push_back(Parent::direct(edge, false));

      notifier(Arc()).erase(arcs);

      notifier(Edge()).erase(edge);

      Parent::erase(edge);

    }

    EdgeSetExtender() {

      arc_notifier.setContainer(*this);

      edge_notifier.setContainer(*this);

    }

    ~EdgeSetExtender() {

      edge_notifier.clear();

      arc_notifier.clear();

    }

  };

}

#endif

      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {

        _graph->firstInc(*this, _direction, node);

      }

      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)

        : _graph(&graph), Edge(edge) {

        _direction = (_graph->source(edge) == node);

      }

      IncEdgeIt& operator++() {

        _graph->nextInc(*this, _direction);

        return *this;

      }

    };

    // \brief Base node of the iterator

    //

    // Returns the base node (ie. the source in this case) of the iterator

    Node baseNode(const OutArcIt &arc) const {

      return Parent::source(static_cast<const Arc&>(arc));

    }

    // \brief Running node of the iterator

    //

    // Returns the running node (ie. the target in this case) of the

    // iterator

    Node runningNode(const OutArcIt &arc) const {

      return Parent::target(static_cast<const Arc&>(arc));

    }

    // \brief Base node of the iterator

    //

    // Returns the base node (ie. the target in this case) of the iterator

    Node baseNode(const InArcIt &arc) const {

      return Parent::target(static_cast<const Arc&>(arc));

    }

    // \brief Running node of the iterator

    //

    // Returns the running node (ie. the source in this case) of the

    // iterator

    Node runningNode(const InArcIt &arc) const {

      return Parent::source(static_cast<const Arc&>(arc));

    }

    // Base node of the iterator

    //

    // Returns the base node of the iterator

    Node baseNode(const IncEdgeIt &edge) const {

      return edge._direction ? u(edge) : v(edge);

    }

    // Running node of the iterator

    //

    // Returns the running node of the iterator

    Node runningNode(const IncEdgeIt &edge) const {

      return edge._direction ? v(edge) : u(edge);

    }

    // Mappable extension

    template <typename _Value>

    class NodeMap

      : public MapExtender<DefaultMap<Graph, Node, _Value> > {

      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;

    public:

        : Parent(graph) {}

      NodeMap(const Graph& graph, const _Value& value)

        : Parent(graph, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap

      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {

      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;

    public:

        : Parent(graph) {}

      ArcMap(const Graph& graph, const _Value& value)

        : Parent(graph, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class EdgeMap

      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {

      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

    public:

        : Parent(graph) {}

      EdgeMap(const Graph& graph, const _Value& value)

        : Parent(graph, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

        return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

    // Alteration extension

    Node addNode() {

      Node node = Parent::addNode();

      notifier(Node()).add(node);

      return node;

    }

    Edge addEdge(const Node& from, const Node& to) {

      Edge edge = Parent::addEdge(from, to);

      notifier(Edge()).add(edge);

      std::vector<Arc> ev;

      ev.push_back(Parent::direct(edge, true));

      ev.push_back(Parent::direct(edge, false));

      notifier(Arc()).add(ev);

      return edge;

    }

    void clear() {

      notifier(Arc()).clear();

      notifier(Edge()).clear();

      notifier(Node()).clear();

      Parent::clear();

    }

    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>

    void build(const Graph& graph, NodeRefMap& nodeRef,

               EdgeRefMap& edgeRef) {

      Parent::build(graph, nodeRef, edgeRef);

      notifier(Node()).build();

      notifier(Edge()).build();

      notifier(Arc()).build();

    }

    void erase(const Node& node) {

      Arc arc;

      Parent::firstOut(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstOut(arc, node);

      }

      Parent::firstIn(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstIn(arc, node);

    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.

      ///

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

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

      /// \brief Constructor.

      ///

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

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

      /// \brief Gives back the given item from its id.

      ///

      /// Gives back the given item from 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.

  /// The values of the map can be accessed

  /// with stl compatible forward iterator.

  ///

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

      template Map<V>::Type Map;

    Container _inv_map;

  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.

    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.

    ///

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

    ValueIterator beginValue() const {

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

      }

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

    }

    ///

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

      }

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

        }

      }

      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.

      ///

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

    }

  };

  /// \brief Provides continuous and unique ID for the

  /// items of a graph.

  ///

  /// RangeIdMap provides a unique and continuous

  /// ID for each item of a given type (\c Node, \c Arc or

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

  /// or with the \c operator() 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 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());

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <deque>

#include <set>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

#include <lemon/maps.h>

#include "test_tools.h"

using namespace lemon;

using namespace lemon::concepts;

struct A {};

inline bool operator<(A, A) { return true; }

struct B {};

class C {

  int x;

public:

  C(int _x) : x(_x) {}

};

class F {

public:

  typedef A argument_type;

  typedef B result_type;

  B operator()(const A&) const { return B(); }

private:

  F& operator=(const F&);

};

int func(A) { return 3; }

int binc(int a, B) { return a+1; }

typedef ReadMap<A, double> DoubleMap;

typedef ReadWriteMap<A, double> DoubleWriteMap;

typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;

typedef ReadMap<A, bool> BoolMap;

typedef ReadWriteMap<A, bool> BoolWriteMap;

typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;

int main()

{

  // Map concepts

  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();

  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();

  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();

  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();

  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();

  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();

  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();

  checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();

  // NullMap

  {

    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();

    NullMap<A,B> map1;

    NullMap<A,B> map2 = map1;

    map1 = nullMap<A,B>();

  }

  // ConstMap

  {

    checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();

    checkConcept<ReadWriteMap<A,C>, ConstMap<A,C> >();

    ConstMap<A,B> map1;

    ConstMap<A,B> map2 = B();

  }

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

  }

  return 0;

}