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

    {

    public:

      NEGRO::EdgePoint e;

      bool isValid() { return e; }

    };

    class InEdgePoint : public EdgePoint {};

    class OutEdgePoint : public EdgePoint {};

    class BiEdgePoint : public EdgePoint {};

    class SymEdgePoint : public EdgePoint {};

    typedef int NodePoint;

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

    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 isValid() { 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() { 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 AllEdgeIterator;

      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::EdgePoint e;

    public:

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

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

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

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

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

      bool isValid() {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() { 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 AllEdgeIterator;

    };

    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(const 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 From();}

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

      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(const Graph<N,E> &Gr,const NodeIterator &nn)

      { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }

      SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); 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==From().n?To():From();}

      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 AllEdgeIterator : public EdgeIterator

    {

      NodeIterator n;  // Itt ketszer van a G

    public:

      AllEdgeIterator() {}

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

      {

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

      }  

      AllEdgeIterator &GoNext()

      {

	e=e->NextOut();

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

	return *this;

      }

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

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

      AllEdgeIterator operator++(int)

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

      NodeIterator Anode() const {return n;}

      NodeIterator Bnode() const {return n.n==From().n?To():From();}

      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(NodePoint &p)   { p=OldGraph<N,E>::FirstNode(); }

    void GetFirst(InEdgePoint &p,const NodePoint &n)

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

    void GetFirst(OutEdgePoint &p,const NodePoint &n)

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

    void GetFirst(SymEdgePoint &p,const NodePoint &n)

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

    void GetFirst(EdgePoint &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>::FirstSym(n.n); }

    void GetFirst(AllEdgeIterator &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 InEdgePoint () const

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

      operator const OutEdgePoint () const

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

      operator const SymEdgePoint () const

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

    };

    class FirstAnythingType

    {

      Graph<N,E> *G;

    public:

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

      operator const AllEdgeIterator () const

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

      operator const EdgePoint () const

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

      operator const NodeIterator () const

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

      operator const NodePoint () const

      {NodePoint 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 Set(NodeIterator i, const T &t) {map[i.Index()]=t;}

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

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

      void update() { map.resize(G->OldGraph<N,E>::NodeMax());}

      NodeMap(Graph<N,E> &Gr) : map(Gr.OldGraph<N,E>::NodeMax()) { G=&Gr ;}

    };

    template<class T> class EdgeMap

    {

      Graph<N,E> *G;

      vector<T> map;

    public:

      typedef T value_type;

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

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

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

      void update()

	{ map.resize(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE);}

      EdgeMap(Graph<N,E> &Gr) 

	:map(Gr.OldGraph<N,E>::edge_block_num*EDGE_BLOCK_SIZE)

	{ G=&Gr ;}

    };

  };

  /*   Ez itt a fiam kommentje:

       <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv

       vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz

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

       mcmn   

  */

}

#endif