#include <iostream>
#include <string>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>

#include "Interface.h"
#include "Graph.h"
#include "CostModel.h"

using std::cout;
using std::endl;
using std::string;
using std::map;
using std::list;
using std::queue;
using std::stack;
using std::vector;

class CompareGreater {
public:
   bool operator()(const list<Node>& lhs,
                   const list<Node>& rhs) const {
      return lhs.begin()->getDFSnumber() > rhs.begin()->getDFSnumber();
      return true;
   }
};

class SearchClassJar {
public:
   SearchClassJar(const string& n) : name(n) {}
   bool operator()( Container<Class_Info>::const_iterator& ptr ) const {
      return ptr->getName() == name;
   }
private:
   string name;
};

class Command {
public:
   Command(const string& n) : name(n) {}
   virtual ~Command() {}
   const string & getName() const { return name; }
   virtual void execute() = 0;
   virtual void undo() {}
private:
   string name;
   Command() : name("unknown") {}
};

class BuildGraphCommand : public Command {
public:
   BuildGraphCommand(const string & fn ) 
			: Command("BuildGraph"), fileName(fn), nestedClassCount(0) {}
   void execute();
   int getNestedClassCount() const { return nestedClassCount; }
private:
   string fileName;
   int nestedClassCount;
   vector< Container<Class_Info>::const_iterator > cinfoPtr;
   void printCinfoPtr() const;
   BuildGraphCommand(); 
   void checkForPolymorphicEdges(const string&, const string&);
   bool isTemplate( const string & ) const;
   void buildStuffInNamespace(const Container<NameSpace_Info>&);
   void buildClasses(const Container<Class_Info>& classes);
   void BuildGraphCommand::printTypeInfo(
                        Container<Variable_Info>::const_iterator);
   void doNestedClassInfo(const string&, 
                          const Container<Class_Info>&);
   void doClassVariableInfo(const string&, 
                            const Container<Variable_Info>&);
   void doClassFunctionInfo(const string&, 
                            const Container<Function_Info>&);
   void processFunctionLocals(const string&, 
                            const Container<Variable_Info>&);
   void addEdge(const Edge&);
};

class BuildStrongComponents : public Command {
public:
   BuildStrongComponents(const Graph& graph)
      : Command("BuildStrongComponents"), graph(graph), cycleCount(0) {}
   void execute();
   void printReverseDfsNumbering() const;
   void printCycles(const list<Graph>&) const;
   list<Graph> getCycles() const { return cycles; }
private:
   Graph graph;
   int cycleCount;
   static int dfsNumber;
   Graph gReverse;
   list<Graph> strongComponents;
   list<Graph> cycles;

   void buildGReverse(list< list<Node> >&, Graph&);
   void assignReverseDFSnumber(list< list<Node> >&, 
                               list< list<Node> >::iterator);
   void buildStrong(list< list<Node> >&,
                    list< list<Node> >::iterator&,
                    Graph&, int);
   void sortGreverse() {
      list< list<Node> >& g_rev = gReverse.getAdjList();
      g_rev.sort(CompareGreater());
   }
   void reverseEdgesInStrongComponents();
   list< list<Node> >::iterator
   findFront(list< list<Node> >&, list<Node>::iterator) const;
   void printVisited() const;
};

class InvalidCommand : public Command {
public: 
   InvalidCommand() : Command("InvalidCommand") {}
   void execute();
};

class BreakCyclesCommand : public Command {
public: 
   BreakCyclesCommand(const CostModel& m, const Graph& graph);
   void execute();
   bool checkForCycles() const;
   void printComponents(const list<Graph>&) const;
   Graph getEdgesRemoved () { return edgesRemoved; }
   static int getBreakCount() { return breakCount; }
private:
   CostModel model;
   Graph cycles;
   Graph edgesRemoved;
   list<Graph> graphList;
   static int breakCount;
};

class FindOrderCommand : public Command {
public: 
   FindOrderCommand(const Graph& g, const map<string,int>& in) 
      : Command("FindOrderCommand"), graph(g), indegrees(in) {}
   void execute();
   stack<Node> getOrder();
private:
   Graph           graph;
   map<string,int> indegrees;
   queue<Node>     zeros;
   stack<Node>     order;

  void findZeros();
};