#include <lemon/bits/erasable_graph_extender.h>

 #include <lemon/bits/clearable_graph_extender.h>

 #include <lemon/bits/extendable_graph_extender.h>

 #include <lemon/bits/alteration_notifier.h>

 #include <lemon/bits/default_map.h>

   /// \e

   template <typename _Graph>

   class NewEdgeSetAdaptorBase {

   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) {}

     };

     class NodesImpl : protected Graph::template NodeMap<NodeT> {

       typedef typename Graph::template NodeMap<NodeT> Parent;

       typedef NewEdgeSetAdaptorBase<Graph> Adaptor;

       Adaptor& adaptor;

     public:

       NodesImpl(Adaptor& _adaptor, const Graph& _graph) 

 	: Parent(_graph), adaptor(_adaptor) {}

       virtual ~NodesImpl() {}

       virtual void build() {

 	Parent::build();

       }

       virtual void clear() {

 	adaptor._clear();

 	Parent::clear();

       }

       virtual void add(const Node& node) {

 	Parent::add(node);

 	adaptor._add(node);

       }

       virtual void erase(const Node& node) {

 	adaptor._erase(node);

 	Parent::erase(node);

       }

       NodeT& operator[](const Node& node) {

 	return Parent::operator[](node);

       }

       const NodeT& operator[](const Node& node) const {

 	return Parent::operator[](node);

       }

     };

     NodesImpl* nodes;

     struct EdgeT {

       Node source, target;

       int next_out, next_in;

       int prev_out, prev_in;

       EdgeT() : prev_out(-1), prev_in(-1) {}

     };

     std::vector<EdgeT> edges;

     int first_edge;

     int first_free_edge;

     virtual void _clear() = 0;

     virtual void _add(const Node& node) = 0;

     virtual void _erase(const Node& node) = 0;

     const Graph* graph;

     void initalize(const Graph& _graph, NodesImpl& _nodes) {

       graph = &_graph;

       nodes = &_nodes;

     }

   public:

     class Edge {

       friend class NewEdgeSetAdaptorBase<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; }

     };

     NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {} 

     virtual ~NewEdgeSetAdaptorBase() {}

     Edge addEdge(const Node& source, const Node& target) {

       int n;

       if (first_free_edge == -1) {

 	n = edges.size();

 	edges.push_back(EdgeT());

       } else {

 	n = first_free_edge;

 	first_free_edge = edges[first_free_edge].next_in;

       }

       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 erase(const Edge& edge) {

       int n = edge.id;

       if (edges[n].prev_in != -1) {

 	edges[edges[n].prev_in].next_in = edges[n].next_in;

       } else {

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

       }

       if (edges[n].next_in != -1) {

 	edges[edges[n].next_in].prev_in = edges[n].prev_in;

       }

       if (edges[n].prev_out != -1) {

 	edges[edges[n].prev_out].next_out = edges[n].next_out;

       } else {

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

       }

       if (edges[n].next_out != -1) {

 	edges[edges[n].next_out].prev_out = edges[n].prev_out;

       }

     }

     void first(Node& node) const {

       graph->first(node);

     }

     void next(Node& node) const {

       graph->next(node);

     }

     void first(Edge& edge) const {

       Node node;

       for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 

 	   next(node));

       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;

     }

     void next(Edge& edge) const {

       if (edges[edge.id].next_in != -1) {

 	edge.id = edges[edge.id].next_in;

       } else {

 	Node node = edges[edge.id].target;

 	for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 

 	     next(node));

 	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;

       }      

     }

     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 fromId(int id, Node) const { return graph->fromId(id, Node()); }

     Edge fromId(int id, Edge) const { return Edge(id); }

     int maxId(Node) const { return graph->maxId(Node()); };

     int maxId(Edge) 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 _Graph>

   class NewEdgeSetAdaptor :

     public ErasableGraphExtender<

     ClearableGraphExtender<

     ExtendableGraphExtender<

     DefaultMappableGraphExtender<

     IterableGraphExtender<

     AlterableGraphExtender<

     NewEdgeSetAdaptorBase<_Graph> > > > > > > {

   public:

     typedef ErasableGraphExtender<

       ClearableGraphExtender<

       ExtendableGraphExtender<

       DefaultMappableGraphExtender<

       IterableGraphExtender<

       AlterableGraphExtender<

       NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

   private:

     virtual void _clear() {

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

       Parent::getNotifier(Edge()).clear();

       Parent::getNotifier(Node()).clear();

     }

     virtual void _add(const Node& node) {

       Parent::getNotifier(Node()).add(node);

     }

     virtual void _erase(const Node& node) {

       Edge edge;

       Parent::firstOut(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstOut(edge, node);

       }

       Parent::firstIn(edge, node);

       while (edge != INVALID) {

 	Parent::erase(edge);

 	Parent::firstIn(edge, node);

       }

       Parent::getNotifier(Node()).erase(node);

     }

     typedef typename Parent::NodesImpl NodesImpl;

     NodesImpl nodes;

   public:

     NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {

       Parent::initalize(_graph, nodes);

     }

     void clear() {

       Parent::edges.clear();

       Parent::first_edge = -1;

       Parent::first_free_edge = -1;

       Parent::getNotifier(Edge()).clear();      

     }

   };