// AListDAG.h - wdg - 2008
// Adjacency list implementation of directed graph
#include "Dag.h"
#include <cstdlib>
using namespace std;

class GNode 
{
   int neighbor;
   GNode *next;
   GNode( int nb, GNode *nx ) : neighbor(nb), next(nx) {
   }
   friend class AListDAG;
};

class AListDAG : public DAG 
{

    private:
       int N;
       GNode **outNeigh;   // used as array of pointers

    public:
    // Constructor
    AListDAG(int vertices) : N(vertices), outNeigh(new GNode *[vertices]) 
    {
       for(int i=0; i<N; i++)
          outNeigh[i]=NULL;
    }

    virtual ~AListDAG( ) 
    {
      for(int i=0; i<N; i++) 
        while( outNeigh[i] ) {
           GNode * hold = outNeigh[i]->next;
           delete outNeigh[i];
           outNeigh[i]=hold;
        }
      delete [] outNeigh;
    }

    void addEdge(int u, int v) 
    {
       outNeigh[u] = new GNode(v, outNeigh[u]);
    }

    void removeEdge(int u, int v) 
    {
       if( outNeigh[u] && v==outNeigh[u]->neighbor ) 
          outNeigh[u] = outNeigh[u]->next;
       else {
          GNode *curr = outNeigh[u];
          while ( curr->next && v!=curr->next->neighbor ) 
              curr = curr->next;
          if( curr->next && v==curr->next->neighbor ) 
               curr->next = curr->next->next;
       }
    }
        
    int numberVertices( ) const 
    {
        return N;
    }
    
    int inDegree(int v) const 
    {
        int count = 0 ;
        for(int i=0; i<N; i++)
          for( GNode *curr = outNeigh[i]; curr; curr=curr->next )
            if( v==curr->neighbor )
              count++;
        return count;
    }

    int outDegree(int v) const 
    {
        int count = 0 ;
        for( GNode *curr = outNeigh[v]; curr; curr=curr->next )
           count++;
        return count;
    }

    bool isAdjacent (int u, int v) const 
    {
          for( GNode *curr = outNeigh[u]; curr; curr=curr->next )
            if( v==curr->neighbor )
              return true;
        return false;
    }

    int numberEdges ( ) const 
    {
       int count = 0;
       for( int i=0; i<N; i++)
          count += outDegree(i);
        return count;
    }

    string toString() const 
    {
        string S;
        for(int i=0; i<N; i++) {
           S += i+'0';
           S += ": ";
           for( GNode *curr = outNeigh[i]; curr; curr=curr->next) {
               S += curr->neighbor+'0';
               S += "," ;
           }
           S+= "\n";
        }
        return S;
    }

};