#pragma once
#include <QSet>
#include <QStack>

#include "Task.h"

struct TaskGroups{

	static QVector< QList<Task*> > split( QList<Task*> list, Structure::Graph * graph )
	{
		QVector< QList<Task*> > groups;

		// Visited tasks or not
		QMap<Node*,bool> visited;
		foreach(Task* t, list) visited[t->node()] = false;

		// Tasks from nodes
		QMap<Node*,Task*> taskMap;
		foreach(Task* t, list) taskMap[t->node()] = t;

		// Start splitting into groups
		foreach(Task* t, list)
		{
			QList<Task*> curSet;

			QStack<Task*> tasksToVisit;
			tasksToVisit.push( t );
			if( visited[t->node()] ) continue;

			while( !tasksToVisit.empty() )
			{
				Task * curTask = tasksToVisit.pop();
				Structure::Node * curNode = curTask->node();
				if(visited[curNode]) continue;

				visited[curNode] = true;
				curSet.push_back( curTask );

				QVector<Node*> adjNodes = graph->adjNodes(curNode);

				foreach( Structure::Node * adj, adjNodes )
				{
					if( visited.keys().contains(adj) && !visited[adj] )
					{
						Task * adjTask = taskMap[adj];

						tasksToVisit.push( adjTask );
					}
				}
			}

			groups.push_back( curSet );
		}

		return groups;
	}

	struct Graph
	{
		typedef QSet< Structure::Node* > QSetNode;
		typedef QVector<Structure::Node *> QVectorNode;

		QSetNode nodes;
		QMap< Structure::Node*, QSetNode > edges;
		QMap< Structure::Node*, QMap<QString,QVariant> > nodeProperty;

		Graph(QList<Task*> list, Structure::Graph * graph)
		{
			// Tasks from nodes
			QMap<Node*,Task*> taskMap;
			foreach( Task* t, list ) taskMap[t->node()] = t;

			// Add to graph
			foreach( Task* t, list )
			{
				Structure::Node * n = t->node();
				nodes.insert( n );
				nodeProperty[n]["task"].setValue( taskMap[n] );

				foreach( Structure::Node * adj, graph->adjNodes(n) )
				{
					if( !taskMap.keys().contains(adj) ) 
					{
						nodeProperty[n]["isBoundary"] = true;
						continue;
					}

					// Add node
					nodes.insert(adj);
					nodeProperty[n]["task"].setValue( taskMap[n] );

					// Add edges (undirected)
					edges[n].insert(adj);
					edges[adj].insert(n);
				}
			}

			/// Drop the "boundary" property when:

			// 1) For group of two, one will not be
			if(list.size() == 2)
			{
				Node * first = list.front()->node();
				Node * last = list.back()->node();
				Structure::Node * n = graph->valence(first) < graph->valence(last) ? first : last;
				nodeProperty[n]["isBoundary"] = false;
			}

			// 2) For boundary nodes connecting with many boundary
			foreach(Structure::Node * n, boundaryNodes()){

				// Count number of neighboring boundaries 
				int numBoundary = 0;
				foreach( Structure::Node * adj, graph->adjNodes(n) ){
					if(nodeProperty[adj]["isBoundary"].toBool())
						numBoundary++;
				}

				// Drop property
				if(numBoundary == 1)
					nodeProperty[n]["isBoundary"] = false;
			}
		}

		void clearProperty(QString propertyName, QVariant value){
			foreach(Structure::Node* n, nodes){
				nodeProperty[n][propertyName] = value;
			}
		}

		void removeNode(Structure::Node * n){
			foreach(Structure::Node * adj, edges[n])
			{
				// Assign neighbor as boundary
				nodeProperty[adj]["isBoundary"] = true;

				// Erase edge
				edges[adj].remove(n);
				edges[n].remove(adj);
			}

			// Erase node
			nodes.remove(n);
		}

		QVector<Structure::Node *> boundaryNodes(){
			QVector<Structure::Node *> b;
			foreach(Structure::Node* n, nodes){
				if(nodeProperty[n]["isBoundary"].toBool())
					b.push_back(n);
			}
			return b;
		}

		QVector< QList<Task*> > peel()
		{
			QVector< QList<Task*> > layers;

			while( nodes.size() )
			{
				QList<Task*> btasks;
				QVectorNode bnodes = boundaryNodes();

				foreach(Structure::Node * bnode, bnodes){
					btasks.push_back(nodeProperty[bnode]["task"].value<Task*>());
					removeNode(bnode);
				}
				
				if(!btasks.size()) break;

				layers.push_back( btasks );
			}

			return layers;
		}
	};

};