#include<iostream>
using namespace std;
#ifndef GENERAL_GRAPH_H
#define GENERAL_GRAPH_H
/**
 * The vertex consist of a number and a capacity
 */
struct Vertex{
  int id; /**< The vertex id */
  int cap; /**< The capacity in the vertex */

  /**
   * Write a Vertex to a ostream
   * @param out the ostream 
   * @param v the vertex
   * @return the ostream
   */
  friend ostream& operator<<(ostream& out, const Vertex& v){
    out << v.id << " " << v.cap;
    return out;
  }
  
  /**
   * Read from a stream 
   * &param in the stream
   * &param v the vertex to put data in
   * @return The vertex data was writen to
   */
  friend Vertex& operator>>(istream& in, Vertex& v){
    in >> v.id ; in >> v.cap; 
    return v;
  }
  
  /**
   * Assignment operator
   * @param rhs the right hand side 
   * @return the left hand side
   */ 
  Vertex& operator=(const Vertex& rhs){
    id = rhs.id;cap=rhs.cap;return *this;
  }
  
  bool operator!=(const Vertex& v){return (v.id != id);}
  bool operator==(const Vertex& v){return (v.id==id);}
  Vertex(int id, int cap){Vertex::id=id;Vertex::cap=cap;}
  Vertex(){id = -1; cap = -1;}
};

#define V Vertex* /**< The V is a set of Vertexes */
static Vertex NIL(-1,-1);
/**
 * The edge consist of the source Vertex and the destenation Vertex
 */
struct Edge{
  int v; /**< The source Vertex */
  int w; /**< The destenation Vertex */
  double d; /**< The distance between v and w */

  /**
   * Write a Edge to a ostream
   * @param out the ostream 
   * @param e the edge 
   */
  friend ostream& operator<<(ostream& out, const Edge& e){
    out << e.v << " " << e.w << " " << e.d;
    return out;
  }
  
  /**
   * Read from a stream 
   * &param in the stream
   * &param e the edge to put data in
   * @return The edge data was writen to
   */
  friend Edge& operator>>(istream& in,Edge& e){
    in>>e.v;in >> e.w;in >> e.d;return e;
  }
  /**
   * Assignment operator
   * @param rhs the right hand side 
   * @return the left hand side
   */
  Edge& operator=(Edge& rhs){v=rhs.v;w=rhs.w;d=rhs.d;return *this;}
};


/**
 * An element in the adjancency list 
 */
struct AdjElm{
  int dst;  /**< The destenation node */
  double d; /**< The distance on the edge */
  AdjElm* next; /**< Pointer to the next element in the list */
  
  /** @name Operators */
  //@{
  /**
   * Write an adjelm to an ostream << overload 
   * @param out the ostream 
   * @param elm the element 
   */
  friend ostream& operator<<(ostream& out, const AdjElm elm){
    out << "Node " << elm.dst << " Inf " << elm.d << " " << elm.next;
    return out;
  }
  
  /**
   * Read from a stream 
   * &param in the stream
   * &param elm the element to put data in
   * @return The element data was writen to
   */
  friend AdjElm& operator>>(istream& in, AdjElm& elm){
    void* tmp;
    in >> elm.dst ;in >> elm.d;
    elm.next = (AdjElm*)tmp;
    return elm;

  }
  
  /**
   * ++ operator for the AdjElms 
   */
  friend AdjElm* operator++(AdjElm& elm){
    return (elm.next);}
  
  /**
   * Assignment operator
   * @param rhs the right hand side 
   * @return the left hand side
   */
  AdjElm& operator=(AdjElm& rhs){dst = rhs.dst;d = rhs.d;next=rhs.next;return *this;}
  //@}

  /** @name Constructors */
  //@{
  
  /**
   * Default constuctor 
   */
  AdjElm(){
    dst = -1;d = 10e30;next = 0x0;}
  
  /**
   * Copy constructor does not copy pointer to next node 
   */
  AdjElm(const AdjElm& elm){dst = elm.dst;d=elm.d;}

  /**
   * Constructor from a Edge 
   */
  AdjElm(const Edge& e){dst=e.w;d=e.d;next=0x0;}
  
  /**
   * Construtor form scatch 
   * @param w the destanation node 
   * @param d the distance  
   */
  AdjElm(int w, double d){dst=w;AdjElm::d=d;next=0x0;}
  //@}
  ~AdjElm(){}
};

/**
 * The Sparse Graph class is represented by an Adjacency_List cf. Cormen et al. 
 * It implement some simple operators to travers the edges or nodes
 * @todo Add support for multiple scan. This can be done by saving old scan vars on a stack.
 * @todo Add support for the capacity in vertexes  
 * @todo Add support for returning wieght of current edge in a scan
 */
class Sparse_Graph{
public:
  /** @name Constructors and Destructors */
  //@{
  /**
   * Create a empty graph with |V| = n 
   */
  Sparse_Graph(int n){
    _n =n;
    _adjList = new AdjElm*[n];
    for(int i=0;i<_n;i++)
      _adjList[i] = 0x0;
  }
  
  /**
   * Copy constructor 
   */
  Sparse_Graph(Sparse_Graph& G){
    _n =G.getNumNodes();
    _adjList = new AdjElm*[_n];
    for(int i=0;i<_n;i++)
      _adjList[i] = 0x0;
    for(Vertex v=G.first_node();v!=NIL;v=G.next_node()){
      for(Vertex w=G.first_adj_node(v);w!=NIL;w=G.next_adj_node()){
	addEdge(v,w,G.getd(v,w));
      }
    }
  }
  
  ~Sparse_Graph(){
    clear();
    delete[] _adjList;
  }
  //@}
  
 /** @name Get, Set and Add methods */
  //@{
  /**
   * Add a edge to the problem 
   * @param 
   */
  void addEdge(Edge& e){
    AdjElm* elm = new AdjElm(e);
    _insert(elm,e.v);
  }
  
  /**
   * Add a edge with
   * @param v as source node 
   * @param w as destenation node 
   * @param d as distance 
   */
  void addEdge(int v,int w,double d){
    AdjElm* elm = new AdjElm(w,d);
    _insert(elm,v);
  }	  
  
  void addEdge(Vertex& v, Vertex w,double d){
    AdjElm* elm = new AdjElm(w.id,d);
    _insert(elm,v.id);
  }
  /**
   * Get the number of nodes 
   */
  int getNumNodes(){return _n;}
  
  /**
   * Get distance between v w.
   * @param v source vertex 
   * @param w destanation vertex 
   * @return the distance between v and w, if no such edge 0
   */
  double getd(Vertex& v, Vertex& w){
    //Include this line to enable edge return on scan 
    return getd(v.id,w.id);

  }
  
  double getd(int v, int w){
    for(AdjElm* a=_adjList[v];a!=0x0;a = a->next)
      if(a->dst == w) return a->d;

    return 0;
  }
  /**
   * Set the distance between v and w, if no such edge exist it is made
   * @param v source node 
   * @param w destanation node 
   * @param d new distance 
   */
  void setd(Vertex& v, Vertex& w, double d){
    setd(v.id,w.id,d);
  }		  
  
  void setd(int v, int w, double d){
    for(AdjElm* a=_adjList[v];a!=0x0;a = a->next)
      if(a->dst == w){ a->d = d;return;}
    addEdge(v,w,d);
  }		  
  void deleteEdge(Vertex&v, Vertex& w){
    AdjElm *last = 0x0;

    for(AdjElm* a=_adjList[v.id];a!=0x0;a=a->next){
      if(a->dst == w.id){ 
	if(last == 0x0){_adjList[v.id] = a->next;}
	else last->next = a->next;
	delete a;	
	return;
      }
      last = a;
    }
  }
    
  //@}
  
  /**
   * Clear the current graph
   */
  void clear(){
    AdjElm *curr;
    for(int i=0;i<_n;i++){
      if(_adjList[i] == 0x0) continue;
      curr = _adjList[i];
      _adjList[i] = 0x0;
      while(curr != 0x0){AdjElm* tmp = curr;curr = curr->next;delete tmp;}

    }
  }
  
  void print(){
    AdjElm* tmp;
    for(int i=0;i<_n;i++){
      tmp = _adjList[i];
      cout << "[" << i << "]";
      while(tmp != 0x0){
	cout << "-> [ " << tmp->dst << ",d= " << tmp->d << "]";
	tmp = tmp->next;
      }
      cout << flush << endl;
    }
  }
  /** @name Scan on each node */
  //@{
  /**
   * Get the first node in the Graph
   * @return the first node in the Graph if empty 0x0
   */
  Vertex& first_node();
  
  /**
   * Get the next node returns 0x0 if none
   */
  Vertex& next_node();
  
  //@}
  
  /** @name Scan adjandant nodes */
  //@{
  
  /**
   * The function get a handle to the first node in the adjList 
   * @param v the node to scan from overwrites information in v to the new node
   * @return 0x0 if nodes adjandant else a node 
   */
  Vertex& first_adj_node(Vertex& v);
  
  /**
   * get next adjandant node 
   * @return next adjandant node if none 0x0
   */
  Vertex& next_adj_node();
    
  /**
   * @name Scan on the edges 
   */
  //@{
  
  /**
   * Get the first edge of the graph 
   * @retur the edge if it exist else 0x0
   */
  Edge& first_edge();
  
  /**
   * Get the next edge 
   * @return the next edge 0x0 if no more edges
   */
  Edge& next_edge();
  
  
 private:
  AdjElm** _adjList; /**< The adjancency list */
  int _n; /**< Number of nodes */

  inline void _insert(AdjElm* elm, int v){
    elm->next = _adjList[v];
    _adjList[v] = elm;
  }

  
  //Data for a node scan 
  Vertex _curr_node;
  AdjElm *_ns_curr, *_ns_next;
  bool node_scan;
  int _ns_pos; 
  
  //Data for the adj_node scan 
  Vertex _adj_curr_node;
  bool _adj_scan;
  int _adj_node_id;
  AdjElm* _curr_adj_elm;
  
  };
#endif