#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include "Command.h"
#include "GraphManager.h"
using std::cout;
using std::endl;

list< list<Node> >::iterator
BuildStrongComponents::findFront(list< list<Node> >& adjList, 
                             list<Node>::iterator target) const {
  string target_name = target->getName();
  for ( list< list<Node> >::iterator ptr = adjList.begin();
         ptr != adjList.end();
         ++ptr ) {
      list<Node>::iterator this_class = ptr->begin();
      string name = this_class->getName();
      if ( name == target_name ) return ptr;
   }
   cout << target_name + string(" Not found in BuildStrongComponents::findFront")
        << endl;
   return adjList.end();
}

void BuildStrongComponents::printCycles(const list<Graph>& comp) const {
   int count = 0;
   cout << endl;
   for ( list<Graph>::const_iterator ptr = comp.begin();
         ptr != comp.end();
         ++ptr ) {
      Graph graph = (*ptr);
      cout << ++count << ". The New Graph: " << endl;
      cout << graph << endl;
   }
}

void BuildStrongComponents::printReverseDfsNumbering() const {
  Graph graph = GraphManager::Instance()->getGraph();
  list< list<Node> > adjList = graph.getAdjList();
  int count = 0;
  for ( list< list<Node> >::iterator ptr = adjList.begin();
         ptr != adjList.end();
         ++ptr ) {
      list<Node>::iterator this_class = ptr->begin();
      if ( this_class->isVisited() ) { 
         ++count; 
         cout << "Class: " << this_class->getName()
              << ", dfs: " << this_class->getDFSnumber()
              << endl;
      }
   }
   cout << count << " nodes were visited" << endl;
}

void BuildStrongComponents::printVisited() const {
  Graph graph = GraphManager::Instance()->getGraph();
  const list< list<Node> > adjList = graph.getAdjList();
  for ( list< list<Node> >::const_iterator ptr = adjList.begin();
         ptr != adjList.end();
         ++ptr ) {
      list<Node>::const_iterator this_class = ptr->begin();
      string name = this_class->getName();
      if ( ptr->size() > 1 ) {
         ++this_class; // skip the first one, 'cuz it's the header
         while ( this_class != ptr->end() ) {
            if ( !this_class->isVisited() ) {
               cout << this_class->getName() << " not visited\n";
            }
            else if ( this_class->isVisited() ) {
               cout << this_class->getName() << " IS visited\n";
            }
            ++this_class;
         }
      }
   }
}

void BuildStrongComponents::buildGReverse(list< list<Node> >& adjList,
                                          Graph& graph) {
  for ( list< list<Node> >::iterator ptr = adjList.begin();
         ptr != adjList.end();
         ++ptr ) {
      list<Node>::iterator this_class = ptr->begin();
      Node new_node(*this_class);
      new_node.markNotVisited();
      graph.insert( new_node );
   }
  for ( list< list<Node> >::iterator ptr = adjList.begin();
         ptr != adjList.end();
         ++ptr ) {
      list<Node>::const_iterator this_class = ptr->begin();
      string source = this_class->getName();
      if ( ptr->size() > 1 ) {
         ++this_class; // skip the first one, 'cuz it's the header
         while ( this_class != ptr->end() ) {
            // add a edge with source & dest reversed:
            Edge edge(this_class->getName(), source, this_class->getEdgeType(),
                      this_class->getEdgeCount(), this_class->getWeight());
            graph.addEdge(edge);
            ++this_class;
         }
      }
   }
}

void BuildStrongComponents::assignReverseDFSnumber(list< list<Node> >& adjList, 
                            list< list<Node> >::iterator ptr) {
  list<Node>::iterator this_class = ptr->begin();
  this_class->markVisited();
  //ptr->begin()->setDFSnumber(++dfsNumber);
  ++this_class;
  while ( this_class != ptr->end() ) {
     list< list<Node> >::iterator frontPtr = findFront(adjList, this_class);
     if ( !(frontPtr->begin()->isVisited()) ) {
        assignReverseDFSnumber( adjList, frontPtr );
     }
     ++this_class;
  }
  ptr->begin()->setDFSnumber(++dfsNumber);
}

void BuildStrongComponents::buildStrong(list< list<Node> >& g_rev,
                            list< list<Node> >::iterator& ptr,
                            Graph& graph, int currentLargest) {
  list<Node>::iterator this_class = ptr->begin();
  this_class->markVisited();
  string source = this_class->getName();
  graph.insert(Node(source, "header", 1, 0));
  ++this_class;
  while ( this_class != ptr->end() ) {
     list< list<Node> >::iterator frontPtr = findFront(g_rev, this_class);
     string dest = this_class->getName();
     if ( frontPtr->begin()->getDFSnumber() <= currentLargest ) {
        string edge_type = this_class->getEdgeType();
        Edge edge(source, dest, edge_type, this_class->getEdgeCount(),
                  this_class->getWeight());
        graph.addEdge(edge);
     }
     if ( !(frontPtr->begin()->isVisited()) ) {
        buildStrong( g_rev, frontPtr, graph, currentLargest );
     }
     ++this_class;
  }
}

void BuildStrongComponents::reverseEdgesInStrongComponents() {
   for ( list<Graph>::const_iterator ptr = strongComponents.begin();
         ptr != strongComponents.end();
         ++ptr ) {
      Graph source_graph = (*ptr);
      Graph target_graph;
      buildGReverse(source_graph.getAdjList(), target_graph);
      cycles.push_back( target_graph );
   }
}

void BuildStrongComponents::execute() {
  // First, get reverse depth-first numbering:
  list< list<Node> > adjList = graph.getAdjList();
  for ( list< list<Node> >::iterator ptr = adjList.begin();
         ptr != adjList.end();
         ++ptr ) {
     if ( !(ptr->begin()->isVisited()) ) {
        assignReverseDFSnumber( adjList, ptr );
     }
  }

  // Second, Build G-Reverse:
  buildGReverse(adjList, gReverse);

  // Third, use dfs on G-Reverse to find cycles;
  // start with highest numbered Node by sorting G reverse;
  sortGreverse();

  // Now, find the cycles, using highest number Node;
  // Store the cycles in strongComponents
  list< list<Node> >& g_rev = gReverse.getAdjList();
  for ( list< list<Node> >::iterator ptr = g_rev.begin(); 
        ptr != g_rev.end(); 
        ++ptr ) {
     if ( !(ptr->begin()->isVisited()) ) {
        Graph graph;
        buildStrong( g_rev, ptr, graph, ptr->begin()->getDFSnumber() );
        strongComponents.push_back( graph );
     }
  }
  reverseEdgesInStrongComponents();
  //printCycles(strongComponents);
  //printCycles(cycles);
}