1.1 --- a/lemon/graph_adaptor.h	Fri Jun 10 12:16:56 2005 +0000
     1.2 +++ b/lemon/graph_adaptor.h	Fri Jun 10 12:22:22 2005 +0000
     1.3 @@ -27,7 +27,12 @@
     1.4  
     1.5  #include <lemon/invalid.h>
     1.6  #include <lemon/maps.h>
     1.7 +#include <lemon/bits/erasable_graph_extender.h>
     1.8 +#include <lemon/bits/clearable_graph_extender.h>
     1.9 +#include <lemon/bits/extendable_graph_extender.h>
    1.10  #include <lemon/bits/iterable_graph_extender.h>
    1.11 +#include <lemon/bits/alteration_notifier.h>
    1.12 +#include <lemon/bits/default_map.h>
    1.13  #include <lemon/bits/undir_graph_extender.h>
    1.14  #include <iostream>
    1.15  
    1.16 @@ -1210,6 +1215,280 @@
    1.17  
    1.18    };
    1.19  
    1.20 +  /// \e
    1.21 +  template <typename _Graph>
    1.22 +  class NewEdgeSetAdaptorBase {
    1.23 +  public:
    1.24 +
    1.25 +    typedef _Graph Graph;
    1.26 +    typedef typename Graph::Node Node;
    1.27 +    typedef typename Graph::NodeIt NodeIt;
    1.28 +
    1.29 +  protected:
    1.30 +
    1.31 +    struct NodeT {
    1.32 +      int first_out, first_in;
    1.33 +      NodeT() : first_out(-1), first_in(-1) {}
    1.34 +    };
    1.35 +    
    1.36 +    class NodesImpl : protected Graph::template NodeMap<NodeT> {
    1.37 +
    1.38 +      typedef typename Graph::template NodeMap<NodeT> Parent;
    1.39 +      typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
    1.40 +
    1.41 +      Adaptor& adaptor;
    1.42 +
    1.43 +    public:
    1.44 +
    1.45 +      NodesImpl(Adaptor& _adaptor, const Graph& _graph) 
    1.46 +	: Parent(_graph), adaptor(_adaptor) {}
    1.47 +
    1.48 +      virtual ~NodesImpl() {}
    1.49 +
    1.50 +      virtual void build() {
    1.51 +	Parent::build();
    1.52 +      }
    1.53 +
    1.54 +      virtual void clear() {
    1.55 +	adaptor._clear();
    1.56 +	Parent::clear();
    1.57 +      }
    1.58 +      
    1.59 +      virtual void add(const Node& node) {
    1.60 +	Parent::add(node);
    1.61 +	adaptor._add(node);
    1.62 +      }
    1.63 +      
    1.64 +      virtual void erase(const Node& node) {
    1.65 +	adaptor._erase(node);
    1.66 +	Parent::erase(node);
    1.67 +      }
    1.68 +
    1.69 +      NodeT& operator[](const Node& node) {
    1.70 +	return Parent::operator[](node);
    1.71 +      }
    1.72 +
    1.73 +      const NodeT& operator[](const Node& node) const {
    1.74 +	return Parent::operator[](node);
    1.75 +      }
    1.76 +      
    1.77 +    };
    1.78 +
    1.79 +    NodesImpl* nodes;
    1.80 +
    1.81 +    struct EdgeT {
    1.82 +      Node source, target;
    1.83 +      int next_out, next_in;
    1.84 +      int prev_out, prev_in;
    1.85 +      EdgeT() : prev_out(-1), prev_in(-1) {}
    1.86 +    };
    1.87 +
    1.88 +    std::vector<EdgeT> edges;
    1.89 +
    1.90 +    int first_edge;
    1.91 +    int first_free_edge;
    1.92 +
    1.93 +    virtual void _clear() = 0;
    1.94 +    virtual void _add(const Node& node) = 0;
    1.95 +    virtual void _erase(const Node& node) = 0;
    1.96 +    
    1.97 +    const Graph* graph;
    1.98 +
    1.99 +    void initalize(const Graph& _graph, NodesImpl& _nodes) {
   1.100 +      graph = &_graph;
   1.101 +      nodes = &_nodes;
   1.102 +    }
   1.103 +    
   1.104 +  public:
   1.105 +
   1.106 +    class Edge {
   1.107 +      friend class NewEdgeSetAdaptorBase<Graph>;
   1.108 +    protected:
   1.109 +      Edge(int _id) : id(_id) {}
   1.110 +      int id;
   1.111 +    public:
   1.112 +      Edge() {}
   1.113 +      Edge(Invalid) : id(-1) {}
   1.114 +      bool operator==(const Edge& edge) const { return id == edge.id; }
   1.115 +      bool operator!=(const Edge& edge) const { return id != edge.id; }
   1.116 +      bool operator<(const Edge& edge) const { return id < edge.id; }
   1.117 +    };
   1.118 +
   1.119 +    NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {} 
   1.120 +    virtual ~NewEdgeSetAdaptorBase() {}
   1.121 +
   1.122 +    Edge addEdge(const Node& source, const Node& target) {
   1.123 +      int n;
   1.124 +      if (first_free_edge == -1) {
   1.125 +	n = edges.size();
   1.126 +	edges.push_back(EdgeT());
   1.127 +      } else {
   1.128 +	n = first_free_edge;
   1.129 +	first_free_edge = edges[first_free_edge].next_in;
   1.130 +      }
   1.131 +      edges[n].next_in = (*nodes)[target].first_in;
   1.132 +      (*nodes)[target].first_in = n;
   1.133 +      edges[n].next_out = (*nodes)[source].first_out;
   1.134 +      (*nodes)[source].first_out = n;
   1.135 +      edges[n].source = source;
   1.136 +      edges[n].target = target;
   1.137 +      return Edge(n);
   1.138 +    }
   1.139 +
   1.140 +    void erase(const Edge& edge) {
   1.141 +      int n = edge.id;
   1.142 +      if (edges[n].prev_in != -1) {
   1.143 +	edges[edges[n].prev_in].next_in = edges[n].next_in;
   1.144 +      } else {
   1.145 +	(*nodes)[edges[n].target].first_in = edges[n].next_in;
   1.146 +      }
   1.147 +      if (edges[n].next_in != -1) {
   1.148 +	edges[edges[n].next_in].prev_in = edges[n].prev_in;
   1.149 +      }
   1.150 +
   1.151 +      if (edges[n].prev_out != -1) {
   1.152 +	edges[edges[n].prev_out].next_out = edges[n].next_out;
   1.153 +      } else {
   1.154 +	(*nodes)[edges[n].source].first_out = edges[n].next_out;
   1.155 +      }
   1.156 +      if (edges[n].next_out != -1) {
   1.157 +	edges[edges[n].next_out].prev_out = edges[n].prev_out;
   1.158 +      }
   1.159 +           
   1.160 +    }
   1.161 +
   1.162 +    void first(Node& node) const {
   1.163 +      graph->first(node);
   1.164 +    }
   1.165 +
   1.166 +    void next(Node& node) const {
   1.167 +      graph->next(node);
   1.168 +    }
   1.169 +
   1.170 +    void first(Edge& edge) const {
   1.171 +      Node node;
   1.172 +      for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 
   1.173 +	   next(node));
   1.174 +      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
   1.175 +    }
   1.176 +
   1.177 +    void next(Edge& edge) const {
   1.178 +      if (edges[edge.id].next_in != -1) {
   1.179 +	edge.id = edges[edge.id].next_in;
   1.180 +      } else {
   1.181 +	Node node = edges[edge.id].target;
   1.182 +	for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 
   1.183 +	     next(node));
   1.184 +	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
   1.185 +      }      
   1.186 +    }
   1.187 +
   1.188 +    void firstOut(Edge& edge, const Node& node) const {
   1.189 +      edge.id = (*nodes)[node].first_out;    
   1.190 +    }
   1.191 +    
   1.192 +    void nextOut(Edge& edge) const {
   1.193 +      edge.id = edges[edge.id].next_out;        
   1.194 +    }
   1.195 +
   1.196 +    void firstIn(Edge& edge, const Node& node) const {
   1.197 +      edge.id = (*nodes)[node].first_in;          
   1.198 +    }
   1.199 +
   1.200 +    void nextIn(Edge& edge) const {
   1.201 +      edge.id = edges[edge.id].next_in;    
   1.202 +    }
   1.203 +
   1.204 +    int id(const Node& node) const { return graph->id(node); }
   1.205 +    int id(const Edge& edge) const { return edge.id; }
   1.206 +
   1.207 +    Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
   1.208 +    Edge fromId(int id, Edge) const { return Edge(id); }
   1.209 +
   1.210 +    int maxId(Node) const { return graph->maxId(Node()); };
   1.211 +    int maxId(Edge) const { return edges.size() - 1; }
   1.212 +
   1.213 +    Node source(const Edge& edge) const { return edges[edge.id].source;}
   1.214 +    Node target(const Edge& edge) const { return edges[edge.id].target;}
   1.215 +
   1.216 +  };
   1.217 +
   1.218 +  template <typename _Graph>
   1.219 +  class NewEdgeSetAdaptor :
   1.220 +    public ErasableGraphExtender<
   1.221 +    ClearableGraphExtender<
   1.222 +    ExtendableGraphExtender<
   1.223 +    DefaultMappableGraphExtender<
   1.224 +    IterableGraphExtender<
   1.225 +    AlterableGraphExtender<
   1.226 +    NewEdgeSetAdaptorBase<_Graph> > > > > > > {
   1.227 +
   1.228 +  public:
   1.229 +
   1.230 +    typedef ErasableGraphExtender<
   1.231 +      ClearableGraphExtender<
   1.232 +      ExtendableGraphExtender<
   1.233 +      DefaultMappableGraphExtender<
   1.234 +      IterableGraphExtender<
   1.235 +      AlterableGraphExtender<
   1.236 +      NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
   1.237 +    
   1.238 +
   1.239 +    typedef typename Parent::Node Node;
   1.240 +    typedef typename Parent::Edge Edge;
   1.241 +
   1.242 +  private:
   1.243 +
   1.244 +    virtual void _clear() {
   1.245 +      Parent::edges.clear();
   1.246 +      Parent::first_edge = -1;
   1.247 +      Parent::first_free_edge = -1;
   1.248 +      Parent::getNotifier(Edge()).clear();
   1.249 +      Parent::getNotifier(Node()).clear();
   1.250 +    }
   1.251 +
   1.252 +    virtual void _add(const Node& node) {
   1.253 +      Parent::getNotifier(Node()).add(node);
   1.254 +    }
   1.255 +
   1.256 +    virtual void _erase(const Node& node) {
   1.257 +      Edge edge;
   1.258 +      Parent::firstOut(edge, node);
   1.259 +      while (edge != INVALID) {
   1.260 +	Parent::erase(edge);
   1.261 +	Parent::firstOut(edge, node);
   1.262 +      }
   1.263 +
   1.264 +      Parent::firstIn(edge, node);
   1.265 +      while (edge != INVALID) {
   1.266 +	Parent::erase(edge);
   1.267 +	Parent::firstIn(edge, node);
   1.268 +      }
   1.269 +      
   1.270 +      Parent::getNotifier(Node()).erase(node);
   1.271 +    }
   1.272 +
   1.273 +
   1.274 +    typedef typename Parent::NodesImpl NodesImpl;
   1.275 +
   1.276 +    NodesImpl nodes;
   1.277 +    
   1.278 +  public:
   1.279 +
   1.280 +    NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
   1.281 +      Parent::initalize(_graph, nodes);
   1.282 +    }
   1.283 +
   1.284 +    void clear() {
   1.285 +      Parent::edges.clear();
   1.286 +      Parent::first_edge = -1;
   1.287 +      Parent::first_free_edge = -1;
   1.288 +
   1.289 +      Parent::getNotifier(Edge()).clear();      
   1.290 +    }
   1.291 +    
   1.292 +  };
   1.293 +
   1.294    ///@}
   1.295  
   1.296  } //namespace lemon