# HG changeset patch
# User deba
# Date 1139245119 0
# Node ID c1c3a0fae8a1ae55009dacee04dbc2c3e82bd0aa
# Parent  8e19ca944727e3b6a2779361e80164bdfadeb346
Bug fixes in ListEdgeSet
Added SmartEdgeSet

diff -r 8e19ca944727 -r c1c3a0fae8a1 lemon/edge_set.h
--- a/lemon/edge_set.h	Mon Feb 06 15:52:32 2006 +0000
+++ b/lemon/edge_set.h	Mon Feb 06 16:58:39 2006 +0000
@@ -19,6 +19,14 @@
 #ifndef LEMON_EDGE_SET_H
 #define LEMON_EDGE_SET_H
 
+#include <lemon/bits/erasable_graph_extender.h>
+#include <lemon/bits/clearable_graph_extender.h>
+#include <lemon/bits/extendable_graph_extender.h>
+#include <lemon/bits/iterable_graph_extender.h>
+#include <lemon/bits/alteration_notifier.h>
+#include <lemon/bits/default_map.h>
+#include <lemon/bits/graph_extender.h>
+
 /// \ingroup graphs
 /// \file
 /// \brief EdgeSet classes.
@@ -92,8 +100,14 @@
 	first_free_edge = edges[first_free_edge].next_in;
       }
       edges[n].next_in = (*nodes)[target].first_in;
+      if ((*nodes)[target].first_in != -1) {
+        edges[(*nodes)[target].first_in].prev_in = n;
+      }
       (*nodes)[target].first_in = n;
       edges[n].next_out = (*nodes)[source].first_out;
+      if ((*nodes)[source].first_out != -1) {
+        edges[(*nodes)[source].first_out].prev_out = n;
+      }
       (*nodes)[source].first_out = n;
       edges[n].source = source;
       edges[n].target = target;
@@ -123,6 +137,11 @@
     }
 
     void clear() {
+      Node node;
+      for (first(node); node != INVALID; next(node)) {
+        (*nodes)[node].first_in = -1;
+        (*nodes)[node].first_out = -1;
+      }
       edges.clear();
       first_edge = -1;
       first_free_edge = -1;
@@ -173,10 +192,10 @@
     int id(const Node& node) const { return graph->id(node); }
     int id(const Edge& edge) const { return edge.id; }
 
-    Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
+    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
     Edge edgeFromId(int id) const { return Edge(id); }
 
-    int maxNodeId() const { return graph->maxId(Node()); };
+    int maxNodeId() const { return graph->maxNodeId(); };
     int maxEdgeId() const { return edges.size() - 1; }
 
     Node source(const Edge& edge) const { return edges[edge.id].source;}
@@ -208,7 +227,7 @@
   /// "StaticGraph" concept.
   ///
   /// In the edge extension and removing it conforms to the 
-  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
+  /// \ref concept::ErasableGraph "ErasableGraph" concept.
   template <typename _Graph>
   class ListEdgeSet :
     public ErasableEdgeSetExtender<
@@ -264,6 +283,8 @@
       
       NodesImpl(const Graph& graph, ListEdgeSet& edgeset) 
 	: Parent(graph), _edgeset(edgeset) {}
+
+      virtual ~NodesImpl() {}
       
     protected:
 
@@ -271,6 +292,12 @@
 	_edgeset.eraseNode(node);
 	Parent::erase(node);
       }
+      virtual void erase(const std::vector<Node>& nodes) {
+        for (int i = 0; i < (int)nodes.size(); ++i) {
+          _edgeset.eraseNode(nodes[i]);
+        }
+	Parent::erase(nodes);
+      }
       virtual void clear() {
 	_edgeset.clearNodes();
 	Parent::clear();
@@ -307,7 +334,7 @@
   /// "StaticGraph" concept.
   ///
   /// In the edge extension and removing it conforms to the 
-  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
+  /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
   template <typename _Graph>
   class ListUEdgeSet :
     public ErasableUEdgeSetExtender<
@@ -358,6 +385,8 @@
       
       NodesImpl(const Graph& graph, ListUEdgeSet& edgeset) 
 	: Parent(graph), _edgeset(edgeset) {}
+
+      virtual ~NodesImpl() {}
       
     protected:
 
@@ -366,7 +395,7 @@
 	Parent::erase(node);
       }
       virtual void erase(const std::vector<Node>& nodes) {
-	for (int i = 0; i < nodes.size(); ++i) {
+	for (int i = 0; i < (int)nodes.size(); ++i) {
 	  _edgeset.eraseNode(nodes[i]);
 	}
 	Parent::erase(nodes);
@@ -393,6 +422,341 @@
     
   };
 
+  template <typename _Graph>
+  class SmartEdgeSetBase {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+
+  protected:
+
+    struct NodeT {
+      int first_out, first_in;
+      NodeT() : first_out(-1), first_in(-1) {}
+    };
+
+    typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
+
+    NodesImplBase* nodes;
+
+    struct EdgeT {
+      Node source, target;
+      int next_out, next_in;
+      EdgeT() {}
+    };
+
+    std::vector<EdgeT> edges;
+
+    const Graph* graph;
+
+    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
+      graph = &_graph;
+      nodes = &_nodes;
+    }
+    
+  public:
+
+    class Edge {
+      friend class SmartEdgeSetBase<Graph>;
+    protected:
+      Edge(int _id) : id(_id) {}
+      int id;
+    public:
+      Edge() {}
+      Edge(Invalid) : id(-1) {}
+      bool operator==(const Edge& edge) const { return id == edge.id; }
+      bool operator!=(const Edge& edge) const { return id != edge.id; }
+      bool operator<(const Edge& edge) const { return id < edge.id; }
+    };
+
+    SmartEdgeSetBase() {} 
+
+    Edge addEdge(const Node& source, const Node& target) {
+      int n = edges.size();
+      edges.push_back(EdgeT());
+      edges[n].next_in = (*nodes)[target].first_in;
+      (*nodes)[target].first_in = n;
+      edges[n].next_out = (*nodes)[source].first_out;
+      (*nodes)[source].first_out = n;
+      edges[n].source = source;
+      edges[n].target = target;
+      return Edge(n);
+    }
+
+    void clear() {
+      Node node;
+      for (first(node); node != INVALID; next(node)) {
+        (*nodes)[node].first_in = -1;
+        (*nodes)[node].first_out = -1;
+      }
+      edges.clear();
+    }
+
+    void first(Node& node) const {
+      graph->first(node);
+    }
+
+    void next(Node& node) const {
+      graph->next(node);
+    }
+
+    void first(Edge& edge) const {
+      edge.id = edges.size() - 1;
+    }
+
+    void next(Edge& edge) const {
+      --edge.id;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      edge.id = (*nodes)[node].first_out;    
+    }
+    
+    void nextOut(Edge& edge) const {
+      edge.id = edges[edge.id].next_out;        
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      edge.id = (*nodes)[node].first_in;          
+    }
+
+    void nextIn(Edge& edge) const {
+      edge.id = edges[edge.id].next_in;    
+    }
+
+    int id(const Node& node) const { return graph->id(node); }
+    int id(const Edge& edge) const { return edge.id; }
+
+    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
+    Edge edgeFromId(int id) const { return Edge(id); }
+
+    int maxNodeId() const { return graph->maxNodeId(); };
+    int maxEdgeId() const { return edges.size() - 1; }
+
+    Node source(const Edge& edge) const { return edges[edge.id].source;}
+    Node target(const Edge& edge) const { return edges[edge.id].target;}
+
+    template <typename _Value>
+    class NodeMap : public Graph::template NodeMap<_Value> {
+    public:
+      typedef typename _Graph::template NodeMap<_Value> Parent;
+      explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset) 
+	: Parent(*edgeset.graph) { }
+      NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
+	: Parent(*edgeset.graph, value) { }
+    };
+
+  };
+
+
+  /// \ingroup semi_adaptors
+  ///
+  /// \brief Graph using a node set of another graph and an
+  /// own edge set.
+  ///
+  /// 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.
+  ///
+  /// \param _Graph The type of the graph which shares its node set with 
+  /// this class. Its interface must conform to the \ref concept::StaticGraph
+  /// "StaticGraph" concept.
+  ///
+  /// In the edge extension and removing it conforms to the 
+  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
+  template <typename _Graph>
+  class SmartEdgeSet :
+    public ClearableEdgeSetExtender<
+    ExtendableEdgeSetExtender<
+    MappableEdgeSetExtender<
+    IterableGraphExtender<
+    AlterableEdgeSetExtender<
+    GraphExtender<
+    SmartEdgeSetBase<_Graph> > > > > > > {
+
+  public:
+
+    typedef ClearableEdgeSetExtender<
+      ExtendableEdgeSetExtender<
+      MappableEdgeSetExtender<
+      IterableGraphExtender<
+      AlterableEdgeSetExtender<
+      GraphExtender<
+      SmartEdgeSetBase<_Graph> > > > > > > Parent;
+    
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    
+    typedef _Graph Graph;
+
+    class UnsupportedOperation : public LogicError {
+    public:
+      virtual const char* exceptionName() const {
+        return "lemon::SmartEdgeSet::UnsupportedOperation";
+      }
+    };
+    
+
+
+  protected:
+
+    typedef typename Parent::NodesImplBase NodesImplBase;
+
+    void eraseNode(const Node&) {
+      throw UnsupportedOperation();
+    }
+    
+    void clearNodes() {
+      Parent::clear();
+    }
+
+    class NodesImpl : public NodesImplBase {
+    public:
+      typedef NodesImplBase Parent;
+      
+      NodesImpl(const Graph& graph, SmartEdgeSet& edgeset) 
+	: Parent(graph), _edgeset(edgeset) {}
+
+      virtual ~NodesImpl() {}
+      
+    protected:
+
+      virtual void erase(const Node& node) {
+	_edgeset.eraseNode(node);
+	Parent::erase(node);
+      }
+      virtual void erase(const std::vector<Node>& nodes) {
+        for (int i = 0; i < (int)nodes.size(); ++i) {
+          _edgeset.eraseNode(nodes[i]);
+        }
+	Parent::erase(nodes);
+      }
+      virtual void clear() {
+	_edgeset.clearNodes();
+	Parent::clear();
+      }
+
+    private:
+      SmartEdgeSet& _edgeset;
+    };
+
+    NodesImpl nodes;
+    
+  public:
+
+    /// \brief Constructor of the adaptor.
+    /// 
+    /// Constructor of the adaptor.
+    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
+      Parent::initalize(graph, nodes);
+    }
+    
+  };
+
+  /// \ingroup semi_adaptors
+  ///
+  /// \brief Graph using a node set of another graph and an
+  /// own uedge set.
+  ///
+  /// 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.
+  ///
+  /// \param _Graph The type of the graph which shares its node set with 
+  /// this class. Its interface must conform to the \ref concept::StaticGraph
+  /// "StaticGraph" concept.
+  ///
+  /// In the edge extension and removing it conforms to the 
+  /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
+  template <typename _Graph>
+  class SmartUEdgeSet :
+    public ClearableUEdgeSetExtender<
+    ExtendableUEdgeSetExtender<
+    MappableUEdgeSetExtender<
+    IterableUGraphExtender<
+    AlterableUEdgeSetExtender<
+    UGraphExtender<
+    SmartEdgeSetBase<_Graph> > > > > > > {
+
+  public:
+
+    typedef ClearableUEdgeSetExtender<
+      ExtendableUEdgeSetExtender<
+      MappableUEdgeSetExtender<
+      IterableUGraphExtender<
+      AlterableUEdgeSetExtender<
+      UGraphExtender<
+      SmartEdgeSetBase<_Graph> > > > > > > Parent;
+    
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    
+    typedef _Graph Graph;
+
+    class UnsupportedOperation : public LogicError {
+    public:
+      virtual const char* exceptionName() const {
+        return "lemon::SmartUEdgeSet::UnsupportedOperation";
+      }
+    };
+
+  protected:
+
+    typedef typename Parent::NodesImplBase NodesImplBase;
+
+    void eraseNode(const Node&) {
+      throw UnsupportedOperation();
+    }
+    
+    void clearNodes() {
+      Parent::clear();
+    }
+
+    class NodesImpl : public NodesImplBase {
+    public:
+      typedef NodesImplBase Parent;
+      
+      NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset) 
+	: Parent(graph), _edgeset(edgeset) {}
+
+      virtual ~NodesImpl() {}
+      
+    protected:
+
+      virtual void erase(const Node& node) {
+	_edgeset.eraseNode(node);
+	Parent::erase(node);
+      }
+      virtual void erase(const std::vector<Node>& nodes) {
+	for (int i = 0; i < (int)nodes.size(); ++i) {
+	  _edgeset.eraseNode(nodes[i]);
+	}
+	Parent::erase(nodes);
+      }
+      virtual void clear() {
+	_edgeset.clearNodes();
+	Parent::clear();
+      }
+
+    private:
+      SmartUEdgeSet& _edgeset;
+    };
+
+    NodesImpl nodes;
+    
+  public:
+
+    /// \brief Constructor of the adaptor.
+    /// 
+    /// Constructor of the adaptor.
+    SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
+      Parent::initalize(graph, nodes);
+    }
+    
+  };
+
 }
 
 #endif
diff -r 8e19ca944727 -r c1c3a0fae8a1 test/Makefile.am
--- a/test/Makefile.am	Mon Feb 06 15:52:32 2006 +0000
+++ b/test/Makefile.am	Mon Feb 06 16:58:39 2006 +0000
@@ -17,6 +17,7 @@
 	counter_test \
 	dfs_test \
 	dijkstra_test \
+	edge_set_test \
 	graph_test \
 	graph_adaptor_test \
 	graph_utils_test \
@@ -54,6 +55,7 @@
 counter_test_SOURCES = counter_test.cc
 dfs_test_SOURCES = dfs_test.cc
 dijkstra_test_SOURCES = dijkstra_test.cc
+edge_set_test_SOURCES = edge_set_test.cc
 graph_test_SOURCES = graph_test.cc
 graph_utils_test_SOURCES = graph_utils_test.cc
 graph_adaptor_test_SOURCES = graph_adaptor_test.cc
diff -r 8e19ca944727 -r c1c3a0fae8a1 test/edge_set_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/edge_set_test.cc	Mon Feb 06 16:58:39 2006 +0000
@@ -0,0 +1,33 @@
+// -*- c++ -*-
+
+#include <iostream>
+#include <vector>
+
+#include <lemon/concept/graph.h>
+#include <lemon/concept/ugraph.h>
+#include <lemon/smart_graph.h>
+
+#include <lemon/edge_set.h>
+
+#include "test_tools.h"
+#include "graph_test.h"
+#include "map_test.h"
+
+
+using namespace lemon;
+using namespace lemon::concept;
+
+typedef StaticGraph Graph;
+
+int main() {
+  { // checking edge_sets
+    checkConcept<StaticGraph, ListEdgeSet<Graph> >();
+    checkConcept<UGraph, ListUEdgeSet<Graph> >();
+    checkConcept<StaticGraph, SmartEdgeSet<Graph> >();
+    checkConcept<UGraph, SmartUEdgeSet<Graph> >();
+  }
+
+  std::cout << __FILE__ ": All tests passed.\n";
+
+  return 0;
+}