// -*- mode:C++ -*-

 #ifndef J_GRAPH_H

 #define J_GRAPH_H

 #include <iostream>

 #include <vector>

 namespace hugo {

   class JGraph {

     struct NodeT 

     {

       int in, out;      

       NodeT() : in(), out() {}

     };

     struct EdgeT 

     {

       int head, tail, in, out;      

     };

     std::vector<NodeT> nodes;

     std::vector<EdgeT> edges;

     /*    template <typename Key> class DynMapBase

     {

     protected:

       SmartGraph* G; 

     public:

       virtual void add(const Key k) = NULL;

       virtual void erase(const Key k) = NULL;

       DynMapBase(SmartGraph &_G) : G(&_G) {}

       virtual ~DynMapBase() {}

       friend class SmartGraph;

       };

     template <typename T> class DynEdgeMap;

     template <typename T> class DynEdgeMap;

     */

   public:

     class TrivNodeIt;

     class TrivEdgeIt;

     class NodeIt;

     class EdgeIt;

     class OutEdgeIt;

     class InEdgeIt;

     /*  protected:

     std::vector<DynMapBase<NodeIt> * > dyn_node_maps;

     std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;

     */

     template <typename T> class NodeMap;

     template <typename T> class EdgeMap;

   public:

     JGraph() : nodes(1), edges(1) {

       edges[0].head=0; 

       edges[0].tail=0; 

       edges[0].in=0; //numEdges (numNodes is maintained in nodes[0].in)

       edges[0].out=0; 

     }    

     /*    ~SmartGraph()

     {

       for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();

 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;

       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();

 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;

 	  }*/

     int numNodes() const { return nodes[0].in; }

     int numEdges() const { return edges[0].in; } 

     TrivNodeIt tail(TrivEdgeIt e) const { return edges[e.n].tail; }

     TrivNodeIt head(TrivEdgeIt e) const { return edges[e.n].head; }

     /*    EachNodeIt& getFirst(EachNodeIt& v) const { 

       v=EachNodeIt(*this); return v; }

     EachEdgeIt& getFirst(EachEdgeIt& e) const { 

       e=EachEdgeIt(*this); return e; }

     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const { 

       e=OutEdgeIt(*this,v); return e; }

     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const { 

       e=InEdgeIt(*this,v); return e; }

     */

     NodeIt firstNode() const { 

       return NodeIt( numNodes() );

     }

     EdgeIt firstEdge() const { 

       return EdgeIt( numEdges() );

     }

     InEdgeIt firstIn(TrivNodeIt v) const { 

       return InEdgeIt(nodes[v.n].in);

     }

     OutEdgeIt firstOut(TrivNodeIt v) const { 

       return OutEdgeIt(nodes[v.n].out);

     }

     void next(NodeIt& it) const {--it.n;}

     void next(OutEdgeIt& it) const { it.n=edges[it.n].out; }

     void next(InEdgeIt& it) const { it.n=edges[it.n].in; }

     void next(EdgeIt& it) const {--it.n;}

     int id(TrivNodeIt v) const { return v.n; }

     int id(TrivEdgeIt e) const { return e.n; }

     TrivNodeIt addNode() {

       TrivNodeIt n; 

       n.n=++nodes[0].in;

       nodes.push_back(NodeT()); //FIXME

       /*      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();

 	      i!=dyn_node_maps.end(); ++i) (**i).add(n.n);*/

       return n;

     }

     TrivEdgeIt addEdge(TrivNodeIt u, TrivNodeIt v) {

       if ( u && v ) {

       TrivEdgeIt e; 

       e.n=++edges[0].in;

       edges.push_back(EdgeT()); //FIXME: Hmmm...

       edges[e.n].tail=u.n;   edges[e.n].head=v.n;

       edges[e.n].out=nodes[u.n].out;

       edges[e.n].in=nodes[v.n].in;

       nodes[u.n].out=nodes[v.n].in=e.n;

       return e;

       } 

       else return TrivEdgeIt();

 	       /*      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();

 		       i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);*/

     }

     void clear() {

       nodes.resize(1);

       edges.resize(1); edges[0].in=0;

     }

     class TrivNodeIt {

       friend class JGraph;

       template <typename T> friend class NodeMap;

       friend class TrivEdgeIt;

       friend class OutEdgeIt;

       friend class InEdgeIt;

     protected:

       int n;

     public:

       TrivNodeIt() : n() {}

       TrivNodeIt(int number) {n=number;}

       bool operator==(const TrivNodeIt i) const {return n==i.n;}

       bool operator!=(const TrivNodeIt i) const {return n!=i.n;}

       operator bool() const  { return n!=0; }

  };

     class NodeIt : public TrivNodeIt {

       friend class JGraph;

     public:

       NodeIt() : TrivNodeIt() { }

       NodeIt(int i) : TrivNodeIt(i) { }

       operator bool() const  { return n!=0; }

     };

     class TrivEdgeIt {

       friend class JGraph;

       template <typename T> friend class EdgeMap;

       friend class TrivNodeIt;

       friend class NodeIt;

     protected:

       int n;

     public:

       TrivEdgeIt() : n() { }

       TrivEdgeIt(int number) {n=number;}

       bool operator==(const TrivEdgeIt i) const {return n==i.n;}

       bool operator!=(const TrivEdgeIt i) const {return n!=i.n;}

       operator bool() const { return n!=0; }

  };

     class EdgeIt : public TrivEdgeIt {

       friend class JGraph;

     public:

       EdgeIt() : TrivEdgeIt() { }

       EdgeIt(int i) : TrivEdgeIt(i) { }

       operator bool() const { return n!=0; } 

  };

     class OutEdgeIt : public TrivEdgeIt {

       friend class JGraph;

     public: 

       OutEdgeIt() : TrivEdgeIt() { }

       OutEdgeIt(int i) : TrivEdgeIt(i) { }

     };

     class InEdgeIt : public TrivEdgeIt {

       friend class JGraph;

     public: 

       InEdgeIt() : TrivEdgeIt() { }

       InEdgeIt(int i) : TrivEdgeIt(i) { }

     };

     // Map types

     template <typename T>

     class NodeMap {

       const JGraph& G; 

       std::vector<T> container;

     public:

       NodeMap(const JGraph& _G) : G(_G), container( G.numNodes()+1  ) { }

       NodeMap(const JGraph& _G, T a) : 

 	G(_G), container(G.numNodes()+1, a) { }

       void set(TrivNodeIt n, T a) { container[n.n]=a; }

       T get(TrivNodeIt n) const { return container[n.n]; }

       /*T& operator[](NodeIt n) { return container[n.n]; }

 	const T& operator[](NodeIt n) const { return container[n.n]; }*/

       void update() { container.resize(G.numNodes()+1); }

       void update(T a) { container.resize(G.numNodes()+1, a); }

     };

     template <typename T>

     class EdgeMap {

       const JGraph& G; 

       std::vector<T> container;

     public:

       EdgeMap(const JGraph& _G) : G(_G), container(G.numEdges()+1) { }

       EdgeMap(const JGraph& _G, T a) : 

 	G(_G), container(G.numEdges()+1, a) { }

       void set(TrivEdgeIt e, T a) { container[e.n]=a; }

       T get(TrivEdgeIt e) const { return container[e.n]; }

       /*T& operator[](EdgeIt e) { return container[e.n]; } 

 	const T& operator[](EdgeIt e) const { return container[e.n]; } */

       void update() { container.resize(G.numEdges()+1); }

       void update(T a) { container.resize(G.numEdges()+1, a); }

     };

     /*template <typename T> class DynNodeMap : public DynMapBase<NodeIt>

     {

       std::vector<T> container;

     public:

       typedef T ValueType;

       typedef NodeIt KeyType;

       DynNodeMap(JGraph &_G) :

 	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())

       {

 	//FIXME: What if there are empty Id's?

 	//FIXME: Can I use 'this' in a constructor?

 	G->dyn_node_maps.push_back(this);

       }

       ~DynNodeMap()

       {

 	if(G) {

 	  std::vector<DynMapBase<NodeIt>* >::iterator i;

 	  for(i=G->dyn_node_maps.begin();

 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;

 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...

 	  //A better way to do that: (Is this really important?)

 	  if(*i==this) {

 	    *i=G->dyn_node_maps.back();

 	    G->dyn_node_maps.pop_back();

 	  }

 	}

       }

       void add(const NodeIt k) 

       {

 	if(k.n>=container.size()) container.resize(k.n+1);

       }

       void erase(const NodeIt k)

       {

 	//FIXME: Please implement me.

       }

       void set(NodeIt n, T a) { container[n.n]=a; }

       T get(NodeIt n) const { return container[n.n]; }

       T& operator[](NodeIt n) { return container[n.n]; }

       const T& operator[](NodeIt n) const { return container[n.n]; }

       void update() {}    //Useless for DynMaps

       void update(T a) {}  //Useless for DynMaps

     };

     template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>

     {

       std::vector<T> container;

     public:

       typedef T ValueType;

       typedef EdgeIt KeyType;

       DynEdgeMap(JGraph &_G) :

 	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())

       {

 	//FIXME: What if there are empty Id's?

 	//FIXME: Can I use 'this' in a constructor?

 	G->dyn_edge_maps.push_back(this);

       }

       ~DynEdgeMap()

       {

 	if(G) {

 	  std::vector<DynMapBase<EdgeIt>* >::iterator i;

 	  for(i=G->dyn_edge_maps.begin();

 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;

 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...

 	  //A better way to do that: (Is this really important?)

 	  if(*i==this) {

 	    *i=G->dyn_edge_maps.back();

 	    G->dyn_edge_maps.pop_back();

 	  }

 	}

       }

       void add(const EdgeIt k) 

       {

 	if(k.n>=int(container.size())) container.resize(k.n+1);

       }

       void erase(const EdgeIt k)

       {

 	//FIXME: Please implement me.

       }

       void set(EdgeIt n, T a) { container[n.n]=a; }

       T get(EdgeIt n) const { return container[n.n]; }

       T& operator[](EdgeIt n) { return container[n.n]; }

       const T& operator[](EdgeIt n) const { return container[n.n]; }

       void update() {}    //Useless for DynMaps

       void update(T a) {}  //Useless for DynMaps

       };*/

   };

 } //namespace hugo

 #endif //J_GRAPH_H