Context Navigation

← Previous Change
Next Change →

deba

Timestamp:

07/14/04 12:06:27 (21 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@952

Message:

Location:

src/work/deba

Files:

: 1 added
: 4 edited

invalid.h (added)
list_graph.h (modified) (1 diff)
main.cpp (modified) (2 diffs)
map_defines.h (modified) (3 diffs)
map_registry.h (modified) (13 diffs)

Legend:

: Unmodified
: Added
: Removed

src/work/deba/list_graph.h

-                      r698
+                      r701
   ///should be implemented independently from ListGraph.
+  };
+  ///A graph class containing only nodes.
+  ///This class implements a graph structure without edges.
+  ///The most useful application of this class is to be the node set of an
+  ///\ref EdgeSet class.
+  ///
+  ///It conforms to the graph interface documented under
+  ///the description of \ref GraphSkeleton with the exception that you cannot
+  ///add (or delete) edges. The usual edge iterators are exists, but they are
+  ///always \ref INVALID.
+  ///\sa \ref GraphSkeleton
+  ///\sa \ref EdgeSet
+  class NodeSet {
+    //Nodes are double linked.
+    //The free nodes are only single linked using the "next" field.
+    struct NodeT
+    {
+      int first_in,first_out;
+      int prev, next;
+      //      NodeT() {}
+    };
+    std::vector<NodeT> nodes;
+    //The first node
+    int first_node;
+    //The first free node
+    int first_free_node;
+  protected:
+    template <typename Key> class DynMapBase
+    {
+    protected:
+      const NodeSet* G;
+    public:
+      virtual void add(const Key k) = 0;
+      virtual void erase(const Key k) = 0;
+      DynMapBase(const NodeSet &_G) : G(&_G) {}
+      virtual ~DynMapBase() {}
+      friend class NodeSet;
+    };
+  public:
+    template <typename T> class EdgeMap;
+    template <typename T> class NodeMap;
+    class Node;
+    class Edge;
+    //  protected:
+    // HELPME:
+  protected:
+    ///\bug It must be public because of SymEdgeMap.
+    ///
+    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
+    //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
+  public:
+    class NodeIt;
+    class EdgeIt;
+    class OutEdgeIt;
+    class InEdgeIt;
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
+  public:
+    ///Default constructor
+    NodeSet() : nodes(), first_node(-1),
+                  first_free_node(-1) {}
+    ///Copy constructor
+    NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
+                                     first_free_node(_g.first_free_node) {}
+    ~NodeSet()
+    {
+      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
+          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
+      //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
+      //          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
+    }
+    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
+    int edgeNum() const { return 0; }  //FIXME: What is this?
+    ///\bug This function does something different than
+    ///its name would suggests...
+    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
+    ///\bug This function does something different than
+    ///its name would suggests...
+    int maxEdgeId() const { return 0; }  //FIXME: What is this?
+    Node tail(Edge e) const { return INVALID; }
+    Node head(Edge e) const { return INVALID; }
+    Node aNode(OutEdgeIt e) const { return INVALID; }
+    Node aNode(InEdgeIt e) const { return INVALID; }
+    Node bNode(OutEdgeIt e) const { return INVALID; }
+    Node bNode(InEdgeIt e) const { return INVALID; }
+    NodeIt& first(NodeIt& v) const {
+      v=NodeIt(*this); return v; }
+    EdgeIt& first(EdgeIt& e) const {
+      e=EdgeIt(*this); return e; }
+    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
+      e=OutEdgeIt(*this,v); return e; }
+    InEdgeIt& first(InEdgeIt& e, const Node v) const {
+      e=InEdgeIt(*this,v); return e; }
+//     template< typename It >
+//     It first() const { It e; first(e); return e; }
+//     template< typename It >
+//     It first(Node v) const { It e; first(e,v); return e; }
+    bool valid(Edge e) const { return false; }
+    bool valid(Node n) const { return n.n!=-1; }
+    void setInvalid(Edge &e) { }
+    void setInvalid(Node &n) { n.n=-1; }
+    template <typename It> It getNext(It it) const
+    { It tmp(it); return next(tmp); }
+    NodeIt& next(NodeIt& it) const {
+      it.n=nodes[it.n].next;
+      return it;
+    }
+    OutEdgeIt& next(OutEdgeIt& it) const { return it; }
+    InEdgeIt& next(InEdgeIt& it) const { return it; }
+    EdgeIt& next(EdgeIt& it) const { return it; }
+    int id(Node v) const { return v.n; }
+    int id(Edge e) const { return -1; }
+    /// Adds a new node to the graph.
+    /// \todo It adds the nodes in a reversed order.
+    /// (i.e. the lastly added node becomes the first.)
+    Node addNode() {
+      int n;
+      if(first_free_node==-1)
+        {
+          n = nodes.size();
+          nodes.push_back(NodeT());
+        }
+      else {
+        n = first_free_node;
+        first_free_node = nodes[n].next;
+      }
+      nodes[n].next = first_node;
+      if(first_node != -1) nodes[first_node].prev = n;
+      first_node = n;
+      nodes[n].prev = -1;
+      nodes[n].first_in = nodes[n].first_out = -1;
+      Node nn; nn.n=n;
+      //Update dynamic maps
+      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
+          i!=dyn_node_maps.end(); ++i) (**i).add(nn);
+      return nn;
+    }
+    void erase(Node nn) {
+      int n=nn.n;
+      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
+      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
+      else first_node = nodes[n].next;
+      nodes[n].next = first_free_node;
+      first_free_node = n;
+      //Update dynamic maps
+      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
+          i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
+    }
+    ///\bug Dynamic maps must be updated!
+    ///
+    void clear() {
+      nodes.clear();
+      first_node = first_free_node = -1;
+    }
+    class Node {
+      friend class NodeSet;
+      template <typename T> friend class NodeMap;
+      friend class Edge;
+      friend class OutEdgeIt;
+      friend class InEdgeIt;
+    protected:
+      int n;
+      friend int NodeSet::id(Node v) const;
+      Node(int nn) {n=nn;}
+    public:
+      Node() {}
+      Node (Invalid i) { n=-1; }
+      bool operator==(const Node i) const {return n==i.n;}
+      bool operator!=(const Node i) const {return n!=i.n;}
+      bool operator<(const Node i) const {return n<i.n;}
+    };
+    class NodeIt : public Node {
+      friend class NodeSet;
+    public:
+      NodeIt() : Node() { }
+      NodeIt(Invalid i) : Node(i) { }
+      NodeIt(const NodeSet& G) : Node(G.first_node) { }
+      ///\todo Undocumented conversion Node -\> NodeIt.
+      NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
+    };
+    class Edge {
+      //friend class NodeSet;
+      //template <typename T> friend class EdgeMap;
+      //template <typename T> friend class SymNodeSet::SymEdgeMap;
+      //friend Edge SymNodeSet::opposite(Edge) const;
+      //      friend class Node;
+      //      friend class NodeIt;
+    protected:
+      //friend int NodeSet::id(Edge e) const;
+      //      Edge(int nn) {}
+    public:
+      Edge() { }
+      Edge (Invalid) { }
+      bool operator==(const Edge i) const {return true;}
+      bool operator!=(const Edge i) const {return false;}
+      bool operator<(const Edge i) const {return false;}
+      ///\bug This is a workaround until somebody tells me how to
+      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
+      //      int idref() {return -1;}
+      //      int idref() const {return -1;}
+    };
+    class EdgeIt : public Edge {
+      //friend class NodeSet;
+    public:
+      EdgeIt(const NodeSet& G) : Edge() { }
+      EdgeIt (Invalid i) : Edge(i) { }
+      EdgeIt() : Edge() { }
+      ///\bug This is a workaround until somebody tells me how to
+      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
+      //      int idref() {return -1;}
+    };
+    class OutEdgeIt : public Edge {
+      friend class NodeSet;
+    public:
+      OutEdgeIt() : Edge() { }
+      OutEdgeIt (Invalid i) : Edge(i) { }
+      OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
+    };
+    class InEdgeIt : public Edge {
+      friend class NodeSet;
+    public:
+      InEdgeIt() : Edge() { }
+      InEdgeIt (Invalid i) : Edge(i) { }
+      InEdgeIt(const NodeSet& G,Node v) :Edge() {}
+    };
+    template <typename T> class NodeMap : public DynMapBase<Node>
+    {
+      std::vector<T> container;
+    public:
+      typedef T ValueType;
+      typedef Node KeyType;
+      NodeMap(const NodeSet &_G) :
+        DynMapBase<Node>(_G), container(_G.maxNodeId())
+      {
+        G->dyn_node_maps.push_back(this);
+      }
+      NodeMap(const NodeSet &_G,const T &t) :
+        DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
+      {
+        G->dyn_node_maps.push_back(this);
+      }
+      NodeMap(const NodeMap<T> &m) :
+        DynMapBase<Node>(*m.G), container(m.container)
+      {
+        G->dyn_node_maps.push_back(this);
+      }
+      template<typename TT> friend class NodeMap;
+      ///\todo It can copy between different types.
+      ///
+      template<typename TT> NodeMap(const NodeMap<TT> &m) :
+        DynMapBase<Node>(*m.G), container(m.container.size())
+      {
+        G->dyn_node_maps.push_back(this);
+        typename std::vector<TT>::const_iterator i;
+        for(typename std::vector<TT>::const_iterator i=m.container.begin();
+            i!=m.container.end();
+            i++)
+          container.push_back(*i);
+      }
+      ~NodeMap()
+      {
+        if(G) {
+          std::vector<DynMapBase<Node>* >::iterator i;
+          for(i=G->dyn_node_maps.begin();
+              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
+          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
+          //A better way to do that: (Is this really important?)
+          if(*i==this) {
+            *i=G->dyn_node_maps.back();
+            G->dyn_node_maps.pop_back();
+          }
+        }
+      }
+      void add(const Node k)
+      {
+        if(k.n>=int(container.size())) container.resize(k.n+1);
+      }
+      void erase(const Node) { }
+      void set(Node n, T a) { container[n.n]=a; }
+      //'T& operator[](Node n)' would be wrong here
+      typename std::vector<T>::reference
+      operator[](Node n) { return container[n.n]; }
+      //'const T& operator[](Node n)' would be wrong here
+      typename std::vector<T>::const_reference
+      operator[](Node n) const { return container[n.n]; }
+      ///\warning There is no safety check at all!
+      ///Using operator = between maps attached to different graph may
+      ///cause serious problem.
+      ///\todo Is this really so?
+      ///\todo It can copy between different types.
+      const NodeMap<T>& operator=(const NodeMap<T> &m)
+      {
+        container = m.container;
+        return *this;
+      }
+      template<typename TT>
+      const NodeMap<T>& operator=(const NodeMap<TT> &m)
+      {
+        std::copy(m.container.begin(), m.container.end(), container.begin());
+        return *this;
+      }
+      void update() {}    //Useless for Dynamic Maps
+      void update(T a) {}  //Useless for Dynamic Maps
+    };
+    template <typename T> class EdgeMap
+    {
+    public:
+      typedef T ValueType;
+      typedef Edge KeyType;
+      EdgeMap(const NodeSet &) { }
+      EdgeMap(const NodeSet &,const T &) { }
+      EdgeMap(const EdgeMap<T> &) { }
+      //      template<typename TT> friend class EdgeMap;
+      ///\todo It can copy between different types.
+      ///
+      template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
+      ~EdgeMap() { }
+      void add(const Edge  ) { }
+      void erase(const Edge) { }
+      void set(Edge, T) { }
+      //T get(Edge n) const { return container[n.n]; }
+      ValueType &operator[](Edge) { return *((T*)(NULL)); }
+      const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
+      const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
+      template<typename TT>
+      const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
+      void update() {}
+      void update(T a) {}
+    };
+  };
+  ///Graph structure using a node set of another graph.
+  ///This structure can be used to establish another graph over a node set
+  /// of an existing one. The node iterator will go through the nodes of the
+  /// original graph, and the NodeMap's of both graphs will convert to
+  /// each other.
+  ///
+  ///\warning Adding or deleting nodes from the graph is not safe if an
+  ///\ref EdgeSet is currently attached to it!
+  ///
+  ///\todo Make it possible to add/delete edges from the base graph
+  ///(and from \ref EdgeSet, as well)
+  ///
+  ///\param GG The type of the graph which shares its node set with this class.
+  ///Its interface must conform with \ref GraphSkeleton.
+  ///
+  ///It conforms to the graph interface documented under
+  ///the description of \ref GraphSkeleton.
+  ///\sa \ref GraphSkeleton.
+  ///\sa \ref NodeSet.
+  template<typename GG>
+  class EdgeSet {
+    typedef GG NodeGraphType;
+    NodeGraphType &G;
+  public:
+    class Node;
+    int id(Node v) const;
+    class Node : public NodeGraphType::Node {
+      friend class EdgeSet;
+      //      template <typename T> friend class NodeMap;
+      friend class Edge;
+      friend class OutEdgeIt;
+      friend class InEdgeIt;
+      friend class SymEdge;
+    public:
+      friend int EdgeSet::id(Node v) const;
+      //      Node(int nn) {n=nn;}
+    public:
+      Node() : NodeGraphType::Node() {}
+      Node (Invalid i) : NodeGraphType::Node(i) {}
+      Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
+    };
+    class NodeIt : public NodeGraphType::NodeIt {
+      friend class EdgeSet;
+    public:
+      NodeIt() : NodeGraphType::NodeIt() { }
+      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
+      NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
+      NodeIt(const typename NodeGraphType::NodeIt &n)
+        : NodeGraphType::NodeIt(n) {}
+      ///\todo Undocumented conversion Node -\> NodeIt.
+      NodeIt(const EdgeSet& _G, const Node &n)
+        : NodeGraphType::NodeIt(_G.G,n) { }
+      operator Node() { return Node(*this);}
+    };
+  private:
+    //Edges are double linked.
+    //The free edges are only single linked using the "next_in" field.
+    struct NodeT
+    {
+      int first_in,first_out;
+      NodeT() : first_in(-1), first_out(-1) { }
+    };
+    struct EdgeT
+    {
+      Node head, tail;
+      int prev_in, prev_out;
+      int next_in, next_out;
+    };
+    typename NodeGraphType::template NodeMap<NodeT> nodes;
+    std::vector<EdgeT> edges;
+    //The first free edge
+    int first_free_edge;
+  protected:
+    template <typename Key> class DynMapBase
+    {
+    protected:
+      const EdgeSet* G;
+    public:
+      virtual void add(const Key k) = 0;
+      virtual void erase(const Key k) = 0;
+      DynMapBase(const EdgeSet &_G) : G(&_G) {}
+      virtual ~DynMapBase() {}
+      friend class EdgeSet;
+    };
+  public:
+    //template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
+    class Node;
+    class Edge;
+    //  protected:
+    // HELPME:
+  protected:
+    // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
+    ///\bug It must be public because of SymEdgeMap.
+    ///
+    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
+  public:
+    class NodeIt;
+    class EdgeIt;
+    class OutEdgeIt;
+    class InEdgeIt;
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
+  public:
+    ///Constructor
+    ///Construates a new graph based on the nodeset of an existing one.
+    ///\param _G the base graph.
+    ///\todo It looks like a copy constructor, but it isn't.
+    EdgeSet(NodeGraphType &_G) : G(_G),
+                                 nodes(_G), edges(),
+                                 first_free_edge(-1) { }
+    ///Copy constructor
+    ///Makes a copy of an EdgeSet.
+    ///It will be based on the same graph.
+    EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
+                                 first_free_edge(_g.first_free_edge) { }
+    ~EdgeSet()
+    {
+      // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
+      //  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
+      for(typename std::vector<DynMapBase<Edge> * >::iterator
+            i=dyn_edge_maps.begin();
+          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
+    }
+    int nodeNum() const { return G.nodeNum(); }  //FIXME: What is this?
+    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
+    ///\bug This function does something different than
+    ///its name would suggests...
+    int maxNodeId() const { return G.maxNodeId(); }  //FIXME: What is this?
+    ///\bug This function does something different than
+    ///its name would suggests...
+    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
+    Node tail(Edge e) const { return edges[e.n].tail; }
+    Node head(Edge e) const { return edges[e.n].head; }
+    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
+    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
+    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
+    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
+    NodeIt& first(NodeIt& v) const {
+      v=NodeIt(*this); return v; }
+    EdgeIt& first(EdgeIt& e) const {
+      e=EdgeIt(*this); return e; }
+    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
+      e=OutEdgeIt(*this,v); return e; }
+    InEdgeIt& first(InEdgeIt& e, const Node v) const {
+      e=InEdgeIt(*this,v); return e; }
+//     template< typename It >
+//     It first() const { It e; first(e); return e; }
+//     template< typename It >
+//     It first(Node v) const { It e; first(e,v); return e; }
+    bool valid(Edge e) const { return e.n!=-1; }
+    bool valid(Node n) const { return G.valid(n); }
+    void setInvalid(Edge &e) { e.n=-1; }
+    void setInvalid(Node &n) { G.setInvalid(n); }
+    template <typename It> It getNext(It it) const
+    { It tmp(it); return next(tmp); }
+    NodeIt& next(NodeIt& it) const { G.next(it); return it; }
+    OutEdgeIt& next(OutEdgeIt& it) const
+    { it.n=edges[it.n].next_out; return it; }
+    InEdgeIt& next(InEdgeIt& it) const
+    { it.n=edges[it.n].next_in; return it; }
+    EdgeIt& next(EdgeIt& it) const {
+      if(edges[it.n].next_in!=-1) {
+        it.n=edges[it.n].next_in;
+      }
+      else {
+        NodeIt n(*this,edges[it.n].head);
+        for(n=next(n);
+            valid(n) && nodes[n].first_in == -1;
+            next(n)) ;
+        it.n = (valid(n))?-1:nodes[n].first_in;
+      }
+      return it;
+    }
+    int id(Edge e) const { return e.n; }
+    /// Adds a new node to the graph.
+    Node addNode() { return G.addNode(); }
+    Edge addEdge(Node u, Node v) {
+      int n;
+      if(first_free_edge==-1)
+        {
+          n = edges.size();
+          edges.push_back(EdgeT());
+        }
+      else {
+        n = first_free_edge;
+        first_free_edge = edges[n].next_in;
+      }
+      edges[n].tail = u; edges[n].head = v;
+      edges[n].next_out = nodes[u].first_out;
+      if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
+      edges[n].next_in = nodes[v].first_in;
+      if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
+      edges[n].prev_in = edges[n].prev_out = -1;
+      nodes[u].first_out = nodes[v].first_in = n;
+      Edge e; e.n=n;
+      //Update dynamic maps
+      for(typename std::vector<DynMapBase<Edge> * >::iterator
+            i=dyn_edge_maps.begin();
+          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
+      return e;
+    }
+  private:
+    void eraseEdge(int n) {
+      if(edges[n].next_in!=-1)
+        edges[edges[n].next_in].prev_in = edges[n].prev_in;
+      if(edges[n].prev_in!=-1)
+        edges[edges[n].prev_in].next_in = edges[n].next_in;
+      else nodes[edges[n].head].first_in = edges[n].next_in;
+      if(edges[n].next_out!=-1)
+        edges[edges[n].next_out].prev_out = edges[n].prev_out;
+      if(edges[n].prev_out!=-1)
+        edges[edges[n].prev_out].next_out = edges[n].next_out;
+      else nodes[edges[n].tail].first_out = edges[n].next_out;
+      edges[n].next_in = first_free_edge;
+      first_free_edge = -1;
+      //Update dynamic maps
+      Edge e; e.n=n;
+      for(typename std::vector<DynMapBase<Edge> * >::iterator
+            i=dyn_edge_maps.begin();
+          i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
+    }
+  public:
+//     void erase(Node nn) {
+//       int n=nn.n;
+//       int m;
+//       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
+//       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
+//     }
+    void erase(Edge e) { eraseEdge(e.n); }
+    ///Clear all edges. (Doesn't clear the nodes!)
+    void clear() {
+      edges.clear();
+      first_free_edge=-1;
+    }
+//     //\bug Dynamic maps must be updated!
+//     //
+//     void clear() {
+//       nodes.clear();edges.clear();
+//       first_node=first_free_node=first_free_edge=-1;
+//     }
+  public:
+    template <typename T> class EdgeMap;
+    ///
+    class Edge {
+    public:
+      friend class EdgeSet;
+      template <typename T> friend class EdgeMap;
+      friend class Node;
+      friend class NodeIt;
+    public:
+      ///\bug It shoud be at least protected
+      ///
+      int n;
+    protected:
+      friend int EdgeSet::id(Edge e) const;
+      Edge(int nn) {n=nn;}
+    public:
+      Edge() { }
+      Edge (Invalid) { n=-1; }
+      bool operator==(const Edge i) const {return n==i.n;}
+      bool operator!=(const Edge i) const {return n!=i.n;}
+      bool operator<(const Edge i) const {return n<i.n;}
+      ///\bug This is a workaround until somebody tells me how to
+      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
+      int &idref() {return n;}
+      const int &idref() const {return n;}
+    };
+    class EdgeIt : public Edge {
+      friend class EdgeSet;
+      template <typename T> friend class EdgeMap;
+    public:
+      EdgeIt(const EdgeSet& G) : Edge() {
+        //              typename NodeGraphType::Node m;
+        NodeIt m;
+        for(G.first(m);
+            G.valid(m) && G.nodes[m].first_in == -1;  G.next(m));
+        //AJJAJ! This is a non sense!!!!!!!
+        this->n = G.valid(m)?-1:G.nodes[m].first_in;
+      }
+      EdgeIt (Invalid i) : Edge(i) { }
+      EdgeIt() : Edge() { }
+      ///\bug This is a workaround until somebody tells me how to
+      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
+      int &idref() {return this->n;}
+    };
+    class OutEdgeIt : public Edge {
+      friend class EdgeSet;
+    public:
+      OutEdgeIt() : Edge() { }
+      OutEdgeIt (Invalid i) : Edge(i) { }
+      OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
+    };
+    class InEdgeIt : public Edge {
+      friend class EdgeSet;
+    public:
+      InEdgeIt() : Edge() { }
+      InEdgeIt (Invalid i) : Edge(i) { }
+      InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
+    };
+    template <typename T> class NodeMap :
+      public NodeGraphType::template NodeMap<T>
+    {
+      //This is a must, the constructors need it.
+      typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
+    public:
+      NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
+      NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
+      //It is unnecessary
+      NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
+        ParentNodeMap(m) { }
+      ///\todo It can copy between different types.
+      ///
+      template<typename TT>
+      NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
+        : ParentNodeMap(m) { }
+    };
+    ///
+    template <typename T> class EdgeMap : public DynMapBase<Edge>
+    {
+    protected:
+    public:
+      ///\bug It should be at least protected
+      ///
+      std::vector<T> container;
+    public:
+      typedef T ValueType;
+      typedef Edge KeyType;
+      EdgeMap(const EdgeSet &_G) :
+        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
+      {
+        //FIXME: What if there are empty Id's?
+        //FIXME: Can I use 'this' in a constructor?
+        G->dyn_edge_maps.push_back(this);
+      }
+      EdgeMap(const EdgeSet &_G,const T &t) :
+        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
+      {
+        G->dyn_edge_maps.push_back(this);
+      }
+      EdgeMap(const EdgeMap<T> &m) :
+        DynMapBase<Edge>(*m.G), container(m.container)
+      {
+        G->dyn_edge_maps.push_back(this);
+      }
+      template<typename TT> friend class EdgeMap;
+      ///\todo It can copy between different types.
+      ///
+      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
+        DynMapBase<Edge>(*m.G), container(m.container.size())
+      {
+        G->dyn_edge_maps.push_back(this);
+        typename std::vector<TT>::const_iterator i;
+        for(typename std::vector<TT>::const_iterator i=m.container.begin();
+            i!=m.container.end();
+            i++)
+          container.push_back(*i);
+      }
+      ~EdgeMap()
+      {
+        if(G) {
+          typename std::vector<DynMapBase<Edge>* >::iterator i;
+          for(i=G->dyn_edge_maps.begin();
+              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
+          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
+          //A better way to do that: (Is this really important?)
+          if(*i==this) {
+            *i=G->dyn_edge_maps.back();
+            G->dyn_edge_maps.pop_back();
+          }
+        }
+      }
+      void add(const Edge k)
+      {
+        if(k.n>=int(container.size())) container.resize(k.n+1);
+      }
+      void erase(const Edge) { }
+      ///\bug This doesn't work. Why?
+      ///      void set(Edge n, T a) { container[n.n]=a; }
+      void set(Edge n, T a) { container[G->id(n)]=a; }
+      //T get(Edge n) const { return container[n.n]; }
+      typename std::vector<T>::reference
+      ///\bug This doesn't work. Why?
+      ///      operator[](Edge n) { return container[n.n]; }
+      operator[](Edge n) { return container[G->id(n)]; }
+      typename std::vector<T>::const_reference
+      ///\bug This doesn't work. Why?
+      ///      operator[](Edge n) const { return container[n.n]; }
+      operator[](Edge n) const { return container[G->id(n)]; }
+      ///\warning There is no safety check at all!
+      ///Using operator = between maps attached to different graph may
+      ///cause serious problem.
+      ///\todo Is this really so?
+      ///\todo It can copy between different types.
+      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
+      {
+        container = m.container;
+        return *this;
+      }
+      template<typename TT> friend class EdgeMap;
+      template<typename TT>
+      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
+      {
+        std::copy(m.container.begin(), m.container.end(), container.begin());
+        return *this;
+      }
+      void update() {}    //Useless for DynMaps
+      void update(T a) {}  //Useless for DynMaps
+    };
+  };
+  template<typename GG>
+  inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
+/// @}
+} //namespace hugo
+}
 #endif //HUGO_LIST_GRAPH_H

src/work/deba/main.cpp

-                      r698
+                      r701
     ListGraph::Node node = g.addNode();
+  }
   ListGraph::NodeMap<int> map(g);
+  ListGraph::NodeMap<int> map(g, 10);
   for (int i = 0; i < 10; ++i) {
     ListGraph::Node node = g.addNode();
 …
     cout << map[it] << endl;
+  }
+  ListGraph::NodeMap<int>::iterator pit;
+  for (pit = map.begin(); pit != map.end(); ++pit) {
+    cout << g.id(pit->first) << ' ' << pit->second << endl;
+  }
+  ListGraph::NodeMap<double> ot_map = map;
+  for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
+    ot_map[it] *= 2.1;
+    cout << ot_map[it] << endl;
+  }
+  ot_map = map;
+  for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
+    ot_map[it] *= 3.1;
+    cout << ot_map[it] << endl;
+  }
   return 0;
+}

src/work/deba/map_defines.h

-                      r676
+                      r701
 #define MAP_DEFINES_H
+/** Creates the EdgeMapRegistry type an declare a mutable instance
+ *  named edge_maps.
+ */
 #define CREATE_EDGE_MAP_REGISTRY \
 typedef MapRegistry<Graph, Edge, EdgeIt> EdgeMapRegistry; \
 EdgeMapRegistry edge_maps;
+mutable EdgeMapRegistry edge_maps;
+/** Creates the NodeMapRegistry type an declare a mutable instance
+ *  named node_maps.
+ */
 #define CREATE_NODE_MAP_REGISTRY \
 typedef MapRegistry<Graph, Node, NodeIt> NodeMapRegistry; \
 NodeMapRegistry node_maps;
+mutable NodeMapRegistry node_maps;
+/** Creates both map registries.
+ */
 #define CREATE_MAP_REGISTRIES \
 CREATE_NODE_MAP_REGISTRY \
 CREATE_EDGE_MAP_REGISTRY
+/** Creates a map a concrete factory type from a template map
+ *  factory to use as node map factory.
+ */
 #define CREATE_NODE_MAP_FACTORY(TemplateFactory) \
 typedef TemplateFactory<NodeMapRegistry> NodeMapFactory;
+/** Creates a map a concrete factory type from a template map
+ *  factory to use as edge map factory.
+ */
 #define CREATE_EDGE_MAP_FACTORY(TemplateFactory) \
 typedef TemplateFactory<EdgeMapRegistry> EdgeMapFactory;
+/** Creates both map factories.
+ */
 #define CREATE_MAP_FACTORIES(TemplateFactory) \
 CREATE_NODE_MAP_FACTORY(TemplateFactory) \
 CREATE_EDGE_MAP_FACTORY(TemplateFactory)
+/** Import a map from a concrete map factory. The import method is
+ *  an overloading of the map type.
+ *  The reason to use these macro is that the c++ does not support
+ *  the template typedefs. If a future release of the c++
+ *  supports this feature it should be fixed.
+ */
 #define IMPORT_NODE_MAP(Factory) \
 template <typename V> \
 …
 public: \
 NodeMap() {} \
+NodeMap(Graph& g) : Factory::Map<V>(g, g.node_maps) {} \
+NodeMap(const Graph& g) : Factory::Map<V>(&g, &(g.node_maps)) {} \
+NodeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
+NodeMap(const NodeMap& copy) : Factory::Map<V>(copy) {} \
+template <typename CMap> NodeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
+NodeMap& operator=(const NodeMap& copy) { \
+  this->Factory::Map<V>::operator=(copy); \
+  return *this; \
+} \
+template <typename CMap>NodeMap& operator=(const CMap& copy) { \
+  this->Factory::Map<V>::operator=<CMap>(copy); \
+  return *this; \
+} \
 };
+/** Import a map from a concrete map factory. The import method is
+ *  an overloading of the map type.
+ *  The reason to use these macro is that the c++ does not support
+ *  the template typedefs. If a future release of the c++
+ *  supports this feature it should be fixed.
+ */
 #define IMPORT_EDGE_MAP(Factory) \
 template <typename V> \
 …
 public: \
 EdgeMap() {} \
+EdgeMap(Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \
+EdgeMap(const Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \
+EdgeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
+EdgeMap(const EdgeMap& copy) : Factory::Map<V>(copy) {} \
+template <typename CMap> EdgeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
+EdgeMap& operator=(const EdgeMap& copy) { \
+  this->Factory::Map<V>::operator=(copy); \
+  return *this; \
+} \
+template <typename CMap>EdgeMap& operator=(const CMap& copy) { \
+  this->Factory::Map<V>::operator=<CMap>(copy); \
+  return *this; \
+} \
 };
+/** This macro creates both map factories and imports both maps.
+ */
 #define CREATE_MAPS(TemplateFactory) \
 CREATE_MAP_FACTORIES(TemplateFactory) \

src/work/deba/map_registry.h

-                      r676
+                      r701
 /**
     Registry class to register edge or node maps in the graph. The
     registry helps you to implement an observer pattern. If you add
     or erase an edge or node you must notify all the maps about the
     event.
+ * Registry class to register edge or node maps into the graph. The
+ * registry helps you to implement an observer pattern. If you add
+ * or erase an edge or node you must notify all the maps about the
+ * event.
 */
   template <typename G, typename K, typename KIt>
 …
+    ///.
+    ///.
+    ///
+    /**
+     * MapBase is the base class of the registered maps.
+     * It defines the core modification operations on the maps and
+     * implements some helper functions.
+     */
     class MapBase {
     public:
 …
       friend class Registry;
       /**
           Default constructor.
       */
+      /**
+       * Default constructor for MapBase.
+       */
       MapBase() : graph(0), registry(0) {}
       /**
           Simple constructor to register into a graph registry.
       */
       MapBase(Graph& g, Registry& r) : graph(&g), registry(0) {
+      /**
+       * Simple constructor to register into a graph registry.
+      */
+      MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) {
         r.attach(*this);
+      }
       /**
           Copy constructor with registering into the map.
+       * Copy constructor to register into the registry.
       */
 …
       /**
           Assign operator.
+       * Assign operator.
       */
 …
       /**
+          Destructor.
+       * Destructor.
       */
 …
+        }
+      }
+      /*
+       * Returns the graph that the map belongs to.
+      */
+      const Graph* getGraph() const { return graph; }
+    private:
+      const Graph* graph;
+      Registry* registry;
+      int registry_index;
     protected:
-      Graph* graph;
-      Registry* registry;
-      int registry_index;
       /**
 …
       virtual void destroy() {
         for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
+        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
           erase(it);
+        }
 …
   protected:
+    /**
+     * The container type of the maps.
+     */
     typedef std::vector<MapBase*> Container;
+    /**
+     * The container of the registered maps.
+     */
     Container container;
+    public:
+    ///.
+  public:
+    /**
+     * Default Constructor of the MapRegistry. It creates an empty registry.
+     */
     MapRegistry() {}
+    ///.
+    /**
+     * Copy Constructor of the MapRegistry. The new registry does not steal
+     * the maps from the right value. The new registry will be an empty.
+     */
     MapRegistry(const MapRegistry&) {}
+    ///.
+    /**
+     * Assign operator. The left value does not steal the maps
+     * from the right value. The left value will be an empty registry.
+     */
     MapRegistry& operator=(const MapRegistry&) {
       for (it = container.begin(); it != container.end(); ++it) {
 …
+    }
+    ///.
+    /**
+     * Destructor of the MapRegistry.
+     */
     ~MapRegistry() {
       typename Container::iterator it;
 …
     public:
+    ///.
+    /**
+     * Attach a map into thr registry. If the map has been attached
+     * into an other registry it is detached from that automaticly.
+     */
     void attach(MapBase& map) {
       if (map.registry) {
 …
+    }
+    ///.
+    /**
+     * Detach the map from the registry.
+     */
     void detach(MapBase& map) {
       container.back()->registry_index = map.registry_index;
 …
+    ///.
+    /**
+     * Notify all the registered maps about a Key added.
+     */
     virtual void add(Key& key) {
       typename Container::iterator it;
 …
+    }
+    ///.
+    /**
+     * Notify all the registered maps about a Key erased.
+     */
     virtual void erase(Key& key) {
       typename Container::iterator it;

Note: See TracChangeset for help on using the changeset viewer.