/*******************************************************
*
*  DESCRIPTION: class Graph 
*
*  AUTHOR: Mariana C. D'Abreu 
*
*  EMAIL: mdabreu@dc.uba.ar
*
********************************************************/

#ifndef _GRAPH_H
#define _GRAPH_H

#include <string>
#include <list>

using namespace std;
 

//******************************************************
//
// Class Graph 
//
// Description: clase para grafos no dirigidos
//
//******************************************************

template<class NData, typename EData = int>
class Graph 
{
  public:

    class Node;
    class Edge;
    class Iterator;

    typedef typename Graph<NData,EData>::Node* PNode;
    typedef typename Graph<NData,EData>::Edge* PEdge;

    friend class Iterator;

  private:

    bool 	_delAdjacency( PNode );
    bool 	_delEdge( PNode, PNode );
    bool 	_delNode( PNode );
    bool 	_addEdge( PNode, PNode, const EData & );
    bool 	_moveAdjacency( PNode, PNode );
    bool 	_isAdjacent( PNode, PNode ) const;
    PEdge 	_getEdge( PNode, PNode ) const;

    typedef typename list<PNode>::iterator 		list_nodes_iter;
    typedef typename list<PEdge>::iterator 		list_edges_iter;
    typedef typename list<PNode>::const_iterator 	list_nodes_const_iter;
    typedef typename list<PEdge>::const_iterator 	list_edges_const_iter;

    list<PNode>	nodes;	// lista de nodos
    int	   	numNodes;

  public:

    Graph();
    ~Graph();

    bool addNode( const NData & );
    bool addNode( Node * );
    bool addNode( const Node & );
    bool addEdge( const Node &, const Node &, const EData & = 0 );
    bool addEdge( const NData &, const NData &, const EData & = 0 );

    bool delNode( const Node & ); 
    bool delNode( const NData & ); 
    bool delEdge( const Node &, const Node & );
    bool delEdge( const NData &, const NData & );

    Iterator& eraseNode( Iterator & );

    Iterator& moveAdjacency ( Iterator &, const Node & );
    Iterator& moveAdjacency ( Iterator &, const NData & );
    bool      moveAdjacency ( const NData &, const NData & );
    bool      eraseAdjacency( const NData & );
    bool      eraseAllEdges ( const Node & );
    bool      eraseAllEdges ( const NData & );

    Iterator& begin() { Iterator *it = new Iterator(nodes.begin()); return *it; }
    Iterator& end()   { Iterator *it = new Iterator(nodes.end()); return *it; }

    bool isNode( const Node & );
    bool isNode( const NData & );
    bool isAdjacent( const Node &, const Node & ) const;
    bool isAdjacent( const NData &, const NData & ) const;

    int	 numberOfNodes() const 
		{ return numNodes; }

    int  degree( const NData &data ) const; 

    PNode getNode( const Node & ) const;
    PNode getNode( const NData & ) const;
    PEdge getEdge( const Node &, const Node & ) const;
    PEdge getEdge( const NData &, const NData & ) const;

    list<PNode>* adjacents( const NData & ) const;
    list<PNode>* adjacents( const Node & ) const;
    list<NData>* adjacentsValue( const NData & ) const;

    void setMarkAllNodes( const bool mark = true );
    
    Graph<NData,EData> & operator = ( const Graph<NData,EData> & );
 
    //ostream& operator << ( ostream &out );  
    void print( ostream &, bool printEdge = true ) const;


    //******************************************************
    //
    // Class Iterador
    //
    // Description: iterador de nodos del grafo
    //
    //******************************************************

    class Iterator {

      public:

        friend class Graph;
    
        Iterator()
		:it() {};

        Iterator( Graph<NData, EData> &graph )
                :it( graph.nodes.begin() ) {}

        ~Iterator() {};

	PNode&    operator *() const  	
		{ return it.operator*(); }

        Iterator& operator++()   	
		{ it.operator++(); return *this; }

        Iterator& operator++(int i) 	
		{ it.operator++(i); return *this; }

        Iterator& operator--()   	
		{ it.operator--(); return *this; }

        Iterator& operator--(int i) 	
		{ it.operator--(i); return *this; }

        bool	  operator==( const Iterator &iter ) const 
		{ return iter.it == this->it; }  

        bool	  operator!=( const Iterator &iter ) const 
		{ return iter.it != this->it; }  
       
      private:

        Iterator( const list_nodes_iter &iter )
		:it( iter ) {};

	list_nodes_iter it;
    };

    //******************************************************
    //
    // Class Node
    // 
    // Description: clase para los nodos del grafo
    //
    //******************************************************

    class Node {

      public:

        Node( const NData & );
        Node( const Node & );
     	~Node();

     	NData& getValue() 
		{ return value; }

	//ostream& operator << ( ostream &out ) const { out << value; return out; }

	void print ( ostream &out ) const 
		{ out << value; }

     	bool  marked() const { return mark; }

     	Node& setMark( const bool mark = true )
		{ this->mark = mark; return *this; }

     	bool  operator == ( const Node &node ) const 
		{ return ( value == node.value ); }

     	bool  operator != ( const Node &node ) const
		{ return ( value != node.value ); }

      private:

     	Node&   operator = ( const Node & );
        bool 	delAdjacency();
        PEdge	getEdge( const Node & );

      	friend class Graph<NData,EData>;

      	NData           value;
      	list<PEdge>     adjs;
      	bool            mark;

    };


    //******************************************************
    //
    // Class Edge
    //
    // Description: clase para los ejes del grafo
    //
    //******************************************************

    class Edge {

      public:

        Edge( Node &, Node &, const EData & );
        Edge( const Edge & );
        ~Edge();

        EData& getData() 
		{ return value; }

        bool marked() const 
		{ return mark; }

        Edge& setMark( const bool mark = true )
		{ this->mark = mark; return *this; }

      private:

	Node*	getEnd( const Node * );

        friend class Graph<NData,EData>;
	friend class Node;

        EData   	value;
        PNode    	n1;
        PNode    	n2;
        bool    	mark;
    };
};


//******************************************************
//
// Class Graph
//
//******************************************************

template<class NData, typename EData>
Graph<NData,EData>::Graph()
{
}

template<class NData, typename EData>
Graph<NData,EData>::~Graph()
{
  list_nodes_iter it = nodes.begin();
  for( ; it != nodes.end(); it++ ) {
    if( *it != NULL ) {
      delete ( *it );
    }
  }
  nodes.clear();
}

template<class NData, typename EData>
bool Graph<NData,EData>::addNode( const NData &data )
{
  Node *node = new Node( data );
  assert( node );
  if( !isNode( *node ) ) { 
    nodes.push_back( node );
    return true;
  }
  return false;
}

template<class NData, typename EData>
bool Graph<NData,EData>::addNode( Node * node )
{
  assert( node );
  if( !isNode( *node ) ) {
    nodes.push_back( node );
    return true;
  }
  return false;
}

template<class NData, typename EData>
bool Graph<NData,EData>::addNode( const Node &node )
{
  Node *nnode  = new Node( node );
  return ( this->addNode( nnode ) );
}

template<class NData, typename EData>
bool Graph<NData,EData>::addEdge( const Node &node1, const Node &node2, const EData &data )
{
  return ( addEdge( node1.value, node2.value, data ) ); 
}

template<class NData, typename EData>
bool Graph<NData,EData>::addEdge( const NData &n1, const NData &n2, const EData &data )
{
  PNode node1, node2;

  node1 = this->getNode( n1 );
  node2 = this->getNode( n2 );
 
  if( node1 == NULL || node2 == NULL ) 
    return false;

  return ( _addEdge( node1, node2, data ) ); 
}

template<class NData, typename EData>
bool Graph<NData,EData>::delNode( const Node &node ) 
{
  return ( delNode( node.value ) );
}

template<class NData, typename EData>
bool Graph<NData,EData>::delNode( const NData &val ) 
{
  PNode node = getNode( val ); 

  if( node == NULL ) {
    return false;
  }
  _delNode( node );

  return true;
}

template<class NData, typename EData>
bool Graph<NData,EData>::delEdge( const Node &n1, const Node &n2 )
{
  return ( delEdge( n1.value, n2.value ) );
}

template<class NData, typename EData>
bool Graph<NData,EData>::delEdge( const NData &v1, const NData &v2 )
{
  PNode node1, node2;

  node1 = this->getNode( v1 );
  node2 = this->getNode( v2 );
 
  return ( _delEdge( node1, node2 ) );
}

template<class NData, typename EData>
Graph<NData,EData>::Iterator& Graph<NData,EData>::eraseNode( Iterator &position )
{
  Node *node;

  if( _delAdjacency( *position.it ) ) {
    node = *(position.it); 
    nodes.erase( position.it );
    position.it--;
    if( node != NULL ) delete node;
  }
  return position;  
}

template<class NData, typename EData>
Graph<NData,EData>::Iterator& Graph<NData,EData>::moveAdjacency ( Iterator &position, const Node &node )
{
  return ( moveAdjacency( position, node.value ) );
}

template<class NData, typename EData>
Graph<NData,EData>::Iterator& Graph<NData,EData>::moveAdjacency ( Iterator &position, const NData &val )
{
  PNode node = *position;
  PNode node1 = getNode( val );

  _moveAdjacency( node, node1 );

  return position;
}

template<class NData, typename EData>
bool Graph<NData,EData>::moveAdjacency ( const NData &val1, const NData &val2 )
{
  PNode node1 = getNode( val1 );
  PNode node2 = getNode( val2 );

  return ( _moveAdjacency( node1, node2 ) );
}

template<class NData, typename EData>
bool Graph<NData,EData>::eraseAdjacency ( const NData &val )
{
   Node *node = getNode( val );
   list<NData> *adjs;
 
   if( node == NULL ) 
     return true;

   adjs = adjacentsValue( val );
   
   if( adjs == NULL ) return false;

   list<NData>::const_iterator it = adjs->begin();

   for( ; it != adjs->end(); it++ ) {
     if( *it != node->getValue() ) {
       this->delNode( *it );
     }
   }
   return true;
}

template<class NData, typename EData>
bool Graph<NData,EData>::eraseAllEdges ( const Node &node )
{
  return ( eraseAllEdges( node.value ) );
}

template<class NData, typename EData>
bool Graph<NData,EData>::eraseAllEdges ( const NData &val )
{
  Node *node = getNode( val );
 
  if( node == NULL ) return false;

  return ( _delAdjacency( node ) );
}

template<class NData, typename EData>
bool Graph<NData,EData>::_delEdge( PNode node1, PNode node2 )
{
  if( node1 == NULL || node2 == NULL ) 
    return false;
  
  Edge *edge = node1->getEdge( *node2 ); 

  assert( edge );

  node1->adjs.remove( edge );
  node2->adjs.remove( edge );

  if( edge ) delete edge;
  
  return true;
}

template<class NData, typename EData>
bool Graph<NData,EData>::_delNode( PNode node )
{
  if( node == NULL ) {
    return false;
  }
  if( _delAdjacency( node ) ) {
    nodes.remove( node );
    return true;
  }
  return false;
}

template<class NData, typename EData>
bool Graph<NData,EData>::_delAdjacency( PNode node1 )
{
  if( node1 == NULL )
    return false;
  
  return ( node1->delAdjacency() );
}

template<class NData, typename EData>
bool Graph<NData,EData>::_addEdge( PNode node1, PNode node2, const EData &data )
{
  if( node1 == NULL || node2 == NULL ) 
    return false;
 
  if( _isAdjacent( node1, node2 ) )
    return true;

  Edge *edge = new Edge( *node1, *node2, data );
  assert( edge );
  node1->adjs.push_back( edge );  
  if( node1 != node2 ) {
    node2->adjs.push_back( edge );  
  }
  return true; 
}

template<class NData, typename EData>
bool Graph<NData,EData>::_moveAdjacency ( PNode node1, PNode node2 )
{
  PEdge edge;

  if( node1 == NULL || node2 == NULL ) return false;

  if( node1 == node2 ) return true;

  list_edges_const_iter it = node1->adjs.begin();

  for( ; it != node1->adjs.end(); it++ ) {
    edge = *it;
    assert( edge );
    if ( node2 != edge->getEnd( node1 ) ) {
      this->_addEdge( node2, edge->getEnd( node1 ), edge->getData() );
    }
  }
  return ( _delAdjacency( node1 ) );
}

template<class NData, typename EData>
bool Graph<NData,EData>::_isAdjacent( PNode node1, PNode node2 ) const 
{
  if( node1 == NULL || node2 == NULL ) 
    return false;
 
  list_edges_const_iter it = node1->adjs.begin();

  for( ; it != node1->adjs.end(); it++ ) {
    if( (*it)->getEnd( node1 ) == node2 ) 
      return true;
  }
  return false;
}


template<class NData, typename EData>
Graph<NData,EData>::PEdge Graph<NData,EData>::_getEdge( PNode node1, PNode node2 ) const 
{
  if( node1 == NULL || node2 == NULL ) 
    return false;

  return ( node1->getEdge( *node2 ) ); 
}

template<class NData, typename EData>
bool Graph<NData,EData>::isNode( const Node &node ) 
{
  return ( isNode( node.value ) );  
}

template<class NData, typename EData>
bool Graph<NData,EData>::isNode( const NData &value ) 
{
  return ( getNode(value) != NULL );  
}

template<class NData, typename EData>
bool Graph<NData,EData>::isAdjacent( const Node &n1, const Node &n2 ) const 
{
  return ( isAdjacent( n1.value, n2.value ) );
}

template<class NData, typename EData>
int Graph<NData,EData>::degree( const NData &value ) const 
{ 
  PNode node = getNode( value ); 
  assert( node ); 
  return node->adjs.size(); 
}

template<class NData, typename EData>
bool Graph<NData,EData>::isAdjacent( const NData &v1, const NData &v2 ) const 
{
  PNode node1, node2;

  node1 = this->getNode( v1 );
  node2 = this->getNode( v2 );
 
  return ( _isAdjacent( node1, node2 ) );
}

template<class NData, typename EData>
list<Graph<NData,EData>::PNode>* Graph<NData,EData>::adjacents( const NData &data ) const
{
  Node *node = this->getNode( data );

  return ( adjacents( *node ) );
}

template<class NData, typename EData>
list<Graph<NData,EData>::PNode>* Graph<NData,EData>::adjacents( const Node &node1 ) const
{
  list<PNode> *nlist = new list<PNode>;

  list_edges_const_iter it = node1.adjs.begin();

  for( ; it != node1.adjs.end(); it++ ) {
    Node *node = (*it)->getEnd( &node1 );
    assert( node );
    nlist->push_back( node );
  }
  return nlist;
}

template<class NData, typename EData>
list<NData>* Graph<NData,EData>::adjacentsValue( const NData &val ) const
{
  list<NData> *nlist = new list<NData>;

  Node *node = this->getNode( val );

  if( node == NULL ) return nlist;

  list_edges_const_iter it = node->adjs.begin();

  for( ; it != node->adjs.end(); it++ ) {
    Node *adj  = (*it)->getEnd( node );
    assert( adj );
    nlist->push_back( adj->getValue() );
  }
  return nlist;
}

template<class NData, typename EData>
void Graph<NData,EData>::setMarkAllNodes( const bool mark )
{
  list_nodes_iter it = nodes.begin();

  for( ; it != nodes.end(); it++ ) {
    (*it)->setMark( mark );  
  }
}

template<class NData, typename EData>
Graph<NData,EData> &Graph<NData,EData>::operator = ( const Graph<NData,EData> &graph )  
{
  list<PNode> *list;

  list_nodes_const_iter it = graph.nodes.begin();
  list_nodes_const_iter iter;

  for( ; it != graph.nodes.end(); it++ ) {
    this->addNode( (*it)->getValue() );  
  }

  for( it = graph.nodes.begin(); it != graph.nodes.end(); it++ ) {
    list = adjacents( *(*it) );
    if( list ) {
      for( iter = list->begin(); iter != list->end(); iter++ ) {
        addEdge( (*it)->getValue(), (*iter)->getValue() );
      }  
    }    
  }
  return *this;
}

template<class NData, typename EData>
Graph<NData,EData>::PNode Graph<NData,EData>::getNode( const Node &node ) const 
{
  return ( getNode( node.value ) );
}

template<class NData, typename EData>
Graph<NData,EData>::PNode Graph<NData,EData>::getNode( const NData &value ) const 
{
  list_nodes_const_iter iter = nodes.begin();
  for( ; iter != nodes.end() && (*iter)->value != value ; iter++ );
  
  if( iter != nodes.end() ) 
    return *iter;

  return NULL;
}

template<class NData, typename EData>
Graph<NData,EData>::PEdge Graph<NData,EData>::getEdge( const Node &n1, const Node &n2 ) const
{
  return ( getEdge( n1.value, n2.value ) );
}

template<class NData, typename EData>
Graph<NData,EData>::PEdge Graph<NData,EData>::getEdge( const NData &v1, const NData &v2 ) const
{
  PNode node1, node2;

  node1 = getNode( v1 );
  node2 = getNode( v2 );

  return ( _getEdge( node1, node2 ) ); 
}

template<class NData, typename EData>
void Graph<NData,EData>::print( ostream &out, bool printEdge ) const
{
  PNode node, nodeadj;
  list<PNode> *adjs;
  list<PNode>::iterator itadjs;
  string sep;
  PEdge edge;

  list_nodes_const_iter it = nodes.begin();
  
  for( ; it != nodes.end(); it++ ) {
    node = *it;
    assert( node );
    out << "\nNodo: ";
    node->print( out ); 
    out << "\nAdyacentes: ";
    
    adjs = adjacents( *node );
    itadjs = adjs->begin();
    sep = "";

    for ( ; itadjs != adjs->end(); itadjs++ ) {
      nodeadj = *itadjs;
      assert( nodeadj );
      edge = _getEdge( node, nodeadj );
      if( printEdge ) {
        out << sep << nodeadj->getValue() << " {" << _getEdge( node, nodeadj )->getData() << "} ";
      }
      else {
        out << sep << nodeadj->getValue();
      }
      sep = ",";
    }
  }
}


//******************************************************
//
// Class Node
//
//******************************************************

template<class NData, typename EData>
Graph<NData,EData>::Node::Node( const NData &data )
{
  value = data;
  mark = false;
}

template<class NData, typename EData>
Graph<NData,EData>::Node::Node( const Node &node )
{
  value = node.value;
  adjs = node.adjs;
  mark = node.mark;
}

template<class NData, typename EData>
Graph<NData,EData>::Node::~Node()
{
  delAdjacency();
}

template<class NData, typename EData>
bool Graph<NData,EData>::Node::delAdjacency()
{
  list_edges_iter it = adjs.begin();
  for( ; it != adjs.end(); it++ ) {
    Edge *edge = *it;
    Node *node;
    if( edge != NULL ) {
      // borro el eje de los dos nodos adyacentes
      node = edge->getEnd( this );
      if( node != this ) {
        node->adjs.remove( edge );
      }
      delete ( *it );
    }
  }
  adjs.clear();
  return true;
}

template<class NData, typename EData>
Graph<NData,EData>::Node& Graph<NData,EData>::Node::operator = ( const Node & node ) 
{
  value = node.value;
  adjs = node.adjs;
  mark = node.mark;
  return *this;
}

template<class NData, typename EData>
Graph<NData,EData>::PEdge Graph<NData,EData>::Node::getEdge( const Node &node2 )
{
  list_edges_iter it = adjs.begin();
  for( ; it != adjs.end(); it++ ) {
    Edge *edge = *it;
    assert( edge );
    if( edge->getEnd( this ) == &node2 ) {
      return edge;
    }
  }
  return NULL;
}


//******************************************************
//
// Class Edge
//
//******************************************************

template<class NData, typename EData>
Graph<NData,EData>::Edge::Edge( Node &node1, Node &node2, const EData &data ) 
{
  n1 = &node1;
  n2 = &node2;
  value = data;
  mark = false;
}

template<class NData, typename EData>
Graph<NData,EData>::Edge::Edge( const Edge &edge ) 
{
  n1 = edge.n1;
  n2 = edge.n2;
  value = edge.value;
  mark = edge.mark;
}

template<class NData, typename EData>
Graph<NData,EData>::Edge::~Edge() 
{
}

template<class NData, typename EData>
Graph<NData,EData>::PNode Graph<NData,EData>::Edge::getEnd( const Node *node )
{
  if( node == n1 ) 
    return n2;
  else if ( node == n2 )
    return n1;
  return NULL;
}


#endif