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

 #ifndef SMART_GRAPH_H

 #define SMART_GRAPH_H

 #include <iostream>

 #include <vector>

 namespace hugo {

   class SmartGraph {

     static const int INVALID=-1;

     struct NodeT 

     {

       int first_in,first_out;      

       NodeT() : first_in(INVALID), first_out(INVALID) {}

     };

     struct EdgeT 

     {

       int head, tail, next_in, next_out;      

       //FIXME: is this necessary?

       EdgeT() : next_in(INVALID), next_out(INVALID) {}  

     };

     std::vector<NodeT> nodes;

     std::vector<EdgeT> edges;

   public:

     class NodeIt;

     class EachNodeIt;

     class EdgeIt;

     class EachEdgeIt;

     class OutEdgeIt;

     class InEdgeIt;

     //      class NodeIt { int n; };

     //     class EachNodeIt : public NodeIt { };

     //     class EdgeIt { int n; };

     //     class EachEdgeIt : public EdgeIt {};

     //     class OutEdgeIt : public EdgeIt {};

     //     class InEdgeIt : public EdgeIt {};

     //    class SymEdgeIt;

     template <typename T> class NodeMap;

     template <typename T> class EdgeMap;

   public:

     /* default constructor */

     SmartGraph() : nodes(), edges() { }

     ~SmartGraph() {}

     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?

     int edgeNum() const { return edges.size(); }  //FIXME: What is this?

     NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }

     NodeIt head(EdgeIt e) const { return edges[e.n].head; }

     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }

     NodeIt aNode(const InEdgeIt& e) const { return head(e); }

     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }

     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }

     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }

     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }

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

     template< typename It >

     It first() const { 

       It e;

       getFirst(e);

       return e; 

     }

     template< typename It >

     It first(NodeIt v) const { 

       It e;

       getFirst(e, v);

       return e; 

     }

     bool valid(EdgeIt e) const { return e.n!=INVALID; }

     bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }

     bool valid(NodeIt n) const { return n.n<int(nodes.size()); }

     template <typename It> It next(It it) const

       //    { It tmp(it); return goNext(tmp); }

     { It tmp; tmp.n=it.n+1; return tmp; }

     NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }

     OutEdgeIt& goNext(OutEdgeIt& it) const

     { it.n=edges[it.n].next_out; return it; }

     InEdgeIt& goNext(InEdgeIt& it) const

     { it.n=edges[it.n].next_in; return it; }

     EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }

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

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

     NodeIt addNode() {

       NodeIt n; n.n=nodes.size();

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

       return n;

     }

     EdgeIt addEdge(NodeIt u, NodeIt v) {

       EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...

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

       edges[e.n].next_out=nodes[u.n].first_out;

       edges[e.n].next_in=nodes[v.n].first_in;

       nodes[u.n].first_out=nodes[v.n].first_in=e.n;

       return e;

     }

     void clear() {nodes.clear();edges.clear();}

     class NodeIt {

       friend class SmartGraph;

       template <typename T> friend class NodeMap;

       friend class EdgeIt;

       friend class OutEdgeIt;

       friend class InEdgeIt;

       friend class SymEdgeIt;

     protected:

       int n;

       friend int SmartGraph::id(NodeIt v) const; 

     public:

       NodeIt() {}

       NodeIt(int nn) {n=nn;}

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

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

     };

     class EachNodeIt : public NodeIt {

       friend class SmartGraph;

     public:

       EachNodeIt(const SmartGraph& G) : NodeIt(0) { }

       EachNodeIt() : NodeIt() { }

     };

     class EdgeIt {

       friend class SmartGraph;

       template <typename T> friend class EdgeMap;

       friend class NodeIt;

       friend class EachNodeIt;

     protected:

       int n;

       friend int SmartGraph::id(EdgeIt e) const;

     public:

       EdgeIt() { }

       EdgeIt(int nn) {n=nn;}

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

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

     };

     class EachEdgeIt : public EdgeIt {

       friend class SmartGraph;

     public:

       EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }

       EachEdgeIt() : EdgeIt() { }

     };

     class OutEdgeIt : public EdgeIt {

       friend class SmartGraph;

     public: 

       OutEdgeIt() : EdgeIt() { }

       OutEdgeIt(const SmartGraph& G,const NodeIt v)

 	: EdgeIt(G.nodes[v.n].first_out) {}

     };

     class InEdgeIt : public EdgeIt {

       friend class SmartGraph;

     public: 

       InEdgeIt() : EdgeIt() { }

       InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}

     };

     // Map types

     template <typename T>

     class NodeMap {

       const SmartGraph& G; 

       std::vector<T> container;

     public:

       typedef T ValueType;

       typedef NodeIt KeyType;

       NodeMap(const SmartGraph& _G) : G(_G), container(G.nodeNum()) { }

       NodeMap(const SmartGraph& _G, T a) : 

 	G(_G), container(G.nodeNum(), a) { }

       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() { container.resize(G.nodeNum()); }

       void update(T a) { container.resize(G.nodeNum(), a); }

     };

     template <typename T>

     class EdgeMap {

       const SmartGraph& G; 

       std::vector<T> container;

     public:

       typedef T ValueType;

       typedef EdgeIt KeyType;

       EdgeMap(const SmartGraph& _G) : G(_G), container(G.edgeNum()) { }

       EdgeMap(const SmartGraph& _G, T a) : 

 	G(_G), container(G.edgeNum(), a) { }

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

       T get(EdgeIt 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.edgeNum()); }

       void update(T a) { container.resize(G.edgeNum(), a); }

     };

   };

 } //namespace hugo

 #endif //SMART_GRAPH_H