#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>

       if ((*nodes)[target].first_in != -1) {

         edges[(*nodes)[target].first_in].prev_in = n;

       }

       if ((*nodes)[source].first_out != -1) {

         edges[(*nodes)[source].first_out].prev_out = n;

       }

       Node node;

       for (first(node); node != INVALID; next(node)) {

         (*nodes)[node].first_in = -1;

         (*nodes)[node].first_out = -1;

       }

       virtual ~NodesImpl() {}

       }

       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 ~NodesImpl() {}

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

     }

   };