// -*-mode: c++; -*-

#ifndef __GRAPH_H_

#define __GRAPH_H_

//inline void *operator new(size_t s, void *p) { return p; }

#include <new>

#include <vector>

namespace NEGRO 

{

  using namespace std;

#include "oldgraph.h"

  template <class N, class E> class Graph : protected OldGraph<N,E>

  {

  public:

    typedef E EdgeType;

    typedef N NodeType;

    class EdgeIt

    {

    public:

      NEGRO::EdgePoint e;

      bool valid() { return e; }

    };

    class InEdgeIt : public EdgeIt {};

    class OutEdgeIt : public EdgeIt {};

    class BiEdgeIt : public EdgeIt {};

    class SymEdgeIt : public EdgeIt {};

    typedef int NodeIt;

    typedef NodeIt EachNodeIt;

    class NodeIterator;

    class EdgeIterator;

    class InEdgeIterator;

    class OutEdgeIterator;

    class BiEdgeIterator;

    class SymEdgeIterator;

    class AllEdgeIterator;

    class FirstAnythingTypeNode; //Required by the unified First() function.

    friend class NodeIterator;

    friend class EdgeIterator;

    friend class InEdgeIterator;

    friend class OutEdgeIterator;

    friend class BiEdgeIterator;

    friend class SymEdgeIterator;

    friend class EachEdgeIterator;

    class NodeIterator

    {

      Graph<N,E> *G;  //operator*() miatt kell!!!

      int n;     //nem kellene, ha itt mutato lenne!!

    public:    

      NodeIterator() {;} 

      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.

      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();} 

      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}

      NodeIterator &goNext() { n=G->NextNode(n); return *this;}

      NodeIterator next() const { return NodeIterator(*this).goNext();}

      NodeIterator &operator++() { return goNext();} 

      NodeIterator operator++(int)

      {NodeIterator tmp(*this); goNext(); return tmp;}

      bool valid() { return n!=INVALID; }

      N &operator*() const { return G->Data(n); }

      N *operator->() const { return &G->Data(n); }

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

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

      int index() const { return n; } //If the nodes are indexable 

      friend class Graph;

      friend class EdgeIterator;

      friend class InEdgeIterator;

      friend class OutEdgeIterator;

      friend class BiEdgeIterator;

      friend class SymEdgeIterator;

      friend class EachEdgeIterator;

      friend class FirstAnythingTypeNode;

      //Nem kellene egy:

      //      static NodeIterator &GetInvalid();  ?

    };

    class EdgeIterator

    {

      Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!

      //Ez csak kicsit baj, de:

      // Meg a From() es To() miatt!!!!!!!!!!

      NEGRO::EdgeIt e;

    public:

      EdgeIterator() {;} //Kell inicializalni? (Nem)

      EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}

      // Lehet, hogy ez a ketto nem kell!!!

      NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}

      NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}

      NodeIterator opposite(const NodeIterator &n) const

      {return n==tail()?head():tail();}

      bool valid() {return e;}

      E &operator*() const { return G->Data(e); }

      E *operator->() const { return &G->Data(e); }

      //operator const OutEdgeIterator ();

      //operator const InEdgeIterator ();

      //operator const BiEdgeIterator ();

      //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal

      bool operator==(const EdgeIterator &i) const {return e==i.e;}

      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}

      int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}

      //If the edges are indexable 

      friend class Graph;

      friend class InEdgeIterator;

      friend class OutEdgeIterator;

      friend class BiEdgeIterator;

      friend class SymEdgeIterator;

      friend class EachEdgeIterator;

    };

    class BiEdgeIterator : public EdgeIterator

    {

    public:

      BiEdgeIterator &goNextIn()  { e=e->NextIn(); return *this;}

      BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}

      BiEdgeIterator nextIn() const  {return BiEdgeIterator(*this).goNextIn();}

      BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}

      operator InEdgeIterator ()

      {InEdgeIterator i; i.G=G;i.e=e;return i;}

      operator OutEdgeIterator ()

      {OutEdgeIterator i; i.G=G;i.e=e;return i;}

      //operator const SymEdgeIterator ()

      friend class Graph;

    };

    class InEdgeIterator : public EdgeIterator

    //Ne a BiEdgeIterator-bol szarmazzon?

    {

    public:

      InEdgeIterator() {}

      InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)

      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}

      InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}

      InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}

      InEdgeIterator &operator++() { return GoNext();}

      InEdgeIterator operator++(int)

      {InEdgeIterator tmp(*this); GoNext(); return tmp;}

      operator const OutEdgeIterator ()

      {OutEdgeIterator i; i.G=G;i.e=e;return i;}

      operator const BiEdgeIterator ()

      {EdgeIterator i; i.G=G;i.e=e;return i;}

      //      operator const SymEdgeIterator ();

      NodeIterator Anode() const {return To();}

      NodeIterator Bnode() const {return From();}

      friend class Graph;

    };

    class OutEdgeIterator : public EdgeIterator

    {

    public:

      OutEdgeIterator() {}

      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)

      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}

      OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}

      OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}

      OutEdgeIterator &operator++() { return goNext();}

      OutEdgeIterator operator++(int)

      {OutEdgeIterator tmp(*this); goNext(); return tmp;}

      NodeIterator aNode() const {return tail();}

      NodeIterator bNode() const {return head();}

      operator const InEdgeIterator ()

      {InEdgeIterator i; i.G=G;i.e=e;return i;}

      operator const BiEdgeIterator ()

      {BiEdgeIterator i; i.G=G;i.e=e;return i;}

      //operator const SymEdgeIterator(); 

      friend class Graph;

    };

    class SymEdgeIterator : public EdgeIterator

    {

      NodeIterator n;  // Itt ketszer van a G

    public:

      SymEdgeIterator() {}

      SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)

      { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }

      SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}

      SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}

      SymEdgeIterator &operator++() { return goNext();}

      SymEdgeIterator operator++(int)

      {SymEdgeIterator tmp(*this); goNext(); return tmp;}

      NodeIterator aNode() const {return n;}

      NodeIterator bNode() const {return n.n==tail().n?head():tail();}

      operator const InEdgeIterator ()

      {InEdgeIterator i; i.G=G;i.e=e;return i;}

      operator const OutEdgeIterator ()

      {OutEdgeIterator i; i.G=G;i.e=e;return i;}

      operator const BiEdgeIterator ()

      {BiEdgeIterator i; i.G=G;i.e=e;return i;}

      friend class Graph;

    };

    class EachEdgeIterator : public EdgeIterator

    {

      NodeIterator n;  // Itt ketszer van a G

    public:

      EachEdgeIterator() {}

      EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)

      {

	e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;

      }  

      EachEdgeIterator &goNext()

      {

	e=e->NextOut();

	if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);

	return *this;

      }

      EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}

      EachEdgeIterator &operator++() { return goNext();}

      EachEdgeIterator operator++(int)

	{EachEdgeIterator tmp(*this); goNext(); return tmp;}

      NodeIterator aNode() const {return n;}

      NodeIterator bNode() const {return n.n==tail().n?head():tail();}

      operator const EdgeIterator ()

      {EdgeIterator i; i.G=G;i.e=e;return i;}

      operator const InEdgeIterator ()

      {InEdgeIterator i; i.G=G;i.e=e;return i;}

      operator const OutEdgeIterator ()

      {OutEdgeIterator i; i.G=G;i.e=e;return i;}

      operator const BiEdgeIterator ()

      {BiEdgeIterator i; i.G=G;i.e=e;return i;}

      friend class Graph;

    };

    typedef NodeIterator DeletingNodeIterator;

    typedef EdgeIterator DeletingEdgeIterator;

    typedef BiEdgeIterator DeletingBiEdgeIterator;

    typedef OutEdgeIterator DeletingOutEdgeIterator;

    typedef InEdgeIterator DeletingInEdgeIterator;

    typedef SymEdgeIterator DeletingSymEdgeIterator;

    const NodeIterator firstNode()

    {

      NodeIterator i;

      i.G=this;i.n=OldGraph<N,E>::FirstNode();

      return i;

    }

    void getFirst(NodeIt &p)   { p=OldGraph<N,E>::FirstNode(); }

    void getFirst(InEdgeIt &p,const NodeIt &n)

    { p=OldGraph<N,E>::FirstIn(n); }

    void getFirst(OutEdgeIt &p,const NodeIt &n)

    { p=OldGraph<N,E>::FirstOut(n); }

    void getFirst(SymEdgeIt &p,const NodeIt &n)

    { p=OldGraph<N,E>::FirstEdge(n); }

    void getFirst(EdgeIt &p) //Vegigmegy mindenen

    { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}

    void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}

    void getFirst(InEdgeIterator &i,const NodeIterator &n)

    { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }

    void getFirst(OutEdgeIterator &i,const NodeIterator &n)

    { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }

    void getFirst(SymEdgeIterator &i,const NodeIterator &n)

    { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }

    void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen

    {

      i.G=this;

      getFirst(i.n);

      i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;

    }  

    //Vagy beginnode()?

    const DeletingEdgeIterator firstOut(const NodeIterator &n)

    {

      EdgeIterator i;

      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);

      return i;

    }

    const DeletingEdgeIterator firstIn(const NodeIterator &n)

    {

      EdgeIterator i;

      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);

      return i;

    }

    const DeletingSymEdgeIterator firstSym(const NodeIterator &n)

    {

      EdgeIterator i;

      i.G=n.G;i.n=n.n;

      i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);

      return i;

    }

    //    class FirstAnythingType;

    //    friend class FirstAnythingType;

    class FirstAnythingTypeNode

    {

      NodeIterator n;

    public:

      FirstAnythingTypeNode(NodeIterator i) : n(i) {}

      operator const InEdgeIterator () const

      {InEdgeIterator i; n.G->GetFirst(i,n);return i;}

      operator const OutEdgeIterator () const

      {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}

      operator const SymEdgeIterator () const

      {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}

      operator const InEdgeIt () const

      {InEdgeIt i; n.G->GetFirst(i,n);return i;}

      operator const OutEdgeIt () const

      {OutEdgeIt i; n.G->GetFirst(i,n);return i;}

      operator const SymEdgeIt () const

      {SymEdgeIt i; n.G->GetFirst(i,n);return i;}

    };

    class FirstAnythingType

    {

      Graph<N,E> *G;

    public:

      FirstAnythingType(Graph<N,E> *gg) : G(gg) {}

      operator const EachEdgeIterator () const

      {EachEdgeIterator i; G->GetFirst(i);return i;}  

      operator const EdgeIt () const

      {EdgeIt i; G->GetFirst(i);return i;}

      operator const NodeIterator () const

      {NodeIterator i; G->GetFirst(i);return i;}  

      operator const NodeIt () const

      {NodeIt i; G->GetFirst(i);return i;}

    } _FST;

    //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}

    FirstAnythingTypeNode first(NodeIterator &i)

    {FirstAnythingTypeNode t(i); return t;}

    const FirstAnythingType &first() {return _FST;}

    // LastNode() vagy endnode() stb. Nem kell?

    DeletingNodeIterator addNode()

    {

      DeletingNodeIterator i;

      i.G=this; i.n=OldGraph<N,E>::AddNode();

      return i;

    }

    DeletingEdgeIterator

    addEdge(const NodeIterator from,const NodeIterator to)

    {

      DeletingEdgeIterator i;

      i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;

    }

    void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}

    void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}

    int nodeNum() { OldGraph<N,E>::NodeNum(); }

    void clean() { OldGraph<N,E>::Clean(); }

    Graph() : _FST(this) {}

    // MAPS:

    template<class T> class NodeMap

    {

      Graph<N,E> *G;

      vector<T> map;

    public:

      typedef T value_type;

      void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}

      T get(const NodeIterator i) const {return map[i.Index()];}

      T operator[](NodeIterator i) {return map[i.Index()];}

      void update() { map.resize(G->MaxNode());}

      NodeMap() {}

      void setG(Graph<N,E> &Gr) { G=&Gr; update();}      

    };

    template<class T> class EdgeMap

    {

      Graph<N,E> *G;

      vector<T> map;

    public:

      typedef T value_type;

      void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}

      T get(const EdgeIterator i) const {return map[i.Index()];}

      T &operator[](EdgeIterator i) {return map[i.Index()];}

      void update()

	{ map.resize(G->MaxEdge());}

      EdgeMap() {}

      void setG(Graph<N,E> &Gr) 

      { G=&Gr ;update();}

    };

    int maxNode() { return OldGraph<N,E>::MaxNode();}

    int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}

  };

  template <class G> //G is a graph-type

  class Path

  {

  public:

    typedef G Graph;

    typedef typename G::NodeIterator NodeIterator;

    typedef typename G::EdgeIterator EdgeIterator;

    typedef typename G::SymEdgeIterator SymEdgeIterator;

  private:

    std::vector<EdgeIterator> path;

    std::vector<bool> reversed;

  public:

    void setLength(int n) { path.resize(n);reversed.resize(n);}

    int getLength() { return path.size(); }

    EdgeIterator &operator[](int n) {return path[n];}

    NodeIterator GetNode(int n) // What about path of length 1?

    {

      return n?

	reversed[n-1]?path[n-1].tail():path[n-1].head():

	reversed[0]?path[0].head():path[0].tail();

    }

    void setRevert(int n,bool r=true) {reversed[n]=r;}

    void setEdge(int n,SymEdgeIterator i)

    {

      path[n]=i;

      reversed[n] = i.head()==i.aNode();

    }

    void setEdge(int n,EdgeIterator i,bool r)

    {

      path[n]=i;

      reversed[n] = r;

    }

    NodeIterator tail() { return getNode(0); }

    NodeIterator head() { return getNode(getLength()); }

  };

  /*   Ez itt a fiam kommentje:

       <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv

       vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz

       <<  < < <  < <  <   .cx..x.c.cc.c          

       mcmn   

  */

};

#endif