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

 #ifndef __OLDGRAPH_H_

 #define __OLDGRAPH_H_

 #include <stdio.h>

 //#include <new>

 #define INVALID -1

 #define FREE_NODE INVALID

 #define EDGE_BLOCK_SIZE 100

 #define INIT_NODES_SIZE 10

 #define INIT_EDGES_BLOCK_MAX 10

 #define foreachNode(n,G) for((n)=(G).FirstNode();(n)!=INVALID;(n)=(G).NextNode(n))

 #define foreachIn(e,G,n)  for((e)=(G).FirstIn(n) ;(e);(e)=(G).NextIn(e) )

 #define foreachOut(e,G,n) for((e)=(G).FirstOut(n);(e);(e)=(G).NextOut(e))

 #define foreachEdge(e,G,n) for((e)=(G).FirstEdge(n);(e);(e)=(G).NextEdge((n),(e)))

 struct EdgeIndex { int block,index; };

 extern EdgeIndex InvalidIndex;

 class EdgeCorp;

 typedef EdgeCorp *EdgePoint;

 class EdgeCorp {

  public:

   int from,to;      //from==INVALID <=> this is a free edge.

   EdgePoint previn,nextin,prevout,nextout;

   EdgeIndex index;

   int From() { return from; }

   int To() { return to; }

   EdgePoint NextIn() { return nextin; }

   EdgePoint NextOut() { return nextout; }

 };

 inline int From(EdgePoint e) { return e->from; }

 inline int To(EdgePoint e) { return e->to; }

 inline EdgePoint NextIn(EdgePoint e) { return e->nextin; }

 inline EdgePoint NextOut(EdgePoint e) { return e->nextout; }

 //////////////////////////////////////////////////////////////////////

 //   OLDGRAPH TEMPLATE

 //////////////////////////////////////////////////////////////////////

 // Copy Constructor should be provided for N

 //class Graph;

 //class Graph::NodeIterator; //Nem megy. Disznosag!

 template <class N, class E> class OldGraph

 {

   //  friend class NEGRO::Graph::NodeIterator; //Nem megy. Disznosag!

   class nodes_t;

   friend class OldGraph::nodes_t;

   class edge_block;

   friend class OldGraph::edge_block;

   class edge_t : public EdgeCorp {

   public:

     //edge_t *previn,*nextin,*prevout,*nextout;

     union {

       int _align;

       char data[sizeof(E)];

     };

   };

   class nodes_t {

   public:

     union {

       int _align;

       char data[sizeof(N)];

     };

     int indeg,outdeg;           // indeg==FREE_NODE <=> this node is free.

     EdgePoint firstin, firstout;

     int prev,next;

     void Copy(nodes_t &n) 

     {

       indeg = n.indeg; outdeg = n.outdeg;

       firstin = n.firstin; firstout = n.firstout;

       prev = n.prev; next = n.next;

       if(n.indeg!=FREE_NODE) new(data) N(*(N*)(n.data));

       //      if(n.indeg!=FREE_NODE) {

       //	new(data) N;

       //	(*(N*)(data))=(*(N*)(n.data));

       //      }

     }

   } *nodes;

   int nodenum, nodes_size;

   int firstnode, freenodes;

   class edge_block {

   public:

     //edge_block *next;

     //    char fields[sizeof(edge_t)*EDGE_BLOCK_SIZE];

     edge_t fields[EDGE_BLOCK_SIZE];    

   } **edges;

   int edge_block_num,edge_block_max;

   EdgePoint freeedges;

   void setup(int nosi = INIT_NODES_SIZE);

   void destroy();

   void inc_nodes_size(int n);

  public:

   int NodeNum() {return nodenum;};

   int EdgeNum();

   int MaxNode() {return nodes_size;};

   int FirstNode() {return firstnode;};

   int NextNode(int n) {return nodes[n].next;};

   int PrevNode(int n) {return nodes[n].prev;};

   N& operator()(int n) {return *(N*)(nodes[n].data);};

   N& Data      (int n) {return *(N*)(nodes[n].data);};

   int AddNode();

   void AddNodeBlock(int n) {for(int i=0;i<n;i++) AddNode();}

   int AddNode(int n);

   void Delete(int n);

   int isaNode(int n) {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};

   int InDeg(int n) {return nodes[n].indeg;};

   int OutDeg(int n) {return nodes[n].outdeg;};

   EdgePoint FirstIn(int n) {return nodes[n].firstin;};

   EdgePoint FirstOut(int n) {return nodes[n].firstout;};

   E& operator()(EdgePoint e) {return *(E*)(((edge_t*)e)->data);};

   E& Data      (EdgePoint e) {return *(E*)(((edge_t*)e)->data);};

   int From(EdgePoint e) {return e->from;};

   int To(EdgePoint e) {return e->to;};

   EdgePoint NextIn(EdgePoint e)

     {return e->nextin;};

   EdgePoint NextOut(EdgePoint e)

     {return e->nextout;};

   EdgePoint AddEdge(int f, int t);

   void Delete(EdgePoint e);

   EdgePoint Edge(int f,int t);

   //  EdgePoint Edge(E &d)

   //    {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};

   E& operator()(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};

   E& Data(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};

   void Delete(int f, int t) {Delete(Edge(f,t));};

   void Reverse(EdgePoint e);

   // Functions for EdgeIndex

   EdgePoint Edge(EdgeIndex i)

     { return (EdgePoint)(edges[i.block]->fields+i.index);};

   EdgeIndex Index(EdgePoint e) { return e->index;};

   EdgeIndex Index(int f, int t) { EdgePoint e; return Edge(f,t)->index; }

   void Delete(EdgeIndex i) { Delete(Edge(i));};

   E& operator()(EdgeIndex i)

      {return *(E*)(edges[i.block]->fields[i.index].data);};

   E& Data(EdgeIndex i)

      {return *(E*)(edges[i.block]->fields[i.index].data);};

   EdgePoint AddEdge(int f, int t,EdgeIndex in);

   // Operators for symmetric graphs:

   EdgePoint FirstEdge(int n)

     { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};

   EdgePoint NextEdge(int n,EdgePoint e)

     { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };

   int Opposite(EdgePoint e,int n)

     { return From(e)+To(e)-n; };

   // Initializers, destructors

   OldGraph() {setup();};

   OldGraph(int nosi) {setup(nosi);};

   OldGraph(OldGraph<N,E> &H) {setup();operator=(H);};

   ~OldGraph() {destroy();};  

   void Clean(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};

   void Clear(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};

   void DeleteEdges();

   OldGraph<N,E> &operator=(OldGraph<N,E> &H);

 };

 //////////////////////////////////////////////////////////////////////

 // Template Definitions

 //////////////////////////////////////////////////////////////////////

 //#include <stdio.h>

 //**********************************************************************

 //                          OldGraph definitions

 //**********************************************************************

 template<class N, class E> void OldGraph<N,E>::setup(int nosi) {

   int i;

   //Set up nodes

   nodenum = 0;

   nodes_size = nosi;

   // nodes = (nodes_t*) new char[sizeof(nodes_t)*nodes_size];

   nodes = (nodes_t*) new nodes_t [nodes_size];

   for(i=0;i<nodes_size;i++)

     {

       nodes[i].prev=i-1;

       nodes[i].next=i+1;

       nodes[i].indeg=FREE_NODE;

       nodes[i].outdeg=0;

       nodes[i].firstin=nodes[i].firstout=NULL;

     }

   firstnode=nodes[0].prev=nodes[nodes_size-1].next=INVALID;

   freenodes=0;

   //Set up edge-list_template_type;

   freeedges = NULL;

   edges = new edge_block* [edge_block_max=INIT_EDGES_BLOCK_MAX];

   edge_block_num = 0;

 }

 template<class N, class E> void OldGraph<N,E>::destroy()

 {

   edge_block *oe;

   int i;

   while(firstnode!=INVALID) Delete(firstnode);

   delete [] nodes;

   for(i=0;i<edge_block_num;i++) delete edges[i];

   delete [] edges;

 }

 template<class N, class E> void OldGraph<N,E>::inc_nodes_size(int n)

 {

   int i;

   if(n<=nodenum) return;

   nodes_t *nn;

 //  nn = (nodes_t*) new char [sizeof(nodes_t)*n];

   nn = (nodes_t*) new nodes_t [n];

   for(i=0;i<nodes_size;i++)

     {

       nn[i].Copy(nodes[i]);

       if(nodes[i].indeg!=FREE_NODE) ((N*)(nodes[i].data))->~N();

     }

   delete [] nodes;

   nodes = nn;

   for(i=nodes_size;i<n;i++)

     {

       nodes[i].prev=i-1;

       nodes[i].next=i+1;

       nodes[i].indeg=FREE_NODE;

       nodes[i].outdeg=0;

       nodes[i].firstin=nodes[i].firstout=NULL;

     }

   nodes[nodes_size].prev=INVALID;

   nodes[n-1].next=freenodes;

   if(freenodes!=INVALID) nodes[freenodes].prev=n-1;

   freenodes=nodes_size;

   nodes_size=n;

 }

 template<class N, class E> OldGraph<N,E> &OldGraph<N,E>::operator=(OldGraph<N,E> &H)

 {

   Clean();

   int i;

   EdgePoint e;

   for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))

     {

       AddNode(i);

       operator()(i)=H(i);

     }

   for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))

     for(e=H.FirstOut(i);e;e=H.NextOut(e))

       operator()(AddEdge(i,H.To(e),H.Index(e)))=H(e);

    return *this;

 }

 template<class N, class E> int OldGraph<N,E>::EdgeNum()

 {

   int n=firstnode, m=0;

   EdgePoint e;

   while(n != INVALID)

   {    

     e=FirstOut(n);

     while (e != NULL)

     {

       m++;

       e=NextOut(e);

     }

     n=nodes[n].next;

   }

   return m;

 }

 template<class N, class E> int OldGraph<N,E>::AddNode()

 {

   int i;

   if(freenodes==INVALID) inc_nodes_size(2*nodes_size);

   i=freenodes;

   if(firstnode!=INVALID) nodes[firstnode].prev=i;

   freenodes=nodes[i].next;

   new(nodes[i].data) N;  //Explicit constructor call

   nodes[i].next=firstnode;

   nodes[i].prev=INVALID;

   nodes[i].indeg=0;

   firstnode=i;

   if(freenodes!=INVALID) nodes[freenodes].prev=INVALID;

   nodenum++;

   return i;

 }

 template<class N, class E> int OldGraph<N,E>::AddNode(int n)

 {

   int i;

   if(n>=nodes_size)

     {

       for(i=INIT_NODES_SIZE;i<=n;i*=2) ;

       inc_nodes_size(i);

     }

   if(nodes[n].indeg==FREE_NODE)

     {

       new(nodes[n].data) N;  //Explicit constructor call

       if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev = nodes[n].prev;

       if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next = nodes[n].next;

       else freenodes = nodes[n].next;

       nodes[n].prev = INVALID;

       if((nodes[n].next = firstnode)!=INVALID) nodes[firstnode].prev=n;

       firstnode = n;

       nodenum++;

       nodes[n].indeg=0;

     }

   return n;

 }

 template<class N, class E> void OldGraph<N,E>::Delete(int n)

 {

   if(n==INVALID||nodes[n].indeg==FREE_NODE) return;

   EdgePoint e;

   while(e=FirstIn(n)) Delete(e);

   while(e=FirstOut(n)) Delete(e);

   if(n==firstnode) firstnode=nodes[n].next;

   if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next=nodes[n].next;

   if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev=nodes[n].prev;

   if(freenodes!=INVALID) nodes[freenodes].prev=n;

   nodes[n].next=freenodes;

   nodes[n].prev=INVALID;

   nodes[n].indeg=FREE_NODE;

   ((N*)(nodes[n].data))->~N();  //Explicit destructor call

   freenodes=n;

   nodenum--;

 }

 template<class N, class E> EdgePoint OldGraph<N,E>::AddEdge(int f, int t)

 {

   int i;

   edge_block *peb;

   edge_block **ppeb;

   edge_t *e;

   if(!freeedges)

     {

       if(edge_block_num>=edge_block_max)

 	{

 	  ppeb = new edge_block* [edge_block_max*=2];

 	  for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];

 	  delete [] edges;

 	  edges = ppeb;

 	}

       peb = new edge_block;

       edges[edge_block_num] = peb;

       for(i=0;i<EDGE_BLOCK_SIZE;i++)

 	{

 	  ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);

 	  ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);

 	  ((edge_t*)peb->fields)[i].index.block = edge_block_num;

 	  ((edge_t*)peb->fields)[i].index.index = i;

 	  ((edge_t*)peb->fields)[i].from = INVALID;

 	}

       ((edge_t*)peb->fields)[0].previn=

 	((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=NULL;

       freeedges = (edge_t*)peb->fields;

       edge_block_num++;

     }

   e=(edge_t *)freeedges;

   new (e->data) E;  //Explicit constructor call

   freeedges=e->nextin;

   if(freeedges) freeedges->previn=NULL;

   e->from=f; e->to=t;

   e->previn=e->prevout=NULL;

   e->nextin=nodes[t].firstin;

   e->nextout=nodes[f].firstout;

   if(nodes[t].firstin) nodes[t].firstin->previn=e;

   if(nodes[f].firstout) nodes[f].firstout->prevout=e;

   nodes[t].firstin=nodes[f].firstout=e;

   nodes[t].indeg++; nodes[f].outdeg++;

   return (EdgePoint)e;

 }

 template<class N, class E>

 EdgePoint OldGraph<N,E>::AddEdge(int f, int t, EdgeIndex in)

 {

   int i;

   edge_block *peb;

   edge_block **ppeb;

   edge_t *e;

   while(edge_block_num<=in.block)

     {

       if(edge_block_num>=edge_block_max)

 	{

 	  ppeb = new edge_block* [edge_block_max*=2];

 	  for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];

 	  delete [] edges;

 	  edges = ppeb;

 	}

       peb = new edge_block;

       edges[edge_block_num] = peb;

       for(i=0;i<EDGE_BLOCK_SIZE;i++)

 	{

 	  ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);

 	  ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);

 	  ((edge_t*)peb->fields)[i].index.block = edge_block_num;

 	  ((edge_t*)peb->fields)[i].index.index = i;

 	  ((edge_t*)peb->fields)[i].from = INVALID;

 	}

       ((edge_t*)peb->fields)[0].previn=NULL;

       ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=freeedges;

       if(freeedges)

 	freeedges->previn = ((edge_t*)peb->fields) + (EDGE_BLOCK_SIZE-1);

       freeedges = (edge_t*)peb->fields;

       edge_block_num++;

     }

   e=((edge_t*)(edges[in.block]->fields))+in.index;

   if(e->from==INVALID)

     {

       if(e->previn) e->previn->nextin = e->nextin;

                else freeedges = e->nextin;

       if(e->nextin) e->nextin->previn = e->previn;

       new (e->data) E;  //Explicit constructor call

       e->from=f; e->to=t;

       e->previn=e->prevout=NULL;

       e->nextin=nodes[t].firstin;

       e->nextout=nodes[f].firstout;

       if(nodes[t].firstin) nodes[t].firstin->previn=e;

       if(nodes[f].firstout) nodes[f].firstout->prevout=e;

       nodes[t].firstin=nodes[f].firstout=e;

       nodes[t].indeg++; nodes[f].outdeg++;

     }

   return (EdgePoint)e;

 }

 template<class N, class E> void OldGraph<N,E>::Delete(EdgePoint e)

 {

   if(!e||e->from==INVALID) return;

   ((E*)(((edge_t*)e)->data))->~E();  //Explicit destructor call

   nodes[e->from].outdeg--; nodes[e->to].indeg--;

   if(e->previn)

     e->previn->nextin=e->nextin;

   else nodes[e->to].firstin=e->nextin;

   if(e->prevout)

     e->prevout->nextout=e->nextout;

   else nodes[e->from].firstout=e->nextout;

   if(e->nextin)

     e->nextin->previn=e->previn;

   if(e->nextout)

     e->nextout->prevout=e->prevout;

   if(freeedges) freeedges->previn=e;

   e->previn=NULL; e->nextin=freeedges;

   e->from = INVALID;

   freeedges=e;

 }

 template<class N, class E> EdgePoint OldGraph<N,E>::Edge(int f, int t)

 {

   EdgePoint e;

   for(e=nodes[f].firstout;e&&e->to!=t;e=e->nextout) ;

   return (EdgePoint) e;

 }

 template<class N, class E> void OldGraph<N,E>::Reverse(EdgePoint e)

 {

   if(!e) return;

   nodes[e->from].outdeg--; nodes[e->to].indeg--;

   if(e->previn)

     e->previn->nextin=e->nextin;

   else nodes[e->to].firstin=e->nextin;

   if(e->prevout)

     e->prevout->nextout=e->nextout;

   else nodes[e->from].firstout=e->nextout;

   if(e->nextin)

     e->nextin->previn=e->previn;

   if(e->nextout)

     e->nextout->prevout=e->prevout;

   int t,f;

   f=e->to;e->to=t=e->from;

   e->from=f;

   e->previn=e->prevout=NULL;

   e->nextin=nodes[t].firstin;

   e->nextout=nodes[f].firstout;

   if(nodes[t].firstin) nodes[t].firstin->previn=e;

   if(nodes[f].firstout) nodes[f].firstout->prevout=e;

   nodes[t].firstin=nodes[f].firstout=e;

   nodes[t].indeg++; nodes[f].outdeg++;

 }

 template<class N, class E> void OldGraph<N,E>::DeleteEdges()

 {

   int n;

   for(n=FirstNode();n!=INVALID;n=NextNode(n))

     while(FirstOut(n)) Delete(FirstOut(n));

 }

 #endif