source: lemon-0.x/src/include/oldgraph.h @ 132:1ac27e476e25

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