// -*-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() const {return nodes_size;};

  int FirstNode() const {return firstnode;};

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

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

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

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

  int AddNode();

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

  int AddNode(int n);

  void Delete(int n);

  int isaNode(int n) const 

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

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

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

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

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

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

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

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

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

  EdgePoint NextIn(EdgePoint e) const 

    {return e->nextin;};

  EdgePoint NextOut(EdgePoint e)const 

    {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) const {return *(E*)(((edge_t*)Edge(f,t))->data);};

  E& Data(int f, int t) const {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) const 

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

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

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

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

  E& operator()(EdgeIndex i) const 

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

  E& Data(EdgeIndex i) const 

     {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) const 

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

  EdgePoint NextEdge(int n,EdgePoint e) const 

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

  int Opposite(EdgePoint e,int n) const 

    { 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()

{

  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