// -*- 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