/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2006

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_EDGE_SET_H

 #define LEMON_EDGE_SET_H

 #include <lemon/bits/default_map.h>

 #include <lemon/bits/edge_set_extender.h>

 /// \ingroup graphs

 /// \file

 /// \brief EdgeSet classes.

 ///

 /// Graphs which use another graph's node-set as own. 

 namespace lemon {

   template <typename _Graph>

   class ListEdgeSetBase {

   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 DefaultMap<Graph, Node, NodeT> NodesImplBase;

     NodesImplBase* 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;

     const Graph* graph;

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

       graph = &_graph;

       nodes = &_nodes;

     }

   public:

     class Edge {

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

     };

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

     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;

       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;

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

     }

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

     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

     NodeNotifier& getNotifier(Node) const {

       return graph->getNotifier(Node());

     } 

     template <typename _Value>

     class NodeMap : public Graph::template NodeMap<_Value> {

     public:

       typedef typename _Graph::template NodeMap<_Value> Parent;

       explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset) 

 	: Parent(*edgeset.graph) {}

       NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)

 	: Parent(*edgeset.graph, value) {}

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   /// \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::Graph

   /// "Graph" concept.

   ///

   /// In the edge extension and removing it conforms to the 

   /// \ref concept::Graph "Graph" concept.

   template <typename _Graph>

   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {

   public:

     typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     typedef _Graph Graph;

     typedef typename Parent::NodesImplBase NodesImplBase;

     void eraseNode(const Node& node) {

       Edge edge;

       Parent::firstOut(edge, node);

       while (edge != INVALID ) {

 	erase(edge);

 	Parent::firstOut(edge, node);

       } 

       Parent::firstIn(edge, node);

       while (edge != INVALID ) {

 	erase(edge);

 	Parent::firstIn(edge, node);

       }

     }

     void clearNodes() {

       Parent::clear();

     }

     class NodesImpl : public NodesImplBase {

     public:

       typedef NodesImplBase Parent;

       NodesImpl(const Graph& graph, ListEdgeSet& 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:

       ListEdgeSet& _edgeset;

     };

     NodesImpl nodes;

   public:

     /// \brief Constructor of the adaptor.

     /// 

     /// Constructor of the adaptor.

     ListEdgeSet(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::Graph

   /// "Graph" concept.

   ///

   /// In the edge extension and removing it conforms to the 

   /// \ref concept::UGraph "UGraph" concept.

   template <typename _Graph>

   class ListUEdgeSet 

     : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {

   public:

     typedef UEdgeSetExtender<UndirGraphExtender<

       ListEdgeSetBase<_Graph> > > Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     typedef _Graph Graph;

     typedef typename Parent::NodesImplBase NodesImplBase;

     void eraseNode(const Node& node) {

       Edge edge;

       Parent::firstOut(edge, node);

       while (edge != INVALID ) {

 	erase(edge);

 	Parent::firstOut(edge, node);

       } 

     }

     void clearNodes() {

       Parent::clear();

     }

     class NodesImpl : public NodesImplBase {

     public:

       typedef NodesImplBase Parent;

       NodesImpl(const Graph& graph, ListUEdgeSet& 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:

       ListUEdgeSet& _edgeset;

     };

     NodesImpl nodes;

   public:

     /// \brief Constructor of the adaptor.

     /// 

     /// Constructor of the adaptor.

     ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {

       Parent::initalize(graph, nodes);

     }

   };

   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 DefaultMap<Graph, Node, 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;}

     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

     NodeNotifier& getNotifier(Node) const {

       return graph->getNotifier(Node());

     } 

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

       NodeMap& operator=(const NodeMap& cmap) {

         return operator=<NodeMap>(cmap);

       }

       template <typename CMap>

       NodeMap& operator=(const CMap& cmap) {

         Parent::operator=(cmap);

         return *this;

       }

     };

   };

   /// \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::Graph

   /// "Graph" concept.

   ///

   /// In the edge extension and removing it conforms to the 

   /// \ref concept::Graph "Graph" concept.

   template <typename _Graph>

   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {

   public:

     typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     typedef _Graph Graph;

   protected:

     typedef typename Parent::NodesImplBase NodesImplBase;

     void eraseNode(const Node& node) {

       if (Parent::InEdgeIt(*this, node) == INVALID &&

           Parent::OutEdgeIt(*this, node) == INVALID) {

         return;

       }

       throw typename NodesImplBase::Notifier::ImmediateDetach();

     }

     void clearNodes() {

       Parent::clear();

     }

     class NodesImpl : public NodesImplBase {

     public:

       typedef NodesImplBase Parent;

       NodesImpl(const Graph& graph, SmartEdgeSet& edgeset) 

 	: Parent(graph), _edgeset(edgeset) {}

       virtual ~NodesImpl() {}

       bool attached() const {

         return Parent::attached();

       }

     protected:

       virtual void erase(const Node& node) {

         try {

           _edgeset.eraseNode(node);

           Parent::erase(node);

         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {

           Parent::clear();

           throw;

         }

       }

       virtual void erase(const std::vector<Node>& nodes) {

         try {

           for (int i = 0; i < (int)nodes.size(); ++i) {

             _edgeset.eraseNode(nodes[i]);

           }

           Parent::erase(nodes);

         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {

           Parent::clear();

           throw;

         }

       }

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

     }

     bool valid() const {

       return nodes.attached();

     }

   };

   /// \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::Graph

   /// "Graph" concept.

   ///

   /// In the edge extension and removing it conforms to the 

   /// \ref concept::UGraph "UGraph" concept.

   template <typename _Graph>

   class SmartUEdgeSet 

     : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {

   public:

     typedef UEdgeSetExtender<UndirGraphExtender<

       SmartEdgeSetBase<_Graph> > > Parent;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     typedef _Graph Graph;

   protected:

     typedef typename Parent::NodesImplBase NodesImplBase;

     void eraseNode(const Node& node) {

       if (typename Parent::IncEdgeIt(*this, node) == INVALID) {

         return;

       }

       throw typename NodesImplBase::Notifier::ImmediateDetach();

     }

     void clearNodes() {

       Parent::clear();

     }

     class NodesImpl : public NodesImplBase {

     public:

       typedef NodesImplBase Parent;

       NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset) 

 	: Parent(graph), _edgeset(edgeset) {}

       virtual ~NodesImpl() {}

       bool attached() const {

         return Parent::attached();

       }

     protected:

       virtual void erase(const Node& node) {

         try {

           _edgeset.eraseNode(node);

           Parent::erase(node);

         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {

           Parent::clear();

           throw;

         }

       }

       virtual void erase(const std::vector<Node>& nodes) {

         try {

           for (int i = 0; i < (int)nodes.size(); ++i) {

             _edgeset.eraseNode(nodes[i]);

           }

           Parent::erase(nodes);

         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {

           Parent::clear();

           throw;

         }

       }

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

     }

     bool valid() const {

       return nodes.attached();

     }

   };

 }

 #endif